基于數(shù)據(jù)分組處理方法的聚類模型

1、基于數(shù)據(jù)分組處理方法的聚類分析模型牛亞旭 信研1401 馬超 信研1402傳統(tǒng)的聚類方法數(shù)據(jù)分組處理聚類分析方法實(shí)例分析 傳統(tǒng)的聚類分析 人類認(rèn)識世界的一種重要方法就是將認(rèn)識的對象進(jìn)行分類，分門別類的對事物進(jìn)行研究，要遠(yuǎn)比在一個混雜多變的集合中更清晰明了和細(xì)致。一、概述 通常，人們可以憑經(jīng)驗(yàn)和專業(yè)知識來實(shí)現(xiàn)分類，而聚類分析作為一種定量方法，從數(shù)據(jù)分析的角度，給出一個更準(zhǔn)確更細(xì)致的分類工具。二、三種聚類方法1、系統(tǒng)聚類 系統(tǒng)聚類法是聚類分析中用得較多的一種方法。 它通過建立、并逐步更新距離系數(shù)矩陣（或相似系數(shù)矩陣），找出并合并最接近的兩類，直到全部分類對象被合并為一類為止。 據(jù)此合并過程，可以做

2、出聚類圖（或稱分群圖、譜系圖），并確定類的個數(shù)和最后聚成的各類。以樣本聚類為例，系統(tǒng)聚類法的工作步驟如下： 計算全部n個樣品兩兩間的距離dij，并構(gòu)成n維距離系數(shù)矩陣D。 將每個樣品作為一類，共構(gòu)成n類。上述的n維矩陣D即為類間的距離系數(shù)矩陣。 由系數(shù)矩陣找出并合并距離最近的類為一新類，于是總的類數(shù)將至少減1。記下參加合并的類的序號與距離。 若只剩下一類了，轉(zhuǎn)至步驟。否則計算新類與當(dāng)前其他各類的距離，調(diào)整系數(shù)矩陣D，然后返回步驟。 根據(jù)步驟中記錄的序號和距離，畫出聚類圖。 確定類的個數(shù)，最后得到所聚成的各類。2、分解聚類法分解聚類法是將類由少變多的聚類法。先把全部個體當(dāng)作一類，然后再分為兩類，

3、三類，直到所有的個體自成一類。3、動態(tài)聚類法動態(tài)聚類法是先將樣品粗略地分一下類，然后再按照某種原則進(jìn)行修正，直至分類比較合理為止。其過程如下圖1所示。圖1 動態(tài)聚類框圖 在上述介紹的三種聚類方法中，系統(tǒng)聚類法和分解聚類法有一個共同點(diǎn)，就是樣品一旦被歸到某個類后就不再變了，這就要求分類的方法比較準(zhǔn)確；而且當(dāng)樣品個數(shù)較大時，相應(yīng)的計算量過大。 而動態(tài)聚類法可彌補(bǔ)它們的不足。 數(shù)據(jù)分組處理（GMDH）聚類分析 與前面提到的通常的聚類方法相比，傳統(tǒng)的聚類方法中關(guān)于劃分方法以及層次的方法這兩個重要因素需要依賴于建模人員的先驗(yàn)知識，因而較多的依賴于建模人員的主觀因素。 客觀聚類分析方法（OCA）能自動、客

4、觀地確定聚類個數(shù)并找到最優(yōu)聚類方案，通過算法步驟的剖析和算例分析，對客觀聚類分析方法的核心構(gòu)建，即一致性準(zhǔn)則的不足進(jìn)行評價，利用偶極子給出了新的一致性準(zhǔn)則，提出了數(shù)據(jù)分組處理（GMDH）聚類分析方法。一、基本原理二、算法實(shí)現(xiàn)2.2 基于偶極子的數(shù)據(jù)樣本分組 從n個數(shù)據(jù)樣本x1,x2,xn可以得到 個偶極子，2.1中dij為該偶極子的值。將它們由小到大排列取前k=n/2個彼此沒有共同樣本的偶極子，將這些偶極子的xi構(gòu)成子集A，樣本xj構(gòu)成子集B，這樣使用偶極子將數(shù)據(jù)樣本集合平均分成兩個子集A和B。 在產(chǎn)生A和B之后，按同樣的方法從剩余的偶極子可得到樣本子集C和D作為檢測集。2nC2.3 進(jìn)行聚類

