多類分類模型和多層次增量算法*

徐 怡，王旭生

1.安徽大學(xué) 計算智能與信號處理教育部重點實驗室，合肥 230039

2.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601

1 引言

三支決策作為決策粗糙集和粒計算理論的一個重要應(yīng)用方向[1-2]，是研究不確定性決策的有力工具，廣泛應(yīng)用于知識發(fā)現(xiàn)、數(shù)據(jù)挖掘和模式識別等領(lǐng)域[3-5]。相比于傳統(tǒng)的二支決策，三支決策的關(guān)鍵是引入了延遲決策，從而規(guī)避了錯誤決策造成的損失。當(dāng)做出延遲決策時，為了下一次做出準(zhǔn)確決策，需要進一步采集決策的狀態(tài)信息，即對決策對象的認識從粗粒度向細粒度進行轉(zhuǎn)化。這種從粗粒度到細粒度的決策過程構(gòu)成了一種序貫決策方法[6-7]，它可以刻畫人們在許多實際問題中所采用的動態(tài)漸進決策過程。例如，在醫(yī)學(xué)診斷中，初步檢查后仍無法判斷患者患有哪種疾病，此時需要通過其他的手段對患者逐步進行檢查，直到最終確定患者病情，并給出相應(yīng)的治療方案。

三支決策作為一種決策方式，其主要用于二分類問題。然而實際應(yīng)用中會經(jīng)常出現(xiàn)多分類的問題，例如病毒性肝炎、流行性感冒、肺炎、扁桃體炎等疾病類型的判定等多類分類問題，而關(guān)于多類分類問題下的模型較少。Yao和Zhao[8]將m分類問題轉(zhuǎn)換成m個二分類問題，并為每個決策類做出三支決策。?l?zak[9]將貝葉斯模型應(yīng)用到分類問題中，基于成對比較的決策類來處理多類分類問題。Liu等[10]提出了基于決策粗糙集的兩階段多分類問題來決定最佳決策。Zhou[11-12]提出了多類分類模型需要3m×m代價矩陣來計算多類分類中的閾值。然而，上述研究只考慮了單層粒度，沒有將決策結(jié)果的代價和決策過程一起考慮，在決策過程中造成較大的決策損失。為了解決這種問題，Yao[6]提出了序貫三支決策?；谛畔⒑椭R粒度，序貫三支決策致力于分層粒度結(jié)構(gòu)下有效問題處理。例如，Li等[13-14]將序貫三支決策方法應(yīng)用到代價敏感臉部識別問題中，并研究了基于序貫粒度特征提取的深度神經(jīng)網(wǎng)絡(luò)。Yang等[15]提出了序貫三支決策的模型并給出其增量方法。Li等[16]引入序貫三支決策的思想并提出三支決策的形式概念分析。

綜上所述，本文將序貫三支決策應(yīng)用到多類分類問題。通過新增屬性來確定每一層的條件屬性，然后在Zhou提出的模型基礎(chǔ)上，計算每個決策類的三支決策。將邊界域與負域中的對象作為下一層需要決策的對象，直到不能再添加新的屬性信息，整個序貫過程結(jié)束。最后，基于本文的序貫三支決策的多類分類模型給出它的增量算法，通過仿真實驗證實了本文所提算法的有效性。

2 基礎(chǔ)概念

本章給出決策粗糙集和三支決策相關(guān)的知識[17-19]。

假設(shè)給定一個信息系統(tǒng)S=(U,AT,V,f)，Ω={w1,w2,…,wm}為m個有限的狀態(tài)集，A={a1,a2,…,an}為n個有限的行動集。x為論域U中的對象，Pr(wi|x)表示x在狀態(tài)wi下的條件概率，λ(aj|wi)表示在狀態(tài)wi下采取行動aj的損失函數(shù)，則x執(zhí)行決策aj的期望損失為：

一般地，對于給定的描述x，令τ(x)為一個決策規(guī)則，?為τ下的總體期望風(fēng)險，則可表示為：

式中，Pr(x)為x的先驗概率，R(τ(x)|x)為采取不同行動x的條件風(fēng)險。根據(jù)貝葉斯的決策準(zhǔn)則，選取使得總體期望風(fēng)險?達到最小的決策行為作為最佳行動方案。

