變精度鄰域等價(jià)粒的鄰域決策樹構(gòu)造算法

謝 鑫，張賢勇*，王旋曄，唐鵬飛

（1.四川師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，成都 610068；2.四川師范大學(xué)智能信息與量子信息研究所，成都 610068）

0 引言

粗糙集［1］是處理不確定性理論的重要工具，廣泛應(yīng)用于人工智能、數(shù)據(jù)挖掘、決策分析等領(lǐng)域［2-5］。經(jīng)典粗糙集主要使用等價(jià)關(guān)系劃分粒結(jié)構(gòu)，因此更適合于處理離散性數(shù)據(jù)，在處理連續(xù)性數(shù)據(jù)時(shí)往往需要進(jìn)行數(shù)據(jù)預(yù)處理，也就是對(duì)數(shù)據(jù)離散化，這將導(dǎo)致部分信息缺失。為了解決這個(gè)問題，粗糙集理論被擴(kuò)展為鄰域粗糙集理論［6-7］。鄰域粗糙集引入了鄰域關(guān)系和鄰域決策信息系統(tǒng)，對(duì)鄰域信息粒子進(jìn)行鄰域粒化和粗糙逼近，擴(kuò)大了粗糙集理論的應(yīng)用范圍。鄰域決策信息系統(tǒng)是鄰域粗糙集理論構(gòu)建的基本形式背景，其上的不確定性度量和樣本分類體系構(gòu)建值得被探討。

分類算法對(duì)于數(shù)據(jù)分析具有重要的意義，決策樹是導(dǎo)出決策規(guī)則的一種常用分類方法。決策樹算法具有分類速度快、精度高、規(guī)則簡(jiǎn)單易懂等優(yōu)點(diǎn)，因此其相關(guān)的歸納算法和知識(shí)發(fā)現(xiàn)在機(jī)器學(xué)習(xí)中有著廣泛的研究和應(yīng)用［8-13］。經(jīng)典的決策樹算法包括基于基尼指數(shù)的決策樹算法CART（Classification And Regression Tree）、基于信息熵的決策樹算法ID3（Iterative Dichotomiser 3）、基于信息增益率的決策樹（C4.5）算法等。CART 算法是一種經(jīng)典的算法，每個(gè)節(jié)點(diǎn)的劃分按照能減少的雜質(zhì)的量來進(jìn)行排序，雜質(zhì)度量方法常用Gini 指標(biāo)［14］。ID3 算法同樣是一種經(jīng)典的決策樹算法［15］，它主要以信息增益為節(jié)點(diǎn)生成的屬性度量準(zhǔn)則，以屬性上的等價(jià)關(guān)系為節(jié)點(diǎn)分裂規(guī)則，表現(xiàn)出了較好的樣本分類效果，但只能處理離散型數(shù)據(jù)。在ID3 算法基礎(chǔ)上，可以處理連續(xù)型數(shù)據(jù)的C4.5 算法［16］被Quinlan 提出。不同于ID3 算法，信息增益率被用作C4.5 算法節(jié)點(diǎn)生成的度量準(zhǔn)則。CART 算法和ID3 算法兩種傳統(tǒng)的決策樹生成算法利用了信息論中的信息測(cè)度，C4.5 算法在處理連續(xù)型數(shù)據(jù)過程中要對(duì)數(shù)據(jù)進(jìn)行離散化，這增加了算法的時(shí)間復(fù)雜度和空間復(fù)雜度，并且可能造成決策信息系統(tǒng)的信息丟失，不利于樣本分類。

為了克服決策樹構(gòu)造算法在面對(duì)連續(xù)型數(shù)據(jù)表現(xiàn)出的信息丟失、算法準(zhǔn)確度不高等缺點(diǎn)，鄰域決策信息系統(tǒng)上的決策樹構(gòu)造算法首次被提出。鄰域決策信息系統(tǒng)具有其信息粒結(jié)構(gòu)表示的獨(dú)特性，因此，鄰域等價(jià)粒被探討，進(jìn)而變精度鄰域等價(jià)粒被挖掘。基尼指數(shù)被擴(kuò)展至變精度鄰域等價(jià)粒結(jié)構(gòu)上，建立鄰域基尼指數(shù)不確定性度量，并探討度量的相關(guān)性質(zhì)。最后，基于鄰域基尼指數(shù)度量構(gòu)造決策樹啟發(fā)式算法，采用來源于UCI 的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，統(tǒng)計(jì)了決策樹算法的準(zhǔn)確度和葉子數(shù)等指標(biāo)，與經(jīng)典的CART 算法、ID3 算法、C4.5 算法以及最新文獻(xiàn)［17］中融合信息增益和基尼指數(shù)IGGI（combining Information Gain and Gini Index）算法作對(duì)比分析。

