2022年聚類算法學(xué)習(xí)筆記

1、精心整理歡迎下載聚類的定義聚類是一個將數(shù)據(jù)集劃分為若干個子集的過程，并使得同一集合內(nèi)的數(shù)據(jù)對象具有較高的相似度， 而不同集合中的數(shù)據(jù)對象則是不相同的，相似或不相似的度量是基于數(shù)據(jù)對象描述屬性的聚類值來確定的，通常就是利用各個聚類間的距離來進行描述的。聚類分析的基本指導(dǎo)思想是最大程度地實現(xiàn)類中對象相似度最大，類間對象相似度最小。聚類與分類不同， 在分類模型中， 存在樣本數(shù)據(jù)， 這些數(shù)據(jù)的類標(biāo)號是已知的，分類的目的是從訓(xùn)練樣本集中提取出分類的規(guī)則，用于對其他標(biāo)號未知的對象進行類標(biāo)識。 在聚類中， 預(yù)先不知道目標(biāo)數(shù)據(jù)的有關(guān)類的信息，需要以某種度量為標(biāo)準(zhǔn)將所有的數(shù)據(jù)對象劃分到各個簇中。因此，聚類分析又

2、稱為無監(jiān)督的學(xué)習(xí)。聚類主要包括以下幾個過程：（1）數(shù)據(jù)準(zhǔn)備：包括特征標(biāo)準(zhǔn)化和降維。（2）特征選擇、提出：從最初的特征中選擇是有效的特征，并將其存儲于向量中。（3）特征提?。和ㄟ^對所選擇的特征進行轉(zhuǎn)換，形成新的突出特征。（4）聚類（或分組）：首先選擇合適特征類型的某種距離函數(shù)（或構(gòu)造新的距離函數(shù)）進行接近程度的度量，然后執(zhí)行聚類或分組。聚類結(jié)果評估：指對聚類結(jié)果進行評估。評估主要有3種：外部有效性評估、內(nèi)部有效性評估和相關(guān)性測試評估。聚類算法的要求（1）可擴展性。許多聚類算法在小數(shù)據(jù)集（少于200 個數(shù)據(jù)對象）時可以工作很好；但一個大數(shù)據(jù)庫可能會包含數(shù)以百萬的對象。利用采樣方法進行聚類分析可能得

3、到一個有偏差的結(jié)果，這時就需要可擴展的聚類分析算法。（2）處理不同類型屬性的能力。許多算法是針對基于區(qū)間的數(shù)值屬性而設(shè)計的。但是有些應(yīng)用需要對實類型數(shù)據(jù)。如：二值類型、符號類型、順序類型，或這些數(shù)據(jù)類型的組合。（3）發(fā)現(xiàn)任意形狀的聚類。許多聚類算法是根據(jù)歐氏距離和manhattan 距離來進行聚類的?；谶@類距離的聚類方法一般只能發(fā)現(xiàn)具有類似大小和密度的精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 6 頁 - - - - - - - - -精心整理歡迎下載圓形或球狀聚類。 而實際一個聚類是可以具有任意形狀的，因此設(shè)計能夠發(fā)現(xiàn)任意開關(guān)類集

4、的聚類算法是非常重要的。（4）需要（由用戶）決定的輸入?yún)?shù)最少。許多聚類算法需要用戶輸入聚類分析中所需要的一些參數(shù)（如：期望所獲得聚類的個數(shù)）。而聚類結(jié)果通常都與輸入?yún)?shù)密切相關(guān)； 而這些參數(shù)常常也很難決定， 特別是包含高維對象的數(shù)據(jù)集。這不僅構(gòu)成了用戶的負(fù)擔(dān)，也使得聚類質(zhì)量難以控制。（5）處理噪聲數(shù)據(jù)的能力。大多數(shù)現(xiàn)實世界的數(shù)據(jù)庫均包含異常數(shù)據(jù)、不明數(shù)據(jù)、數(shù)據(jù)丟失和噪聲數(shù)據(jù)， 有些聚類算法對這樣的數(shù)據(jù)非常敏感并會導(dǎo)致獲得質(zhì)量較差的數(shù)據(jù)。（6）對輸入記錄順序不敏感。一些聚類算法對輸入數(shù)據(jù)的順序敏感，也就是不同的數(shù)據(jù)輸入順序會導(dǎo)致獲得非常不同的結(jié)果。因此設(shè)計對輸入數(shù)據(jù)順序不敏感的聚類算法也是非常

