基于“三分”法的序貫判別樹(shù)

江 梅方積乾

基于“三分”法的序貫判別樹(shù)

江 梅1，2方積乾2

目的構(gòu)建基于“三分”法的序貫判別樹(shù)，并對(duì)算法性能進(jìn)行評(píng)價(jià)。方法將空間分為三個(gè)區(qū)域，落入其中兩個(gè)區(qū)域者作肯定性判斷，否則便待判的“三分”法的思想，構(gòu)建“序貫判別樹(shù)”的分類(lèi)器，并將序貫判別樹(shù)算法的結(jié)果與常用的判別分析方法Fisher判別和經(jīng)典的決策樹(shù)方法CART法進(jìn)行比較，分別計(jì)算訓(xùn)練樣本和考核樣本的實(shí)際平均錯(cuò)判率。結(jié)果序貫判別樹(shù)與Fisher判別和CART法比較發(fā)現(xiàn)，在相同的相關(guān)條件下，隨著可分離程度的增大，三種方法判別效果也越好。從平均變量數(shù)來(lái)看，序貫判別樹(shù)使用變量數(shù)較少，在訓(xùn)練樣本中，序貫判別樹(shù)的錯(cuò)判率為0，并且存在“待判率”一項(xiàng)。而在考核樣本中，序貫判別樹(shù)的正確判別率跟其他兩種方法比較接近，錯(cuò)判率遠(yuǎn)遠(yuǎn)低于其他兩種方法。結(jié)論基于“三分法”的序貫判別樹(shù)的分類(lèi)精度高，變量少。

“三分”法 序貫判別樹(shù) 待判域 待判率

經(jīng)典的判別分析一般要求每個(gè)樣品對(duì)于每個(gè)指標(biāo)都要測(cè)量，這個(gè)要求在有些實(shí)際問(wèn)題中是過(guò)高的。而且判別分析屬于一次判決的分類(lèi)器，將空間一分為二的判別規(guī)則過(guò)于絕對(duì)化，分類(lèi)效果往往不及決策樹(shù)，因?yàn)樵趯?shí)際中，最優(yōu)判決界常常是非線性的。決策樹(shù)多次判別其實(shí)起到了非線性判別的作用，與經(jīng)典的根據(jù)一組變量的取值一次判別的方法相比，既可減少需要觀察的項(xiàng)目又可提高分類(lèi)的準(zhǔn)確性。

但是目前很多決策樹(shù)算法在構(gòu)建樹(shù)時(shí)，都是在變量間是相互獨(dú)立假設(shè)前提下進(jìn)行的，每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)的分割判斷規(guī)則只選用一個(gè)變量進(jìn)行劃分，未能充分利用變量間內(nèi)在聯(lián)系所提供的信息。而在實(shí)際中類(lèi)的劃分不僅僅與單屬性有關(guān)，往往與一個(gè)屬性集有關(guān)，因?yàn)槎鄠€(gè)弱特征的組合可能具有很強(qiáng)的分類(lèi)能力。

為充分發(fā)揮這兩種典型方法的優(yōu)點(diǎn)，克服各自的缺點(diǎn)，我們可以把兩者結(jié)合起來(lái)進(jìn)行分析研究。本文基于Kendall〔1〕（1975）和方積乾〔2-5〕（1979）提出將空間分為三個(gè)區(qū)域，落入其中兩個(gè)區(qū)域者作肯定性判斷，否則便待判的“三分”法的思想，結(jié)合經(jīng)典判別分析中Fisher準(zhǔn)則充分利用變量間內(nèi)在聯(lián)系建立線性判別函數(shù)進(jìn)行判別的優(yōu)點(diǎn)，和決策樹(shù)序貫地進(jìn)行判別的優(yōu)點(diǎn)，提出一種基于“三分法”的序貫判別樹(shù)算法。模擬實(shí)驗(yàn)和實(shí)例表明，該算法的分類(lèi)精度高，可以得到精簡(jiǎn)的復(fù)合規(guī)則。

原理和方法

