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

江 梅方積乾

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

江 梅1，2方積乾2

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

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

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

但是目前很多決策樹算法在構建樹時，都是在變量間是相互獨立假設前提下進行的，每個內部節點對應的分割判斷規則只選用一個變量進行劃分，未能充分利用變量間內在聯系所提供的信息。而在實際中類的劃分不僅僅與單屬性有關，往往與一個屬性集有關，因為多個弱特征的組合可能具有很強的分類能力。

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

原理和方法

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

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

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

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

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

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

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

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

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

否則，便待判。

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

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

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

否則，便待判。

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

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

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

否則，便待判。

圖1 根據第一最佳擴展屬性進行“三分”示意圖

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

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

2．計算

分別計算：

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

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

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

圖2 根據第二最佳擴展屬性進行“三分”示意圖

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

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

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

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

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

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

②待定判斷域的樣本量小于子節點的最小樣本量Nmin；

模擬研究

本人使用Delphi獨立開發了一個名為“序貫判別樹”的分類器，能夠實現對訓練樣本集進行分類挖掘，生成一棵決策樹，并利用OLE（對象連接與嵌入）技術和數據庫計數，使得結果和規律可以快速重現，并可進一步對測試樣本進行判別。

我們根據X的各個不同分量之間的相關性來產生數據，選取6個變量，重復200次隨機抽樣，并設置了隨機數種子1～200，把隨機數種子j為奇數而產生的數據集作為訓練樣本，把隨機數種子j＋1而產生的數據集作為相應的考核樣本，把考核樣本的錯判率Rd作為評價分類效果的指標。選取比較常用的判別分析方法Fisher判別，和經典的決策樹方法CART，跟序貫判別樹算法的結果進行比較，分別計算各自的實際平均錯判率。

1.完全不相關

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

2.存在相關

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

表1 完全不相關，μ＝1不同算法結果的比較

表2 完全不相關，μ＝1.5不同算法結果的比較

表3 完全不相關，μ＝2不同算法結果的比較

（1）低相關，見表4～6。

表4 低相關時，μ＝1不同算法結果的比較

表5 低相關時，μ＝1.5不同算法結果的比較

表6 低相關時，μ＝2不同算法結果的比較

（2）中相關，見表7～9。

表7 中相關時，μ＝1不同算法結果的比較

表8 中相關時，μ＝1.5不同算法結果的比較

表9 中相關時，μ＝2不同算法結果的比較

（3）高相關，見表10～12。

表10 高相關時，μ＝1不同算法結果的比較

表11 高相關時，μ＝1.5不同算法結果的比較

表12 高相關時，μ＝2不同算法結果的比較

從上面的比較結果可以得到以下結論：

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

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

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

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

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

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

2.方積乾.序貫判別分析.應用數學學報，1979，2（3）：287-293.

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

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

5.方積乾，楊周南.序貫判別樹在肺癌鑒別診斷中的應用.北京醫學院學報，1983，15（2）：96-99.

（責任編輯：郭海強）

Sequential Decision Tree Based on Trichotom y

Jiang Mei，Fang Jiqian（State Key Laboratory of Respiratory Disease，Guangzhou Institute of Respiratory Diseases，First 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.廣州醫科大學附屬第一醫院廣州呼吸疾病研究所（510120）

2.中山大學公共衛生學院流行病與衛生統計系