Поэтапный процесс кластерного анализа данных на основе алгоритма кластеризации k-means | Статья в журнале «Молодой ученый»

Авторы: ,

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

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

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

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

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

Кокорева Я. В., Макаров А. А. Поэтапный процесс кластерного анализа данных на основе алгоритма кластеризации k-means // Молодой ученый. — 2015. — №13. — С. 126-128. — URL https://moluch.ru/archive/93/20759/ (дата обращения: 17.07.2018).

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

Рассмотрим задачу кластеризации данных. Имеется выборка  и функция, отображающая расстояние между объектами  Алгоритм кластеризации — это функция  которая всем объектам  проставляет метку кластера  [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 – минимизировать среднее арифметическое сумм квадратов расстояний от каждого документа кластера до его центра, называемого...

Кластерный анализ разработки современных алгоритмов...

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

Кластерный анализ обработки данных может быть использован в области цифрового

Кластеризация компаний, развивает конкуренцию, распространяют свое влияние на...

Метод естественной кластеризации данных | Статья в журнале...

Метод естественной кластеризации данных. Автор: Демин Александр Викторович.

4. Повторять шаги 2, 3 пока центры кластеров не перестанут изменяться. Поскольку алгоритм k-means очень чувствителен к выбору начальных приближений центров классов, то на практике...

Использование матриц комбинаторного типа для построения...

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

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

Метод естественной кластеризации данных.

Метод k средних при решении задачи распознавания диктора по...

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

Рис. 1.Результат кластеризации алгоритмом k-means (k=3). Метод k-means хорошо работает, когда кластеры представляют...

Оценка рисков информационной безопасности с помощью метода...

Алгоритм разделяет данные на k кластеров Si (I = 1, 2, …, k). Кластер Si связан с представителем (центр кластера) Ci.

Затем K-means алгоритм кластеризации классифицирует данные с исходными кластерами и центрами кластеров.

Методы решения задачи кластеризации и прогнозирования...

Все значения включим в множество . Это и есть шаг кластеризации.

Кластеры составляются до тех пор, пока есть значения атрибута , не вошедшие ни в один кластер.

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

Особенности использования мини-кластера при расчете...

Рис. 1. Структура мини-кластера. Кластер содержит управляющий узел CU и несколько вычислительных узлов n1, n2, . . . nk.

Таким образом, время решения существенно зависит от m и n. Были выполнены ряд решений при различных значениях m и n. Переменная m задает...

Применение методов кластеризации для обработки новостного...

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

Цель алгоритма k-means – минимизировать среднее арифметическое сумм квадратов расстояний от каждого документа кластера до его центра, называемого...

Кластерный анализ разработки современных алгоритмов...

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

Кластерный анализ обработки данных может быть использован в области цифрового

Кластеризация компаний, развивает конкуренцию, распространяют свое влияние на...

Метод естественной кластеризации данных | Статья в журнале...

Метод естественной кластеризации данных. Автор: Демин Александр Викторович.

4. Повторять шаги 2, 3 пока центры кластеров не перестанут изменяться. Поскольку алгоритм k-means очень чувствителен к выбору начальных приближений центров классов, то на практике...

Использование матриц комбинаторного типа для построения...

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

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

Метод естественной кластеризации данных.

Метод k средних при решении задачи распознавания диктора по...

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

Рис. 1.Результат кластеризации алгоритмом k-means (k=3). Метод k-means хорошо работает, когда кластеры представляют...

Оценка рисков информационной безопасности с помощью метода...

Алгоритм разделяет данные на k кластеров Si (I = 1, 2, …, k). Кластер Si связан с представителем (центр кластера) Ci.

Затем K-means алгоритм кластеризации классифицирует данные с исходными кластерами и центрами кластеров.

Методы решения задачи кластеризации и прогнозирования...

Все значения включим в множество . Это и есть шаг кластеризации.

Кластеры составляются до тех пор, пока есть значения атрибута , не вошедшие ни в один кластер.

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

Особенности использования мини-кластера при расчете...

Рис. 1. Структура мини-кластера. Кластер содержит управляющий узел CU и несколько вычислительных узлов n1, n2, . . . nk.

Таким образом, время решения существенно зависит от m и n. Были выполнены ряд решений при различных значениях m и n. Переменная m задает...

Обсуждение

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

Похожие статьи

Применение методов кластеризации для обработки новостного...

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

Цель алгоритма k-means – минимизировать среднее арифметическое сумм квадратов расстояний от каждого документа кластера до его центра, называемого...

Кластерный анализ разработки современных алгоритмов...

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

Кластерный анализ обработки данных может быть использован в области цифрового

Кластеризация компаний, развивает конкуренцию, распространяют свое влияние на...

Метод естественной кластеризации данных | Статья в журнале...

Метод естественной кластеризации данных. Автор: Демин Александр Викторович.

4. Повторять шаги 2, 3 пока центры кластеров не перестанут изменяться. Поскольку алгоритм k-means очень чувствителен к выбору начальных приближений центров классов, то на практике...

Использование матриц комбинаторного типа для построения...

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

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

Метод естественной кластеризации данных.

Метод k средних при решении задачи распознавания диктора по...

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

Рис. 1.Результат кластеризации алгоритмом k-means (k=3). Метод k-means хорошо работает, когда кластеры представляют...

Оценка рисков информационной безопасности с помощью метода...

Алгоритм разделяет данные на k кластеров Si (I = 1, 2, …, k). Кластер Si связан с представителем (центр кластера) Ci.

Затем K-means алгоритм кластеризации классифицирует данные с исходными кластерами и центрами кластеров.

Методы решения задачи кластеризации и прогнозирования...

Все значения включим в множество . Это и есть шаг кластеризации.

Кластеры составляются до тех пор, пока есть значения атрибута , не вошедшие ни в один кластер.

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

Особенности использования мини-кластера при расчете...

Рис. 1. Структура мини-кластера. Кластер содержит управляющий узел CU и несколько вычислительных узлов n1, n2, . . . nk.

Таким образом, время решения существенно зависит от m и n. Были выполнены ряд решений при различных значениях m и n. Переменная m задает...

Применение методов кластеризации для обработки новостного...

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

Цель алгоритма k-means – минимизировать среднее арифметическое сумм квадратов расстояний от каждого документа кластера до его центра, называемого...

Кластерный анализ разработки современных алгоритмов...

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

Кластерный анализ обработки данных может быть использован в области цифрового

Кластеризация компаний, развивает конкуренцию, распространяют свое влияние на...

Метод естественной кластеризации данных | Статья в журнале...

Метод естественной кластеризации данных. Автор: Демин Александр Викторович.

4. Повторять шаги 2, 3 пока центры кластеров не перестанут изменяться. Поскольку алгоритм k-means очень чувствителен к выбору начальных приближений центров классов, то на практике...

Использование матриц комбинаторного типа для построения...

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

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

Метод естественной кластеризации данных.

Метод k средних при решении задачи распознавания диктора по...

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

Рис. 1.Результат кластеризации алгоритмом k-means (k=3). Метод k-means хорошо работает, когда кластеры представляют...

Оценка рисков информационной безопасности с помощью метода...

Алгоритм разделяет данные на k кластеров Si (I = 1, 2, …, k). Кластер Si связан с представителем (центр кластера) Ci.

Затем K-means алгоритм кластеризации классифицирует данные с исходными кластерами и центрами кластеров.

Методы решения задачи кластеризации и прогнозирования...

Все значения включим в множество . Это и есть шаг кластеризации.

Кластеры составляются до тех пор, пока есть значения атрибута , не вошедшие ни в один кластер.

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

Особенности использования мини-кластера при расчете...

Рис. 1. Структура мини-кластера. Кластер содержит управляющий узел CU и несколько вычислительных узлов n1, n2, . . . nk.

Таким образом, время решения существенно зависит от m и n. Были выполнены ряд решений при различных значениях m и n. Переменная m задает...

Задать вопрос