裴生雷　賈國(guó)慶　葉利娟

1(青海民族大學(xué)物理與電子信息工程學(xué)院　青海 西寧 810007) 2(青海民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院　青海 西寧 810007)

0　引　言

在傳統(tǒng)的分類任務(wù)中，人們很少去考慮數(shù)據(jù)的有序性。然而現(xiàn)實(shí)世界中很多任務(wù)都存在這類問題，特征值的序關(guān)系，可以更好地描述數(shù)據(jù)本身的特點(diǎn)，使用戶獲得潛在的偏好信息。在解決多屬性決策問題時(shí)，有序特征的評(píng)價(jià)指標(biāo)就顯得非常重要。這些指標(biāo)可以用于有限決策方案的排序擇優(yōu)問題，可以應(yīng)用于信用評(píng)價(jià)、顧客滿意度評(píng)估、社會(huì)調(diào)查統(tǒng)計(jì)、故障診斷等領(lǐng)域[1-5]。在這里我們舉一個(gè)例子，來(lái)說明數(shù)據(jù)本身具備的有序特征。假設(shè)信用評(píng)價(jià)任務(wù)中存在三個(gè)條件屬性(歷史信譽(yù)、收入和學(xué)歷)用于描述客戶，決策屬性是信用等級(jí)。在這里，如果客戶X的三個(gè)條件屬性值比客戶Y的好，那么X的信用等級(jí)也不比Y的差。這類問題中，對(duì)象的條件屬性和決策屬性存在序關(guān)系，即屬性值之間是可以比較大小。目前，在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和智能決策領(lǐng)域中越來(lái)越引起研究人員的重視。

有序分類問題中，隨著研究的深入和發(fā)展，特征評(píng)價(jià)指標(biāo)也得到了改進(jìn)和發(fā)展。有序條件熵、排序互信息、排序基尼不純度可以很好地判斷排序一致性，進(jìn)而獲取有效的特征，完成數(shù)據(jù)的分類或者決策模型的優(yōu)化[6-7]。但是，模型由于應(yīng)用不同有序判別指標(biāo)，導(dǎo)致分類任務(wù)的效果有所不同。這三個(gè)指標(biāo)，在決策樹模型中應(yīng)用較多，例如經(jīng)典C4.5算法使用的評(píng)價(jià)指標(biāo)是信息增益，即互信息；CART決策樹使用的評(píng)價(jià)指標(biāo)是基尼不純度。在實(shí)際應(yīng)用中應(yīng)考慮有序特征評(píng)價(jià)指標(biāo)的選擇問題，文中主要針對(duì)這三個(gè)有序特征判別指標(biāo)進(jìn)行分析，以方便用戶更好的根據(jù)實(shí)際需求選擇必要的指標(biāo)，完成特征評(píng)價(jià)。

1　有序特征評(píng)價(jià)指標(biāo)

本文引入三個(gè)有序分類的特征評(píng)價(jià)指標(biāo)。它們是目前應(yīng)用比較廣泛的特征評(píng)價(jià)指標(biāo)，較好地反映兩個(gè)變量之間的排序一致性，即反映出變量值之間序的關(guān)系，特征值好的樣本應(yīng)該被分到好的類別中。

假設(shè)給定有序數(shù)據(jù)集U={x1,x2,…,xn}，特征集A={a1,a2,…,am},B?A，Y是一組類標(biāo)記，并且有yi是xi的類標(biāo)記。

1.1　有序條件熵

有序條件熵是胡清華教授等于2010年提出的用于有序分類的判別指標(biāo)，能夠反映特征值之間的序關(guān)系，用于評(píng)價(jià)特征質(zhì)量[6]。在香農(nóng)熵基礎(chǔ)上定義的有序條件熵，考慮了對(duì)象之間的序結(jié)構(gòu)，可以有效地度量特征和決策之間的排序一致性。由于繼承了香農(nóng)熵的魯棒性特點(diǎn)，使得單個(gè)噪聲樣本不會(huì)引起概率分布的變化。香農(nóng)熵是數(shù)據(jù)不確定性的度量，不確定程度越高，熵值越大。

