Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 10
Текст из файла (страница 10)
Минимальное число состояний рав. но минимальной сумме компонент форм распределения.- гпах (й) и ппп (й) определяются из следующих уравне. ний: шах(п) =п — т+й (3.5) и ппп(й) =й(п/т), (3.6) если и делится на т нацело. В противном случае ,(3.7) ([и/ач]+1)й для 1 =й(п — т[п/т] ш)п(й) = и — (т — й) [и/т] для и — т[п/т]< <й<щ Число состояний на шаге й определяется как 1 для Й=О, и/с(й) шаиь), С„) для Й=1,2,...,тп.
)=шькп) (3.8) Общее число состояний при динамическом программировании равно (3.9) ~ Мо(й). п=о В рассмотренном подходе большое значение имеет общее число значений (Рп (г) прн переходе от шага й — 1 к шагу й, т. е. число способов построения состояния на шаге й. Состояния последовательных шагов связываются дугами. Два состояния'на шаге й и й — 1 связываются допустимыми дугами, если объекты состояния на шаге й связаны с состоянием на шаге й — 1. Отсюда следует, что допустимая дуга не может связывать состояние на шаге Й вЂ” 1 и состояние на шаге й, если объект некоторого состояния на шаге й — 1 ие связан ни с одним состоянием на шаге й для 2<й<тш В алгоритме динамического программирования общее число допустимых дуг равно: (3.10) А=) шах(ь) шацьы)-ш)пра ТА (й) = 2', 2„РА (1, 1), (3.11), )=ш)п~) 1=~ где ) С С в если ш(п(й+1) =1+1< <гпах(й+1), (3.12) 0 в других случаях.
60 где ТА (й) обозначает общее число дуг между шагами й и й+1 для Й=1,2,..., тр. Значение ТА (й) находится ' по формуле В уравнениях (3.11) и (3.12) . 1 обозначает число объектов в классе (допустилсых) состояний шага й. Всего имеется С, таких состояний, содержащих с' объектов; это следует из того факта, что число подмножеств, с содержащих с объектов, равно Сл .
Символом / обозначено число объектов, которые комбинируются с с объектами и образуют новое состояние шага й+1. Очевидно, для состояния порядка с+/, присутствующего на шаге й+1, пнп(й+1) <1+/<шах(/с+1). Если с+/ удовлетворяет приведенному условию, то существует Сс„ с множеств порядка п — с, которые добавляются к с объектам /с раз. Дженсен предлагает способ вычисления эффективности динамического программирования по сравнению с методом полного перебора. Эта эффективность измеряется отношением общего числа переходных вычислений при динамическом программировании к соответствующему числу вычислений прн полном переборе. В качестве альтернативы в числителе можно взять общее число допустимых дуг. В любом случае процедура динамического программирования довольно эффективна.
Однако применение методов динамического программирования требует привлечения дополнительной памяти ЭВМ; соответственно увеличивается время вычислений за счет обращения к памяти машины, что в конечном счете может привести к тому, что метод полного перебора окажется более предпочтительныме. В любом случае для больших п и пс, может быть, целесообразнее воспользоваться другими методами, например 1300АТА 118] или ступенчатым. Для иллюстрации методики, предложенной Дженсеном, рассмотрим наш пример, в котором п=б, а пс=З. В этом случае п=2пт и поэтому нам необходимо рассмотреть и — пс 6 — 3=3 шага, т.
е. псе=3. Кроме того, шах(1) и — пс+1=4; ппп(2) = ([6/3])2=4; ппп(1) = (16/3]) 1-2; шах(3) =и — па+3=6; снах (2) = и- гп+ 2 = 6; гп(п (3) = (16/3] ) 3 = 6, как следует из табл. 3.1. ч Кая известно, время обращеняя н дополнительной памяти ЭВМ намного больше времени вычислений с данными пв оператявной памяти.— Примеч.
пер. 61 Общее число состояний на шаге О, 1, 2 и 3 находятся из формул: й!Я(0) 1; !УЯ (1) =* Сз + Се + Сзз = 50; Ж8(2) =Се+Се =21' й!8(3) =Се =1. Эти состоянии приведены в табл. ЗЛ. Таким образом, общее число состояний равно 73. Это число можно было бы получить непосредственным подсчетом состояний в табл. 3.1 (Фо(0)=Ц. Для й=1 из уравнения (ЗЛ2) находим: ЕА (3, 1) = Св Сз =60; РА (2, 2) =Се Са =90; ЕА(З, 2) = Сз Сз = 60; РА (3, 3) =РА (4, 2) =0 РА(4, Ц =СвСз =ЗО; н общее число допустимых дуг между шагами 1 н 2 равно ТА(Ц =240.
Для й=2 получим. 4 3 5 ТА(2) =Сз Сз+Сз С~ =21. Таким образом, общее число допустимых дуг в нашем .примере, как следует из (3.10), равно: ТРА=МБ(Ц+ ~ УА(й) =50+240+21=311. ь=$ В параграфе 3.1 было показано, что половина состояний на шаге (2), соответствующих компонентам форм рас- пределения (2) (2), лишние, н 60 дуг, соответствующие компонентам (3) (Ц, в конечном счете приводят к фор- ме распределения (3) (Ц (2), которая эквивалентна форме (3) (2) (Ц.
Таким образом, прн редуцировании число допустимых дуг, которое обозначим через !УА, равно: УА=50+135+21=206. Число допустимых дуг между шагами й и й+1 после исключения равно: твцм шах(а+о-пзпоо й!А(й)= 2', 2", А(й!), 4=шьхю !=1 с С С -ь если 1~7', 1 ч з -у-С„С ь если з=1, О в других случаях.. А (1,1) = 1 3'5 4 1 51 1 4 5 4 2 6/ ° з Аг=!3 з з(и =32, з 4з=18, з Аз= 1~ дщ — — 41, з з(зз = 2, г з(зз = 5, з з(зз=8, з г(зз=8, з з з(зз=б, дзз=32 з(зз = 25 з (зз= 13 Следуя алгоритму динамического программировании, будем иметь: ш а г О.
(Ро(0) =0; ш а г 1. Вычислим %'ь(г) =7 (а — У)+ з( ) +)Рз(0) =Т(а) для каждого множества объектов ша. га 1. Например, )Р~(1 2 3 4) =Т(1 2 3.4)+Уз(0) = 2 3 3 3 3 2 — 17,75. (Аз+зйз+йм+Нзв+Пзз+Лзз) 4 н ппп(й+1) =1+1(шах(й+1), (т-й)(+Р~п. Общее число дуг после редуцирования равно: то-1 ФА=%5(1)+'~„', ХА(й). (3.13) з=1 Легко проверить, что при а=6 и и=3 уравнение (3.13)', приведет к значению Л~А = 206. Итак, максимальное число допустимых дуг, которые необходимо рассмотреть при динамическом программировании, для нашего при. мера равно 206. Чтобы показать, как работает алгоритм динамиче.
ского программирования, допустим р=-2, а шесть объек. тов равны (1, 1), (3, 4), (5, 5), (4, 4), (1, 2) и (5, 6), т. е. На данном шаге мы должны получить 50 таких значе. ний; ш а г 2. Для каждого множества объектов этого шага Вычислим % 3 (3) у (Т (~ У) +(р!(У) ) ' Например, %1з = (1, 2, 3, 4, 5) = пип(Т (5) +%1 (1, 2, 3, 4), Т(4)+%',(1,2,3,5) Т (3) + %71 (1, 2, 4, 5), Т (2) + %'1 (1, 3, 4, 5), Т(1) -1- %', (2, 3, 4, 5), Т (1, 2) +%'1 (3, 4, 5), Т(1,3)+Ф1(2,4,5), Т(1,4)+%1(2,3,5);, Т (1, 5) -1- %', (2, 3, 4), Т (2, 3) + %'1 ( 1., 4, 5), Т (2, 4) + 371 (1, 3, 5), Т (2, 5) + %1(1, 3, 4), Т(3, 4)+%'1 (1, 2, 5), Т(3, 5)+%'1(1, 2, 4)„ Т (4, 5) + %'1 (1, 2, 3) ); ш а г 3.
Для каждого множества объектов этого шага вычислим Жз(г)= с11" (Т(я — у)+%гз(у)). На этом шаге г обозначает единственное множество объек- тов (1, 2, 3, 4, 5, 6). Всего сушествует 21 допустимая дуга, соединяюшая состояния шага 2 с состоянием ша- га 3. Таким образом, нам необходимо выбрать, как минимум, 21 значение. Одно из этих значений равно Т (2, 4) + М7з (1, 3, 5, 6). Оно соответствует состоянию под номером 15 (см. табл. 3,1), для которого у соответствует множеству (1„3, 5, 6), з соответствует (1, 2, 3, 4, 5, 6), а г — у мно- жеству (2, 4). Результатом применения процедуры динамического программирования будут кластеры (1, 1) и (1, 2)', (3, 4) и (4, 4), (5, 5) и (5, 6) с формой распределения (2), (2), (2).
Максимальное значение равно:. 1(Уз(1 2 3. 4 5 6) 1 5. Решение показано на рис. 2. 3.3. Применение целочисленного программирования в нластерном анализе В этом параграфе кластерная проблема будет рас смотрела в терминах целочисленного программирования впервые это было сделано Вайнодом [3801 и Рао 12911 64 «,5 ч е В 5 й 2 с. ! г з е 5 и Карактедпсгпла ! Рис. 2. Граф для п=б объектов Балинский [12) в своем обзоре рассматривает новые методы целочисленного программирования. Посоветуем . читателю также работы [11), [26), [134) и [228).
В формулировке Вайнода [380) рассматривается случай одной измеряемой характеристики (р= 1), в со-. ответствии с которой и выполняется разбиение на кла'стерые..Предположим, у нас имеется а объектов со значениями х!, ..., х . Обозначим через и! число объек- т тов в /-й группе (1=1,2, ..., т); а= в и!. Число объ- 5 1 ектов в максимальном (по числу их) кластере обозначим через нее. Если в!о специально не определено, то лте=п. «Издержки», связанные с включением 5-го объекта в 1чю группу, обозначим через гсп очевидно, си=О, с;;=си. Положим ам=1, если зъй объект принадлежит 1-й группе, и ам=Π— в противном случае.
Имеем и;=' и = Вам, т. е. пу есть сумма элементов в 1-м' столбце мат- с-! 'рицы А= (а!!). Если число кластеров т известно заранее, то матрицм 'С= (см) и А= (ац) будут иметь порядок лзХн. Однако, если ят неизвестно, порядок матриц С и А также неиз'вестен. Чтобы обойти это ограничение, предположим, что обшее число групп равно и, а число пустых групп равно л — и!. В целях идентификации групп введем понятие так называемого ведущего элия!енто группы. По- ' п этом случае задача сводится к простой группироике по одному признаку. — Примеч, дед. з заказ еззе ложим у!=1, если 1-й объект является ведущим, и ух=О в противном случае. В формулировке лластерной задачи на языке целочисленного программирования матрица издержек С предполагается извест!взй.
Например, в качестве см может быть рассмотрено приращение в ВСК при включении !-го объекта в группу с 1чм ведущим элементом. Задача целочисленною программирования заключается в минимизации общей суммы издержек по всем группам разбиения при условии некоторых ограничений: и а минимизировать ~ ~ амсм 1=! з=! при условии, что л 1) л,а!!=1, ! 1,2,, и; (3.14) 3-! 2) Еуз-— и!; (3.15)' /-! 3) у;!а!ь у;>а!я ..., у,Р-а„ь != 1,2, ..., и. (3.16) Ограничение (1) означает, что никакой объект не может'содержаться более чем в одной группе. Ограничение (2) означает, что существует ровно и! групп. Последнее условие означает, что, прежде чем объекты будут присоединены к группе, содержащей 1чй элемент, этот элемент должен быть ведущим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
