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

53 Для иллюстрации решения с помощью динамического программирования рассмотрим табл. 3.1. Второй столбец таблицы соответствует первой компоненте формы распределения, т. е. кластерам, образованным на первом шаге. Число кластеров первого шага равно: С»»-)-С»'+С»~=50. Функция Я7 на первом шаге вычисляется для каждых нз пяти кластеров. На втором шаге мы будем иметь 2 кластера, соответствующих первым двум компонентам формы распределения, размеры зтих кластеров будут (4) и (1),-или (3) и (2) или (2) и (2). Таким образом, общее число объектов на втором шаге равно 5 или 4.

Число способов получения 5 объектов равно: С»» Сг'+С»» Сзз=90. Число способов получения 4 объектов равно: С»~ С»'+С»»С»'-— 150, а общее число объектов на втором шаге равно 240. На втором шаге существует '/2 С»тС»з=45 способов образования кластеров с компонентами формы распределения (2), (2); зто означает, что мы имеем 45 повторений. На третьем шаге необходимо к компонентам (3) и (1) из второго шага добавить еще (2), что приведет к форме (3) (1) (2) или зквивалентно (3) (2) (1). Таким образом, общее число способов разбиения на втором шаге равно: » В 2 ! 2 3 С» С2 +С» Сз + з С» С» =30+60+45=135 вместо 105.

Число различных множеств, содержащих 4 или 5 объектов, на втором шаге равно: С»»+С»»=21. Эти множества приведены в табл. 3.1 (шаг 2) и называются состояниями. Итак, на втором шаге имеется 21 состояние. На первом шаге число состояний равно 50. В табл. 3.1 показано 5 из 135 допустимых способов получения состояний на втором шаге. Третий шаг является окончательным. Он состоит из 3 кластеров. На последнем этапе имеется одно состояние, содержащее все 6 объектов.

Число способов получения шести объектов на последнем шаге равно: »»» 3 С» С~ +С» Сз =6+15=21, т. е. имеется 21 допустимая дуга, связывающая шаг 2 с шагом 3. Например, если п=6 и т=З, то общее число допустимых дуг равно: 135+21=156. При включении первоначальных состояний число их будет: 156+50=206. Каждая допустимая дуга приводит к переходным вычислениям по формуле 1. а Т(й)= —" 5:,(,,, нь ьляепеь (3.2) где дл обозначает группу из ла объектов, а 4(м= расстояние между Х» и Хя В нашем примере всего 90 альтернатив разбиения, для каждой из которых необходимо-произвести 3 переходные вычисления (всего 270).

Решение с помощью динамического программирования требует 206 или по крайней мере 64 переходных вычислений. Предположим, что на некотором шаге й имеется некоторое распределение-объектов Хь..., Х, д(п. В процедуре динамического программирования запоминается оптимальный способ разбиения с) объектов на й непустых непересекающихся ' подмножеств. На следующих шагах, иа которых требуется разбить д объектов на й групп, уже не будет необходимости решать эту задачу, перебирая все возможные способы их разбиения. В качестве иллюстрации рассмотрим наш пример, в котором а=б и т=З.

