Оценка качества алгоритмов кластеризации

В интеллектуальном анализе данных задача кластеризации используется для быстрого автоматического разбиения объектов на классы по степени их схожести между собой. Кластеризация является одной из важных задач в области Data Mining, которую можно использовать при выполнении предварительной обработки данных, являющейся первым этапом в анализе данных. В зависимости от особенностей конкретной прикладной задачи [1] с помощью кластеризации можно, например:

• -    сократить объем хранимых данных в случае сверхбольшой выборки, оставив по одному наиболее типичному представителю от каждого кластера;

• -    понять структуру множества объектов, разбив его на группы схожих объектов, и упростить дальнейшую обработку данных, работая с каждым кластером по отдельности;

• -    выделить нетипичные объекты, которые не подходят ни одному из кластеров, тем самым выполнить так называемую одноклассовую классификацию.

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

Краткое описание алгоритмов

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

Farthest First. Алгоритм является модификацией алгоритма k-means. В отличие от алгоритма k-means, случайная инициализация центра кластера производится только для первого центроида. Остальные центроиды устанавливаются на наибольшем отдалении от уже вы- бранных центроидов. Благодаря такой модификации алгоритм обладает более быстрой сходимостью.

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

ЕМ (без указания количества кластеров). Алгоритм является модификацией алгоритма ЕМ. В рамках алгоритма дополнительно решается задача определения оптимального количества кластеров методом V-кратной кросс-проверки.

Иерархический (метод ближайшего соседа). Алгоритм основан на построении минимального остовного дерева на множестве объектов. В полученном дереве удаляют N-1 самых длинных ребер для получения N компонент связности. Полученные компоненты связности и являются кластерами [2].

CLOPE и Large Item. Алгоритмы основаны на оптимизации глобального критерия. При задании глобального критерия оптимизации добавление новой точки в кластер не требует больших вычислений: оно рассчитывается на основе старого значения, нового объекта и так называемых кластерных характеристик (clusters features) [3].

Эффективность работы алгоритмов кластеризации можно оценить с помощью двух параметров: временной и/или пространственной сложности. В таблице 1 представлена временная сложность алгоритмов кластеризации.

Таблица 1

Временная сложность алгоритмов кластеризации

Алгоритм кластеризации	Временная сложность
k-средних	O(N*k)
Farthest First	O(N*k)
ЕМ	О(N*k)
CLOPE	О(N*k)
Large item	O(N*lnN)
Метод ближайшего соседа	O(N*lnN)
ЕМ (без указания количества кластеров)	O(N2)

Здесь N – число объектов; k – число выделяемых кластеров. Алгоритмы K-средних, Farthest First и ЕМ основаны на едином принципе минимизации локальной квадратичной ошибки. Алгоритмы CLOPE и Large Item используют глобальную функцию оптимизации. Использование глобальной функции позволяет алгоритмам иметь свойство масштабируемости – работа в ограниченном объеме оперативной памяти с возможностью продолжения вычислений после прерывания [4]. Метод ближайшего соседа является иерархическим алгоритмом кластеризации и базируется на алгоритмах Крускала или Прима. Наконец, модифицированный алгоритм ЕМ имеет большую временную сложность, так как данный алгоритм также решает задачу определения оптимального количества кластеров.

В зависимости от цели кластеризации, характера входных данных и накладываемых ограничений необходимо выбирать тот или иной метод кластеризации. Тип входных данных относится к числу наиболее важных критериев при выборе метода кластеризации. Таким образом, алгоритмы кластеризации можно разделить по типу обрабатываемых данных (рис. 1). Входные данные делятся на числовые и нечисловые (категориальные) [5].

Рис. 1. Классификация методов кластеризации

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

Оценка качества кластеризации числовых данных

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

-100                          75                           250

Рис. 2. Визуализация искусственных данных

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

Таблица 2 Тестирование алгоритмов кластеризации: измерение памяти