假設(shè)現(xiàn)有一個(gè)訓(xùn)練集T，從兩總體∏1和∏2中隨機(jī)獲得，其中非類(lèi)別屬性Xi均是連續(xù)型變量，類(lèi)別屬性C＝｛1，2｝。令T中樣品屬性的取值記為xijk，其中i＝1，2表示兩種類(lèi)別；j＝1，2，…，p表示屬性序號(hào)；k＝1，2，…，ni表示樣品序號(hào)。事先規(guī)定λ0≥0，和子節(jié)點(diǎn)的最小樣本量Nmin，作為終止程序的閾值。具體算法如下：

第1步：對(duì)于每個(gè)非類(lèi)別屬性Xj，計(jì)算類(lèi)別間離差平方和與類(lèi)別內(nèi)離差平方和之比（簡(jiǎn)稱(chēng)差方比），選擇差方比最大的非類(lèi)別屬性Xj作為第一個(gè)最佳擴(kuò)展屬性。

第2步：對(duì)于選出來(lái)的第一最佳擴(kuò)展屬性X（1）＝Xj1，利用“三分法”思想將空間分為三個(gè)區(qū)域，兩類(lèi)別樣本的重疊部分作待判域，其他兩個(gè)區(qū)域作判別域（如圖1所示）。

制定“三分”的兩個(gè)臨界值有很多種方法，這里我們將在方積乾教授原有的方法上改進(jìn)：將兩類(lèi)別樣本的重疊部分適當(dāng)放寬后作為待判域，放寬的標(biāo)準(zhǔn)為重疊部分所在區(qū)間的5%（或1%）。

對(duì)于選出來(lái)的第一最佳擴(kuò)展屬性X（1）＝Xj1，分別計(jì)算：

令｜d-c｜×5%＝e（或｜d-c｜×1%＝e），

我們可以制定如下判別規(guī)則R（1）：

若m inxij1k≤a1，則判樣品來(lái)自第i類(lèi)；

若maxxi′j1k≥b1，則判樣品來(lái)自第i′類(lèi)；

否則，便待判。

我們可以制定如下判別規(guī)則R（1）：

若m inxij1k≤a1，則判樣品來(lái)自第i類(lèi)；

若maxxi′j1k≥b1，則判樣品來(lái)自第i′類(lèi)；

否則，便待判。

我們可以制定如下判別規(guī)則R（1）：

若m inxij1k≤a1，則判樣品來(lái)自第i類(lèi)；

若maxxij1k≥b1，則判樣品來(lái)自第i′類(lèi)；

否則，便待判。

圖1 根據(jù)第一最佳擴(kuò)展屬性進(jìn)行“三分”示意圖

第3步：對(duì)于待判域，引進(jìn)第二個(gè)擴(kuò)展屬性，跟第一個(gè)最佳擴(kuò)展屬性線性組合，使得差方比最大，則將該線性組合作為第二最佳擴(kuò)展屬性。

上標(biāo)（1）表示通過(guò)對(duì)第一次分割之后刪余樣本進(jìn)行計(jì)算得到的值，k＝0表示第一個(gè)最佳分割屬性，l＝1，2，…，p且l≠j1表示除了第一個(gè)分割屬性外的第j個(gè)屬性。

2．計(jì)算

分別計(jì)算：

3．計(jì)算μ（1）和v（1）之比。

通過(guò)以上計(jì)算，引進(jìn)新變量Xj2，它和第一最佳擴(kuò)展屬性X（1）線性組合，產(chǎn)生第二個(gè)最佳擴(kuò)展屬性X（2）＝μ（1）X（1）＋v（1）Xj2。

第4步：對(duì)于選出來(lái)的第二最佳擴(kuò)展屬性X（2），利用“三分法”思想將空間分為三個(gè)區(qū)域，兩類(lèi)別樣本的重疊部分作待判域，其他兩個(gè)區(qū)域作判別域（圖2）。

圖2 根據(jù)第二最佳擴(kuò)展屬性進(jìn)行“三分”示意圖

類(lèi)似第2步方法確定相應(yīng)的臨界值a2和b2，可以得到判別規(guī)則R（2）：

如果X（2）≤a2時(shí)，判斷樣品來(lái)自Π1總體；

