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

5(п,п+Ы) =О для й)О. По теореме Ньютона [172, гл. 6] полипом и-й степени ' 0 (х) может быть записан в виде: 2.3. Рекурсивное соотношение между числами Стирлинга второго рода Для нахождения чисел Стирлинга второго рода может быть применено уравнение (2.1). Однако если требуется найти последовательность значений этих чисел, то удобнее воспользоваться рекурреитным соотношением, связывающим эти величины 5 (п+ 1, 1) = 15 (п, 1) + 5 (и, 1 — 1) .

Эта формула следует прежде всего из того, что х<1+о=х(х-1) ° ° ° (х — 1) =х<1>(х — 1) =хх<о — <х<1>. Откуда (2.13) Х<1+1>+ <Х<1> = ХХщ. Пользуясь определением 5 (а, 1), найдем: и+1 х"+'= 2; 5(п+1,1)х< (2.14) (2.15) Хи+1=ХХи= ~ 5(а, 1)ХХ<1>. Воспользовавшись равенством (2.13), из (2.15) получим: и хи+'= ~ 5(п,<)'(х<1+1>+<х<1>) = и+1 и 5(а, 1 1)х<о+ ~ 15(а,<)х<1>, 1=1 1=1 Но поскольку 5 (и, 0) =5 (а, а+1) =О, и+1 хи+'= ~ [5(а,< — 1)+15(а,>)1х<о, (2.! 6) Сравнивая этот результат с (2.4), мы имеем: 5(п+1,1) =5(а,1 — 1)+15(п,1). 47 Если число подмножеств разбиения т известно за.ранее, то общее число разбиений п объектов на т кластеров равно 5 (а, т).

Если же значение т неизвестно, то общее число всех разбиений равно ,2 5(п,т). ии=1 Эквивалентной формулой для 5 (и, т) является с» 5(и, т) = — ~) С ( — 1) -айн, а о откуда получаем: Б(нт) 1 т а / й тп = — ~ С. (-1)--а т" т1 т а=о При и — ~-оо каждый член суммы за исключением последнего стремится к нулю, поэтому л(н, т) ! !пп 'Таким образом, при больших и т» л(и т) = — =т"-' т В.табл. 2.1 приводятся значения 5 (и,т) для и, не превышаюших 8. Таблица 2.1. Число разбиений на кластеры длн различ- нык значений т и и' ' л — число объексов, Зв — чксло кластеров. 2.4. Вычислительные аспекты полного перебора Имея целевую функцию, например внутригрупповую сумму квадратов, которая эквивалентна евклидовой метрике, оптимальное решение кластерной проблемы теоре.

46 тически может быть получено перебором всех возмож ных альтернатив разбиения; при этом оптимальному разбиению отвечает и оптимальное значение целевой функции. Однако этот процесс практически неосуществим за исключением случаев, когда а мало. При полном переборе некоторые кластеры для разных альтернатив разбиения будут совпадать, что приводит к лишним вычислениям, которые можно сократить.

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

Рассмотренные в первой главе методы кластеризации также достаточно быстро приводят к оптимальному решению. К таким методам, например, принадлежат методы последовательной кластеризации. Однако эти методы работают только на подмножестве всех возможных альтернатив разбиения и поэтому не гарантируют того, что найденное решение будет оптимальным или близким к нему.

При кластеризации с помощью полного перебора необходимо иметь в памяти одну матрицу наблюдений Х, и все вычисления будут основываться только яа ней без привлечения дополнительных массивов., Однако необходимый объем вычислений так велик, что, несмотря на высокое быстродействие современных вычислительных машин, решение задачи остается безнадежным. (В табл. 2.1 приводится общее число кластеров для различных значений и (число объектов меньших 9).) Привлечение методов динамического программирования для решения кластерной проблемы требует большой скорости прн обращении к дополнительным массивам, хранящим информацию. Эти методы привлекают «старые» вычисления и выполняют «новые».

