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