王雅輝，錢宇華，3*，劉郭慶

（1.山西大學(xué)大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院，太原 030006；2.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006；3.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)），太原 030006）

0 引言

有序分類是一種特殊的分類問題，其樣本的屬性具有線性結(jié)構(gòu)，類別取值D={ω1，ω2，…，ωc}之間存在偏序關(guān)系ω1?ω2?…?ωc［1］。如在員工績效考核問題中，將貢獻(xiàn)度、技能水平、績效作為績效考核的3 個(gè)重要指標(biāo)，其得分顯然存在序關(guān)系；員工績效考核的評(píng)定等級(jí)為“優(yōu)秀，良好，合格，基本合格”，它們之間存在優(yōu)劣次序。該問題的屬性（貢獻(xiàn)度，技能水平，績效）與類別（評(píng)定等級(jí)）之間存在這樣的單調(diào)性約束：當(dāng)一名員工在貢獻(xiàn)度、技能水平、績效這3 個(gè)屬性上的得分都高于其他員工時(shí)，該員工的評(píng)定等級(jí)一定高于其他員工。處理有序分類任務(wù)的關(guān)鍵在于從訓(xùn)練集中學(xué)習(xí)并生成單調(diào)的規(guī)則集，并利用屬性和類別之間的單調(diào)依賴關(guān)系來指導(dǎo)樣本的分類。有序分類問題在醫(yī)療診斷［2］、個(gè)人信譽(yù)評(píng)定［3］、欺詐公司判定［4］等許多領(lǐng)域都有廣泛應(yīng)用。

決策樹算法是一種重要的分類和回歸方法，具有分類速度快、準(zhǔn)確率高、可讀性強(qiáng)等特點(diǎn)，被廣泛應(yīng)用于醫(yī)學(xué)診斷、數(shù)據(jù)挖掘等任務(wù)中。在決策樹的構(gòu)建過程中通常使用一個(gè)函數(shù)作為評(píng)價(jià)指標(biāo)來選擇和評(píng)估特征，根據(jù)選擇的特征將每個(gè)節(jié)點(diǎn)中的樣本劃分為更細(xì)的子集。作為評(píng)價(jià)指標(biāo)常用的函數(shù)有基尼指數(shù)（Gini index）、卡方系數(shù)、信息增益、信息增益比等。將傳統(tǒng)的決策樹算法應(yīng)用到有序分類任務(wù)時(shí)存在以下兩方面問題：

1）傳統(tǒng)的決策樹算法無法反映訓(xùn)練數(shù)據(jù)中的序結(jié)構(gòu)。由香農(nóng)熵計(jì)算得到的信息增益及信息增益比在著名的決策樹算法ID3（Iterative Dichotomiser 3）及C4.5 中起著重要作用。實(shí)驗(yàn)表明，在構(gòu)建決策樹時(shí)，使用香農(nóng)熵的變形及由香農(nóng)熵誘導(dǎo)出的互信息作為選擇特征的評(píng)價(jià)指標(biāo)時(shí)的性能優(yōu)于Gini 和Dependency 度量，但香農(nóng)熵?zé)o法反映有序分類任務(wù)中訓(xùn)練數(shù)據(jù)的序結(jié)構(gòu)，即給定一個(gè)單調(diào)的數(shù)據(jù)集，學(xué)習(xí)到的規(guī)則集可能是非單調(diào)的規(guī)則集。該結(jié)果限制了傳統(tǒng)決策樹分類算法在有序分類任務(wù)中的應(yīng)用。

2）傳統(tǒng)的決策樹分類算法無法學(xué)習(xí)不精確知識(shí)。傳統(tǒng)的決策樹分類算法在假設(shè)樣本的屬性和類別取值確定的前提下，使用特征選擇函數(shù)建立一棵清晰樹。當(dāng)對(duì)象類別劃分不清晰時(shí)會(huì)引起模糊性、不確定性，在很多情況下，人類推理和概念構(gòu)造的知識(shí)都是模糊而非精確的，具有精確特征描述的清晰決策樹無法自動(dòng)獲取系統(tǒng)中的不精確知識(shí)。

