許 行 王文劍,2 任麗芳,3

1(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 太原 030006)2(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué)) 太原 030006)3 (山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 太原 030006)

?

一種基于決策森林的單調(diào)分類方法

許 行1王文劍1,2任麗芳1,3

1(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 太原 030006)2(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué)) 太原 030006)3(山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 太原 030006)

(xuh102@126.com)

單調(diào)分類問題是特征與類別之間帶有單調(diào)性約束的有序分類問題.對(duì)于符號(hào)數(shù)據(jù)的單調(diào)分類問題已有較好的方法，但對(duì)于數(shù)值數(shù)據(jù)，現(xiàn)有的方法分類精度和運(yùn)行效率有限.提出一種基于決策森林的單調(diào)分類方法(monotonic classification method based on decision forest， MCDF)，設(shè)計(jì)采樣策略來構(gòu)造決策樹，可以保持?jǐn)?shù)據(jù)子集與原數(shù)據(jù)集分布一致，并通過樣本權(quán)重避免非單調(diào)數(shù)據(jù)的影響，在保持較高分類精度的同時(shí)有效提高了運(yùn)行效率，同時(shí)這種策略可以自動(dòng)確定決策森林中決策樹的個(gè)數(shù).在決策森林進(jìn)行分類時(shí)，給出了決策沖突時(shí)的解決方法.提出的方法既可以處理符號(hào)數(shù)據(jù)，也可以處理數(shù)值數(shù)據(jù).在人造數(shù)據(jù)集、UCI及真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)表明:該方法可以提高單調(diào)分類性能和運(yùn)行效率，縮短分類規(guī)則的長度，解決數(shù)據(jù)集規(guī)模較大的單調(diào)分類問題.

單調(diào)分類；決策樹；單調(diào)一致性；決策森林；集成學(xué)習(xí)

單調(diào)分類是一種特殊的分類問題，廣泛存在于實(shí)際生活中，如大學(xué)綜合水平的評(píng)定問題，其中“科研水平”、“師資隊(duì)伍”、“教學(xué)質(zhì)量”是3個(gè)重要指標(biāo)，其得分很顯然就是一種序關(guān)系，大學(xué)綜合水平的“評(píng)定等級(jí)”若為“高、中、低”，則它們之間也具有優(yōu)劣次序，這一問題的特征(科研水平、師資隊(duì)伍、教學(xué)質(zhì)量)與類別(評(píng)定等級(jí))之間存在以下單調(diào)性約束：當(dāng)一所學(xué)校在科研水平、師資隊(duì)伍、教學(xué)質(zhì)量這3個(gè)特征上的分?jǐn)?shù)都不比另一所學(xué)校低時(shí)，它的評(píng)定等級(jí)就一定不會(huì)比另一所學(xué)校低.此外，還有諸如決策風(fēng)險(xiǎn)分析、企業(yè)績(jī)效考核、消費(fèi)者滿意度評(píng)價(jià)等問題都具有同樣的特點(diǎn)，這類問題就是單調(diào)分類問題.與一般分類問題不同，單調(diào)分類問題的特征與類別上的取值都存在序的關(guān)系，且2者之間滿足單調(diào)性約束.

對(duì)于一般的分類問題，已經(jīng)有很多分類方法，如決策樹、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等，這些方法一般不考慮特征與類別上的序關(guān)系，所以不能得到單調(diào)一致的分類規(guī)則.目前對(duì)于單調(diào)分類問題已有一些研究，如以粗糙集為理論框架的模型解決單調(diào)分類問題[1-6]，但這些方法獲得的單調(diào)一致的分類規(guī)則數(shù)量有限，且只能用于符號(hào)數(shù)據(jù).對(duì)于數(shù)值數(shù)據(jù)的單調(diào)分類問題，我國學(xué)者Hu等人[7-10]提出的單調(diào)決策樹是目前較好的方法，他們?cè)谝欢ǔ潭壬辖鉀Q了單調(diào)性和泛化能力之間的沖突，還將序的關(guān)系引入經(jīng)典Shannon熵，提出有序信息熵概念，并在此基礎(chǔ)上設(shè)計(jì)了基于有序信息熵的決策樹算法(rank entropy based monotonic decision tree, REMT).這種方法能夠產(chǎn)生結(jié)構(gòu)簡(jiǎn)單、易于理解的規(guī)則集，但得到的精度相對(duì)有限，且存在過度擬合問題.

決策森林源于隨機(jī)森林[11]，是以決策樹為基礎(chǔ)分類器的集成算法，可以有效避免過度擬合，且能夠提高分類精度，因而受到了研究者的廣泛關(guān)注.但決策森林目前只用于解決一般的分類問題，對(duì)于單調(diào)分類問題，構(gòu)造決策森林時(shí)面臨3種困難：1)單個(gè)決策樹的構(gòu)造需要在不同的訓(xùn)練子集上進(jìn)行，如何保證子集的單調(diào)性；2)如何確定決策森林的規(guī)模；3)集成規(guī)則出現(xiàn)沖突時(shí)如何解決.