1 基本知識(shí)

L=(U，C∪D，V，f)為一個(gè)決策信息系統(tǒng)，常簡(jiǎn)記為決策表DT=(U，C∪D)。其中：U表示有限非空樣本全集；C={a1，a2，…，a|C|}表示有限非空條件屬性全集；D表示決策屬性；V=表示屬性值的集合，Vc表示屬性c的屬性值范圍，即屬性c的值域；f：U×B→V(B?C)表示一個(gè)信息函數(shù)。

1.1 鄰域決策信息系統(tǒng)

經(jīng)典粗糙集理論建立于等價(jià)關(guān)系基礎(chǔ)上，對(duì)具有連續(xù)值信息系統(tǒng)進(jìn)行信息的不確定性度量和對(duì)數(shù)據(jù)做特征選擇時(shí)，往往需要離散化，這將造成信息的丟失，鄰域粗糙集理論的探討具有意義［5］。

給定一個(gè)決策表DT=(U，C∪D)，其中C={c1，c2，…，cn}={cj|j∈{1，2，…，n}}。對(duì)?B?C，B可以表示為：

則樣本x、y在B上的距離函數(shù)為：

特別地，當(dāng)p=1 時(shí)，此距離被稱為Manhattan 距離。本文主要采用Manhattan 距離。由距離函數(shù)，?x∈U在B上的δ-鄰域（類）為：

為了區(qū)分一般的信息系統(tǒng)，將鄰域決策信息系統(tǒng)（Neighborhood Decision information System，NDS）表示為：NDS=(U，C∪D，V，f，d，δ)，與一般信息系統(tǒng)相比增加了距離函數(shù)d和鄰域半經(jīng)δ。

命題1NDS=(U，C∪D，V，f，d，δ)為一個(gè)鄰域決策信息系統(tǒng)，則如下性質(zhì)成立：

1）若δ1≤δ2，則?x∈U有；若δ=0，則=[x]B。

2）若A?B，則?x∈U有。

命題1 揭示了鄰域與半徑閾值以及屬性集大小的關(guān)系，其中當(dāng)鄰域半徑δ=0 時(shí)，樣本的鄰域退化為與它等價(jià)的樣本集。

1.2 三種經(jīng)典決策樹算法

決策樹是一種自頂向下的樹型分類器，通常由葉子、非葉節(jié)點(diǎn)、根節(jié)點(diǎn)三部分構(gòu)成。它首先進(jìn)行根節(jié)點(diǎn)優(yōu)選，非葉節(jié)點(diǎn)根據(jù)如下的分裂函數(shù)h(x，ai)進(jìn)行分裂：

其中：ai∈C為單屬性；x(ai)為樣本x在屬性ai上的取值；αi為間值，根據(jù)屬性ai的劃分而取值。樣本通過分裂函數(shù)h(x，ai)被分配到?jīng)Q策樹的每片葉子中。例如：h(x，ai)=0代表最左邊的葉子，h(x，ai)=1 代表最右邊的葉子，而其余的代表中間的葉子。

基尼指數(shù)能表征數(shù)據(jù)的不均衡分布，其誘導(dǎo)的CART 算法可以構(gòu)造分類樹。

定義1［14］在決策表DT=(U，C∪D)中，決策分類U/D的基尼指數(shù)為：

D關(guān)于B?C的基尼指數(shù)為：

其中：Gini(Bi)=1 -，U/B={B1，B2，…，Bn}。

CART 算法采用基尼指數(shù)來實(shí)施屬性優(yōu)選，由此建立分類樹。此外，CART 算法還可以構(gòu)建回歸樹。

來源于信息理論的信息熵關(guān)聯(lián)于系統(tǒng)信息含量，能夠表征樣本集合的不確定性，由此可以得到經(jīng)典的決策樹歸納算法ID3［15］。

定義2［15］在決策表DT=(U，C∪D)中，決策分類U/D={D1，D2，…，Dm}信息熵為：

其中：H(Bi)=。進(jìn)而，條件屬性B的信息增益為：

gain(D，B)=H(D)-H(D|B)。

ID3 算法遍歷每一個(gè)屬性特征，選擇具有最優(yōu)信息增益的特征來劃分?jǐn)?shù)據(jù)，由此遞歸構(gòu)造決策樹。ID3 算法操作簡(jiǎn)單，但容易涉及偏移性與低精度，后續(xù)具有較多改進(jìn)算法，包括C4.5 算法等。