基于決策粗糙集的思想，三支決策利用兩個狀態(tài)集和三個行動集來描述決策過程。狀態(tài)集D={X,?X}，行動集A={aP,aB,aN}，其中，aP、aB、aN分別表示將對象劃分到正域POS(X)、邊界域BND(X)、負域NEG(X)三種決策行為。λPP、λBP、λNP表示當(dāng)樣本x真實屬于X類時，分別做出aP、aB、aN三種決策所對應(yīng)的損失函數(shù)，λPN、λBN、λNN表示當(dāng)樣本x真實屬于?X類時，分別做出aP、aB、aN三種決策所對應(yīng)的損失函數(shù)，該三種決策的期望損失分別表示為：

在式（3）中，[x]表示樣本的等價類。選擇期望損失最小的行動集作為最佳行動方案，因此得到如下三條決策規(guī)則：

（P）如果R(aP|[x])≤R(aB|[x])且R(aP|[x])≤R(aN|[x])，則令x∈POS(X)；

（B）如果R(aB|[x])≤R(aP|[x])且R(aB|[x])≤R(aN|[x])，則令x∈BND(X)；

（N）如果R(aN|[x])≤R(aB|[x])且R(aN|[x])≤R(aP|[x])，則令x∈NEG(X)。

?X是X的補集，Pr(X|[x])+Pr(?X|[x])=1。從式（1）中可知，決策規(guī)則只和Pr(X|[x])及λ??(?=P,B,N)有關(guān)?？紤]到實際決策過程，一個合理的假設(shè)為0≤λPP≤λBP＜λNP，0≤λNN≤λBN＜λPN，因此上述的三條決策規(guī)則改寫為如下形式：

（P1）如果Pr(X|[x])≥α且Pr(X|[x])≥γ，則令x∈POS(X)；

（B1）如果β＜Pr(X|[x])＜αx，則令x∈BND(X)；

（N1）如果Pr(X|[x])≤β且Pr(X|[x])≤γ，則令x∈NEG(X)。

閾值α、β、γ與決策的損失函數(shù)密切相關(guān)，具體的推導(dǎo)過程以及關(guān)于閾值的討論參見文獻[2]。

3 基于多類分類的序貫三支決策模型

本章將討論序貫三支決策在多類分類問題中的應(yīng)用。首先，給出序貫三支決策的基本概念和定義；然后，結(jié)合Zhou提出的多類分類模型，提出一種基于多類分類的序貫三支決策模型；最后，給出該模型的相關(guān)算法和實例。

定義1給定決策表Si=(Ui,ATi=Ci?Di)，其中i=1,2,…,m，Ui是一個非空的有限集合。Ci是條件屬性集，滿足C1?C2?…?Cm?AT。多層次粒結(jié)構(gòu)記為GS，GS的第i層記為GSi，分別表示為：

其中，Ei表示第i層下的等價關(guān)系，val(x)Ci表示x(x∈U)在第i層下的條件屬性集值，[x]Ci表示其等價類且[x]Ci={y∈U|val(x)Ci=val(y)Ci}。

在多層粒結(jié)構(gòu)下，第k層的決策表為Sk=(Uk,ATk=Ck?Dk)，第k+1層的決策表為Sk+1=(Uk+1,ATk+1=Ck+1?Dk+1)。下面給出從第k層到k+1層多類分類問題的處理方法。

定義2給定決策表Sk=(Uk,ATk=Ck?Dk)，πΩ=表示根據(jù)決策屬性Dk劃分的n個類，則類的正域、邊界域和負域分別為：

其中，(αi,βi)為的閾值，計算方法如下。

定義3給定n個類的損失函數(shù)矩陣定義為3×m的矩陣，如表1所示。

Table 1 Loss functions matrix of表1 的損失函數(shù)矩陣

決策行為D1 k D2 k Dnk aPi λ(aPi|D1k)λ(aPi|D2k)????????????λ(aPi|Dnk)aBi λ(aBi|D1k)λ(aBi|D2k)λ(aBi|Dnk)aNi λ(aNi|D1k)λ(aNi|D2k)λ(aNi|Dnk)

定義4給定決策表Sk=(Uk,ATk=Ck?Dk)，其中，給定3n×n的損失函數(shù)矩陣Costk。根據(jù)式（1），對象x采取不同行動的期望損失為：

類似于三支決策的閾值計算過程，多類分類中每個決策類的閾值為：

在多類分類問題處理中，當(dāng)對象x分類到

