各種聚類(lèi)算法介紹及對(duì)比(編輯修改稿)
2025-07-20 16:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 [3] 系統(tǒng)演化方法將一個(gè)數(shù)據(jù)集視為偽熱力學(xué)系統(tǒng)，當(dāng)數(shù)據(jù)集被劃分為K個(gè)聚類(lèi)時(shí)稱(chēng)系統(tǒng)處于狀態(tài)K。系統(tǒng)由初始狀態(tài)K=1出發(fā)，經(jīng)過(guò)分裂過(guò)程和合并過(guò)程，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)Ki，所對(duì)應(yīng)的聚類(lèi)結(jié)構(gòu)決定了最優(yōu)類(lèi)數(shù)Ki。系統(tǒng)演化方法能提供關(guān)于所有聚類(lèi)之間的相對(duì)邊界距離或可分程度，適用于明顯分離的聚類(lèi)結(jié)構(gòu)和輕微重疊的聚類(lèi)結(jié)構(gòu)。④使用canopy算法進(jìn)行初始劃分[4] 基于Canopy Method的聚類(lèi)算法將聚類(lèi)過(guò)程分為兩個(gè)階段 Stage聚類(lèi)最耗費(fèi)計(jì)算的地方是計(jì)算對(duì)象相似性的時(shí)候，Canopy Method在第一階段選擇簡(jiǎn)單、計(jì)算代價(jià)較低的方法計(jì)算對(duì)象相似性，將相似的對(duì)象放在一個(gè)子集中，這個(gè)子集被叫做Canopy ，通過(guò)一系列計(jì)算得到若干Canopy，Canopy之間可以是重疊的，但不會(huì)存在某個(gè)對(duì)象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預(yù)處理； Stage在各個(gè)Canopy 內(nèi)使用傳統(tǒng)的聚類(lèi)方法(如Kmeans)，不屬于同一Canopy 的對(duì)象之間不進(jìn)行相似性計(jì)算。從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy 不要太大且Canopy 之間重疊的不要太多的話會(huì)大大減少后續(xù)需要計(jì)算相似性的對(duì)象的個(gè)數(shù)；其次，類(lèi)似于Kmeans這樣的聚類(lèi)方法是需要人為指出K的值的，通過(guò)Stage1得到的Canopy 個(gè)數(shù)完全可以作為這個(gè)K值，一定程度上減少了選擇K的盲目性。 其他方法如貝葉斯信息準(zhǔn)則方法（BIC）可參看文獻(xiàn)[5]。2）初始質(zhì)心的選取 選擇適當(dāng)?shù)某跏假|(zhì)心是基本kmeans算法的關(guān)鍵步驟。常見(jiàn)的方法是隨機(jī)的選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問(wèn)題的一種常用技術(shù)是：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡(jiǎn)單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個(gè)數(shù)。 第二種有效的方法是，取一個(gè)樣本，并使用層次聚類(lèi)技術(shù)對(duì)它聚類(lèi)。從層次聚類(lèi)中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法通常很有效，但僅對(duì)下列情況有效：（1）樣本相對(duì)較小，例如數(shù)百到數(shù)千（層次聚類(lèi)開(kāi)銷(xiāo)較大）；（2）K相對(duì)于樣本大小較小 第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。然后，對(duì)于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過(guò)的初始質(zhì)心最遠(yuǎn)的點(diǎn)。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的，而且是散開(kāi)的。但是，這種方法可能選中離群點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開(kāi)銷(xiāo)也非常大。為了克服這個(gè)問(wèn)題，通常該方法用于點(diǎn)樣本。由于離群點(diǎn)很少（多了就不是離群點(diǎn)了），它們多半不會(huì)在隨機(jī)樣本中出現(xiàn)。計(jì)算量也大幅減少。 第四種方法就是上面提到的canopy算法。3）距離的度量 常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評(píng)定個(gè)體間差異的大小的。歐幾里得距離度量會(huì)受指標(biāo)不同單位刻度的影響，所以一般需要先進(jìn)行標(biāo)準(zhǔn)化，同時(shí)距離越大，個(gè)體間差異越大；空間向量余弦?jiàn)A角的相似度度量不會(huì)受指標(biāo)刻度的影響，余弦值落于區(qū)間[1,1]，值越大，差異越小。但是針對(duì)具體應(yīng)用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？ 從幾何意義上來(lái)說(shuō)，n維向量空間的一條線段作為底邊和原點(diǎn)組成的三角形，其頂角大小是不確定的。也就是說(shuō)對(duì)于兩條空間向量，即使兩點(diǎn)距離一定，他們的夾角余弦值也可以隨意變化。感性的認(rèn)識(shí)，當(dāng)兩用戶評(píng)分趨勢(shì)一致時(shí)，但是評(píng)分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個(gè)極端的例子，兩用戶只對(duì)兩件商品評(píng)分，向量分別為(3,3)和(5,5)，這兩位用戶的認(rèn)知其實(shí)是一樣的，但是歐式距離給出的解顯然沒(méi)有余弦值合理。4）質(zhì)心的計(jì)算 對(duì)于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質(zhì)心都是其均值，即向量各維取平均即可。5）算法停止條件 一般是目標(biāo)函數(shù)達(dá)到最優(yōu)或者達(dá)到最大的迭代次數(shù)即可終止。對(duì)于不同的距離度量，目標(biāo)函數(shù)往往不同。當(dāng)采用歐式距離時(shí)，目標(biāo)函數(shù)一般為最小化對(duì)象到其簇質(zhì)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1