Алгоритм кластеризации	Пространственная сложность (мегабайт)
	750	1000	1500	2000	2500	3000	10000	50000
FarthestFirst	0,23	0,36	0,29	0,37	0,50	0,58	1,67	3,62
К-средних	0,90	3,08	1,93	3,56	1,91	0,74	2,69	16,59
ЕМ	1,09	1,45	3,13	4,68	1,60	5,24	9,03	35,37
EM (мод.)	1,57	2,98	7,16	5,52	3,36	5,69	11,64	45,05
Метод ближайшего соседа	24,57	54,08	97,09	206,93	294,91	386,22	1103,33	2837,38

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

Таблица 3

Тестирование алгоритмов кластеризации: измерение времени

Алгоритм кластеризации	Временная сложность (секунды)
	750	1000	1500	2000	2500	3000	10000	50000
FarthestFirst	0,01	0,06	0,01	0,01	0,05	0,04	0,07	0,2
К-средних	0,01	0,07	0,11	0,26	0,33	0,41	1,95	9,23
ЕМ	0,47	1,2	2,31	2,74	4,76	4,66	20,22	124,07
Метод ближайшего соседа	1,45	2,24	5,5	11,4	15,84	23,31	298,95	9049
EM (мод.)	18	75	124	219	354	477	900	34122

Детально рассмотрим алгоритм вычисления индекса качества кластеризации.

Пусть, A 1 ,…,A k – априорные кластеры, полученные в результате генерации исходного массива данных;

k – априорное количество кластеров;

n i – количество объектов в i-м кластере;

R 1 ,…,R k – кластеры, полученные в ходе выполнения алгоритма;

k' – количество кластеров, которое было определено алгоритмом кластеризации.

Чтобы оценить качество кластеризации, необходимо сопоставить полученные кластеры R 1 ,…,R k с априорными кластерами A 1 ,…,A k . Для этого необходимо получить однозначное соответствие априорного кластера A i результирующему кластеру R_p . Множество индексов { p 1 , … , p k } должно быть подобрано таким образом, чтобы максимизировать сумму c i – количество верно определенных объектов в априорном кластере A i . Из этого следует, что c i можно вычислить по следующей формуле:

c i = 1 4 I R p, |: Ii Pi = 0 U p , = argmax E c

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

У ^k = 1 ck

I =- !—n-. .

k

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

n ₁   0        0

1+ ... +

I = n 1    n 2        n k = 1

^I min            _{k           k}

.

Наибольшее значение индекса качества кластеризации возможно в том случае, если алгоритм точно определил количество кластеров и корректно определил состав кластеров. Тогда максимальное значение индекса можно определить по формуле:

I

max

nn n

— + — +... + — n1   n2       nk   k kk

= 1.

Таким образом, область значений индекса качества кластеризации определена на отрезке [1/k;1], где k – априорное количество кластеров. В проведенных нами экспериментах среднее количество кластеров равнялось 5, то есть минимальное значение индекса качества кластеризации равно 0,2. В целом удовлетворительным качество кластеризации можно считать, начиная со значения индекса 0,6.

Оценка качества алгоритмов кластеризации посредством предложенного алгоритма приведена в таблице 4.

Таблица 4

Оценка качества кластеризации

Алгоритм кластеризации	EM (мод.)	EM	Farthest First	K-средних	Метод ближайшего соседа
Индекс качества	0,6	0,9	0,48	0,85	0,32

Лучшие показатели индекса качества выявлены у алгоритмов ЕМ и K-средних: 0,9 и 0,85 соответственно. Однако алгоритм К-средних выполняется в среднем в 10 раз быстрее алгоритма EM. Поэтому при обработке больших объемов числовых данных предпочтительней использовать алгоритм К-средних. Полученные результаты свидетельствуют о том, что предложенный алгоритм вполне приемлем для оценки качества методов кластеризации с целью выбора наилучшего для обработки данных.

Описание эксперимента кластеризации на реальных данных