定義3［16］在決策表DT=(U，C∪D)中，D關(guān)于條件屬性B?C的信息增益率被定義為：

其中：split.info(B)=。

C4.5 是用信息增益比率來作為選擇分支的準(zhǔn)則。信息增益比率通過引入一個(gè)被稱作分裂信息（Split information）的項(xiàng)來對(duì)信息增益進(jìn)行歸一化處理。C4.5 彌補(bǔ)了ID3 中不能處理特征屬性值連續(xù)的缺陷，但是，對(duì)連續(xù)屬性值需要掃描排序，這使C4.5 性能下降。

2 變精度鄰域等價(jià)粒鄰域決策樹

2.1 變精度鄰域等價(jià)粒

定義4以下關(guān)系被稱為B?C上的鄰域等價(jià)關(guān)系：

其中：δ∈[0，1]為鄰域半徑；表示樣本*在B上的δ-鄰域。基于鄰域等價(jià)關(guān)系，誘導(dǎo)出鄰域等價(jià)劃分：

定義1 表明當(dāng)兩個(gè)樣本的鄰域完全相等時(shí)，這兩個(gè)樣本被看作等價(jià)的。然而，這樣的條件太過嚴(yán)格，即現(xiàn)實(shí)數(shù)據(jù)中很難找到兩個(gè)鄰域完全一樣的樣本，因此，變精度鄰域等價(jià)粒被提出。

定義5NDS=(U，C∪D，V，f，d，δ)為鄰域決策信息系統(tǒng)，x，y∈U在屬性B下的鄰域相似度定義如下：

以下關(guān)系被稱為B?C上的變精度鄰域等價(jià)關(guān)系：

其中：δ表示鄰域半徑閾值；β表示變精度閾值。基于變精度鄰域等價(jià)關(guān)系，誘導(dǎo)出變精度鄰域等價(jià)粒結(jié)構(gòu)：

粒結(jié)構(gòu)中，常常伴隨著粒粗細(xì)的比較。變精度鄰域等價(jià)粒結(jié)構(gòu)的粗細(xì)定義如下。

命題2NDS=(U，C∪D，V，f，d，δ)為鄰域決策信息系統(tǒng)，以下性質(zhì)成立：

1）若δ1≤δ2，則；

2）若β1≤β2，則。

證明

推論1NDS=(U，C∪D，V，f，d，δ)為鄰域決策信息系統(tǒng)，0 <δ1≤δ2≤…≤δn≤1、0 <β1≤β2≤…≤βn≤1 分別為鄰域半徑閾值增鏈和精度閾值增鏈，則有：

命題2 和推論1 簡(jiǎn)要探討了變精度鄰域等價(jià)粒結(jié)構(gòu)的一些性質(zhì)。自然地，基于粒結(jié)構(gòu)可構(gòu)造上面的度量函數(shù)。

2.2 變精度鄰域基尼指數(shù)度量

在經(jīng)典的決策樹構(gòu)造算法中，基尼指數(shù)被用作決策樹節(jié)點(diǎn)分裂的度量函數(shù)，后被發(fā)展為互補(bǔ)熵、互補(bǔ)條件熵、互補(bǔ)互信息等。本文中，基尼指數(shù)被擴(kuò)展為鄰域基尼指數(shù)，以此度量鄰域決策信息系統(tǒng)的不確定性，進(jìn)而構(gòu)造面向連續(xù)性數(shù)據(jù)的決策樹分類算法。

定義7NDS=(U，C∪D，V，f，d，δ)為鄰域決策信息系統(tǒng)，B?C基于變精度鄰域等價(jià)關(guān)系的鄰域基尼指數(shù)為：

其中：U/D={D1，D2，…，Dm}。

定義8NDS=(U，C∪D，V，f，d，δ)為鄰域決策信息系統(tǒng)，的鄰域基尼指數(shù)為：

證明 設(shè)NG(x)=x(1 -x)，則NG(x)為一元二次函數(shù)，對(duì)稱中心x=，定義域端點(diǎn)處取得最小值0。

決策樹構(gòu)造過程中，對(duì)數(shù)據(jù)不確定性的度量主要考慮決策屬性D關(guān)于條件屬性的不確定性量化。首先定義D關(guān)于單個(gè)粒的信息度量。

定義9NDS=(U，C∪D，V，f，d，δ)為鄰域決策信息系統(tǒng)，D關(guān)于的鄰域基尼指數(shù)為：取得最大值

