數(shù)據(jù)挖掘?qū)д?第8章-聚類-2017-v3

第8章聚類分析:基本概念和算法8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

8.1概述8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

什么是聚類分析聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對象及其關(guān)系的信息，將數(shù)據(jù)對象分組。其目標(biāo)是，組內(nèi)的對象之間是相似的（相關(guān)的），而不同的組中的對象是不同的（不相關(guān)的）。組內(nèi)的相似性（同質(zhì)性）越大，組間差別越大，聚類就越好。Inter-clusterdistancesaremaximizedIntra-clusterdistancesareminimized聚類分析的應(yīng)用旨在理解生物學(xué)：分類、現(xiàn)類似功能的基因組信息檢索：將搜索結(jié)果分成若干簇氣候：分析極地和海洋大氣壓力模式醫(yī)學(xué)和心理學(xué)：識別不同類型的抑郁癥商業(yè)：將顧客劃分成若干組旨在實(shí)用匯總數(shù)據(jù)壓縮數(shù)據(jù)發(fā)現(xiàn)最近鄰ClusteringprecipitationinAustralia簇（Cluster）的定義是不精確的Howmanyclusters?FourClusters

TwoClusters

SixClusters

8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

不同的簇類型Well-separatedclusters（明顯分離的簇）Center-basedclusters（基于中心的簇）Contiguousclusters（基于鄰近的簇）Density-basedclusters（基于密度的簇）PropertyorConceptual（概念簇）明顯分離的簇:簇是對象的集合，不同組中的任意兩點(diǎn)之間的距離都大于組內(nèi)任意兩點(diǎn)之間的距離?；谠偷拇兀ɑ谥行牡拇兀┐厥菍ο蟮募?，其中每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近（或更加相似）。對于具有連續(xù)屬性的數(shù)據(jù)，簇的原型通常是質(zhì)心，即簇中所有點(diǎn)的平均值。當(dāng)質(zhì)心沒有意義是，原型通常是中心點(diǎn)，即簇中最有代表性的點(diǎn)。這種簇傾向于呈球狀。基于圖的（基于鄰近的簇）：如果數(shù)據(jù)用圖表示，其中節(jié)點(diǎn)是對象，而邊代表對象之間的聯(lián)系，則簇可以定義為連通分支，即互相連通但不與組外對象連通的對象組?；趫D的簇一個重要例子就是基于臨近的簇，其中兩個對象是相連的，僅當(dāng)他們的距離在指定的范圍之內(nèi)。也就是說，每個對象到該簇某個對象的距離比不同簇中的任意點(diǎn)的距離更近?；诿芏鹊模捍厥菍ο蟮某砻軈^(qū)域，被低密度的區(qū)域環(huán)繞。當(dāng)簇不規(guī)則或互相盤繞，并且有噪聲和離群點(diǎn)時，常常使用基于密度的簇定義。不同的簇類型8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

