Дюран Б._ Оделл П. - Кластерный анализ (1977) (Дюран Б._ Оделл П. - Кластерный анализ (1977).djvu), страница 12

3 показан один из примеров диаграммы-дерева. В дальнейшем мы будем рассматривать диаграм. мы-деревья только одного вида, и поэтому дендограммы ' н диаграммы-деревья- будут отождествляться. 'Рис. 3 соответствует случаю шести объектов (л=6) и )т характеристик (признаков).

Объекты 1 и 3 наиболее близки (наименее удалены друг от друга), и поэтому объединяются в один кластер на уровне близости, равном 0,9. Объекты 4 и 5 объединяются прн уровне 0,8. На этом шаге имеются 4 кластера: (1, 3), (6), (5, 4) (2). На третьем и четвертом шаге процесса образуются кластеры (1, 3, 6) и (5, 4, 2), соответствующие уровню близости; равному 0,7 н 0,6. Окончательно все объекты группируются в один кластер при уровне 0,5.

С некоторыми специальными вопросами представления результатов клас- ' теризации читатель может ознакомиться по работе ' 73 . где» вЂ” наименьшее целое из множества (О, 1,..., т) такое,.что Х»~С» и Х«ейС». Например, из рис.' 3 видим, что »((Х»ь Хэ) =0,4 и»» (Хь Х») =0,3. Матрица расстояний, соответствующая этой мере, будет следующей: 0 0,5 0,1 0,5 0,5 0,3 0,5 0 0,5 0,4 0,4 0,5 О,1 0,5 0 0,5 0,5 0,3 0,5 0,4 0,5 0 0,2 0,5 0,5 0,4 0,5 0,2 0 0,5 ' 0,3 0,5 '0,3 0,5 0,5 0 (4.2) Сокала и Свита (3361 Вид дендограммы зависит от выбора меры сходства или расстояния между объектом и кластером'и методом кластеризации. Наиболее важным моментом является выбор меры сходства или меры расстояния между объектом и кластером.

Некоторые меры расстояния обсуждались в главе 1. Дендограмму можно постРонть для любой из этих мер. Джонсон 11861 рассматривает различные последовательные процедуры кластеризации и их связь с одной специальной метрикой. Рассмотрим последовательность множества кластеров С,, Сь С,,..., С и связанные с ними числа а,=О, 1'=О, 1,...т. В терминах примера, показанного на рис. 3, С; соответствует точке отвегвле»»ия, а,— уровню, при котором производится кластеризация. Множество Се содержит и кластеров, состоящих из одного объекта, а аз=О. Таким образом, а«<а» -.

