聚類演算法比較
1. 有哪些常用的聚類演算法
【聚類】聚類分析是直接比較各對象之間的性質,根據在對象屬性中發現的描述對象及其關系的信息,將數據對象分組。其目標是,組內的對象相互之間是相似的(相關的),而不同組中的對象是不同的(不相關的)。組內的相似性(同質性)越大,組間差別越大,聚類就越好。
聚類的目標是通過對無標記訓練樣本的學習來揭示數據的內在性質及規律,是無監督學習過程。在無監督學習中,訓練樣本標記信息是未知的。聚類試圖將數據集中的樣本劃分為若干個通常不相交的子集,每個子集稱為一個「簇」,每個簇可能對應於一些潛在的類別,這些類別概念對聚類演算法而言事先是未知的,聚類過程僅能自動形成簇結構,簇所對應的概念語義需要由使用者來把握和命名。
2. 八:聚類演算法K-means(20191223-29)
學習內容:無監督聚類演算法K-Means
k-means:模型原理、收斂過程、超參數的選擇
聚類分析是在數據中發現數據對象之間的關系,將數據進行分組,組內的相似性越大,組間的差別越大,則聚類效果越好。
不同的簇類型: 聚類旨在發現有用的對象簇,在現實中我們用到很多的簇的類型,使用不同的簇類型劃分數據的結果是不同的。
基於原型的: 簇是對象的集合,其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近,如(b)所示的原型即為中心點,在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ,最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。
基於密度的 :簇是對象的密度區域,(d)所示的是基於密度的簇,當簇不規則或相互盤繞,並且有早上和離群點事,常常使用基於密度的簇定義。
關於更多的簇介紹參考《數據挖掘導論》。
基本的聚類分析演算法
1. K均值: 基於原型的、劃分的距離技術,它試圖發現用戶指定個數(K)的簇。
2. 凝聚的層次距離: 思想是開始時,每個點都作為一個單點簇,然後,重復的合並兩個最靠近的簇,直到嘗試單個、包含所有點的簇。
3. DBSCAN: 一種基於密度的劃分距離的演算法,簇的個數有演算法自動的確定,低密度中的點被視為雜訊而忽略,因此其不產生完全聚類。
不同的距離量度會對距離的結果產生影響,常見的距離量度如下所示:
優點:易於實現
缺點:可能收斂於局部最小值,在大規模數據收斂慢
演算法思想:
選擇K個點作為初始質心
repeat
將每個點指派到最近的質心,形成K個簇
重新計算每個簇的質心
until 簇不發生變化或達到最大迭代次數
這里的「重新計算每個簇的質心」,是根據目標函數來計算的,因此在開始時要考慮 距離度量和目標函數。
考慮歐幾里得距離的數據,使用 誤差平方和(Sum of the Squared Error,SSE) 作為聚類的目標函數,兩次運行K均值產生的兩個不同的簇集,使用SSE最小的那個。
k表示k個聚類中心,ci表示第幾個中心,dist表示的是歐幾里得距離。
這里有一個問題就是為什麼,我們更新質心是讓所有的點的平均值,這里就是SSE所決定的。
k均值演算法非常簡單且使用廣泛,但是其有主要的兩個缺陷:
1. K值需要預先給定 ,屬於預先知識,很多情況下K值的估計是非常困難的,對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景,可以進行迭代運算,然後找出Cost Function最小時所對應的K值,這個值往往能較好的描述有多少個簇類。
2. K-Means演算法對初始選取的聚類中心點是敏感的 ,不同的隨機種子點得到的聚類結果完全不同
3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇,銀冠指定足夠大的簇的個數是他通常可以發現純子簇。
4. 對離群點的數據進行聚類時,K均值也有問題 ,這種情況下,離群點檢測和刪除有很大的幫助。
下面對初始質心的選擇進行討論:
當初始質心是隨機的進行初始化的時候,K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕,可能只能得到局部的最優解,而無法得到全局的最優解。
多次運行,每次使用一組不同的隨機初始質心,然後選擇一個具有最小的SSE的簇集。該策略非常的簡單,但是效果可能不是很好,這取決於數據集合尋找的簇的個數。
關於更多,參考《數據挖掘導論》
為了克服K-Means演算法收斂於局部最小值的問題,提出了一種 二分K-均值(bisecting K-means)
將所有的點看成是一個簇
當簇小於數目k時
對於每一個簇
計算總誤差
在給定的簇上進行K-均值聚類,k值為2 計算將該簇劃分成兩個簇後總誤差
選擇是的誤差最小的那個簇進行劃分
在原始的K-means演算法中,每一次的劃分所有的樣本都要參與運算,如果數據量非常大的話,這個時間是非常高的,因此有了一種分批處理的改進演算法。
使用Mini Batch(分批處理)的方法對數據點之間的距離進行計算。
Mini Batch的好處:不必使用所有的數據樣本,而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少,所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。
聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集,每個子集成為一個「簇」。通過這樣的劃分,每個簇可能對應於一些潛在的概念(也就是類別);需說明的是,這些概念對聚類演算法而言事先是未知的,聚類過程僅能自動形成簇結構,簇對應的概念語義由使用者來把握和命名。
聚類是無監督的學習演算法,分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集(也就是說提前知道訓練集里的數據屬於哪個類別),機器學習演算法在訓練集上學習到相應的參數,構建模型,然後應用到測試集上。而聚類演算法是沒有標簽的,聚類的時候,需要實現的目標只是把相似的東西聚到一起。
聚類的目的是把相似的樣本聚到一起,而將不相似的樣本分開,類似於「物以類聚」,很直觀的想法是同一個簇中的相似度要盡可能高,而簇與簇之間的相似度要盡可能的低。
性能度量大概可分為兩類: 一是外部指標, 二是內部指標 。
外部指標:將聚類結果和某個「參考模型」進行比較。
內部指標:不利用任何參考模型,直接考察聚類結果。
對於給定的樣本集,按照樣本之間的距離大小,將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起,而讓簇間的距離盡量的大
初學者會很容易就把K-Means和KNN搞混,其實兩者的差別還是很大的。
K-Means是無監督學習的聚類演算法,沒有樣本輸出;而KNN是監督學習的分類演算法,有對應的類別輸出。KNN基本不需要訓練,對測試集裡面的點,只需要找到在訓練集中最近的k個點,用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程,找到k個類別的最佳質心,從而決定樣本的簇類別。
當然,兩者也有一些相似點,兩個演算法都包含一個過程,即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。
優點:
簡單, 易於理解和實現 ;收斂快,一般僅需5-10次迭代即可,高效
缺點:
1,對K值得選取把握不同對結果有很大的不同
2,對於初始點的選取敏感,不同的隨機初始點得到的聚類結果可能完全不同
3,對於不是凸的數據集比較難收斂
4,對噪點過於敏感,因為演算法是根據基於均值的
5,結果不一定是全局最優,只能保證局部最優
6,對球形簇的分組效果較好,對非球型簇、不同尺寸、不同密度的簇分組效果不好。
K-means演算法簡單理解,易於實現(局部最優),卻會有對初始點、雜訊點敏感等問題;還容易和監督學習的分類演算法KNN混淆。
參考閱讀:
1.《 深入理解K-Means聚類演算法 》
2.《 K-Means 》
3. 用於數據挖掘的聚類演算法有哪些,各有何優勢
聚類方法的分類,主要分為層次化聚類演算法,劃分式聚類演算法,基於密度的聚類演算法,基於網格的聚類演算法,基於模型的聚類演算法等。
而衡量聚類演算法優劣的標准主要是這幾個方面:處理大的數據集的能力;處理任意形狀,包括有間隙的嵌套的數據的能力;演算法處理的結果與數據輸入的順序是否相關,也就是說演算法是否獨立於數據輸入順序;處理數據雜訊的能力;是否需要預先知道聚類個數,是否需要用戶給出領域知識;演算法處理有很多屬性數據的能力,也就是對數據維數是否敏感。
.聚類演算法主要有兩種演算法,一種是自下而上法(bottom-up),一種是自上而下法(top-down)。這兩種路徑本質上各有優勢,主要看實際應用的時候要根據數據適用於哪一種,Hierarchical methods中比較新的演算法有BIRCH主要是在數據體量很大的時候使用;ROCK優勢在於異常數據抗干擾性強……
關於數據挖掘的相關學習,推薦CDA數據師的相關課程,課程以項目調動學員數據挖掘實用能力的場景式教學為主,在講師設計的業務場景下由講師不斷提出業務問題,再由學員循序漸進思考並操作解決問題的過程中,幫助學員掌握真正過硬的解決業務問題的數據挖掘能力。這種教學方式能夠引發學員的獨立思考及主觀能動性,學員掌握的技能知識可以快速轉化為自身能夠靈活應用的技能,在面對不同場景時能夠自由發揮。點擊預約免費試聽課。
4. 四種聚類方法之比較
四種聚類方法之比較
介紹了較為常見的k-means、層次聚類、SOM、FCM等四種聚類演算法,闡述了各自的原理和使用步驟,利用國際通用測試數據集IRIS對這些演算法進行了驗證和比較。結果顯示對該測試類型數據,FCM和k-means都具有較高的准確度,層次聚類准確度最差,而SOM則耗時最長。
關鍵詞:聚類演算法;k-means;層次聚類;SOM;FCM
聚類分析是一種重要的人類行為,早在孩提時代,一個人就通過不斷改進下意識中的聚類模式來學會如何區分貓狗、動物植物。目前在許多領域都得到了廣泛的研究和成功的應用,如用於模式識別、數據分析、圖像處理、市場研究、客戶分割、Web文檔分類等[1]。
聚類就是按照某個特定標准(如距離准則)把一個數據集分割成不同的類或簇,使得同一個簇內的數據對象的相似性盡可能大,同時不在同一個簇中的數據對象的差異性也盡可能地大。即聚類後同一類的數據盡可能聚集到一起,不同數據盡量分離。
聚類技術[2]正在蓬勃發展,對此有貢獻的研究領域包括數據挖掘、統計學、機器學習、空間資料庫技術、生物學以及市場營銷等。各種聚類方法也被不斷提出和改進,而不同的方法適合於不同類型的數據,因此對各種聚類方法、聚類效果的比較成為值得研究的課題。
1 聚類演算法的分類
目前,有大量的聚類演算法[3]。而對於具體應用,聚類演算法的選擇取決於數據的類型、聚類的目的。如果聚類分析被用作描述或探查的工具,可以對同樣的數據嘗試多種演算法,以發現數據可能揭示的結果。
主要的聚類演算法可以劃分為如下幾類:劃分方法、層次方法、基於密度的方法、基於網格的方法以及基於模型的方法[4-6]。
每一類中都存在著得到廣泛應用的演算法,例如:劃分方法中的k-means[7]聚類演算法、層次方法中的凝聚型層次聚類演算法[8]、基於模型方法中的神經網路[9]聚類演算法等。
目前,聚類問題的研究不僅僅局限於上述的硬聚類,即每一個數據只能被歸為一類,模糊聚類[10]也是聚類分析中研究較為廣泛的一個分支。模糊聚類通過隸屬函數來確定每個數據隸屬於各個簇的程度,而不是將一個數據對象硬性地歸類到某一簇中。目前已有很多關於模糊聚類的演算法被提出,如著名的FCM演算法等。
本文主要對k-means聚類演算法、凝聚型層次聚類演算法、神經網路聚類演算法之SOM,以及模糊聚類的FCM演算法通過通用測試數據集進行聚類效果的比較和分析。
2 四種常用聚類演算法研究
2.1 k-means聚類演算法
k-means是劃分方法中較經典的聚類演算法之一。由於該演算法的效率高,所以在對大規模數據進行聚類時被廣泛應用。目前,許多演算法均圍繞著該演算法進行擴展和改進。
k-means演算法以k為參數,把n個對象分成k個簇,使簇內具有較高的相似度,而簇間的相似度較低。k-means演算法的處理過程如下:首先,隨機地選擇k個對象,每個對象初始地代表了一個簇的平均值或中心;對剩餘的每個對象,根據其與各簇中心的距離,將它賦給最近的簇;然後重新計算每個簇的平均值。這個過程不斷重復,直到准則函數收斂。通常,採用平方誤差准則,其定義如下:
這里E是資料庫中所有對象的平方誤差的總和,p是空間中的點,mi是簇Ci的平均值[9]。該目標函數使生成的簇盡可能緊湊獨立,使用的距離度量是歐幾里得距離,當然也可以用其他距離度量。k-means聚類演算法的演算法流程如下:
輸入:包含n個對象的資料庫和簇的數目k;
輸出:k個簇,使平方誤差准則最小。
步驟:
(1) 任意選擇k個對象作為初始的簇中心;
(2) repeat;
(3) 根據簇中對象的平均值,將每個對象(重新)賦予最類似的簇;
(4) 更新簇的平均值,即計算每個簇中對象的平均值;
(5) until不再發生變化。
2.2 層次聚類演算法
根據層次分解的順序是自底向上的還是自上向下的,層次聚類演算法分為凝聚的層次聚類演算法和分裂的層次聚類演算法。
凝聚型層次聚類的策略是先將每個對象作為一個簇,然後合並這些原子簇為越來越大的簇,直到所有對象都在一個簇中,或者某個終結條件被滿足。絕大多數層次聚類屬於凝聚型層次聚類,它們只是在簇間相似度的定義上有所不同。四種廣泛採用的簇間距離度量方法如下:
這里給出採用最小距離的凝聚層次聚類演算法流程:
(1) 將每個對象看作一類,計算兩兩之間的最小距離;
(2) 將距離最小的兩個類合並成一個新類;
(3) 重新計算新類與所有類之間的距離;
(4) 重復(2)、(3),直到所有類最後合並成一類。
2.3 SOM聚類演算法
SOM神經網路[11]是由芬蘭神經網路專家Kohonen教授提出的,該演算法假設在輸入對象中存在一些拓撲結構或順序,可以實現從輸入空間(n維)到輸出平面(2維)的降維映射,其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。
SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量,輸出層由一系列組織在2維網格上的有序節點構成,輸入節點與輸出節點通過權重向量連接。學習過程中,找到與之距離最短的輸出層單元,即獲勝單元,對其更新。同時,將鄰近區域的權值更新,使輸出節點保持輸入向量的拓撲特徵。
演算法流程:
(1) 網路初始化,對輸出層每個節點權重賦初值;
(2) 將輸入樣本中隨機選取輸入向量,找到與輸入向量距離最小的權重向量;
(3) 定義獲勝單元,在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏;
(4) 提供新樣本、進行訓練;
(5) 收縮鄰域半徑、減小學習率、重復,直到小於允許值,輸出聚類結果。
2.4 FCM聚類演算法
1965年美國加州大學柏克萊分校的扎德教授第一次提出了『集合』的概念。經過十多年的發展,模糊集合理論漸漸被應用到各個實際應用方面。為克服非此即彼的分類缺點,出現了以模糊集合論為數學基礎的聚類分析。用模糊數學的方法進行聚類分析,就是模糊聚類分析[12]。
FCM演算法是一種以隸屬度來確定每個數據點屬於某個聚類程度的演算法。該聚類演算法是傳統硬聚類演算法的一種改進。
演算法流程:
(1) 標准化數據矩陣;
(2) 建立模糊相似矩陣,初始化隸屬矩陣;
(3) 演算法開始迭代,直到目標函數收斂到極小值;
(4) 根據迭代結果,由最後的隸屬矩陣確定數據所屬的類,顯示最後的聚類結果。
3 四種聚類演算法試驗
3.1 試驗數據
實驗中,選取專門用於測試分類、聚類演算法的國際通用的UCI資料庫中的IRIS[13]數據集,IRIS數據集包含150個樣本數據,分別取自三種不同的鶯尾屬植物setosa、versicolor和virginica的花朵樣本,每個數據含有4個屬性,即萼片長度、萼片寬度、花瓣長度,單位為cm。在數據集上執行不同的聚類演算法,可以得到不同精度的聚類結果。
3.2 試驗結果說明
文中基於前面所述各演算法原理及演算法流程,用matlab進行編程運算,得到表1所示聚類結果。
如表1所示,對於四種聚類演算法,按三方面進行比較:(1)聚錯樣本數:總的聚錯的樣本數,即各類中聚錯的樣本數的和;(2)運行時間:即聚類整個過程所耗費的時間,單位為s;(3)平均准確度:設原數據集有k個類,用ci表示第i類,ni為ci中樣本的個數,mi為聚類正確的個數,則mi/ni為第i類中的精度,則平均精度為:
3.3 試驗結果分析
四種聚類演算法中,在運行時間及准確度方面綜合考慮,k-means和FCM相對優於其他。但是,各個演算法還是存在固定缺點:k-means聚類演算法的初始點選擇不穩定,是隨機選取的,這就引起聚類結果的不穩定,本實驗中雖是經過多次實驗取的平均值,但是具體初始點的選擇方法還需進一步研究;層次聚類雖然不需要確定分類數,但是一旦一個分裂或者合並被執行,就不能修正,聚類質量受限制;FCM對初始聚類中心敏感,需要人為確定聚類數,容易陷入局部最優解;SOM與實際大腦處理有很強的理論聯系。但是處理時間較長,需要進一步研究使其適應大型資料庫。
聚類分析因其在許多領域的成功應用而展現出誘人的應用前景,除經典聚類演算法外,各種新的聚類方法正被不斷被提出。
5. 分類和聚類的區別及各自的常見演算法
1、分類和聚類的區別:
Classification (分類),對於一個classifier,通常需要你告訴它「這個東西被分為某某類」這樣一些例子,理想情況下,一個 classifier 會從它得到的訓練集中進行「學習」,從而具備對未知數據進行分類的能力,這種提供訓練數據的過程通常叫做supervised learning (監督學習),
Clustering (聚類),簡單地說就是把相似的東西分到一組,聚類的時候,我們並不關心某一類是什麼,我們需要實現的目標只是把相似的東西聚到一起。因此,一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了,因此 clustering 通常並不需要使用訓練數據進行學習,這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類,簡單來說,就是根據文本的特徵或屬性,劃分到已有的類別中。如在自然語言處理NLP中,我們經常提到的文本分類便就是一個分類問題,一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括:決策樹分類法,樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器,神經網路法,k-最近鄰法(k-nearestneighbor,kNN),模糊分類法等等。
分類作為一種監督學習方法,要求必須事先明確知道各個類別的信息,並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足,尤其是在處理海量數據的時候,如果通過預處理使得數據滿足分類演算法的要求,則代價非常大,這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然,除此之外,還有很多諸如屬於劃分法K中心點(K-MEDOIDS)演算法、CLARANS演算法;屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等;基於密度的方法:DBSCAN演算法、OPTICS演算法、DENCLUE演算法等;基於網格的方法:STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法;基於模型的方法)。
6. 分類和聚類的區別及各自的常見演算法
1、分類和聚類的區別:
Classification (分類),對於一個classifier,通常需要你告訴它「這個東西被分為某某類」這樣一些例子,理想情況下,一個 classifier 會從它得到的訓練集中進行「學習」,從而具備對未知數據進行分類的能力,這種提供訓練數據的過程通常叫做supervised learning (監督學習),
Clustering (聚類),簡單地說就是把相似的東西分到一組,聚類的時候,我們並不關心某一類是什麼,我們需要實現的目標只是把相似的東西聚到一起。因此,一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了,因此 clustering 通常並不需要使用訓練數據進行學習,這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類,簡單來說,就是根據文本的特徵或屬性,劃分到已有的類別中。如在自然語言處理NLP中,我們經常提到的文本分類便就是一個分類問題,一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括:決策樹分類法,樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器,神經網路法,k-最近鄰法(k-nearestneighbor,kNN),模糊分類法等等。
分類作為一種監督學習方法,要求必須事先明確知道各個類別的信息,並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足,尤其是在處理海量數據的時候,如果通過預處理使得數據滿足分類演算法的要求,則代價非常大,這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然,除此之外,還有很多諸如屬於劃分法K中心點(K-MEDOIDS)演算法、CLARANS演算法;屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等;基於密度的方法:DBSCAN演算法、OPTICS演算法、DENCLUE演算法等;基於網格的方法:STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法;基於模型的方法)。
7. 常用的聚類方法有哪幾種
聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。
1、劃分法,給定一個有N個元組或者紀錄的數據集,分裂法將構造K個分組,每一個分組就代表一個聚類,K<N。
2、層次法,這種方法對給定的數據集進行層次似的分解,直到某種條件滿足為止。
3、基於密度的方法,基於密度的方法與其它方法的一個根本區別是:它不是基於各種各樣的距離的,而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。
4、圖論聚類方法解決的第一步是建立與問題相適應的圖,圖的節點對應於被分析數據的最小單元,圖的邊(或弧)對應於最小處理單元數據之間的相似性度量。
5、基於網格的方法,這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。
6、基於模型的方法,基於模型的方法給每一個聚類假定一個模型,然後去尋找能夠很好的滿足這個模型的數據集。
(7)聚類演算法比較擴展閱讀:
在商業上,聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來,並且概括出每一類消費者的消費模式或者說習慣。
它作為數據挖掘中的一個模塊,可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息,並且概括出每一類的特點,或者把注意力放在某一個特定的類上以作進一步的分析;並且,聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。
許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好;但是,一個大規模資料庫可能包含幾百萬個對象,在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。
許多聚類演算法在聚類分析中要求用戶輸入一定的參數,例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定,特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔,也使得聚類的質量難以控制。