X（2）≥b2時(shí)，判斷樣品來(lái)自Π2總體；

a2＜X（2）＜b2時(shí)，待判。

第5步：重復(fù)第3和第4步，逐漸引進(jìn)其他屬性，跟上一步的最佳擴(kuò)展屬性作線性組合，選擇使差方比最大的線性組合作為新的最佳擴(kuò)展屬性，然后利用“三分”法進(jìn)行判別，直到滿足以下條件，就停止迭代過(guò)程，該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，不標(biāo)記任何類(lèi)別。

①差方比小于給定的閾值λ0；

②待定判斷域的樣本量小于子節(jié)點(diǎn)的最小樣本量Nmin；

模擬研究

本人使用Delphi獨(dú)立開(kāi)發(fā)了一個(gè)名為“序貫判別樹(shù)”的分類(lèi)器，能夠?qū)崿F(xiàn)對(duì)訓(xùn)練樣本集進(jìn)行分類(lèi)挖掘，生成一棵決策樹(shù)，并利用OLE（對(duì)象連接與嵌入）技術(shù)和數(shù)據(jù)庫(kù)計(jì)數(shù)，使得結(jié)果和規(guī)律可以快速重現(xiàn)，并可進(jìn)一步對(duì)測(cè)試樣本進(jìn)行判別。

我們根據(jù)X的各個(gè)不同分量之間的相關(guān)性來(lái)產(chǎn)生數(shù)據(jù)，選取6個(gè)變量，重復(fù)200次隨機(jī)抽樣，并設(shè)置了隨機(jī)數(shù)種子1～200，把隨機(jī)數(shù)種子j為奇數(shù)而產(chǎn)生的數(shù)據(jù)集作為訓(xùn)練樣本，把隨機(jī)數(shù)種子j＋1而產(chǎn)生的數(shù)據(jù)集作為相應(yīng)的考核樣本，把考核樣本的錯(cuò)判率Rd作為評(píng)價(jià)分類(lèi)效果的指標(biāo)。選取比較常用的判別分析方法Fisher判別，和經(jīng)典的決策樹(shù)方法CART，跟序貫判別樹(shù)算法的結(jié)果進(jìn)行比較，分別計(jì)算各自的實(shí)際平均錯(cuò)判率。

1.完全不相關(guān)

我們從總體N6（O，I）和N6（u2，λI）隨機(jī)抽取n1＝n2＝500個(gè)樣品，λ＝2，μ2＝（μ，μ-0.5，μ＋0.5，0，0，0），具體結(jié)果見(jiàn)表1～3。

2.存在相關(guān)

我們從總體N6（O，∑1）和N6（u2，∑2）隨機(jī)抽取n1＝n2＝500個(gè)樣品，μ2＝（μ，μ-0.5，μ＋0.5，0，0，0），具體結(jié)果如下：

表1 完全不相關(guān)，μ＝1不同算法結(jié)果的比較

表2 完全不相關(guān)，μ＝1.5不同算法結(jié)果的比較

表3 完全不相關(guān)，μ＝2不同算法結(jié)果的比較

（1）低相關(guān)，見(jiàn)表4～6。

表4 低相關(guān)時(shí)，μ＝1不同算法結(jié)果的比較

表5 低相關(guān)時(shí)，μ＝1.5不同算法結(jié)果的比較

表6 低相關(guān)時(shí)，μ＝2不同算法結(jié)果的比較

（2）中相關(guān)，見(jiàn)表7～9。

表7 中相關(guān)時(shí)，μ＝1不同算法結(jié)果的比較

表8 中相關(guān)時(shí)，μ＝1.5不同算法結(jié)果的比較

表9 中相關(guān)時(shí)，μ＝2不同算法結(jié)果的比較

（3）高相關(guān)，見(jiàn)表10～12。

表10 高相關(guān)時(shí)，μ＝1不同算法結(jié)果的比較

表11 高相關(guān)時(shí)，μ＝1.5不同算法結(jié)果的比較

表12 高相關(guān)時(shí)，μ＝2不同算法結(jié)果的比較

