И.Д. Мандель - Кластерный анализ (1185344), страница 16
Текст из файла (страница 16)
41). Затем определяют наличие ближайших соседей (среди классов) так: 2 класса называются ближайшими соседями, если среднее значение их объединения ближе к одному из классов, чем .к любому из других кластерных средних. Очевидно, число таких соседей может оказаться существенно меньше, чем число всех пар в~. Строится матрица расстояний, в которой конечные расстояния ставятся только между соседями, а для других пар с(!;=оо. К этой матрице применяется метод единственной связи (алг. 2).
Самое интересное здесь — элиминация больших расстояний. В [154] эта идея особенно не эксплуатируется, так как внимание уделяется в основном вероятностной проблематике, но с вычислительной точки зрения она представляется привлекательной и скорее всего может служить основой для создания быстрых процедур.
67. Для каждого объекта задан )сь который определяет гиперсферу. Областью взаимного поглощения называется такое пересечение гиперсфер, при котором их центры также находятся в этом пересечении. Все объекты в областях поглощения составляют классы. На рис. 2.20 заштрихованы области поглощения: !!! — 2, 3; Щ— 2, 1; = — 5, 6. Эти группы объектов и составляют классы, причем, как видно, объект 3 попадает сразу в 2 класса, а объект 4 не попадает никуда. При )т!=сонэ( для всех 1 алгоритм превращается в процедуру типа [35].
Рекомендации выбора Я! носят эвристический характер как среднее расстояние данного объекта до всех остальных или, в общем случае, как некий настроечный параметр. Могут быть сильные пересечения классов. 68. У каждого объекта упорядочиваются все расстояния от него до других объектов; затем вводится на этих порядках некая новая мера близости объектов, например, коэффициент ран- 4 говой корреляции, после чего данные обрабатываются какими-либо алгоритмами. Вариант: для каждого объекта отыскивается а ближайших к нему, пос- ! ле чего между этими векторами определяется мера близости (по Хеммингу и пр. [21[), либо класс формируется из Рис.
2.20. 68 тех объектов, которые пересекаются в в-окрестностях (зто похоже на алг. 67). В целом меры такого типа (часто используемые в многомерном шкалировании) весьма интересны, так как позволяют ~скрыть более точно топологию пространства (см. 1.2), но изучены они недостаточно. 2.2.4.ОВСРЖДЕНИЕ ОСНОВНЫХ ТИПОВ ПРОЦЕДУР Иерархические алгоритмы. Как можно было заметить, почти все иерархические алгоритмы (особенно агломеративные) отличаются друг от друга фактически только методом расчета расстояний между классами. Оказывается, многие способы пересчета можно задать по единой формуле с изменяющимися значениями параметров, предложенной Г.
Лансом и У. Уильямсом [5, 33, 34 и др.] и обобщенной М. Жамбю [135; 85, с. 124 — !37]. Формула имеет вид: 55Ш52 ! 55~+ 2 552+ 3 5152+ + 4(5+ 615,+ 615 + (2.)) где 54[)52 — класс, полученный объединением двух классов на предыдущей итерации и объединяемый на данной итерации с 5, 6(„з — РасстоЯние междУ множествами А и В; 1„— РасстоЯние, при котором произошло образование кластера А (т.
е. его уровень на дендрограмме); а4 — ат — коэффициенты, с помощью которых можно вести рекурсивный подсчет расстояний между кластерами на любом уровне. В формуле Ланса — Уильямса а4 — аз отсутствуют. Значения а~ — аз определяют различные функции расстояния между классами или величины, подобные расстояниям, которые имеет смысл минимизировать на каждом шаге алгоритма. В табл.
2.4, составленной на основе [123, 124, 137], приведены основные варианты значений параметров, которые определяют соответствуюшие алгоритмы. При анализе дендрограмм естественно считать, что объединение объектов на позднем шаге алгоритма осуществляется при более высоком значении расстояния, чем на раннем шаге, т. е. соблюдается монотонность. Однако в некоторых алгоритмах появляется немонотонность, что затрудняет анализ. Внимание исследователей привлекла задача: при каких значениях а~ — аз (ранее а2 — аз, ат) монотонность не будет нарушаться, т. е.
в дереве не будет инверсий. Решения ее В. Коппом [137], Г. Миллиганом, В. Батажеличем [115] были обобшены в 1984 г. Е. Диде и В. Моро в [123]. Показано, что инверсии отсутствуют, если справедливы неравенства: ат) — ш)п(аь аз); а4+аз)0, а,+аз+аз)1; а4)0, 1=4, 5, 6. (2.2) В частности, для алгоритмов «медиана» и «центроид» третье условие не выполнено, т. е. зти алгоритмы могут давать немонотонные деревья. 69 сч О Р О о ! о о о о о о о о о О о р р ь о о о о о р о р сс о о с~ ~с. ! ! сч Ю сс 1» сс сс сС 1» сч + - + й 66 » ъ ~н 66 сс — ~сс Ф й ч й й.
сЕ сс 3 й й о с "с а о Ф Ец й $ вс $ а» ,„з й й ч й ч й Ф й. й с ч й ч» й й а й ч .с В сс й а й а й К й й о » ч ф а» й й ч чс сс1 сС е ш сЛ щ 6 й» Е Е а '" с с о о ч й й й В л с й й й Е В й й а о ч й Е И й й ча с.с ЛЛ оо оо Х с Х о. ь а о у оо оо а а а Х о с О Оо а щ о а М о Х ОО Ю а а ь ЙЛ оо о Х с Х СЧ щ сч о ЛО о ас о Х щ ь щ ь а щ ой 'щ Х о .а уаа Х2щ а3 о ь 'Ххь, Я а»й Х Х Ф аыа и х И оо Хсб Х ХХ а ХО ыс йа ащь у с. щ ь Зо ~о~ ос йР ..Я' ..й а а 1~ у а а о С а о ~ ос ,. х" со а ь а ай Х ь», о щи и и х и \ ь ы ь а а з ХО Х С'3 щ а щ ыс х.|о со ~й а ао а а оу о.
Х Х о о. с щ и 1 с щ о а Х о. щ Х с щ с о щ ь о Х а Х Х о щ О + ~! и ш 1 ь с~ !». о о Х Х щ 'щ а ы а и а Х р щ у ИЙ й ь х о с у о а о щ й а о а о И+ Х~ Й+ ас ~~ Х 1! ы о. ь ! 'х и .Иь .!! ао ~.й Х Д Ф а о у а х й~ о. а с О О а ау х ь' о ы ! о ~" О) ХЖ с о) а о Х Н а о Х о а а щ с Х ь ( Х о ь а 71 Наличие условий (2.2) позволило авторам [123] сформулировать интересную постановку задачи классификации.
Пусть имеются некоторые иерархии или разбиения с известными межклассовыми расстояниями. В [123] для этой цели предлагается брать некоторые искусственные данные, в которых отражены предполагаемые свойства реального разбиения (например, наличие вытянутых кластеров и т. д.). Тогда (2.1) можно рассматривать как некоторое уравнение регрессии, в котором а~ — аг неизвестны, а остальные величины даны по обучающей выборке. Неравенство (2.2) следует рассматривать как ограничения и решать соответствующую регрессионную задачу с ограничениями (см., например, методы решения в [3, т.
2]). Найденные оптимальные значения параметров используются в классификации «большого» массива. Конечно, здесь возникает ряд вопросов, связанных с формированием обучающей выборки, но в целом идея частичного обучения выглядит многообещающей. В табл. 2.4 (алг. 13) приведены расчетные значения, полученные при двух обучающих примерах: первая строка — два плотных кластера с соединяющей цепочкой, вторая — два плоских параллельных кластера с цепочкой. По этим значениям параметров успешно распознались семь (из 1!) остальных фигур в [123] (полуторы с центром, вложенные полукольца и т. д.). Поскольку этот результат наилучший, параметры можно использовать непосредственно в других расчетах.
Данные первой строки напоминают по результатам значения, полученные методом ближнего соседа, второй — дальнего. Особый интерес представляют алг. 10 — 12. Их показатели удовлетворяют условию редуктивности (алг. 16) и используются в быстрых процедурах. В [85, с. !30 — !37] М. Жамбю названы еще несколько показателей такого типа, а Е. Диде приводит особые требования, при которых расстояния в (2.1) удовлетворяют этому условию (неравенства несколько отличны от (2.2) ).
Так что в целом можно сказать, что вопрос о быстрых иерархических процедурах теоретически решен достаточно полно. Что касается практики, то обычные алгоритмы требуют О(п') объема памяти, а редуктивные сокращают эти параметры на порядок. Так, в [!35] приводится пример обработки 5000 объектов за 7 мин. на 1ВМ-370. Другой путь ускорения процедур заключается не в полной кластеризации всего набора объектов, а в случайной классификации некоторых выборок исходных данных с тем, чтобы общие свойства разбиения с определенной вероятностью гарантировались для всего множества.
Разные схемы такого рода описаны в [1!3, 136] и обобщены О. Матулой [59, с. 83 — !11] (см. также [65] и алг. 51). Очень быстрый алгоритм со скоростью О(1ояп) описан; он тоже опирается на предварительное обучение, как и схемы вычислений в [123]. Вообще процедуры с частичным обучением представля- ' Мис1ег Д., 0азоиа гн. Арргохппапае 1аа1 пеагеа1 — пе1яьопг гесояпиюп// Раг.
гесояп. 1е11ега.— 1983.— Ч. 1.— р. 277 — 288. ,от собой промежуточное звено между «чистой кластеризацией» н классическим методом распознавания образов (см. также [145[ и р4. в 2.3). Точный ответ на вопрос о сферах применимости того или иного метода отсутствует. Общепризнано, что метод ближнего соседа имеет тенденцию к выделению цепочечно расположенных кластеров (см. рис. 2.2); метод дальнего соседа может на раннем этапе объединить довольно несхожие группы. В силу этих крайностей часто подчеркивают преимущество «умеренных» г-связывающнх процедур [84, с.
112 — 128[, но вопрос о выборе «хорошего» г остается открытым. У советских исследователей г-связывающие методы пока практически не нашли применения, хотя «обычные» алгоритмы используются широко ( [5, 34, 47, 74 и др.[, см. 4.2). В целом по иерархическим процедурам накоплена чрезвычайно богатая литература, что связано, видимо, с четкостью, изяществом и математической строгостью конструкций, позволяющих использовать развитой аппарат теории графов, ранговой статистики и т. д. для анализа алгоритмов. С точки зрения экспериментального сравнения этим алгоритмам также повезло — именно они чаще всего используются в искусственных полигонах (см.
2.4). Существенно то, что многие методы при своей внешней «непосредственности» на самом деле доставляют локальный экстремум какому-либо критерию (алг. 8, 16 и др., см. 2.3), так что они вполне вписываются и в рамки оптимизационного подхода. Важным достоинством иерархических алгоритмов является наглядность результатов работы, позволяющая тщательно изучить дендрограмму н сделать по ней выводы, причем желательно сравнивать несколько дендрограмм, полученных разными методами. Примеры использования алгоритмов даны в 4.3, 4.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
