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

Ограничение (3) можно. переписать следующим образом: 3)' иу;Р-.Хаев(=1,2, ..., и. ! 1 Приведенная формулировка может быть применена и для случая, когда каждый объект имеет р измере. ний, т. е. т Х! = (х!!, хм,...,х„!). В этом случае в качестве издержек может выступать любая метрика расстояния из главы 1. Порядок матри. цы С при этом не меняется; задача заключается в минимизации С с учетом его нового определения. Во второй формулировке Вайнода издержки см определяются в терминах ВСК.

Значении х!, ха, ..., х для и объектов располагаются в возрастающем порядке г!, гм..., г„, т. е. г!«»г!«» ° ° ° »«ги Проблема заключается в разбиении г!, гм ..., г . Обо- 66 значим чеРез й', группу, минимальное значение и равно гь Элемент г~ назовем ведущим элементом гр ние которой пы дь Матрица А определяется так же, как и в пред . том групдущем случае, т. е. ам=1 или 0 в зависимости от того, принадлежит ли г, к л; или нет. Поскольку г упорядочены, г~ не может принадлежать к дг ьь "° Л„это означает, что элементы матрицы А, которые лежат™выше диагонали, равны нулю, или ам=О.

1 $з ьм Задачу теперь можно представить как минимизацию а а ам(г;-г;)з, (3.17) 1=! з 1 где г; есть среднее 1-й группы г;=,'~ амг;/п~ в=1 Для, того чтобы (3.17) обращалось в минимум, необходимо выполнение так называемого условия цепи (з(г)пд ргорег1у). Условие цепи означает, что не существует группы, содержащей г; и. г~ (1(1) и не содержащей все г, значения которых лежат между ними.

Это означает, что матрица А=(ан) не может содержать прерывающихся цепочек из единиц, расположенных ниже главной диагонали, т. е: ам~~а~+с;>... >а„;,/=1,2,..., п. Максимальная цепочка содержит гпо членов, поскольку максимальное число элементов, которое может содержать группа, равно гни. Лемма 3.1. Условие цепи ан>аььь; =- ... >а ~ является необходимым условием минимальности. Д о к а з а т е л ь с т в о. При объединении объектов гь гньь ..., г;+ь-1 с 1~+ь увеличение ВСК равно следу матрицы (1.10), т. е.

э !»»-,! —:(г»»»- — Е г»+!)' ' й+! ' й То же происходит при "объединеиии гь г»+», ..., г»+а-! с г»»-ь+»,' увеличение равно а !»»-! (г'+ь» — — Е гьь!)'. э+! э Однако г!+ь»!)г;+м что и доказывает необходимый результат. »»»» Минимизация ХХ а»;(㻠— г!)' эквивалентна миними. »»» э»»-! зации . ХЕацсц при .соответствующем выборе А » »,/ ! (а!») и С=(сц): »» . Т» »» т» -~:,' ацсц= ~ Д,' ац (г»-г;)з ° »=! »=! ».! »=! Значения сц необходимо определить только для !)), т. е. для элементов ниже главной диагонали.

Значение сц численйо равно приращению ИСК при включении элемента г; в группу,, состоящую из элементов г,, ..., г! !. Принимая во внимание (1.10), имеем: » — ! ! ' сц = —.—, (г! — —.. ~", 'гь) з ° - (3.18) »-»+! . ' ! — ! »»=» При таком определении сц можно показать, что ~ ацсц= ~ ~', ац(г»-г!)э, ! ! ! ! ! ! 5! с помощью которого первоначальную задачу квадратичного программирования можно свести к задаче линейного программирования. Окончательно задачу можно сформулировать следующим образом: и и минимизировать »', 2 ',.ац сц »=!» ! при условии: 1) ац)а!+! »~ ...

)а»»ч 1=1,2, ..., а; ! 1 У ' ! !- хз 2) со= —.. [ а — — Еах! ! †!+1 ! — 1 ь=! Обобщение второй формулировки Вайнода на.много- мерный случай более затруднительно, чем первой. Пусть имеется Хь Хм ..., Х„точек в р-мерном прост- ранстве. Поскольку условие цепи нельзя непосредствен- но обобщить с одномерного случая на многомерный,. Вайнод [3801 предлагает обобщенное условие цепи, которое можно применить и в многомерном случае. Им также установлено, что условие цепи — это необходимое условие минимума ВСК. Рао [2911 приводит контрпри- мер и предлагает альтернативную форму обобщенного условия цепи, которое также представляет'собой необ- ходимое условие минимума ВСК.

