聚類分析原理及步驟

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

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

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

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

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

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

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