不完備混合型數據的決策粗糙集與三支決策分類算法

王 光 瓊

(四川文理學院智能制造學院 四川 達州 635000)

0 引 言

粗糙集理論[1]是當今人工智能和知識發現領域的一種重要模型，在處理不確定性和不完備性的數據方面發揮著尤為重要的作用。傳統的粗糙集模型基于等價關系建立，通過等價關系對信息系統進行劃分來達到不確定性概念的粗糙近似。然而傳統的粗糙集模型對噪聲數據較為敏感[1-4]，不具有較好的泛化能力，為了改善這一局限，提出了一種稱之為決策粗糙集的模型。

決策粗糙集最早由加拿大學者Yao等[5]提出，將貝葉斯決策理論融入傳統粗糙集模型中，使得其最終的粗糙近似結果具有最小的決策代價，其中決策粗糙集的上下近似通過一對閾值來限定，相比傳統的粗糙集模型，該模型對噪聲數據具有更好的容忍效果。在決策粗糙集模型的基礎上，Yao[6]進一步地提出了三支決策理論，建立了不確定性數據環境下一種新的決策方法。為了提高決策粗糙集模型的應用范圍，學者們進行了大量的改進和推廣，例如：在分布式數據集下，Lin等[7]提出了一種多源信息系統的決策粗糙集模型；在不完備信息系統下，Liu等[8]提出了一種適用不完備數據的改進決策粗糙集模型；Zhao等[9]針對多值信息系統提出一種擴展的決策粗糙集；Feng等[10]提出一種變精度的多粒度決策粗糙集模型；在模糊數據的環境下，Sun等[11]提出了模糊集的決策粗糙集模型以及相關應用；Zhao等[12]在其基礎上進一步地提出了模糊區間值的決策粗糙集模型；劉久兵等[13]提出了直覺模糊信息系統的決策粗糙集模型。另一方面，數值型數據也是一種常見的數據類型，Li等[14]提出了基于鄰域關系的決策粗糙集模型。因此可以看出，目前決策粗糙集模型的研究已不斷趨于完善。

混合性和不完備性是目前數據的一個典型特征，對于粗糙集理論，學者們對這種類型的數據也進行了廣泛的研究[15-17]。然而目前的決策粗糙集模型還未對這種類型的數據進行探索，因此本文將在前人研究的基礎上提出一種不完備混合型信息系統的決策粗糙集模型。

對于不完備混合型信息系統，Zhao等[15]定義了鄰域容差關系，對這類信息系統進行了有效處理。本文采用鄰域容差關系重新對傳統的決策粗糙集模型進行重構，提出不完備混合型信息系統下的決策粗糙集模型，同時基于該模型進一步地提出相應的三支決策。此外，基于最小化決策代價的原則，本文對于所提出的決策粗糙集模型設計出一種最小化決策代價的屬性約簡算法。另一方面，由于三支決策提供了一種新的決策思維，本文將其融入分類模型中，提出一種不完備混合型數據的三支決策分類算法，該分類算法將樣本對象的類決策結果分成三種情況，比傳統的分類算法增加延遲分類的情形，即對于不確定性的樣本對象進行延遲處理。仿真實驗結果表明，所提出的三支決策分類算法可以有效地降低分類結果的誤分類代價，提高分類精度，具有更高的分類性能。

1 決策粗糙集模型

在粗糙集理論中，數據集表示成信息系統的形式，一個信息系統可表示為S=(U,At=C∪D,V)，其中：U為該信息系統S的論域，即數據集的樣本空間；At為信息系統的屬性集；C為條件屬性集；D為決策數據集；V為整個信息系統的屬性值集域，根據V中屬性值的類型，通常可以將信息系統分為離散型信息系統、連續型信息系統以及混合型信息系統。通常信息系統也可簡單表示為S=(U,At=C∪D)。

定義1[1]對于離散型信息系統S=(U,At=C∪D)，基于屬性子集B?C構建的等價關系EB定義為：

EB={(x,y)∈U×U|a(x)=a(y),?a∈B}

(1)

式中：a(x)表示對象x在屬性a下的屬性值。根據等價關系EB，可以得到任意對象的等價類，即對象x的等價類表示為[x]B={y∈U|(x,y)∈EB}。