(... Са а каждый кластер из С» представляет собой объединение кластеров из С; ». Подобные процедуры будем называть схемами иерархической кластеризации (СИК). Далее Джонсон показывает, что каждая СИК приводит к специальному виду метрики между объектами и, наоборот, СИК может быть получена на основе этой метрики. Таким обраэом, СИК может быть исследована с помощью изучения соответствующей метрики.

Пусть в СИК даны См Сь...,С со значениями ае, аь...а; определим меры расстояния»((Хр, Х«) как »»(Хр, Х«) =а», (4.1) Можно показать, что мера расстояния (4 1) является «действенной» (Ьопа Ые) метрикой (см. определение 1.1). Наибольший интерес представляет проверка выполнимости неравенства треугольника.

Пусть Х, У и Я вЂ” ' любые трн объекта и д (Х, У) =аь а Ы (У, 2) =аь Отсюда следует, что Х и У принадлежат некоторым кластерам, содержащимся в Сь а У и Л вЂ” некоторым кластерам из Сь. Однако кластер, содержащийся в Сь где (=шах (1', Ь), содержит и другой кластер, что следует из свойств СИК. Таким образом, Х, У и Е принадлежат одному кластеру из Сь Далее Н(Х, У) (а;=шах(аь аь), д(У, Х) (а; шах(аь аь) и д(Х,Я)(шах[0(Х, У), д(У,Я)1. (43) Неравенство (4.3) называется ультраметрическим неравенством. Поскольку шах (й (Х, У), И (У, 2))(п' (Х, У)+ +И (У, Я), неравенство (4.3) сильнее обычного неравенства треугольника, поэтому Н(Х,Е) (и'(Х, У)+д(У, Я).

Каждой СИК соответствует единственная «действенная» метрика. Наоборот, имея матрицу расстояний, например (4.2), можно построить соответствующую диаграмму-дерево (рис. 3), т. е. СИК. Неотъемлемой частью процедуры Джонсона является определение расстояния между кластерами.

Два кла* стерв, имеющие минимальное расстояние, объединяются. Джонсон пользуется в качестве межкластерного расстояния минимальным и максимальным локальным расстоянием между кластерами (определения 1.8 и 1.9). Эти меры приводят к инвариантным методам кластеризации, т. е.

результаты кластеризации инвариантны относитель. но монотонных преобразований матрицы сходства. Джардайн и Сибсон 11791 определяют дендограмму как функцию, отображающую интервал (О, сю) в множество отношений эквивалентности на Р (множество и объектов), удовлетворяющую следующим условиям: !) каждый кластер для данного уровня Ь' есть объединение кластеров на уровне Ь, где 0<Ь(Ь'; 2) для достаточно больших Ь все объекты объединены в один кластер; 3) для данного Ь существуют б)0, такое, что множества кластеров для Ь и Ь+б совпадают.

Условия (1), (2), (3) аналогичны соответствующим условиям Джонсона. Однако в определениях Джардай- на и Сибсона не требуется, чтобы все объекты на уровне 6=0 были различны. й в определениях Джардайна н Сибсона соответствует а в определении Джонсона, у которого предполагается, что по=А=О. Джардайн и Сибсон обсуждают также ультраметрнческое неравенство и связывают свои результаты с различными методами кластеризации.

Аналогичные вопросы рассматриваются в [176], [176], [178] и [!80].'В некоторых из них обсуждается также аксиоматический подход к кластерному анализу. Гауер и Росс [139] вводят понятие минимального дерева и рассматривают его'связь с односвязным кластерным анализом (минимальное локальное расстояние между кластерами, определение 1.8). '' Определение 4.1. Пусть' даны п точек в Е„; деревом, Натянутым на данные точКи, назмвается множество отрезков прямых (робер), связывающих попарно этн точки таким образом, что 1) не существует. замкнутых контуров; 2) через каждую точку проходит по крайней мере одна прямая; ' 3) дерево связано, т.

е. любые две точки соединены прямой. Идеи этого определения идут из теории графов (см. [164] илн [278]). Длиной дерева называется сумма длин отрезков прямых, составляющих дерево. Мини. мальным деревом называется дерево минимальной длины. Гауер и Росс предлагают два алгоритма для отыскав ния минимального дерева; там же рассматривается ал-. горитм, описанный в [299]. Пусть [х(ь х(и,...,ххь) обозначает множество длин ребер минимального дерева; число ребер равно й. На ос. нове множества х(х можно построить дендограмму, груп. пируя 'такие две Гочки, которым соответствует минимальное ребро; далее процедура совпадает с методом ' кластеризации.

по минимальному локальному расстояХ5 3 Хт 76 Рис. 4. Минимальное дерево для семи точек о г,о го до «а хо до г ноиер ооаек го 7 Рис. 5. Леидограмма мииимальиого дерева иа рис. 4 нию. Рис. 4 и 5 иллюстрируют эту процедуру. Описанный метод кластеризации по минимальному локаль'ному расстоянию на минимальном дереве эквивалентен методу кластеризации на матрице расстояний, при этом элементы матрицы, которые не соответствуют ребрам дерева, во внимание не принимаются. Отсюда следует, что кластеризация на минимальном дереве эквивалентна кластеризации на матрице расстояний (Джонсон [186]. Зан (408] изучает свойства минимального дерева и возможные приложения этого понятия, в том числе к методам ступенчатой кластеризации. 4.2.

Сравнения дендограмм и матриц сходства, Мы уже отмечали, что в некоторых случаях матрица расстояний содержит всю информацию о соответствующей дендограмме, и наоборот (например, матрица (4.2) и дендограмма на рис. 3). Однако подобная идеальная ситуация не всегда встречается на практике. Поэтому было бы целесообразным иметь объективный способ определения, насколько хорошо дендограмма представляет свою 'метрику сходства или расстояния. В работе Сокала и Рольфа (335] предлагается мера соответствия между матрицей сходства и ее аппроксимацией„полученной из дендограммы. Они также предлагают метод сравнения двух дендограмм с помощью обычного коэффициента корреляции между множествами значений„которые получаются на основе этих дендограмм. Это в свою очередь приводит к методу сравнения процедур кластеризации. Поскольку дерево или дендограмма содержит ие всю информацию о матрице сходства, мы сталкиваемся с проблемой определения такого дерева, которое содержит максимум информации о матрице сходства.

Таким образом, перед нами стоит проблема построения такого дерева, которое «наилучшим образом подгоняется» под данную матрицу сходства. Эта проблема была решена Хартигеном [162]. В следующих двух параграфах при« водятся его основные результаты. 4.3. Основные определения Дерево, которое обозначим т, будем рассматривать в качестве структуры ступенчатой кластеризации. На этом мы останавливались в предыдущих параграфах. Под узлом (поде) (вершиной графа, дерева),будем понимать либо один-единственный объект, либо кластер объектов, либо кластер кластеров.

На рис. 3 каждая точка ветви представляет собой узел. Определение 4.2. Матрица сходства 5 имеет точную структуру дерева, если з (Хь Х;) (з (Хр, Хч) всякий раз, когда узел, в котором Х~ и Хз объединяются впервые, на'ходится левее узла, в котором объединяются Хр и Х«. Если Хр и Х«более сходны друг с другом, чем Х; и Хь то естественно, что Хр и Х«объединяется в узел (кластер) раньше, чем Х; и Хь или, что то же, з (Хь Х;) ~ (з (Х», Х«), если наименьший кластер, содержащий Х, и Хь содержит также Хр и Х .

Определение дерева по Джонсону 1186 (параграф 21)] включает ультраметрическое неравенство и удовлетворяет понятию точной структуры дерева. Это же относится и к Джардайну и Сибсону 1179]. Если матрица сходства 5 имеет точную структуру де. рева', то такую же структуру будет иметь любая матри. ца, элементы, которой получены с помощью монотонно возрастающей функции от элементов матрицы 5. Для, описания матрицы 5 необходимо задать и (н — 1)/2 значений, однако если 5 имеет точную структуру дерева, то для этого необходимо только 2н — 1 значений, которые соответствуют узлам (точкам ответвления дерева).