Для тестирования алгоритмов кластеризации на реальных данных была использована база данных кинотеатра с информацией о продажах билетов в период с 2007 по 2012 г. Упрощенная модель базы данных представлена на рисунке 3.

Продажа                   Сеансы              Фильмы

Код продажи	1	Код сеанса	1	Код фильма
Дата		Дата сеанса		Название фильма
Код сеанса	ОО	Время сеанса
Сумма		Код фильма	оо

Количество билетов

Рис. 3. Модель базы данных

Записи базы данных были приведены к виду, удовлетворяющему условиям кластеризации. Для определения объекта кластеризации был составлен набор атрибутов. В качестве объекта в эксперименте рассматривается один день кинопроката. Состав атрибутов объекта представлен в таблице 5.

Таблица 5

Атрибуты объекта «День кинопроката»

Название атрибута	Тип атрибута
Количество зрителей в день	Числовой
Дисперсия количества зрителей по фильмам	Числовой
День недели	Категориальный
Год	Категориальный

В эксперименте обрабатывались только числовые атрибуты «Количество зрителей в день» и «Дисперсия количества зрителей по фильмам». Атрибут «Дисперсия количества зрителей по фильмам» отражает разброс количества зрителей по различным кинофильмам в день. Чем больше значение дисперсии, тем более неравномерно зрители посещали сеансы разных фильмов в один день, как это показано на рисунке 4.

Рис. 4. Визуализация реальных данных

В результате проведенного эксперимента по кластеризации на реальных данных можно сделать следующие выводы:

• 1.    Значения атрибутов «Количество зрителей в день» и «Дисперсия количества зрителей по фильмам» прямо пропорциональны друг другу.

• 2.    В дни премьер значение атрибута «Дисперсия количества зрителей по фильмам» резко возрастает.

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

Сравнительный анализ алгоритмов кластеризации

Для обобщения результатов, полученных в разделах 2 и 3, произведен сравнительный анализ качества алгоритмов кластеризации. Для проведения анализа были определены критерии оценки, которые отражают положительные свойства алгоритмов. Результаты анализа представлены в таблице 6, в которой знак «плюс» означает наличие критерия у алгоритма, а знак «минус» - его отсутствие. Знак вопроса в критерии «Индекс качества кластеризации» у алгоритмов CLOPE и LargeItem означает, что тестирование данных алгоритмов нами не проводилось. Оценка по критериям алгоритмов CLOPE и LargeItem получена из работы [3].

Качественное сравнение алгоритмов кластеризации

Таблица 6

Критерии	Методы кластеризации числовых данных					Методы кластеризации категориальных данных
	K-средних	Farthest first	EM	ЕМ (мод.)	Метод ближайшего соседа	CLOPE	Large Item
Простота реализации	+	+	+	-	+	+	+
Относительно высокое быстродействие	+	+	-	-	-	+	-
Нетребовательность к объему памяти	+	+	+	+	-	+	+
Возможность выделения кластеров произвольной формы	-	-	-	-	+	-	-
Отсутствие необходимости задания количества кластеров	-	-	-	+	+	+	+
Работа с числовыми атрибутами	+	+	+	+	+	-	-
Работа с категориальными атрибутами	-	-	-	-	-	+	+
Индекс качества кластеризации	0,85	0,48	0,9	0,6	0,32	?	?

Из таблицы 5 видно, что хорошие результаты имеют следующие алгоритмы: числовые алгоритмы K-средних, ЕМ и категориальный алгоритм CLOPE. Алгоритмы Farthest first, модифицированный ЕМ и метод ближайшего соседа имеют низкие показатели индекса качества кластеризации. В то же время данные алгоритмы имеют свои преимущества. Алгоритм кластеризации Farthest first выполняется значительно быстрее других алгоритмов, модифицированный алгоритм ЕМ обладает свойством автоматического определения количества кластеров, и, наконец, метод ближайшего соседа является иерархическим алгоритмом, т.е. в ходе работы строит дерево разбиения на кластеры.

Заключение

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

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