Разработка системы анализа алгоритмов кластеризации

                     Санкт-Петербургский государственный университет

                 Математико-Механический Факультет

                           Кафедра Информатики

 

 

                     Любимов Дмитрий Александрович

   Разработка системы  анализа алгоритмов                 

                       кластеризации

                      Дипломная Работа

 

 

Допущен к защите

Зав. Кафедрой:

Профессор, доктор физ-мат наук Косовский Н.К.

 

 

Научный руководитель

Аспирант  Шалымов Д.С.

 

 

Рецензент:

Профессор, доктор физ-мат наук Граничин О.Н.

 

 

                                              

                                               Санкт–Петербург

                                         2009

Оглавление

 

Оглавление 2

Введение 3

ГЛАВА 1: алгоритмы кластеризации 4

1.1 Задача кластеризации 4

1.2 Средства анализа алгоритмов кластеризации данных 9

1.3 Постановка задачи 12

ГЛАВА 2: Теоретические основания РАБОТЫ 15

2.1 Индексные методы оценки кластеризации 15

2.2 Анализ главных компонент 18

ГЛАВА 3: Программная Реализация 21

3.1 CAMA 21

3.2 Примеры 26

Заключение 29

СПИСОК Литературы 30

 

 

 

 

 

 

Введение

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

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

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

В зависимости  от особенностей конкретной задачи кластеризация может иметь различные  цели:

 – определение структуры множества данных, путем разбиения его на группы схожих  объектов;

– выделение объектов, не подходящих ни к одному из кластеров;

– упрощение работы с данными, когда рассматриваются не целые классы данных, а лишь типичных представителей классов.

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

Целью данной работы была разработка системы,  предоставляющей свободно распространяемые программные средства с открытым кодом для анализа алгоритмов кластеризации  с поддержкой загрузки пользовательских алгоритмов и данных, а также визуализацией работы алгоритмов.

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

 

 

Глава 1. Алгоритмы кластеризации

1.1 Задача кластеризации

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

Пусть имеется набор данных Xn = {x₁,...,x_n} X (n>0) и функция, определяющая степень сходства объектов,  в большинстве случаев это функция расстояния между объектами  ρ(x_i , x_j).

Требуется разбить последовательность Xn на непересекающиеся подмножества (кластеры)  так, чтобы каждый кластер состоял из объектов, близких по метрике ρ, а объекты разных кластеров существенно отличались. Алгоритм кластеризации – это функция A: X → Y которая любому объекту x X ставит в соответствие метку кластера Y. Чаще всего множество Y заранее не известно и дополнительной задачей является определение оптимального числа кластеров с точки зрения того или иного показателя качества кластеризации.

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

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

Следует учитывать, что кластерный анализ сопряжен с рядом сложностей:

– выбор метода кластеризации достаточно эффективного для решения определенной задачи, требует достаточного знания алгоритмов и условий их применения;

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

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

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

Основные используемые алгоритмы кластеризации обычно делятся на два вида: иерархические и неиерархические.

Иерархические алгоритмы

Принцип работы данных методов  заключается в последовательном объединении маленьких кластеров  в большие или наоборот разделении больших кластеров на маленькие.

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

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

Неиерархические алгоритмы

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

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

Рассмотрим один из самых  популярных и широко используемых подобных методов – k–means (k–средних).  Этот алгоритм минимизирует среднеквадратичное отклонение на точках каждого кластера:

 

где – набор векторов принадлежащих–му кластеру, а – среднее значение этих векторов

 

 

 

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

 

Другой популярный алгоритм The Fuzzy C–means  основан на минимизации  C–means функционала.   Определенного как:

 

 

 

 

где                  

 

 

 V – вектор кластерных центров, который должен быть определен,  и

 

 .

 

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

 

2. Средства для анализа алгоритмов                                кластеризации данных

 

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

 

The Fuzzy Clustering and Data Analysis Toolbox

Программный комплекс для Matlab предоставляющие три категории функций:

– алгоритмы кластеризации, разбивающие данные на кластеры различными подходами: K-means и K-medoid – алгоритмы устойчивой кластеризации. FCMclust, GKclust и GGclust алгоритмы неустойчивой кластеризации;

 

– функции анализа, оценивающие, каждое фиксированное  разбиение, выполненное алгоритмом, основанные на индексах(Dunn, Alternative Dunn, Xie  and Beni’s, Partition index);

 

– функции визуализации реализующие модифицированный метод Sammon’а отображения данных в пространство меньшей размерности.

 

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

 

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

 

Cluster Validity Analysis Platform (CVAP)

Приложение также как и предыдущее реализовано на Matlab, но является не пакетом встраиваемых функций, а непосредственно программным инструментом. Основанное на удобном графическом интерфейсе, включает в себя несколько алгоритмов кластерного анализа (PAM,K-means, hierarchical,SOM), а также наиболее широко используемые  индексы оценки их работы. Работая с этим приложением, пользователь получает возможность загружать свои данные, а так же сохранить результаты работы.  Несомненным достоинством является то, что графическая часть позволяет анализировать для одного индекса сразу несколько алгоритмов. помимо этого реализовано графическое представление данных, в том числе и многомерных с помощью анализа главных компонент

SPSS Statistics 

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

 

Недостатки

Недостаток  существующих программных средств прежде всего заключается в их недоступности и невозможности анализа собственных алгоритмов. Например, некоммерческие приложения реализованы в основном на Matlab, который автоматически накладывает ряд ограничений:

–  приложения  зависят от версии и поставленных дополнительных библиотек;

–  необходимо знать его внутреннюю структуру и правила работы;

–  графическая и вычислительная реализации фиксированы;

–   анализ собственных алгоритмов, если и возможен, то необходимо создание дополнительных систем взаимодействия.

Например, упомянутая  ранее система Cluster Validity Analysis Platform (CVAP), хотя и имеет удобный графический интерфейс, но поддерживается он только средствами запущенного приложения Matlab. 

Для использования средств The Fuzzy Clustering and Data Analysis Toolbox,  необходимо написание дополнительных функций, связывающих алгоритм и функции анализа.

Так как  подобные приложения в большинстве  своем являются персональными исследованиями, то они, как правило, не  развиваются.   К  тому же зачастую они были созданы для демонстрации конкретных методов, поэтому ограничены по своим функциям и  вряд ли могут быть объективными.