http://blog.sina.com.cn/s/blog_6002b97001014nja.html

4、聚類

聚類分析提供由個別數(shù)據(jù)對象到數(shù)據(jù)對象所指派到簇的抽象。此外，一些聚類技術(shù)使用簇原型（即代表簇中其他對象的數(shù)據(jù)對象）來刻畫簇的特征。聚類分析是研究發(fā)現(xiàn)最具有代表性的簇原型的技術(shù)。回歸和PCA的時間復(fù)雜度都是O(m²)。注意：簇的定義是不精確的，而最好的定義依賴于數(shù)據(jù)的特征和期望的結(jié)果。聚類分析與其他將數(shù)據(jù)對象分組的技術(shù)有關(guān)。監(jiān)督學(xué)習(xí)（也叫監(jiān)督分類或分類）：使用一個由類標(biāo)號已知的對象開發(fā)的模型，對新的、無標(biāo)記的對象賦予一個類標(biāo)號。非監(jiān)督學(xué)習(xí)（也叫非監(jiān)督分類或聚類）。在數(shù)據(jù)挖掘中，不附加任何條件使用術(shù)語分類時，通常是指監(jiān)督分類。盡管術(shù)語分割和劃分有時也作聚類的同義詞，但是這些術(shù)語通常用來表示傳統(tǒng)的聚類分析之外的方法。

4.1?聚類類型

不同的聚類類型：層次的（嵌套的）與劃分的（非嵌套的），互斥的，重疊的與模糊的，完全的與部分的。劃分聚類：簡單地將數(shù)據(jù)對象劃分成不重疊的子集（簇），使得每個數(shù)據(jù)對象恰在一個子集中。層次聚類：允許簇具有子簇，層次聚類是嵌套簇的集簇，組織成一棵樹。層次聚類可以看作劃分聚類的序列，劃分聚類可以通過取序列的任意成員得到，即通過在一個特定層剪斷層次樹得到。互斥聚類：每個對象都指派到單個簇。重疊的或非互斥的聚類用來反映一個對象同時屬于多個組（類）這一事實。模糊聚類：每個對象以一個0（絕對不屬于）和1（絕對屬于）之間的錄屬權(quán)值屬于每個簇。完全聚類：將每一個（全部的對象）指派到一個簇，而部分聚類是有些對象沒有被聚類。

不同的簇類型：明顯分離的：不同組中的任意兩點之間的距離都大于組內(nèi)任意兩點之間的距離。明顯分離的簇不必是球形的，可以具有任意形狀。基于原型的：簇是對象的集合，其中每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近（或更加相似）。對于具有連續(xù)屬性的數(shù)據(jù)，簇的原型通常是質(zhì)心，即簇中所有點的平均值。這種簇傾向于呈球狀。基于原型的聚類技術(shù)創(chuàng)建數(shù)據(jù)對象的單層劃分。基于圖的：如果數(shù)據(jù)用圖表示，其中節(jié)點是對象，而邊代表對象之間的聯(lián)系，則簇可以定義為連通分支，即互相連通但不與組外對象連通的對象組。當(dāng)簇不規(guī)則或纏繞時，簇的這種定義是有用的。但是，當(dāng)數(shù)據(jù)具有噪聲時就可能出現(xiàn)問題。也存在其他類型的基于圖的簇。一種方法是定義簇為團(tuán)，即圖中相互之間完全連接的節(jié)點的集合。基于密度的：簇是對象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞。當(dāng)簇不規(guī)則或互相盤繞，并且有噪聲和離群點時，常常使用基于密度的簇定義。共同性質(zhì)的（概念簇）：把簇定義為有某種共同性質(zhì)的對象的集合。發(fā)現(xiàn)這樣的簇的過程稱作概念聚類。

4.2 K均值

K均值是基于原型的、劃分的聚類技術(shù)。它試圖發(fā)現(xiàn)用戶指定個數(shù)（K）的簇（由質(zhì)心代表）。

K均值聚類用于n維連續(xù)空間中的對象。K中心點使用中心點定義原型，其中中心點是一組點中最有代表性的點。K中心點聚類可以用于廣泛的數(shù)據(jù)，因為它只需要對象之間的鄰近性度量。盡管質(zhì)心幾乎從來不對應(yīng)實際的數(shù)據(jù)點，但是根據(jù)定義，中心點必須是一個實際的數(shù)據(jù)點。K均值的算法步驟：首先選擇K個初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個數(shù)。每個點指派到最近的質(zhì)心，而指派到一個質(zhì)心的點集為一個簇。然后，根據(jù)指派到簇的點，更新每個簇的質(zhì)心。重復(fù)指派和更新步驟，直到簇不發(fā)生變化，或等價的，直到質(zhì)心不發(fā)生變化。算法流程如下：

為了將點指派到最近的質(zhì)心，我們需要鄰近性度量來量化所考慮的數(shù)據(jù)的“最近”概念，通常，對歐式空間中的點使用歐幾里得距離，對文檔用余弦相似性。第四步“重新計算每個簇的質(zhì)心”，因為質(zhì)心可能隨數(shù)據(jù)鄰近性度量和聚類目標(biāo)不同而改變。聚類的目標(biāo)通常用一個目標(biāo)函數(shù)表示，該函數(shù)依賴于點之間，或點到簇的質(zhì)心的鄰近性；如：最小化每個點到最近質(zhì)心的距離的平方。然而，關(guān)鍵點是：一旦我們選定了鄰近性度量和目標(biāo)函數(shù)，則應(yīng)當(dāng)選擇的質(zhì)心可以從數(shù)學(xué)上確定。考慮鄰近性度量為歐幾里得距離的數(shù)據(jù)。我們使用誤差的平方和（SSE也稱散布）作為度量聚類質(zhì)量的目標(biāo)函數(shù)。換言之，我們計算每個數(shù)據(jù)點的誤差，即它到最近質(zhì)心的歐幾里得距離，然后計算誤差的平方和。給定由兩次運行K均值產(chǎn)生的兩個不同的簇集，我們更喜歡誤差平方和最小的那個，因為這意味聚類的原型（質(zhì)心）是簇中點的更好代表。假設(shè)數(shù)據(jù)是文檔數(shù)據(jù)，相似度用余弦來度量。我們的目標(biāo)是最大化簇中文檔與簇的質(zhì)心的相似性；該度量稱作凝聚度。對于該目標(biāo)，可以證明，與歐幾里得數(shù)據(jù)一樣，簇的質(zhì)心是均值。曼哈頓距離的質(zhì)心是中位數(shù)。Bregman散度也是一種鄰近性度量，該散度函數(shù)的重要性為質(zhì)心的K均值類型的聚類算法的基礎(chǔ)。用該散度作為鄰近性度函數(shù)，則聚類算法的收斂性、局部最小等性質(zhì)與通常的K均值相同。

當(dāng)質(zhì)心隨機(jī)初始化，K均值的不同運行將產(chǎn)生不同的總SSE。選擇適當(dāng)?shù)某跏假|(zhì)心是基本K 均值過程的關(guān)鍵步驟。一種常見的方法是隨機(jī)地選取初始質(zhì)心，但是簇的質(zhì)量常常會很差的。處理選取初始質(zhì)心問題的一種常見技術(shù)是：多次運行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE的簇集。該策略雖然簡單，但是效果可能不好，這依賴于數(shù)據(jù)集合尋找的簇的個數(shù)。另外還有的技術(shù)包括：取一個樣本，并使用層次聚類技術(shù)對它聚類。從層次聚類中提取K個簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法只在下列條件下有效（1）樣本相對較小（層次聚類開銷較大）；（2）K相對于樣本大小較小。還有一種選擇初始質(zhì)心的方法：隨機(jī)地選擇第一個點，或取所有點的質(zhì)心作為第一個點。然后，對于每個后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心較遠(yuǎn)的點。通常該方法用于點樣本。由于離群點很少，他們多半不會在隨機(jī)樣本中出現(xiàn)。

前面介紹的基本K均值存在一個問題：如果所有的點在指派步驟都未分配到某個簇，就會得到空簇。如果這種情況發(fā)生，則需要某種策略來選擇一個替補質(zhì)心，否則的話，平方誤差將會偏大。一種方法是選擇一個距離當(dāng)前任何質(zhì)心最遠(yuǎn)的點。另一種方法是從具有最大SSE的簇中選擇一個替補質(zhì)心。我們還可能刪除那些很小的簇，因為它們常常代表離群點的組。一種降低SSE的明顯方法是找出更多簇，即使用很大的K。然而，在許多情況下，我們希望降低ＳＳＥ，但并不想增加簇的個數(shù)。因為Ｋ均值常常收斂于局部最小。一種常用的方法是交替地使用簇分裂和簇合并。

增量的更新質(zhì)心：可以在點到簇的每次指派之后，增量地更新質(zhì)心，而不是在所有的點都指派到簇中之后才更新簇的質(zhì)心，每次需要零次或兩次質(zhì)心更新。使用增量更新策略確保不會產(chǎn)生空簇。因為所有的簇都從單個點開始；并且一個簇只有單個點，則該點總是被指派到相同的簇。增量更新還有兩個優(yōu)點：（１）可以調(diào)整點的相對權(quán)值。（２）使用不同于“最小化ＳＳＥ”的目標(biāo)。缺點：增量的更新質(zhì)心可能導(dǎo)致次序的依賴性，即：所產(chǎn)生的簇可能依賴于點的處理次序。Ｋ均值收斂相當(dāng)快。