本文提出一種用于解決單調(diào)分類問題的基于決策森林的單調(diào)分類方法，設(shè)計(jì)采樣策略來構(gòu)造決策樹，該策略考慮數(shù)據(jù)集單調(diào)一致的特點(diǎn)，可避免非單調(diào)數(shù)據(jù)的噪聲影響，同時(shí)這種策略可以自動(dòng)確定決策森林中決策樹的個(gè)數(shù).在決策森林進(jìn)行分類時(shí)，本文還提出葉子節(jié)點(diǎn)上的規(guī)則支持度的概念，從而給出決策沖突時(shí)的解決方法.本文提出的方法既可以處理符號(hào)數(shù)據(jù)，也可以處理數(shù)值數(shù)據(jù).

1 背景知識(shí)

1.1 單調(diào)分類問題

令U={x1,x2,…,xn}為數(shù)據(jù)集，A={a1,a2,…,am}是描述數(shù)據(jù)的特征集，xi在特征a上的值記為a(xi)，xi的類標(biāo)簽記為y(xi).如果y(xi)的值域{c1,c2,…,cs}上存在序關(guān)系c1

對(duì)于一個(gè)有序分類問題，如果?xi,xj∈U在每一個(gè)特征ak∈A上都滿足若ak(xi)≤ak(xj)，則y(xi)≤y(xj)，那么該問題為單調(diào)分類問題[12].

給定xi∈U，若特征集B?A，則在特征集B上xi的優(yōu)勢(shì)類和劣勢(shì)類分別定義為

(1)

(2)

1.2 決策森林

決策森林是由多個(gè)單棵決策樹組成集成分類器的集成學(xué)習(xí)方法，可表示為{h(x,θk),k=1,2,…}，其中，x是輸入樣本，θk是獨(dú)立同分布的隨機(jī)變量，h(x,θk)表示一棵決策樹.對(duì)于輸入樣本x，每棵決策樹判斷其類別后投票給與其判斷結(jié)果相符的類，得票最多的一類為最終分類結(jié)果.構(gòu)建決策森林的方式主要有基于數(shù)據(jù)集的構(gòu)造方式和基于特征集的構(gòu)造方式.

構(gòu)建決策森林模型時(shí)主要考慮4方面：

1) 當(dāng)采用基于數(shù)據(jù)集的構(gòu)造方式構(gòu)造決策森林時(shí)，訓(xùn)練數(shù)據(jù)子集如何構(gòu)成；

2) 當(dāng)采用基于特征集的構(gòu)造方式構(gòu)造決策森林時(shí)，特征子集如何構(gòu)成；

3) 決策樹的數(shù)目如何確定；

4) 生成的所有決策樹如何集成為決策森林模型.

2 決策森林單調(diào)分類方法

2.1 單棵決策樹的構(gòu)造

決策森林的預(yù)測(cè)能力與每棵決策樹相關(guān)，為用較少的決策樹構(gòu)造出精度較高的決策森林，決策樹必須要有一定的差異性.本文采用基于數(shù)據(jù)集的構(gòu)造方式構(gòu)造決策森林，通過為每個(gè)決策樹構(gòu)造有差異性的訓(xùn)練子集來獲得決策樹之間的差異性.構(gòu)造單棵決策樹的訓(xùn)練子集時(shí)，不能采用經(jīng)典的隨機(jī)采樣、bagging[13]、boosting[14]等方法，因?yàn)殡S機(jī)采樣和bagging方法都不考慮數(shù)據(jù)的分布情況，boosting方法對(duì)噪聲的敏感性使其更易于產(chǎn)生過擬合現(xiàn)象[15]，并且這些方法也沒有考慮數(shù)據(jù)的單調(diào)性.Liang等人[16]提出一種較好的重采樣方法，使得采樣得到的子集間有一定的差異度又能較大程度地覆蓋原始數(shù)據(jù)集，且與原數(shù)據(jù)集分布相同，但該方法不考慮數(shù)據(jù)的序關(guān)系，且只能用于符號(hào)數(shù)據(jù)的處理.

本文借鑒文獻(xiàn)[16]，將以上方法引入單調(diào)分類問題，可以同時(shí)處理符號(hào)數(shù)據(jù)和數(shù)值數(shù)據(jù).在構(gòu)造單棵決策樹時(shí)，為保持單調(diào)分布的一致性，為每個(gè)樣本加權(quán)，在多次采樣時(shí)權(quán)值不是固定不變的，而是隨著已有決策樹的錯(cuò)誤率和錯(cuò)分樣本的單調(diào)一致性進(jìn)行調(diào)整，在調(diào)整中去掉不一致的樣本.另外，本文中訓(xùn)練子集的規(guī)模不是由用戶指定的固定值，而是根據(jù)數(shù)據(jù)集的特征自動(dòng)確定的.

1) 訓(xùn)練子集規(guī)模的確定

對(duì)于數(shù)據(jù)集U，文獻(xiàn)[16]給出的訓(xùn)練子集規(guī)模M為

(3)

其中，Z為置信水平下的Z-統(tǒng)計(jì)值，可以計(jì)算得出，E為可以接受的誤差，由用戶指定，這2個(gè)變量取值已知，因此計(jì)算M的關(guān)鍵在于數(shù)據(jù)集上的標(biāo)準(zhǔn)差σ的計(jì)算.文獻(xiàn)[16]給出了符號(hào)數(shù)據(jù)上σ的計(jì)算方法.

