Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf

на каждом шаге некоторому критерию качества разбиения, приводят для любого наперед заданного числа кластеров k к разбиению, весьма далекому от оптимального в смысле того же самого критерия качест­ ва. Если прибавить к этому широкое экспериментальное подтвержде­ ние того же эффекта [28], то можно прийти к выводу, что «конечная неоптимальность» оптимального иерархического алгоритма является скорее правилом, чем исключением. Специфический характер метода образования групп, свойственный иерархическим процедурам, ока­ зывается, по-видимому, слишком жестким ограничением с точки зре­ ния экстремального подхода к решению задач классификации наблю­ дений при определенном числе классов.

Приведем некоторые примеры иерархических алгоритмов:

•— агломеративный иерархический алгоритм «ближайшего соседа» (или «одной связи»). Этот алгоритм исходит из матрицы расстояний между наблюдениями, в которой расстояние между кластерами опре­ делено по формуле (3.4). На первом шаге алгоритма каждое наблюде­ ние X t (і = 1, 2, ..., п) рассматривается как отдельный кластер. Далее на каждом шаге работы алгоритма происходит объединение двух самых близких кластеров и соответственно по формуле (3.4) пере­ считывается матрица расстояний, размерность которой, естественно, снижается на единицу. Работа алгоритма заканчивается, когда все исходные наблюдения объединены в один класс. Поскольку расстоя­ ние между любыми двумя кластерами в этом алгоритме равно расстоя­ нию между двумя самыми близкими элементами, представляющими свои классы, то получаемые в итоге кластеры могут иметь достаточно сложную форму, в частности, они не обязаны быть выпуклыми; ведь два элемента (наблюдения) попадают в один кластер, если существует соединяющая их цепочка близких между собой элементов. Это обстоя­ тельство можно отнести как к достоинствам алгоритма, так и к его недо­ статкам.

Для устранения опасности появления случайных, не характерных для исследуемого явления объединений [77] предложена модификация алгоритма «ближайшего соседа». Эта модификация состоит в том, что элементы исследуемой совокупности включаются в рассмотрение в порядке убывания плотности наблюдений в их окрестности, причем плотность оценивается как величина, обратная расстоянию до самого дальнего из т элементов, ближайших к данному. Целое число т назначается заранее из некоторых априорных соображений и, по смыс­ лу использования в процедуре, определяет число элементов (в коли­ честве т + 1) в кластере, являющемся наиболее представительным, наиболее населенным среди всех кластеров, образующихся на первом шаге процедуры. А кластеры эти образуются по следующему прави­ лу. Из элементов исследуемой совокупности (Xt), занумерованных в порядке возрастания расстояния R t (т) от каждого из них до самого дальнего из т ближайших к нему соседей, выбираются вначале т то­ чек, попавших в окрестность точки Х г радиуса R1(т), и из этих (т+1) точек формируется первый кластер S ±. Затем берется следующая по порядку точка Х іг из числа п — т — 1 оставшихся, т. е. не попавших в кластер S lt и к ней «притягиваются» для образования следующего

101

класса все точки, из числа не попавших в кластер Si, попадающие в ее окрестность радиуса R i2 (т), и т. д. Следует отметить, что описан­ ная модификация алгоритма ближайшего соседа, оставаясь агломеративной процедурой, уже не является, строго говоря, процедурой иерархической, так как не предусматривает в качестве обязательного итога объединение всех наблюдений в один класс.

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

Отметим, что существует тесная связь между алгоритмом ближай­ шего соседа и различными алгоритмами, основанными на представ­ лении матрицы расстояний в виде графа [8], [13], [46]:

— агломеративные иерархические алгоритмы «средней связи», «полной связи» (или «дальнего соседа») и «минимального внутриклассового разб­ роса». Эти алгоритмы отличаются от описанного выше алгоритма «ближайшего соседа» лишь способом вычисления расстояния между классами. В алгоритме средней связи под расстоянием между клас­ терами понимается среднее из расстояний между всевозможными парами представителей этих кластеров, и следовательно, это расстоя­ ние вычисляется по формуле (3.7). В алгоритме полной связи (или дальнего соседа) расстояние между двумя кластерами определяется как расстояние между двумя самыми отдаленными друг от друга пред­ ставителями своих кластеров, т. е. вычисляется по формуле (3.5). В оп­ тимальном иерархическом алгоритме (в алгоритме минимального внут­ риклассового разброса) расстояние между кластерами определяется по формуле (3.10);