二分Ｋ均值：為了得到Ｋ個簇，將所有點的集合分裂成兩個簇，從這些簇中選取一個繼續(xù)分裂，如此下去，直到產(chǎn)生Ｋ個簇。待分裂的簇有許多不同的選擇方法。可以選擇最大的簇，選擇具有最大SSE的簇，或者使用一個基于大小和SSE的標(biāo)準(zhǔn)進(jìn)行選擇。二分K均值算法最終的簇集并不代表使SSE局部最小的聚類。二分K均值不太受初始化的困擾，因為它執(zhí)行了多次二分試驗并選取具有最小SSE的試驗結(jié)果，還因為每步只有兩個質(zhì)心。通過記錄K均值二分簇所產(chǎn)生的聚類序列，我們還可以使用二分K均值產(chǎn)生層次聚類。當(dāng)簇具有非球形形狀或具有不同尺寸或密度時，K均值很難檢測到“自然的”簇。K均值的目標(biāo)函數(shù)是最優(yōu)化等尺寸和等密度的球形簇，或者明顯分離的簇。所以K均值只適合與上面的三種情況的聚類。

優(yōu)缺點：K均值簡單并且可以用于各種數(shù)據(jù)類型。它也相當(dāng)有效，盡管常常多次運行。然而，K均值并不適合所有的數(shù)據(jù)類型。它不能處理非球形簇、不同尺寸和不同密度的簇，盡管指定足夠大的簇個數(shù)時它通常可以發(fā)現(xiàn)純子簇。對包含離群點的數(shù)據(jù)進(jìn)行聚類時，K均值也有問題。K均值僅限于具有中心（質(zhì)心）概念的數(shù)據(jù)。K中心點沒有這種限制，但是開銷更大。

最后，給定一個諸如“最小化SSE”這樣的目標(biāo)函數(shù)，可以把聚類視為優(yōu)化問題。

4.3?凝聚的層次聚類

它通過如下的步驟產(chǎn)生層次聚類：開始，每個點作為一個單元簇，然后，重復(fù)地合并兩個最靠近的簇，直到產(chǎn)生單個的、包含所有點的簇。有兩種產(chǎn)生層次聚類的基本方法：

（1）凝聚的：從點作為個體簇開始，每一合并兩個最接近的簇。這需要定義簇的鄰接性的概念。（2）分裂的：從包含所有點的一個簇開始，每一步分裂一個簇，直到僅剩下單點簇。這種情況下，我們需要確定每一步分裂哪個簇，以及如何分裂。

其中凝聚層次聚類技術(shù)是常見的。層次聚類常常使用一種稱作樹狀圖的類似于樹的圖顯示。對于二維點的集合，層次聚類也可以使用嵌套圖表示。層次聚類的關(guān)鍵操作是計算兩個簇之間的鄰近度，并且正是簇的鄰近性定義區(qū)分了我們將討論的各種凝聚層次技術(shù)。簇的鄰近性通常用特定的簇類型定義。通常的方法有MIN、MAX和組平均，都源于簇的基于圖的觀點。MIN（也叫做單鏈）定義簇的鄰近度為不同簇的兩個最近的點之間的鄰近度，使用圖的術(shù)語即：不同結(jié)點子集中兩個結(jié)點之間的最短邊。單鏈技術(shù)擅長于處理非橢圓形狀的簇，但對噪聲和離群點很敏感。MAX（也叫全鏈）取不同簇中兩個最遠(yuǎn)的點之間的鄰近度作為簇的鄰近度，使用圖的術(shù)語即：不同結(jié)點子集中兩個結(jié)點之間的最長邊。完全連接對噪聲和離群點不太敏感，但是它可能使大的簇破裂，并且偏好于球形。組平均：定義簇鄰近度為取自不同簇的所有點的平均逐對鄰近度。如果我們?nèi)』谠偷挠^點，簇用質(zhì)心代表，則不同的簇鄰近度定義就更加自然。使用質(zhì)心時，簇的鄰近度一般定義為簇質(zhì)心之間的鄰近度，另一種技術(shù)，Ward方法，也假定簇用其質(zhì)心代表，但它使用合并兩個簇導(dǎo)致的SSE增加來度量兩個簇之間的鄰近性，像K均值一樣，Ward方法也試圖最小化點到其簇質(zhì)心的距離的平方和。當(dāng)兩個點之間的鄰近度取它們之間距離的平方時，Ward方法與組平均非常相似。

質(zhì)心方法：通過計算簇質(zhì)心之間的距離來計算兩個簇之間的鄰近度。質(zhì)心方法具有一種其他層次聚類不具備的特性（常被認(rèn)為是壞的）：倒置的可能性。即合并的兩個簇可能比前一步合并的蔟對更相似。對于其他方法，被合并的簇之間的距離隨層次聚類進(jìn)展單調(diào)地增加。

上面的所有方法都可以合并到一個叫Lance-Williams公式中去。任何使用該公式表示的層次聚類技術(shù)都不需要保留原來的數(shù)據(jù)點。替換地，鄰近度矩陣隨聚類而更新。

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

優(yōu)點和缺點：使用這類聚類算法是因為基本應(yīng)用（如創(chuàng)建一種分類法）需要層次結(jié)構(gòu)。凝聚層次聚類算法是昂貴的，所有合并是最終的，對于噪聲、高維數(shù)據(jù)（如文檔數(shù)據(jù)），這也可能造成問題。先使用其他技術(shù)（如K均值）進(jìn)行部分聚類，這兩個問題都可以在某種程度上加以解決。

層次聚類的空間復(fù)雜度O(m²)。總時間復(fù)雜度O(m²logm)。

4.4 DBSCAN

這是一種產(chǎn)生劃分聚類的基于密度的聚類算法，簇的個數(shù)由算法自動的確定。低密度區(qū)域中的點被視為噪聲而忽略，因而DBSCAN不產(chǎn)生完全聚類。

基于密度的聚類尋找被低密度區(qū)域分離的高密度區(qū)域。定義密度的方法有很多，在DBSCAN中使用的是基于中心的方法，在該方法中，數(shù)據(jù)集中特定點的密度通過對該點的Eps半徑之內(nèi)的點計數(shù)（包括點本身）來估計。核心點：這些點在基于密度的簇內(nèi)部。一個點是核心點，如果該點的給定鄰域內(nèi)的點的個數(shù)超過給定的閾值MinPts，其中MinPts也是一個用戶指定的參數(shù)。邊界點：邊界點不是核心點，但他落在某個核心點的鄰域內(nèi)。噪聲點：噪聲點是既非核心點也非邊界點的任何點。DBSCAN算法可以非形式化的描述如下：任何兩個足夠靠近（相互之間的距離在Eps之內(nèi)）的核心點將放在同一簇中。類似的，任何與核心點足夠靠近的邊界點也放到核心點相同的簇中。（如果一個邊界點靠近不同簇的核心點，則可能需要解決平局問題）。噪聲點被丟棄。

（1）該算法的時間復(fù)雜度是O(m²)，然而，在低維空間，有一些數(shù)據(jù)結(jié)構(gòu)，如kd樹，使得可以有效的檢索特定點給定距離內(nèi)的所有點，時間復(fù)雜度可以降低到O(mlogm)。（2）選擇DBSCAN的參數(shù)（Eps和MinPts）。基本方法是觀察點到它的k個最近鄰的距離（稱為k-距離）的特性。對于屬于某個簇的點，如果k不大于簇的大小的話，則k-距離將很小。然而，對于不在簇中的點（如噪聲點），k-距離將相對較大。因此，如果我們對某個k，計算所有點的k-距離，以遞增的次序?qū)⑺麄兣判?#xff0c;然后繪制排序后的值，則我們預(yù)期會看到k-距離的急劇變化，對應(yīng)于合適的Eps值。（3）變密度的簇：如果簇的密度變化很大，DBSCAN可能會有問題。（4）DBSCAN優(yōu)缺點。因為該方法使用簇的基于密度的定義，因此它是相對抗噪聲的，并且能夠處理任意形狀和大小的簇。它可以發(fā)現(xiàn)使用K均值不能發(fā)現(xiàn)的許多簇。缺點：不適合密度變化太大。對于高維數(shù)據(jù)，該方法也有問題，因為密度定義困難。最后，當(dāng)鄰近計算需要計算所有的點對鄰近度時（對于高維數(shù)據(jù)，常常如此），DBSCAN可能是開銷很大的。

4.5?簇評估

由于簇的特性，簇評估技術(shù)未能很好開發(fā)，或者說不是聚類分析普遍使用的。盡管如此，簇評估，或者簇確認(rèn)是重要的。由于存在大量不同的簇類型（在某種意義下，每種聚類算法都定義了子集的簇類型），似乎每種情況都可能需要一種不同的評估度量。例如，K均值簇可能需要用SSE來評估，但是基于密度的簇不必是球形的，SSE全然不起作用。盡管如此，簇評估應(yīng)該是聚類分析中的一部分。一個主要動機(jī)是，幾乎每種聚類算法都會在數(shù)據(jù)集中發(fā)現(xiàn)簇，即便該數(shù)據(jù)集根本沒有自然的簇結(jié)構(gòu)。簇確認(rèn)的一些任務(wù)：(1)確定數(shù)據(jù)集的聚類趨勢，即識別數(shù)據(jù)中是否實際存在非隨機(jī)結(jié)構(gòu)。（2）確定正確的簇個數(shù)；（3）不引用附加的信息，評估聚類分析結(jié)果對數(shù)據(jù)擬合情況；（4）將聚類分析結(jié)果與已知的客觀結(jié)果（如，外部提供的類標(biāo)號）比較。（5）比較兩個簇集，確定哪個更好。

