聚類被廣泛使用。例如，在商業應用中，聚類可以幫助營銷人員根據客戶的屬性對客戶進行分層，並找到不同的客戶群體及其購買傾向(客戶根據顏色偏好進行分類，如下圖所示)。通過這種方式，公司可以更有效地找到潛在市場，開發定制產品和服務。在文本分析處理中，聚類可以幫助記者根據話題相似度對最新微博進行分類，快速獲取熱點新聞和關註對象。在生物醫學中，我們可以通過對具有相似表達譜的基因進行聚類來了解未知基因的功能。
因為聚類是壹種無監督的學習方法，所以不同的聚類方法基於不同的假設和數據類型。因為通常可以從不同的角度對數據進行分類，所以不存在通用的聚類算法，每種聚類算法都有其局限性和偏見。也就是說，某些聚類算法在市場數據中可能非常有效，但在基因數據中卻無能為力。
聚類算法有很多，包括基於劃分的聚類算法(如k-means)、層次聚類算法(如BIRCH)、基於密度的聚類算法(如DBSCAN)、基於網格的聚類算法(如STING)等等。本文將介紹聚類中最常用的方法之壹——基於密度的聚類。
與其他聚類方法相比，基於密度的聚類方法可以在噪聲數據中找到各種形狀和大小的聚類。DBSCAN(Ester，1996)就是這類方法中最典型的算法之壹(DBSCAN獲得2014 SIG KDD時間測試獎)。核心思想是先找到高密點，然後把相似的高密點壹步步連接起來，生成各種簇。算法的實現是以每個數據點為圓心，以eps為半徑畫壹個圓(稱為鄰域eps-neigbourhood)，然後統計這個圓上有多少個點，就是點密度值。然後我們可以選擇壹個密度閾值，比如圓內中心點點數小於MinPts的點為低密度點，中心點密度大於等於MinPts的點為高密度點(稱為核心點)。如果在另壹個高密點的圓上有壹個高密點，我們就把這兩個點連起來，這樣就可以連續串聯很多個點。之後，如果高密點所在的圈裏有壹個低密度點，就把它連接到最近的高密點上，這個高密點就叫邊界點。這樣所有能連在壹起的點就成了壹個簇，不在任何高密度點的圓內的低密度點就是異常點。下圖顯示了DBSCAN的工作原理。
由於DBSCAN是通過連續連接鄰域內的高密度點來發現簇的，所以只需要定義鄰域大小和密度閾值，就可以發現不同形狀和大小的簇。下圖顯示了二維空間中DBSCAN聚類的結果。
DBSCAN算法的偽代碼表示如下:
由於DBSCAN使用全局密度閾值MinPts，所以只能找到由密度不小於MinPts的點組成的簇，即很難找到不同密度的簇。其成功和失敗的例子如下:
為了尋找不同密度的聚類，人們發明了很多新的方法，比如光學(排序點識別聚類結構)，將鄰域點按照密度排序，然後用可視化的方法尋找不同密度的聚類，如下圖所示。光學必須通過其他算法在視覺圖上找到“谷”才能找到簇，因此其性能直接受到這些算法的制約。
此外，SNN使用壹種基於KNN的相似度計算方法來改進DBSCAN。對於每個點，我們找到空間中最近的k個點(稱為k近鄰)。兩點之間的相似度是統計這兩點享有多少K個最近鄰點。如果這兩點沒有* * * K個最近鄰或者都不是對方的K個最近鄰，那麽這兩點的相似度為0。然後我們用SNN相似度代替DBSCAN中的距離公式，重新計算每個點的鄰域和密度，這樣就可以找到不同密度的聚類。SNN的核心是用壹個基於每壹對點共享的鄰域的範圍來代替原來的密度計算，同時忽略其真實的密度分布。SNN的缺點是必須定義最近鄰數k，其性能對k的大小非常敏感，下圖是SNN計算相似度的方法。
《科學》雜誌在2014中發表了壹個通過快速搜索和尋找密度峰值(DP)的聚類，其中也使用了壹種可視化的方法來幫助尋找不同密度的簇。其思想是每個聚類都有壹個最大密度點作為聚類中心，每個聚類中心吸引並連接周圍密度較低的點，不同的聚類中心點相對較遠。為了實現這個想法，它首先計算每個點的密度(即鄰域EPS-neighbourhood中有多少個點)，然後計算每個點到其最近的密度比它高的點的距離。這樣我們每個點都有兩個屬性值，壹個是它自己的密度值，壹個是它到最近的密度比它高的點的距離。對於這兩個屬性，我們可以生成壹個2-D圖(決策圖)，所以右上角的點可以代表不同類的中心，也就是密度高且遠離其他類的中心。然後我們可以逐漸地將其他點連接到最近和最密集的點，直到我們最終連接到壹個簇的中心點。這樣，所有共享壹個聚類中心的點都屬於壹個聚類，而距離其他點較遠且密度較低的點就是異常點。因為這種方法基於相對距離和相對密度來連接點，所以可以找到不同密度的簇。DP的缺點是每個聚類必須有壹個最大密度點作為聚類中心點。如果壹個簇的密度分布與壹個簇的密度分布相同或者壹個簇有多個高密度的點，那麽它會把壹些簇分成幾個子簇。另外，DP需要用戶指定有多少個集群，在實際操作中需要不斷調整。下圖顯示了由DP生成的決策圖。
另外，密度比估計可以用來克服DBSCAN不能發現不同密度簇的缺陷。密度比的核心思想是計算每個點的密度與其鄰域密度的比值，然後用密度比計算代替DBSCAN的密度計算來尋找核心點，其他過程與DBSCAN相同。這樣，每個局部高密度點將被選為核心點，這樣就可以發現不同密度的簇。基於這壹思路，我們還可以根據原始數據的密度分布對其進行歸壹化處理，即擴大高密度區域，繼續縮小低密度區域。這樣，密度不同的簇就可以變成密度相近的簇，我們就可以直接在標準化的數據上運行DBSCAN了。這種方法需要用戶設置鄰域範圍來計算密度比。下圖是標準化前後的數據分布對比。
基於密度的聚類是壹種非常直觀的聚類方法，即將相鄰的高密度區域訓練成壹個簇。該方法可以發現各種大小和形狀的簇，並具有壹定的抗噪聲特性。在日常應用中，我們可以使用不同的索引方法或基於網格的方法來加快密度估計，提高聚類的速度。基於密度的聚類也可以用於流數據和分布式數據。有關其他方向的應用，請參見(Aggarwal 2013)。
DP:？/MATLAB central/file exchange/53922-density clust
DBSCAN，光學和密度比:/項目/密度比/
阿加瓦爾，C. C .，& amp雷迪，C. K .(編輯。).(2013).算法和應用。CRC出版社。
安科斯特，m，布魯尼格，M. M，克裏格爾，H. P。桑德，J. (1999，六月)。光學:對點進行排序以識別集群結構。《美國計算機學會記錄》(第28卷，第2期，第49-60頁)。ACM。
Ert？z，l，Steinbach，m。Kumar，V. (2003年5月)。在嘈雜的高維數據中尋找不同大小、形狀和密度的聚類。2003年SIAM數據挖掘國際會議論文集(第47-58頁)。工業和應用數學學會。
Ester，m .，Kriegel，H. P .，Sander，j .徐，X. (1996，八月)。壹種基於密度的發現帶噪聲的大型空間數據庫中聚類的算法。在SIGKDD(第96卷，第34期，第226-231頁)。
韓俊傑，裴俊傑。坎伯，M. (2011)。數據挖掘:概念和技術。愛思唯爾。
羅德裏格斯，a。萊奧公司(2014)。通過快速搜索和尋找密度峰值進行聚類。理科，344(6191)，1492-1496。
朱玉英、丁克明、&卡曼，M. J. (2016)。基於密度比的聚類發現不同密度的聚類。模式識別，第60卷，2016，第983-997頁，ISSN 0031-3203。