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

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

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

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

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

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

6、在檢測(cè)集C和D上進(jìn)行聚類，方法與在A,B集進(jìn)行的聚類過(guò)程相同，考察在A,B集上 的幾種聚類方案，看哪種聚類方案在檢測(cè)集C,D上也滿足 ，則這個(gè)聚類是要找的最優(yōu)的聚類方案。0c0c當(dāng)找不到當(dāng)找不到 時(shí)怎么辦？時(shí)怎么辦？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è)施的國(guó)家（地區(qū)）聚類分析 按

7、照信息基礎(chǔ)設(shè)施的發(fā)展現(xiàn)狀，對(duì)世界的20個(gè)國(guó)家（地區(qū)進(jìn)行聚類），信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r的屬性（變量）又六個(gè)，（1）CALL每千人擁有的電話線長(zhǎng)度；（2）MOVECALL-每千戶居民蜂窩移動(dòng)電話數(shù)；（3）FEE-高峰時(shí)期每三分鐘國(guó)際電話的成本；（4）COMPUTER-每千人擁有的計(jì)算機(jī)數(shù)；（5）MIPS-每千人中計(jì)算機(jī)的功率;(6)NET-每千人互聯(lián)網(wǎng)絡(luò)戶主數(shù)。各國(guó)（地區(qū)）信息基礎(chǔ)設(shè)施的發(fā)展?fàn)顩r數(shù)據(jù)見(jiàn)下表：聚類步驟如下：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時(shí)，都有 ，哪個(gè)是最優(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上沒(méi)有出現(xiàn)一個(gè) 為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)行檢測(cè)，k=4時(shí)， =3；k=3時(shí)， =2，k=2時(shí)， =1，k=2時(shí) 的值最小，因此最優(yōu)的聚類方案分兩類ccccc 第一類：10,12,13,14,15,16,17,18,11,即巴西，墨西哥，俄羅斯，波蘭，匈牙利，馬來(lái)西亞，泰國(guó)，智利和印度。這一類轉(zhuǎn)型的國(guó)家和亞洲以及拉美的發(fā)展中國(guó)家，這些國(guó)家經(jīng)濟(jì)較不發(fā)達(dá)，基礎(chǔ)設(shè)施較薄弱，基于信息基礎(chǔ)設(shè)施較落后的國(guó)家。第二類：8,9,3,19,20,7,6,4,5,2,1，即中國(guó)臺(tái)灣，韓國(guó)，德國(guó)，法國(guó)，英國(guó)，新加坡