— К-обобщенная иерархическая процедура, т. е. обобщенная по Колмогорову. Поскольку все вышеперечисленные виды расстояний между кластерами могут быть получены в качестве частных случаев обобщенного расстояния Колмогорова (3.8), то нам представляется естественным ввести понятие /(-обобщенной иерархической процеду­ ры. Очевидно, в класс /(-обобщенных иерархических процедур следует включить все обычные иерархические алгоритмы, использующие в качестве расстояний между кластерами обобщенное расстояние Колмогорова (3.8) при том или другом конкретном выборе числового параметра г;

— процедуры иерархические, использующие понятие порога. Общая схема подобных процедур отличается от обычной логической схемы ранее описанных иерархических процедур лишь дополнительным заданием последовательности, как правило, монотонной, порогов сь с2, .., си которые используются следующим образом. Для опреде­ ленности дадим пояснения для агломеративных процедур. На первом шаге алгоритма попарно объединяются элементы, расстояние между которыми не превосходит величины clt либо мера близости которых

102

не менее сг. На втором шаге алгоритма объединяются элементы, или группы элементов, расстояние между которыми не превосходит с2, либо мера близости которых не менее с2, и т. д. Очевидно, при ct = оо или при сравнении мер близости, при ct = 0, на последнем t-м шаге все элементы исходной совокупности окажутся объединенными в один общий класс. Заметим, однако, что объединение в кластеры, подчи­ ненные подобным пороговым иерархическим алгоритмам, приводит к образованию, вообще говоря, пересекающихся промежуточных клас­ сов, которые могут не расцепиться вплоть до последнего шага. Поэтому эффективность подобных процедур, возможность выбора подходящих пороговых значений съ ..., ct существенно зависят от внутренней гео­ метрической структуры исходного множества наблюдений. В част­ ности, пороговые иерархические процедуры оказываются уместными и достаточно эффективными в ситуациях, когда отсутствует (или слабо выражен) цепочечный эффект в структуре исходной совокупности наблюдений и когда последние, естественно, распадаются на какое-то количество достаточно отдаленных друг от друга отдельных скоплелений точек в исследуемом факторном пространстве.

Примеры пороговых иерархических процедур читатель может найти, в частности, в [30], [51].

2.Параллельные кластер-процедуры

Валгоритмах кластер-анализа реализуется обычно одна из двух основных родственных идей, которой исследователь хочет подчинить

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

Однако, нетрудно подсчитать, что уже при общем числе класси­ фицируемых точек п (порядка нескольких десятков) полный перебор всех вариантов разбиения на заданное, а тем более на неизвестное число классов является практически неосуществимым.Следовательно, основной смысл конструирования различных параллельных алгорит­ мов классификации — в указании способа сокращения числа перебора вариантов, в описании пути, приводящего, быть может, лишь к приб­ лиженному решению поставленной задачи, но пути конструктивного реализуемого и не слишком дорогого.

а) Алгоритмы, связанные с функционалами качества разбиения.

К таким алгоритмам следует, в первую очередь, отнести алгоритмы «последовательного переноса точек из класса в класс» [42], [45], [63].

103

либо из методов предварительной обработки исходных наблюдений. Вычисляется значение принятого критерия качества разбиения Q (5), например, вида (3.11) при заданном числе классов k, или вида (3.21) при неизвестном числе классов. Затем каждое из наблюдений X t поочередно перемещается во все кластеры, рассматривается как само­ стоятельный кластер, если число кластеров неизвестно, и оставляет­ ся в том положении, которое соответствует наилучшему значению функционала качества Q. Работа алгоритма заканчивается, когда перемещения наблюдений перестанут приводить к улучшению (в смыс­ ле Q) разбиения. Часто описанный алгоритм применяют несколько

Другие возможности сокращенного перебора вариантов разбиения с целью определения оптимальной в смысле (3.15) кластер-процедуры описаны в [12]. Одним из распространенных приемов такого рода яв­ ляется предварительное агрегирование исходных объектов, т. е. некоторое предварительное разбиение исследуемой совокупности на­ блюдений на классы, после которого с полученными классами обра­ щаются как с отдельными точками и находят наилучшие разбиения уже методом полного перебора вариантов. По поводу методов предва­ рительной обработки исходных наблюдений см. ниже, п. 6.

Сокращения числа переборов различных вариантов разбиения можно добиться и ограничив класс всевозможных разбиений, в ко­ тором отыскивается экстремум функционала качества Q разбиениями некоторого специального вида. Например, в [69] предложен метод (правда, только для случаев р = 1 и р = 2) построения процедуры, оптимальной в смысле некоторого критерия качества лишь в классе разбиений, для которых линейные оболочки каждого из классов яв­ ляются выпуклыми.

но и сокращенный перебор остается для большинства реальных за­ дач практически трудноосуществимым.

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

Под эталонными множествами Еъ Е 2, ..., Eh будем понимать ка­ ким-то образом, в частности случайным, сформированные непересе-

тельную долю от общего числа исходных наблюдений п. В частном

104