【正文】 歐氏空間的一個(gè)點(diǎn)，則聚類(lèi)分析問(wèn)題可歸結(jié)為給p 維空間中n 個(gè)點(diǎn)作出一種恰當(dāng)?shù)姆诸?lèi)方法。樣品距離：設(shè) n 個(gè)樣品，每個(gè)樣品測(cè)得p 項(xiàng)指標(biāo)，樣本數(shù)據(jù)陣為：待考察的任意兩個(gè)樣品間的距離可定義為 p 維空間兩個(gè)點(diǎn)之間的距離。常用的距離有：Ⅰ，明考夫斯基（Minkowski）距離Ⅱ，蘭氏距離（Lance 和Villians）? ? ? ? ???? ? ? ? ???n n npppx x xx x xx x x,......,....,. ...,....,...,...1, 221 , 22 211 , 12 133Ⅲ，斜交空間距離Ⅳ，馬氏距離類(lèi)：設(shè) T 為預(yù)先給定的閥值，樣品集合G 中任意的兩個(gè)樣品Xi 與Xj 間的距離為Dij，如果DijT，則稱(chēng)G 為一個(gè)類(lèi)。類(lèi)間距離：針對(duì)不同的問(wèn)題，類(lèi)的定義和形式不盡相同，故類(lèi)與類(lèi)之間的距離也多種多樣，主要有：最短距離法、最長(zhǎng)距離法、重心法、類(lèi)平均法、離差平方和法等（詳見(jiàn)文獻(xiàn)[34]）。5．2．3 系統(tǒng)聚類(lèi)基本思想是，先將n 個(gè)樣品各自看成一類(lèi)，然后計(jì)算各類(lèi)兩兩之間的距離，選擇其中距離最小的兩類(lèi)合并成一個(gè)新類(lèi)，于是n 類(lèi)樣品就聚成n1 類(lèi)，計(jì)算這一新類(lèi)與其他各類(lèi)之間的距離，再合并其中距離最小的兩類(lèi)，如此反復(fù)進(jìn)行，每次減少一類(lèi)，直到所有樣品歸為一類(lèi)。根據(jù)類(lèi)之間距離的不同定義，可以有不同的系統(tǒng)聚類(lèi)法，可以把這些不同的聚類(lèi)算法統(tǒng)一起來(lái)，這種統(tǒng)一關(guān)鍵在于不同距離定義的統(tǒng)一，有如下的遞推公式：設(shè) Gp 類(lèi)和Gq 類(lèi)合并為新類(lèi)Gr，則上式中的Dir 就是新類(lèi)與任意類(lèi)Gi 間的距離。上式中系數(shù)取不同值，就可以得到不同的距離公式（見(jiàn)文獻(xiàn)[34]）。算法實(shí)現(xiàn)：假設(shè)對(duì)含有 p 個(gè)指標(biāo)的n 個(gè)樣品進(jìn)行聚類(lèi)：input: n 個(gè)樣品間的距離陣a[n][n]，期望結(jié)果的類(lèi)別數(shù)koutput: 記錄最終聚類(lèi)結(jié)果的二維數(shù)組b[k][n]FUNC Cluster(a[n][n],k)FOR i:=1 TO n DO{b[i][1]:=1。b[i][2]:=i。b[i][3]:=0} //初始化b[n][n]，//將n 個(gè)樣品各自看作一類(lèi)m=nWHILE mk DO{a[p][q]=min(a[1..m][1..m])；//確定p,q,使得第p 類(lèi)和第q 類(lèi)間的距離最小adjust(b[1..m2][1..m2])；//重置類(lèi)別記錄數(shù)組，撤銷(xiāo)第p 類(lèi)和第q 類(lèi)//將第p 類(lèi)與第q 類(lèi)合為一類(lèi)b[m1][1]:=b[p][1]+b[q][1]。Dir ? apDip ? aqDiq ? mDpq ? n Dip ? Diq .........公式（1）34b[m1][2..x]=b[p][2..x]。b[m1][x+1..z]=b[q][2..y]。b[m1][z+1]=0。adjust(a[1..m2][1..m2])；//重置距離陣，撤銷(xiāo)第p 類(lèi)和第q 類(lèi)FOR i:=1 TO m1 DO{a[m1][i]=s1*a[i][p]+s2*a[i][q]+s3*a[p[q]+b4*|a[i][p]a[i][q]|。}//利用公式（1），計(jì)算新類(lèi)與其他各類(lèi)間的距離m:=m1}return(b[1..k][1..n])。ENDF。{Cluster}5．2．4 多重系統(tǒng)聚類(lèi)1．基本原理根據(jù)分類(lèi)對(duì)象的不同，聚類(lèi)分為樣本聚類(lèi)和變量聚類(lèi)，前者稱(chēng)為 Q 型聚類(lèi)分析、后者稱(chēng)為R 型聚類(lèi)分析。上文的系統(tǒng)聚類(lèi)算法關(guān)注的僅是樣本聚類(lèi)，但在實(shí)際中，單純的樣本聚類(lèi)有時(shí)并不準(zhǔn)確，主要原因是忽視了不同指標(biāo)間也存在一定的關(guān)系。因?yàn)榭疾斓慕嵌炔煌?，所以不同指?biāo)對(duì)最終樣本聚類(lèi)結(jié)果會(huì)產(chǎn)生不同的影響，這就導(dǎo)致了結(jié)果的不準(zhǔn)確性，尤其是當(dāng)指標(biāo)個(gè)數(shù)很多時(shí)?？朔@種缺點(diǎn)的途徑之一是先將指標(biāo)按一定的規(guī)則分成若干類(lèi)別，對(duì)包含每一類(lèi)別指標(biāo)的樣本數(shù)據(jù)分別進(jìn)行聚類(lèi)，然后對(duì)聚類(lèi)結(jié)果進(jìn)行二次聚類(lèi)，這種方法就是多重聚類(lèi)?？疾?p 維的歐氏空間：按一定規(guī)則將 p 個(gè)n 維變量分成若干類(lèi)別，每一類(lèi)別的指標(biāo)在實(shí)際中往往有具體的含義，則：這樣，整個(gè) p 維歐氏空間劃分為q 個(gè)多維子空間，對(duì)每一個(gè)Y 分別進(jìn)行系統(tǒng)聚類(lèi)?？梢钥吹剑謩e聚類(lèi)的結(jié)果，仍可以構(gòu)成一個(gè)q 維的歐氏空間，對(duì)這個(gè)包含q 個(gè)二級(jí)指標(biāo)的樣本聚類(lèi)結(jié)果再作一次系統(tǒng)聚類(lèi)，得到最終結(jié)果。（見(jiàn)圖）39。M＝（X1，X 2，X 3，...Xp）其中Xi ?（xi1，xi 2，xi3，...xin）M ?（YY Y3...Yq）其中Yi ? ( Xm。Xk )，并且rmk ? T ,T為某一閥值， rmk為Xm與Xk的相關(guān)系數(shù)352． 算法實(shí)現(xiàn)設(shè)樣品個(gè)數(shù)為 n，每一樣品有p 個(gè)指標(biāo)：input：樣本數(shù)據(jù)矩陣M[n][p]；期望結(jié)果的類(lèi)別數(shù)koutput：記錄最終聚類(lèi)結(jié)果的二維數(shù)組b[k][n]PROC Multi_Cluster（M[n][p],k）按具體含義劃分 p 個(gè)指標(biāo)為q 類(lèi)，即將樣本數(shù)據(jù)的一個(gè)p 維空間映射為q 個(gè)子空間//先對(duì)每個(gè)子空間樣本進(jìn)行聚類(lèi)FOR i:=1 TO q DO{計(jì)算ai[ni][ni]。//對(duì)第i 個(gè)子空間樣本計(jì)算距離陣，ni 為其中指標(biāo)個(gè)數(shù)bi[k][k]:=Cluster(ai[ni][ni],k’)。 //調(diào)用系統(tǒng)聚類(lèi)算法，對(duì)包含某特定指標(biāo)類(lèi)的樣品聚類(lèi),k’為首次聚類(lèi)結(jié)果的類(lèi)別數(shù)}計(jì)算 a0[q][q]。 // a0[q][q]存儲(chǔ)一次聚類(lèi)后的結(jié)果樣本距離陣//對(duì)首次聚類(lèi)結(jié)果進(jìn)行再聚類(lèi)，得到最終結(jié)果b[k][n]=Cluster(a0[q][q],k)ENDP。{Multi_Cluster}3． 幾點(diǎn)考慮首先是子空間劃分的粒度問(wèn)題；多重聚類(lèi)建立在對(duì)包含某一類(lèi)指標(biāo)的樣品分別聚類(lèi)的結(jié)果的基礎(chǔ)上，最后結(jié)果的準(zhǔn)確性與指標(biāo)的劃分是有著直接關(guān)系。因此，關(guān)鍵是對(duì)指標(biāo)的適當(dāng)劃分，但劃分的規(guī)則往往很難確定。在實(shí)際中，具體規(guī)則一般由指標(biāo)的具體含義來(lái)確定。還有一種可能的做法是將每一個(gè)指標(biāo)劃分為一類(lèi)，即p 維的歐氏空間映射為p 個(gè)子空間，這種做法雖然最終的系統(tǒng)聚類(lèi)仍要面對(duì)p 維的歐氏空間，但由于對(duì)每個(gè)樣本來(lái)說(shuō)，其數(shù)據(jù)是反映類(lèi)別的無(wú)12..n..X1 X2 X3X4 ... ... Xpx11 x12 x13 x14 x1px21 x22 x23 x24 x2p... ...... ...xn1 xn2 xn3 xn4 ... ... xnp... ... ... ... ... ... ...... ... ... ... ... ... ...12..n..X1 X2 X3 X4 ... ... Xpx11 x12 x13 x14 x1px21 x22 x23 x24 x2 p... ...... ...xn1 xn2 xn3 xn4 ... ... xnp... ... ... ... ... ... ...... ... ... ... ... ... ...Y1 Y2 Yq ...Y1 Y2 ... Yqn12....12....類(lèi)別np維歐氏空間 q個(gè)歐氏子空間首次聚類(lèi)結(jié)果最終結(jié)果圖 多重系統(tǒng)聚類(lèi)過(guò)程36綱量，這就克服了傳統(tǒng)系統(tǒng)聚類(lèi)的指標(biāo)間的不可衡量性。這兩種劃分方法在實(shí)際應(yīng)用中可根據(jù)具體的問(wèn)題靈活采用，但通過(guò)實(shí)踐驗(yàn)證可以看出，一般情況下，前者更可靠一些。其次是對(duì)首次聚類(lèi)結(jié)果的排序問(wèn)題；因?yàn)槎嘀鼐垲?lèi)的第一步工作是對(duì)包含某類(lèi)指標(biāo)的樣品分別聚類(lèi)，因?yàn)椴煌?lèi)別指標(biāo)的衡量規(guī)則不同，所以聚類(lèi)的結(jié)果往往缺乏一定的可比較性，而下一步聚類(lèi)的就是針對(duì)這個(gè)結(jié)果，因此很有必要找到一種統(tǒng)一的規(guī)則來(lái)對(duì)這個(gè)結(jié)果作一排序。這樣，對(duì)某兩個(gè)特定樣本來(lái)說(shuō)，它們根據(jù)每一指標(biāo)所進(jìn)行的首次聚類(lèi)就有了一定的可比較性，也為下一步的聚類(lèi)提供了前提。5．3 有監(jiān)督分類(lèi)算法— C55．3．1 算法概述C5 屬于一種歸納學(xué)習(xí)算法。歸納學(xué)習(xí)（inductive learning）旨在從大量的經(jīng)驗(yàn)數(shù)據(jù)中歸納抽取一般的判定規(guī)則和模式，它是機(jī)器學(xué)習(xí)（machinelearning）中最核心、最成熟的一個(gè)分支。根據(jù)有無(wú)導(dǎo)師指導(dǎo)，歸納學(xué)習(xí)又分為有導(dǎo)師學(xué)習(xí)（supervised learning，又稱(chēng)為示例學(xué)習(xí)）與無(wú)導(dǎo)師學(xué)習(xí)(unsupervised learning)。C5 屬于有導(dǎo)師學(xué)習(xí)算法。示例學(xué)習(xí)是對(duì)某些概念的正例與反例集合，通過(guò)歸納推理覆蓋所有正例并排除所有反例的概念描述。學(xué)習(xí)算法可分為兩大類(lèi)：覆蓋算法（coveringalgorithms）和分治算法（divideandconquer algorithms）；前者歸納生成規(guī)則，后者歸納生成決策樹(shù)。決策樹(shù)方法是用屬性值對(duì)例子集逐級(jí)劃分，直到一個(gè)節(jié)點(diǎn)僅含有同一類(lèi)的例子為止。它起源于Hunt 等人提出的概念學(xué)習(xí)系統(tǒng)CLS（Concept LearningSystem），然后發(fā)展到Quinlan 的ID3（Interactive Dichotomic version3）算法，最后演化為能處理連續(xù)屬性的C5。決策樹(shù)構(gòu)造的輸入是一組帶有類(lèi)別標(biāo)記的例子，構(gòu)造的結(jié)果是一棵二叉或多叉樹(shù)。二叉樹(shù)的內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）一般表示為一個(gè)邏輯判斷，如形式為(ai=vi)的邏輯判斷，其中ai 是屬性，vi 是該屬性的某個(gè)屬性值；樹(shù)的邊是邏輯判斷的分支結(jié)果。多叉樹(shù)（ID3）的內(nèi)部節(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個(gè)屬性值，就有幾條邊。樹(shù)的葉子節(jié)點(diǎn)都是類(lèi)別標(biāo)記。構(gòu)造決策樹(shù)的方法是采用自上而下的遞歸構(gòu)造。以多叉樹(shù)為例，它的構(gòu)造思路是，如果訓(xùn)練例子集合中的所有例子是同類(lèi)的，則將之作為葉子節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)容即是該類(lèi)別標(biāo)記。否則，根據(jù)某種策略選擇一個(gè)屬性，按照屬性的各個(gè)取值，把例子集合劃分為若干子集合，使得每個(gè)子集上的所有例子在該屬性上37具有同樣的屬性值。然后再依次遞歸處理各個(gè)子集。這種思路實(shí)際上就是“分而治之”（divideandconquer）的道理。二叉樹(shù)同理，差別僅在于要選擇一個(gè)好的邏輯判斷。構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組例子，可以有很多決策樹(shù)能符合這組例子。人們研究出，一般情況下或具有較大概率地說(shuō)，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩浴Ｓ捎跇?gòu)造最小的樹(shù)是NP 難題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩浴Ｔ趯?shí)際中，用于模型學(xué)習(xí)的訓(xùn)練數(shù)據(jù)往往不是完美的，可能是因?yàn)椋孩倌承傩宰侄紊先敝担╩issing values）；②缺少必須的數(shù)據(jù)而造成數(shù)據(jù)不完整；③數(shù)據(jù)不準(zhǔn)確含有噪聲甚至是錯(cuò)誤的。這時(shí)就有克服噪聲和決策樹(shù)剪枝問(wèn)題?；镜臎Q策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練例子擬合。有噪聲情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能。剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。有兩種剪枝策略：向前剪枝（forward pruning）和向后剪枝（backwardpruning）。向前剪枝方法是，在生成樹(shù)的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)； 向后剪枝方法是一種兩階段法： 擬合－ 化簡(jiǎn)（fittingandsimplifying），首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹(shù)，然后從樹(shù)的葉子開(kāi)始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合（tuning set 或adjusting set），如果存在某個(gè)葉子剪去后能使得在測(cè)試集上的準(zhǔn)確度或其它測(cè)度不降低（不變得更壞），則剪去該葉子；否則停機(jī)。值得注意的是，剪枝并不是對(duì)所有的數(shù)據(jù)集都好，就象最小樹(shù)并不是最好（具有最大的預(yù)測(cè)率）的樹(shù)。當(dāng)數(shù)據(jù)稀疏時(shí)，要防止過(guò)分剪枝（overpruning）。從某種意義上講，剪枝也是一種偏向（bias），對(duì)有些數(shù)據(jù)效果好而有的數(shù)據(jù)則效果差。正是由于不同的屬性選擇及剪枝過(guò)程的實(shí)現(xiàn)，才產(chǎn)生了各種不同的歸納學(xué)習(xí)算法。一個(gè)簡(jiǎn)單的決策樹(shù)的例子見(jiàn)下圖（）：38本例根據(jù)加薪百分比、工作時(shí)長(zhǎng)、法定節(jié)假日、及醫(yī)療保險(xiǎn)三個(gè)屬性來(lái)判斷一個(gè)企業(yè)的福利狀況(good 或bad)。下面簡(jiǎn)單介紹幾種決策樹(shù)算法的演進(jìn)：CLS 系統(tǒng)CLS 的工作過(guò)程為：首先找出最有判別力的屬性A，把數(shù)據(jù)分成多個(gè)子集，每個(gè)子集再選擇最有判別力的屬性B 進(jìn)行劃分，一直進(jìn)行到所有子集僅包含同一類(lèi)型的數(shù)據(jù)為止。因此CLS 以一棵空決策樹(shù)開(kāi)始，并通過(guò)增加結(jié)點(diǎn)逐步求精，直到產(chǎn)生一棵能正確分類(lèi)訓(xùn)練例子的決策樹(shù)，這是一個(gè)循環(huán)遞歸過(guò)程：已知訓(xùn)練子集PN，1． 如果PN 中的所有例子均為正例，則生成一個(gè)YES 結(jié)點(diǎn)并終止；如果PN 中的所有例子均為反例，則生成一個(gè)NO 結(jié)點(diǎn)并終止；否則，根據(jù)某種啟發(fā)式策略選擇一個(gè)屬性A，設(shè)A 取值為υ1，υ2… υr，并生成新結(jié)點(diǎn)。2． 將PN 中的例子根據(jù)其屬性A 的取值加以劃分，生成r 個(gè)子集記為PN1,PN2…PNr。3． 遞歸地應(yīng)用該算法到每個(gè)子集PNi。ID3 算法分類(lèi)屬性的選擇決定了算法的效率與所生成的決策樹(shù)的繁簡(jiǎn)程度、預(yù)測(cè)效果。選擇屬性是決策樹(shù)歸納算法的關(guān)鍵。CLS 算法可以產(chǎn)生所有可能的決策樹(shù)，正確分類(lèi)訓(xùn)練實(shí)例，并能選擇最簡(jiǎn)單的決策樹(shù)。但是屬性選擇范圍的不確定，在實(shí)際應(yīng)用中往往受問(wèn)題大小的限制。wage increasefirst yearworkinghoursstatutoryholidayscontribution tohealth pa