Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf

R описывается гиперсфера Сх. Находится центр тяжести Х 2 точек совокупности, попавших j b Сх. И з Х 2 радиусом R описывается гипер­ сфера С2 и определяется Х 3 центр тяжести точек исследуемой совокуп­ ности, попавших в С2. Процедура построения гиперсфер и точек X hпов­

торяется до тех пор, пока точки Х к не перестанут меняться. Точки совокупностщ попавшие в «остановившуюся» гиперсферу, принимаются за первый класс Sx. Для всех оставшихся точек, т. е. не попавших

ориентировочно оценить наиболее предпочтительное число классов для данной совокупности объектов. При этом основанием для выбора числа классов может служить многократное повторение одного и того же чис­

ла классов для нескольких последовательных значений RM и его рез­ кое возрастание на следующем шаге.

Если ставится задача разбить совокупность на заданное число клас­ сов, то одна из модификаций алгоритма «Форель-1» — «Форель-2» методом последовательных приближений позволяет находить минималь­ ный радиус R min, дающий разбиение на заданное число классов.

В общем случае с помощью алгоритмов типа «Форель» можно разби­ вать исследуемую совокупность на классы, имеющие более сложную форму, чем гиперсферы. А именно, такие классы аппроксимируются несколькими гиперсферами. Пусть нужно разбить совокупность на k классов. Процедура аппроксимации, состоит в следующем. Находим такое R, при котором совокупность разбивается на ш > 4 классов сцентрами (выборочными арифметическими средними каждого класса)

ными центрами в этом кратчайшем пути, занумерованы в порядке убы­ вания их величин. «Разрубив» ребро Ях, получим два подграфа КНП. Тогда все точки, принадлежащие классам с центрами, входящими в со­ став первого подграфа КНП, объединяются в один класс, остальные — в другой. Затем разрубается ребро Я,2)... и так до тех пор, пока мы не получим нужное число классов.

Покажем теперь, как процедура выделения одного класса точек из совокупности, являющаяся основой алгоритмов типа «Форель», может быть изложена в рамках описанной выше общей схемы «эталонных алго­ ритмов». Выделение класса точек из совокупности эквивалентно разде­ лению совокупности на два класса. В качестве набора эталонных мно­

способами, например так:

Ф (A, S lt Е) = 2 pi(A , X t). xi esl

ПО

3. Исследование иерархических и параллельных процедур «на допустимость»

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

В литературе известно несколько различных определений допусти­ мости [42], [64], [67]. Выбор того или иного из них зависит от содержа­ ния и природы исходных данных в каждой конкретной задаче. Ниже приводится достаточно широкий набор вариантов понятия «допусти­ мость», позволяющий исследователю подобрать наиболее подходящий для себя вариант, исходя из конкретной специфики своей задачи:

— допустимость в классе образов. Пусть 5 = {Si, S 2, ..., Sfe} не­ которое разбиение исходной совокупности элементов Xlt Х2, ..., Хп, занумерованных для удобства таким образом, что

•••, X j } , S 2 = - { X l l + 1 , . . . , X i 2 } , . . . , 5ft = {X;ji_i+ i, . . . , X J .

И пусть Yu ..., Yn — некоторое произвольное переупорядочивание элементов исследуемой совокупности. Тогда разбиение S' = (SI, ...,

Sk), где

в классе образов, если его нельзя улучшить переупорядочиванием объ­ ектов. Соответственно алгоритм называется допустимым в классе об­ разов, если он приводит к допустимому в классе образов разбиению;

— допустимость выпуклая. Разбиение S = (5Ь ..., S k) (и соответ­ ствующий алгоритм) называется выпукло допустимым, если выпуклые оболочки групп S1( ..., S k не пересекаются;

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

П1