針對(duì)上述問題，本文提出基于模糊優(yōu)勢(shì)互補(bǔ)互信息的有序分類決策樹構(gòu)建算法。Liang 等［5］提出互補(bǔ)熵的概念，互補(bǔ)熵的信息增益函數(shù)具有補(bǔ)集的性質(zhì)，因此能全面反映信息系統(tǒng)的信息含量，同時(shí)互補(bǔ)熵是一個(gè)模糊熵，能夠度量信息系統(tǒng)的隨機(jī)不確定性和模糊性不確定性。本文使用由互補(bǔ)熵誘導(dǎo)出的互補(bǔ)互信息，由于互補(bǔ)互信息無法學(xué)習(xí)數(shù)據(jù)集中的序關(guān)系，本文將等價(jià)類轉(zhuǎn)化為優(yōu)勢(shì)集，使用優(yōu)勢(shì)集表示數(shù)據(jù)集中的序結(jié)構(gòu)，同時(shí)引入模糊集的計(jì)算，形成模糊優(yōu)勢(shì)集。在模糊優(yōu)勢(shì)集及互補(bǔ)互信息的基礎(chǔ)上提出模糊優(yōu)勢(shì)互補(bǔ)互信息，并使用模糊優(yōu)勢(shì)互補(bǔ)互信息作為評(píng)價(jià)和選擇屬性的度量指標(biāo)設(shè)計(jì)有序分類決策樹算法。該算法能有效學(xué)習(xí)到數(shù)據(jù)集中的單調(diào)性規(guī)則集，并獲取數(shù)據(jù)集中模糊不確定性知識(shí)。

1 相關(guān)工作

有序分類又稱為單調(diào)性分類，或多標(biāo)準(zhǔn)決策分析［6］。目前，對(duì)有序分類問題的研究越來越受到學(xué)者們的重視，用于分類任務(wù)的粗糙集［7］、支持向量機(jī)［8］、神經(jīng)網(wǎng)絡(luò)［9］、集成決策樹［10］等算法被改進(jìn)后用于有序分類任務(wù)。Zhu等11］提出基于神經(jīng)網(wǎng)絡(luò)的有序分類算法，該算法是一個(gè)以單調(diào)關(guān)系為約束、以最小化訓(xùn)練誤差為目的的二次規(guī)劃方法。Cardoso 等［12］提出的large-margin方法將一個(gè)k分類問題簡化為k個(gè)二分類問題，再使用支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)對(duì)二分類問題進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，上述方法對(duì)有序分類任務(wù)有效，但由于神經(jīng)網(wǎng)絡(luò)和支持向量機(jī)對(duì)領(lǐng)域?qū)＜襾碚f很難理解，因此上述方法的可解釋性較低。Tang等［13］假設(shè)相似度高的樣本對(duì)具有相同的序關(guān)系，并以此來指導(dǎo)有序分類任務(wù)。Gonzalez 等［14］提出基于單調(diào)約束的集成剪枝算法，該算法的目的是在單調(diào)性模型的構(gòu)建與分類精度間進(jìn)行折中。Pinto Da Costa等［15］將k分類問題簡化為k-1個(gè)二分類問題后使用一般的分類方法學(xué)習(xí)這些二分類問題，但該算法在建模過程中沒有考慮單調(diào)性約束條件。

決策樹歸納學(xué)習(xí)算法是一種分類速度快、高效且易于理解的學(xué)習(xí)方法，代表性算法有ID3［16］、CART（Classification And Regression Tree）［17］等。傳統(tǒng)的決策樹學(xué)習(xí)算法沒有考慮單調(diào)性約束條件，因此對(duì)于給定的相同數(shù)據(jù)，可能會(huì)產(chǎn)生不同的決策樹?；谝陨蠁栴}，從單調(diào)數(shù)據(jù)集中提取單調(diào)的規(guī)則集已成為機(jī)器學(xué)習(xí)和決策分析領(lǐng)域的研究熱點(diǎn)。很多學(xué)者針對(duì)決策樹學(xué)習(xí)算法做出了改進(jìn)，使其能夠抽取數(shù)據(jù)中的單調(diào)規(guī)則集從而應(yīng)用于有序分類任務(wù)中。Feelders等［18］提出了一系列剪枝技術(shù)，通過剪枝可以使非單調(diào)的決策樹變成單調(diào)的決策樹；Verbeke等［19］提出單調(diào)有序規(guī)則歸納算法，并與決策樹歸納算法結(jié)合用于有序分類任務(wù)；Xia等［20］提出的Ranking Impurity方法將CART 中使用的基尼指數(shù)擴(kuò)展到有序分類任務(wù)上。上述算法雖然可以從數(shù)據(jù)中提取序信息，但是給定一個(gè)單調(diào)的訓(xùn)練數(shù)據(jù)集時(shí)，構(gòu)造出來的決策樹依然不一定是單調(diào)的決策樹。對(duì)于數(shù)值數(shù)據(jù)的有序分類問題，Hu等［21］提出單調(diào)決策樹算法，該算法在香農(nóng)熵的基礎(chǔ)上引入序的關(guān)系提出排序熵的概念，在一定程度上解決了單調(diào)性和泛化能力之間的沖突。在排序熵的基礎(chǔ)上設(shè)計(jì)了基于有序排序熵的單調(diào)決策樹（Rank Entropy based Monotonic decision Tree，REMT）算法，該算法被應(yīng)用于故障程度診斷［22］中。REMT 算法能學(xué)習(xí)到簡單且易于理解的規(guī)則集，但得到的精度相對(duì)有限。許行等［23］設(shè)計(jì)采樣策略來構(gòu)造決策樹算法，該策略考慮了數(shù)據(jù)集中的單調(diào)一致性的特點(diǎn)，可以避免非單調(diào)數(shù)據(jù)的噪聲影響。