注意：第1、2、3項不適用任何外部信息（他們是非監(jiān)督技術(shù)），而第4項使用外部信息。第5項可以用監(jiān)督或非監(jiān)督的方式執(zhí)行。評估的挑戰(zhàn)：（1）簇的有效性度量可能受限于它的可用范圍;例如：聚類趨勢度量方面的大部分工作都是針對二、三維空間數(shù)據(jù)（2）我們需要一個框架來解釋任意度量。匹配的優(yōu)良度可以通過考察該值的統(tǒng)計分布來度量，即這樣的值偶然出現(xiàn)的幾率多大。（3）如果度量太復(fù)雜，難以使用或難以理解，則很少有人愿意使用它。傳統(tǒng)的，用于評估簇的各方面的評估度量或指標(biāo)分成如下三類：（1）非監(jiān)督的：聚類結(jié)構(gòu)的優(yōu)良性度量，不考慮外部信息。如SSE。簇的有效性的非監(jiān)督度量常常可以進(jìn)一步分為兩類：（A）簇的凝聚性（緊湊性、緊致性）度量確定簇中對象如果密切相關(guān)。（B）簇的分離性（孤立性）：度量確定一個簇如何不同于其他簇。非監(jiān)督度量通常稱為內(nèi)部指標(biāo)，因為它們僅使用出現(xiàn)在數(shù)據(jù)集中的信息。（2）監(jiān)督的：度量聚類算法發(fā)現(xiàn)的聚類結(jié)構(gòu)與某種外部結(jié)構(gòu)的匹配程度。如熵，它度量簇標(biāo)號與外部提供的標(biāo)號的匹配程度。監(jiān)督度量通常稱為外部指標(biāo)，因為他們使用了不在數(shù)據(jù)集中出現(xiàn)的信息。（3）相對的：比較不同的聚類和簇。

4.5.1?非監(jiān)督簇評估：使用凝聚度和分離度

如果有效性函數(shù)是凝聚度，則值越高越好。如果是分離度，則越低越好。對于基于圖的簇，簇的凝聚度可以定義為連接簇內(nèi)點的鄰近度圖中邊的加權(quán)和；兩個簇之間的分離度可以用從一個簇的點到另一個簇的點的邊的加權(quán)和來度量。對于基于原型的簇，簇的凝聚度可以定義為關(guān)于簇原型（質(zhì)心或中心點）的鄰近度的和；兩個簇之間的分離度可以用兩個簇原型的鄰近度度量。簇原型與總原型的分離度有時與簇原型之間的分離度直接相關(guān)。對于簇的凝聚度和分離度，通過使用加權(quán)和可以將它們組合成簇的有效性的總度量。盡管度量簇的凝聚性和分離性的基于圖的方法與基于原型的方法看上去截然不同，但是對于某些鄰近性度量它們是等價的。當(dāng)鄰近度用歐幾里得距離度量時，簇之間分離性的傳統(tǒng)度量是組平方和（SSB），總SSB越高，簇之間的分離性越好。我們也可以使用對象對簇的總凝聚度或分離度的貢獻(xiàn)，來評估簇中的對象。對凝聚度和分離度貢獻(xiàn)越大的對象就越靠近簇的“內(nèi)部”，反之，對象可能離簇的“邊緣”很近。

輪廓系數(shù)：結(jié)合了凝聚度和分離度。下面是如何計算個體點的輪廓系數(shù)（我們使用距離，但是類似的方法可以使用相似度）：（1）對于第i個對象，計算它到簇中所有其他對象的平均距離。該值記為。（2）對于第i個對象和不包含該對象的任意簇，計算該對象到給定簇中所有對象的平均距離，關(guān)于所有的簇，找出最小值；該值記為b_i。（3）對于第i個對象，

因為負(fù)值表示點到簇內(nèi)點的平均距離 大于點到其他簇的最小平均距離b_i。我們希望輪廓系數(shù)是正的（ <b_i），并且 越靠近0越好，因為當(dāng) =0時輪廓系數(shù)取其最大值1.我們可以簡單地取簇中點的輪廓系數(shù)的平均值，計算簇的平均輪廓系數(shù)。通過計算所有點的平均輪廓系數(shù)，可以得到聚類優(yōu)良性的總度量。

4.5.2?非監(jiān)督簇評估：使用鄰近度矩陣

有兩種：（1）比較實際的鄰近度矩陣和理想的鄰近度矩陣；（2）使用可視化技術(shù)。理想的簇是這樣的簇，它的點與簇內(nèi)所有點的相似度為1，而與其他簇的所有點的相似度為0,。這樣，如果將相似度矩陣的行和列排序，使得屬于相同的簇的對象在一起，則理想的相似度矩陣具有塊對角結(jié)構(gòu)。鄰近度矩陣對于許多基于密度和基于近鄰的簇，這不是好的度量，因為它們不是球形的，并且常常與其他簇緊密地盤繞在一起。從理論上講，如果有明顯分離的簇，則相似度矩陣粗略地是塊對角的。如果不是，則鄰近度矩陣所顯示的模式可能揭示簇之間的聯(lián)系。所有這些也可以用于相異度矩陣。

4.5.3?層次聚類的非監(jiān)督簇評估

基于層次聚類的流行的評估度量——共性分類相關(guān)。兩個對象之間的共性分類距離是凝聚層次聚類技術(shù)首次將對象放在同一簇時的鄰近度。例如：如果兩個合并簇之間的最小距離是0.1，則一個簇中的所有點關(guān)于另一個簇中的各點的共性分類距離都是0.1。在共性分類距離矩陣中，項是每對對象之間的共性分類距離。點集的每個層次聚類的共性分類距離不同。共性相關(guān)系數(shù)是該矩陣與原來的相異度矩陣的項之間的相關(guān)度，是（特定類型的）層次聚類對數(shù)據(jù)擬合程度的標(biāo)準(zhǔn)度量。該度量的最常見應(yīng)用時評估對于特定的數(shù)據(jù)類型，哪種類型的層次聚類最好。

確定正確的簇個數(shù):多種非監(jiān)督評估度量都可以用來近似地確定正確的或自然的簇個數(shù)。我們可以通過尋找簇個數(shù)的評估度量曲線圖中的拐點、尖峰或下降點，試圖發(fā)現(xiàn)簇的自然個數(shù)。

聚類趨勢。確定數(shù)據(jù)集中是否包含簇的一種明顯的方法是試著對他聚類。我們可以評估結(jié)果簇，至少有些簇具有好的質(zhì)量，才能說數(shù)據(jù)集中包含簇。然而，事實是數(shù)據(jù)集中可能存在不同于我們的聚類算法所能發(fā)現(xiàn)的簇類型。聚類趨勢度量：試圖估計數(shù)據(jù)集中是否包含簇，而不進(jìn)行聚類。最常用的方法（特別對于歐幾里得空間數(shù)據(jù)）是使用統(tǒng)計檢驗來檢驗空間的隨機(jī)性。如Hopkins（霍普金斯）統(tǒng)計量。

4.5.4?簇有效性的監(jiān)督度量

考慮劃分聚類的兩類不同的方法：（1）使用分類的度量，如熵、純度、精度、召回率和F度量。這些度量評估簇包含單個類的對象的程度。（2）涉及二元數(shù)據(jù)的相似性度量。如：Jaccard系數(shù)。這些方法度量在多大程度上，同一類的兩個對象在同一個簇中，或相反。

層次聚類的監(jiān)督評估更加困難，這里，我們給出一個根據(jù)類標(biāo)號集評估層次聚類方法的例子。類標(biāo)號集可能比先前存在的簇結(jié)構(gòu)更容易得到。該方法的關(guān)鍵思想是：評估層次聚類是否對于每個類，至少有一個簇相對較純，并且包含了該類的大部分對象。為了根據(jù)此目標(biāo)評估層次聚類，我們對每個類，計算簇層次結(jié)構(gòu)中每個簇的F度量，對于每個類，取最大的F度量。最后，通過計算每類的F度量的加權(quán)平均，計算層析聚類的總F度量，其中，權(quán)值基于類的大小。

4.5.5?評估簇有效性度量的顯著性

一種常用的方法是同統(tǒng)計學(xué)術(shù)語解釋有效性度量值。具體的說，我們試圖確定觀測值隨機(jī)得到的可能性有多大。值是好的，如果它是不尋常的。即它不像是隨機(jī)結(jié)果。這種顯著性有兩個方面：差別是否是統(tǒng)計顯著的（可重復(fù)的），差別的量級對于應(yīng)用是否具有意義。

4.6?聚類分析：附加的問題和算法

沒有一種算法能夠適應(yīng)所有的數(shù)據(jù)類型、簇和應(yīng)用。在許多情況下，對于什么是一個好的簇集，仍然憑主觀解釋。

