WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
СОВРЕМЕННЫЕ ТЕНДЕНЦИИ В КЛАСТЕРНОМ АНАЛИЗЕ В.Б. Бериков, Г.С. Лбов Институт математики им. С.Л. Соболева СО РАН 630090, г. Новосибирск, пр. Академика Коптюга, д. 4 Аннотация. В статье сделан обзор существующих подходов к решению задачи кластерного анализа. Рассматриваются новые разработки в области кластерного анализа, основанные на привлечении ансамблей алгоритмов и логических моделей.

Описываются преимущества таких алгоритмов. Ансамблевые методы позволяют значительно повысить устойчивость группировочных решений. Логические модели позволяют группировать разнотипные данные, а также давать объяснение результатов анализа на языке логических высказываний. Формулируются перспективные направления развития кластерного анализа.

Annotation. In this paper, we overview the existing approaches to solving the problem of cluster analysis. We consider new developments in the field of the cluster analysis, based on ensembles of algorithms and logical models. The advantages of such algorithms are described. The ensemble methods allow to raise significantly the stability of grouping decisions. Logical models allow to group heterogeneous data, as well as give an explanation of results of the analysis on the language of logical statements. The perspective directions of cluster analysis are formulated.

1 1. Введение В последние десятилетия наблюдается рост интереса к новому направлению в обработке информации – интеллектуальному анализу данных (Data Mining). В отличие от классических способов анализа, в этой области большое внимание уделяется моделированию поведения человека, решающего сложные интеллектуальные задачи обобщения, выявления закономерностей, нахождения ассоциаций и т.д. В большой степени развитию этой дисциплины способствовало проникновение в сферу анализа данных идей, возникших в теории искусственного интеллекта.

В предлагаемой работе рассматривается частная задача интеллектуального анализа данных – задача кластерного анализа, известная также как задача автоматической группировки объектов, классификации без учителя или таксономии.

Основной целью в кластерном анализе является выделение сравнительно небольшого числа групп объектов, как можно более схожих между собой внутри группы, и как можно более отличающихся в разных группах. Этот вид анализа широко используется в информационных системах при решении задач классификации и обнаружения закономерностей в данных: при работе с базами данных, анализе интернет-документов, сегментации изображений и т.д. В настоящее время разработано достаточно большое число алгоритмов кластерного анализа (см. [1,2,17]). Однако в этой области существует ряд актуальных проблем, рассмотрению которых и посвящена статья.

Работа имеет следующий план. В параграфе 2 вводятся основные понятия и обозначения, используемые в работе. В следующем параграфе кратко перечисляются известные подходы, применяемые в кластерном анализе. В четвертом параграфе формулируются актуальные методологические проблемы кластерного анализа. В параграфе 5 описывается ансамблевый подход к решению задачи кластер-анализа.

Шестой параграф посвящен логическим моделям кластерного анализа. В заключении делаются выводы, обрисовываются перспективные направления дальнейших исследований.

2. Основные понятия и обозначения Пусть имеется выборка объектов исследования s={o(1),...,o(N)}, которая сформирована в результате отбора некоторых представителей генеральной совокупности. Требуется сформировать K 2 классов (групп объектов); число классов может быть как выбрано заранее, так и не задано (в последнем случае оптимальное количество кластеров должно быть определено автоматически). Каждый объект генеральной совокупности описывается с помощью набора переменных X1,...,Xn.

Набор Х={X1,...,Xn} может включать переменные разных типов (количественные и качественные, под которыми будем понимать номинальные и булевы, а также порядковые). Пусть Dj обозначает множество значений переменной Xj. Обозначим через x=x(o)=x1(o),...,xn(o) набор наблюдений переменных для объекта о, где xj(o) есть значение переменной Xj для данного объекта. Соответствующий выборке набор наблюдений переменных будем представлять в виде таблицы данных V с N строками и n столбцами: V={ x(i) }, i=1,2,…,N, j=1,2,…,n; при этом значение x(i), находящееся на j j пересечении i-й строки и j-го столбца соответствует наблюдению j-й переменной для iго объекта: x(i) =Xj( o(i) ). В некоторых задачах исходная информация представляет j собой таблицу попарных расстояний между объектами.

Можно выделить следующие основные этапы кластерного анализа.

1. Формирование системы переменных. Часто исследователь не может с уверенностью сказать, какие именно переменные действительно важны для анализа, поэтому стремится включить как можно больше потенциально информативных факторов. Нередко требуется предварительно выбрать из исходного множества переменных наиболее эффективную подсистему (в зарубежной литературе этот процесс называется «feature selection»). Кроме того, в некоторых задачах целесообразно трансформировать исходные переменные так, чтобы образовать новые, более информативные показатели («feature extraction»). Чтобы избежать «доминирования» переменных с большим масштабом измерения, проводят предварительную нормировку исходных переменных.