聚類算法的分類大體上，主要的聚類算法可以劃分為如下幾類：劃分方法層次方法基于密度的方法基于網(wǎng)格的方法聚類算法的分類1.劃分方法（partitionmethod）給定一個有N個元組或者記錄的數(shù)據(jù)集，劃分方法將構(gòu)造K個分組，每一個分組就代表一個聚類，K<N。而且這K分組滿足下列條件：1）每一個分組至少包含一個數(shù)據(jù)記錄；2）每一個數(shù)據(jù)記錄隸屬于且僅屬于一個分組；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后分組方案都較前一次好，所謂的“好”的標(biāo)準(zhǔn)就是同一分組的記錄越相似越好，而不同分組中的記錄則越相異越好。最著名與最常用的劃分方法是k-均值方法和k-中心點(diǎn)方法。聚類算法的分類2.基于層次的方法（hierarchicalmethod）一個層次的聚類方法是將數(shù)據(jù)對象組成一棵聚類的樹。根據(jù)層次分解是自底向上還是自頂向下形成，層次的聚類方法可以進(jìn)一步分為聚合式層次聚類（agglomerative）和分裂式層次聚類（divisive）。聚合式的層次聚類，其層次過程的方向是自底向上的。將樣本集合中的每個對象作為一個初始簇，然后將最近的兩個簇合并，組成新的簇，再將這個新簇與剩余的簇中最近的合并，這種合并過程需要反復(fù)進(jìn)行，直到所有的對象最終被聚到一個簇中。分裂式的層次聚類，其層次過程的方向是自頂向下的，最初先將有關(guān)對象放到一個簇中，然后將這個簇分裂，分裂的原則是使兩個子簇之間的聚類盡可能的遠(yuǎn)，分裂的過程也反復(fù)進(jìn)行，直到某個終止條件被滿足時結(jié)束。不論是合并還是分解的過程，都會產(chǎn)生樹狀結(jié)構(gòu)，樹的葉子節(jié)點(diǎn)對應(yīng)各個獨(dú)立的對象，頂點(diǎn)對應(yīng)一個包含了所有對象的簇。常見的層次聚類算法有：BIRCH算法、CURE算法、ROCK算法等。聚類算法的分類3.基于密度的方法（density-basedmethod）基于密度的方法與其他方法的一個最根本的區(qū)別是：它不是基于各種各樣的距離，而是基于密度的，它將簇看做是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度對象區(qū)域，這種方法的優(yōu)勢是善于發(fā)現(xiàn)空間數(shù)據(jù)庫中任意形狀的聚類?；诿芏鹊木垲惛鶕?jù)空間密度的差別，把具有相似密度的點(diǎn)作為聚類。由于密度是一個局部概念，這類算法又稱為局部聚類（LocalClustering）。一般情況下，基于密度的聚類只掃描一次數(shù)據(jù)庫，故又稱為是單次掃描聚類（SingleScanClustering）?；诿芏鹊木垲惙椒ㄖ饕篋BSCAN算法、DENCLUE算法。聚類算法的分類4.基于網(wǎng)格的方法（density-basedmethod）基于網(wǎng)格的方法采用一個多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)。它將數(shù)據(jù)空間量化，并將其劃分為有限數(shù)目的網(wǎng)格單元，所有的聚類操作都在網(wǎng)格上進(jìn)行。該算法的優(yōu)勢在于處理速度快，處理時間與數(shù)據(jù)對象的數(shù)目無關(guān)?；诰W(wǎng)格的聚類方法有STING算法和CLIQUE算法等。8.2K-均值聚類算法

K-meansClustering

K-meansClusteringK均值是基于原型的、劃分的聚類技術(shù)。典型的基于原型的、劃分的聚類算法：K均值、K中心點(diǎn)。K均值用質(zhì)心定義原型，其中質(zhì)心是一組點(diǎn)的均值。K均值聚類用于n維連續(xù)空間中的對象。它試圖發(fā)現(xiàn)用戶指定個數(shù)（K）的簇（由質(zhì)心代表）。K中心點(diǎn)使用中心點(diǎn)定義原型，其中中心點(diǎn)是一組點(diǎn)中最有代表性的點(diǎn)。K中心點(diǎn)聚類可以用于廣泛的數(shù)據(jù)，因?yàn)樗恍枰獙ο笾g的鄰近性度量。盡管質(zhì)心幾乎從來不對應(yīng)實(shí)際的數(shù)據(jù)點(diǎn)，但是根據(jù)定義，中心點(diǎn)必須是一個實(shí)際的數(shù)據(jù)點(diǎn)。8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

基本K均值算法K均值的算法步驟：首先選擇K個初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個數(shù)。每個點(diǎn)指派到最近的質(zhì)心，而指派到一個質(zhì)心的點(diǎn)集為一個簇。然后，根據(jù)指派到簇的點(diǎn)，更新每個簇的質(zhì)心。重復(fù)指派和更新步驟，直到簇不發(fā)生變化，或等價的，直到質(zhì)心不發(fā)生變化。算法流程如下：K-meansClustering:ExampleK-meansClustering:ExampleK-均值聚類的距離度量與目標(biāo)函數(shù)慮鄰近度量為歐幾里得距離的數(shù)據(jù),度量聚類質(zhì)量最常用的是誤差的平方和(SumofSquaredError,SSE)對于每個點(diǎn),其誤差是到最近質(zhì)心的距離為了得到SSE,我們對每個點(diǎn)的誤差求平方和x是簇Ci的點(diǎn),ci

是簇Ci的代表點(diǎn)可以證明ci