K均值聚類可以看作一種統(tǒng)計聚類（混合模型）的特例，所以它假定所有的數(shù)據(jù)都來自球形高斯分布，具有不同的均值，但是具有相同的協(xié)方差矩陣。DBSCAN不基于任何形式化模型，所以它不對數(shù)據(jù)的分布做任何假定。K均值和DBSCAN，當(dāng)簇具有很不相同的密度時，兩種算法的性能都很差。K均值可以用于稀疏的高維數(shù)據(jù)，如文檔數(shù)據(jù)。DBSCAN通常在這類數(shù)據(jù)上性能很差，因為多域高維數(shù)據(jù)，傳統(tǒng)的歐幾里得密度定義不能很好的處理。K均值可以發(fā)現(xiàn)不是明顯分離的簇，即便簇有重疊也可以發(fā)現(xiàn)，但是DBSCAN會合并有重疊的簇。K均值算法的時間復(fù)雜度是O（m）而DBSCAN是O(m²)，除非用于諸如低維歐幾里得數(shù)據(jù)這樣的特殊情況。DBSCAN多次運行產(chǎn)生相同的結(jié)果，而K均值通常使用隨機(jī)初始化質(zhì)心。不會產(chǎn)生相同的結(jié)果。注意：噪聲可能導(dǎo)致單鏈等技術(shù)合并兩個不應(yīng)當(dāng)合并的簇。Chameleon、基于SNN密度的聚類和CURE在聚類的過程中顯式的處理噪聲和離群點。

簇特性：（1）某些聚類算法假定數(shù)據(jù)具有特定的分布。更具體的說，他們常常假定可以用混合分布對數(shù)據(jù)建模，其中每個簇對應(yīng)于一個分布。（2）形狀：DBSCAN和單鏈技術(shù)可以處理任意形狀的簇，但是基于原型的方法和諸如全鏈和組平均這樣的層次聚類技術(shù)不能進(jìn)行這樣的處理。Chameleon和CURE是專門用來處理這一問題的技術(shù)的例子。（3）不同的密度：具有很不相同的密度的簇可能對DBSCAN和K均值算法造成問題，SNN密度聚類技術(shù)就是處理這一問題的。（4）無明顯分離的簇。模糊聚類是一種旨在處理未形成明顯分離的簇的數(shù)據(jù)的技術(shù)。（3）簇之間的聯(lián)系。在大部分聚類技術(shù)中，都不明顯地考慮簇之間的聯(lián)系，如簇的相對位置。自組織映射（SOM）是一種在聚類期間直接考慮簇之間聯(lián)系的聚類技術(shù)。具體的，點到簇的指派影響鄰近簇的定義。（4）子空間簇。簇可能只在維（屬性）的一個子集中存在，并且使用一個維集合確定的簇可能與使用另一個維集合確定的簇很不相同。簡單地在所有可能的維子集中尋找簇是不可行的。

聚類算法的一般特性：（1）次序依賴性。對于某些算法，所產(chǎn)生的簇的質(zhì)量和個數(shù)可能因數(shù)據(jù)處理的次序不同而顯著地變化。SOM是次序依賴算法的一個例子。（2）非確定性。每次運行都產(chǎn)生不同的結(jié)果，因為它們依賴于需要隨機(jī)選擇的初始化步驟。（3）可伸縮性。包含數(shù)以百萬計對象的數(shù)據(jù)集并不罕見，而用于這種數(shù)據(jù)集的聚類算法應(yīng)當(dāng)具有線性或接近線性的時間和空間復(fù)雜度。（4）參數(shù)選擇。通常的態(tài)度是參數(shù)越少越好。

4.6.1?基于原型的聚類

本節(jié)討論的聚類方法以一種或多種方式擴(kuò)展基于原型的概念，如下所述：

（1）???????允許對象屬于多個簇，更具體的說，對象以某個權(quán)值屬于每一個簇，這樣的方法針對這樣的事實，某些對象與多個簇原型一樣近。（有模糊聚類）

（2）???????用統(tǒng)計分布對簇進(jìn)行建模，即對象通過一個隨機(jī)過程，有一個被若干統(tǒng)計參數(shù)（如均值和方差）刻畫的統(tǒng)計分布產(chǎn)生。（有混合模型聚類）

（3）???????簇被約束為具有固定的聯(lián)系。就常見地，這些聯(lián)系是指定近鄰關(guān)系的約束，即兩個簇互為鄰居的程度。約束簇之間的聯(lián)系可以簡化對數(shù)據(jù)的解釋和可視化。

模糊c均值(也叫FCM)使用模糊邏輯和模糊集合論的概念，提出一種聚類方案，它很像K均值，但是不需要硬性的將某個對象只指派到一個簇中。混合模型聚類采用這樣的聚類方法，簇集合可以使用一個混合分布建模，每一個分布對應(yīng)一個簇。基于自組織映射（SOM）的聚類方法在一個框架（例如二維網(wǎng)格結(jié)構(gòu)）內(nèi)進(jìn)行聚類，該框架要求簇具有預(yù)先指定的相互聯(lián)系。

(1)?模糊c均值

模糊集合論和模糊邏輯作為一種處理不精確和不確定的方法。簡要的說，模糊集合論允許對象以0和1之間的某個錄屬度屬于一個集合，而模糊邏輯允許一個陳述以0和1之間的確定度為真。存在多種模糊聚類（事實上，許多數(shù)據(jù)分析算法都可以“模糊化”），我們只考慮K均值的模糊版本，稱作模糊c均值（FCM）。前提：對每個對象和每個簇賦予一個權(quán)值，指明該對象屬于該簇的程度。從數(shù)學(xué)上講，w_ij是對象X_i屬于簇C_j的權(quán)值。算法步驟：(1)選擇一個初始模糊偽劃分，即對所有的w_ij賦值；（2）使用模糊偽劃分，計算每個簇的質(zhì)心（即依據(jù)質(zhì)心（保證了變化性）更新模糊偽劃分）；（3）重新計算模糊偽劃分，即w_ij；（4）重復(fù)（2）（3）直到質(zhì)心不發(fā)生變化（替換的終止條件是“如果誤差的變化低于指定的閾值”或“如果所有w_ij的變化的絕對值都低于指定的閾值”）。算法中，重新計算模糊偽劃分等價于指派步驟。

將以下合理的條件施加在簇上，以確保簇形成模糊偽劃分：

與K均值一樣，FCM可以解釋為試圖最小化誤差的平方和，盡管FCM基于SSE的模糊版本，事實上，K均值可以看作FCM的特例。

初始化：通常使用隨機(jī)初始化。特殊地，權(quán)值隨機(jī)地選取，同時限定與任何對象相關(guān)聯(lián)的權(quán)值之和必須等于1（但是，隨機(jī)選取也和K均值一樣，有他的有點和缺點）。

優(yōu)缺點：優(yōu)點：它產(chǎn)生指示任意點屬于任意簇的程度的聚類。除此之外，它具有與K均值相同的優(yōu)缺點，盡管它的計算密集程度更高一些。

(2)?使用混合模型的聚類

假定數(shù)據(jù)是由一個統(tǒng)計過程產(chǎn)生的，并且通過找出最佳擬合數(shù)據(jù)的統(tǒng)計模型來描述數(shù)據(jù)，其中統(tǒng)計模型中用分布和該分布的一組參數(shù)描述。在高層，該過程涉及確定數(shù)據(jù)的統(tǒng)計模型，并由數(shù)據(jù)估計該模型的參數(shù)。混合模型，它使用若干統(tǒng)計分布對數(shù)據(jù)建模，每一個分布對應(yīng)于一個簇，而每個分布的參數(shù)提供對應(yīng)簇的描述，通常用中心和發(fā)散描述。

混合模型將數(shù)據(jù)看作從不同的概率分布得到的觀測值的集合，概念上講，混合模型對應(yīng)于如下數(shù)據(jù)產(chǎn)生過程，給定幾個分布（通常類型相同但參數(shù)不同），隨機(jī)地選取一個分布并由產(chǎn)生一個對象。重復(fù)過程m次，其中m是對象的個數(shù)。對于混合模型，每個分布描述一個不同的組，即一個不同的簇。通過使用統(tǒng)計方法，我們可以由數(shù)據(jù)估計這些分布的參數(shù)，從而描述這些分布（簇）。我們也可以識別哪個對象屬于哪個簇。然而，混合模型并不產(chǎn)生對象的明確指派，而是給出具體對象屬于特定簇的概率。

EM算法的聚類：假設(shè)我們已經(jīng)知道整體數(shù)據(jù)集是由幾個相同類型的分布（只是參數(shù)不同）（每個分布對應(yīng)一個簇）組成的，我們將每個分布組合起來成一個混合的模型（比如簡單的，將每個分布（假設(shè)是高斯分布）的分布概率函數(shù)相加）。為了將數(shù)據(jù)分類就需要估計混合模型中的參數(shù)找到參數(shù)后可以知道每個分布，每一分布對應(yīng)一個簇，聚類就完成。而估計參數(shù)的方法流行的有兩種：（1）最大似然估（MLE）計：這個主要用在（A）整體數(shù)據(jù)集只有一個分布；（2）當(dāng)用最大似然估計來估計混合模型的參數(shù)時，我們知道哪個數(shù)據(jù)對象來自哪個分布，于是問題又歸結(jié)為給定符合某分部的數(shù)據(jù)，估計單個分布的參數(shù)。