Таблица 32 Альтерннтиве Переходные вычисления 1 Т(1,2)+Т(3,4!+Т(56) 2 Т(1,3)+Т(2,4)+Т(5,6) 3 Т(1,4)+Т(2,3)+Т(5,6) Напомним, что при а=б и т=З имеется Я (6,3) =90 альтернатив разбиения. Три из 90 возможных альтернатив приведены в табл. 3.2. При полном переборе для трех альтернатив потребовалось бы 9 переходных вычислений.

При оптимальном разбиении множества (1, 2, 3, 4) на две группьг размера 2 требуется только 6 переходных вычислений. Если запомнить оптимальное разбиение Т (1,3)+Т (2,4)=((Та (1, 2, 3, 4), то для определения ))Та (1, 2, 3, 4)+Т (6,6) требуется только одно вычисление Т (6,6). Для трех альтернатив применение динамического программирования дает возможность, таким образом, сократить число вычислений на 9 — 7=2. Естест.

венно, при увеличении а и па число сокращаемых вычис. лений значительно увеличивается, однако по ко по отношению к общему числу переходных вычйслеиий это увеличение может быть не столь значительным. 3.2, Модель динамического программирования Джен«сна В отличие от линейного программирования, для которого существует точная стандартная формулировка задачи, в динамическом программировании таковая отсутствует. В задачах динамического программирования соответствующие формулы и уравнения зависят от конкретной постановки проблемы. При этом, как правило, задачу сводят к последовательности рекурсивных формул или уравнений, отражающих связи, имевших место в задаче, по которым и отыскивается «оптимальное» решение. Рао [2911 приводит формулировку применения динамического программирования для решения кластерной про.

блемы при р=1. Дженсен 11831 описывает более общую ситуацию, которую мы сейчас и рассмотрим. На языке динамического программирования задачу кластеризации Дженсеи описывает в виде следующих рекурсивных уравнений: О, если В=О; щ(п(Т(г — у)+Фа ~(у)Я, (3.3) « если Ф=1, 2,..., гпо где т — число непересекающихся непус1(ых под. множеств, на которые разбивается и объектов; й — индекс или переменная шага; гп,=гп, если и т, н равно а — пг„если и (лг; г — переменная состояния, характеризующая данное множество объектов на шаге й; д — переменная состояния, характеризующая данное множество объектов на шаге й — 1; я — у — подмножество всех объектов, содержащихся в г и не содержащихся в у; Т (г — у) — «переходные издержки» (1гапзйюп соз1) объектов в кластере (г — у).

Переменные у и г представляют собой два состояния (множества объектов) на шаге й — 1 и й соответственно. Разность з — у представляет собой те объекты, которые содержатся на шаге й и не содержатся на шаге й — 1. Т (г — у) означает «переходные издержки», т. е. ВСК объектов, объединенных иа 'шаге й — 1; %Г»(г) =ппп [Т(г — у)+вгь ~(у)1 дает минимальное значение ВСК при разбиении объектов, содержащихся в г, на й непустых непересекающихся подмножеств.

Очевидно, формула (З.З) приводит к большому числу вычислений. Напомним читателю, что, как следует из уравнения (3.2) параграфа 3.1, где л; обозначает кластер из п, объектов, переходные издержки Т (я;) равны: 1 а Т(йд= — „, ~ с(~, а<~~из, что совпадает в ВСК кластера йь Заметим, что число шагов равно и«=и, если п)гп, и и ш, если а<2гн. Это объясняется тем, что если и( <2гп, то обязательно сущестнуют по крайней мере л — т+1 кластеров, состоящих из одного объекта.

Переходные издержки Т для кластера нз одного объекта равны нулю, поэтому вклад такого кластера в вг также равен нулю. Следовательно, процесс может закончиться на шаге т,; при этом все оставшиеся кластеры будут содержать по одному объекту. При вычислении %'а (г) необходимо подчеркнуть, что объекты, соответствующие любому состоянию на шаге й, состоят из объектов некоторого множества„соответствующего некоторому состоянию.у на шаге й — 1, и объектов, содержащихся в другом множестве, содержащемся в г — у. В качестве примера, иллюстрирующего рекурсивные уравнения (3.3), рассмотрим 37-е состояние первого шага и 15-е состояние второго шага; напомним, что л=б, т=З (табл.

3.1). В этом случае у обозяачает объекты (1, 3) 37-го состояния первого шага, з — объекты (1, 3, 5, 6) 15-го состояния второго шага, а з — у — объекты (5, 6). «Переходными издержками» из 37-го состояния в 15-е будут: Т(з-у) =Т(5,6) =Ыз« Переходнымн издержками из 37-го состояния первого шага в первое состояние второго шага будут: й й Им +ам +ам Т(з — у) Т(2, 4, 5) = На первом шаге алгоритма динамического програм. мирования для данного множества кластеров вычисляется значение В'~ (г). В этом случае %1(г) =ш(п<Т(з — у) + Я7з(у)) =Т(з), где з обозначает данное множество объектов.

Значение Я~,(г) вычисляется для каждого из кластеров первого шага. Максимальное число объектов, содержащихся в кластере на первом шаге, обозначим через шах (1): гпах(1) =п — т+1; это означает, что максимальный кластер содержит ив — т+1 объектов, а все остальные кластеры по одному. Минимальное число объектов в кластере на первом ша. ге, которое обозначим через ппп (1), равно: ппп(1) =и/т, если п делится нацело на т, и 1и/т)+1 дли 1(п — т<и/т1, и — (т — 1) (п/т1 для и — т<п/т)(1~т, если п не делится нацело на т; (п/т) обозначает наи.

большее число, меньшее или равное п/т. Общее число кластеров на первом шаге, которое обозначим через ЖЗ (1), равно: (3.4)' На первом шаге алгоритма для всех возможных класте. ров /то (1) вычисляется значение Т(г). В общем случае максимальное число объектов в од. ном состоянии на шаге Й равно максимальной сумме компонент всех форм распределения с первого по Й-й ')паг включительно.