定義6給定多層次粒結(jié)構(gòu)GS的第k層GSk=(Uk,Ek,Ck,[x]Ck,val(x)Ck)，Uk的正域、負域和邊界域分別為則第k+1層的Uk+1和定義為：

計算出Uk+1和，然后通過增加新的屬性得到條件屬性集Ck+1，因此第k+1層的決策表Sk+1=(Uk+1,ATk+1=Ck+1?Dk+1)。類似于第k層的分類方法，計算出第k+1層的正域、負域和邊界域。此時，第k層向第k+1層的分類過程結(jié)束。在多層粒結(jié)構(gòu)中，基于此分類過程對論域做出決策，直到整個序貫過程結(jié)束。

定理1給定m層粒結(jié)構(gòu)GSi=(Ui,Ei,Ci,[x]Ci,val(x)Ci)，對應(yīng)決策表Si=(Ui,ATi=Ci?Di)，i=1,2,…,m。Ci是Ui的條件屬性集滿足C1?C2?…?Cm?AT，Ei是Ui的等價關(guān)系滿足Em?Em-1?…?E1。是根據(jù)決策屬性Di劃分的n個類。是第k層的一個類集合，是第k+1層的類集合，。從第k層向第k+1層處理時，對于?x∈Uk，如果，則對象x的條件概率變化情況如下：

（1）如果|[x]Ck+1|=|[x]Ck|，則：

算法1基于多類分類的序貫三支決策算法

輸入：決策表S=(U,C?D)，損失函數(shù)矩陣Costi，i=1,2,???,m。

輸出：確定到?jīng)Q策類的對象X。

下面給出一個例子說明算法1的計算過程。

例1給定決策表S=(U,AT=C?D)，其中U={x1,x2,x3,x4,x5,x6,x7,x8,x9,x10}，C={c1,c2,c3}。根據(jù)決策屬性D劃分得到πD={D1,D2,D3}，D1={x1,x4,x5,x8}，D2={x2,x3,x10}，D3={x6,x7,x9}。第一層中以第一個屬性作為條件屬性，后面依次通過增加一個屬性作為下一層的條件屬性，因此構(gòu)建三層粒結(jié)構(gòu)(GS1,GS2,GS3)。給出GS1的損失函數(shù)矩陣Cost1，如表2所示，GS2損失函數(shù)矩陣Cost2，如表3所示，GS3的損失函數(shù)矩陣Cost3，如表4所示。

Table 2 Loss functions matrixCost1表2 損失函數(shù)矩陣Cost1

Table 3 Loss functions matrixCost2表3 損失函數(shù)矩陣Cost2

Table 4 Loss functions matrixCost3表4 損失函數(shù)矩陣Cost3

4 基于多類分類的序貫三支決策增量算法

基于多類分類的序貫三支決策問題處理中，m層粒結(jié)構(gòu)(GS1,GS2,…,GSm)，第k層表示為GSk=(Uk,Ek,Ck,[x]Ck,val(x)Ck)，第k+1層表示為GSk+1=(Uk+1,Ek+1,Ck+1,[x]Ck+1,val(x)Ck+1)。下面將給出從第k層到第k+1層多類分類問題處理的增量方法。

定理2基于序貫三支決策的多類分類處理中，m層粒結(jié)構(gòu)GS=(GS1,GS2,…,GSm)，GSi=(Ui,Ei,Ci,[x]Ci,val(x)Ci)，對應(yīng)決策表Si=(Ui,ATi=Ci?Di)，i=1,2,…,m。Ci是Ui的條件屬性集滿足C1?C2?…?Cm?AT，Ei是Ui的等價關(guān)系滿足Em?Em-1?…?E1。那么對于Uk+1中的對象，有[x]Ck+1?[x]Ck。

基于序貫三支決策的多類分類處理中，m層粒結(jié)構(gòu)GS=(GS1,GS2,…,GSm)，GSi=(Ui,Ci,[x]Ci,val(x)Ci)，i=1,2,…,m。Ci是Ui的條件屬性集滿足C1?C2?…?Cm?AT，Ei是Ui的等價關(guān)系滿足Em?Em-1?…?E1。那么從GS的第k層到第k+1層，有因此第k+1層的等價類[x]Ck+1可以通過第k層的等價類[x]Ck和新增屬性Ck+1-Ck推導(dǎo)得到，不需要通過Ck+1中所有屬性來重新計算。當(dāng)存在，因此在第k+1層不需要重新計算Uk+1中的所有對象的。此外，當(dāng)=?時，則不需要再計算，直接記為0。綜上，下面給出多類分類增量算法如下。