為同時(shí)處理符號(hào)數(shù)據(jù)和數(shù)值數(shù)據(jù)，本文設(shè)計(jì)的標(biāo)準(zhǔn)差σ為

(4)

對(duì)于數(shù)值型特征，先統(tǒng)一各個(gè)特征的取值范圍，將所有樣本的特征取值歸一化：

(5)

其中，akmin(x)和akmax(x)分別表示所有樣本在特征ak上的最小值和最大值,然后計(jì)算該特征的特征標(biāo)準(zhǔn)差：

對(duì)于符號(hào)型特征，與文獻(xiàn)[16]不同，本文采用單個(gè)特征的不相似度而不是基于所有特征上的不相似度來計(jì)算特征標(biāo)準(zhǔn)差σak.

(7)

一般地，為保證學(xué)習(xí)器的訓(xùn)練效率，訓(xùn)練子集的規(guī)模M不宜太大，若M與樣本總數(shù)N超過一定比率θ(如θ=5%)，需要調(diào)整訓(xùn)練子集的規(guī)模，調(diào)整方法為

(8)

確定訓(xùn)練子集樣本的規(guī)模算法總結(jié)如下.

算法1. 確定訓(xùn)練子集樣本的規(guī)模算法.

輸入: 單調(diào)數(shù)據(jù)集U、參數(shù)Z,E,θ；

輸出: 訓(xùn)練子集的規(guī)模M.

Step1. 按式(4)計(jì)算數(shù)據(jù)集的標(biāo)準(zhǔn)差：若特征為數(shù)值型，則按式(5)將所有樣本在該特征上的取值歸一化，然后按式(6)計(jì)算其特征標(biāo)準(zhǔn)差；若特征為符號(hào)型，則按式(7)計(jì)算其特征標(biāo)準(zhǔn)差；

Step2. 按式(3)計(jì)算訓(xùn)練子集的規(guī)模M；

Step4. 返回M.

2) 訓(xùn)練子集的采樣

采樣訓(xùn)練子集前，先計(jì)算原始訓(xùn)練集U中每個(gè)類別的樣本占所有樣本的比例pl：

(9)

其中，l=1,2,…,s，Cl={xi∈U|y(xi)=cl}，i=1,2,…,n.采樣時(shí)要確保各個(gè)類別的樣本數(shù)在原訓(xùn)練集與采樣出的訓(xùn)練子集中的比例相同.之后通過迭代采樣訓(xùn)練子集，每次迭代產(chǎn)生1個(gè)訓(xùn)練子集.迭代過程如下：

初始狀態(tài)下，原訓(xùn)練集U中所有樣本的權(quán)重相等，即每個(gè)樣本的初始權(quán)重為

(10)

其中,n為原訓(xùn)練集中樣本的數(shù)量.

首先采樣第1個(gè)訓(xùn)練子集U1，在原訓(xùn)練集U中隨機(jī)選擇M個(gè)樣本，并保證其中每個(gè)類別的樣本數(shù)與M的比例為pl,l=1,2,…,s.采樣下一個(gè)訓(xùn)練子集Ut時(shí)，先在前一個(gè)訓(xùn)練子集上生成決策樹，計(jì)算該決策樹的加權(quán)誤差εt：

(11)

根據(jù)錯(cuò)誤率更新原訓(xùn)練集的樣本權(quán)重：對(duì)于錯(cuò)分的樣本，首先判斷該樣本的單調(diào)一致性，本文用包含度描述樣本的單調(diào)一致性.定義xi在特征集A與類標(biāo)簽y上的包含度為

(12)

D(xi)的值越大，表示樣本xi在特征集與類別上取值的單調(diào)一致性越高.這里把滿足D(xi)≥e的樣本xi看作單調(diào)一致的樣本，否則為非單調(diào)一致的樣本，e為給定的參數(shù).

對(duì)于錯(cuò)分的單調(diào)一致樣本，增加其權(quán)重：

(13)

