3. Методы классификации, основанные на описании классов ядрами.

«Ядерные» методы нацелены на выявление сгущений ОТЕ в признаковом пространстве и ранее носили чисто эвристический характер, так как понятие компактности ОТЕ в признаковом пространстве не было формализовано. Для ряда эвристических процедур с развитием теории были найдены функционалы качества разбиения на группы и тем самым формализовано соответствующее им понятие компактности [С. А. Айвазян и др., 1989. - С. 217]. В соответствии с этим алгоритмы классификации, основанные на описании классов ядрами, под­разделяют на эвристические и оптимизационные. Кроме того, методы можно разделить по способу подачи ОТЕ на вход алгоритма. Если ОТЕ подаются по одному (последовательно), то соответствующие процедуры называются после­довательными. Если на вход алгоритмов подаются сразу все ОТЕ, то они назы­ваются параллельными. Преимуществом последовательных процедур является высокая скорость работы, параллельных - независимость получаемой класси­фикации от порядка ОТЕ в исходном множестве О.

14

Под ядром класса подразумевается некоторая реально существующая ус­ловная наиболее «представительная» ОТЕ, весь комплекс характеристик кото­рой является эталоном данного класса. Часто алгоритмы, основанные на описа­нии классов ядрами, используют процедуру классификации ОТЕ к ядрам по минимальности расстояний:

• задаться метрикой d;

• найти ядра классов;

• классифицировать все ОТЕ к ядрам по минимальности расстояния до них.

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

Некоторые эвристические подходы к выбору ядер. Некоторые эвристи­ческие формализованные процедуры выбора ядер классов известны уже более двух десятков лет [В. С. Тикунов, 1978].

Во-первых, отыскивать ядра классов можно исходя из принципа макси­мальной гетерогенности. Например, в качестве первых двух ядер можно вы­брать две ОТЕ, наиболее отличающиеся между собой по комплексу показате­лей. Далее, если уже имеется (К-1) ядер, в качестве К-го ядра выбирается ОТЕ, наиболее отличающаяся от (К-1) ядер.

Другой принцип формирования ядер основывается на выделении макси­мально гомогенных классов ОТЕ. При выборе ядер классов необходимо, чтобы при отнесении к ним оставшихся ОТЕ по минимальности расстояния (и полу­чении таким образом системы классов) используемый функционал качества классификации достигал своего экстремума (максимума или минимума, в зави­симости от интерпретации функционала качества).

Еще одним «ядерным» эвристическим алгоритмом является метод после­довательного выделения ядер. В основе этого метода лежит предположение о том, что классы находятся друг от друга на некотором расстоянии с, превы­шающем внутриклассовые расстояния между ОТЕ. Алгоритм начинает свою

15

работу с формирования первого ядра, которым становится 0\. Далее, на каждом следующем шаге алгоритма рассматривается очередная ОТЕ О,

Если существует j-e ядро, расстояние от которого до 0, меньше порога с, О, относится у- му классу. В противном случае 0, формирует новый класс и стано­вится его ядром.

Недостатками алгоритма являются: необходимость выбора порогового значения с и зависимость результатов от последовательности поступлений ОТГ на вход классификатора (т.е. на одном и том же наборе ОТЕ могут быть полу­чены разные варианты классификации, в зависимости от их нумерации). Вто­рой недостаток является общим для всех последовательных процедур.

Метод к-средних. Метод k-средних является одним из самых известных параллельных оптимизационных алгоритмов классификации данных, основан­ных на описании классов ядрами. Идея алгоритма заключается в постоянном пересчете ядер классов, что позволяет в процессе его работы выйти на реальную структуру сгущений ОТЕ в признаковом пространстве. С формальной точки зрения алгоритм минимизирует суммарный разброс ОТЕ вокруг ядер.

Несомненным преимуществом алгоритма является лучшее нежели без пересчета ядер классов, качество классификации, способность находить истин­ные ядра и скопления ОТЕ в признаковом пространстве. Недостаток алгоритма - большое количество вычислений.