Мы приведем оба определения после чего коротко обсудим два соответствующие им варианта проблемы (Рао и Вайнода). Пусть 0 (А!) обозначает матрицу пХп парных евклидовых расстояний. Элементы 1-го столбца перегруппируем в порядке возрастания, т. е. А!«Ап !«... А„„!, что совпадает с одномерным случаем для г. В терминах матрицы А обобщенное условие цепи означает, чтоцепь из единиц должна проходить через 1!,(з, ..., („ь Мак- симальная длина цепи для любого столбца равна шмПриведем теперь два определения обобщенного ус- ловия цепи.

1. (Вайнод). Цепь из единиц для !'-го столбца мат- рицы А проходит через й, !м ..., 1„ !, причем Аз=0<А,я<А.л<... <А„,л 2. (Рао). Каждая группа содержит хотя бы один объект (ведущнй группы), такой, что расстояние между этим объектом и любым другим объектом, не входящим в эту группу, не меньше, чем расстояние между этим объектом н любым объектом из этой группы. с;„„(1д~/) Вайнод определяет как приращение ВСК при включении Х!„в группу из объектов 1, 1!, ..., (ь !. Значение с;„,; аналогично (3.18) и в многомерном слу- чае равно: 1 ! з ! 2 т=! Пользуясь матрицей издержек, соответствующей урав- нению (3.19), и матрицей А, элементы которой удовле- вв творяют неравенству а»» а»„»>а»„»>.».>а»„» ь задачу минимизации ВСК можно свести к минимизации л и Е Хапссь »-» »=1 При формулировке задачи линейного целочисленного программирования Рао [291] гребует выполнения условия цепи 2. Задача, таким образом, заключается в том, чтобы найти пц'п Сту (3.20) при условии АУ=Ьт, где у»=О или 1 (за исключением последнего элемента); А — матрица (и+1) Х 1и(п — 1)+21; У вЂ” вектор-столбец порядка и(п — 1)+2; Ь вЂ” вектор-столбец порядка и+1, равный (1 ! 1 п»)т.

Ст — вектор-строка порядка п(и — 1)+2. Заметим, что минимизируемая величина (3.20) снова является линейной функцией переменных, состоящих из О и 1. Каждый элемент У служит индикатором группы, т. е. у»=О илн 1 в зависимости от того, пользуются ли »-й группой в окончательном решении или' нет. Вектор С" является вектором значений целевой функции; с» представляет собой значение целевой функции »-й груп- пы.

Например, если в качестве целевой функции рас. сматривается ВСК, то с» имеет вид: а» Р с»-— ~, '~; (х;» — х;)' »=»»=» Вектор У содержит и» единиц и и(и — 1)+2 — и» нулей. Выражение Сту определяет значение целевой функции для данной альтернативы разбиения. Матрица А аналогична соответствующей матрице из (3.17); однаКо теперь ее порядок равен (и+1)1п(ив — 1)+2!. Матрица А удовлетворяет следующим условиям: 1) последняя строка А состоит из единиц, т. е.

а„+»;=1,1=1, 2,..., и(п — 1) +2; 2) каждая строка А, за исключением последней, соответствует одному объекту и содержит только одну единицу; все остальные п(и — 1)+1 элементы равны нулю; 70 3) каждый столбец А, за исключением последнего, представляет собой коэффициенты группы, т. е. и ~.",' ам=ля /=1, 2,..., п(л — 1)+1; (=г 4) последний столбец А состоит из нулей, за исключением последнего элемента, который равен 1. Последний элемент в векторе б равен общему числу кластеров, т.