2. Определение способа вычисления расстояния между объектами или группами объектов. Этот способ должен отражать специфику решаемой прикладной задачи. Для каждой пары объектов o(i) и o(l) обозначим расстояние между ними через (o(i),o(l)), где i l. Например, в случае непрерывных переменных может быть задано евклидово n расстояние E (o(i),o(l)) (x(ji) x(jl))2. Чтобы исключить влияние сильных jлинейных корреляций между переменными, применяют расстояние Махалонобиса M (o(i),o(l)) (x(i) x(l))T 1(x(i) x(l)), где x(i) и x(l) - вектора-столбцы значений переменных для соответствующих объектов, - ковариационная матрица (оцененная по выборке, либо полагаемая известной априори). Для номинальных переменных может использоваться расстояние Хэмминга. Для групп объектов также определяется способ нахождения расстояния, например, по принципу «дальнего соседа», «ближнего соседа» и др. [2]. Принцип «дальнего соседа» оправдан в случае, когда есть априорная информация о том, что таксоны имеют компактную сферическую форму. Принцип «ближнего соседа» имеет смысл применять, если известно, что таксоны могут иметь «вытянутую» форму или концентрически расположены.



3. Группировка объектов. На этом шаге проводится создание групп объектов.

Разбиение на группы может быть «жестким» (формируется разбиение исходного множества объектов), а может быть и «нечетким» (вычисляется степень принадлежности каждого объекта к группам). В данной работе будем рассматривать группировку первого типа. Пусть сформировано группировочное решение G={C(1), (iNk ) C(2),…, C(K)}, где C(k) {o(i1),o(i2 ),...,o }, Nk – число объектов, входящих в k-й кластер, k=1,2,…,K. Под группировочной решающей функцией будем понимать отображение f: s {1,2…,K}.

Существует большое многообразие алгоритмов группировки. Основные подходы, на которых базируются эти алгоритмы, представлены в параграфе 3.

4. Представление результатов. Требуется получить простое и информативное описание полученных кластеров. Часто для такого описания выбирается «типичный объект» или определяется набор усредненных по группе показателей. Используется также описание в виде набора таксонов. Под таксоном будем понимать подобласть пространства переменных минимального объема, имеющую некоторую заданную форму и содержащую точки соответствующей группы.

5. Определение качества полученной группировки. Специалисту прикладной области необходимо удостовериться в том, что сформированные группы действительно отражают внутренние закономерности, характерные для решаемой задачи, способствуют достижению целей анализа, помогают открыть новые свойства изучаемых объектов. Существуют также более формальные способы проверки качества, связанные с нахождением вероятности случайного образования групп, которую можно вычислить в рамках той или иной модели распределения (с проверкой статистических гипотез об однородности наблюдений различных классов); с бутстрэпметодом; с вычислением различных показателей качества (внутригруппового разброса, индекса Гудмана-Крускаля; Ранда; С-индекса и т.д.) [25].

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

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

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

параметры распределения неизвестны. Имеющаяся выборка наблюдений представляет собой реализацию смеси распределений. Необходимо определить наиболее правдоподобные значения параметров, восстановив закон распределения для каждого класса. Существуют приближенные алгоритмы расщепления смеси (ЕМ-алгоритм) [1].

Проверка значимости разделения может быть проведена с использованием аппарата проверки статистических гипотез. Известны также алгоритмы, основанные на непараметрических оценках плотности.

- Подход, использующий аналогию с центром тяжести. Для каждой группы определяется вектор средних значений показателей, интерпретируемый как «центр тяжести» группы. Используется критерий внутригруппового рассеяния:

