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

Объект 2 в равной мере принадлежит классам 2 и 3; объект 7 близок ко всем 3 классам. Такое представление позволяет углубить анализ. Такая же матрица может быть получена, если отнормировать расстояния каждого объекта до всех кластеров (см. 3.4). 50. Реализуется алг. 37, но не до стабилизации разбиения, а до получения <естественного» числа классов.

Это достигается варьированием порогов )с и р; при некоторых их значениях число классов, которое убывает при росте !с и снижении р, становится стабильным для целого спектра значений параметров. Представляет собой типичный пример сложно организованной процедуры, носящей в себе черты имитационного эксперимента. На основании перечисленных в табл. 2.3 алгоритмов можно придумать немало подобных процедур. 51.

Произвольным образом (случайно, экспертным путем или алгоритмически) выбирается некоторая система эталонных множеств Еь..., Я. Каждое из них преврашается в класс по принципу максимальной типичности точек; в частности, при 1р=)г, если классы объекты з 9 О 1 О б б 9 1 О 9 2 1 7 9 О 3 3 4 9 2 О г 2 О 9 ю Рис. 2.!3. Рис. 2.!4 63 рв(Р, то а;ен5!. Затем строится такая система эталонов, чтобы минимизировать нетипичность классов ф при заданных их численностях и! (например, разделяют непохожие эталоны).

Затем снова следят за ~р и т. д. вплоть до устойчивых классов. В [5) подробно описаны условия сходимости алгоритмов такого типа. 52. Подробного описания процедуры проводить не будем; это сделано в [5, с. 105 — 106]. Как видно из используемых параметров, общая схема базируется на основных идеях эталонных алгоритмов, восходящих к алг. 36, 37, 39 и др. Оказывается, алгоритмы такого типа могут быть широко использованы и для оптимизационных постановок (см. 2.3). 2.2.3А. Алгоритмы типа разрезания графа 53. Из полносвязного графа размерностью )УХУ удаляются последовательно дуги с самыми большими расстояниями до тех пор, пока граф не распадается на несколько несвязанных подграфов. Фактически в [88] дуги убирались по некоторым пороговым величинам, полученным из анализа гистограммы расстояний,— отбрасывались расстояния, большие или равные межклассовым; если изолированных групп не появлялось — снижалась пороговая величина и процедура повторялась. Гистограмма расстояний при хорошей структурированности имеет вид, приведенный на рис.