е. гп. Будем предполагать, что г(м~Аа, если /~й. Из уело. вия цепи следует, что существует а — 1 групп, в которых !-й объект является ведущим, Для демонстрации этого факта рассмотрим неравенство г(я=0<А,л<йи,з«... А„,п ° При условии, что /-й объект является ведущим, возможны следующие разбиения на группы: (1,'~) (! !ь(з), (1, !ь|м, ! ~). Число таких групп равно а — 1. Поскольку всего имеется и объектов, то отсюда следует, что общее число возможных групп равно п(а — !)+1, включая и ту группу, которая содержит все объекты. Число элементов в векторе У соответствует общему числу возможных кластеров с тем ограничением, что общее число возможных кластеров равно гп.

Задача (3.20) вместе с соответствующими ограничениями может быть решена различными методами, описанными в работе 1127). Рао приводит другие критерии минимизации, которыми также можно пользоваться и которые приводят к задаче математического программирования.

Это ! ) минимизация суммы средних квадратов внутригрупповых расстояний; 2) минимизация общей суммы внутригрупповыхрасстояний; 3) минимизация максимума внутригрупповых расстояний. С вычислительной точки зрения эти критерии неудобны, за исключением случаев небольших значений л и т. Если число групп т=2, то они более удобны. Это значение т довольно популярно, если иметь в виду метод Эдвардса и Кавалли-Сфорца [93), который делит все объекты на две компактные группы, и процедура повторяется.

7! ГЛАВА 4 ПРЕДСТАВЛЕНИЯ МАТРИЦ СХОДСТВ Как было отмечено в предыдуших главах, задачи кластерного анализа можно решать как в терминах матрицы расстояний О, так и в терминах матрицы сходства 5. В этой главе мы рассмотрим:различные аспекты представления результатов кластеризации, матриц сходства и расстояния. Параграфы 4.1 и 4,2 служат неформальным введением в более строгое изложение соответствующих вопросов с точными формулировками (Хартиген), которые читатель найдет в параграфе.4.3.

4Л. Дендограммы Последовательный процесс кластеризации начинается с рассмотрения п объектов; затем два наименее удаленных (ближайших) объекта объединяются в один кластер и число кластеров становится равным, и — 1. Процесс повторяется до тех пор, пока все п объектов . не попадут в один кластер, содержащий все объекты. Идеи, изложенные в этой главе, имеют л виду применение методов последовательной (стратифицированной) кластеризации. Наиболее известный метод представления матрицы расстояний (разнородности) или сходства основан на идее «деидограммы», или «диаграммы-дерезам Дендограмму можно определить как графическое изображение результатов процесса последовательной кластеризации, который осуществляется в терминах матрицы расстояний или сходства. В дальнейшем процесс такой кластеризации будем рассматривать, как процедуру с матрицей расстояний или сходства.

Таким образом, с помощью дендограммы можно графически 22 или геометрически изображать процедуру кластеризации при условии, что эта процедура оперирует только с элементами матрицы расстояний или сходства. Существует много способов построения диаграмм- деревьев, соответствующих данной дендограмме. В диаграмме-дереве объекты располагаются вертикально слева, а результаты кластеризации справа. Значения расстояний или сходства, отвечающие построению но.

вых кластеров, -изображаются на горизонтальной пря. мой поверх дендограммы. Имея и объектов, можно по. строить большое количество диаграмм-деревьев, кото. рые соответствуют данной процедуре кластеризации, однако для данной 'конкретной матрицы расстояний или сходства существует только одна диаграмма-дерево. т,а В,В О,В ат аб О,б бтодотдо о О, т дг 03 во об роеотоннов нонтер б ровен та Рис в' На рис.