有序條件熵是基于概率分布函數(shù)計(jì)算的，由于屬性值之間存在序關(guān)系，因此被分為向上的有序條件熵和向下的有序條件熵。給定屬性集C，且C?A，如果C已知的情況，B的不確定性信息表示為關(guān)于C的向上的有序條件熵或者是向下的有序條件熵，形式化定義如下[6]。

向上的有序條件熵：

向下的有序條件熵：

1.2　排序互信息

排序互信息的提出有效地改進(jìn)了有序條件熵，能夠有效地刻畫變量之間單調(diào)一致性程度，因此可以應(yīng)用于多標(biāo)準(zhǔn)決策屬性的相關(guān)性和依賴性分析，以及有序分類學(xué)習(xí)。排序互信息受互信息的啟發(fā)而提出，依據(jù)排序條件熵和排序熵的形式化定義推導(dǎo)產(chǎn)生。它反映了對(duì)象根據(jù)屬性值提供的信息進(jìn)行排序的一致性程度，而不是分類的一致性程度。

假設(shè)給定有序數(shù)據(jù)集U={x1,x2,…,xn}，包含屬性集A，其中B?A，C?A，數(shù)據(jù)集U關(guān)于B和C的排序互信息，形式化定義如下[6]。

向上的排序互信息：

向下的排序互信息：

1.3　排序基尼不純度

基尼不純度與熵都是數(shù)據(jù)不確定性的度量，兩者的主要區(qū)別是熵達(dá)到頂峰的過程要慢一些，熵對(duì)于混亂數(shù)據(jù)集合的判罰要更重一些?；岵患兌葘?lái)自集合的某種結(jié)果隨機(jī)應(yīng)用于某一數(shù)據(jù)項(xiàng)的預(yù)期誤差率，基尼不純度越小，純度越高，集合的有序程度越高，分類效果越好，它主要應(yīng)用于CART分類回歸樹。2015年，Masala受到排序互信息的啟發(fā)，基于基尼不純度提出了排序基尼不純度作為單調(diào)分類的判定指標(biāo)[7]。

排序基尼不純度使用優(yōu)勢(shì)集替代了傳統(tǒng)基尼不純度的等價(jià)類，形式化定義如下：給定有序數(shù)據(jù)集U={x1,x2,…,xn}，包含屬性集A，其中B?A，C?A，數(shù)據(jù)集U關(guān)于B的排序基尼不純度定義如下[7]。

向上的排序基尼不純度：

向下的排序基尼不純度：

如果C已知的情況下，關(guān)于B的向下排序基尼不純度形式化定義如下。

向上的有序條件基尼不純度：

向下的有序條件基尼不純度：

2　特征評(píng)價(jià)指標(biāo)的判別能力

為了對(duì)各項(xiàng)排序判別指標(biāo)有一個(gè)清晰的認(rèn)識(shí)，為不同排序判別指標(biāo)靈活運(yùn)用于不同業(yè)務(wù)領(lǐng)域提供借鑒，需要對(duì)排序指標(biāo)的判別能力做出分析和比較。下面通過算法1來(lái)判斷不同指標(biāo)是否能夠很好地去選擇屬性，并進(jìn)一步地發(fā)現(xiàn)單調(diào)函數(shù)以判別屬性與決策的單調(diào)性，挖掘潛在的偏好信息。算法1是基于C4.5提出的，通過獲得最好的特征來(lái)完成數(shù)據(jù)劃分，遞歸的生成決策樹，進(jìn)而產(chǎn)生可理解的決策規(guī)則。

圖1　不同指標(biāo)的排序判別能力