2 信息熵

香農(nóng)引入熱力學(xué)中熵的概念來度量一個(gè)系統(tǒng)的不確定性，香農(nóng)熵及其變形被廣泛用來度量信息系統(tǒng)的混亂程度，著名的決策樹算法ID3、C4.5 都使用了香農(nóng)信息熵作為特征選擇的評(píng)價(jià)指標(biāo)。香農(nóng)熵定義如下：

定義1給定樣本集U及屬性集A，B?A是一個(gè)屬性子集，得到一組等價(jià)類：U/IND={X1，X2，…，Xn}。關(guān)于屬性子集B的互補(bǔ)熵定義為：

與香農(nóng)熵使用對(duì)數(shù)變換不同，互補(bǔ)熵從信息增益的補(bǔ)集出發(fā)，能全面度量信息系統(tǒng)的信息含量。與香農(nóng)熵類似，根據(jù)互補(bǔ)熵可以誘導(dǎo)出互補(bǔ)互信息的定義。互補(bǔ)互信息不僅度量了信息系統(tǒng)中兩組等價(jià)類的一致性，還度量了兩組等價(jià)類的補(bǔ)集的一致性。因此，互補(bǔ)互信息比由香農(nóng)熵誘導(dǎo)出的互信息能更加全面有效地評(píng)估屬性的重要性。互補(bǔ)熵和互補(bǔ)互信息的定義如下。

定義2給定樣本集U及屬性集A，B?A是一個(gè)屬性子集，得到一組等價(jià)類：U/IND={X1，X2，…，Xm}。關(guān)于屬性子集B的互補(bǔ)熵定義為：

其中：表示等價(jià)類Xi的補(bǔ)集；|Xi|/|U|表示等價(jià)類Xi在樣本集U中發(fā)生的概率；||/|U|表示等價(jià)類Xi的補(bǔ)集在樣本集U中發(fā)生的概率。

定義3給定樣本集U及屬性集A，B?A是一個(gè)屬性子集，決策集D={Y1，Y2，…，Yn}，屬性子集B和決策集D之間的互補(bǔ)互信息定義為：

3 模糊優(yōu)勢(shì)互補(bǔ)互信息

3.1 優(yōu)勢(shì)集

傳統(tǒng)的決策樹算法學(xué)習(xí)到的是數(shù)據(jù)集中的一致性，即具有相同屬性取值的樣本應(yīng)分為同一類，而有序分類任務(wù)的分類器將擁有好的屬性取值的樣本分在好的類別中。從互補(bǔ)互信息的定義來看，其建立在等價(jià)類的基礎(chǔ)上，對(duì)于含有順序信息的信息系統(tǒng)而言，互補(bǔ)互信息無法學(xué)習(xí)數(shù)據(jù)集中的序結(jié)構(gòu)并保持特征和類別之間的單調(diào)一致性，無法有效度量序信息系統(tǒng)的不確定性。因此互補(bǔ)互信息無法直接用于有序分類任務(wù)。優(yōu)勢(shì)粗糙集是處理有序分類問題的有效方法，可以從有序數(shù)據(jù)集中抽取有序的分類規(guī)則，因此，本文使用優(yōu)勢(shì)集表示數(shù)據(jù)中的序關(guān)系。優(yōu)勢(shì)集定義如下：

定義4給定樣本集U及屬性集A，x為樣本集中的一個(gè)樣本，a∈A是樣本的一個(gè)屬性，關(guān)于樣本x的優(yōu)勢(shì)集定義如下：

下面使用例1來說明優(yōu)勢(shì)集的計(jì)算方法及作用。

例1 如表1 所示，給出10 個(gè)樣本，a為樣本的屬性，決策集D={1，2，3}。以樣本x4為例，根據(jù)式（4）和指示函數(shù)可以得到兩個(gè)清晰的集合

表1 例1中十個(gè)有序分類樣本Tab.1 Ten ordinal classification samples in example 1

3.2 模糊優(yōu)勢(shì)集