然而實際情況是我們不知道哪個點由哪個分布產(chǎn)生。這樣我們就不能直接計算每一個點的概率，因此我們不能使用最大似然原理來估計參數(shù)。解決這個問題的方案是使用EM算法（期望最大化）。算法思想：先給定參數(shù)值的一個猜測，EM算法計算每個點屬于每個分布的概率，然后使用這些概率，計算參數(shù)的新的估計（這些參數(shù)是最大化該似然估計的參數(shù)）。該迭代繼續(xù)下去，直到參數(shù)的估計不再改變或改變很小。這樣，我們通過一個迭代搜索，仍然使用了最大似然估計。EM算法步驟：（1）選擇模型參數(shù)的初始集（與K均值一樣，可以隨機(jī)地做，也可以用各種方法。）（2）期望步??對于每個對象，計算每個對象屬于每個分布的概率。（3）最大化步???給定期望步得到的概率（保證了動態(tài)性），找出最大化該期望的新的參數(shù)估計。（5）重復(fù)（2）（3）步直到參數(shù)不再改變（替換地，如果參數(shù)的改變低于預(yù)先指定的閾值則停止）。事實上，歐幾里得數(shù)據(jù)的K均值算法是具有相同協(xié)方差矩陣，但具有不同均值的球形高斯分布的EM算法的特殊情況。期望步對應(yīng)于K均值將每個對象指派到一個簇的步驟，但將每個對象以某一概率指派到每個簇（分布）。最大化步對應(yīng)于計算簇的質(zhì)心，但是選取分布的所有參數(shù)以及權(quán)值參數(shù)來最大化似然。這一過程常常是直截了當(dāng)?shù)?#xff0c;因為參數(shù)一般使用由最大似然估計推導(dǎo)出來的公式進(jìn)行計算。每個點最后指派到它具有最大錄屬權(quán)值的簇中。

優(yōu)缺點：（1）EM算法可能很慢，對于具有大量分量的模型可能不切實際；當(dāng)簇只包含少量數(shù)據(jù)點，或者數(shù)據(jù)點近似線性時，他也不能很好處理。（2）在估計簇的個數(shù)，或更一般地，在選擇正確的模型形式方面也存在問題。這個問題通常使用貝葉斯方法處理。簡單的說，貝葉斯聚類方法基于由數(shù)據(jù)得到的估計，給出一個模型相對于另一個模型的概率。（3）混合模型在有噪聲和離群點時也可能有問題。優(yōu)點：（1）混合模型比K均值或模糊K均值更一般，因為它可以使用各種類型的分布。（2）混合模型可以發(fā)現(xiàn)不同大小或橢球形狀的簇。（3）基于模型的方法提供了一種消除與數(shù)據(jù)相關(guān)聯(lián)的復(fù)雜性的方法。（4）可以簡化數(shù)據(jù)。如果模型是數(shù)據(jù)的一個好的匹配，用數(shù)據(jù)擬合一個模型是一種簡化數(shù)據(jù)的好方法。（5）模型更容易刻畫所產(chǎn)生的簇，因為它們可以用少量的參數(shù)描述。（6）很多數(shù)據(jù)實際上是隨機(jī)處理的結(jié)果，因此應(yīng)當(dāng)滿足這些模型的統(tǒng)計假設(shè)。

(3)?自組織映射（SOM）

SOM是一種基于神經(jīng)網(wǎng)絡(luò)觀點的聚類和數(shù)據(jù)可視化技術(shù)。盡管SOM源于神經(jīng)網(wǎng)絡(luò)，但它更容易表示成一種基于原型的聚類的變形，與其他基于質(zhì)心的聚類一樣，SOM的目標(biāo)是發(fā)現(xiàn)質(zhì)心的集合（用SOM的術(shù)語，參考向量），并將數(shù)據(jù)集中的每個對象指派到提供該對象最佳近似的質(zhì)心。用神經(jīng)網(wǎng)絡(luò)的術(shù)語，每一質(zhì)心都與一個神經(jīng)元相關(guān)聯(lián)。與增量K均值一樣，每次處理一個數(shù)據(jù)對象并更新質(zhì)心。與K均值不同，SOM賦予質(zhì)心地形序，也更新附近的質(zhì)心。此外，SOM不記錄對象的當(dāng)前簇錄屬情況：并不像K均值，如果對象轉(zhuǎn)移簇，并不明確地更新簇質(zhì)心。當(dāng)然，舊的簇質(zhì)心可能是新的簇質(zhì)心的近鄰，這樣它可能因此而更新。繼續(xù)處理點，直到達(dá)到某個預(yù)先確定的界限，或者質(zhì)心變化不大為止。SOM最終的輸出是一個隱式定義的質(zhì)心的集合。每個簇由最靠近某個特定質(zhì)心的點組成。

SOM算法的顯著特征是它賦予質(zhì)心（神經(jīng)元）一種地形（空間）組織。SOM使用的質(zhì)心具有預(yù)先確定的地形序關(guān)系，這是不同于其他基于原型的聚類的根本差別。在訓(xùn)練的過程中，SOM使用每個數(shù)據(jù)點更新最近的質(zhì)心和在地形序下鄰近的質(zhì)心。以這種方式，對于任意給定的數(shù)據(jù)集，SOM產(chǎn)生一個有序的質(zhì)心集合。換言之，在SOM網(wǎng)格中互相靠近的質(zhì)心比遠(yuǎn)離的質(zhì)心更加密切相關(guān)。由于這種約束，可以認(rèn)為二維點SOM質(zhì)心在一個盡可能好地擬合n維數(shù)據(jù)的二維曲面上。SOM質(zhì)心也可以看做關(guān)于數(shù)據(jù)點的非線性回歸的結(jié)果。SOM算法步驟：（1）初始化質(zhì)心；（2）選擇下一個對象；（3）確定帶該對象最近的質(zhì)心；（4）更新該質(zhì)心和附近的質(zhì)心，即在一個鄰域內(nèi)的質(zhì)心；（5）重復(fù)（2）到（4）直到質(zhì)心改變不多或超過某個閾值；（6）指派每個對象到最近的質(zhì)心。

初始化：有多種方法：（1）對每個分量，從數(shù)據(jù)中觀測到的值域隨機(jī)地選擇質(zhì)心的分量值。盡管該方法可行，但不一定是最好的，特別是對于快速收斂；（2）從數(shù)據(jù)中隨機(jī)地選擇初始質(zhì)心。選擇對象：由于算法可能需要許多步才收斂，每個數(shù)據(jù)對象可能使用多次，特別是對象較少時。然而如果對象較多，則并非需要使用每個對象。

優(yōu)缺點：優(yōu)點：它將相鄰關(guān)系強加在簇質(zhì)心上，所以，互為鄰居的簇之間比非鄰居的簇之間更相關(guān)。這種聯(lián)系有利于聚類結(jié)果的解釋和可視化。缺點：（1）用戶必選選擇參數(shù)、鄰域函數(shù)、網(wǎng)格類型和質(zhì)心個數(shù)；（2）一個SOM簇通常并不對應(yīng)單個自然簇，可能有自然簇的合并和分裂。例如：像其他基于原型的聚類技術(shù)一樣，當(dāng)自然簇的大小、形狀和密度不同時，SOM傾向于分裂或合并它們。（3）SOM缺乏具體的目標(biāo)函數(shù)。SOM受限于質(zhì)心之間的地形約束(為了更好的近似數(shù)據(jù)的質(zhì)心的集合)；但是SOM的成功不能用一個函數(shù)來表達(dá)。這可能使得比較不同的SOM聚類的結(jié)果是困難的。（4）SOM不保證收斂，盡管實際中它通常收斂。

4.6.2?基于密度的聚類

（1）基于網(wǎng)格的聚類。基本思想：將數(shù)據(jù)空間劃分成網(wǎng)格單元（方法：將每個屬性的可能值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合。每個對象落入一個網(wǎng)格單元。網(wǎng)格單元對應(yīng)的屬性區(qū)間包含對象值）。然后由足夠稠密的網(wǎng)格單元形成簇。這樣的方法是有效地，至少對于低維數(shù)據(jù)如此。算法步驟：（1）定義一個網(wǎng)格單元集；（2）將對象指派到合適的單元，并計算每個單元的密度；（3）刪除密度低于指定的閾值的單元；（4）由鄰近的稠密單元形成簇。

定義網(wǎng)格單元：存在許多方法將每個屬性的可能值分割成許多相鄰的區(qū)間，如：等寬、等頻、聚類等。網(wǎng)格的定義對聚類結(jié)果有很大的影響。

網(wǎng)格單元的密度定義：一種自然的方法是：定義網(wǎng)格單元（或更一般形狀的區(qū)域）的密度為該區(qū)域中的點數(shù)除以區(qū)域的體積。一種常見的方法是使用具有相同體積的網(wǎng)格單元，使得每個單元的點數(shù)直接度量單元的密度。

由鄰接的稠密單元形成簇：問題是我們需要定義鄰接單元的含義以及需要有效的技術(shù)發(fā)現(xiàn)鄰接單元。

優(yōu)缺點：優(yōu)點:可能是非常有效的。給定每個屬性的劃分，單遍數(shù)據(jù)掃描就可以確定每個對象的網(wǎng)格單元和網(wǎng)格單元的計數(shù)。此外，盡管潛在的網(wǎng)格單元數(shù)量可能很高，但是只需要為非空單元創(chuàng)建網(wǎng)格。這樣，定義網(wǎng)格、將每個對象指派到一個單元并計算每個單元的密度的時間復(fù)雜度和空間復(fù)雜度為O(m)，其中，m是點的個數(shù)。如果鄰接的、已占據(jù)的單元可以有效的訪問（例如，通過使用搜索樹）則整個聚類過程將非常高效，例如具有O(mlogm)的時間復(fù)雜度。缺點：（1）像大多數(shù)基于密度的聚類算法一樣、基于網(wǎng)格的聚類非常依賴于密度閾值的選擇。（太高，簇可能或丟失；太低，本應(yīng)分開的簇可能被合并）；（2）如果存在不同密度的簇和噪聲，則也許不可能找到適合于數(shù)據(jù)空間所有部分的值；（3）隨著維度的增加，網(wǎng)格單元個數(shù)迅速增加（指數(shù)增長）。即對于高維數(shù)據(jù)，基于網(wǎng)格的聚類傾向于效果很差。