通過觀察圖1，可以清楚的看到判別指標(biāo)在三組不同數(shù)據(jù)上的變化情況，隨著非單調(diào)噪聲的增大各項(xiàng)判別指標(biāo)都在發(fā)生變化。排序互信息的值在下降，并且下降較快，有較強(qiáng)的判別能力；其次是排序條件熵的值在上升，并且上升較快，具有一定的判別能力；最后是排序基尼不純度的值也在隨著噪聲的增大而緩慢上升，表明其判別能力較好。

因此，這三項(xiàng)指標(biāo)都能夠有效地實(shí)現(xiàn)有序分類任務(wù)特征判別，然而排序條件熵和排序互信息對(duì)信息的混亂程度懲罰更重一些。在實(shí)際應(yīng)用中要根據(jù)數(shù)據(jù)的不同特點(diǎn)選擇合適的判別指標(biāo)，以獲得更好的分類效果。

3　實(shí)驗(yàn)分析

3.1　有序分類算法

通過設(shè)計(jì)的決策樹算法對(duì)三種指標(biāo)的評(píng)價(jià)效果做出分析，在真實(shí)的分類任務(wù)上進(jìn)行性能比較[8-9]。根據(jù)有序分類問題的特點(diǎn)，使用了平均絕對(duì)誤差對(duì)性能做出評(píng)價(jià)，可以看出基于排序互信息的決策樹算法在三種指標(biāo)中效果最好，排序條件熵和排序基尼不純度效果非常接近。因此，在實(shí)際應(yīng)用中，對(duì)于改進(jìn)的C4.5和CART決策樹中分別應(yīng)用排序互信息和排序基尼不純度將使得排序的一致性增強(qiáng)[10]。

有序決策樹算法1：

輸入：訓(xùn)練樣本集合，樣本用(A,D)來(lái)表述。停止參數(shù)：ε，L

輸出：有序決策樹。

// 根據(jù)不同判別指標(biāo)的定義，對(duì)于排序互信息和序條件熵計(jì)算最大值，排序基尼不純度計(jì)算最小值。

開始：

步驟1：生成決策樹根節(jié)點(diǎn)；

步驟2：如果剩余的樣本數(shù)小于L或者所有的樣本屬于同一類，則標(biāo)記為葉節(jié)點(diǎn)，返回；否則，執(zhí)行步驟3；

步驟3：對(duì)于每個(gè)屬性Ai對(duì)于每個(gè)分裂點(diǎn)Ai=a計(jì)算排序判別指標(biāo)的值，并得到每次的最大值(或最小值)對(duì)應(yīng)的分裂點(diǎn)以及最大值(或最小值)；

步驟4：選擇所有分裂點(diǎn)對(duì)應(yīng)的排序互信息的最大值或最小值)；

步驟5：如果最大值(或最小值)小于ε，則標(biāo)記葉節(jié)點(diǎn)，返回；否則繼續(xù)執(zhí)行步驟6；

步驟6：分裂點(diǎn)Aj=a劃分父節(jié)點(diǎn)為左右子節(jié)點(diǎn)；

步驟7：依據(jù)左右子節(jié)點(diǎn)，遞歸的構(gòu)造有序決策樹。

輸出：生成的有序決策樹

當(dāng)然，在實(shí)際分類任務(wù)中并不是所有的特征都是有序的，還存在部分有序的情況。對(duì)于這類問題，需要提出有效的有序分類特征選擇算法，從而選擇最好的特征完成數(shù)據(jù)劃分，這是一種較為合理的思路。文獻(xiàn)[4]中討論的齒輪裂紋的嚴(yán)重性識(shí)別任務(wù)，提到混合特征存在時(shí)的解決方案，通過設(shè)計(jì)特征選擇算法獲取分類能力較強(qiáng)的故障特征子集，進(jìn)而利用改進(jìn)的遺傳算法完成數(shù)據(jù)分類獲得了較好的效果。針對(duì)這類任務(wù)的算法設(shè)計(jì)，可以參照文獻(xiàn)[4]中的思路。