模糊數(shù)學(xué)是研究模糊現(xiàn)象的學(xué)科，所研究的事物概念本身是模糊而非清晰的，具有模糊性的概念無法用精準(zhǔn)的標(biāo)準(zhǔn)來衡量，即一個(gè)對(duì)象是否屬于這個(gè)概念難以確定，如不能用人的頭發(fā)數(shù)量來劃分“禿”與“不禿”。因此不能用取值為0～1的指示函數(shù)表示一個(gè)樣本是否屬于某個(gè)模糊集合。描述一個(gè)樣本與模糊集合之間的關(guān)系時(shí)可以用［0，1］區(qū)間上的實(shí)數(shù)進(jìn)行度量，即隸屬度。隸屬函數(shù)是用來表征模糊集合的數(shù)學(xué)工具，描述元素u與集合U上一個(gè)模糊集合的隸屬關(guān)系。本文使用隸屬函數(shù)對(duì)優(yōu)勢(shì)集進(jìn)行計(jì)算，形成模糊優(yōu)勢(shì)集。模糊優(yōu)勢(shì)集定義如下。

定義5給定樣本集合U及屬性集A，xi為樣本集中的一個(gè)樣本，a∈A是樣本的一個(gè)屬性，關(guān)于樣本xi的模糊優(yōu)勢(shì)集定義如下：

其中，rji和sji由隸屬函數(shù)計(jì)算得到，所用隸屬函數(shù)如式（6）所示：

rji和sji的計(jì)算方法如下：

使用模糊優(yōu)勢(shì)集表示數(shù)據(jù)的序關(guān)系時(shí)，不僅可以得到a(x) ≤a(y)或a(x) ≥a(y)，還可以得到a(x)與a(y)之間相差的程度。

例1中樣本x4的模糊優(yōu)勢(shì)集合為：

3.3 模糊優(yōu)勢(shì)互補(bǔ)互信息

在互補(bǔ)互信息及模糊優(yōu)勢(shì)集的基礎(chǔ)上，本文提出模糊優(yōu)勢(shì)互補(bǔ)互信息，模糊優(yōu)勢(shì)互補(bǔ)互信息定義如下：

定義6給定樣本集U及屬性集合A，B∈A，C∈A，則B和C的模糊優(yōu)勢(shì)互補(bǔ)互信息定義為：

使用下面的例子說明模糊優(yōu)勢(shì)集的作用及模糊優(yōu)勢(shì)互補(bǔ)互信息的有效性。

例2 給出5個(gè)樣本進(jìn)行有序分類任務(wù)，樣本有a1和a2兩個(gè)屬性，屬性a1取值離散，取值范圍為{1，2，3}，屬性a2取值連續(xù)，決策集D={1，2，3}，樣本數(shù)據(jù)如表2所示。

表2 例2中有序分類任務(wù)Tab.2 Ordinal classification task in example 2

對(duì)于表2 中給出的數(shù)據(jù)樣本，首先使用式（2）分別計(jì)算按屬性a1和a2劃分?jǐn)?shù)據(jù)集時(shí)的互補(bǔ)熵：

通過計(jì)算可以得到E(a1；D)=E(a2；D)，說明若使用互補(bǔ)熵作為劃分?jǐn)?shù)據(jù)集的評(píng)價(jià)指標(biāo)，則用屬性a1或?qū)傩詀2劃分?jǐn)?shù)據(jù)集的分類結(jié)果一樣好。再使用式（8）分別計(jì)算屬性a1和a2與決策集D之間的模糊優(yōu)勢(shì)互補(bǔ)互信息，計(jì)算結(jié)果如下：

從計(jì)算中得出FACMI>(a1；D) (a2；D)，說明若使用模糊優(yōu)勢(shì)互補(bǔ)互信息作為評(píng)價(jià)指標(biāo)來指導(dǎo)數(shù)據(jù)集的劃分時(shí)，使用屬性a2來劃分?jǐn)?shù)據(jù)集的分類結(jié)果更好。使用模糊優(yōu)勢(shì)互補(bǔ)互信息作為評(píng)價(jià)指標(biāo)，分別使用屬性a1和a2劃分?jǐn)?shù)據(jù)集的劃分結(jié)果圖1所示。

圖1 按屬性a1或a2劃分?jǐn)?shù)據(jù)集Fig.1 Dividing dataset by attributes a1 or a2

從圖1可以看出，根據(jù)屬性a1劃分?jǐn)?shù)據(jù)集時(shí)，分類任務(wù)的準(zhǔn)確率為80%，根據(jù)屬性a2劃分?jǐn)?shù)據(jù)集時(shí)，分類任務(wù)的準(zhǔn)確率為100%，說明使用屬性a2劃分?jǐn)?shù)據(jù)集的結(jié)果更好，這符合使用模糊優(yōu)勢(shì)互補(bǔ)互信息的計(jì)算結(jié)果。使用模糊優(yōu)勢(shì)互補(bǔ)互信息作為評(píng)價(jià)指標(biāo)來指導(dǎo)決策樹的構(gòu)建是有效的且效果優(yōu)于使用互補(bǔ)熵作為評(píng)價(jià)指標(biāo)的分類結(jié)果。