（2）子空間聚類。基本思想：在所有維的子空間中尋找簇（稠密區(qū)域），由于子空間太多，因此需要有效的技術(shù)。目標(biāo)是：發(fā)現(xiàn)簇和它們存在的維。CLIQUE是一種基于網(wǎng)格的聚類算法，它基于如下觀察提供了一種有效的子空間聚類方法：高維空間的稠密區(qū)域暗示低維空間稠密區(qū)域的存在性。CLIQUE依賴于以下性質(zhì)(該性質(zhì)基于以下事實：低維單元的密度大于等于高維（維可以理解成屬性的個數(shù)）單元的密度，即低維單元除了包含所有高維單元的點還包含其他的點。)：

基于密度的簇的單調(diào)性：如果一個點集在k維（屬性）上形成一個基于密度的簇，則相同的點集在這些維的所有可能子集上也是基于密度的簇的一部分。

算法步驟如下：（1）找出對應(yīng)于每個屬性的一維空間中所有稠密區(qū)域。這是稠密的一維單元

優(yōu)缺點：優(yōu)點：（1）提供了一種搜索子空間發(fā)現(xiàn)簇的有效技術(shù)（相似與Apriori）。（2）用一小組不等式概括構(gòu)成一個簇的單元列表的能力。缺點：它的缺點和其他基于網(wǎng)格的密度算法相同，其他缺點和Apriori相同，例如：（1）指數(shù)復(fù)雜度（2）正如頻繁項集可以共享項一樣，CLIQUE發(fā)現(xiàn)的簇也可以共享對象。允許簇重疊可能大幅度增加簇的個數(shù)，并使得解釋更加困難。

（3）DENCLUE。基本思想：使用核密度函數(shù)用個體數(shù)據(jù)對象影響之和對點集總密度建模，盡管DENCLUE本質(zhì)上不是基于網(wǎng)格的技術(shù)，但是它使用基于網(wǎng)格的方法提高性能。DENCLUE也是一種基于密度的方法。結(jié)果總密度函數(shù)具有局部尖峰（稱作局部吸引點），并且這些局部尖峰用來以自然的方式定義簇。集體的說，對于每個數(shù)據(jù)點，一個爬山過程找出與該點相關(guān)聯(lián)的最近的尖峰，并且與一個特定的尖峰相關(guān)聯(lián)的所有數(shù)據(jù)稱為一個簇。DENCLUE算法步驟：（1）對數(shù)據(jù)點占據(jù)的空間推導(dǎo)密度函數(shù)；（2）識別局部最大點（這是局部吸引點）；（3）通過沿密度增長最大的方向移動，將每個點關(guān)聯(lián)到一個密度吸引點；（4）定義與特定的密度吸引點相關(guān)聯(lián)的點構(gòu)成的簇；（5）丟棄密度吸引點的密度小于用戶指定閾值的簇；（6）合并通過密度大于或等于的點路徑連接的簇。

核密度估計：核密度估計的目標(biāo)是用函數(shù)描述數(shù)據(jù)的分布。對于核密度估計，每個點對總密度函數(shù)的貢獻(xiàn)用一個影響或核函數(shù)表示。總密度函數(shù)僅僅是與每個點相關(guān)聯(lián)的影響函數(shù)之和。核密度的計算可能相當(dāng)昂貴，為了降低時間復(fù)雜度，DENCLUE使用一種基于網(wǎng)格的實現(xiàn)來有效地定義近鄰，并借此限制定義點的密度所需要考慮的點的數(shù)量。首先，預(yù)處理步創(chuàng)建網(wǎng)格單元集。僅創(chuàng)建被占據(jù)的單元，并且這些單元及其相關(guān)信息可以通過搜索樹有效地訪問。然后計算點的密度，并找出其最近的密度吸引點。DENCLUE只考慮近鄰中的點，即相同單元或者與該點所在單元相連接的單元中的點。即犧牲精度加快時間。

優(yōu)缺點：（1）DENCLUE提供了比其他基于網(wǎng)格的聚類技術(shù)和DBSCAN更加靈和、更加精確的計算密度的方法（DBSCAN是DENCLUE的特例）；（2）DENCLUE擅長處理噪聲和離群點，并且可以發(fā)現(xiàn)不同形狀和不同大小的簇；缺點：（1）DENCLUE可能比其他基于密度的聚類技術(shù)的計算開銷更大；（2）網(wǎng)格的使用對于密度估計的精度可能產(chǎn)生負(fù)面的影響；并且這使得DENCLUE容易受基于網(wǎng)格的方法共同存在的問題的影響，例如：很難選擇合格的網(wǎng)格尺寸；（3）對于高維數(shù)據(jù)和包含密度很不相同的簇的數(shù)據(jù)，DENCLUE可能有問題。

4.6.3?基于圖的聚類

數(shù)據(jù)的基于圖的觀點：數(shù)據(jù)對象用節(jié)點表示，而兩個對象之間的鄰近度用對應(yīng)結(jié)點之間邊的權(quán)值表示，簇用圖的連通分支表示。本節(jié)介紹的基于圖的聚類利用了下面的一些重要的性質(zhì)：（1）稀疏化鄰近度圖，只保留對象與其最近鄰之間的連接。這種稀疏化對于處理噪聲和離群點時有用的。稀疏化使得我們可以利用稀疏圖開發(fā)有效的圖劃分算法；（2）基于共享的最近鄰個數(shù)，定義兩個對象之間的相似度性度量。該方法基于如下觀察：對象和它的最近鄰?fù)ǔ儆谕粋€類。該方法有助于克服高維和變密度的問題。（3）定義核心對象并構(gòu)建環(huán)繞它們的簇。與DBSCAN一樣，圍繞核心對象構(gòu)建簇導(dǎo)致一種聚類技術(shù)，可以發(fā)現(xiàn)不同形狀和大小的簇。（4）使用鄰近度圖中的信息，提供兩個簇是否應(yīng)當(dāng)合并的更復(fù)雜的評估。具體地，兩個簇合并，僅當(dāng)結(jié)果簇具有類似于原來的兩個簇的特性。（Chameleon算法的主要思想）。

（1）???????稀疏化。基于如下事實：對于大部分?jǐn)?shù)據(jù)集，對象只與少量對象高度相似，而與大部分其他對象的相似性很弱。這一性質(zhì)可以用來稀疏化鄰近度圖（矩陣）：在實際的聚類過程開始之前，將許多低相似性（高相異度）的值置0。例如，稀疏化可以這樣進(jìn)行，斷開相似度（相異度）低于（高于）指定閾值的邊，或僅保留連接到點的k個最近鄰的邊。后一種方法創(chuàng)建所謂k-最近鄰圖。鄰近圖的稀疏化使得使用圖劃分算法進(jìn)行聚類稱為可能。例如，Opossum和Chameleon都使用圖劃分。應(yīng)該把鄰近度圖的稀疏化看成使用實際聚類算法之前的初始化步驟。我們常常將稀疏鄰近度圖修改，產(chǎn)生新的鄰近度圖，新的鄰近度圖還可以被稀疏化。正如我們在算法Jarvis-Patrick和基于SNN密度的聚類時看到的。

（2）???????最小生成樹聚類（MST）。MST（一種分裂層次聚類技術(shù)）從鄰近度圖的最小生成樹開始，可以看作用稀疏化找出簇的應(yīng)用。MST也產(chǎn)生與單鏈凝聚聚類相同的聚類。最小生成樹可以看作一種特殊類型的稀疏化圖。算法步驟：（1）計算相異度圖的最小生成樹；（2）斷開對應(yīng)于最大相異度的邊，創(chuàng)建一個新的簇；（3）重復(fù)第（2）步直到只剩下單個簇。第二步也可以看作圖的稀疏化。因此，MST可以看作一種基于相異度圖稀疏化的聚類算法。問題：MST怎么是個層次聚類呢？

（3）???????Opossum:使用METIS的稀疏度相似度最優(yōu)劃分。Opossum是一種專門為諸如文檔或購物籃數(shù)據(jù)等稀疏、高維數(shù)據(jù)設(shè)計的聚類技術(shù)。與MST一樣，它基于鄰近度圖的稀疏化進(jìn)行聚類。然而，Opossum使用METIS算法，該算法是專門為劃分稀疏圖設(shè)計的。算法步驟如下：（1）計算稀疏化的相似度圖；（2）使用METIS，將相似度圖劃分成k個不同的分支（簇）。算法中k參數(shù)是用戶指定的參數(shù)，所使用的相似性度量是適合于稀疏、高維數(shù)據(jù)的度量，如擴(kuò)充的Jaccard度量或余弦度量。METIS圖劃分程序旨在（1）最小化分支之間邊的權(quán)值（相似度）；（2）實現(xiàn)平衡約束。Opossum使用如下兩種平衡約束中的一種：（1）每個簇中的對象個數(shù)必須粗略相等；或（2）屬性值的和必須粗略相等。優(yōu)缺點：優(yōu)點：（1）簡單、速度快；（2）將數(shù)據(jù)劃分大小粗略相等的簇。缺點：（1）由于簇被約束為大小粗略相等，因此簇可能被分裂或合并；（2）如果使用Opossum產(chǎn)生大量簇，則這些簇通常是更大簇的相對純的片段。事實上Opossum類似于Chameleon聚類過程的初始化步驟。

