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

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

 

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

 

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

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

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

Пусть у  нас есть набор анализируемых данных, к ним применяется набор алгоритмов кластеризации  ,  где  k либо фиксированное число кластеров, либо  последовательность индексов 2,…k, характеризующих количество кластеров, для которого применяются алгоритмы, где k – максимальное количество кластеров, до которого проводится исследование. Будем считать, что каждый фиксированный алгоритм, примененный к фиксированным данным, дает результат  , который необходимо проанализировать. Следует отметить, что  результат   является разбиением исходных данных алгоритмом   на k кластеров. 

В ходе выполнения дипломной работы должны были быть решены следующие задачи:

1. Реализовать несколько вариантов сравнительного анализа алгоритмов, обеспечивающих:

 – выполнение фиксированного алгоритма на фиксированных данных при различном количестве кластеров;

– выполнения фиксированного алгоритма на различных данных;

– выполнения различных алгоритмов на фиксированных данных.

2. Предоставить пользователю возможность визуального анализа с помощью графического вывода данных.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава2. Теоретические основания работы                                   

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

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

Пусть определены некоторые методы анализа разбиения выполненного алгоритмом, ограничим итеративный процесс  максимально возможным числом классов  k_{max .}  Далее алгоритм выполняется для  k {2,3,…,k_max } .  Для каждого разбиения применяются методы анализа,  результаты которых могут быть сравнены в дальнейшем.  За счет подобного изучения результатов достигается достаточно большая гибкость кластеризации.

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

Существует  несколько основных подходов к исследованию  устойчивых алгоритмов и определению  количества кластеров в множестве  данных[1] :

– статистики, определяющие наиболее вероятное решение;

– оценка плотностей распределений;

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

       – индексах, сравнивающих степени «разброса» данных внутри кластеров и между кластерами.

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

Krzanowski and Lai index

Подход  Krzanowski and Lai [6]  анализирует функцию

 

где

 

k – количество кластеров,   p – размерность исследуемого пространства,  W(k)  – матрица внутренней дисперсии

 

x’_i – центр кластера K_j . Основная идея  индекса заключается в измерении порядка изменчивости W(k).

Значение k, которое максимизирует индекс KL, рассматривается в качестве истинного количества кластеров [6].

 

 

Caliński–Harabasz index

Индекс Caliński–Harabasz [5], характеризует следующая функция: 

 

где  k – количество кластеров, i=1,…,k, n – количество объектов в изучаемых данных, W(k) –   матрица внутренней дисперсии,  а B(k) – матрица внешней дисперсии

 

 

Наиболее  вероятным количеством кластеров  является значение k, на котором индекс CH  достигает максимальное значение [5].

Dunn index

   Индекс Dunn [4] первоначально был предложен чтобы определять насколько "компактно и хорошо отделенны группы".   

 

 

где          

       

 

 

 

 

 

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

Главный недостаток данных методов  в том, что их вычисление становится все более сложным, как с увеличением числа кластеров k так и с  увеличением числа объектов входящих в данные.

 

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

  Для решения второй задачи дипломной работы по предоставлению пользователю возможности визуального анализа данных и результатов работы алгоритмов с данными содержащими вектора размерности n>2 возникает проблема проектирования подобных данных на плоскость.  Для решения этой задачи использовался анализ главных компонент алгоритмом Хебба[2].

Предположим у нас есть вектор X размерности n, который мы хотим передать с помощью m чисел, где m<n. Просто откидывая часть элементов вектора X, получаем, что среднеквадратическая ошибка будет равна сумме дисперсий отброшенных элементов.  Поэтому возникает потребность в линейном преобразовании Т, для которого сокращение элементов вектора TX будет оптимальным в смысле среднеквадратической ошибки. Очевидно, что при этом преобразование T должно иметь свойство маленькой дисперсии своих отдельных компонентов.

