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