(2)

表1 決策代價

根據貝葉斯決策理論，Yao等通過最小化決策代價的原則，利用代價矩陣推導出一對閾值來進行粗糙集模型中粗糙近似的計算，使得近似的結果擁有最小的誤分類代價，該模型即為決策粗糙集模型。

(3)

式中：θ+=max{α,β,γ};θ-=min{α,β,γ}。其中：

在決策粗糙集模型基礎上，Yao等進一步地提出了三支決策模型。對于一個決策對象x，利用三支決策進行的決策行為可以描述為：

(1) 若p(X|[x])>θ+，則x判定為X;

(2) 若θ-

2 不完備混合型信息系統下的決策粗糙集模型

2.1 鄰域容差關系

在粗糙集理論中，傳統的模型都基于完備離散型的信息系統而建立，而現實環境下的數據類型是復雜多樣，不完備混合型的信息系統便是其中常見的一種。Hu等[18]通過在連續型數據下建立鄰域關系，從而解決粗糙集理論對連續型以及混合型信息系統的處理。Kryszkiewicz[19]提出一種基于容差關系的擴展粗糙集模型，解決了不完備信息系統下的粗糙集近似。在兩位學者的基礎上，Zhao等[15]提出了鄰域容差關系用于對不完備混合型信息系統的處理。

定義3[15]給定不完備混合型信息系統S=(U,AT)，設屬性集A?AT滿足A=AD∪AN，其中AD和AN分別表示A下的離散型屬性集和連續型屬性集，那么屬性集A在不完備混合型信息系統下確定的鄰域容差關系定義為：

((a∈AD→a(x)=a(y))∧(a∈AN→d(x,y)≤δ))}

(4)

式中：d(x,y)表示對象x與y之間的距離度量[18]；δ為鄰域半徑，是一個非負常數；a(x)表示對象x在屬性a下的屬性值，a(x)=*表示屬性值為缺失的情形。

根據鄰域容差關系，可以對整個不完備混合型信息系統的論域誘導出一組鄰域容差粒化，鄰域容差粒化的結果將是不完備混合型信息系統進行粗糙逼近的基礎。

(5)

同時，論域U上所有對象鄰域容差類構成的集合GSA={δA(x1),δA(x2),…,δA(x|U|)}稱為該信息系統的一個粒結構。顯然，GSA為論域U上的一個覆蓋。

2.2 模型設計

在Zhao等提出的鄰域容差關系基礎上，將經典的決策粗糙集進行推廣，提出不完備混合型信息系統下的決策粗糙集模型，同時相應的三支決策也被提出。

在鄰域量化容差關系中，將對象x∈U的鄰域容差類δ(x)看成與該對象屬于同一類的對象集，因此在不完備混合型信息系統中，對于一個對象x隸屬于某個對象集X的概率可表示為：

(6)

基于該定義框架，本文構造了不完備混合型信息系統的決策粗糙集模型以及相應的三支決策。

(7)

因此，可以得到如下三種最小代價規則：

POSδ(X)、BUNδ(X)和NEGδ(X)分別表示X的δ正區域、邊界域和負區域。

所以，可以進一步得到：

λPP·p(X|δ(x))+λPN·(1-p(X|δ(x)))≤

λBP·p(X|δ(x))+λBN·(1-p(X|δ(x)))?

且：

λPP·p(X|δ(x))+λPN·(1-p(X|δ(x)))≤

λNP·p(X|δ(x))+λNN·(1-p(X|δ(x)))?

λBP·p(X|δ(x))+λBN·(1-p(X|δ(x)))≤

λPP·p(X|δ(x))+λPN·(1-p(X|δ(x)))?

且：

λBP·p(X|δ(x))+λBN·(1-p(X|δ(x)))≤

λNP·p(X|δ(x))+λNN·(1-p(X|δ(x)))?

λNP·p(X|δ(x))+λNN·(1-p(X|δ(x)))≤

λPP·p(X|δ(x))+λPN·(1-p(X|δ(x)))?

且：

λNP·p(X|δ(x))+λNN·(1-p(X|δ(x)))≤

