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

2019-08-12 02:11:36王旭生

計(jì)算機(jī)與生活 2019年8期

徐怡，王旭生

1.安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230039

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

1 引言

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

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

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

2 基礎(chǔ)概念

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

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

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

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

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

在式（3）中，[x]表示樣本的等價(jià)類。選擇期望損失最小的行動(dòng)集作為最佳行動(dòng)方案，因此得到如下三條決策規(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的補(bǔ)集，Pr(X|[x])+Pr(?X|[x])=1。從式（1）中可知，決策規(guī)則只和Pr(X|[x])及λ??(?=P,B,N)有關(guān)?？紤]到實(shí)際決策過程，一個(gè)合理的假設(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)于閾值的討論參見文獻(xiàn)[2]。

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

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

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

其中，Ei表示第i層下的等價(jià)關(guān)系，val(x)Ci表示x(x∈U)在第i層下的條件屬性集值，[x]Ci表示其等價(jià)類且[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個(gè)類，則類的正域、邊界域和負(fù)域分別為：

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

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

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

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

類似于三支決策的閾值計(jì)算過程，多類分類中每個(gè)決策類的閾值為：

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

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

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

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

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

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

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

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

下面給出一個(gè)例子說明算法1的計(jì)算過程。

例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è)屬性作為條件屬性，后面依次通過增加一個(gè)屬性作為下一層的條件屬性，因此構(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)，對(duì)應(yīng)決策表Si=(Ui,ATi=Ci?Di)，i=1,2,…,m。Ci是Ui的條件屬性集滿足C1?C2?…?Cm?AT，Ei是Ui的等價(jià)關(guān)系滿足Em?Em-1?…?E1。那么對(duì)于Uk+1中的對(duì)象，有[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的等價(jià)關(guān)系滿足Em?Em-1?…?E1。那么從GS的第k層到第k+1層，有因此第k+1層的等價(jià)類[x]Ck+1可以通過第k層的等價(jià)類[x]Ck和新增屬性Ck+1-Ck推導(dǎo)得到，不需要通過Ck+1中所有屬性來(lái)重新計(jì)算。當(dāng)存在，因此在第k+1層不需要重新計(jì)算Uk+1中的所有對(duì)象的。此外，當(dāng)=?時(shí)，則不需要再計(jì)算，直接記為0。綜上，下面給出多類分類增量算法如下。

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

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

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

使用非增量算法1和增量算法2構(gòu)建的X是相同的，但是通過增量算法2計(jì)算出的X比非增量算法1計(jì)算出的X更簡(jiǎn)單。接下來(lái)通過仿真實(shí)驗(yàn)來(lái)驗(yàn)證算法2比算法1效率更高。

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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