基于模糊優(yōu)勢互補互信息的有序決策樹算法

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

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

0 引言

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

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

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

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

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

1 相關工作

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

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

2 信息熵

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

定義1給定樣本集U及屬性集A，B?A是一個屬性子集，得到一組等價類：U/IND={X1，X2，…，Xn}。關于屬性子集B的互補熵定義為：

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

定義2給定樣本集U及屬性集A，B?A是一個屬性子集，得到一組等價類：U/IND={X1，X2，…，Xm}。關于屬性子集B的互補熵定義為：

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

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

3 模糊優(yōu)勢互補互信息

3.1 優(yōu)勢集

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

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

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

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

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

3.2 模糊優(yōu)勢集

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

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

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

rji和sji的計算方法如下：

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

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

3.3 模糊優(yōu)勢互補互信息

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

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

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

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

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

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

通過計算可以得到E(a1；D)=E(a2；D)，說明若使用互補熵作為劃分數(shù)據(jù)集的評價指標，則用屬性a1或屬性a2劃分數(shù)據(jù)集的分類結果一樣好。再使用式（8）分別計算屬性a1和a2與決策集D之間的模糊優(yōu)勢互補互信息，計算結果如下：

從計算中得出FACMI>(a1；D) (a2；D)，說明若使用模糊優(yōu)勢互補互信息作為評價指標來指導數(shù)據(jù)集的劃分時，使用屬性a2來劃分數(shù)據(jù)集的分類結果更好。使用模糊優(yōu)勢互補互信息作為評價指標，分別使用屬性a1和a2劃分數(shù)據(jù)集的劃分結果圖1所示。

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

從圖1可以看出，根據(jù)屬性a1劃分數(shù)據(jù)集時，分類任務的準確率為80%，根據(jù)屬性a2劃分數(shù)據(jù)集時，分類任務的準確率為100%，說明使用屬性a2劃分數(shù)據(jù)集的結果更好，這符合使用模糊優(yōu)勢互補互信息的計算結果。使用模糊優(yōu)勢互補互信息作為評價指標來指導決策樹的構建是有效的且效果優(yōu)于使用互補熵作為評價指標的分類結果。

3.4 有序分類決策樹的構建

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

3.4.1 FACMI算法

FACMI算法的偽代碼如下。

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

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

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

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

3）對兩個子節(jié)點遞歸的調用步驟1）和2），直到滿足停止條件時算法運行結束。

3.4.2 算法性能分析

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

1）時間復雜度。構建決策樹的時間復雜度為O(NMD)，計算模糊優(yōu)勢互補互信息的時間復雜度為O(N2)。

2）空間復雜度。構建決策樹的時間復雜度為O(N+M*Split)，計算模糊優(yōu)勢互補互信息的時間復雜度為O(N)。

4 實驗與結果分析

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

實驗設備為1 臺配置為3.60 GHz-4 核GPU、8 GB 內存的計算機，實驗平臺為Matlab R2020a，實驗參數(shù)threshold設置為0.01。

4.1 評價指標

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

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

4.2 人工數(shù)據(jù)實驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5 結果分析

從上述實驗結果中可以看出，在人工數(shù)據(jù)集和現(xiàn)實數(shù)據(jù)集上，本文提出的FACMI 算法的分類能力與其余算法相比相對較好。這是因為該算法考慮了特征取值與決策集之間的單調關系：不僅度量了特征與決策集之間的單調關系，還度量了每個特征取值的補集與決策集之間的單調關系，因此該算法從數(shù)據(jù)中獲得了更多的先驗知識。FACMI算法將樣本的特征值模糊化后再處理，有利于學習數(shù)據(jù)中的不精確知識，獲得更多的有效信息指導樣本的分類。

5 結語

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