5、重要的。（7）高維問題。一個數(shù)據(jù)庫或一個數(shù)據(jù)倉庫或許包含若干維屬性。許多聚類算法在處理低維數(shù)據(jù)時 （僅包含二到三個維） 時表現(xiàn)很好， 然而設(shè)計對高維空間中的數(shù)據(jù)對象， 特別是對高維空間稀疏和怪異分布的的數(shù)據(jù)對象，能進行較好聚類分析的聚類算法已成為聚類研究中的一項挑戰(zhàn)。（8）基于約束的聚類。現(xiàn)實世界中的應(yīng)用可能需要在各種約束之下進行聚類分析。假設(shè)需要在一個城市中確定一些新加油站的位置，就需要考慮諸如： 城市中的河流、 調(diào)整路，以及每個區(qū)域的客戶需求等約束情況下居民住地的聚類分析。 設(shè)計能夠發(fā)現(xiàn)滿足特定約束條件且具有較好聚類質(zhì)量的聚類算法也是一個重要聚類研究任務(wù)。（9）可解釋性和可用性。用戶往往希

6、望聚類結(jié)果是可理解的、可解釋的，以及可用的， 這就需要聚類分析要與特定的解釋和應(yīng)用聯(lián)系在一起。因此研究一個應(yīng)用的目標(biāo)是如何影響聚類方法選擇也是非常重要的。各種聚類算法介紹隨著人們對數(shù)據(jù)挖掘的深入研究和了解，各種聚類算法的改進算法也相繼提出，很多新算法在前人提出的算法中做了某些方面的提高和改進，且很多算法是有針對性地為特定的領(lǐng)域而設(shè)計。 我們必須清楚地了解各種算法的優(yōu)缺點和應(yīng)用范圍，根據(jù)實際問題選擇合適的算法。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 6 頁 - - - - - - - - -精心整理歡迎下載基于層次的聚類算法基于層次

7、的聚類算法對給定數(shù)據(jù)對象進行層次上的分解，可分為凝聚算法和分裂算法。 (1)自底向上的凝聚聚類方法。這種策略是以數(shù)據(jù)對象作為原子類，然后將這些原子類進行聚合。 逐步聚合成越來越大的類， 直到滿足終止條件。 凝聚算法的過程為：在初始時，每一個成員都組成一個單獨的簇，在以后的迭代過程中，再把那些相互鄰近的簇合并成一個簇，直到所有的成員組成一個簇為止。其時間和空間復(fù)雜性均為o(n2)。通過凝聚式的方法將兩簇合并后，無法再將其分離到之前的狀態(tài)。在凝聚聚類時，選擇合適的類的個數(shù)和畫出原始數(shù)據(jù)的圖像很重要。 (2) 自頂向下分裂聚類方法。與凝聚法相反，該法先將所有對象置于一個簇中，然后逐漸細分為越來越小的

8、簇， 直到每個對象自成一簇， 或者達到了某個終結(jié)條件。其主要思想是將那些成員之間不是非常緊密的簇進行分裂。跟凝聚式方法的方向相反， 從一個簇出發(fā)， 一步一步細化。 它的優(yōu)點在于研究者可以把注意力集中在數(shù)據(jù)的結(jié)構(gòu)上面。 一般情況下不使用分裂型方法， 因為在較高的層很難進行正確的拆分基于密度的聚類算法很多算法都使用距離來描述數(shù)據(jù)之間的相似性，但對于非凸數(shù)據(jù)集， 只用距離來描述是不夠的。 此時可用密度來取代距離描述相似性，即基于密度的聚類算法。它不是基于各種各樣的距離， 所以能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。 其指導(dǎo)思想是： 只要一個區(qū)域中的點的密度 （對象或數(shù)據(jù)點的數(shù)目）大過某個

