Авторы: Кокорева Яна Валерьевна, Макаров Александр Александрович

Рубрика: Технические науки

Опубликовано в Молодой учёный №13 (93) июль-1 2015 г.

Дата публикации: 30.06.2015

Статья просмотрена: 501 раз

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

Кокорева Я. В., Макаров А. А. Поэтапный процесс кластерного анализа данных на основе алгоритма кластеризации 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.

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

Обсуждение

Социальные комментарии Cackle
Задать вопрос