各種聚類算法介紹及對比-文庫吧
2025-06-08 16:43 本頁面
【正文】 onbased methods聚類多適用于中等體量的數據集，但我們也不知道“中等”到底有多“中”，所以不妨理解成，數據集越大，越有可能陷入局部最小。Kmeans算法的原理kmeans算法以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。kmeans算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心，即選擇K個初始質心。對剩余的每個對象，根據其與各簇中心的距離，將它賦給最近的簇。然后重新計算每個簇的平均值。 這個過程不斷重復，直到準則函數收斂，直到質心不發(fā)生明顯的變化。通常，采用平方誤差準則，誤差的平方和SSE作為全局的目標函數，即最小化每個點到最近質心的歐幾里得距離的平方和。此時，簇的質心就是該簇內所有數據點的平均值。選擇K個點作為初始質心repeat將每個點指派到最近的質心，形成K個簇重新計算每個簇的質心until簇不發(fā)生變化或達到最大迭代次數時間復雜度：O(tKmn)，其中，t為迭代次數，K為簇的數目，m為記錄數，n為維數空間復雜度：O((m+K)n)，其中，K為簇的數目，m為記錄數，n為維數KMeans 算法的詳細過程從上圖中，我們可以看到，A, B, C, D, E 是五個在圖中點。而灰色的點是我們的種子點，也就是我們用來找點群的點。有兩個種子點，所以K=2。然后，KMeans的算法如下：①隨機在圖中取K（這里K=2）個種子點。②然后對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那么Pi屬于Si點群。（我們可以看到A,B屬于上面的種子點，C,D,E屬于下面中部的種子點）③接下來，我們要移動種子點到屬于他的“點群”的中心。（見圖上的第三步）④然后重復第2）和第3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A,B,C，下面的種子點聚合了D，E）。聚類的效果如下圖，折線是歷次循環(huán)時3個簇的質心的更新軌跡，黑點是初始質心： 我們查看基本K均值算法實現步驟及上面的聚類效果可以發(fā)現，該聚類算法將所有數據點都進行了指派，不識別噪音點。另外選擇適當的初試質心是基本K均值過程的關鍵。k均值的優(yōu)缺點及分類優(yōu)點：1，簡單，易于理解和實現；2，時間復雜度低缺點：1）kmeans要手工輸入類數目，對初始值的設置很敏感；所以有了kmeans++、intelligent kmeans、genetic kmeans；2）kmeans對噪聲和離群值非常敏感，所以有了kmedoids和kmedians；3）kmeans只用于numerical類型數據，不適用于categorical類型數據，所以kmodes；4）kmeans不能解決非凸（nonconvex）數據，所以有了kernel kmeans。5）kmeans主要發(fā)現圓形或者球形簇，不能識別非球形的簇。kmeans與DBSCAN的區(qū)別kmeans聚類算法的初始點選擇不穩(wěn)定，是隨機選取的，這就引起聚類結果的不穩(wěn)定。kmeans屬于動態(tài)聚類，往往聚出來的類有點圓形或者橢圓形。kmeans對于圓形區(qū)域聚類效果較好，dbscan基于密度，對于集中區(qū)域效果較好。對于不規(guī)則形狀，kmeans完全無法用，dbscan可以起到很好的效果。kmeans注意問題1）K如何確定 kmenas算法首先選擇K個初始質心，其中K是用戶指定的參數，即所期望的簇的個數。這樣做的前提是我們已經知道數據集中包含多少個簇，但很多情況下，我們并不知道數據的分布情況，實際上聚類就是我們發(fā)現數據分布的一種手段。如何有效的確定K值，這里大致提供幾種方法：①與層次聚類結合[2] 經常會產生較好的聚類結果的一個有趣策略是，首先采用層次凝聚算法決定結果粗的數目，并找到一個初始聚類，然后用迭代重定位來改進該聚類。②穩(wěn)定性方法[3] 穩(wěn)定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類算法對2個數據子集進行聚類，產生2個具有k個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明k個聚類反映了穩(wěn)定的聚類結構，其相似度可以用來估計聚類個數。采用次方法試探多個k，找到合適的k值。③系統演化方法
環(huán)評公示相關推薦
鄂ICP備17016276號-1