從上面的比較結(jié)果可以得到以下結(jié)論：

（1）用μ＝1，1.5，2來(lái)表示兩總體可分離程度，在相同的相關(guān)條件下，隨著可分離程度的增大，三種方法判別效果也越來(lái)越好。當(dāng)可分離性較小（μ＝1）時(shí)，重疊區(qū)域比較大，因此序貫判別樹(shù)面臨較多無(wú)法判決的第三類(lèi)，待判率也相應(yīng)高些，三種方法的判別效果都不是很好，錯(cuò)判率相差比較大。而當(dāng)可分離性較大（μ＝2）時(shí)，三種方法錯(cuò)判率彼此接近。

（2）當(dāng)變量間相關(guān)程度不高時(shí)（包括不相關(guān)和低相關(guān)），從訓(xùn)練樣本和考核樣本來(lái)看：三種方法之中一般以Fisher判別的錯(cuò)判率最高，分類(lèi)效果不及決策樹(shù)，但隨著總體分離程度的增大，三種方法正確率越來(lái)越接近。說(shuō)明兩總體可分離程度較小時(shí)，重疊區(qū)域比較大，如果用屬于一次判決的判別分析去判別，由于判別分析的判別規(guī)則是將空間一分為二，過(guò)于絕對(duì)化，會(huì)導(dǎo)致錯(cuò)判率較高。實(shí)際上最優(yōu)判決界往往是非線性的，而決策樹(shù)的多次判別起到了非線性判別的作用，所以判別效果比較好。

（3）當(dāng)變量間相關(guān)程度增高時(shí)（包括中相關(guān)和高相關(guān)），對(duì)于訓(xùn)練樣本來(lái)說(shuō)，F(xiàn)isher判別的錯(cuò)判率越來(lái)越低，越接近另外兩種決策樹(shù)方法。這主要在于Fisher判別充分利用變量間內(nèi)在相關(guān)聯(lián)系，使得預(yù)測(cè)準(zhǔn)確率有所提高。雖然這時(shí)Fisher判別的錯(cuò)判率比CART算法略高一些，但是從考核樣本來(lái)看，CART算法的錯(cuò)判率卻遠(yuǎn)比Fisher判別高。這是因?yàn)镃ART算法在構(gòu)建樹(shù)時(shí)要求變量間是相對(duì)獨(dú)立的，而在實(shí)際中有些變量之間存在一定相關(guān)性，很難滿足這個(gè)前提，從而降低預(yù)測(cè)準(zhǔn)確率。CART算法每次只選用一個(gè)變量進(jìn)行劃分，未能充分利用變量間內(nèi)在聯(lián)系所提供的信息，因此要用很多次分支才能近似將它分成小長(zhǎng)方形，這樣容易導(dǎo)致訓(xùn)練過(guò)度。即決策樹(shù)生長(zhǎng)太“枝繁葉茂”，節(jié)點(diǎn)個(gè)數(shù)過(guò)多，每個(gè)節(jié)點(diǎn)所包含的實(shí)例個(gè)數(shù)太小，不便于作出合理的統(tǒng)計(jì)學(xué)推斷，實(shí)際解釋時(shí)也沒(méi)有足夠的說(shuō)服力，不但會(huì)降低樹(shù)的可理解性和可用性，同時(shí)也使決策樹(shù)本身對(duì)歷史數(shù)據(jù)的依賴(lài)性增大，考核時(shí)預(yù)測(cè)準(zhǔn)確率會(huì)下降很多。

（4）從平均變量數(shù)來(lái)看，雖然Fisher判別用了逐步判別來(lái)篩選變量，但是使用變量數(shù)均比另外兩種決策樹(shù)方法多。說(shuō)明決策樹(shù)方法按照一定規(guī)則序貫地引用變量進(jìn)行判決，在能作判斷時(shí)就不需要測(cè)量其他變量了。這樣既可減少需要觀察的項(xiàng)目，又可以提高效率。

