Бумага | Кластеризация путем быстрого поиска и обнаружения пиков плотности

Оригинал: Кластеризация путем быстрого поиска и нахождения пиков плотности
Алекс Родригес и Алессандро Лайо
Источник: Наука 344.6191 (2014), 1492-1496.

Резюме

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

текст

Различные стратегии кластеризации

дистанционный подход

существуетK-meansиK-medoids, кластер представляет собой совокупность данных, характеризующихся небольшим расстоянием от центра кластера.

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

намекать:K-均值 (K-Means)Метод K-средних имеет смысл только тогда, когда определено среднее значение в кластере, и метод K-средних не работает, когда задействованы данные с номинальными свойствами. И здесь можно использоватьK-众数 (K-Modes)вариант , то есть с использованием基于频率способ обновления режима кластеров, кластеризующий данные с номинальными свойствами. Конечно, естьK-Prototype $^{[1,2]}$ ,K-Means++ $^{[3]}$ и другие оптимизированные версии алгоритма.

Методы, основанные на плотности

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

DBSCAN(Density-Based Spatial Clustering of Applications with Noise) — это алгоритм кластеризации на основе плотности, который определяет кластер как наибольший набор точек, связанных плотностью, которые могут разделить поля с достаточно высокой плотностью на кластеры. Кластеры произвольной формы можно найти в зашумленных пространственных базах данных.

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

Улучшенный метод в этой статье

Во-первых, алгоритм предполагает, что центры кластеров邻居点в окружении и с большей плотностью任何点Там относительно большое расстояние. Для каждой точки данных i, чтобы рассчитать两个量: локальная плотность точек $\rho_i$ и расстояние от этой точки до точки с более высокой локальной плотностью $\delta_i$ . Оба этих значения зависят от расстояния между точками данных ${d}_{ij}$ (евклидово расстояние, также известное как欧式距离). Локальная плотность точек данных определяется как:

ρ i =∑ j χ( d i j −d c ) ρi=∑jχ(dij−dc)

в $\chi(x)$ является функцией 0-1, если x ;в противном случае $\chi(x) = 0$ , $d_{c}$ Является截断距离. в основном, $\rho_i$ равно расстоянию от точки i меньше, чем $d_{c}$ количество баллов. Алгоритмы работают только с различиями $\rho_i$ чувствителен к относительному размеру , что означает, что для больших наборов данных результаты анализа $d_{c}$ есть хороший выбор鲁棒性.

$\delta_i$ рассчитывается между точками最小距离для измерения, то есть минимальное расстояние между точкой данных i и ее ближайшей, более плотной точкой j:

Подсказка: как вы можете видеть на рис. 1-1.(A), точки данных расположены в порядке убывания плотности.

δ i =m in j :ρ j >ρ i (d i j ) δi=minj:ρj>ρi(dij)

Если точка данных i является самой плотной точкой, $\delta_i$ максимальное расстояние до точки данных i среди всех узлов:

δ i =m ax j (d i j ) δi=maxj(dij)

Как показано на рисунке 1-1, он показывает основную идею алгоритма. Рисунок 1-1.(A) показывает 28 точек в двумерном пространстве,且 A 中数据点是按照密度降序排列. На рис. 1-1.(B) $\rho_i$ как абсцисса, $\delta_i$ В качестве ординаты нарисуйте двумерную диаграмму и назовите ее диаграммой решений. можно найти в точках 1 и 10 $\rho_i$ и $\delta_i$ является самым большим, поэтому он принимается за центр кластера.

пункт 9 и пункт 10 $\rho_i$ похоже, но $\delta_i$ Значения совсем разные: точка 9 принадлежит кластеру точки 1, а несколько других выше $\rho_i$ точки находятся очень близко к ней, однако точка 10 имеет более высокую плотность ближайших соседей, принадлежащих другим кластерам.

Так что, как и ожидалось, только с высоким $\delta_i$ и относительно высокий $\rho_i$ Дело в том类簇中心. Поскольку точки 26, 27, 28 изолированы, существует относительно высокая $\delta_i$ стоимость и низкая $\rho_i$ значений, их можно рассматривать как кластеры отдельных точек, т.е.异常点.

Рисунок 1-1 Дисплей алгоритма в двумерном пространстве

После того как центр кластера найден, каждая оставшаяся точка ставится в соответствие тому кластеру, к которому принадлежит ее ближайший сосед с большей плотностью. Для назначения кластера класса требуется только一步即可完成, в отличие от других алгоритмов, которые делают迭代优化.

В кластерном анализе важно количественно измерить надежность заданий. В этом алгоритме сначала определите边界区域(то есть множество точек, отнесенных к этому кластеру, и расстояние от точек других кластеров меньше, чем d_c ), то для каждого кластера найти точку с наибольшей плотностью в его граничной области $\rho_b$ , а так как представляет собой плотность точки. Если отношение значений локальной плотности в кластере $\rho_b$ Крупные точки расцениваются как ядерная часть кластера (то есть надежность отнесения к кластеру высокая), остальные точки (отношение значений локальной плотности в кластере $\rho_b$ маленькие точки) считаются кластерообразными光晕部分(также рассматривается как шум).

Рисунок 1-2 Результаты синтетического распределения точек

(A) Распределение вероятностей для нанесенного на график распределения точек. (B и C) Распределение точек для 4000 и 1000 точек выборки соответственно. И каждая точка представлена своим цветовым кластером, а черная точка принадлежит гало-кластеру (шумовой точке). (D и E) — соответствующие решающие диаграммы (B и C), центры которых раскрашены соответствующими кластерами. (F) Оценка, присвоенная неправильно сгруппированным точкам в зависимости от размера выборки. Столбики погрешностей представляют собой стандартную ошибку среднего значения.

Как видно из рисунка 1-2.(F), доля ошибочно классифицированных точек остается ниже 1% даже в небольшой выборке, состоящей всего из 1000 точек, что указывает на хорошую надежность алгоритма.

Как видно из рис. 1-3, алгоритм может достигать хороших результатов кластеризации для различных уровней данных (результаты тестовых случаев в цитируемой литературе показаны на рисунке).

Рисунок 1-3 Результаты тестового примера из цитируемой литературы

использованная литература

[1] Huang Z. Clustering large data sets with mixed numeric and categorical values [C]. 1997: 21-34.
[2] Huang Z. Extensions to the k-means algorithm for clustering large data sets with categorical values [J]. Data mining and knowledge discovery, 1998, 2(3): 283-304.
[3] San O M, Huynh V N, Nakamori Y. A clustering algorithm for mixed numeric and categorical data [J]. Journal of Systems Science and Complexity, 2003, 16(4): 562-571.

Автор этой статьи: Kofe
Ссылка на эту статью: Woohoo.KOF ES.Talent/2018/05/c олень…
Уведомление об авторских правах:Все статьи в этом блоге, если не указано иное, используютCC BY-NC-SA 3.0соглашение. Пожалуйста, укажите источник!