Пусть X – n–мерный вектор, а w – единичный вектор так же размерности n, на который проектируется X. Эта проекция определяется как скалярное произведение векторов X и w:

 

при ограничении

=1.

Необходимо найти такие значения w при которых дисперсия проекции A будет минимальна.

Алгоритм Хебба (матричная  формулировка)

 Пусть данные  представляют собой n проецируемых векторов,

и w(n) – приближение искомого вектора,  на n–ом шаге итерации

 Проекция  вектора x(n) на w(n) равна

Алгоритм нахождения w(n), предложенный Xеббом [2]

где w(0) – случайный единичный вектор без нулевых компонент, а – достаточно малый параметр интенсивности обучения [2].

После выполнения описаной процедуры определяется вектор, проекции на который являются первыми координатами искомого представления, далее вектора x(n) проецируются на подпространство, ортогональное ,

и алгоритм применяется  повторно для  ,  определяя вектор и вторые координаты.

На Рис. 1 изображен результат  использования этого алгоритма  для 4х мерных данных с двумя четко выделенными кластерами.

 

Рис. 1 Графическое представления 4х мерных данных реализованное разработанной системой с помощью алгоритма Хебба.

 

 

 

 

Глава 3. Программная реализация

3.1 CAMA

   Разработанная в рамках дипломного проекта система получила рабочее название CAMA (Clustering Algorithms Meta Applier) и была реализована на языке Java с использованием технологий JSP, JDBC, JavaServlets, XML–RPC,  JavaScript, сервлет–контейнера Tomcat и сервера базы данных MySQL, а так же с использованием  вычислительного ядра, написанного на С#. База данных системы имеет приведенную на Рис. 2 структуру

Рис. 2 Структура разработанной базы данных.

 

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

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

 Основные  разделы сайта:

– раздел выполнения  алгоритмов (Рис. 3);

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

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

– раздел просмотра сохраненных результатов.

Рис. 3 Web интерфейс системы. Раздел выполнения алгоритмов.

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

  Выполнение алгоритмов

  Пользователь определяет алгоритмы, данные и настройки, и запускает процесс кластеризации и анализа. Происходит вызов  JavaScript функции, которая посылает  HTTP–запрос сервлету, генерирующему результаты и возвращающему их пользователю.

Сервлет, реализующий анализ кластеризации, получает идентификаторы данных и алгоритма, и опции кластеризации.  После чего он преобразовывает информацию с полученным идентификатором данных   из соответствующей таблицы, происходит обращение к таблицам алгоритмов, откуда класс получает идентификатор алгоритма для вычислительного сервера. Далее по протоколу XML–RPC с помощью пакета org.apache.xmlrpc происходит обращение непосредственно к  вычислительному ядру, получение и форматирование результатов. Затем по полученным данным и центрам высчитываются индексы (Dunn, Caliński–Harabasz, Krzanowski Lai) [4-6].  Далее следует обращение к классам, генерирующим визуальное представление. Если размерность  данных больше двух, то они проецируются на двухмерное пространство  с помощью решения задачи   анализа главных компонент фильтром Хебба [2].  В конце работы сервлета генерируется HTML код, содержащий значения индексов и ссылки на изображения визуальных представлений данных.    

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

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

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

 

Добавление, просмотр и редактирование данных

В этом разделе  пользователь  может добавлять  и редактировать загруженные им ранее данные.  Отметим, что общие данные не доступны для редактирования, а загрузка информации о конкретных данных происходит по средствам JavaScript функции, обращающейся к определенному  сервлету, без перезагрузки страницы.  Загрузка файлов реализована с помощью пакета org.apache.commons.fileupload. Файлы хранятся в  базе данных, для них хранится идентификатор пользователя, который их загрузил и они доступны только ему.  Так же в этом разделе поддерживается просмотр данных. Можно просмотреть как непосредственно текстовый файл со значениями, так и визуальное представление данных, сгенерированное системой.