9、閾值， 就把它加到與之相近的聚類中去。該法從數(shù)據(jù)對象的分布密度出發(fā)，把密度足夠大的區(qū)域連接起來，從而可發(fā)現(xiàn)任意形狀的簇， 并可用來過濾“噪聲”數(shù)據(jù)。常見算法有dbscan，denclue 等基于劃分的聚類算法給定一個 n個對象的元組或數(shù)據(jù)庫，根據(jù)給定要創(chuàng)建的劃分的數(shù)目k，將數(shù)據(jù)劃分為 k 個組，每個組表示一個簇類（ =n ）時滿足如下兩點： (1) 每個組至少包含一個對象； (2) 每個對象必須屬于且只屬于一個組。算法先隨機創(chuàng)建一個初始劃分，然后采用一種迭代的重定位技術(shù)，通過將對象根據(jù)簇類之間的差異從一個劃分移到另一個劃分來提高簇類內(nèi)數(shù)據(jù)之間的相似程度。一種好的劃分的一般精品學(xué)習(xí)資料 可選擇p

10、 d f - - - - - - - - - - - - - - 第 3 頁，共 6 頁 - - - - - - - - -精心整理歡迎下載準(zhǔn)則是：在同一個類中的對象盡可能“接近”或相似，而不同類中的對象盡可能“遠離”或不同。為了達到全局最優(yōu)， 基于劃分的聚類會要求窮舉所有可能的劃分。典型的劃包括： k-means ，pam ，em等。劃分法收斂速度快，在對中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用。 缺點是它傾向于識別凸形分布大小相近、密度相近的聚類，不能發(fā)現(xiàn)分布形狀比較復(fù)雜的聚類，它要求類別數(shù)目k 可以合理地估計，且初始中心的選擇和噪聲會對聚類結(jié)果產(chǎn)生很大影響。還要求用戶預(yù)先指定聚類個數(shù)。基于網(wǎng)格

11、的聚類算法首先將數(shù)據(jù)空間量化為有限個單元的網(wǎng)格結(jié)構(gòu)，然后對量化后的單個的單元為對象進行聚類。典型的算法有sting ，clique等。網(wǎng)格聚類法處理速度快，處理時間與數(shù)據(jù)對象的數(shù)目無關(guān)， 一般由網(wǎng)格單元的數(shù)目決定。 缺點是只能發(fā)現(xiàn)邊界是水平或垂直的聚類， 不能檢測到斜邊界。 該類算法也不適用于高維情況，因為網(wǎng)格單元的數(shù)目隨著維數(shù)的增加而呈指數(shù)增長。另外還有下列問題：一是如何選擇合適的單元大小和數(shù)目， 二是怎樣對每個單元中對象的信息進行匯總，三是存在量化尺度的問題?；谀Ｐ偷木垲愃惴ɑ谀Ｐ偷姆椒ńo每一個聚簇假定了一個模型，然后去尋找能夠很好滿足這個模型的數(shù)據(jù)集。 這個模型可能是數(shù)據(jù)點在空間中的

12、密度分布函數(shù)，它由一系列的概率分布決定， 也可能通過基于標(biāo)準(zhǔn)的統(tǒng)計數(shù)字自動決定聚類的數(shù)目。它的一個潛在假定是： 目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。一般有 2 種嘗試方向：統(tǒng)計的方案和神經(jīng)網(wǎng)絡(luò)的方案。cobweb是一種流行的簡單增量概念聚類算法，以一個分類樹的形式來創(chuàng)建層次聚類，它的輸入對象用分類屬性-值對來描述。cobweb的優(yōu)點為：可以自動修正劃分中類的數(shù)目；不需要用戶提供輸入?yún)?shù)。缺點為： cobweb基于這樣一個假設(shè)：在每個屬性上的概率分布是彼此獨立的。但這個假設(shè)并不總是成立。 且對于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導(dǎo)致時間和空間復(fù)雜性的劇烈變化，不適用于聚類大型數(shù)據(jù)庫的數(shù)據(jù)。

