И.Д. Мандель - Кластерный анализ (И.Д. Мандель - Кластерный анализ.djvu), страница 14

По резкому изменению разности надо выделять пунктирное разбиение. Если принять порог Лр(3, то разбиение — сплошное. 28. Реализуется алг. 27, но строится график изменения средней связи объектов с классом, на котором резкие впадины интерпретируются как границы классов. 29. Осуществляется алг. 26, но в качестве меры близости объекта к классу выбрано его минимальное расстояние до какого- либо объекта класса.

30. Выпуклой называется симметрическая матрица, у которой все элементы (выше диагонали) не убывают с ростом номера по строке. Алгоритмы [61[ позволяют построить матрицу, максимально близкую к выпуклой (так как точного решения может не быть), и здесь не приводятся. На «почти выпуклой» матрице выделение классов проводится визуально или автоматически (см. алг. 23, 25). 3!. Инверсией расстояния называется модуль разности рангов этого расстояния в исходной матрице (по строке) и в выпуклой матрице (см. алг.

21). Сумма всех инверсий характеризует близость данной матрицы к абсолютно выпуклой матрице и должна быть минимизирована. Предлагается несколько алгоритмов минимизации. В [41] приводится один из них, доставляющий локальный минимум этой суммы. Его основным шагом является перенос в левую часть матрицы столбца с максимальной инверсией. Похожие эвристические процедуры описаны в [130[. 2.2.3.3.

Процедуры эталонного тнла 32. Если в качестве близости к эталону брать каное-либо расстояние и в качестве эталона — сформированный алгоритм, то процедура составной частью войдет во многие нзлагающиеся ниже схемы расчетов. 33. Выбирается случайным образом й точек, объявляемых центрами классов (сферы должны покрывать все объекты, иначе надо менять й). Каждый объект описывается булевским вектором длиной й (маской): если аи()7, то в векторе стоит 1, если с(а))7, то — О.

Класс составляют объекты с одинаковыми илн наиболее похожими масками. На рис. 2.10 маски объектов для классов с центрами в 2, 5, 7: М1 (1, О, 0), Мз (О, 1, 0), Мр (О, 1, 0), Мр (О, 1, 0), Ми (О, 1, 1) Классы: 1, 2/3, 4, 5/б, 7. Объект 8 может попасть в любой из двух классов. 34. Выполняется процедура, близкая к алг. 33, но эталоны выбираются не случайно: либо из некоторых экспериментальных [20], либо из общих качественных [30] соображений. 35.

Случайный объект объявляется центром класса; все объекты, для которых рн«И, объявляются кластерами и исключаются из рассмотрения. В оставшемся множестве процедура повторяется; по версии Хнверинена [33] эталонами выбирают не случайные, а некоторые типичные точки. 36. Шаг 1 — случайный объект объявляется центром класса; р:а;ен50 если рн()7; если рн>р, а; является центром 5р, если И(рн(р, р(; выбывает из рассмотрения до следующего шага. Затем точка проверяется относительно каждого из двух кластеров и т. д. Центр тяжести пересчитывается как средневзвешенная величина.

КΠ— все точки распределены по классам (см. рис. 2.1!). 37. Берется й пуоизвольных точек (эталонов). Затем эталоны «огрубляются» по р: если р~р«..р, классы 5ь 5р заменяются одним классом со средневзвешенными параметрами. Огрубление кончается тем, что для всех 1, д рц)р, при этом й'(й. Затем извлекается точка и сравнивается ее расстояние до ближайшего эталона с )с. Если р(и))7, точка объявляется новым эталоном, проводится пересчет эталонов и т. д. При хорошем подборе р и )р в силу параллельности выбора классов результаты обычно лучше, чем в алг.

35. Рис. 2.!О. Рис. 2.! Ь 38. Задается несколько радиусов сфер )сь ..., Рь Если объект попадает в сферу, ее центр пересчитывается; если нет — объект объявляется новым центром. Процедура повторяется до полного распределения точек и представляет собой расширенный вариант алг. 35 и основу для алг. 44, где иной принцип стабилизации сферы (последовательный). 39. Шаг 1 — случайно выбирается й центров классов, каждый объект присоединяется к ближнему эталону; р-эталоны пересчитываются как центры тяжести классов. После пересчета эталонов объекты снова распределяются по ближайшим классам и т. д. КΠ— стабилизация процесса, т. е.

неизменность центров тяжести .классов. 40. Шаг 1 — выбирается й случайных эталонов„.р — точка аг относится к ближайшему классу, центр которого пересчитывается как новый центр тяжести. Следующий объект снова относится к ближайшему классу с пересчетом и т. д. КΠ— стабилизация центров классов. Само названне метод д-среднах, ставшее популярным, предложено дж. МакКином.

Но фактически алг. 39 ревлнзует идею того же метода с другим порядком стабнлнзапня, не последовательного для каждого класса, а параллельного длн всех классов. Поэтому мы решили назвать алг. 39 также методом Д-средннх. 41. Осуществляется алг. 40, после его окончания происходит перераспределение объектов по центрам (как в алг. 39) таким образом, чтобы сумма квадратов евклидовых расстояний от центров кластеров до входящих в них точек на каждом шаге уменьшалась (т. е. алгоритм приближается к оптимизационному — см. 2.3). Здесь, следовательно, синтезируются два основных процесса стабилизации.

42. Выбирается й случайных центров и объекты распределяются по ближайшим центрам (см. алг. 39). Затем в каждом классе проверяется для всех 1:ох!(о]. Если для одного признака неравенство не выполняется, 5г разбивают на два класса; в противном случае 5г пытаются объединить с каким-либо классом. Центры классов пересчитываются при изменениях, как в алг. 36, 40. Число классов меняется; КΠ— при сходимости процесса. Алгоритм привлекает естественностью выбора порога: для дисперсий его легче обосновать, чем для расстояний. 43.

Алгоритм является одной из «наиболее эвристических» процедур, что следует из обилия задаваемых параметров. Это может быть и слабой, и сильной стороной метода. В принципе он пригоден для диалогового общения человека с ЭВМ, но реализуется и в машинном варианте. При желании читатель может сам придумать схему кластеризации с данным набором порогов, ориентируясь на алг. 44, 42 и др. Полное описание алгоритма из 14 шагов приведено в [91, с. 112 — 116]. Упрощенное описание дано в виде схемы, заимствованной из [129, р. 107] с некоторыми изменениями (см. 60 Рис.

2Л2. рис. 2.12). Конкретные особенности (как именно разделять классы, как определять устойчивость и т. д.) могут, видимо, варьироваться. Так, в (129] предлагается вообще отказаться от априорного задания порогов, а рассчитывать их в процессе классификации. Конкретные способы их определения выглядят достаточно спорными и базируются на некоторых достаточно жестких посылках (например, порог для разделения классов зависит от предполагаемого закона распределения в классе и т.

д.). В целом надо отметить, что алгоритмы типа!БОРАТА являются одними из наиболее популярных, особенно у зарубежных исследователей. Фактически, как было видно, существует несколько их версий, в том числе довольно эффективная процедура гиггу (размытая) — 150РАТА 117, 145 и др.]. Подробного описания этих процедур приводить не будем. 44. Случайный объект объявляется центром класса, все объекты, такие, что ри()7, входят в первый класс.

В нем определяется центр 61 тяжести, который снова объявляется центром гиперсферы и т. д. до стабилизации сферы. Затем все попавшие в первый класс объекты изымаются и со случайным центром процедура повторяется. Можно делить совокупность и на-заданное число классов, тогда методом последовательных приближений следует менять радиус )7 — «Форэль-2». Доказана сходимость этой процедуры при любых начальных точках в конечных и бесконечных множествах 1! 81. Алгоритм весьма популярен; некоторые его модификации с функционалами качества разбиения рассмотрены в 2.5.

45. Отыскиваются два центра классов как самые удаленные друг от друга объекты; (-й центр определяется как самый удаленный в среднем от имеющихся центров. Объект а!~5!, если от всех остальных центров он удален максимально. Здесь использован новый способ распределения объектов по классам — не к ближайшему центру, как обычно, а к самому удаленному от остальных. 46. Первые два центра выбираются, как в алг.

45; пусть это а!, а,. Затем определяются расстояния до центров и делается проверка: шах(ш1п!1,!)(р? Если да, а, объявляется новым центром, !. д ч»!д пока не наберется й центров. Объекты распределяются по ближайшим центрам. 47. Для каждой точки а, формируется класс 5!гв;ев5!, если П! !(!! ~((7. Для всех 5! определяется частост!и с! = — т-, Все точки с с!)с объявляются эталонами, и проводится кластеризация одним из эталонных методов (например, й-средних).

Здесь, таким образом, в отличие от алг. 39 — 41, центрами могут быть не любые объекты, а точки с модальной плотностью окрестностей. Этот прием является весьма эффективным. 48. Для каждой точки определяется мо!цность класса, образованного радиусом Р, т. е. количество точек пь таких, что р,!(Я. Класс с максимальной мощностью убирается из рассмотрения; в оставшейся части множества пересчитываются классы, и процедура повторяется до исчерпания точек.

49. Процедура аналогична алг. 36, только вместо расстояния от центра Ю используется функция принадлежности объекта к классу 1х. Если 1х!!)1», а! включается в 5!. После первичного распределения можно использовать любой алгоритм стабилизации (алг. 39, 44 и др.); 1х можно вычислять различными способами, например, как в алг. 44. В силу того, что функция принадлежности либо не может быть явно задана, либо, напротив, задается простым образом через расстояния, частости и др., мы не считаем язык теории размытых множеств особенно удобным для теории классификации (как это делается, например, в [34) и др.].

Он универсален так же, как и язык бинарных отношений и «обычных» мер близости объектов, а принципиально новые конструкции с его помощью не получаются. 62 Но с точки зрения интерпретации полученных решений концепция размытых множеств весьма удобна. Если предположить, что ~ )аи =1, то решение задачи классификации можно представить в форме таблицы (рис. 2.13). По ней удобно оценить действительное распределение объектов по классам, используя те же посылки, что при рассмотрении матрицы факторных или компонентных нагрузок. Подчеркнуты числа (значения рт1, умноженные на 10), близкие к ! 0; они определяют довольно четкие классы 3, 4, 8/1, б, 8/ 5, !О.