算法2基于序貫三支決策的多類分類增量算法

輸入：決策表S=(U,C?D)，損失函數(shù)矩陣Costi，i=1,2,…,m。

輸出：確定到?jīng)Q策類的對象X。

使用非增量算法1和增量算法2構(gòu)建的X是相同的，但是通過增量算法2計算出的X比非增量算法1計算出的X更簡單。接下來通過仿真實驗來驗證算法2比算法1效率更高。

5 實驗分析

本章將通過實驗證明，在多層粒結(jié)構(gòu)下，根據(jù)本文提出的多類分類模型，有效地將論域中的對象劃分到?jīng)Q策類中。此外，在分類過程中，使用算法2計算決策類中的對象數(shù)比使用算法1更有效。

本文選取4個UCI數(shù)據(jù)集用于算法的驗證，數(shù)據(jù)集的信息如表5所示。在實驗中，將每個數(shù)據(jù)集的屬性集分成4個屬性子集用于構(gòu)建多層粒結(jié)構(gòu)。例如，第1個屬性子集作為GS的第1層條件屬性集，在實驗中記為level_1，前兩個作為第2層level_2的條件屬性集，前3個作為level_3的條件屬性集，將4個屬性子集結(jié)合在一起作為level_4的條件屬性集。關(guān)于每個數(shù)據(jù)集的粒結(jié)構(gòu)，每層的屬性個數(shù)如表6所示。

Table 5 Description of datasets表5 數(shù)據(jù)集描述

在實驗中，每個數(shù)據(jù)集隨機選取4個損失函數(shù)矩陣來計算每層的決策閾值。其中，Balance和Contraceptive Method是9×3的損失函數(shù)矩陣，Car是12×4的損失函數(shù)矩陣，Zoo對應(yīng)的是21×7的矩陣。然后，根據(jù)本文提出的多類分類模型，計算出每層決策后劃分到?jīng)Q策類的對象數(shù)，具體的實驗結(jié)構(gòu)如圖1所示。

Table 6 Attributes under each level of granular structure表6 粒結(jié)構(gòu)下每一層的條件屬性

圖1展示了數(shù)據(jù)集在每層決策后，決策表中劃分到?jīng)Q策類的對象數(shù)和沒有劃分到?jīng)Q策類的對象數(shù)之間的變化。從圖1中可以看出，每層分類后非確定決策類的對象數(shù)逐漸減少。因此，數(shù)據(jù)集中劃分到?jīng)Q策類中對象數(shù)逐漸增多。接下來，為了驗證算法2比算法1有效，將4個數(shù)據(jù)集分別在算法1和算法2下進行計算，每組實驗進行100次，然后取其平均值作為最終的運行時間，實驗結(jié)果如圖2所示。

Fig.1 Comparison among the number of objects of determining decision class for 4 datasets圖1 4組數(shù)據(jù)集分別確定決策類的對象數(shù)對比

Fig.2 Running time comparison between algorithm 1 and algorithm 2 for 4 datasets圖2 4組數(shù)據(jù)集分別使用算法1和算法2的運行時間對比

圖2 是使用增量算法2與非增量算法1去計算多類分類問題的運行時間對比。在多層次粒結(jié)構(gòu)的第一層中，算法2和算法1的計算過程是一樣的，因此該層的運行時間是一致的，但是在第二層到第四層中，經(jīng)過決策過程中增量處理，可以看到算法2的運行時間要比算法1的運行時間少。因此，本文提出的增量算法是有效的。

6 結(jié)束語

實際應(yīng)用中，序貫三支決策是一種有效的動態(tài)決策方法去處理多粒度變化問題。本文針對多類分類的決策問題，提出一種基于序貫三支決策的多類分類模型來求解問題。在模型中，利用信息熵來確定對每層決策幫助最大的條件屬性，然后構(gòu)建多層粒結(jié)構(gòu)，從不同粒度層次上進行多類分類。為了減少使用該模型計算決策類的對象數(shù)的運行時間開銷，提出了增量的方法去計算決策類的對象數(shù)。在此基礎(chǔ)上，給出了基于序貫三支決策的多類分類增量算法。仿真實驗驗證了本文所提算法的有效性。在以后的工作中，將進一步研究其他的基于序貫三支決策的多類分類模型。