Таким образом, высокая скорость обращения к хранящейся ин. формации очень желательна, если не обязательна. Один из методов динамического программирования был разработан Дженсеном [1831; этот метод будет описан в следующей главе. Там же будут рассмотрены другие методы, основанные на динамическом программировании. 4 Заказ «79« ГЛАВА 3 МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И КЛАСТЕРНЫЙ АНАЛИЗ Напомним, что решением кластерной задачи является такое разбиение и объектов на гл непересекающихся подмножеств, которое удовлетворяет некоторому критерию однородности внутри кластеров. Один нз способов отыскания такого разбиения был рассмотрен в преды. душей главе: он заключался в полном переборе всех возможных разбиений на т кластеров и выбора из них оптимального.

К сожалению, указанный метод практически неосуществим даже для небольших л и и. В качестве альтернативы метода полного перебора можно предложить другие методы, составляющие содержание так называемого математического программирования; эти методы позволяют сократить общий объем вычислений и в то же время приводят к оптимальному решению. Заметим, что большинство из ранее рассмотренных методов кластеризации (гл. 1) дает оптимальное решение в классе меньшем, чем класс всех возможных разбиений (кластеров), поэтому нет гарантии, что найденное решение будет оптимально в классе всех разбиений. Различные применения математического программирования читатель найдет, например, у Дженсена [1831, Вайнода 13801 и Рао 12911.

ЗЛ. Применение динамического программирования к кластерному анализу В этом параграфе мы рассмотрим задачу разбиения множества из 6 объектов на 3 подмножества; в качестве меры расстояния между объектами выберем евклидову метрику, что соответствует критерию минимизации внутригрупповой суммы квадратов (ВСК).

60 (1)' И: (2). Каждая компонента формы распределения обозначает число объектов в некотором кластере. Компоненты в форме распределения всегда будем записывать в убывающем порядке. В нашем примере .имеется 90 альтернатив разбиения и 3 формы распределения. В общем ав 51 Напомним, что ВСК вычисляется по формуле Ш т М7= 1Г Е зу = Е Яту ° з 1 з=г где 3~ обозначает рХр матрицу рассеяния 1-го кластера, и 1гЗг=%';. Таким образом, имеем: / ~ я е~ ~-Е~ —, Е 2 ~(ХьХ) г ~ Зеп м ( 1 а( а~ 2ш (3.1) где дэ (Х* Х;) = (Х» — Х~)" (Х~ — Х;).

Суть методов динамического программирования состоит в целенаправленном поиске разбиения, дающего минимальное значение величины 1Г, при этом разбиения, которые приводят к большему значению Яг, отбрасываются. Подробнее остановимся на проблеме разбиения п=б объектов на т=3 группы с помощью полного перебора. На этом же примере мы рассмотрим применения мего; дов динамического программирования, которые приведены в работе Дженсена 1183]. Общее число способов разбиения 6 объектов на 3 группы определяется из уравнения (2.1!): 1 з й 5(6,3) = —, Е (-1) "Сз (3 — й)а=90.

' м=а 90 альтернатив кластеризации может быть классифицировано соответственно формам распределения [183). В нашем примере существуют три формы распределения, которые обозначим (1) (4) (Ц (2) (3) (2) (3) (2) (2) (6, 2, з), (4, 5), (П (6, 2, 3), (4, 1), (5) (6, 2, 3), (1, 5), (4) Форма распределения (1, 2), (3, 4), (5, 6) (1, 2), (3, 5), (4, 6) (1, 2), (3, 6), (4, 5) (1, 3), (2, 4), (5, 6) (1, 3), (2, 5), (4, 6) (1, 3), (2, 6), (4, 5) (1, 4), (2, 3), (5, 6) (1, 4), (2, 5), (3, 6) П лодоялс ее и в (4, 5, 6), (1, 2), (3) (4, 5, 6), (1, 3), (2) (4, 5, 6), (2, 3), (!) (2), (2», (2) (1, 4), (2, 6), (3, 5) (1, 5), (3, 4), (2, 6) (1, 5), (3, 2), (4, 6) (1, 5), (3, 6), (2, 4) (1, 6), (3, 4), (5, 2) (1, 6), (3, 5), (4, 2) (1, 6), (3, 2), (4, 5) При полном переборе целевую функцию (ВСХ) необ« ходимо вычислить для каждой из 90 альтернатив раз.

биения, приведенных выше; затем отыскивается такое разбиение, которое приводит Я7 к минимуму. Из-приведенного списка возможных альтернатив разбиения видно, что ВСК для некоторых кластеров, например для (1, 2, 3), будет вычисляться больше одного раза. Применение методов динамического программирова.

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

ряет обработку массива информации. Описанный выше пример рассмотрим в качестве иллюстраций применения динамического программирования. Прежде всего все альтернативы кластеризация классифицируются соответственно формам распределения. Напомним, что компоненты форм распределения располагаются в убывающем порядке. На первом шаге для каждой компоненты первой формы распределения вычисляется и запоминается соответствующая целевая функция. На втором шаге для кластеров, соответствующих первым двум компонентам формы распределения вычисляются новые значения целевых функций; при этом привлекается вся информация, полученная на первом шаге; таким образом, внутригрупповая сумма квадратов не вычисляется заново для каждого кластера, а ее значение берется из предыдущего шага.