3.2　有序判別指標(biāo)的魯棒性分析

根據(jù)文獻(xiàn)[11]中提到的算法生成單調(diào)數(shù)據(jù)集，并設(shè)計(jì)實(shí)驗(yàn)來(lái)分析在不同的單調(diào)程度下判別指標(biāo)的排序性能，主要使用平均絕對(duì)誤差(MAE)來(lái)評(píng)價(jià),這是有序分類任務(wù)中的重要性能評(píng)價(jià)指標(biāo)。生成訓(xùn)練樣本600個(gè)，測(cè)試樣本120個(gè)，屬性5個(gè)，屬性取值個(gè)數(shù)為5，樣本共分為4類，其中測(cè)試樣本非單調(diào)性指標(biāo)(NMI)為0.2%。為了驗(yàn)證不同指標(biāo)的魯棒性，設(shè)置非單調(diào)性從0.2%逐步變化為1.2%，步長(zhǎng)0.2%。

根據(jù)圖2中的曲線走勢(shì)可以看出，不同指標(biāo)的性能隨著單調(diào)程度的增大而發(fā)生變化。從趨勢(shì)可以看出三種判別指標(biāo)變化較為平緩，性能較為穩(wěn)定，魯棒性較強(qiáng)。其中，有序條件熵與排序互信息的隨著非單調(diào)性的變化趨勢(shì)較為一致，主要是因?yàn)槎际且韵戕r(nóng)提出的信息熵為基礎(chǔ)的。排序基尼不純度變化也較為平緩，性能下降稍微明顯一些。

圖2　判別指標(biāo)的魯棒性分析

3.3　有序判別指標(biāo)在真實(shí)任務(wù)上的性能評(píng)價(jià)

本文利用算法1在UCI數(shù)據(jù)集上實(shí)驗(yàn)并分析對(duì)比[12]。使用三個(gè)向下的排序判別指標(biāo)分別訓(xùn)練，并且基于十折交叉驗(yàn)證技術(shù)計(jì)算平均絕對(duì)誤差(MAE)及標(biāo)準(zhǔn)差。

在表1中描述了三個(gè)向下的排序判別指標(biāo)在10個(gè)任務(wù)上的性能比較，其中每個(gè)數(shù)據(jù)集對(duì)應(yīng)的第一行表示十折交叉驗(yàn)證的平均絕對(duì)誤差(MAE)，第二行表示十折交叉驗(yàn)證的標(biāo)準(zhǔn)差。表1中的最后一行表示在10個(gè)分類任務(wù)上MAE的平均值。

表1　排序判別指標(biāo)在10個(gè)任務(wù)上的性能比較

通過表1中顯示的平均絕對(duì)誤差可以看出，排序互信息與排序條件熵在多數(shù)數(shù)據(jù)集上相同。然而對(duì)于10個(gè)數(shù)據(jù)集來(lái)說，排序條件熵與排序基尼不純度的平均值相同。排序互信息在10個(gè)數(shù)據(jù)集上的平均性能高出3個(gè)百分點(diǎn)。根據(jù)統(tǒng)計(jì)檢驗(yàn)確定不同判別指標(biāo)的平均性能是否存在顯著性差異，本文應(yīng)用t檢驗(yàn)兩兩比較了所有指標(biāo)的平均性能，進(jìn)而明確了排序互信息指標(biāo)存在的優(yōu)勢(shì)[15-16]。

根據(jù)以上的實(shí)驗(yàn)分析，可以清楚的看到三種有序分類判別指標(biāo)的效果，排序互信息具有很強(qiáng)的魯棒性，性能較好。排序基尼不純度在傳統(tǒng)的基尼不純度上提出，也大大增強(qiáng)了實(shí)際的有序分類效果，魯棒性較強(qiáng)。在現(xiàn)實(shí)生活中的有序分類任務(wù)有很多，可以根據(jù)三種有序判別指標(biāo)的特點(diǎn)進(jìn)行選擇，已達(dá)到預(yù)期效果和目標(biāo)。