（4）???????Chameleon：使用動態(tài)建模的層次聚類。前面的凝聚層次聚類存在的問題：（1）簇的相似性定義依賴于具體的算法。如組平均，將其相似性概念建立在兩個簇之間的連接強度上（例如，兩個簇中點的逐對相似性）。而單鏈?zhǔn)褂么氐慕咏?#xff08;例如：不同簇中點的最小距離）來度量簇的相似性。盡管有兩種基本方法，但是僅使用其中一種方法可能導(dǎo)致錯誤的簇合并。（2）大部分聚類技術(shù)都有一個全局（靜態(tài)）簇模型。例如，K均值假定簇是球形的，而DBSCAN基于單個密度閾值定義簇。使用這樣一種全局模型的聚類方案不能處理諸如大小、形狀和密度等簇特性在簇間變化很大的情況。Chameleon是一種凝聚聚類技術(shù)，它解決前面提到的兩個問題。它將數(shù)據(jù)的初始劃分（使用一種有效的圖劃分算法）與一種新穎的層次聚類方案相結(jié)合。這種層次聚類使用接近性和互連性概念以及簇的局部建模。關(guān)鍵思想是：僅當(dāng)合并后的結(jié)果簇類似于原來的兩個簇時，這兩個簇才應(yīng)當(dāng)合并。因為這種方法依賴于蔟對而不是全局模型（所以稱作動態(tài)建模），Chameleon能夠處理包含具有各種不同特性的簇的數(shù)據(jù)。相對接近度（RC）：是被簇的內(nèi)部接近度規(guī)范化的兩個簇的絕對接近度。連個簇合并，僅當(dāng)結(jié)果簇中的點之間的接近程度幾乎與原來的每個簇一樣。相對互連度（RI）：是被簇的內(nèi)部互連度規(guī)范化的兩個簇的絕對互連度。如果結(jié)果簇中的點之間的連接幾乎與原來的每個簇一樣強，兩個簇合并。RI和RC可以用多種不同的方法組合，產(chǎn)生自相似性的總度量。Chameleon就是使用合并最大化自相似性的蔟對。算法步驟：（1）構(gòu)造k-最近鄰圖；（2）使用多層圖劃分算法劃分圖；（3）合并關(guān)于相對互連性和相對接近性而言，最好地保持簇的自相似性的簇；（4）重復(fù)（3）直到不再有可以合并的簇。在算法Chameleon中可以用參數(shù)指定，讓Chameleon一步合并多個簇對，并且在所有的對象都合并到單個簇之前停止。步驟的第二步——圖劃分：一旦得到稀疏化圖，就可以使用METIS等有效的多層圖劃分算法來劃分?jǐn)?shù)據(jù)集。Chameleon從一個全包含的圖（簇）開始。然后，二分當(dāng)前最大的子圖（簇），直到?jīng)]有一個簇多于MIN_SIZE個點，其中MIN_SIZE是用戶指定的參數(shù)。這一過程導(dǎo)致大量大小相等的、良連接的頂點（高度相似的數(shù)據(jù)點）的集合。目標(biāo)是確保每個劃分包含的對象都大部分來自一個真正的簇。算法時間復(fù)雜度（假設(shè)m是數(shù)據(jù)點數(shù)，p是劃分的個數(shù)）：在p個劃分進(jìn)行凝聚層次聚類需要O(p²logp)時間，劃分圖需要的時間總量是O(mp+mlogm)。建立k-鄰近圖如果使用k-d 樹或類似的數(shù)據(jù)結(jié)果，需要O(mlogm)時間。但是這種數(shù)據(jù)結(jié)構(gòu)只適用于低維數(shù)據(jù)，因此，對于高維數(shù)據(jù)，稀疏化的時間復(fù)雜度是O(m²)。空間復(fù)雜度：由于只需要存放k-最近鄰表，空間復(fù)雜度是O(km)加上存放數(shù)據(jù)所需要的空間。優(yōu)缺點：優(yōu)點：能夠很好的聚類空間數(shù)據(jù)，即便存在噪聲和離群點，并且簇具有不同的形狀、大小和密度。缺點：（1）算法假定有稀疏化和圖劃分過程產(chǎn)生的對象組群是子簇，即一個劃分中的大部分點屬于同一個真正的簇。如果不是，則凝聚層次聚類將混合這些錯誤，因為它絕對不可能再將已經(jīng)錯誤地放到一起的對象分開。這樣，當(dāng)劃分過程未產(chǎn)生子簇時，Chameleon就有問題，對于高維數(shù)據(jù)，常常出現(xiàn)這種情況。（2）Chameleon并不丟棄噪聲點，而是把它們指派到簇中。

共享最近鄰相似度。本節(jié)引入一種相似度的間接方法，它基于以下原理：如果兩個點與相同的點中的大部分都相似，則即使直接的相似性度量不能指出，它們也相似。一個對象的大多數(shù)最近鄰?fù)ǔＨ匀粚儆谕粋€類。相似性的SNN版本解決的兩個問題：低相似性和不同密度。SNN相似度計算。關(guān)鍵思想是：在定義相似性度量時考慮點的環(huán)境。點的環(huán)境可以用相似性的共享最近鄰（SNN）定義量化。本質(zhì)上講，只要兩個對象都在對方的最近鄰列表中，SNN相似度就是它們共享的近鄰個數(shù)。計算共享最近鄰相似度的算法步驟：（1）找出所有點的k-最近鄰；（2）if 兩個點x 和

（5）???????度圖稱作SNN相似度圖。由于許多對象之間的SNN相似度為0，所以相似度圖非常稀疏。SNN相似度可以處理如下情況：一個對象碰巧與另一個對象相對接近，但屬于不同的類。在這種情況下，對象一般不共享許多近鄰，并且它們的SNN相似度低。SNN相似度也能處理變密度的問題。由于SNN相似度只依賴于兩個對象共享的最近鄰的個數(shù)，而不是這些近鄰相距多遠(yuǎn)。所以，SNN相似度關(guān)于點的密度進(jìn)行自動縮放。

（6）???????Jarvis-Patrick聚類算法。JP聚類算法用SNN相似度取代兩個點之間的鄰近度。然后使用一個閾值來稀疏化SNN相似度矩陣。使用圖的術(shù)語就是，創(chuàng)建并稀疏化SNN相似度圖。簇是SNN圖的連通分支。JP聚類算法步驟：（1）計算SNN相似度圖；（2）使用相似度閾值，稀疏化相似度圖；（3）找出稀疏化的SNN相似度圖的連通分支（簇）。JP算法的存儲需求僅為O(km)，因為即便在初始階段也不需要存放整個相似度矩陣。JP聚類的基本時間復(fù)雜度是O(m²)。因為k-最近鄰列表的創(chuàng)建可能需要計算O(m²)個鄰近度。然而，如果對低維歐幾里得數(shù)據(jù)，可以使用像k-d樹來有效地找出k-最近鄰，而不必計算整個相似度矩陣。時間復(fù)雜度就為O(mlogm,)。優(yōu)缺點：優(yōu)點：（1）刪除處理噪聲和離群點，并且能夠處理不同大小、形狀和密度的簇；（2）該算法對高維數(shù)據(jù)效果良好，尤其擅長發(fā)現(xiàn)強相關(guān)對象的緊致簇。缺點：（1）算法優(yōu)點脆弱，即它可能分裂真正的簇，或者合并本應(yīng)該分開的簇；（2）并非所有的對象都被聚類（剩下的對象可以添加到已有的簇中）；（3）與其他聚類算法一樣，選擇好的參數(shù)值可能是一個挑戰(zhàn)。

（7）???????SNN密度。解決的問題：傳統(tǒng)的歐幾里得密度在高維空間變得沒有意義。由于SNN相似性度量反映了數(shù)據(jù)空間中點的局部結(jié)構(gòu)，因此它對密度的變化和空間的維度都相對不太敏感。所以可以基于它定義高維空間的密度。SNN密度度量一個點被類似的點（關(guān)于最近鄰）包圍的程度。這樣，在高密度和低密度區(qū)域的點一般具有相對較高的SNN密度，而在從低密度到高密度過度的區(qū)域中的點（簇間的點）將傾向于具有低SNN密度。這樣的方法可能更適合這樣的數(shù)據(jù)集，其中密度變化很大，但是低密度的簇仍然是有趣的。具有高SNN密度（即SNN圖中的高連接性）的點是候選代表點或核心點，因為它們傾向于在簇的內(nèi)部；而具有低連接性的點是候選噪聲點或離群點，因為它們多半在環(huán)繞簇的區(qū)域中。

（8）???????基于SNN密度的聚類。是一種將SNN密度與DBSCAN算法結(jié)合在一起的算法。類似于JP算法，都以SNN相似度圖開始。然而，基于SNN密度的聚類算法簡單地使用DBSCAN，而不是使用閾值稀疏化SNN相似度圖，然后取連通分支作為簇。算法步驟：（1）計算SNN相似度圖；（2）以用戶指定的參數(shù)Eps和MinPts，使用DBSCAN。算法自動地確定數(shù)據(jù)中的簇的個數(shù)。注意并非所有的點都被聚類。被丟棄的點包括噪聲和離群點，以及沒有很強地連接到一組點的那些點。基于SNN密度的聚類發(fā)現(xiàn)這樣的簇，簇中的點相互之間都是強連接的。依賴于應(yīng)用，我們可能希望丟棄許多點。例如：基于SNN密度的聚類對于發(fā)現(xiàn)文檔組中的主題效果很好。優(yōu)缺點：優(yōu)缺點類似于JP聚類，然而，核心點和SNN密度的使用大大增加了該方法的能力和靈活性，不像DBSCAN，它可以用于高維數(shù)據(jù)和簇具有不同密度的情況。不像JP聚類簡單地使用閾值，然后取連通分支作為簇，基于SNN密度的聚類使用SNN密度和核心點概念的方法。