2.15, где А — межкластерные расстояния,  — внутрикластерные, так что пороговое значение 4( обычно можно нащупать. Вообще такое графическое представление данных очень полезно и в смысле интерпретации (см. 3.4), и в теоретическом аспекте (см. о распределении расстояний 1.1). 54. Строится кратчайший незамкнутый путь (КНП) (иногда его называют оптимальным деревом или дендритом [7!), минимальным покрывающим деревом [32, с.

260) и др.) следующим образом. Соединяются ребром две ближайшие точки, затем отыскивается точка, ближайшая к любой из уже рассмотренных точек, и соединяется с ней и т. д. до исчерпания всех точек. Такой способ объединения повторяет метод ближайшего соседа.

Процедура аналогична алг. 29, но там она начинается с произвольной точки, Рис. 2.!6. Рис. 2Л6. 64 а не с пары ближайших точек. В найденном КНП отбрасывают ь — 1 самых длинных дуг и получают й классов. На рис. 2.!б !(!) - !(2)!(з', следовательно, прн я=2 надо разрезать дугу длиной !(!, при я=4 — дуги с длинами и! — и». Метод позволяет выделять кластеры произвольной формы. 55. Строится КНП, все его дуги упорядочиваются по длине: о!) 42..., затем опРеделЯютсЯ й»=-!-, „,, пл ! — — ~г —, Если д„(й»+!, выделяются алг.

54 й классов; если таких случаев несколько, выбирается наименьшее й. Такая эвристика не всегда является удачной. Можно предложить другие: например, каждой дуге сопоставить максимальный из прилагающих к ней отрезков и разрезать граф там, где это отношение больше единицы, а у соседних ребер — меньше. 56. Из полного графа сходства случайным образом производится выборка вершин, между которыми строится КНП (см. алг. 54). Запоминаются все его звенья и частоты нх повторяемости.

Звенья с частотами, большими (;1, рассматриваются как межклассовые и отбрасываются, т. е. происходит разрезание графа. Процедура основана на том факте, что межклассовых расстояний всегда л, 1л — 11 больше, чем внутриклассовых: если последних Я вЂ” [-2 — ~, то 1=! первых П л,л,. Поэтому наиболее часто попадающиеся звенья и « можно интерпретировать как межклассовые, не обращая внимания на их длину. Алгоритм является первой процедурой «случайной кластеризации», перспективной для больших массивов данных (см. 2.2.3).

57. См. алг. 13 и [59[. 2.2.3.». Прочме и момбмнмрованные апгормтмы 58. Поскольку теория персептронов широко известна [20, 32 и др.[, мы не будем описывать сам алгоритм, а укажем лишь на его идею. Персептрон представляет собой устройство порогового типа, предназначенное для перевода входных объектов в классы образов. Это осуществляется настройкой коэффициентов разделяющей функции в процессе обучения.

Если же обучения нет, то для самообучения надо задать какие-то начальные значения порогов, которые потом пересчитываются. Но это, как выяснилось, приводит в большинстве случаев к неустойчивым классификациям либо к устойчивым, но тривиальным (типа попадания всех объектов в один класс). Видимо, дело в трудности правильного задания весов, ибо оно фактически предполагает знание структуры обрабатываемых данных.

З злк. !!!л 65 59. Шаг 1 — все расстояния в матрице заменяются на нули и единицы (а(;=1, если с(п(а равно нулю в обратном случае); р — выделяются все компактные группы, такие, что все расстояния внутри них единичны, а вне их — нулевые. Это может осуществляться подбором объектов друг к другу с проверкой условий (как у алг. 25 — 30). Классы могут пересекаться. Затем удаляется самый большой класс, изменяются остальные, удаляется следующий и т. д. до исчерпания множества. Фактически это можно назвать «методом масок» (см. алг.

33). 60. Осуществляется некоторая рекуррентная процедура пересчета коэффициентов разделяющих плоскостей, которая сводится к определению первых собственных чисел матрицы ковариаций и их собственных векторов. Классификация сначала проходит по ортогональной плоскости, задаваемой 2-й компонентой. Такое разделение может дать не только хорошие (см. А на рис. 2.17), но и далекие от истины результаты В и С. В принципе процедура напоминает лингвистический анализ (см. 1.1) в его упрощенном варианте. Вопросы использования компонентного анализа в задаче классификации рассмотрены в 3.1. 61. Каждый объект формирует свой первичный класс по принципу: а;ы51, если рии-.К.

Пусть а( — центр 1-го класса 5(. Тогда класс 5~ формируется из всех таких точек, которые включены в 5ь а также если а;~5(, то 5~ =Ц5!. Класс 51 на рис. 2.18 состоит ияж из объектов 1, 2, 3, а класс 5~ включает еще объекты 4, 5, поскольку они попали в )с-окрестности точек 2 и 3, входящих в 5(. Можно задавать несколько центров, удалять точки последова-. тельно и т.

д. Алгоритмы интересно сравнить с алг. 66, где осуществляется не объединение, а пересечение пороговых областей. 62. Выбирается максимальный радиус !сь при котором существует хотя бы один кластер мощностью лс»ль Этот самый плотный кластер удаляется, пороговое значение увеличивается, затем отыскивается менее плотный кластер и удаляется и т. д. Можно менять и кч на каждом шаге. Рис.

2.!7. Рис. 238. 63. Шаг 1 — находится ближайшая пара объектов, и с нее начинается формирование первого класса: а~~5~, если А;<Х При этом следят за другими условиями: чтобы ближайший к включенному в 5, объекту а, объект а,~5~ был не ближе к 5~, чем а. Таким образом получают классы, в которых диаметр меньше Н, а расстояние между классами не меньше А. 64. При заданном 1г, желательно небольшом, находят по алг. 44 й')й классов.

Их центры соединяют КНП (см. алг. 64), из которого удаляется й — 1 максимальных вершин и получают Й классов. Классы получаются более сложной формы, чем гиперсферы (рис. 2.19). Здесь важна идея двухэтапности классификации: сначала выделить заведомо компактные маленькие группы, затем произвести их разбиение. Так можно успешно классифицировать весьма большие массивы информации (см. 4.3). 66. Кластерами считаются некоторые скопления точек в сферах определенной формы, а именно — кубоидах (параллелепипедах) и эллипсоидах (ограничимся рассмотрением кубоидов, так как результаты идентичны). Начальные размеры кубоида по каждой оси определяются формально как некоторые доверительные интервалы 5;.

Затем центр первого кубоида помещается в случайную точку либо в заранее определенное место. Определяется геометрический центр тяжести точек, попавших в данный объем, и если разница между ним и первоначальным центром меньше некоторого порога (например, 5,/10 по каждой оси 1!26]), первоначальный центр сдвигается, делается пересчет и т. д.

Доказано, что процесс поиска окончательного места для кластера сходится (для двух форм кластеров). Затем этот кластер исключается из рассмотрения и процесс повторяется. После размешения всех кластеров задается еше один порог 6 (снова как функция от 5;), с помощью которого выделяются зоны высокой плотности.

Первая часть алгоритма, как видно, весьма напоминает «Форзль» (см. алг. 44, 64) с той разницей, что перемешение объемов идет «скачкамн», в соответствии с порогамн. Выбор порога здесь весьма условен (например, связан с доверительной вероятностью), но привлекательна идея работы с отдельными осями пространства, без использования расстояний, чем метод похож на алг. 19. Можно найти, видимо, другие эвристические приемы, Реализующие перемещение объемов в исходном пространстве. 66. В [154[ изложение имеет сильную вероятностную окраску, так как опирается на результаты автора в этой области. В частности, важную роль в данном алгоритме играют функции плотности в классах, мы же остановимся только на идейной стороне метода, рассматривая расстояния в общем виде. На первом шаге методом й-средних отыскивают кластеры таким образом, чтобы сумма квадратов внутрикластерных отклонений от средних не уменьшалась перемещением объекта из класса в класс (алг.