3.4 有序分類決策樹的構(gòu)建

本文對(duì)互補(bǔ)互信息進(jìn)行了拓展，使用優(yōu)勢(shì)集來度量數(shù)據(jù)的序關(guān)系，并引入模糊集對(duì)優(yōu)勢(shì)集進(jìn)行計(jì)算以形成模糊優(yōu)勢(shì)集，提出了模糊優(yōu)勢(shì)互補(bǔ)互信息。本節(jié)使用模糊優(yōu)勢(shì)互補(bǔ)互信息作為啟發(fā)式來構(gòu)建有序分類決策樹，設(shè)計(jì)基于模糊優(yōu)勢(shì)互補(bǔ)互信息的有序決策樹（Fuzzy Advantage Complementary Mutual Information based decision tree，F(xiàn)ACMI）算法并分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

3.4.1 FACMI算法

FACMI算法的偽代碼如下。

FACMI 算法將模糊優(yōu)勢(shì)互補(bǔ)互信息作為分裂準(zhǔn)則，節(jié)點(diǎn)選擇劃分?jǐn)?shù)據(jù)集的分裂屬性時(shí)，根據(jù)模糊優(yōu)勢(shì)互補(bǔ)互信息選擇與類標(biāo)簽單調(diào)一致性高的屬性，這樣能夠充分利用先驗(yàn)知識(shí)來生成更簡單、泛化能力更強(qiáng)的樹。

FACMI算法首先判斷決策樹當(dāng)前節(jié)點(diǎn)中的樣本個(gè)數(shù)和類別個(gè)數(shù)，若當(dāng)前節(jié)點(diǎn)中只有一個(gè)樣本或只有一個(gè)類別，則決策樹停止生長，否則開始劃分該節(jié)點(diǎn)：

1）計(jì)算現(xiàn)有特征對(duì)數(shù)據(jù)集的模糊優(yōu)勢(shì)互補(bǔ)互信息（FACMI），對(duì)每個(gè)特征Ai的每個(gè)可能取值cj計(jì)算Ai=cj時(shí)的模糊優(yōu)勢(shì)互補(bǔ)互信息。

2）在所有屬性及其所有切分點(diǎn)中，選擇FACMI 值最大的屬性及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)屬性A及最優(yōu)切分點(diǎn)c*，若屬性A對(duì)數(shù)據(jù)集的模糊優(yōu)勢(shì)互補(bǔ)互信息FACMI(A)小于閾值threshold，則決策樹停止生長；否則，根據(jù)最優(yōu)屬性及最優(yōu)切分點(diǎn)將該節(jié)點(diǎn)的樣本分裂到兩個(gè)子節(jié)點(diǎn)中。

3）對(duì)兩個(gè)子節(jié)點(diǎn)遞歸的調(diào)用步驟1）和2），直到滿足停止條件時(shí)算法運(yùn)行結(jié)束。

3.4.2 算法性能分析

FACMI 算法的時(shí)間復(fù)雜度和空間復(fù)雜度分為兩部分，其中，N為數(shù)據(jù)集中的樣本個(gè)數(shù)，M為樣本屬性個(gè)數(shù)，Split為所有屬性取值個(gè)數(shù)的平均值，D為決策樹高度：

1）時(shí)間復(fù)雜度。構(gòu)建決策樹的時(shí)間復(fù)雜度為O(NMD)，計(jì)算模糊優(yōu)勢(shì)互補(bǔ)互信息的時(shí)間復(fù)雜度為O(N2)。

2）空間復(fù)雜度。構(gòu)建決策樹的時(shí)間復(fù)雜度為O(N+M*Split)，計(jì)算模糊優(yōu)勢(shì)互補(bǔ)互信息的時(shí)間復(fù)雜度為O(N)。

4 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的基于模糊優(yōu)勢(shì)互補(bǔ)互信息的有序分類決策樹（FACMI）算法的有效性，分別在5個(gè)人工數(shù)據(jù)以及9個(gè)現(xiàn)實(shí)數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)，將FACMI 算法與經(jīng)典的決策樹分類算法進(jìn)行比較。

實(shí)驗(yàn)設(shè)備為1 臺(tái)配置為3.60 GHz-4 核GPU、8 GB 內(nèi)存的計(jì)算機(jī)，實(shí)驗(yàn)平臺(tái)為Matlab R2020a，實(shí)驗(yàn)參數(shù)threshold設(shè)置為0.01。

4.1 評(píng)價(jià)指標(biāo)

本文實(shí)驗(yàn)在每個(gè)數(shù)據(jù)集上進(jìn)行五折交叉驗(yàn)證，使用平均絕對(duì)誤差（Mean Absolute Error，MAE）度量決策樹算法的分類能力，MAE定義為：