λBP·p(X|δ(x))+λBN·(1-p(X|δ(x)))?

這里令：

(8)

則有：

(1) 若p(X|δ(x))≥α且p(X|δ(x))≥γ，那么x∈POSδ(X);

(2) 若p(X|δ(x))≤α且p(X|δ(x))≥β，那么x∈BUNδ(X);

(3) 若p(X|δ(x))≤β且p(X|δ(x))≤γ，那么x∈NEGδ(X)。

特別地，若代價函數滿足如下關系：

那么此時有0≤β<γ<α≤1，則上述三個規則即為：

(1) 若p(X|δ(x))≥α，則x∈POSδ(X);

(2) 若β≤p(X|δ(x))≤α，則x∈BUNδ(X);

(3) 若p(X|δ(x))≤β，則x∈NEGδ(X)。

根據以上推導的這三條規則，可以直接得到不完備混合型信息系統下的決策粗糙集模型，同時也蘊含了不完備混合型信息系統下三支決策。

(9)

(10)

(11)

另一方面，根據本文所提出決策粗糙集模型的三個區域劃分，這里便得到了不完備混合型信息系統下的三支決策。對于目標決策結果X和待決策的對象x，那么：

(1) 若對象x滿足目標決策結果X的決策條件，即p(X|δ(x))>θ+，那么接受對象x判定為X，即x∈POSθ+(X);

(2) 若對象x不滿足目標決策結果X的決策條件，即p(X|δ(x))<θ-，那么拒絕對象x判定為X，即x∈NEGθ-(X);

(3) 若對象x不確定是否滿足目標決策結果X的決策條件，即θ-≤p(X|δ(x))≤θ+，那么延遲對象x的判定，即x∈BUN(θ-,θ+)(X)，待得到更多信息后再進行確定。

(12)

(13)

(14)

證明：

因此(1)成立。

(3) 由于:

綜合(1)、(2)可以得到：

因此(3)成立。

證畢。

性質1表明了本文所提出決策粗糙集三個區域的單調性。基于三支決策的視角，性質1中的式(12)表明當決策的接受閾值θ+越大，即接受的決策條件越為苛刻，那么最終可接受的對象越少。式(13)表明當決策的拒絕閾值θ-越小，即拒絕的決策條件越為苛刻，那么最終拒絕的對象越少。式(14)表明接受決策閾值越大且拒絕決策閾值越小時，即接受決策和拒絕決策都比較嚴格時，那么延遲決策的程度就比較寬松。相反，接受決策閾值越小且拒絕決策閾值越大時，即接受決策和拒絕決策都比較寬松時，那么延遲決策的程度就比較嚴格，這表現出了兩種不同的決策態度。由于決策粗糙集中的閾值θ-和θ+直接由分類代價矩陣直接確定，那么代價的取值不同就決定了三支決策的決策態度。

2.3 屬性約簡

屬性約簡是粗糙集理論的重要研究內容，在決策粗糙集模型中，基于最小代價的屬性約簡是目前的研究熱點[20-22]。

(15)

基于最小化代價的屬性約簡定義如下：

定義7給定不完備混合型決策信息系統為S=(U,AT=C∪D),設鄰域半徑為δ，由決策代價確定的一對閾值分別為θ-和θ+。若屬性子集A?C是該信息系統的最小代價屬性約簡，那么當且僅當：

(1)CostA≤CostC;

(2) ?A′?A,CostA′>CostA。

在定義7中，條件(1)表明屬性約簡集的決策代價小于屬性全集的決策代價；條件(2)展示了屬性約簡集決策代價的極小性，即屬性約簡集的決策代價在所有屬性子集中是最小的。

啟發式搜索是尋找信息系統約簡集的一種常用方法，其中啟發式函數的構造是該方法的核心。本節將通過決策代價Cost構造出一種屬性約簡的啟發式函數。

給定不完備混合型決策信息系統為S=(U,AT=C∪D),設屬性集A?C，對于?a∈A關于屬性集A的屬性重要度定義為：

(16)

利用sigA(a)作為啟發式函數設計出的最小代價屬性約簡算法如算法1所示。