因此，D關(guān)于條件屬性B?C基于變精度鄰域等價(jià)關(guān)系的鄰域基尼指數(shù)為：

證明 當(dāng)δ=0，β=1 時(shí)，變精度鄰域等價(jià)關(guān)系就變成了一般等價(jià)關(guān)系，變精度鄰域等價(jià)粒結(jié)構(gòu)也就變成了一般等價(jià)粒結(jié)構(gòu)，因此鄰域基尼指數(shù)退化為一般基尼指數(shù)。

例1 表1 為一個(gè)連續(xù)性數(shù)據(jù)的鄰域決策信息系統(tǒng)。其中U={x1，x2，…，x7}，C={c1，c2，…，c5}，U/D={{1，2，4，5}，{3，6，7}}。基于Manhattan 距離和取定δ=0.5、β=0.7，計(jì)算相關(guān)度量值，相關(guān)結(jié)果如表2 所示。表2 中“*”代表具體的粒結(jié)構(gòu)，本例中主要為。現(xiàn)考慮δ=0，β=1 這種特殊情況，計(jì)算結(jié)果如表3 所示。

表1 實(shí)例決策表Tab.1 Example decision table

表2 δ=0.5、β=0.7時(shí)兩種度量的函數(shù)值Tab.2 Function values of two measures with δ=0.5 and β=0.7

表3 δ=0、β=1時(shí)四種度量的函數(shù)值Tab.3 Function values of four measures with δ=0 and β=1

表3 表明當(dāng)δ=0、β=1 時(shí)，NG(*)=Gini(c)和NG(D，*)=Gini(D，c)，這與命題1 符合。

決策樹構(gòu)造以NG(D，)為節(jié)點(diǎn)分裂的度量函數(shù)。

2.3 變精度鄰域等價(jià)粒鄰域決策樹構(gòu)建

決策樹構(gòu)建常常涉及到節(jié)點(diǎn)選擇和樹的分裂，根據(jù)鄰域基尼指數(shù)度量函數(shù)構(gòu)建鄰域決策樹算法。

算法1 涉及到將一個(gè)鄰域決策信息系統(tǒng)分割為多個(gè)子決策信息系統(tǒng)，然后對(duì)每個(gè)子決策信息系統(tǒng)遞歸的執(zhí)行操作，最終遞歸生成決策樹。第1）步，遍歷決策信息系統(tǒng)的所有單屬性；第2）步，根據(jù)式（18）計(jì)算每個(gè)單屬性的不確定性度量NG(D，)，并反演找出最優(yōu)單屬性，以此作為分裂節(jié)點(diǎn)屬性。第3）～4）步，根據(jù)節(jié)點(diǎn)單屬性誘導(dǎo)其上的變精度鄰域等價(jià)粒結(jié)構(gòu)，構(gòu)造節(jié)點(diǎn)分裂產(chǎn)生樹的分支，產(chǎn)生多個(gè)子決策信息系統(tǒng)。第5）步，對(duì)每個(gè)子決策信息系統(tǒng)遞歸執(zhí)行第1）～4）步，判斷算法終止條件，最終根據(jù)第6）步返回決策樹。算法主要涉及到屬性不確定性的遍歷計(jì)算和子決策信息系統(tǒng)的遞歸劃分，因此算法的時(shí)間復(fù)雜度和空間復(fù)雜度主要為Ο(|C||U|)。

鄰域決策樹算法與傳統(tǒng)的ID3 算法、CART 算法、C4.5 算法有著類似的算法框架，但有著本質(zhì)的區(qū)別。具體表現(xiàn)在：1）鄰域決策樹算法對(duì)葉子節(jié)點(diǎn)分裂的信息，采用鄰域基尼指數(shù)度量，能從底層度量連續(xù)性數(shù)據(jù)。經(jīng)典的三種算法度量函數(shù)均不可直接度量連續(xù)性數(shù)據(jù)，往往需要將數(shù)據(jù)離散化，伴隨著信息的丟失。2）節(jié)點(diǎn)的分裂規(guī)則不一樣。傳統(tǒng)的ID3算法、CART 算法、C4.5 算法主要以樣本的等價(jià)劃分為分裂規(guī)則。鄰域決策樹算法的葉子分裂規(guī)則為變精度鄰域等價(jià)粒結(jié)構(gòu)，且可以通過調(diào)節(jié)精度閾值β來控制節(jié)點(diǎn)分支的粗細(xì)，當(dāng)β=1 時(shí)，退化為鄰域等價(jià)粒，意味著每個(gè)分支里面樣本的鄰域均相同。

3 數(shù)據(jù)集實(shí)驗(yàn)