其中：N表示測試集樣本數(shù)量，yi表示樣本xi的實(shí)際類標(biāo)簽表示樣本xi在分類器上的預(yù)測類標(biāo)簽。

4.2 人工數(shù)據(jù)實(shí)驗(yàn)

本節(jié)實(shí)驗(yàn)測試FACMI 算法在人工數(shù)據(jù)集上的分類性能，使用式（10）［21］生成單調(diào)數(shù)據(jù)集：

其中：x1和x2為取值范圍在[0，1]區(qū)間且滿足均勻分布的兩個(gè)隨機(jī)變量，作為數(shù)據(jù)集的兩個(gè)屬性；將函數(shù)值f(x1，x2)歸一化后進(jìn)行離散化：D∈{0，1/k，2/k，…，1}，其中k為類別個(gè)數(shù)，由此得到k類單調(diào)分類問題。

4.2.1 人工數(shù)據(jù)集上樣本數(shù)量對(duì)算法性能影響

本節(jié)實(shí)驗(yàn)使用人工數(shù)據(jù)集測試樣本數(shù)量對(duì)FACMI 算法分類性能的影響，并與經(jīng)典決策樹算法CART、使用改進(jìn)之前的互補(bǔ)互信息作為評(píng)價(jià)指標(biāo)的決策樹分類算法（Information Entropy，IE）以及有序決策樹算法（Rank Tree，RT）［20］進(jìn)行對(duì)比。所用數(shù)據(jù)集由式（10）生成，樣本數(shù)量為1 000，類別個(gè)數(shù)k=4，其散點(diǎn)圖如圖2（b）所示。

圖2 人工數(shù)據(jù)集Fig.2 Synthetic datasets

4.2.2 人工數(shù)據(jù)集上樣本數(shù)量對(duì)算法性能影響

實(shí)驗(yàn)中隨機(jī)抽取4～36個(gè)樣本作訓(xùn)練集，保證每次抽取時(shí)4個(gè)類別的樣本都能取到，其余樣本作測試集。隨著樣本數(shù)量的增加，分別計(jì)算3個(gè)算法的平均絕對(duì)誤差。實(shí)驗(yàn)重復(fù)100次，取絕對(duì)誤差的平均值作為實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 人工數(shù)據(jù)集上的平均絕對(duì)誤差Fig.3 Mean absolute errors on synthetic datasets

從圖3 可以看出，在4 分類單調(diào)分類任務(wù)上，樣本數(shù)量越多，各算法的分類誤差越低，4 個(gè)分類算法的分類能力越接近，F(xiàn)ACMI 算法始終獲得最低的分類誤差。樣本數(shù)量越少FACMI 算法的優(yōu)勢(shì)越明顯。實(shí)驗(yàn)結(jié)果表明FACMI 與其他算法相比能更好地反映數(shù)據(jù)中的序關(guān)系并指導(dǎo)樣本分類。

4.2.3 人工數(shù)據(jù)集上樣本類別數(shù)量對(duì)算法性能影響

本節(jié)實(shí)驗(yàn)使用人工數(shù)據(jù)集測試數(shù)據(jù)類別數(shù)量對(duì)分類器分類性能的影響。根據(jù)式（10）生成數(shù)據(jù)集，類別個(gè)數(shù)分別為k=2，4，6，8，10。使用生成的數(shù)據(jù)集分別在FACMI、CART、ID3、C4.5、使用改進(jìn)前的互補(bǔ)互信息作為評(píng)價(jià)指標(biāo)的決策樹算法（IE）以及有序決策樹RT 算法［20］上進(jìn)行實(shí)驗(yàn)。將MAE 作為分類算法性能的評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)重復(fù)100次，取100次實(shí)驗(yàn)的平均MAE作為最終的實(shí)驗(yàn)結(jié)果，如表3所示。

表3 不同類別數(shù)量數(shù)據(jù)集上的平均絕對(duì)誤差Tab.3 Mean absolute errors on datasets with different category numbers

從表3 中可以看出，在單調(diào)分類任務(wù)上，樣本類別數(shù)量越多各算法的絕對(duì)誤差越大。FACMI算法在不同類別數(shù)量的單調(diào)分類任務(wù)上的分類性能都優(yōu)于其余算法，表明FACMI 算法在人工構(gòu)造的單調(diào)分類任務(wù)上是有效的。類別個(gè)數(shù)為10 時(shí)，F(xiàn)ACMI算法的分類誤差與其余算法的分類誤差相差最大。

4.3 現(xiàn)實(shí)數(shù)據(jù)集實(shí)驗(yàn)