算法1不完備混合型信息系統下決策粗糙集模型的最小代價屬性約簡

輸入：不完備混合型信息系統S=(U,AT=C∪D)；決策代價矩陣C,鄰域半徑δ。

輸出：屬性約簡集R。

步驟1初始化R=?。

步驟2對于?a∈C，計算a的屬性重要度sigC(a)，并將屬性集C按照屬性重要度從大到小進行排序，排序后的屬性集記為C′。

步驟3選擇屬性集C′中屬性重要度最大的屬性at，若CostR∪{at}>CostC，那么進行C′←C′-{at}且R←R∪{at},并重新進入步驟3，若CostR∪{at}≤CostC，那么R←R∪{at}并進入步驟4。

步驟4對于屬性集?r∈R，若滿足關系CostR-{r}≤CostR，那么進行R←R-{r}。

步驟5返回結果R。

3 不完備混合型信息系統的三支決策分類算法

Hu等[23]通過鄰域粗糙集模型構造出了混合型數據的鄰域分類算法，實驗證明該算法具有較好的分類效果。本文在該分類算法的基礎上，將三支決策思想融入其中，提出基于三支決策方法的數據分類模型。

三支決策是在經典的貝葉斯決策模型基礎上的推廣，它將決策對象的決策結果分成三個部分，分別為接受、拒絕和延遲，確定這三種決策結果則通過決策粗糙集模型中的閾值θ-和θ+來實現。把數據的分類也看成對數據類別的決策，因此利用三支決策模型來用于數據的分類，可以描述成如下形式：

對于二分類問題，設一個訓練樣本集為Data，其中樣本包含兩種類別，分別記為正類別和負類別，并且Data中正類別樣本集表示為D+，負類別樣本集表示為D-。對于一個待標記類別的樣本對象x，δ(x)為對象x在樣本集Data中的鄰域類，那么基于三支決策模型對象x的判定規則為：

(1) 若p(D+|δ(x))>θ+，x判定為正類別;

(2) 若p(D+|δ(x))≤θ-，x判定為負類別;

(3) 若θ-

對于多分類情形，可以不斷將其轉換成多個二分類問題進行處理，因此基于三支決策模型的多分類判定規則為：

(1) 若p(Dmax|δ(x))>θ+，x判定為Dmax;

(2) 若p(Dmax|δ(x))≤θ-，x不判定為任何類;

(3) 若θ-

根據如上判定規則，不完備混合型信息系統的三支決策分類算法如算法2所示。

算法2不完備混合型信息系統的三支決策分類算法

輸出：對象x的類別。

步驟1根據決策代價矩陣C計算決策閾值θ-和θ+。

步驟2根據算法1對原信息系統S進行最小化代價屬性約簡，得到約簡結果R。

步驟3計算對象x在論域U中屬性集R下的鄰域類δR(x)。

步驟4判斷p(Dmax|δR(x))與θ+之間的關系：

1) 若p(Dmax|δR(x))>θ+,那么x判定為Dmax；

2) 若θ-

3) 若p(Dmax|δR(x))≤θ-那么x不判定為任何類。

步驟5返回對象x的類別。

4 實 驗

表2為實驗中所使用的數據集，這10個數據集均來源于UCI機器學習數據庫，其中：Mushroom為只包含離散型屬性的數據集；Wine、Sonar和Musk為只包含連續型屬性的數據集；其余為混合型屬性的數據集。部分數據集為完備型的數據集，本實驗選擇其中5%的屬性值進行刪除，從而構造出不完備的數據集，同時，為了避免連續型屬性量綱帶來的影響，在實驗前將所有數據集的連續型屬性標準化至[0,1]區間。

表2 實驗數據集

4.1 實驗設置

在本文提出的三支決策分類算法中，決策代價矩陣發揮著很重要的作用，實驗采用在[0,1]之間取隨機值的方法進行選取，選取的決策代價滿足如下關系：

(17)

本實驗將所提出的三支決策分類算法與支持向量機分類算法(SVM)、決策樹分類算法(C4.5)、樸素貝葉斯分類算法(NB)和鄰域粗糙集分類算法[23](NRSC)進行實驗比較，其中比較結果通過分類精度Acc、F度量和誤分類MCost代價來體現，計算式表示為：

