各種聚類(lèi)算法介紹及對(duì)比-wenkub
2023-07-08 16:43:15 本頁(yè)面
【正文】 rs=NULL) ：進(jìn)行層次聚類(lèi)。聚類(lèi)的效果如下圖，黑色是噪音點(diǎn)： 另外我們可以看出凝聚的層次聚類(lèi)并沒(méi)有類(lèi)似基本K均值的全局目標(biāo)函數(shù)，沒(méi)有局部極小問(wèn)題或是很難選擇初始點(diǎn)的問(wèn)題。層次聚類(lèi)的流程凝聚型層次聚類(lèi)的策略是先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到所有對(duì)象都在一個(gè)簇中，或者某個(gè)終結(jié)條件被滿足。為彌補(bǔ)分解與合并的不足，層次合并經(jīng)常要與其它聚類(lèi)方法相結(jié)合，如循環(huán)定位。自下而上法就是一開(kāi)始每個(gè)個(gè)體（object）都是一個(gè)類(lèi)，然后根據(jù)linkage尋找同類(lèi)，最后形成一個(gè)“類(lèi)”。不停的合并，直到合成了一個(gè)類(lèi)。一、層次聚類(lèi)層次聚類(lèi)的原理及分類(lèi)1）層次法（Hierarchical methods）先計(jì)算樣本之間的距離。其中類(lèi)與類(lèi)的距離的計(jì)算方法有：最短距離法，最長(zhǎng)距離法，中間距離法，類(lèi)平均法等。自上而下法就是反過(guò)來(lái)，一開(kāi)始所有個(gè)體都屬于一個(gè)“類(lèi)”，然后根據(jù)linkage排除異己，最后每個(gè)個(gè)體都成為一個(gè)“類(lèi)”。絕大多數(shù)層次聚類(lèi)屬于凝聚型層次聚類(lèi)，它們只是在簇間相似度的定義上有所不同。合并的操作往往是最終的，一旦合并兩個(gè)簇之后就不會(huì)撤銷(xiāo)。d為距離矩陣；method表示類(lèi)的合并方法，single最短距離法，plete最長(zhǎng)距離法，median中間距離法，mcquitty首先你要確定這堆散點(diǎn)最后聚成幾類(lèi)，然后挑選幾個(gè)點(diǎn)作為初始中心點(diǎn)，再然后依據(jù)預(yù)先定好的啟發(fā)式算法（heuristic algorithms）給數(shù)據(jù)點(diǎn)做迭代重置（iterative relocation），直到最后到達(dá)“類(lèi)內(nèi)的點(diǎn)都足夠近，類(lèi)間的點(diǎn)都足夠遠(yuǎn)”的目標(biāo)效果。對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各簇中心的距離，將它賦給最近的簇。此時(shí)，簇的質(zhì)心就是該簇內(nèi)所有數(shù)據(jù)點(diǎn)的平均值。時(shí)間復(fù)雜度：O(tKmn)，其中，t為迭代次數(shù)，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)空間復(fù)雜度：O((m+K)n)，其中，K為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)KMeans 算法的詳細(xì)過(guò)程從上圖中，我們可以看到，A, B, C, D, E 是五個(gè)在圖中點(diǎn)。②然后對(duì)圖中的所有點(diǎn)求到這K個(gè)種子點(diǎn)的距離，假如點(diǎn)Pi離種子點(diǎn)Si最近，那么Pi屬于Si點(diǎn)群。聚類(lèi)的效果如下圖，折線是歷次循環(huán)時(shí)3個(gè)簇的質(zhì)心的更新軌跡，黑點(diǎn)是初始質(zhì)心： 我們查看基本K均值算法實(shí)現(xiàn)步驟及上面的聚類(lèi)效果可以發(fā)現(xiàn)，該聚類(lèi)算法將所有數(shù)據(jù)點(diǎn)都進(jìn)行了指派，不識(shí)別噪音點(diǎn)。kmeans與DBSCAN的區(qū)別kmeans聚類(lèi)算法的初始點(diǎn)選擇不穩(wěn)定，是隨機(jī)選取的，這就引起聚類(lèi)結(jié)果的不穩(wěn)定。kmeans注意問(wèn)題1）K如何確定 kmenas算法首先選擇K個(gè)初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個(gè)數(shù)。 ②穩(wěn)定性方法[3] 穩(wěn)定性方法對(duì)一個(gè)數(shù)據(jù)集進(jìn)行2次重采樣產(chǎn)生2個(gè)數(shù)據(jù)子集，再用相同的聚類(lèi)算法對(duì)2個(gè)數(shù)據(jù)子集進(jìn)行聚類(lèi)，產(chǎn)生2個(gè)具有k個(gè)聚類(lèi)的聚類(lèi)結(jié)果，計(jì)算2個(gè)聚類(lèi)結(jié)果的相似度的分布情況。 系統(tǒng)演化方法將一個(gè)數(shù)據(jù)集視為偽熱力學(xué)系統(tǒng)，當(dāng)數(shù)據(jù)集被劃分為K個(gè)聚類(lèi)時(shí)稱(chēng)系統(tǒng)處于狀態(tài)K。 基于Canopy Method的聚類(lèi)算法將聚類(lèi)過(guò)程分為兩個(gè)階段 常見(jiàn)的方法是隨機(jī)的選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。 第二種有效的方法是，取一個(gè)樣本，并使用層次聚類(lèi)技術(shù)對(duì)它聚類(lèi)。 第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開(kāi)銷(xiāo)也非常大。 兩者都是評(píng)定個(gè)體間差異的大小的。 也就是說(shuō)對(duì)于兩條空間向量，即使兩點(diǎn)距離一定，他們的夾角余弦值也可以隨意變化。 對(duì)于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質(zhì)心都是其均值，即向量各維取平均即可。 當(dāng)采用歐式距離時(shí)，目標(biāo)函數(shù)一般為最小化對(duì)象到其簇質(zhì)心的距離的平方和。 這將消除當(dāng)前對(duì)總平方誤差影響最大的點(diǎn)。另外，編程實(shí)現(xiàn)時(shí)，要注意空簇可能導(dǎo)致的程序bug?；诿芏染垲?lèi)的思想：思路就是定一個(gè)距離半徑，最少有多少個(gè)點(diǎn)，然后把可以到達(dá)的點(diǎn)都連起來(lái)，判定為同類(lèi)。DBSCAN的擴(kuò)展叫OPTICS（Ordering Points To Identify Clustering Structure）通過(guò)優(yōu)先對(duì)高密度（high density）進(jìn)行搜索，然后根據(jù)高密度的特點(diǎn)設(shè)置參數(shù)，改善了DBSCAN的不足。注意：密度可達(dá)是單向的，密度可達(dá)即可容納同一類(lèi)。DBSCAN目的是找到密度相連對(duì)象的最大集合。當(dāng)沒(méi)有新的點(diǎn)可以添加到任何簇時(shí)，
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1