聚類分析原理及步驟.doc

聚類分析原理及步驟將未知數(shù)據(jù)按相似程度分類到不同的類或簇的過程1 傳統(tǒng)的統(tǒng)計聚類分析方法包括系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。采用k-均值、k-中心點等算法的聚類分析工具已被加入到許多著名的統(tǒng)計分析軟件包中，如SPSS、SAS等。典型應(yīng)用1 動植物分類和對基因進(jìn)行分類2 在網(wǎng)上進(jìn)行文檔歸類來修復(fù)信息3 幫助電子商務(wù)的用戶了解自己的客戶，向客戶提供更合適 的服務(wù)主要步驟1 數(shù)據(jù)預(yù)處理選擇數(shù)量，類型和特征的標(biāo)度（依據(jù)特征選擇和抽?。┨卣鬟x擇選擇重要的特征，特征抽取把輸入的特征轉(zhuǎn)化為一個新的顯著特征，它們經(jīng)常被用來獲取一個合適的特征集來為避免“維數(shù)災(zāi)”進(jìn)行聚類）和將孤立點移出數(shù)據(jù)（孤立點是不依附于一般數(shù)據(jù)行為或模型的數(shù)據(jù)）2 為衡量數(shù)據(jù)點間的相似度定義一個距離函數(shù)既然相類似性是定義一個類的基礎(chǔ)，那么不同數(shù)據(jù)之間在同一個特征空間相似度的衡量對于聚類步驟是很重要的，由于特征類型和特征標(biāo)度的多樣性，距離度量必須謹(jǐn)慎，它經(jīng)常依賴于應(yīng)用，例如，通常通過定義在特征空間的距離度量來評估不同對象的相異性，很多距離度都應(yīng)用在一些不同的領(lǐng)域一個簡單的距離度量，如Euclidean距離，經(jīng)常被用作反映不同數(shù)據(jù)間的相異性，一些有關(guān)相似性的度量，例如PMC和SMC，能夠被用來特征化不同數(shù)據(jù)的概念相似性，在圖像聚類上，子圖圖像的誤差更正能夠被用來衡量兩個圖形的相似性3 聚類或分組將數(shù)據(jù)對象分到不同的類中【劃分方法（劃分方法一般從初始劃分和最優(yōu)化一個聚類標(biāo)準(zhǔn)開始 ，Crisp Clustering和Fuzzy Clusterin是劃分方法的兩個主要技術(shù)，Crisp Clustering，它的每一個數(shù)據(jù)都屬于單獨的類；Fuzzy Clustering，它的每個數(shù)據(jù)可能在任何一個類中）和層次方法（基于某個標(biāo)準(zhǔn)產(chǎn)生一個嵌套的劃分系列，它可以度量不同類之間的相似性或一個類的可分離性用來合并和分裂類）是聚類分析的兩個主要方法，另外還有基于密度的聚類，基于模型的聚類，基于網(wǎng)格的聚類】4 評估輸出評估聚類結(jié)果的質(zhì)量（它是通過一個類有效索引來評價，一般來說，幾何性質(zhì)，包括類間的分離和類內(nèi)部的耦合，一般都用來評價聚類結(jié)果的質(zhì)量，類有效索引在決定類的數(shù)目時經(jīng)常扮演了一個重要角色，類有效索引的最佳值被期望從真實的類數(shù)目中獲取，一個通常的決定類數(shù)目的方法是選擇一個特定的類有效索引的最佳值，這個索引能否真實的得出類的數(shù)目是判斷該索引是否有效的標(biāo)準(zhǔn)，很多已經(jīng)存在的標(biāo)準(zhǔn)對于相互分離的類數(shù)據(jù)集合都能得出很好的結(jié)果，但是對于復(fù)雜的數(shù)據(jù)集，卻通常行不通，例如，對于交疊類的集合。）聚類分析的主要計算方法原理及步驟劃分法1 將數(shù)據(jù)集分割成K個組（每個組至少包含一個數(shù)據(jù)且每一個數(shù)據(jù)紀(jì)錄屬于且僅屬于一個分組），每個組成為一類2 通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好（標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的紀(jì)錄越遠(yuǎn)越好，使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法）層次法1“自底向上”方案將每個數(shù)據(jù)單獨作為一組，通過反復(fù)迭代的方法，把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止，代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等2“自頂向下”方案主要算法原理及步驟 K-MEANS算法 k-means 算法接受輸入量 k ；然后將n個數(shù)據(jù)對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進(jìn)行計算的。 k-means 算法的工作過程說明如下：1從n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；2計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測度函數(shù). k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。K-MEDOIDS算法K-MEANS有其缺點：產(chǎn)生類的大小相差不會很大，對于臟數(shù)據(jù)很敏感。 改進(jìn)的算法：kmedoids 方法：選取一個對象叫做mediod來代替上面的中心的作用，這樣的一個medoid就標(biāo)識了這個類。步驟： （1）、任意選取K個對象作為medoids（O1,O2,OiOk）。 以下是循環(huán)的： （2）、將余下的對象分到各個類中去（根據(jù)與medoid最相近的原則）； （3）、對于每個類（Oi）中，順序選取一個Or，計算用Or代替Oi后的消耗E（Or）。選擇E最小的那個Or來代替Oi。這樣K個medoids就改變了，下面就再轉(zhuǎn)到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算法得到相應(yīng)的（O1,O2OiOk），然后在這當(dāng)中選取E最小的一個作為最終的結(jié)果。Clarans算法 Clara算法的效率取決于采樣的大小，一般不太可能得到最佳的結(jié)果在Clara算法的基礎(chǔ)上，又提出了Clarans的算法，與Clara算法不同的是：在Clara算法尋找最佳的medoids的過程中，采樣都是不變的。而Clarans算法在每一次循環(huán)的過程中所采用的采樣都是不一樣的。與上次課所講的尋找最佳medoids的過程不同的是，必須人為地來限定循環(huán)的次數(shù)