（5）在訓(xùn)練樣本中，序貫判別樹(shù)的錯(cuò)判率為0，并且存在“待判率”一項(xiàng)。這是因?yàn)樾蜇炁袆e樹(shù)運(yùn)用“三分”法思想進(jìn)行判別。序貫判別樹(shù)算法寧愿將最后一次“三分”落入待判域這部分樣品判為“待判”，等待引入其他新的信息再下結(jié)論，也不愿意去冒比較大的誤判風(fēng)險(xiǎn)進(jìn)行判決。我們也嘗試通過(guò)改變每次判決的界值（5%或1%）來(lái)觀察待判率和錯(cuò)判率的變化，發(fā)現(xiàn)在考核樣本中隨著改變界值的百分比越大，待判率和錯(cuò)判率也隨之增加，但是錯(cuò)判率增加不如待判率多。雖然在訓(xùn)練樣本中序貫判別樹(shù)的正確判別率并不是總比其他兩種方法高，但是錯(cuò)判率為0，遠(yuǎn)遠(yuǎn)低過(guò)其他兩種方法。而在考核樣本中，序貫判別樹(shù)的正確判別率跟其他兩種方法比較接近，甚至比它們還高，錯(cuò)判率遠(yuǎn)遠(yuǎn)低于其他兩種方法。由此可看出：“三分法”的好處是使那些在兩類(lèi)邊界附近的樣品不至于由于某種偶然的，微小的變化而引起截然不同的判決和分類(lèi)，可以使得生成的決策樹(shù)更加穩(wěn)定。

1.Kendall MG.Multivariate analysis.Charles Griffin＆Co，1975.

2.方積乾.序貫判別分析.應(yīng)用數(shù)學(xué)學(xué)報(bào)，1979，2（3）：287-293.

3.方積乾，楊周南.多母體離散型序貫判別樹(shù)及其應(yīng)用.數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，1980，1（1）：8-15.

4.方積乾，王紀(jì)憲，周宗燦，等.預(yù)測(cè)致癌性的遺傳毒理學(xué)試驗(yàn)組合的選擇和序貫判別方法.北京醫(yī)科大學(xué)學(xué)報(bào)，1990，22（6）：421-424.

5.方積乾，楊周南.序貫判別樹(shù)在肺癌鑒別診斷中的應(yīng)用.北京醫(yī)學(xué)院學(xué)報(bào)，1983，15（2）：96-99.

（責(zé)任編輯：郭海強(qiáng)）

Sequential Decision Tree Based on Trichotom y

Jiang Mei，F(xiàn)ang Jiqian（State Key Laboratory of Respiratory Disease，Guangzhou Institute of Respiratory Diseases，F(xiàn)irst Affiliated Hospital of Guangzhou Medical University（510120），Guangzhou）

ObjectiveTo construct a sequential decision tree algorithm based on and trichotomy，and evaluate the performance of the algorithm.MethodsSequential Decision tree was founded by the concept of Kendall（1975）and JiQian Fang（1979），which is to divide the space into three regions，and if case is in two regions then make affirmative decision，otherw isemake itwait to be decided.The classification results of sequential decision tree algorithm in simulation experiments were compared w ith Fisher＇s discrim inate analysis method and classical CART decision treemethod，through calculation of actual averagem isclassification rate in training and testing dataset.ResultsItwas discovered that the judgment effectwas associated w ith increasement of separable degree in the same relevant conditions in all threemethods（sequential decision tree，CART tree and Fisher′s discrim inate analysis）.From the average number of variables used，the sequential decision tree use least variables in all threemethods，m isjudged rate of sequential decision tree was 0 in all training dataset，and there is an option of“to be sentenced Rate”in sequential decision tree.The accuracy of classification of sequential decision tree was close to the other two methods w ith lower m isclassification rate in the testing dataset.ConclusionClassification by sequential decision tree based on trichotomy was better in accuracy and less variable using.

Sequential decision tree；Multivariate normal distribution；Trichotomy；Likelihood ratio；M isclassification rate

1.廣州醫(yī)科大學(xué)附屬第一醫(yī)院廣州呼吸疾病研究所（510120）

2.中山大學(xué)公共衛(wèi)生學(xué)院流行病與衛(wèi)生統(tǒng)計(jì)系