對應(yīng)于簇的質(zhì)心(均值)給定兩個聚類,我們可以選擇具有最小SSE的聚類其它距離度量K-means也可以用于非歐氏空間數(shù)據(jù)例,文檔數(shù)據(jù)通常,文檔用余弦相似性度量距離是相異性度量,而余弦是相似性度量質(zhì)心仍然用均值最近的質(zhì)心是最相似的質(zhì)心目標(biāo):最大化簇中文檔與簇的質(zhì)心的相似性總凝聚度（totalcohesion）其它距離度量K均值：鄰近度、質(zhì)心和目標(biāo)函數(shù)的常見選擇

鄰近度函數(shù)質(zhì)心目標(biāo)函數(shù)曼哈頓距離（L1）中位數(shù)最小化對象到其簇質(zhì)心的L1距離和平方歐幾里得距離均值最小化對象到其簇質(zhì)心的L2距離的平方和余弦均值最大化對象與其簇質(zhì)心的余弦相似度和Bregman散度均值最小化對象到其簇質(zhì)心的Bregman散度和8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

基本K均值算法存在的問題不同的初始質(zhì)心將收斂得到不同的目標(biāo)函數(shù)，可能只能達(dá)到局部最優(yōu)解。隨機(jī)選取初始質(zhì)心，拙劣的初始質(zhì)心，可能導(dǎo)致很糟糕的聚類結(jié)果?？赡墚a(chǎn)生空簇容易受到離群點(diǎn)的影響不能處理非球形簇、不同尺寸和不同密度的簇。不同的初始質(zhì)心導(dǎo)致不同的SSESub-optimalClusteringOptimalClusteringOriginalPoints基本K均值算法存在的問題拙劣的初始質(zhì)心基本K均值算法存在的問題解決初始質(zhì)心的選擇問題：多次運(yùn)行，選取最小的SSE采用小部分?jǐn)?shù)據(jù)，并進(jìn)行層次聚類得到初始質(zhì)心選擇多于K個的初始質(zhì)心，并在其中選出K個分布廣泛的作為初始質(zhì)心。隨機(jī)地選擇第一個點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個點(diǎn)。然后，對于每個后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心最遠(yuǎn)的點(diǎn)。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的，而且是散開的。但是，這種方法可能選中離群點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開銷也非常大。為了克服這個問題，通常該方法用于點(diǎn)樣本。基本K均值算法存在的問題不同的初始質(zhì)心將收斂得到不同的目標(biāo)函數(shù)，可能只能達(dá)到局部最優(yōu)解。隨機(jī)選取初始質(zhì)心，拙劣的初始質(zhì)心，可能導(dǎo)致很糟糕的聚類結(jié)果?？赡墚a(chǎn)生空簇容易受到離群點(diǎn)的影響不能處理非球形簇、不同尺寸和不同密度的簇。如果所有的點(diǎn)在指派步驟都未分配到某個簇，就會得到空簇。如果這種情況發(fā)生，則需要某種策略來選擇一個替補(bǔ)質(zhì)心，否則的話，平方誤差將會偏大。一種方法是選擇一個距離當(dāng)前任何質(zhì)心最遠(yuǎn)的點(diǎn)。這將消除當(dāng)前對總平方誤差影響最大的點(diǎn)。另一種方法是從具有最大SSE的簇中選擇一個替補(bǔ)的質(zhì)心。這將分裂簇并降低聚類的總SSE。如果有多個空簇，則該過程重復(fù)多次。基本K均值算法存在的問題不同的初始質(zhì)心將收斂得到不同的目標(biāo)函數(shù)，可能只能達(dá)到局部最優(yōu)解。隨機(jī)選取初始質(zhì)心，拙劣的初始質(zhì)心，可能導(dǎo)致很糟糕的聚類結(jié)果。可能產(chǎn)生空簇容易受到離群點(diǎn)的影響不能處理非球形簇、不同尺寸和不同密度的簇。使用平方誤差時，離群點(diǎn)會過度影響所發(fā)現(xiàn)的簇在可能的條件下，提前刪除離群點(diǎn)也可以在后處理時識別離群點(diǎn)基本K均值算法存在的問題不同的初始質(zhì)心將收斂得到不同的目標(biāo)函數(shù)，可能只能達(dá)到局部最優(yōu)解。隨機(jī)選取初始質(zhì)心，拙劣的初始質(zhì)心，可能導(dǎo)致很糟糕的聚類結(jié)果。可能產(chǎn)生空簇容易受到離群點(diǎn)的影響不能處理非球形簇、不同尺寸和不同密度的簇不能處理非球形簇、不同尺寸和不同密度的簇OriginalPointsK-means(3Clusters)OriginalPointsK-means(3Clusters)不能處理非球形簇、不同尺寸和不同密度的簇OriginalPointsK-means(2Clusters)不能處理非球形簇、不同尺寸和不同密度的簇OriginalPoints K-meansClusters一個可能的解決方法：生產(chǎn)多個初始的簇，再將其中部分簇進(jìn)行合并。不能處理非球形簇、不同尺寸和不同密度的簇OvercomingK-meansLimitationsOriginalPoints K-meansClustersOvercomingK-meansLimitationsOriginalPoints K-meansClustersk-中心點(diǎn)聚類方法k-均值算法對離群點(diǎn)很敏感!因?yàn)榫哂刑貏e大的值的對象可能顯著地影響數(shù)據(jù)的均值.k-中心點(diǎn)(k-Medoids)不采用簇中對象的平均值作為參照點(diǎn),而是選用簇中最靠近中心的對象,即中心點(diǎn)(medoid)作為參照點(diǎn).