對(duì)于錯(cuò)分的非單調(diào)一致樣本，減小其權(quán)重：因?yàn)榉菃握{(diào)一致的樣本會(huì)影響分類器的精確度，故令其權(quán)重直接為0.

由于每次迭代產(chǎn)生1個(gè)訓(xùn)練子集，每個(gè)訓(xùn)練子集對(duì)應(yīng)生成1棵決策樹，因此迭代執(zhí)行的次數(shù)就是決策森林中決策樹的數(shù)目.當(dāng)M確定后，每次從未抽取過的數(shù)據(jù)集中抽取的樣本個(gè)數(shù)(1-α)M也隨之確定，進(jìn)而可以確定總迭代次數(shù).也就是說，決策森林中決策樹的數(shù)目可以通過確定每個(gè)訓(xùn)練子集的樣本規(guī)模自動(dòng)確定.

訓(xùn)練子集的采樣算法總結(jié)如下.

算法2. 訓(xùn)練子集的采樣算法.

輸入: 單調(diào)數(shù)據(jù)集U、參數(shù)Z,E,θ,e,α；

輸出:h個(gè)訓(xùn)練子集.

Step1. 用算法1確定訓(xùn)練子集的樣本規(guī)模M.

Step2. 對(duì)于單調(diào)數(shù)據(jù)集U，按式(9)計(jì)算其中各個(gè)類別的比例pl；

Step3. 按式(10)為訓(xùn)練集中每個(gè)樣本的權(quán)重賦初值；

Step4. 在U上隨機(jī)選擇訓(xùn)練子集U1，并保證其中各類別樣本數(shù)占該訓(xùn)練子集中所有樣本數(shù)的相應(yīng)比例為pl；

Step5. 按以下步驟，迭代生成決策樹，直到訓(xùn)練集U上未被抽取的樣本數(shù)小于M時(shí)結(jié)束循環(huán)，并記錄迭代執(zhí)行的次數(shù)h；

Step5.1. 在上一訓(xùn)練子集上用REMT[9]方法生成決策樹，并按式(11)計(jì)算決策樹的加權(quán)誤差；

Step5.2. 對(duì)錯(cuò)分樣本按式(12)計(jì)算其單調(diào)一致性，對(duì)給定參數(shù)e，若D(xi)≥e，則按式(13)更新xi的權(quán)重，否則權(quán)重為0；

Step5.3. 在Ut-1上抽取αM個(gè)樣本，在U上未被抽取的樣本中抽取(1-α)M個(gè)樣本，得到新的訓(xùn)練子集Ut，并保證其各類別的相應(yīng)比例為pl；

Step5.4. 對(duì)Ut中的樣本權(quán)重歸一化；

Step6. 返回h個(gè)訓(xùn)練子集Ut(t=1,2,…,h).

在每個(gè)訓(xùn)練子集Ut上，采用適用于單調(diào)分類的REMT算法[9]可以生成單棵決策樹Tt，t=1,2,…,h.

2.2 決策森林的生成算法

本文提出一種基于決策森林的單調(diào)分類算法(monotonic classification method based on decision forest, MCDF)，通過計(jì)算每棵決策樹的規(guī)則支持度，獲得決策森林最終的分類結(jié)果.

對(duì)于每棵決策樹，設(shè)葉子節(jié)點(diǎn)leafi中包含的樣本集為Uleafi，這些樣本來自不同的類c1,c2,…，定義分類規(guī)則在類別ck上的規(guī)則支持度為

(14)

其中,Uleafi k表示葉子節(jié)點(diǎn)leafi中的第k類樣本集.

規(guī)則支持度Support(ck)記錄在每棵決策樹的每個(gè)葉子節(jié)點(diǎn)上，集成決策樹時(shí)，根據(jù)每棵樹的分類規(guī)則和規(guī)則支持度確定分類結(jié)果：當(dāng)一個(gè)新的樣本輸入時(shí)，讓每棵決策樹根據(jù)自己的分類規(guī)則對(duì)其投票，即投票給它認(rèn)為正確的類別，最后選擇得票數(shù)最多的類作為該樣本的最終分類結(jié)果.若有r個(gè)類別的得票數(shù)相等(r≥2)，即決策沖突時(shí)，計(jì)算每棵決策樹中用于判斷該樣本類別的葉子節(jié)點(diǎn)的規(guī)則支持度，將這h棵決策樹在每種類別上的規(guī)則支持度加和，取規(guī)則支持度之和最大的類別作為該樣本的最終分類結(jié)果，即該樣本的分類結(jié)果為

(15)

本文提出的MCDF算法的主要步驟如下.

算法3. MCDF算法.

輸入: 訓(xùn)練集UTrain、測(cè)試集UTest、參數(shù)Z,E,θ,e,α；

輸出: 測(cè)試集UTest中所有樣本的分類結(jié)果.

Step1. 用算法2得到訓(xùn)練集UTrain的h個(gè)訓(xùn)練子集Ut,t=1,2,…,h；

Step2. 在每個(gè)訓(xùn)練子集上用決策樹算法REMT[9]生成決策樹Tt,t=1,2,…,h，按式(14)計(jì)算每個(gè)葉子節(jié)點(diǎn)中各個(gè)類別上的規(guī)則支持度；

Step3. 對(duì)測(cè)試集中的一個(gè)樣本x，讓h棵決策樹對(duì)其分類并投票，得到多個(gè)分類結(jié)果ck,k=1,2,…；

Step4. 比較每個(gè)類別ck的得票數(shù)，按以下步驟決定最終分類結(jié)果：

Step4.1. 若具有最多票數(shù)的ck唯一，記為cmax，則cmax就是該樣本的最終類別；

Step4.2. 若同時(shí)具有最多票數(shù)的類別ck有r個(gè)(r≥2)，則按式(15)計(jì)算這r個(gè)類中規(guī)則支持度之和最大的類別ck，作為該樣本的最終類別；

Step5. 對(duì)測(cè)試集UTest中的所有樣本分類后返回分類結(jié)果.

2.3 時(shí)間復(fù)雜度分析

由于決策樹數(shù)目可以提前計(jì)算，因此，MCDF方法構(gòu)建決策森林的時(shí)間主要由采樣時(shí)間和生成決策樹的時(shí)間2部分構(gòu)成.

采樣過程中，樣本在特征集與類標(biāo)簽上的包含度可以在采樣前提前計(jì)算，不需占用采樣時(shí)間.而計(jì)算決策樹的加權(quán)誤差、更新樣本權(quán)重和抽樣過程都需要分別遍歷1次M個(gè)樣本，因此單棵決策樹的采樣過程的時(shí)間復(fù)雜度為O(M).

生成決策樹時(shí)，需要分別考慮非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)上的時(shí)間復(fù)雜度.

