劃分聚類演算法
⑴ 數據挖掘干貨總結(四)--聚類演算法
本文共計2680字,預計閱讀時長七分鍾
聚類演算法
一 、 本質
將數據劃分到不同的類里,使相似的數據在同一類里,不相似的數據在不同類里
二 、 分類演算法用來解決什麼問題
文本聚類、圖像聚類和商品聚類,便於發現規律,以解決數據稀疏問題
三 、 聚類演算法基礎知識
1. 層次聚類 vs 非層次聚類
– 不同類之間有無包含關系
2. 硬聚類 vs 軟聚類
– 硬聚類:每個對象只屬於一個類
– 軟聚類:每個對象以某個概率屬於每個類
3. 用向量表示對象
– 每個對象用一個向量表示,可以視為高維空間的一個點
– 所有對象形成數據空間(矩陣)
– 相似度計算:Cosine、點積、質心距離
4. 用矩陣列出對象之間的距離、相似度
5. 用字典保存上述矩陣(節省空間)
D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}
6. 評價方法
– 內部評價法(Internal Evalution):
• 沒有外部標准,非監督式
• 同類是否相似,跨類是否相異
DB值越小聚類效果越好,反之,越不好
– 外部評價法(External Evalution):
• 准確度(accuracy): (C11+C22) / (C11 + C12 + C21 + C22)
• 精度(Precision): C11 / (C11 + C21 )
• 召回(Recall): C11 / (C11 + C12 )
• F值(F-measure):
β表示對精度P的重視程度,越大越重視,默認設置為1,即變成了F值,F較高時則能說明聚類效果較好。
四 、 有哪些聚類演算法
主要分為 層次化聚類演算法 , 劃分式聚類演算法 , 基於密度的聚類演算法 , 基於網格的聚類演算法 , 基於模型的聚類演算法等 。
4.1 層次化聚類演算法
又稱樹聚類演算法,透過一種層次架構方式,反復將數據進行分裂或聚合。典型的有BIRCH演算法,CURE演算法,CHAMELEON演算法,Sequence data rough clustering演算法,Between groups average演算法,Furthest neighbor演算法,Neares neighbor演算法等。
凝聚型層次聚類 :
先將每個對象作為一個簇,然後合並這些原子簇為越來越大的簇,直到所有對象都在一個簇中,或者某個終結條件被滿足。
演算法流程:
1. 將每個對象看作一類,計算兩兩之間的最小距離;
2. 將距離最小的兩個類合並成一個新類;
3. 重新計算新類與所有類之間的距離;
4. 重復2、3,直到所有類最後合並成一類。
特點:
1. 演算法簡單
2. 層次用於概念聚類(生成概念、文檔層次樹)
3. 聚類對象的兩種表示法都適用
4. 處理大小不同的簇
5. 簇選取步驟在樹狀圖生成之後
4.2 劃分式聚類演算法
預先指定聚類數目或聚類中心,反復迭代逐步降低目標函數誤差值直至收斂,得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering,CLARANS等
經典K-means:
演算法流程:
1. 隨機地選擇k個對象,每個對象初始地代表了一個簇的中心;
2. 對剩餘的每個對象,根據其與各簇中心的距離,將它賦給最近的簇;
3. 重新計算每個簇的平均值,更新為新的簇中心;
4. 不斷重復2、3,直到准則函數收斂。
特點:
1.K的選擇
2.中心點的選擇
– 隨機
– 多輪隨機:選擇最小的WCSS
3.優點
– 演算法簡單、有效
– 時間復雜度:O(nkt)
4.缺點
– 不適於處理球面數據
– 密度、大小不同的聚類,受K的限制,難於發現自然的聚類
4.3 基於模型的聚類演算法
為每簇假定了一個模型,尋找數據對給定模型的最佳擬合,同一」類「的數據屬於同一種概率分布,即假設數據是根據潛在的概率分布生成的。主要有基於統計學模型的方法和基於神經網路模型的方法,尤其以基於概率模型的方法居多。一個基於模型的演算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。
SOM 神經網路演算法 :
該演算法假設在輸入對象中存在一些拓撲結構或順序,可以實現從輸入空間(n維)到輸出平面(2維)的降維映射,其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。
SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量,輸出層由一系列組織在2維網格上的有序節點構成,輸入節點與輸出節點通過權重向量連接。學習過程中,找到與之距離最短的輸出層單元,即獲勝單元,對其更新。同時,將鄰近區域的權值更新,使輸出節點保持輸入向量的拓撲特徵。
演算法流程:
1. 網路初始化,對輸出層每個節點權重賦初值;
2. 將輸入樣本中隨機選取輸入向量,找到與輸入向量距離最小的權重向量;
3. 定義獲勝單元,在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏;
4. 提供新樣本、進行訓練;
5. 收縮鄰域半徑、減小學習率、重復,直到小於允許值,輸出聚類結果。
4.4 基於密度聚類演算法
只要鄰近區域的密度(對象或數據點的數目)超過某個閾值,就繼續聚類,擅於解決不規則形狀的聚類問題,廣泛應用於空間信息處理,SGC,GCHL,DBSCAN演算法、OPTICS演算法、DENCLUE演算法。
DBSCAN:
對於集中區域效果較好,為了發現任意形狀的簇,這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域;一種基於高密度連通區域的基於密度的聚類方法,該演算法將具有足夠高密度的區域劃分為簇,並在具有雜訊的空間數據中發現任意形狀的簇。
4.5 基於網格的聚類演算法
基於網格的方法把對象空間量化為有限數目的單元,形成一個網格結構。所有的聚類操作都在這個網格結構(即量化空間)上進行。這種方法的主要優點是它的處理 速度很快,其處理速度獨立於數據對象的數目,只與量化空間中每一維的單元數目有關。但這種演算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的演算法結合使用。代表演算法有STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法等。
⑵ 聚類演算法有哪幾種
聚類分析計算方法主要有: 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中,前兩種演算法是利用統計學定義的距離進行度量。
k-means 演算法的工作過程說明如下:首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象,則根據它們與這些聚類中心的相似度(距離),分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點:各聚類本身盡可能的緊湊,而各聚類之間盡可能的分開。
其流程如下:
(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;
(2)根據每個聚類對象的均值(中心對象),計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;
(3)重新計算每個(有變化)聚類的均值(中心對象);
(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。
優點: 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的,且類與類之間區別明顯時,效果較好。對於處理大數據集,這個演算法是相對可伸縮和高效的,計算的復雜度為 O(NKt),其中N是數據對象的數目,t是迭代的次數。
缺點:
1. K 是事先給定的,但非常難以選定;
2. 初始聚類中心的選擇對聚類結果有較大的影響。
⑶ 聚類演算法有哪些
聚類演算法有:劃分法、層次法、密度演算法、圖論聚類法、網格演算法、模型演算法。
1、劃分法
劃分法(partitioning methods),給定一個有N個元組或者紀錄的數據集,分裂法將構造K個分組,每一個分組就代表一個聚類,K<N。使用這個基本思想的演算法有:K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法。
2、層次法
層次法(hierarchical methods),這種方法對給定的數據集進行層次似的分解,直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。代表演算法有:BIRCH演算法、CURE演算法、CHAMELEON演算法等。
3、密度演算法
基於密度的方法(density-based methods),基於密度的方法與其它方法的一個根本區別是:它不是基於各種各樣的距離的,而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。代表演算法有:DBSCAN演算法、OPTICS演算法、DENCLUE演算法等。
4、圖論聚類法
圖論聚類方法解決的第一步是建立與問題相適應的圖,圖的節點對應於被分析數據的最小單元,圖的邊(或弧)對應於最小處理單元數據之間的相似性度量。因此,每一個最小處理單元數據之間都會有一個度量表達,這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源,因而其主要優點是易於處理局部數據的特性。
5、網格演算法
基於網格的方法(grid-based methods),這種方法首先將數據空間劃分成為有限個單元(cell)的網格結構,所有的處理都是以單個的單元為對象的。代表演算法有:STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法。
6、模型演算法
基於模型的方法(model-based methods),基於模型的方法給每一個聚類假定一個模型,然後去尋找能夠很好的滿足這個模型的數據集。通常有兩種嘗試方向:統計的方案和神經網路的方案。
(3)劃分聚類演算法擴展閱讀:
聚類分析起源於分類學,在古老的分類學中,人們主要依靠經驗和專業知識來實現分類,很少利用數學工具進行定量的分類。隨著人類科學技術的發展,對分類的要求越來越高,以致有時僅憑經驗和專業知識難以確切地進行分類,於是人們逐漸地把數學工具引用到了分類學中,形成了數值分類學,之後又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富,有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。
在商業上,聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來,並且概括出每一類消費者的消費模式或者說習慣。它作為數據挖掘中的一個模塊,可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息,並且概括出每一類的特點,或者把注意力放在某一個特定的類上以作進一步的分析;並且,聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。
⑷ kmeans聚類演算法是什麼
K-means演算法是最為經典的基於劃分的聚類方法,是十大經典數據挖掘演算法之一。K-means演算法的基本思想是:以空間中k個點為中心進行聚類,對最靠近他們的對象歸類。通過迭代的方法,逐次更新各聚類中心的值,直至得到最好的聚類結果。
聚類屬於無監督學習,以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的,也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y,只有特徵x,比如假設宇宙中的星星可以表示成三維空間中的點集。
(4)劃分聚類演算法擴展閱讀:
k個聚類以便使得所獲得的聚類滿足:同一聚類中的對象相似度較高;而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」(引力中心)來進行計算的。
(1)適當選擇c個類的初始中心;
(2)在第k次迭代中,對任意一個樣本,求其到c個中心的距離,將該樣本歸到距離最短的中心所在的類;
(3)利用均值等方法更新該類的中心值;
(4)對於所有的c個聚類中心,如果利用(2)(3)的迭代法更新後,值保持不變,則迭代結束,否則繼續迭代。
⑸ K-Means聚類演算法
所謂聚類演算法是指將一堆沒有標簽的數據自動劃分成幾類的方法,屬於無監督學習方法,這個方法要保證同一類的數據有相似的特徵,如下圖所示:
根據樣本之間的距離或者說是相似性(親疏性),把越相似、差異越小的樣本聚成一類(簇),最後形成多個簇,使同一個簇內部的樣本相似度高,不同簇之間差異性高。
相關概念:
K值 :要得到的簇的個數
質心 :每個簇的均值向量,即向量各維取平均即可
距離量度 :常用歐幾里得距離和餘弦相似度(先標准化)
演算法流程:
1、首先確定一個k值,即我們希望將數據集經過聚類得到k個集合。
2、從數據集中隨機選擇k個數據點作為質心。
3、對數據集中每一個點,計算其與每一個質心的距離(如歐式距離),離哪個質心近,就劃分到那個質心所屬的集合。
4、把所有數據歸好集合後,一共有k個集合。然後重新計算每個集合的質心。
5、如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大,趨於穩定,或者說收斂),我們可以認為聚類已經達到期望的結果,演算法終止。
6、如果新質心和原質心距離變化很大,需要迭代3~5步驟。
K-Means採用的啟發式方式很簡單,用下面一組圖就可以形象的描述:
上圖a表達了初始的數據集,假設k=2。在圖b中,我們隨機選擇了兩個k類所對應的類別質心,即圖中的紅色質心和藍色質心,然後分別求樣本中所有點到這兩個質心的距離,並標記每個樣本的類別為和該樣本距離最小的質心的類別,如圖c所示,經過計算樣本和紅色質心和藍色質心的距離,我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心,如圖d所示,新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程,即將所有點的類別標記為距離最近的質心的類別並求新的質心。最終我們得到的兩個類別如圖f。
坐標系中有六個點:
1、我們分兩組,令K等於2,我們隨機選擇兩個點:P1和P2
2、通過勾股定理計算剩餘點分別到這兩個點的距離:
3、第一次分組後結果:
組A:P1
組B:P2、P3、P4、P5、P6
4、分別計算A組和B組的質心:
A組質心還是P1=(0,0)
B組新的質心坐標為:P哥=((1+3+8+9+10)/5,(2+1+8+10+7)/5)=(6.2,5.6)
5、再次計算每個點到質心的距離:
6、第二次分組結果:
組A:P1、P2、P3
組B:P4、P5、P6
7、再次計算質心:
P哥1=(1.33,1)
P哥2=(9,8.33)
8、再次計算每個點到質心的距離:
9、第三次分組結果:
組A:P1、P2、P3
組B:P4、P5、P6
可以發現,第三次分組結果和第二次分組結果一致,說明已經收斂,聚類結束。
優點:
1、原理比較簡單,實現也是很容易,收斂速度快。
2、當結果簇是密集的,而簇與簇之間區別明顯時, 它的效果較好。
3、主要需要調參的參數僅僅是簇數k。
缺點:
1、K值需要預先給定,很多情況下K值的估計是非常困難的。
2、K-Means演算法對初始選取的質心點是敏感的,不同的隨機種子點得到的聚類結果完全不同 ,對結果影響很大。
3、對噪音和異常點比較的敏感。用來檢測異常值。
4、採用迭代方法, 可能只能得到局部的最優解,而無法得到全局的最優解 。
1、K值怎麼定?
答:分幾類主要取決於個人的經驗與感覺,通常的做法是多嘗試幾個K值,看分成幾類的結果更好解釋,更符合分析目的等。或者可以把各種K值算出的 E 做比較,取最小的 E 的K值。
2、初始的K個質心怎麼選?
答:最常用的方法是隨機選,初始質心的選取對最終聚類結果有影響,因此演算法一定要多執行幾次,哪個結果更reasonable,就用哪個結果。 當然也有一些優化的方法,第一種是選擇彼此距離最遠的點,具體來說就是先選第一個點,然後選離第一個點最遠的當第二個點,然後選第三個點,第三個點到第一、第二兩點的距離之和最小,以此類推。第二種是先根據其他聚類演算法(如層次聚類)得到聚類結果,從結果中每個分類選一個點。
3、關於離群值?
答:離群值就是遠離整體的,非常異常、非常特殊的數據點,在聚類之前應該將這些「極大」「極小」之類的離群數據都去掉,否則會對於聚類的結果有影響。但是,離群值往往自身就很有分析的價值,可以把離群值單獨作為一類來分析。
4、單位要一致!
答:比如X的單位是米,Y也是米,那麼距離算出來的單位還是米,是有意義的。但是如果X是米,Y是噸,用距離公式計算就會出現「米的平方」加上「噸的平方」再開平方,最後算出的東西沒有數學意義,這就有問題了。
5、標准化
答:如果數據中X整體都比較小,比如都是1到10之間的數,Y很大,比如都是1000以上的數,那麼,在計算距離的時候Y起到的作用就比X大很多,X對於距離的影響幾乎可以忽略,這也有問題。因此,如果K-Means聚類中選擇歐幾里德距離計算距離,數據集又出現了上面所述的情況,就一定要進行數據的標准化(normalization),即將數據按比例縮放,使之落入一個小的特定區間。
參考文章: 聚類、K-Means、例子、細節
⑹ 空間聚類演算法簡述
空間數據聚類演算法主要包括四大類:(1)給予劃分的聚類;(2)基於層次的聚類;(3)基於密度的聚類;(4)基於網格的聚類。時空數據聚類演算法是空間數據聚類演算法的驗身,它將時許維度納入聚類計算中。
1.1基於劃分的空間聚類演算法
k-means演算法 :用戶定義k個簇的質心位置——將每個數據點聚合到與之最近的質心所在的簇——重新為每個簇計算質心所在位置——重復步驟二和三直到質心收斂。其計算復雜度為 ,T為步驟四中迭代次數,他對於用戶給定的簇中心點的初始位置和雜訊點非常敏感。同時,在處理海量數據的時候運行時間較長。
1.2基於層次的空間聚類演算法
層次聚的目的是將數據對象分配到一個層次結構中,它遵循兩種劇本策略:向上凝聚和向下分裂。向上凝聚方法將每一個對象看做獨立的簇,然後從整個層次結構的底層開始對具有相似特徵的簇聚合,逐層遞歸至頂層。相反,向下分裂方法把所有的數據對象看做同一個簇,然後從整個層次結構的頂層開始,對具有不同特徵的簇進行分裂,逐層遞歸至底層。其計算的事件復雜度是
1.3基於密度的空間聚類演算法
基於茄豎密度的聚類演算法在發現任意形狀和數據造成方面具有獨特的優勢,且不要求對簇的數量進行初始設置。其演算法包括:DBSCAN演算法,OPTICS演算法,DENCLUE演算法,CURD演算法,Incremental DBSCAN演算法,SDBDC演算法,ST-DBSCAN演算法等。DBSCAN是第一個被提出的基於密度的聚類演算法。而密度主要通過兩個基本參數進行定義:空間半徑 和密度閾值MinPts.
DBSCAN基本概念:
演算法的主要缺點是它的運算時間復 ,因此對海量空間數據的聚類過程需要經過一個無法忍受的耗時。它的另一個缺陷是無法支持多密度聚類埋枝、增量聚類和並行計算。許多工作針對這些問題進行了研究他們可以被概括為兩大類工彎納敏作:⑴演算法改進;(2)演算法並行化。傳統的改進方法採用空間索引技術來快速鎖定數據對象。GirDBSCAN被稱為最先進的DBSCAN演算法它基於網格劃分策略極大的減低了演算法的時間復雜度,且沒有計算精度損失。得益於網格的超規則空間結構,任意兩個格子之間的最短空間距離可以很容易被獲取。對於任意點 ,其關於 的近鄰點只存在於一個固定的格子集合范圍內;換言之,那些格子集合范圍外的點一定不是其的近鄰點,因此這些點與點 之間的距離計算可以被省略,從而提高DBSCAN演算法的計算效率。基於這個想法,Gunawan將整個網格劃分為以 為邊長的正方形格子,用於2維空間數據的基於密度聚類計算,使得每個正方格子內的最大空間距離為因此一旦格子內的點的數量達到或超過MinPts,則該格子里的所有點都是核心點,且屬於同一個簇。因此一個簇可以通過密度相連格子和密度可達格子的最大集合進行計算,從而省略了許多點與點之間的距離計算。同時採用了Voronoi圖技術,進一步改進了DBSCAN演算法的運算效率。但是,構建一個Voronoi圖本身需要消耗大量的時間。基於這個想法,Gan和Tao提出了一種關於p近似DBSCAN演算法來獲得近似精度的計算結果,但只需要關於N的線性計算時間,用於取代傳統的DBSCAN演算法。
1.4基於網格的聚類
基於網格聚類演算法將數據空間劃分為規則的互不相交的格子,再將所有的數據對象映射帶網格中基於格子進行聚類。總結一下就是:將對象空間量化為有限數目的單元,形成一個網狀結構,所有聚類都在這個網狀結構上進行。
我們將學習一下STING演算法以及CLIQUE演算法。
⑺ 層次聚類方法的典型演算法分別是
層次聚類方法的典型演算法分別是:
1、凝聚的層次聚類:
AGNES演算法(AGglomerative NESting):採用自底向上爛前閉的策略。最初將每個對象作為一個簇,然後這些簇根據某些准則被一步一步合並, 兩個簇間的距離可以由這兩個不同簇中距離最近的數據點飢裂的相似度來確定;聚類的合並過程反復進行直到所有的對象滿足簇數目。凝聚類的用的比較多一些。
層次聚類
層次聚類試圖在不同悔汪層次對數據集進行劃分,從而形成樹形的聚類結構。數據集劃分可採用「自底向上」的聚合策略,也可採用「自頂向下」的分拆策略。層次聚類是另一種主要的聚類方法,它具有一些十分必要的特性使得它成為廣泛應用的聚類方法。
它生成一系列嵌套的聚類樹來完成聚類。單點聚類處在樹的最底層,在樹的頂層有一個根節點聚類。根節點聚類覆蓋了全部的所有數據點。
⑻ 常用的聚類方法有哪幾種
聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。
1、劃分法,給定一個有N個元組或者紀錄的數據集,分裂法將構造K個分組,每一個分組就代表一個聚類,K<N。
2、層次法,這種方法對給定的數據集進行層次似的分解,直到某種條件滿足為止。
3、基於密度的方法,基於密度的方法與其它方法的一個根本區別是:它不是基於各種各樣的距離的,而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。
4、圖論聚類方法解決的第一步是建立與問題相適應的圖,圖的節點對應於被分析數據的最小單元,圖的邊(或弧)對應於最小處理單元數據之間的相似性度量。
5、基於網格的方法,這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。
6、基於模型的方法,基於模型的方法給每一個聚類假定一個模型,然後去尋找能夠很好的滿足這個模型的數據集。
(8)劃分聚類演算法擴展閱讀:
在商業上,聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來,並且概括出每一類消費者的消費模式或者說習慣。
它作為數據挖掘中的一個模塊,可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息,並且概括出每一類的特點,或者把注意力放在某一個特定的類上以作進一步的分析;並且,聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。
許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好;但是,一個大規模資料庫可能包含幾百萬個對象,在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。
許多聚類演算法在聚類分析中要求用戶輸入一定的參數,例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定,特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔,也使得聚類的質量難以控制。