0123456789100123456789100123456789100123456789108.3凝聚層次聚類層次聚類將數(shù)據(jù)對象以樹狀的層次關(guān)系來看待。依層次建構(gòu)的方式，一般分成兩種來進(jìn)行：凝聚的(Agglomerative)分裂的(Divisive)層次聚類層次聚類凝聚的(Agglomerative):StartwiththepointsasindividualclustersAteachstep,mergetheclosestpairofclustersuntilonlyonecluster(orkclusters)left分裂的(Divisive):Startwithone,all-inclusiveclusterAteachstep,splitaclusteruntileachclustercontainsapoint(ortherearekclusters)TraditionalhierarchicalalgorithmsuseasimilarityordistancematrixMergeorsplitoneclusteratatime8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

基本的凝聚層次聚類算法Basic基本算法流程關(guān)鍵操作是如何計(jì)算簇之間的鄰近性如何計(jì)算簇之間的鄰近性MIN（單鏈：singlelinkage)：又稱最短距離法。MAX（全鏈：completelinkage)：又稱最長距離法。組平均(GroupAverage)DistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWard’sMethodusessquarederrorSimilarity?HowtoDefineInter-ClusterSimilarityMINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWard’sMethodusessquarederrorHowtoDefineInter-ClusterSimilarityMINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWard’sMethodusessquarederrorHowtoDefineInter-ClusterSimilarityMINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWard’sMethodusessquarederrorHowtoDefineInter-ClusterSimilarityMINMAXGroupAverageDistanceBetweenCentroidsOthermethodsdrivenbyanobjectivefunctionWard’sMethodusessquarederror

8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

Example點(diǎn)x坐標(biāo)y坐標(biāo)P1P2P3P4P5p60.40050.21480.34570.26520.07890.45480.53060.38540.31560.18750.41390.3022P1P2P3P4P5P6P1P2P3P4P5p60.00000.23570.22180.36880.34210.23470.23570.00000.14830.20420.13880.25400.22180.14830.00000.15130.28430.11000.36880.20420.15130.00000.29320.22160.34210.13880.28430.29320.00000.39210.23470.25400.11000.22160.39210.0000簇相似性:MINorSingleLinkSimilarityoftwoclustersisbasedonthetwomostsimilar(closest)pointsinthedifferentclustersDeterminedbyonepairofpoints,i.e.,byonelinkintheproximitygraph例:dist({3,6},{2,5})=min(dist(3,2),dist(6,2),dist(3,5),dist(6,5)) =min(0.15,0.25,0.28,0.39)=0.15優(yōu)缺點(diǎn)：MIN擅長處理非橢圓形的簇對噪聲和離群點(diǎn)很敏感簇相似性:MAXorCompleteLinkageSimilarityoftwoclustersisbasedonthetwoleastsimilar(mostdistant)pointsinthedifferentclustersDeterminedbyallpairsofpointsinthetwoclustersExampledist({3,6},{4})=max(dist(3,4),dist(6,4))=max(0.15,0.22)=0.22dist({3,6},{2,5})=max(dist(3,2),dist(6,2),dist(3,5),dist(6,5)) =max(0.15,0.25,0.28,0.39)=0.39dist({3,6},{1})=max(dist(3,1),dist(6,1))=max(0.22,0.23)=0.23優(yōu)缺點(diǎn)：MAX對噪聲和離群點(diǎn)不太敏感TwoClustersTwoClusters