5、 step1：將子集A和B分別聚為k類； 把產(chǎn)生子集A,B的全體k個偶極子按他們的值從小到大的順序進(jìn)行編號，稱該編號為這個偶極子的編號或其中兩個樣本的編號。Step2：將子集A和B分別聚成k-1類； 分別將子集A和B中距離最近的兩個類聚為一類，則子集A和B都被聚成k-1個類。Step3： 重復(fù)step2，將子集A和B分別聚成k-2個類，注意各子集中類與類之間的距離由兩類中距離最近的樣本間的距離給出。此時集合AUB中仍有k個列 繼續(xù)上述過程，直到將子集A和B聚成兩個類。Step4： 找出所有準(zhǔn)則值 的聚類方案，它們?yōu)樽顑?yōu)聚類方案的候選方案。0c2.4 運(yùn)用檢測集C和D找出一個唯一的最優(yōu)聚類方案

6、在檢測集C和D上進(jìn)行聚類，方法與在A,B集進(jìn)行的聚類過程相同，考察在A,B集上 的幾種聚類方案，看哪種聚類方案在檢測集C,D上也滿足 ，則這個聚類是要找的最優(yōu)的聚類方案。0c0c當(dāng)找不到當(dāng)找不到 時怎么辦？時怎么辦？0c2.新一致性準(zhǔn)則： 假設(shè)集合A,B已分別聚為k類，偶極子總數(shù)為q，集合AUB的偶極子總數(shù)為p，該列與子集的子集形成的類的總數(shù)為r，則有：NMrkNpqMc新準(zhǔn)則 表示需要拆分的偶極子的數(shù)目。NMc 因?yàn)楸疚牡姆椒ㄊ腔谂紭O子的聚類，偶極子被拆分的數(shù)目越少，則聚類結(jié)果越優(yōu)。因此，基于偶極子定義的新準(zhǔn)則 的值越小，聚類方案越優(yōu)。c 實(shí)例研究基于信息基礎(chǔ)設(shè)施的國家（地區(qū)）聚類分析 按

7、照信息基礎(chǔ)設(shè)施的發(fā)展現(xiàn)狀，對世界的20個國家（地區(qū)進(jìn)行聚類），信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r的屬性（變量）又六個，（1）CALL每千人擁有的電話線長度；（2）MOVECALL-每千戶居民蜂窩移動電話數(shù)；（3）FEE-高峰時期每三分鐘國際電話的成本；（4）COMPUTER-每千人擁有的計算機(jī)數(shù)；（5）MIPS-每千人中計算機(jī)的功率;(6)NET-每千人互聯(lián)網(wǎng)絡(luò)戶主數(shù)。各國（地區(qū)）信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r數(shù)據(jù)見下表：聚類步驟如下：1）產(chǎn)生偶極子以及子集A和B 偶極子(12，10),(14，13),(9，8),(19，3),(20，7),(6，4),(18，17),(16，15),(5，2) 樣本子集A=12

8、,14,9,19,20,6,18,16,5 樣本子集B=10,13,8,3,7,4,17,15,22) 按子集A,B用一致性準(zhǔn)則 聚類 下表給出了各聚類方案中 的值，由表可知，除去k=9的情況外，k=4,k=3和k=2時，都有 ，哪個是最優(yōu)方案呢？cc0c3）按子集C,D用一致性準(zhǔn)則 聚類產(chǎn)生集合C,D的偶極子為：(12,11),(10,17),(3,5),(15,14),(18,13),(20,2),(19,8),(16.9),(7.6) 除去k=9的情況外，在集合C,D上沒有出現(xiàn)一個 為0的方案，不能為唯一確定最優(yōu)聚類方案提供補(bǔ)充信息，一致性準(zhǔn)則 失效。ccc4）用新一致性準(zhǔn)則 聚類： 重復(fù)2）3）兩步，但用新一致性準(zhǔn)則，結(jié)果如下表，在集合A,B上得到三種最優(yōu)候選聚類方法：k=4,k=3,k=2,利用聚合C,D進(jìn)行檢測，k=4時， =3；k=3時， =2，k=2時， =1，k=2時 的值最小，因此最優(yōu)的聚類方案分兩類ccccc 第一類：10,12,13,14,15,16,17,18,11,即巴西，墨西哥，俄羅斯，波蘭，匈牙利，馬來西亞，泰國，智利和印度。這一類轉(zhuǎn)型的國家和亞洲以及拉美的發(fā)展中國家，這些國家經(jīng)濟(jì)較不發(fā)達(dá)，基礎(chǔ)設(shè)施較薄弱，基于信息基礎(chǔ)設(shè)施較落后的國家。第二類：8,9,3,19,20,7,6,4,5,2,1，即中國臺灣，韓國，德國，法國，英國，新加坡