除人工數(shù)據(jù)外，本文還在表4 所示的9 個(gè)數(shù)據(jù)集上驗(yàn)證FACMI 算法的有效性。9 個(gè)數(shù)據(jù)集中的數(shù)據(jù)收集于現(xiàn)實(shí)生活中的應(yīng)用場景，能更好地測試FACMI 算法在現(xiàn)實(shí)應(yīng)用問題中的泛化性能，其中，Diabetes、Segement、Squash 數(shù)據(jù)集來自Weka（https：//www.cs.waikato.ac.nz/ml/weka/），其余6 個(gè)為UCI（http：//archive.ics.uci.edu/ml/datasets.php）數(shù)據(jù)集。Car為符號(hào)型數(shù)據(jù)集，Diabetes、Segment、Balance 為既包含符號(hào)型也包含數(shù)值型特征的數(shù)據(jù)集，其余5 個(gè)為數(shù)值型數(shù)據(jù)。在構(gòu)建有序分類決策樹時(shí)，需要保持特征取值和決策集之間的單調(diào)一致性，即特征取值與決策集之間呈正相關(guān)。因此，在使用9 個(gè)現(xiàn)實(shí)數(shù)據(jù)集訓(xùn)練有序決策樹之前，需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將單調(diào)遞減的特征通過計(jì)算其取值的倒數(shù)轉(zhuǎn)換為單調(diào)遞增的特征。

表4 九個(gè)現(xiàn)實(shí)數(shù)據(jù)集的基本信息Tab.4 Basic information of nine real datasets

4.3.1 現(xiàn)實(shí)數(shù)據(jù)集上樣本數(shù)量對(duì)算法性能的影響

本節(jié)實(shí)驗(yàn)使用現(xiàn)實(shí)數(shù)據(jù)集測試樣本數(shù)量對(duì)FACMI 分類性能的影響。對(duì)每一個(gè)數(shù)據(jù)集取不同的樣本個(gè)數(shù)，分別計(jì)算在FACMI、經(jīng)典的決策樹算法CART、ID3、C4.5、IE 以及RT 算法［20］上的平均絕對(duì)誤差（MAE）。使用五折交叉驗(yàn)證，實(shí)驗(yàn)重復(fù)100 次，取平均MAE 作為最終的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同樣本數(shù)量在不同數(shù)據(jù)集上的平均絕對(duì)誤差Fig.4 Mean absolute errors with different sample sizes on different datasets

從實(shí)驗(yàn)結(jié)果可以看出，在現(xiàn)實(shí)的單調(diào)分類任務(wù)上，隨著樣本數(shù)量的增加，6 個(gè)算法的平均絕對(duì)誤差呈下降趨勢(shì)，F(xiàn)ACMI算法的誤差始終低于其余5 個(gè)算法。樣本量越少，F(xiàn)ACMI 算法與其余5 個(gè)算法的誤差相差越大。在Wine、Wine Quality、EEG 數(shù)據(jù)集上，各算法的分類性能相近，在Balance、Segment以及Squash 這5 個(gè)數(shù)據(jù)集上，F(xiàn)ACMI 算法的優(yōu)勢(shì)更加明顯。從圖4 中可以看出，在Segment、Squash 數(shù)據(jù)集上，樣本數(shù)量對(duì)FACMI算法分類性能的影響與其余算法相比相對(duì)較小。實(shí)驗(yàn)結(jié)果表明，F(xiàn)ACMI算法在現(xiàn)實(shí)單調(diào)分類任務(wù)上是有效的。

4.3.2 現(xiàn)實(shí)數(shù)據(jù)集上算法性能

本節(jié)實(shí)驗(yàn)使用數(shù)據(jù)集中的全部數(shù)據(jù)測試FACMI 算法的分類能力，將FACMI 算法與經(jīng)典決策樹算法、RT 算法［20］及REMT（Rank Entropy based Monotonic decision Tree）［21］進(jìn)行對(duì)比。使用平均絕對(duì)誤差度量算法的分類性能。每個(gè)數(shù)據(jù)集中80%的數(shù)據(jù)用作訓(xùn)練集，其余樣本為測試集，在每個(gè)數(shù)據(jù)集上進(jìn)行五折交叉驗(yàn)證，實(shí)驗(yàn)重復(fù)100次，取平均MAE作為實(shí)驗(yàn)結(jié)果。7個(gè)算法在9個(gè)現(xiàn)實(shí)數(shù)據(jù)集上的分類誤差如表5所示。

表5 九個(gè)現(xiàn)實(shí)數(shù)據(jù)集上的平均絕對(duì)誤差Tab.5 Mean absolute errors on 9 real datasets