可能使大的簇破裂

偏好球形簇簇相似性:GroupAverageProximityoftwoclustersistheaverageofpairwiseproximitybetweenpointsinthetwoclusters.NeedtouseaverageconnectivityforscalabilitysincetotalproximityfavorslargeclustersExampledist({3,6,4},{1})=(0.22+0.37+0.23)/(3*1)=0.28dist({2,5},{1})=(0.2357+0.3421)/(2*1)=0.2889dist({3,6,4},{2,5})=(0.15+0.28+0.25+0.39+0.20+0.29)/(3*2)=0.26dist({3,6,4},{2,5})比dist({3,6,4},{1})和dist({2,5},{1})小，簇{3,6,4}和{2,5}在第4階段合并

簇相似性:GroupAverageExample:GroupAverage8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

層次聚類的主要問題（1）缺乏全局目標(biāo)函數(shù)。凝聚層次聚類不能視為全局優(yōu)化一個目標(biāo)函數(shù)。這樣的方法沒有局部最小問題或很難選擇初始點(diǎn)的問題。（2）處理不同大小的聚類能力。即如何處理待合并的簇對的相對大小。有兩種方法：加權(quán)，平等的對待所有簇，非加權(quán)，考慮每個簇的點(diǎn)數(shù)。注意：術(shù)語加權(quán)和非加權(quán)是對數(shù)據(jù)而言，而不是對簇。即，平等的對待不同大小的簇意味著賦予不同簇中的點(diǎn)不同的權(quán)值，而考慮簇的大小則賦予不同簇中的點(diǎn)相同的權(quán)值。一般地，非加權(quán)的方法更可取，除非有理由相信個體點(diǎn)具有不同的權(quán)值：例如，或許對象類非均勻地抽樣（3）合并決策是最終的。對于合并兩個簇，凝聚層次算法傾向于作出好的局部決策，因?yàn)樗鼈兛梢允褂盟悬c(diǎn)的逐對相似度信息。然而，一旦作出合并兩個簇的決策，以后就不能撤銷。有一些技術(shù)試圖克服“合并是最終的”這一限制。一種方法試圖通過如下方法來修補(bǔ)層次聚類，移動樹的分支以改善全局目標(biāo)函數(shù)。另一種方法使用劃分聚類技術(shù)（如K均值）來創(chuàng)建許多小簇，然后從這些小簇出發(fā)進(jìn)行層次聚類。8.1概述

8.1.1什么是聚類分析

8.1.3不同的簇類型

補(bǔ)充

聚類算法的分類

8.2K-均值聚類算法

8.2.1基本K均值算法

基本K均值算法存在的問題

8.3凝聚層次聚類

8.3.1基本的凝聚層次聚類算法

8.3.2如何計(jì)算簇之間的鄰近性

8.3.4層次聚類的主要問題

8.4DBSCAN

8.4DBSCANDBSCANDBSCAN:Ester等(KDD’96)DBSCAN是一種基于密度的聚類算法，簇的個數(shù)由算法自動的確定。低密度區(qū)域中的點(diǎn)被視為噪聲而忽略，因而DBSCAN不產(chǎn)生完全聚類。密度：數(shù)據(jù)集中特定點(diǎn)的密度通過對該點(diǎn)的Eps半徑之內(nèi)的點(diǎn)計(jì)數(shù)（包括點(diǎn)本身）來估計(jì)。核心點(diǎn)：這些點(diǎn)在基于密度的簇內(nèi)部。一個點(diǎn)是核心點(diǎn)，如果該點(diǎn)的給定鄰域內(nèi)的點(diǎn)的個數(shù)超過給定的閾值MinPts，其中MinPts也