聚類分析原理及步驟.doc

《聚類分析原理及步驟.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《聚類分析原理及步驟.doc（5頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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