根據(jù)實(shí)驗(yàn)結(jié)果，在現(xiàn)實(shí)單調(diào)分類任務(wù)上，除Breast、Wine Quality、Segment 數(shù)據(jù)集外，F(xiàn)ACMI 算法分類能力都優(yōu)于其他算法。在Segment、Banlance、Car這3個(gè)數(shù)據(jù)集上，F(xiàn)ACMI算法的損失明顯低于其余6 個(gè)算法。每個(gè)數(shù)據(jù)集上分類能力最好的算法已用加粗突出顯示。

4.4 傳統(tǒng)非有序分類任務(wù)上算法性能

本節(jié)實(shí)驗(yàn)測試FACMI 算法在傳統(tǒng)的非有序分類任務(wù)上的分類性能。使用表4 中未被單調(diào)化預(yù)處理過的9 個(gè)數(shù)據(jù)集作為非有序任務(wù)數(shù)據(jù)集，將FACMI 算法與傳統(tǒng)決策樹算法、RT算法進(jìn)行對(duì)比。使用平均絕對(duì)誤差度量算法性能，在數(shù)據(jù)集上使用五折交叉驗(yàn)證，取100 次實(shí)驗(yàn)的平均MAE 作為實(shí)驗(yàn)結(jié)果，如表6所示。

表6 非有序任務(wù)上的平均絕對(duì)誤差Tab.6 Mean absolute errors of non-ordinal tasks

根據(jù)表6 中實(shí)驗(yàn)結(jié)果可以看出，除數(shù)據(jù)集Wine 和Wine Quality 外，F(xiàn)ACMI 算法在其余數(shù)據(jù)集上取得最低的平均絕對(duì)誤差。

對(duì)比表5和表6，F(xiàn)ACMI算在非有序分類任務(wù)上的損失高于在有序分類任務(wù)上的損失，由此可得，相較于非有序分類任務(wù)，F(xiàn)ACMI算法在有序分類任務(wù)上的性能更好。

4.5 結(jié)果分析

從上述實(shí)驗(yàn)結(jié)果中可以看出，在人工數(shù)據(jù)集和現(xiàn)實(shí)數(shù)據(jù)集上，本文提出的FACMI 算法的分類能力與其余算法相比相對(duì)較好。這是因?yàn)樵撍惴紤]了特征取值與決策集之間的單調(diào)關(guān)系：不僅度量了特征與決策集之間的單調(diào)關(guān)系，還度量了每個(gè)特征取值的補(bǔ)集與決策集之間的單調(diào)關(guān)系，因此該算法從數(shù)據(jù)中獲得了更多的先驗(yàn)知識(shí)。FACMI算法將樣本的特征值模糊化后再處理，有利于學(xué)習(xí)數(shù)據(jù)中的不精確知識(shí)，獲得更多的有效信息指導(dǎo)樣本的分類。

5 結(jié)語

有序分類是決策分析中的一類重要任務(wù)，該任務(wù)利用從樣本屬性和決策集中學(xué)到的序關(guān)系來指導(dǎo)樣本分類。高效且分類速度快的決策樹算法在一般分類任務(wù)中應(yīng)用廣泛，決策樹算法中評(píng)價(jià)指標(biāo)的選擇對(duì)決策樹算法的性能有一定影響。許多決策樹算法使用香農(nóng)熵作為評(píng)價(jià)指標(biāo)，但香農(nóng)熵?zé)o法表示數(shù)據(jù)中的序關(guān)系且無法度量數(shù)據(jù)的模糊性，因此在有序分類任務(wù)上性能相較一般分類任務(wù)而言較差。互補(bǔ)熵能彌補(bǔ)香農(nóng)熵非模糊熵的性質(zhì)，本文使用由互補(bǔ)熵誘導(dǎo)出的互補(bǔ)互信息作為決策樹評(píng)價(jià)指標(biāo)，用優(yōu)勢(shì)集表示數(shù)據(jù)中的序信息，并引入模糊集將清晰樹推廣為模糊樹，提出了基于模糊優(yōu)勢(shì)互補(bǔ)互信息的有序分類決策樹算法。實(shí)驗(yàn)結(jié)果表明，該算法在有序分類任務(wù)上的分類能力優(yōu)于經(jīng)典決策樹。在監(jiān)督學(xué)習(xí)中，訓(xùn)練數(shù)據(jù)所對(duì)應(yīng)的標(biāo)簽質(zhì)量對(duì)于學(xué)習(xí)效果至關(guān)重要。如果學(xué)習(xí)時(shí)使用噪聲標(biāo)簽，可能會(huì)訓(xùn)練不出有效的預(yù)測模型。但是由于人類認(rèn)知限制、自然因素限制、成本限制等原因，噪聲往往是不可避免的。在接下來的工作中，我們將考慮通過FACMI 算法與標(biāo)簽噪聲過濾方法［22-24］相結(jié)合，以進(jìn)一步提高FACMI算法的分類性能，增強(qiáng)分類器的魯棒性。