2) 在第j個(gè)葉子節(jié)點(diǎn)上，需要遍歷該節(jié)點(diǎn)中的所有樣本求其所包含的每個(gè)類別的支持度，故葉子節(jié)點(diǎn)上的時(shí)間復(fù)雜度為O(nj)≤O(M).

假設(shè)決策森林中的非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)數(shù)分別為k1和k2，則生成決策樹的時(shí)間復(fù)雜度為O(k1mvM2+k2M).

綜上，設(shè)MCDF方法構(gòu)建的決策森林中決策樹數(shù)目為h個(gè)，那么MCDF方法的時(shí)間復(fù)雜度為O(hM+k1mvM2+k2M).

由以上分析可知，本方法中雖然增加了采樣過程，但采樣的時(shí)間復(fù)雜度僅為O(hM)，而通過采樣可以將時(shí)間復(fù)雜度中的樣本數(shù)量M由原訓(xùn)練集的樣本數(shù)量n減少為采樣后的M，而M?n.

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

本文分別在4個(gè)人造數(shù)據(jù)集、7個(gè)UCI及1個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).4個(gè)單調(diào)的人造數(shù)據(jù)集構(gòu)造[8]為

(16)

其中，x1,x2∈[0,1].

每個(gè)數(shù)據(jù)集都有1 000個(gè)樣本、2個(gè)特征，類別數(shù)依次為2類、4類、6類和8類，其散點(diǎn)圖如圖1所示:

Fig. 1 The artificial datasets圖1 人造數(shù)據(jù)集

本文還使用表1所示的8個(gè)數(shù)據(jù)集驗(yàn)證算法，除Score為山西大學(xué)學(xué)生成績(jī)的真實(shí)數(shù)據(jù)集外，剩下的7個(gè)為UCI數(shù)據(jù)集.其中Wine，Score為數(shù)值型數(shù)據(jù)集，Breast-w，Car為符號(hào)型數(shù)據(jù)集，其他4個(gè)為既包含符號(hào)型特征也包含數(shù)值型特征的數(shù)據(jù)集.

Table 1 The Datasets Description表1 數(shù)據(jù)集描述

在每個(gè)數(shù)據(jù)集上進(jìn)行十折交叉驗(yàn)證.使用分類準(zhǔn)確率和平均絕對(duì)誤差作為預(yù)測(cè)能力的評(píng)價(jià)標(biāo)準(zhǔn).

分類準(zhǔn)確率CA定義為

(17)

平均絕對(duì)誤差MAE定義為

(18)

此外，用決策樹的平均深度Depth作為分類規(guī)則長度的評(píng)價(jià)標(biāo)準(zhǔn).實(shí)驗(yàn)設(shè)備是1臺(tái)配置為3.60 GHz-4核CPU、8 GB內(nèi)存的計(jì)算機(jī)，實(shí)驗(yàn)平臺(tái)是MyEclipse 2015CI.相關(guān)參數(shù)設(shè)置如下：Z=1.96，E=1.2，θ=0.05，e=0.1，α=0.5.

3.2 MCDF與REMT算法的比較

Hu等人提出的REMT單調(diào)分類算法[9]是單調(diào)分類問題中較為經(jīng)典的算法，因此本文首先比較MCDF與REMT單調(diào)分類算法的分類精度、平均絕對(duì)誤差和決策樹深度.

圖2和圖3分別為2種算法在人造數(shù)據(jù)集和UCI及真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

從圖2和圖3可以看出，除人造數(shù)據(jù)集Set3以外，MCDF方法在所有數(shù)據(jù)集上都比REMT算法的分類準(zhǔn)確率高，平均絕對(duì)誤差低；由于訓(xùn)練子集的規(guī)模比原訓(xùn)練集的規(guī)模小，所以在包括Set3在內(nèi)的所有數(shù)據(jù)集上，MCDF方法都比REMT算法的決策樹深度小.

Fig. 2 The experimental result comparison of REMT and MCDF on the artificial datasets圖2 人造數(shù)據(jù)集上REMT算法與MCDF方法的實(shí)驗(yàn)結(jié)果比較