13、模糊聚類算法現(xiàn)實中很多對象沒有嚴(yán)格的屬性， 其類屬和形態(tài)存在著中介性， 適合軟劃分。恰好模糊聚類具有描述樣本類屬中間性的優(yōu)點，因此成為當(dāng)今聚類分析研究的主精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 6 頁 - - - - - - - - -精心整理歡迎下載流。常用的模糊聚類有動態(tài)直接聚類法、最大樹法、fcm 等。基本原理為：假設(shè)有 n個要分析的樣本，每個樣本有m個可量化的指標(biāo)，一般步驟為：(1) 標(biāo)準(zhǔn)化數(shù)據(jù)：常用的數(shù)據(jù)標(biāo)準(zhǔn)化方法有：小數(shù)定標(biāo)規(guī)范化，最大最小值規(guī)范化，標(biāo)準(zhǔn)差規(guī)范化等。 (2) 建立模糊相似矩陣，標(biāo)定相似系數(shù)。(3) 計算

14、多極相似矩陣，計算整體相似關(guān)系矩陣，有傳遞閉包法，動態(tài)直接聚類法，最大樹法等。(4) 給定一個聚類水平， 計算絕對相似矩陣， 按行列調(diào)整絕對相似矩陣， 每個分塊即為一個分類。其它聚類算法（1）基于群的聚類方法該法是進化計算的一個分支， 模擬了生物界中蟻群、 魚群等在覓食或避敵時的行為?？煞譃橄伻核惴╝co 和 pso 。蟻群聚類算法的許多特性，如靈活性、健壯性、分布性和自組織性等， 使其非常適合本質(zhì)上是分布、動態(tài)及又要交錯的問題求解中，能解決無人監(jiān)督的聚類問題，具有廣闊的前景。pso 模擬了魚群或鳥群的行為。在優(yōu)化領(lǐng)域， pso 可以與遺傳算法相媲美，并在預(yù)測精度和運行速度方面占優(yōu)勢。 對 a

15、co 或 pso在數(shù)據(jù)挖掘中應(yīng)用的研究仍處于早期階段，要將這些方法用到實際的大規(guī)模數(shù)據(jù)挖掘的聚類分析中還需要做大量的研究工作。（2）基于粒度的聚類方法從粒度的角度看，我們會發(fā)現(xiàn)聚類和分類有很大的相通之處：聚類操作實際上是在一個統(tǒng)一粒度下進行計算的；分類操作是在不同粒度下進行的。所以說在粒度原理下，聚類和分類是相通的，很多分類的方法也可以用在聚類方法中。作為一個新的研究方向， 雖然目前粒度計算還不成熟， 尤其是對粒度計算語義的研究還相當(dāng)少， 但相信隨著粒度理論的不斷發(fā)展，今后幾年它必將在聚類算法及其相關(guān)領(lǐng)域得到廣泛的應(yīng)用。（3）譜聚法譜聚類方法建立在譜圖理論基礎(chǔ)之上，并利用數(shù)據(jù)的相似矩陣的特征向

16、量進行聚類，是一種基于兩點間相似關(guān)系的方法， 這使得該方法適用于非測度空間。它與數(shù)據(jù)點的維數(shù)無關(guān)， 而僅與數(shù)據(jù)點的個數(shù)有關(guān)， 可以避免由特征向量的過高維數(shù)所造成的奇異性問題。 它又是一個判別式算法， 不用對數(shù)據(jù)的全局結(jié)構(gòu)作假設(shè)，而是首先收集局部信息來表示兩點屬于同一類的可能性；然后根據(jù)某一聚類精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 6 頁 - - - - - - - - -精心整理歡迎下載判據(jù)作全局決策， 將所有數(shù)據(jù)點劃分到不同的數(shù)據(jù)集合中。通常這樣的判據(jù)可以在一個嵌入空間中得到解釋，該嵌入空間是由數(shù)據(jù)矩陣的某幾個特征向量張成的。譜聚類算法成功原因在于： 通過特征分解， 可以獲得聚類判據(jù)在放松了的連續(xù)域中的全局最優(yōu)解。與其他算法相比，它不僅思想簡單、易于實現(xiàn)、不易陷入局部最優(yōu)解， 而且具有識別非凸分布的聚類能力，非常適合于許多實際問題。 目前，該算法已應(yīng)用于語音識別、vlsi 設(shè)計、文本挖掘等領(lǐng)域。（4）多種聚類方法的融合實際應(yīng)用的復(fù)雜性和數(shù)據(jù)的多樣性往往使得單一的算法無能為力。因此，很多人對多種算法的融合進行了廣泛研究并取得了一些成果。大