И.Д. Мандель - Кластерный анализ (1185344), страница 13
Текст из файла (страница 13)
Для пары 1 — 5: 1) 1 — 2, 2 — 5 (2; 4,9); 2) 1 — 3, 3 — 5 (5; 1,2); 3) 1 — 4, 4 — 5 (6; 1,3). Здесь максимальное из максимальных расстояний равно 4,9. Другие объекты можно не проверять, так как максимальное расстояние для объекта 2 равно 4,9. Видно, что между любой парой объектов множества можно 1 — 2 8 в 8,2 построить путь длиной в 2 звена или мень- 2 — 4 4,8 4,8 ше, такой, что расстояние между соседними звеньями будет не больше 4,9. Это и есть з 2-диаметр. Аналогично строится 3-диаметр и т.
д., причем У вЂ” 1-диаметр равен минимальному расстоянию множества. Рис. 2.5 Получается, что г-связующие процедуры на своих «краях» имеют полносвязывающий метод (г — 1) и односвязывающий метод (чем и объясняются их названия) и в атом смысле являются более гибкими. Правда, трудоемкость выбора г-диаметра довольно велика, и к тому же приходится как-то фиксировать величину г [110].
В рассматриваемом сильном г-связующем методе предполагается, что объединение классов происходит, если их соединяет точно г связей определенной близости (равной г-диаметру) (см. алг. !2). !2. Первый шаг — как в алг. 1!. Классы объединяются, если имеется не менее г связей между ними. 13. Алгоритмы, обобщающие понятие г-связности за счет пересекающихся классов, особым образом устроенных клик графа и т. д. Здесь не приводятся, но представляют большой интерес. 14. Первый шаг — все объекты считаются одним кластером; задается некоторое определение кластера (см. 2.2.2), т. е. факти- чески тип порога с(; принимается Й~ =гпахЫч; р — порог '! принимает такое значение сх (с(ь что совокупность разделяется не менее чем на р кластеров; КΠ— каждый объект представляет собой класс. 15. Осуществляется алг.
1, но расстояние между классами определяется с помощью потенциальных функций (см. 2.3). 16. Рассмотренные выше процедуры направлены на определение мер близости классов, которые вычисляются как некоторая функция от собственно межкластерных расстояний. На зто и ориентирована общая формула пересчета расстояний Ланса — Уильямса (см. 2.2.4).
Однако можно исследовать и другие критерии агрегирования кластеров на каждом шаге, которые уже учитывают и внутренние свойства объединяемых кластеров. Впервые систематически зту идею стал реалнэовывать М. Жамбю [!551, причем в универсальной форме; во-первых, каждому объекту (а стало быть, к классу) были приписаны некоторые «массы» (веса), во-вторых, была обобщена формула Ланга — Уильямса (см. 2.2Л). Это дало возможность применять прн объеднненнн критерии мнннмнзацнн взвешенной н невзвешенной дисперсии в классах, критерий макснмнзацнн межнлассового разброса в разных формах, а также увязать задачу кластеризации с задачами корреляционного н факторного аналнза.
Все алгоритмы ориентированы на евклндово пространство (см. подробнее 2.2.4,). !7. В 1978 г. М. Брюиношем было введено важное понятие редуктивности расстояний, которое тесно связано с алгоритмами агломеративной классификации. Свойство редуктивности заключается в том, что некоторая )7-окрестность кластера, полученного объединением двух других кластеров, должна находиться внутри объединения )7-окрестностей исходных кластеров. Если зто справедливо для любых )г, то можно облегчить процедуру поиска кластеров, объединяемых на каждом шаге, отыскивая их среди кластеров, попавших в Й-окрестности рассмотренных на раннем шаге алгоритма 55 объектов. На рис.
2.6 кластеры 1 и 2 имеют некоторые окрестности (внешний пунктир); в окрестности 2 находится кластер 3. Прн объединении 1 и 2 получается кластер 1,2, окрестность которого, по свойству редуктнвности, находится внутри объединения окрестностей (внутренний пунктир). Следовательно, для присоединения к кластерам 1,2 кластера 3 достаточно просмотреть окрестности классов 1 и 2, а не проверять связь 1,2 — 4. Поскольку доказано, что при его справедливости прямые классификации н полученные по )2-окрестностям совпадают, зто дало основание М.
Жамбю построить целый ряд чрезвычайно быстрых процедур, позволяющих обрабатывать тысячи объектов. Но не все меры близости обладают свойством редуктивности, например используемые в алг. 2 — 9 (см. 2.2.4). На основе свойства редуктивности предложены аналогичные алгоритмы П.
Бензенкрн (1982), Ф. Муртагом (!983) и др. [1241. Временная трудоемкость зтих процедур оценивается в О (л') против О (л') обычных иерархических, пространственная — О (л) против О(л'). Причем зги оценки справедливы для плохих случаев, а чаще всего времени требуется значительно меньше.
В [1241 предложена некоторая модификация алгоритма Муртага, позволяющая при пространственных затратах О(лз) обрабатывать данине алг. 6 и 6 табл. 2.3. 18. Предлагается для нахождения ближайшего кластера пользоваться ускоренными процедурами поиска экстремального элемента, имеющими трудоемкость не 0(п), а О(!ода). 19. Гиперкуб, в котором содержатся все точки (определяемый размахами вариации признаков), разбивается на первом шаге по каждой оси перпендикулярной ей плоскостью на 2" «кубика». На 1-м шаге каждый из этих кубиков также разбивается, т.
е. получается 2"ь гиперкуба. Если в полученном кубе есть хоть один объект, он считается заполненным, если нет — пустым. Кластером здесь называется максимально большая связная область, в которой любые два объекта соединены непустыми клетками. По мере увеличения 1 число кластеров растет, т. е.
алгоритм носит дивизимный характер. На рис. 2.7 видно, что при т=2 для 1=1 (шаг 1) выделено 2зч=4 клетки и все объекты попали в один класс (три непустых клетки связаны). При 1=2 (шаг 2) выделено 2з.а=[6 клеток (пунктир); образуются 3 связные области (кластера); 1,2,5/3,4/6,7,8. Временная трудоемкость О(л), что является рекордом для иерархических алгоритмов. В целом алгоритм выглядит очень привле- / / кательно; установлены полезные свойства разбиений; эксперименты 1 ~тн ~~ ' 2 у показали способность метода разделять весьма сложные скопления объектов (торы с центром и др.) .
Метод не требует предвари- Рис. 2.6 56 тельной нормировки показателей и расчета расстояний, может работать в исходном пространстве. 20. Рассматриваются способы настройки параметров в обобщенной формуле (2.1), позволяющие выделять кластеры разной формы (кольца, звезды, ленты и пр.) (см. подробнее 2.2.4). 2.2.3.2. Процедуры типа упорядочения (диагонапизацин) матрицы расстояний н поспедоватепьного формирования кластеров 21.
Все расстояния разбиваются условно на малые, средние и большие. Вручную осуществляется такая перестановка строк и столбцов матрицы, чтобы у диагонали собрались малые и средние расстояния. Выделение классов производится визуально. 22. Шаг 1 — к произвольному объекту присоединяется объект, который обеспечивает малое убывание однородности класса, измеряемой энтропией Е; р — если р 2 ,1~ ~!7~ ыкс !77! где М с1~5 ~Р~)="зх(ч, резко меняется (Е, <<Ер ~), то р-й объект начинает новый с~ класс; КΠ— исчерпано все множество объектов (см.
алг. 27). 23. Шаг 1 — к произвольному объекту добавляется ближайший; р — к рассмотренному объекту добавляется такой, что разница между суммой расстояний от него до всех оставшихся Мр ~ элементов и общим расстоянием до просмотренных объектов максимальна; КΠ— исчерпаны все объекты. Выделение классов визуально. 24.
Шаг 1 — см. алг. 23; р — к рассмотренным объектам добавляется объект такой, что среднее расстояние от класса до всех остальных объектов не уменьшается; КΠ— исчерпаны все объекты. Выделение классов происходит визуально. 25. Требуется построить разбиение, чтобы каждый класс в нем удовлетворял условию: если (а;, а,)яро то А,(с(р (когда ар ен5~); р — в 51 включается с(р(с(ср ~)=ш(пйч проверяется справедливость / определения; если Н не позволяет' считать 5 классом, ар начинает новый класс; КΠ— все объекты в классах.
Этот алгоритм отыскивает главное разбиение, т. е. с минимальным числом классов, удовлетворяющих опре- '4 делению. 26. Шаг 1 — выбирается произволь- ! ный (первый) объект и отыскивается ближайший к нему; р — выбирается ° з ! в 'в объект, ближайший к рассмотренным р — ! объектам, и присоединяется к ним. В принципе возможны любые способы 7 определения близости объекта к классу; в (30) используется средняя связь; Рис. 2.7. КΠ— исчерпано множество объектов. 57 г з «з з азах з 2 3 4 З З 7 Рис.
2.9. Рис. 2.9. В перестроенной по новым номерам объектов матрице классы выделяются визуально. На рнс. 2.8 показаны два варианта выделения классов в упорядоченной матрице. 27. В упорядоченной по алг. 26 матрице (методом средней связи) следят за изменением средней связи объекта с классом: если для 1-го объекта связь резко упала, т. е. р; к~ †,л,р, 1-й объект начинает новый класс. Средние связи объектов с предыдущими объектами равны: ри =2; 2; 2,33; 2,5; 5,8; 6,33. Их разности 2 — 2=0; 2,33 — 2=0,33 и т. д. (рис. 2.9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
