И.Д. Мандель - Кластерный анализ (1185344), страница 22
Текст из файла (страница 22)
е. возможность обрабатывать поступающие наблюдения без анализа всей матрицы данных. Это сокращает объем памяти и увеличивает скорость, позволяет классифицировать большие массивы информации. Поскольку описание алгоритмов, с одной стороны, потребовало бы весьма специальных разъяснений и много места, а с другой — оно подробно осуществлено в упоминаемой литературе, мы приводить его не будем. Алгоритмы, увеличивающие значения функционала на каждом шаге («пожирающие» процедуры).
Смысл алгоритма в том, что на каждом шаге его работы осуществляется наибольшее увеличение искомого критерия качества из всех возможных на множестве некоторых допустимых операций. Операции фактически сводятся к двум видам: объединению (разделению) и перемещению. Об ъе д и н яю т с я (разделяются) такие два класса, что прирост функционала максимален. Наиболее популярны агломерационные процедуры, дивизи иные — менее. Классический пример такого алгоритма — иерархическая группировка Дж. Уорда (алг. 8 в табл. 2.3), в которой на каждом шаге обеспечивается минимизация внутриклассовой дисперсии.
При п е р ем е ще н и и объект из одного класса переносится в тот, в котором обеспечивается максимальный прирост критерия на множестве всех возможных перемещений. Оба принципа увеличения функционалов могут различным образом сочетаться в конкретных вычислительных схемах: можно сначала организовать объединение до остановки, затем перемещение или начать со случайного разбиения (полученного какой-либо эталонной процедурой) и к нему применить любую из операций; произвольно итерирующий процесс повторять несколько раз с различными начальными состояниями и т. д.
Во многих конкретных случаях удается определить прирост функционалов при единичном акте перемещения или объединения в виде аналитической формулы, что облегчает проведение расчетов. Это типично для многих алгоритмов типа й-средних, иерархических процедур, метода динамических сгущений и др. Особенностью описываемых алгоритмов является их универсальность. Фактически для любого критерия можно без труда построить 'определенный процесс вычислений в духе перечисленных выше операций, и он обязательно сойдется к некоторому локальному экстремуму (7, с. 374 — 377). К сожалению, неизвестными остаются два обстоятельства: как быстро сойдется алгоритм и как далеко будут лежать друг от друга значения найденного локального и глобального экстремумов. Как отмечалось в 2.2, в кластерном анализе не укоренилась традиция сопровождать предлагаемые алгоритмы оценкой их временной и пространственной трудоемкости.
Из некоторых прикидок и отрывочных сведений (частично они приводились выше) можно считать, что для всех приведенных в 2.2 н 2.3 алгоритмов время вычислений приблизительно О ()у —:М4). Конечно, такой грубой оцен4зж, нн 97 ки совершенно недостаточно, и работа по установлению трудоемкости каждого алгоритма представляется как одна из первоочередных в кластерном анализе. Что касается второго вопроса, то он исследован еще меньше.
В одной из немногих работ на эту тему [26] осуществляется оценка снизу для получаемых алгоритмом значений функционала. А именно, если стоит задача-максимизации суммы внутриклассовых связей, т. е. критерий равен — Ем, и она решается любым из трех вышеперечисленных алгоритмов пошаговой оптимизации, то для каждого из них можно гарантировать следующее значение критерия: 1.„) ь — ! )77: —, (., где 7.
— общая сумма всех связей в матрице, й=[М/й]— . целая часть результата деления числа объектов на число классов. Но и здесь не ясно, насколько далека полученная оценка от глобального экстремума. По этим причинам в общем случае весьма трудно сказать, что же все-таки получено в результате расчетов и «лучше ли оно» классификации, построенной каким-либо прямым алгоритмом.
Впрочем, продолжая рассуждения, аналогичные приведенным, можно иначе взглянуть и на связь прямых процедур с оптимизационными. Достаточно вспомнить характер работы многих алгоритмов прямой классификации, особенно эталонных процедур, чтобы убедиться, что схемы итерации очень напоминают описанные процедуры объединения и перемещения и отличаются от них фактически только критерием единичного действия на каждом шаге.
Не приводит ли такая операция тоже к оптимизации некоторого функционала? Есть все основания считать, что это именно так. Основной результат Дж. Мак-Кина (1967) заключался в доказательстве того, что его алгоритм стабилизации (алг. 40 в табл. 2.3) доставляет локальный экстремум критерию г"и Причем при простых вероятностных предположениях показывалось, что процесс сходится в смысле этого же критерия.
Дж. Джардайн, Н. Джардайн и Р. Сибсон в том же году установили, что метод ближнего соседа строит дерево, наиболее хорошо приближающее исходные расстояния в смысле их близости к матрице, содержащей значения ультра- метрики (расстояние между объектами, измеренное как расстояние между теми классами, при объединении которых два данных объекта впервые при агломеративном процессе попали в один класс).
Похожие аппроксимационные постановки обсуждаются в 2.3.4. Мы уже упоминали о локальной оптимальности алгоритма Уорда и т. д. В настоящее время вопросы взаимосвязи процедур в ряде случаев подробно изучены. Некоторые результаты приведены в 2.3.4. Общий подход к алгоритмам автоматической классификации, предложенный в [18] (см. также предисловие к [29]), позволил выяснить оптимальность известных процедур. Там введено понятие интерпретирую- щего функционала качества для некоторого итерирующего процесса, 98 который не убывает, начиная с определенного шага работы алгоритма.
Для конкретного процесса может быть найдено несколько интерпретирующих функционалов. Показано, что такие популярные процедуры прямой кластеризации, как «Форэль»,метод й-средних и его обобщения, общая процедура эталонного типа, а также алгоритм размытой классификации Беждека — Данна, алгоритмы МИР, имеют свои функционалы, и установлено, какие именно. Введен так называемый алгоритм (й — г)-средних, частными случаями которого являются алгоритмы й-средних и «Форэль».
Такого рода результаты очень интересны. Они ясно говорят в пользу тезиса о тесной близости оптимизационных и прямых процедур, что, с одной стороны, не позволяет проводить между ними резкую грань, а с другой — помогает в построении новых схем оптимизации. В качестве общего замечания ко всем алгоритмам локальной оптимизации отметим, что результаты их работы в большой степени зависят от выбора начальных состояний.
Все сказанное на этот счет в 2.2 остается здесь в силе; экспериментальное подтверждение содержится в 2.4. Рассмотрим вкратце точные алгоритмы классификации. Их можно подразделить на три основных класса: использующие идеи математического программирования, главным образом динамического; применяющие метод ветвей и границ; ориентированные на оптимизацию в монотонных системах. Поскольку каждое из этих направлений для своего подробного изложения требует привлечения математического материала, выходящего за рамки сложности, принятые в книге, ограничимся конспективным указанием основного содержания и областей применимости подходов.
Общей особенностью всех методов точной классификации является избирательный подход к функционалам качества разбиения. Алгоритмы могут применяться только к некоторым функционалам, обладающим определенными, в каждом случае специально проверяемыми свойствами. В этом отношении они уступают многим рассмотренным выше процедурам, имеющим универсальный характер. Первые попытки представить задачу кластерного анализа в стандартных рамках математического программирования относятся к концу 60-х — началу 70-х годов В работах Р.
Дзкенсена, М. П. Рао, Д. Вайнода и других приведены алгоритмы минимизации г1 с помощью схем динамического и целочисленного программирования. В последнем случае задача ставится в форме условной оптимизации, в которой ограничения носят, правда, весьма естественный характер. Для динамического программирования строится некоторая рекуррентная процедура пошаговой классификации, относительно которой известно, что почти всегда экстремум будет найден за количество шагов, намного меньшее, чем при полном переборе. Примеры использования алгоритмов обоих типов подробно рассмотрены в ~331. В целом алгоритмы такого типа ие получили широкого расее 99 пространения в силу высокой трудоемкости расчетов и сложности организации вычислительного процесса.
Значительно чаще удается использовать в задачах классификации стандартный прием дискретной оптимизации — метод ветвей и границ. Видимо, первое применение принадлежит Дж. Антониссу, разработавшему схему ветвления для Р~в в 1968 г. Впоследствии этот функционал стал весьма популярным; задача его максимизации в случае мер близости даже получила специальное название: задача блочной триангуляции.
Известен точный метод ее решения алгоритмом ветвей и границ [23„с. 123 — !24]; таким же методом она решается в [26] при наличии ограничения на общую сумму связей в классе. Для функционала довольно общего вида Рзо и аналогичного ему . Ра1 удалось построить точный алгоритм В. Ямпольскому и И. Макарову [111].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