本章將在來自UCI 數(shù)據(jù)庫的連續(xù)性數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證算法的性能［18］，并與傳統(tǒng)的ID3 算法、CART 算法和C4.5 算法進(jìn)行對(duì)比性實(shí)驗(yàn)分析。考慮到ID3 算法、CART 算法面向的為連續(xù)數(shù)據(jù)集，所以需要先對(duì)數(shù)據(jù)進(jìn)行離散化，再進(jìn)行樣本分類。數(shù)據(jù)離散化采用等距離劃分方法［19］。等距離劃分根據(jù)用戶給定的區(qū)間數(shù)目K，將數(shù)值屬性的值域[Xmin，Xmax]劃分成距離相等的K個(gè)區(qū)間，每個(gè)區(qū)間的寬度為δ=(Xmax-Xmin)/K。實(shí)驗(yàn)數(shù)據(jù)集采用的UCI 數(shù)據(jù)集如表4 所示，它們的決策屬性個(gè)數(shù)均為一個(gè)。其中ILPD 為數(shù)據(jù)集Indian Liver Patient Dataset 的縮寫。

表4 UCI 數(shù)據(jù)集Tab.4 UCI datasets

決策樹算法評(píng)價(jià)常常考慮算法準(zhǔn)確度和葉子數(shù)兩種評(píng)價(jià)指標(biāo)。本文同樣考慮這兩種評(píng)價(jià)指標(biāo)，其中葉子數(shù)由編程軟件直接統(tǒng)計(jì)得到，算法準(zhǔn)確度由式（19）計(jì)算：

其中：m為決策屬性中的標(biāo)簽類別數(shù)；表示所有類別的樣本數(shù)之和；TDj表示正確的被分為第j類的樣本集；|·|表示集合的基數(shù)。

對(duì)數(shù)據(jù)集采用十折交叉法進(jìn)行算法驗(yàn)證，得到相關(guān)結(jié)果如表5 所示。

經(jīng)典的ID3、CART 對(duì)連續(xù)性數(shù)據(jù)進(jìn)行樣本分類時(shí)，需要進(jìn)行數(shù)據(jù)離散化，而信息的丟失主要與離散化方法有關(guān)。本文采用的是等距離劃分方法，區(qū)間數(shù)K的大小影響著樹的準(zhǔn)確度和葉子數(shù)。一般來說，K越大樹的葉子數(shù)越多，準(zhǔn)確度越高，樣本分類更準(zhǔn)確。然而，針對(duì)不同的數(shù)據(jù)集，找到合適的K值，是一件不容易的事。表5 中的信息表明，NDT 算法在不同數(shù)據(jù)集上面的算法準(zhǔn)確度均有不同程度的提高，例如：相較于CART 算法準(zhǔn)確率提升了0.232 3，其余算法也平均提升了20 個(gè)百分點(diǎn)左右。NDT 算法直接從底層度量連續(xù)性數(shù)據(jù)的信息，對(duì)樣本的識(shí)別更準(zhǔn)確。

表5 不同決策樹算法的實(shí)驗(yàn)結(jié)果對(duì)比Tab.5 Comparison of experimental results of different decision tree algorithms

圖1～2 展示了不同算法的準(zhǔn)確度、葉子數(shù)的比較結(jié)果，結(jié)果表明：NDT 算法的準(zhǔn)確度在大部分?jǐn)?shù)據(jù)集上面均有明顯提升，只有seeds、heart 和segment 上提升不明顯；葉子數(shù)方面，NDT 算法CART 算法的葉子數(shù)較接近，NDT 算法有不同程度的提高但仍處于可接受范圍，這是算法機(jī)制所導(dǎo)致。

圖1 不同算法的準(zhǔn)確度對(duì)比Fig.1 Accuracy comparison of different algorithms

圖2 不同算法的葉子數(shù)對(duì)比Fig.2 Comparison of leaf number of different algorithms

4 結(jié)語

鄰域決策樹構(gòu)造算法聚焦信息系統(tǒng)的底層信息度量，避免經(jīng)典決策樹算法針對(duì)連續(xù)性數(shù)據(jù)樣本分類時(shí)造成信息丟失問題。挖掘信息系統(tǒng)的變精度等價(jià)粒結(jié)構(gòu)，構(gòu)建鄰域基尼指數(shù)度量，最終誘發(fā)鄰域決策樹構(gòu)造算法。實(shí)驗(yàn)結(jié)果表明，本文提出的鄰域決策樹算法準(zhǔn)確度得到了明顯的提高，算法具有有效性。