在人造數(shù)據(jù)集Set3上，MCDF方法在CA和平均絕對(duì)誤差MAE上比REMT算法低約0.4%.MCDF方法在生成多個(gè)決策樹的迭代過程中，除了每次采樣不同的訓(xùn)練樣本外，還通過判斷錯(cuò)分樣本的單調(diào)一致程度來改變每棵決策樹中訓(xùn)練樣本的權(quán)重，以增加各個(gè)決策樹之間的差異度，從而提高決策森林的分類精度.而由于構(gòu)造的人造數(shù)據(jù)集具有較強(qiáng)的單調(diào)一致性，一方面單調(diào)一致的數(shù)據(jù)集中不會(huì)有權(quán)重為0的樣本出現(xiàn)，另一方面，單棵決策樹在單調(diào)一致的數(shù)據(jù)集上每次迭代得到的錯(cuò)分樣本數(shù)量較少，即權(quán)重改變的樣本數(shù)較少，造成了各個(gè)決策樹之間的樣本權(quán)重差異度不大，所以MCDF方法的優(yōu)越性沒有得到充分體現(xiàn)；而REMT算法由于使用了全部的訓(xùn)練對(duì)象，在人造數(shù)據(jù)集上具有較好的分類性能.實(shí)際上，在人造數(shù)據(jù)集上，2種方法的分類性能差別不大：在Set1，Set2，Set4上MCDF方法精度比REMT算法提高不多(分別為0.9%，0.6%和1.8%)，在Set3上低于REMT算法的差距也很小(0.4%).

根據(jù)實(shí)驗(yàn)結(jié)果，在人造數(shù)據(jù)集和UCI及真實(shí)數(shù)據(jù)集上，MCDF方法比REMT算法的分類準(zhǔn)確率分別平均提高了0.72%和4.14%，平均絕對(duì)誤差分別平均降低了0.73%和4.21%，而且由于使用了較小規(guī)模的訓(xùn)練子集，MCDF方法得到的決策樹深度在人造數(shù)據(jù)集和UCI及真實(shí)數(shù)據(jù)集上分別平均減少了1.6和3.21，因此本文提出的方法可以提高單調(diào)分類的性能，縮短分類規(guī)則的長度.

Fig. 3 The experimental result comparison of REMT and MCDF on the UCI and real datasets圖3 UCI及真實(shí)數(shù)據(jù)集上REMT算法與MCDF方法的實(shí)驗(yàn)結(jié)果比較

3.3 MCDF與Adaboost.M1算法的比較

MCDF與經(jīng)典的集成學(xué)習(xí)方法Adaboost.M1算法[14]進(jìn)行了比較，表2是2種方法在12個(gè)數(shù)據(jù)集上的準(zhǔn)確率和平均絕對(duì)誤差比較.

從表2可以看出，除Australian以外的其他11個(gè)數(shù)據(jù)集上，MCDF比Adaboost.M1的分類準(zhǔn)確率高、平均絕對(duì)誤差低.因?yàn)锳daboost.M1算法是根據(jù)基分類器的錯(cuò)誤率改變錯(cuò)分的訓(xùn)練樣本的權(quán)重，進(jìn)而構(gòu)造不同的訓(xùn)練子集，生成決策樹，而對(duì)于單調(diào)分類問題，由于訓(xùn)練集中存在非單調(diào)一致的樣本，在Adaboost.M1算法的迭代過程中，這些樣本的權(quán)重逐漸增大，降低了基分類器的準(zhǔn)確率，使得Adaboost.M1算法的集成結(jié)果較差.而本文算法中根據(jù)D(xi)判斷樣本xi的單調(diào)一致性，避免采樣非單調(diào)一致的樣本，同時(shí)提高采樣得到的訓(xùn)練子集的差異性，所以取得了較好的集成效果.

在數(shù)據(jù)集Australian上，MCDF方法在CA和平均絕對(duì)誤差MAE上都比Adaboost.M1算法低2.3%，其原因首先與數(shù)據(jù)集Australian本身的特點(diǎn)有關(guān).根據(jù)文獻(xiàn)[12]中有序數(shù)據(jù)集上特征對(duì)類別的依賴度的定義可以求得：數(shù)據(jù)集Australian上的特征依賴度為0.998，接近于1，也就是說幾乎所有樣本都可以被一致地分配類別，這與人造數(shù)據(jù)集上的情況相似.其次，MCDF方法在數(shù)據(jù)集Australian上的迭代過程中較少出現(xiàn)權(quán)重改變較大的樣本，降低了MCDF方法創(chuàng)建的決策森林中各個(gè)決策樹之間的差異度，使得MCDF方法的性能受到影響；而數(shù)據(jù)集Australian中噪聲較少的特點(diǎn)恰好避開了Adaboost.M1算法對(duì)噪聲比較敏感的弱點(diǎn)，使其分類效果不受影響.另外，數(shù)據(jù)集Australian的類別數(shù)為2，也使得MCDF方法針對(duì)多類別之間的有序關(guān)系上的優(yōu)勢(shì)難以得到體現(xiàn)，而Adaboost.M1每次都使用了全部訓(xùn)練樣本生成決策樹，具有相對(duì)較好的分類性能.以上3個(gè)因素共同造成了MCDF在Australian上的分類性能略差于Adaboost.M1算法.但是與Set3一樣，雖然MCDF方法的分類精度比Adaboost.M1略有下降，但其運(yùn)行效率比Adaboost.M1算法高.

Table 2 The CA and MAE Result Comparison of Adaboost.M1 and MCDF on the Datasets表2 Adaboost.M1算法與MCDF方法的準(zhǔn)確率和誤差比較