4　結(jié)　語(yǔ)

根據(jù)有序分類任務(wù)的特點(diǎn)，對(duì)三類有序判別指標(biāo)的判別能力做出分析，給出不同任務(wù)下的平均絕對(duì)誤差，以此判斷三者的判別能力以及分類效果。對(duì)于包含噪聲的樣本，分別計(jì)算了三種有序判別指標(biāo)，結(jié)果顯示有序特征判別能力較強(qiáng)。然而，有序條件熵和有序排序互信息對(duì)混亂數(shù)據(jù)的懲罰更弱一些，并且性能更為接近。對(duì)三種指標(biāo)的魯棒性分析，顯示三種判別指標(biāo)度都較為魯棒，排序互信息繼承了互信息的魯棒性特點(diǎn)，排序基尼不純度繼承了基尼不純度的特點(diǎn)。通過判別指標(biāo)的比較及其在決策樹中的應(yīng)用，可輔助不同領(lǐng)域人員構(gòu)建適合需求的高效的有序分類模型，為從事相關(guān)研究工作的人員提供一定的參考。

[1] Greco S,Matarazzo B,Slowinski R.Customer satisfaction analysis based on rough set approach[J].Journal of Business Economics,2007,77(3):325-339.

[2] Tsumoto S.Mining Hierarchical Decision Rules from Clinical Databases Using Rough Sets and Medical Diagnostic Model[J].Information Sciences An International Journal,2004,162(2):65-80.

[3] Wang G,Ma J,Huang L,et al.Two credit scoring models based on dual strategy ensemble trees[J].Knowledge-Based Systems,2012,26:61-68.

[4] 潘巍巍,宋彥萍,于達(dá)仁.齒輪裂紋程度識(shí)別的有序分類算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2016(7):156-162.

[5] 李戰(zhàn)江,句芳,修長(zhǎng)柏,等.銀行信用風(fēng)險(xiǎn)小樣本評(píng)級(jí)模型的構(gòu)建[J].統(tǒng)計(jì)與決策,2016(9):39-43.

[6] Hu Q H,Guo M Z,Yu D R,et al.Information entropy for ordinal classification[J].Science China Information Sciences,2010,53(6):1188-1200.

[7] Marsala C,Petturiti D.Rank discrimination measures for enforcing monotonicity in decision tree induction[J].Information Sciences An International Journal,2015,291(C):143-171.

[8] 潘偉,佘堃.基于偏好不一致熵的有序決策[J].計(jì)算機(jī)應(yīng)用,2017,37(3):796-800.

[9] 王鑫,王熙照,陳建凱,等.有序決策樹的比較研究[J].計(jì)算機(jī)科學(xué)與探索,2013(11):1018-1025.

[10] Hu Q,Che X,Zhang L,et al.Rank Entropy Based Decision Trees for Monotonic Classification[J].IEEE Transactions on Knowledge & Data Engineering,2011,24(99):1-1.

[11] Milstein I,David A B,Potharst R.Generating noisy monotone ordinal datasets[J].Artificial Intelligence Research,2013,3(1).

[12] Bache K,Lichman M.UCI Machine Learning Repository[J].University of California Irvine School of Information,2013,2008(14/8).

[13] 陳建凱,王熙照,高相輝.改進(jìn)的基于排序熵的有序決策樹算法[J].模式識(shí)別與人工智能,2014(2):134-140.

[14] 鄭津楊,徐坤,李建強(qiáng).用于RFID系統(tǒng)數(shù)據(jù)處理的排序鄰居算法性能分析[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(12):207-210.

[15] 董躍華,劉力.基于均衡系數(shù)的決策樹優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(7):266-272.

[16] 石建國(guó).有序決策樹在大學(xué)生綜合素質(zhì)測(cè)評(píng)中的應(yīng)用研究[D].河北大學(xué),2015.