Nk n Nk ) K d( G ) ( x(jil ) gkj )2, где gkj x(jil – координата «центра Nk l k 1 l 1 j тяжести» k-го кластера по переменной Xj, j=1,2,…,n, k=1,2,…,K. Оптимальная группировка, при заданном K, соответствует минимальному значению критерия.

В алгоритме K-средних [2] группировочное решение формируется динамически из некоторой исходной группировки путем поэтапного перераспределения объектов в группы с ближайшими центрами тяжести. Это перераспределение идет до получения устойчивого разделения. Аналогичная методика используется также в алгоритме FOREL [3].

- Подход, основанный на теории графов. Наиболее известный алгоритм этого семейства – алгоритм кратчайшего незамкнутого пути [29]. Предварительно строится минимальное остовное дерево графа, в котором вершины соответствуют объектам, а ребра имеют длину, равную расстоянию между соответствующими объектами. Для образования кластеров из построенного дерева удаляются ребра максимальной длины.

- Иерархический подход. Данное направление также имеет отношение к теоретико-графовому подходу. Результаты группировки представляются в виде дерева группировки (дендрограммы). Алгоритмы, основанные на этом подходе, можно разделить на агломеративные (поэтапно объединяющие ближайшие группы или объекты) и дивизимные (в которых поэтапно осуществляется разделение исходной группы на наиболее удаленные подгруппы; те в свою очередь также разделяются на подгруппы и т.д.). Группировочные решения представляют собой вложенную иерархию подгрупп.





- Подход, основанный на понятии ближайшего соседа. Группировка осуществляется последовательно путем приписывания объекта кластеру, в котором находится ближайший объект, при условии, что расстояние до объекта не превышает заданный порог. Существуют различные варианты определения расстояния; при определении меры близости может учитываться и расположение других соседних точек [14].

- Нечеткие алгоритмы кластерного анализа. При использовании данного подхода предполагается, что каждый кластер представляет собой нечеткое множество объектов. К наиболее популярным алгоритмам этого семейства можно отнести алгоритм нечетких C-средних [8].

- Подход, использующий искусственные нейронные сети, основан на аналогии с процессами, происходящими в биологических нейронных системах. Известно большое число алгоритмов данного семейства [16]. Типичная архитектура представляет собой однослойную сеть, в которой каждый нейрон соответствует некоторому кластеру. В процессе обучения сети происходит итеративное изменение передаточных весов между входными и выходными узлами сети; тем самым осуществляется поиск оптимального значения критерия группировки. Нейронные сети позволяют эффективно использовать параллельные методы вычислений. Привлекательным свойством самоорганизующихся сетей Кохонена [21] является то, что они формируют наглядное двумерное отображение множества объектов. Существует определенное подобие в процессе группировки между алгоритмами, основанными на нейронных сетях и некоторыми классическими методами кластерного анализа.

Эволюционный (генетический) подход. Алгоритмы данного семейства построены на аналогии с природной эволюцией. В них используются понятия популяции – набора различных вариантов группировки (называемых также хромосомами, по аналогии с соответствующими биологическими объектами), и эволюционных операторов – процедур, позволяющих из одной или нескольких родительских хромосом получить одну или несколько хромосом-потомков. Этими процедурами являются: селекция, рекомбинация и мутация. Генетический алгоритм [13] способен осуществлять поиск решения, доставляющего глобальный минимум критерию качества группировки. Опишем подробнее основные шаги алгоритма.

1) Формируется случайная популяция группировочных решений (рис. 1).

Каждый вариант группировки представляется в виде последовательности целых чисел длины N, кодирующих номера кластеров. Для каждой последовательности («хромосомы») определяется значение критерия качества.

2 2 2 1 1 3 3 3 2 2 2 1 1 1 1 1 1 1 1 1 2 2 3 3 3 3 1 1 2 2 ·.

.

.

3 3 3 3 3 1 1 1 1 1 1 2 2 2 2 Рис. 1. Популяция хромосом; число классов K=3, число объектов N=2) Генерируется следующая популяция путем использования эволюционных операторов. Оператор селекции служит для случайного отбора «родительских» хромосом, наилучших с точки зрения критерия качества. Рекомбинация служит для образования из отобранных хромосом новых последовательностей. Наиболее известным является оператор рекомбинации «кроссовер». Этот оператор для каждой пары родительских хромосом образует пару хромосом-потомков с помощью перестановки одного или нескольких сегментов (рис. 2).

Оператор мутации случайным образом изменяет последовательность в соответствии с определенным правилом (например, заменяет в случайно выбранном элементе один номер группы другим). Для новой популяции вычисляются соответствующие значения критерия.

3) Шаг 2 повторяется, пока не будет выполняться заданное условие остановки.

родитель 1 2 2 2 1 1 3 3 3 2 2 2 1 1 1 1 точка кроссовера родитель 2 1 1 1 1 1 2 2 3 3 3 3 1 1 2 2 2 2 2 1 1 3 3 3 3 3 3 1 1 2 2 потомок потомок 1 1 1 1 1 2 2 3 2 2 2 1 1 1 1 Рис. 2. Оператор кроссовера Описанный оператор рекомбинации обладает рядом недостатков, к числу которых относят недействительность группировочных решений и нечувствительность к контексту. Недействительность решений возникает, когда образуются потомки с меньшим числом кластеров. Например, после применения оператора кроссовера к последовательностям (2 2 1 1 3 3) и (3 3 1 2 1 2) в точке между вторым и третьим элементами, возникают две новые последовательности (3 3 1 1 3 3) и (2 2 1 2 1 2), у которых только два кластера. Нечувствительность к контексту проявляется, когда одно и то же группировочное решение кодируется разными последовательностями. Например, последовательности (1 1 1 2 2 2) и (2 2 2 1 1 1) представляют одно и то же разбиение объектов на группы. При этом потомки этих последовательностей (1 1 1 1 1 1) и (2 2 2 2 2 2) значительно отличаются от оригиналов.

Указанные недостатки приводят к значительному ухудшению качества группировки. Один из возможных способов решения проблемы, предложенный в работе [15], описан в параграфе 5.

Существуют и другие подходы к решению задачи глобальной оптимизации, которые могут применяться в кластерном анализе. Так, например, известен подход имитации отжига [19], также базирующийся на идее моделирования природных процессов. Отметим также работу [5], в которой предлагался метод случайного поиска с адаптацией, явившийся одним из первых в семействе эволюционных алгоритмов.

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.