聚類分析原理及步驟

1、聚類分析原理及步驟1傳統(tǒng)的統(tǒng)計聚類分析方法包括系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。采用k-均值、k-中心點等算法的聚類分析工具已被加入到許多著名 的統(tǒng)計分析軟件包中，如SPSS SAS等典型應用1動植物分類和對基因進行分類2在網(wǎng)上進行文檔歸類來修復信息3幫助電子商務的用戶了解自己的客戶，向客戶提供更合適的服務主要步驟1 數(shù)據(jù)預處理一一選擇數(shù)量，類型和特征的標度（依據(jù)特征選擇和抽取）特征選擇選擇重要的特征，特征抽取把輸入的特征轉化 為一個新的顯著特征，它們經常被用來獲取一個合適的特征集來為避免“維數(shù)災”進行聚類 ）和將孤立點移出數(shù)據(jù)（ 孤立點是不依附于一

2、 般數(shù)據(jù)行為或模型的數(shù)據(jù) ）2為衡量數(shù)據(jù)點間的相似度定義一個距離函數(shù)既然相類似性是定義一個類的基礎，那么不同數(shù)據(jù)之間在同一個特 征空間相似度的衡量對于聚類步驟是很重要的，由于特征類型和特 征標度的多樣性，距離度量必須謹慎，它經常依賴于應用，例如， 通常通過定義在特征空間的距離度量來評估不同對象的相異性，很 多距離度都應用在一些不同的領域一個簡單的距離度量，如Euclidean距離，經常被用作反映不同數(shù)據(jù)間的相異性，一些有關 相似性的度量，例如PMC和SMC能夠被用來特征化不同數(shù)據(jù)的概 念相似性，在圖像聚類上，子圖圖像的誤差更正能夠被用來衡量兩 個圖形的相似性3聚類或分組一一將數(shù)據(jù)對象分到不同的

3、類中【劃分方法（劃分方法一般從初始劃分和最優(yōu)化一個聚類標準開始，Cris pClustering 和口 Fuzzy Clusterin 是劃分方法的兩個主要技術， Crisp Clusteri ng ，它的每一個數(shù)據(jù)都屬于單獨的類；Fuzzy Clusteri ng ，基于密度的聚類，基于模型的聚類，基于網(wǎng)格的聚類】4 評估輸出 評估聚類結果的質量（它是通過一個類有效索引來 評價，一般來說，幾何性質，包括類間的分離和類內部的耦合，一般 都用來評價聚類結果的質量，類有效索引在決定類的數(shù)目時經常扮演 了一個重要角色，類有效索引的最佳值被期望從真實的類數(shù)目中獲取， 一個通常的決定類數(shù)目的方法是選擇一

4、個特定的類有效索引的最佳 值，這個索引能否真實的得出類的數(shù)目是判斷該索引是否有效的標準， 很多已經存在的標準對于相互分離的類數(shù)據(jù)集合都能得出很好的結 果，但是對于復雜的數(shù)據(jù)集，卻通常行不通，例如，對于交疊類的集 合。）聚類分析的主要計算方法原理及步驟劃分法1將數(shù)據(jù)集分割成K個組（每個組至少包含一個數(shù)據(jù)且每一個數(shù)據(jù)紀錄屬于且 僅屬于一個分組），每個組成為一類2通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次 好（標準就是：同一分組中的記錄越近 越好，而不同分組中的紀錄越遠越好，使用這個基本思想的算法有：K-MEANS算法、K-MEDOID算法、CLARAN算法）層次法1“自底向

5、上”方案一一將每個數(shù)據(jù)單獨作為 一組，通過反復迭代的方法，把那些相互鄰近 的組合并成一個組，直到所有的記錄組成一個 分組或者某個條件滿足為止，代表算法有：BIRCH算法、CUR算法、chameleon法2“自頂向下”方案主要算法原理及步驟K-MEANS算 法k-means算法接受輸入量k ;然后將n個數(shù)據(jù)對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相 似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。k-means算法的工作過程說明如下：1從n個數(shù)據(jù)對象任意選擇 k個對象作為初始聚 類中心；而對于所剩下其它

6、對象，則根據(jù)它們與這些聚類中 心的相似度（距離），分別將它們分配給與其最相似的（聚 類中心所代表的）聚類；2計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值) ；不斷重復這一過程直到標準測度函數(shù)開始 收斂為止。一般都采用均方差作為標準測度函數(shù) .k 個聚類具有以下特點：各聚類本身盡可能的緊 湊，而各聚類之間盡可能的分開。K-MEDOIDS算法K-MEANS有其缺點：產生類的大小相差不會很大，對 于臟數(shù)據(jù)很敏感。改進的算法：k medoids 方法：選取一個對象叫做 mediod 來代替上面的中心的作 用，這樣的一個 medoid 就標識了這個類。步驟：(1)、任意選取 K個對象作為 med

7、oids (01,02，Oi -Ok)o以下是循環(huán)的：( 2)、將余下的對象分到各個類中去(根據(jù)與medoid 最相近的原則) ；(3)、對于每個類( 0i)中，順序選取一個Or,計算用Or代替Oi后的消耗 E (Or)o選擇E最小的那個Or來代替Oi。這樣 K 個 medoids 就改變了，下面就再轉到 2。( 4)、這樣循環(huán)直到 K 個 medoids 固定下來。 這 種算法對于臟數(shù)據(jù)和異常數(shù)據(jù)不敏感， 但計算量顯 然要比 K 均值要大，一般只適合小數(shù)據(jù)量Clara 算法K-medoids 算法不適合于大數(shù)據(jù)量的計算， Clara 算法 的思想就是用實際數(shù)據(jù)的抽樣來代替整個數(shù)據(jù)，然后再在這 些抽樣的數(shù)據(jù)上利用 K-medoids 算法得到最佳的 medoids 。 Clara 算法從實際數(shù)據(jù)中抽取多個采樣，在每個采樣上都用 K-medoids算法得到相應的(O1,O2Oi-Ok),然后在這當 中選取E最小的一個作為最終的結果。Clarans 算法Clara 算法的效率取決于采樣的大小， 一般不太可能得 到最佳的結果在 Clara 算法的基礎上，又提出了 Clarans 的算法， 與 Clara 算法不同的是：在 Clara 算法尋找最佳的 m