Библиографическое описание:

Кокорева Я. В., Макаров А. А. Поэтапный процесс кластерного анализа данных на основе алгоритма кластеризации k-means // Молодой ученый. — 2015. — №13. — С. 126-128.

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

Рассмотрим задачу кластеризации данных. Имеется выборка  и функция, отображающая расстояние между объектами  Алгоритм кластеризации — это функция  которая всем объектам  проставляет метку кластера  [1].

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

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

                                                                                                (1)

где

объект кластеризации (точка);

 — центр кластера (центроид),

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

                                                                                           (2)

где

 расстояние между объектами  и ;

 числовое значение й переменной для объекта ;

 числовое значение й переменной для объекта ;

 число переменных, которыми описываются объекты (или количество данных характеристик) [3].

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

                                                                   (3)

где

 количество набора кластеров в результате кластеризации;

 количество начального набора кластеров;

коэффициент принадлежности.

Определения коэффициента принадлежности объекта к определенному кластеру, которая считается по формуле:

                                                                                                           (4)

где

 расстояние от объекта до центра кластера;

 коэффициент неопределенности,

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

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

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

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

Определим понятия точности и полноты полученного кластера  относительно ожидаемого кластера :

-                   точность:

;

-                   полнота:

,

где

число элементов в кластере

число элементов в кластере

число общих элементов  и

Введем для пары  и  меру как среднее гармоническое точности и полноты:

                                                             (5)

Далее определим меру  относительно ожидаемого разбиения  как максимальное значение мер  относительно кластеров из разбиения :

                                                                                             (6)

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

                                                                                             (7)

где количество кластеров в разбиении ;

число элементов в кластере

общее число элементов в выборке.

Чем  больше, тем ближе полученное разбиение к ожидаемому разбиению. В лучшем случае, когда каждому кластеру из  отвечает ровно один из  обращается в единицу [4].

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

                                                                                                 (8)

Одним из подходов определения оптимального количества кластеров является анализ индексов Калинского-Харабаза (Caliński–Harabasz index). Для этого необходимо найти такое количество кластеров, которое максимизировало бы функцию, представленную в формуле:

                                                                                           (9)

где

 количество кластеров;

 матрица внутренней дисперсии;

 матрица внешней дисперсии.

                                                                           (10)

где

 количество объектов в изучаемых данных.

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

Алгоритм k-means является простым итеративным алгоритмом кластеризации, разделяющим множество данных на k кластеров. По своей сути, алгоритм работает с помощью перебора в два этапа: 1) кластеризация всех точек данных в зависимости от расстояния между точкой и ее ближайшим представителем кластера; 2) переоценка представителей кластера. Ограничения алгоритма k-means включает чувствительность k-means к инициализации и определению значения k.

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

 

Литература:

 

1.                  Кутуков Д. С. Применение методов кластеризации для обработки новостного потока / Д. С. Кутуков // Технические науки: проблемы и перспективы: материалы междунар. науч. конф. (г. Санкт-Петербург, март 2011 г.). — СПб.: Реноме, 2011. — с. 77–83.

2.                  Кондратьев М. Е. Анализ методов кластеризации новостного потока. — Труды 8-й Всерос. науч. конф. «Электронные библиотеки: перспективные методы и технологии.

3.                  Баргесян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining. — СПб.: БХВ-Петербург, 2004. — 336 с.

4.                  Сокэл Р. Р. Кластерный-анализ и классификация: предпосылки и основные направления. В кн: Классификация и кластер /Под ред. Дж.Вэн Райзина М: Мир, 1980, с.7–19.

Обсуждение

Социальные комментарии Cackle