(18)

式中：nPP表示被分類正確的對象數；nNP表示被錯誤分類的對象數；nBP表示被待定的對象數。

4.2 鄰域半徑的選取

在本文所提出的三支決策分類算法中，鄰域半徑是一個較為關鍵的參數，它的取值不同對最終的實驗結果將產生很大的影響，因此在進行實驗之前需要對鄰域半徑的大小進行確定。由于連續型屬性已標準化至[0,1]區間，本實驗將鄰域半徑δ在區間[0,0.3]中以0.02為間隔分別進行取值，將選取的每個值對所有數據集進行十折交叉分類，這樣便得到對應的分類精度結果。圖1為每個數據集在不同鄰域半徑下得到分類精度結果。

圖1 不同鄰域半徑下各個數據集的分類精度

觀察圖1的實驗結果，可以發現當鄰域半徑選取為0.10時可以得到較好的分類結果，因此本實驗選擇δ=0.10進行實驗。

4.3 結果分析

表3為本文的三支決策分類算法與SVM、C4.5、NB和NRSC算法對每個數據集通過十折交叉法得到的分類精度Acc,結果通過“均值±標準差”來表示，最高的分類精度已用粗體表示。觀察表3的實驗結果可以發現，本文算法在大部分數據集下擁有最高的分類精度；SVM在少部分數據集下擁有最高的分類精度，例如數據集Sonar和Credit；NB算法在數據集German中擁有最高的分類精度。因此本文算法具有更高的分類準確度，這主要是由于分類機制的差異導致的。SVM擁有較好的分類性能，但是它是一種二支分類模型，即對象的分類的結果只有兩種，標記為特定的類或不標記為特定的類，對于處于類之間的對象，可能會出現誤分類情形。而本文算法對于確定的對象直接進行分類，對于類與類之間的模糊對象，通過進行延遲處理的方式，減少誤分類的情況，因而在大部分數據集下擁有更高的分類精度。

表3 分類精度Acc比較結果

表4給出了三支決策分類算法與SVM、C4.5、NB和NRSC算法對每個數據集進行分類的F度量結果，其中最高的結果值已用粗體表示。觀察表4可以發現，SVM分類算法在大部分數據集下擁有最高的度量值，而本文算法在所有數據集中都擁有較小的F度量結果，這主要是由于參與比較的分類算法對待分類的對象都進行了具體的類別判定，不存在延遲判定的情況，即nBP=0，因此Cov始終等于1，而本文算法會對有的對象進行延遲判別，因而nBP≥0，那么Cov≤1，因此F值會偏小。

表4 F度量比較結果

表5為所有算法對每個數據集分類結果的誤分類代價MCost比較結果，其中最低的誤分類代價MCost已用粗體表示。觀察表5可以發現，本文算法在所有的數據集下都擁有最小的誤分類代價，其他分類算法的誤分類代價都高于本文算法。主要原因是本文算法增加延遲分類的判別結果，處于類邊界的對象進行延遲決策，減少誤分類的情況，而其他傳統的分類算法對這類情形可能會將判別對象分類入其他錯誤的類，而進行延遲分類的代價要小于錯誤分類的代價，因此本文算法的誤分類代價要更小。

表5 誤分類代價MCost比較結果

綜合實驗結果表明，本文提出的三支決策分類算法在不完備混合型數據下具有較好的分類效果。

5 結 語

決策粗糙集是目前粗糙集理論研究的重點模型。由于現實應用環境下數據往往都是不完備混合類型，本文將傳統的決策粗糙集模型進行推廣，提出不完備混合型信息系統下的決策粗糙集模型，構建該模型框架下的三支決策，并設計出該模型的一種最小化代價屬性約簡算法。基于所提出的三支決策，提出一種不完備混合型數據的三支決策分類算法。實驗分析表明，所提出的三支決策分類算法比其他傳統的分類算法具有更高的分類精度、較小的誤分類代價和更高的優越性。動態性也是現實數據集的重要特征，因此接下來將進一步研究不完備混合型數據決策粗糙集的增量式學習問題。