基于“三分”法的序貫判別樹

江 梅方積乾

基于“三分”法的序貫判別樹

江 梅1，2方積乾2

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

“三分”法 序貫判別樹 待判域 待判率

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

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

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

原理和方法

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

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

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

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

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

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

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

若m inxij1k≤a1，則判樣品來自第i類；

若maxxi′j1k≥b1，則判樣品來自第i′類；

否則，便待判。

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

若m inxij1k≤a1，則判樣品來自第i類；

若maxxi′j1k≥b1，則判樣品來自第i′類；

否則，便待判。

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

若m inxij1k≤a1，則判樣品來自第i類；

若maxxij1k≥b1，則判樣品來自第i′類；

否則，便待判。

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

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

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

2．計算

分別計算：

3．計算μ（1）和v（1）之比。

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

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

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

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

如果X（2）≤a2時，判斷樣品來自Π1總體；

X（2）≥b2時，判斷樣品來自Π2總體；

a2＜X（2）＜b2時，待判。

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

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

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

模擬研究

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

我們根據(jù)X的各個不同分量之間的相關(guān)性來產(chǎn)生數(shù)據(jù)，選取6個變量，重復(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)的考核樣本，把考核樣本的錯判率Rd作為評價分類效果的指標(biāo)。選取比較常用的判別分析方法Fisher判別，和經(jīng)典的決策樹方法CART，跟序貫判別樹算法的結(jié)果進(jìn)行比較，分別計算各自的實(shí)際平均錯判率。

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

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

2.存在相關(guān)

我們從總體N6（O，∑1）和N6（u2，∑2）隨機(jī)抽取n1＝n2＝500個樣品，μ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)，見表4～6。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.方積乾，楊周南.序貫判別樹在肺癌鑒別診斷中的應(yīng)用.北京醫(yī)學(xué)院學(xué)報，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)計系