3.4 REMT，Adaboost.M1與MCDF的運(yùn)行時(shí)間

REMT，Adaboost.M1與MCDF方法在運(yùn)行時(shí)間上進(jìn)行了比較，表3是3種方法在12個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

Table 3 The Running Time Comparison of REMT, Adaboost.M1 and MCDF表3 REMT，Adaboost.M1與MCDF方法的運(yùn)行 時(shí)間比較 s

從表3可以看出，運(yùn)行效率上，MCDF方法的執(zhí)行時(shí)間比REMT算法、Adaboost.M1算法都有很大提高，尤其在數(shù)值型數(shù)據(jù)集上，如Set1～Set4，效果非常顯著.按照2.3節(jié)中的分析可知，生成每棵決策樹的時(shí)間復(fù)雜度為O(k1mvM2+k2M)，由于Set1～Set4為數(shù)值型數(shù)據(jù)集，所以其特征的值域取值有ni種，即v=ni，以根節(jié)點(diǎn)為例，數(shù)值型數(shù)據(jù)集根節(jié)點(diǎn)上的時(shí)間復(fù)雜度就為O(mM3)，那么與REMT和Adaboost.M1算法每次都使用訓(xùn)練集中的所有對(duì)象生成單棵決策樹相比，如果MCDF方法的樣本量減少為原來的20%，根節(jié)點(diǎn)上的運(yùn)行時(shí)間就可以減少為原來的1500，同理，其他節(jié)點(diǎn)上的運(yùn)行時(shí)間也都有不同程度的降低，而采樣過程所增加的時(shí)間花銷卻很小.因此，盡管REMT算法只訓(xùn)練1棵決策樹，但其時(shí)間復(fù)雜度為2n)，而M?n，所以其運(yùn)行速度仍然比MCDF方法慢，而Adaboost.M1算法所需時(shí)間為REMT的hA倍(hA為Adaboost.M1算法構(gòu)造的基分類器數(shù)量)，運(yùn)行速度更慢.由實(shí)驗(yàn)結(jié)果可知，在數(shù)值型的人造數(shù)據(jù)集上，MCDF方法的平均時(shí)間花銷分別約為REMT和Adaboost.M1算法的19和1130；在UCI及真實(shí)數(shù)據(jù)集上，MCDF方法的平均時(shí)間花銷提高最多的是German數(shù)據(jù)集，分別約為REMT和Adaboost.M1的15和155，即使在提高最少的CPU數(shù)據(jù)集上，MCDF方法的時(shí)間花銷也僅約為REMT和Adaboost.M1的12和114.因此，本文提出的方法有效地提高了運(yùn)行效率.

3.5 MCDF在較大規(guī)模數(shù)據(jù)集上的有效性

由于UCI中單調(diào)數(shù)據(jù)集的規(guī)模較小，為了驗(yàn)證MCDF在較大規(guī)模數(shù)據(jù)集上的有效性，用以下函數(shù)構(gòu)造單調(diào)數(shù)據(jù)集：

f(x1,x2,…,xm)=

(19)

Table 4 The Large Dataset Description表4 大規(guī)模數(shù)據(jù)集描述

在該數(shù)據(jù)集上，MCDF方法的實(shí)驗(yàn)結(jié)果如表5所示.而REMT和Adaboost.M1算法在數(shù)據(jù)集LargeSet1，LargeSet2上用MCDF方法的10倍運(yùn)行時(shí)間仍無法得到結(jié)果；在LargeSet3～LargeSet6這4個(gè)數(shù)據(jù)集上，也無法在可接受的時(shí)間內(nèi)得到結(jié)果.

Table 5 The Experimental Result on the Large Dataset表5 大規(guī)模數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

4 結(jié)束語

本文提出的MCDF方法針對(duì)單調(diào)的數(shù)據(jù)集，用基于數(shù)據(jù)集的構(gòu)造方式構(gòu)建決策森林，解決單調(diào)分類問題.該方法既可處理符號(hào)型數(shù)據(jù)，又可處理數(shù)值型數(shù)據(jù)以及包含符號(hào)型和數(shù)值型的混合數(shù)據(jù)；設(shè)計(jì)的采樣策略，在保持較高分類精度的同時(shí)大大提高了運(yùn)行效率；提出的規(guī)則支持度有效地保證了單調(diào)分類的性能；此外，該方法還可以解決大規(guī)模數(shù)據(jù)集上的單調(diào)分類問題.本文通過數(shù)據(jù)集各個(gè)特征上的取值來自動(dòng)確定決策樹的數(shù)目，可以避免人工干預(yù)，但需要遍歷所有樣本來獲得對(duì)決策樹的評(píng)價(jià)，對(duì)算法效率有一定影響.能否根據(jù)決策樹本身的結(jié)構(gòu)選擇部分決策樹來構(gòu)成決策森林還需要進(jìn)一步研究.

[1]Greco S, Matarazzo B, Slowinski R. Rough approximation by dominance relations[J]. International Journal of Intelligent Systems, 2002, 17(2): 153-171

