基于流形距離的密度峰值快速搜索聚類算法

張嘉琪　張紅云

摘要：針對2014年6月發表在Science上的基于密度峰和快速搜索的聚類算法容易忽略無密度極值的簇的缺陷，提出了一種基于流形距離的密度峰值快速搜索聚類算法。算法利用流形距離彌補了傳統歐式距離對于復雜數據無法反應聚類的全局一致性（即位于同一個類中的樣本點之間有較高的相似度）的缺陷，通過近鄰點充分挖掘復雜數據的流形結構信息，使處于同一個流形中的樣本點之間相似性較高，從而正確找到密度極值點作為聚類中心點，完成聚類。本文算法能夠發現較復雜的流形結構，在公開數據集上能取得較好的實驗結果。

關鍵詞： 聚類；流形距離；密度極值；全局一致性；聚類中心

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）02-0179-04

Clustering by Fast Search and ?nd of Density Peaks Based on Manifold Distance

ZHANG Jia-qi1，2，ZHANG Hong-yun1，2

（1.Department of Computer Science and Technology， Tongji University， Shanghai 201804， China；2.Key Laboratory of Embedded Systems and Service Computing，Ministry of Education，Tongji University，Shanghai 201804， China）

Abstract：The clustering algorithm based on density peak and fast search， which was published on Science in June 2014， is easy to ignore the cluster which has no density extreme value.So We propose an algorithm based on manifold distance to solve this problem.Instead of Euclidean distance，the algorithm uses manifold distance to reflect the global consistency of samples，which means the samples in the same cluster have high similarity.We find manifold structure information of complex data by neighbor points ，so that samples in the same manifold have high similarity and the cluster center is easy to find. In this paper， we can find manifold structure of complex data， and obtain better results in the open data sets.

Key words：clustering；manifold distance；density peak； global consistency；clustering center

1 概述

聚類作為一種有效的數據分析手段，已成為模式識別，人工智能，數據挖掘等領域的研究熱點。在聚類分析過程中，不需要任何先驗知識或者是假設，因此聚類是一種無監督學習過程。聚類算法包括劃分式聚類方法、層次聚類方法、基于密度的聚類方法和基于網格的聚類方法，以及基于模型的聚類算法.K-means[1]是應用范圍最廣的劃分式聚類算法.然而，K-means算法的聚類結果依賴于初始類簇中心的選取，而且傾向于發現凸形狀的簇，對噪聲點和離群點敏感，且聚類個數K需要事先設定.針對K-means的缺陷，出現了K-modes[2]算法等諸多改進算法. DBSCAN[3]是一種比較典型的基于密度的聚類方法，要求聚類空間中的一定區域內所包含對象（點或其他空間對象）的數目不小于某一給定閾值。……