Глава 7. АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ, ОСНОВАННАЯ НА ОПИСАНИИ КЛАССОВ «ЯДРАМИ»

7.1. Эвристические алгоритмы

Рассмотрим сначала методы автоматической классификации (АК), непосредственно опирающиеся на постановку задачи выделения в многомерном пространстве компактных групп точек. Такие методы и отвечающие им алгоритмы называются эвристическими, так как само понятие «компактная группа (облако) точек» не поддается строгой формализации. В прикладных задачах автоматической классификации они стали применяться одними из первых и до сих пор сохраняют большое значение в разведочном анализе данных благодаря наглядности интерпретации полученных результатов и, как правило, простоте реализации. Для ряда эвристических процедур с развитием теории АК были найдены функционалы качества разбиения на группы и тем самым формализовано соответствующее им понятие «компактности».

7.1.1. Параллельные процедуры.

Процедуры, в которых выборка вся сразу поступает на классификацию, называются параллельными.

Алгоритм k эталонов. Следуя [56], приведем типичный пример эвристического алгоритма, основная идея которого заключается в том, что совокупность объектов, находящихся на одинаковом расстоянии от каждого из k эталонов (ядер), образует компактную группу.

Пусть для классификации имеется выборка причем объект характеризуется вектором признаков .

Рассмотрим -мерное признаковое пространство вместе с функцией задающей в расстояние (либо степень близости).

Схема алгоритма

1. Выберем к эталонов и порог

2. Поставим в соответствие объекту - код из к двоичных символов где если в противном случае.

3. Разобьем выборку на классы, относя к одному классу объекты с одинаковым кодом.

В зависимости от порога и геометрии выборки число классов может варьироваться от 1 до Анализируя полученное разбиение выборки на классы, исследователь может уточнить выбор эталонов и перейти к следующей итерации алгоритма. Если в качестве эталонов взять векторы признаков объектов из данной выборки, то на вход алгоритма достаточно подать матрицу взаимных попарных расстояний . В [56] рекомендуется набор эталонов составлять из к случайно выбранных точек. Укажем наиболее важные модификации алгоритма, связанные со способом выбора эталонов:

а) эталоны строятся на основе представлений экспертов (или какой-либо другой априорной информации о типичных представителях классов);

б) эталоны берутся из векторов, соответствующих представителям заведомо разных классов, но не обязательно типичных в своем классе. При этом достоинством алгоритма является то, что число эталонов не обязано равняться числу классов;

в) эталоны могут пониматься в расширенном смысле, как ядра в методе динамических сгущений (см. п. 7.4).

Следующая модификация рассматриваемой процедуры связана с возможностью варьировать порог сходства.

Алгоритм взаимного поглощения. Рассмотрим процедуру автоматической классификации, целесообразность которой обосновывается в [58] правилом формирования сплоченных коллективов людей по принципу взаимного интереса и симпатии. Ключевым словом здесь является «взаимный», т. е. подразумевается, что отношение «объект 0, близок (интересен) объекту не симметрично и объекты ; объединяются, если не только О, близок к но и наоборот.

Схема алгоритма в предыдущих обозначениях алгоритма к эталонов:

1. Объекту поставим в соответствие порог называемый его радиусом влияния, т. е. объект считается близким к О, (находится в сфере влияния объекта ), если

2. Объекту поставим в соответствие код где если в противном случае.

3. Выделим в выборке классы, относя набор объектов к одному классу, если у их кодов все координаты с номерами равны I.

4. Выделим в выборке минимальное число классов, объединение которых дает всю выборку.

Ясно, что алгоритм дает в общем случае нечеткую классификацию выборки. Геометрически каждому объекту в признаковом пространстве отвечает шар радиуса с центром в точке Классу отвечает пересечение шаров содержащее все центры и называемое областью взаимного поглощения данного класса [58]. В ряде задач основной целью классификации является покрытие признакового пространства областями взаимного поглощения классов.

Ясно, что настройка рассматриваемого алгоритма на специфику решаемой задачи осуществляется выбором порогов . Приведем примеры такого выбора, взятые из [58]:

а)

б)

в)

Здесь — некоторая константа; — весовые множители. Они задаются либо эвристически, либо на этапе разведочного анализа служат управляющими параметрами.

7.1.2. Последовательные процедуры.

Процедуры, в которых элементы выборки поступают на классификацию по одному или малыми порциями, называются последовательными.

Приведем простой последовательный алгоритм классификации, в основе которого лежит предположение, что представители одного класса не могут быть удалены друг от друга более чем на заданную пороговую величину.

Пусть на классификацию объекты поступают последовательно, например по одному. Если исходная информация представлена в форме матрицы «объект — свойство», то параметрами алгоритма являются функция близости (расстояние) между объектами и пороговое значение если исходная информация представлена матрицей взаимных расстояний, то единственным параметром является пороговое значение

Схема алгоритма

1. Первый объект объявляется ядром первого класса.

2. Пусть на шаге выделено k классов с ядрами

Для поступившего объекта если , то относим к первому классу; если , то относим к классу;

если , то объявляется ядром нового класса.

Если функция удовлетворяет неравенству треугольника, как, например, когда — метрика, то объекты, отнесенные алгоритмом к одному классу, удалены друг от друга не более чем на