[2]Sai Ying, Yao Yiyu, Zhong Ning. Data analysis and mining in ordered information tables[C]Proc of IEEE ICDM’01. Los Alamitos, CA: IEEE Computer Society, 2001: 497-504

[3]Kotlowski W, Dembczynski K, Greco S, et al. Stochastic dominance based rough set model for ordinal classification[J]. Information Sciences, 2008, 178(21): 4019-4037

[4]Hu Qinghua, Yu Daren, Guo Maozu. Fuzzy preference based rough sets[J]. Information Sciences, 2010, 180(10): 2003-2022

[5]Qian Yuhua, Dang Chuangyin, Liang Jiye, et al. Set-valued ordered information systems[J]. Information Sciences, 2009, 179(16): 2809-2832

[6]Ben-David A. Automatic generation of symbolic multiattribute ordinal knowledge-based DSSs: Methodology and applications[J]. Decision Sciences, 1992, 23(6): 1357-1372

[7]Hu Qinghua, Guo Maozu, Yu Daren, et al. Information entropy for ordinal classification[J]. Science China: Information Sciences, 2010, 53(6): 1188-1200

[8]Hu Qinghua, Pan Weiwei, Zhang Lei, et al. Feature selection for monotonic classification[J]. IEEE Trans on Fuzzy Systems, 2012, 20(1): 69-81

[9]Hu Qinghua, Che Xunjian, Zhang Lei, et al. Rank entropy based decision trees for monotonic classification[J]. IEEE Trans on Knowledge and Data Engineering, 2012, 24(11): 2052-2064

[10]Che Xunjian. Ordinal decision tree based fault level detection[D]. Harbin: Harbin Institute of Technology, 2011 (in Chinese)(車勛建. 基于有序決策樹的故障程度診斷研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2011)

[11]Breiman L. Random forest[J]. Machine Learning, 2001, 45(1): 5-32

[12]Hu Qinghua, Yu Daren. Applied Rough Computing[M]. Beijing: Science Press, 2012 (in Chinese)(胡清華, 于達(dá)仁. 應(yīng)用粗糙計(jì)算[M]. 北京: 科學(xué)出版社, 2012)

[13]Breiman L. Bagging predictors[J]. Machine Learning, 1996, 24(2): 123-140

[14]Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences, 1997, 55(1): 119-139

[15]Wang Wenjian, Men Changqian. Support Vector Machine Modeling and Application[M]. Beijing: Science Press, 2014 (in Chinese)(王文劍, 門昌騫. 支持向量機(jī)建模及應(yīng)用[M]. 北京: 科學(xué)出版社, 2014)

[16]Liang Jiye, Wang Feng, Dang Chuangyin, et al. An efficient rough feature selection algorithm with a multi-granulation view[J]. International Journal of Approximate Reasoning, 2012, 53(6): 912-926

Xu Hang, born in 1987. PhD candidate. Her main research interests include machine learning and service computing.

Wang Wenjian, born in 1968. PhD. Professor, PhD supervisor. Senior member of CCF. Her main research interests include neural networks, support vector machine, machine learning and intelligent computing.

Ren Lifang, born in 1976. PhD candidate. Lecturer. Her main research interests include machine learning and service computing.

A Method for Monotonic Classification Based on Decision Forest

Xu Hang1, Wang Wenjian1,2, and Ren Lifang1,3

1(SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006)2(KeyLaboratoryofComputationalIntelligenceandChineseInformationProcessing(ShanxiUniversity),MinistryofEducation,Taiyuan030006)3(SchoolofAppliedMathematics,ShanxiUniversityofFinanceandEconomics,Taiyuan030006)

Monotonic classification is an ordinal classification problem in which the monotonic constraint exists between features and class. There have been some methods which can deal with the monotonic classification problem on the nominal datasets well. But for the monotonic classification problems on the numeric datasets, the classification accuracies and running efficiencies of the existing methods are limited. In this paper, a monotonic classification method based on decision forest (MCDF) is proposed. A sampling strategy is designed to generate decision trees, which can make the sampled training data subsets having a consistent distribution with the original training dataset, and the influence of non-monotonic noise data is avoided by the sample weights. It can effectively improve the running efficiency while maintaining the high classification performance. In addition, this strategy can also determine the number of trees in decision forest automatically. A solution for the classification conflicts of different trees is also provided when the decision forest determines the class of a sample. The proposed method can deal with not only the nominal data, but also the numeric data. The experimental results on artificial, UCI and real datasets demonstrate that the proposed method can improve the monotonic classification performance and running efficiency, and reduce the length of classification rules and solve the monotonic classification problem on large datasets.

monotonic classification; decision tree; monotonic consistency; decision forest; ensemble learning

2016-03-11；

2016-08-08

國家自然科學(xué)基金項(xiàng)目(61673249,61503229)；山西省回國留學(xué)人員科研基金項(xiàng)目(2016-004)；山西省研究生教育創(chuàng)新項(xiàng)目(2016BY003) This work was supported by the National Natural Science Foundation of China (61673249, 61503229), the Scientific Research Foundation for Returned Scholars of Shanxi Province (2016-004), and the Innovation Project of Shanxi Graduate Education (2016BY003).

王文劍(wjwang@sxu.edu.cn)

TP181