4.6.4?可伸縮的聚類算法

層次聚類的存儲需求一般是O(m²)，其中m是對象的個數(shù)。使用k-d樹或R*樹，一般產(chǎn)生數(shù)據(jù)空間的層次劃分，可以用來減少發(fā)現(xiàn)點的最近鄰所需要的時間。注意，基于網(wǎng)格的聚類方法也劃分?jǐn)?shù)據(jù)空間。使用抽樣可以降低時間復(fù)雜度，但是，抽樣的問題是小簇可能丟失。另一種降低時間復(fù)雜度的方法是，使用某種有效的技術(shù)，將數(shù)據(jù)劃分成不相交的集合，然后分別對這些集合聚類。最終的簇的集合是這些分離的簇的集合的并，或者通過合并和對分離的簇的集合求精得到。一個例子是二分K均值，所以二分K均值顯著地比一般的K均值快。另一種角力方法：首先匯總數(shù)據(jù)（通過一遍掃描），然后在匯總數(shù)據(jù)上聚類。特殊地，領(lǐng)導(dǎo)者算法或者將一個數(shù)據(jù)對象放進(jìn)最近的簇（如果該簇足夠近），或者創(chuàng)建一個包含當(dāng)前對象的新簇。這種方法關(guān)于對象個數(shù)是線性的，可以用來匯總數(shù)據(jù)，以便使用其他聚類技術(shù)。BIRCH算法使用了類似的概念。

（1）???????BIRCH。它用于歐幾里得向量空間數(shù)據(jù)，即平均值是有意義的數(shù)據(jù)。BIRCH能夠用一遍掃描有效地對這種數(shù)據(jù)進(jìn)行聚類，并可以使用附加的掃描改進(jìn)聚類。BIRCH還能夠有效的處理離群點。BIRCH不要求數(shù)據(jù)都在內(nèi)存中。BIRCH基于聚類特征（CF）和CF樹的概念。其基本思想是：數(shù)據(jù)點（向量）的簇可以用三元組(N,LS,SS)表示。N：簇中點的個數(shù)；LS：點的線性和；SS點的平方和。這些量可以增量的更新。CF樹是一顆高度平衡的樹。葉節(jié)點由一個聚類特征序列CF_i組成，葉節(jié)點的直徑必須小于參數(shù)化的閾值T。可以通過調(diào)整閾值參數(shù)T，可以控制樹的高度。目標(biāo)是通過調(diào)整參數(shù)T，將CT樹保存在內(nèi)存中。CF樹在掃描時創(chuàng)建。BIRCH在每次分裂后跟隨一個合并步。這一步的目的是提高空間利用率，避免不對稱的數(shù)據(jù)輸入順序帶來的問題。BIRCH還有一個刪除離群點的過程。當(dāng)用盡內(nèi)存而需要重建樹時，可以將離群點寫到磁盤。（離群點定義為包含的點遠(yuǎn)小于平均情況的結(jié)點）。在該過程的特定點，掃描離群點，看是否可以將它們吸收到樹中，而不導(dǎo)致樹增長。如果可以，則吸收它們，如果不可以，則刪除它們。?算法步驟：（1）通過創(chuàng)建匯總數(shù)據(jù)的CF樹，將數(shù)據(jù)轉(zhuǎn)入內(nèi)存；（2）根據(jù)第3階段的需要，構(gòu)造一顆較小的CF樹。T增值，然后重新插入葉頂點項（簇）。由于T已增加，某些簇將合并；（3）進(jìn)行全局聚類。可以使用不同形式的全局聚類（使用所有簇之間的逐對距離的聚類）。然而，我們選取一種凝聚的層次技術(shù)，因為聚類特征存放了對于特定聚類類型很重要的匯總信息，可以使用全局聚類算法，就像它用于CF代表的簇中的所有點上一樣；（4）使用步驟（3）發(fā)現(xiàn)的簇質(zhì)心，重新分布數(shù)據(jù)點，從而發(fā)現(xiàn)新的簇集合。這客服了可能在BIRCH第一階段發(fā)現(xiàn)的問題。由于頁面大小的限制和參數(shù)T的緣故，應(yīng)當(dāng)在一個簇中的點有時可能被分裂，而應(yīng)當(dāng)在不同簇中的點有時可能被合并。此外，如果數(shù)據(jù)集中包含重復(fù)點，則這些點根據(jù)出現(xiàn)次序的不同，有時可能被聚類到不同的類。通過多次重復(fù)本階段，過程將收斂到一個局部最優(yōu)解。

CURE。它能夠處理大型數(shù)據(jù)、離群點和具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。CURE使用簇中的多個代表點來表示一個簇。理論上，這些點捕獲了簇的幾何形狀。選取的點的個數(shù)是一個參數(shù)，但是業(yè)已發(fā)現(xiàn)10或更大的值效果很好。CURE使用一種凝聚層次聚類方案進(jìn)行實際的聚類。兩個簇之間的距離是任意兩個代表點（在它們向它們代表的中心收縮之后）之間的最短距離。盡管這種方法與我們看到的其他層次聚類方案不完全一樣。但是如果 =0，它等價于基于質(zhì)心的層次聚類；而 =1時它與單鏈層次聚類大致相同。注意，盡管使用層次聚類方案，但是CURE的目標(biāo)是發(fā)現(xiàn)用戶指定個數(shù)的簇。CURE利用層次聚類過程的特性，在聚類過程的兩個階段刪除離群點。首先，如果一個簇增長緩慢，則這意味它主要由離群點組成，因為根據(jù)定義，離群點遠(yuǎn)離其他點，并且不會經(jīng)常與其他點合并。在CURE中，離群點刪除的第一個階段一般出現(xiàn)在簇的個數(shù)是原來點數(shù)的1/3時。第二個離群點刪除階段出現(xiàn)在簇的個數(shù)達(dá)到K（期望的簇的個數(shù)）的量級時。此時，小簇又被刪除。由于CURE在最壞情況下復(fù)雜度為O(m²logm)，它不能直接用于大型數(shù)據(jù)集。因此CURE使用了兩種技術(shù)來加快聚類過程。第一種技術(shù)是取隨機(jī)樣本，并在抽樣的數(shù)據(jù)點上進(jìn)行層次聚類。隨后是最終掃描，通過選擇具有最近代表點的簇，將數(shù)據(jù)集中剩余的點指派到簇中。在某些情況下，聚類所需要的樣本仍然太大，需要第二種技術(shù)。在這種情況下，CURE劃分樣本數(shù)據(jù)，然后聚類每個劃分中的點。這種預(yù)聚類步后通常緊隨中間簇的聚類，以及將數(shù)據(jù)集中的每個點指派到一個簇的最終掃描。CURE算法步驟：（1）由數(shù)據(jù)集抽取一個隨機(jī)樣本。值得注意的是，CURE的文章明確地推出一個公式，指出為了以較高的概率確保所有的簇都被最少的點代表，樣本應(yīng)當(dāng)多大；（2）將樣本劃分成p個大小相等的劃分；（3）使用CURE的層次聚類算法，將每個劃分中的點聚類成個簇，得到總共個簇。注意，在此處理過程中將刪除某些離群點；（4）使用CURE的層次聚類算法對上一步發(fā)現(xiàn)的個簇進(jìn)行聚類，直到只剩下K個簇；（5）刪除離群點。這是刪除離群點的第二階段；（6）將所有剩余的數(shù)據(jù)點指派到最近的簇，得到完全聚類。CURE抽樣：關(guān)鍵問題是樣本是否具有代表性，即它是否捕獲了感興趣的特征。對于聚類，該問題是我們是否能夠在樣本中發(fā)現(xiàn)與整個樣本對象集中相同的簇。CURE的創(chuàng)建者推導(dǎo)出了一個樣本大小的界，指出為了（以較高的概率）確保我們從每個簇至少得到一定數(shù)量的點，

?

數(shù)。再次說明，CURE以如下方式使用抽樣。首先抽取一個樣本，然后使用CURE對該樣本進(jìn)行聚類。找到簇之后，將每個未聚類的點指派到最近的簇。劃分：關(guān)鍵問題是如何選擇p和q。CURE的時間復(fù)雜度是O(m²)或更高，并且還需要將所有的數(shù)據(jù)放在內(nèi)存。因此，我們希望選擇盡可能小的p，使得整個劃分可以以“合理的”時間在內(nèi)存處理。選擇p和q的另一個因素涉及聚類質(zhì)量。具體的說，目標(biāo)是選取p和q的值，使得同一個基本簇的對象最終在一個簇中。

4.6.5?使用哪種聚類算法

常見生物學(xué)分類法，層次是首選。對于旨在匯總的聚類，劃分聚類是常用的。基于原型的聚類方案以及某些基于圖的聚類方案（全鏈、質(zhì)心和Ward）傾向于產(chǎn)生全局簇。相比之下，基于密度的聚類技術(shù)和某些基于圖的聚類技術(shù)（如單鏈）傾向于產(chǎn)生非全局的簇，因而包含許多相互之間不很相似的對象。

總結(jié)

以上是生活随笔為你收集整理的聚类Introducion的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。