雙論域模糊概率三支決策模型及其應用

卓雪雪，朱蒼璐

（安徽三聯學院計算機工程學院,安徽 合肥 230000）

0 引言

粗糙集理論［1］是人工智能領域一種重要的數據分析工具，由Pawlak于1982年首次提出。作為一種新的建模在不完全知識的數學理論，它可以有效地處理復雜系統中數據不精確或信息不精確的問題，目前已成功應用于數據挖掘、智能控制等領域［2-3］。

然而，目前粗糙集的大多數研究都是在同一論域的假設下進行的。但在現實中，可能存在2個或多個不同的論域情形，針對這一問題，學者們提出了基于雙論域信息系統的粗糙集模型，并受到了學界的廣泛關注，對雙論域信息系統的粗糙集進行不斷推廣和改進，如Ugur等［4］提出了廣義的雙論域粗糙集模型；Sun等［5］在雙論域信息系統下建立了模糊相似關系，并提出了多粒度的模糊雙論域模型；黃心宏等［6-7］進一步推廣，提出了直覺模糊關系的雙論域粗糙集模型。三支決策模型是粗糙集理論的重要應用，一經提出便受到了學者們的廣泛關注和研究，并成功應用于雙論域信息系統，如Li等［8］在雙論域信息系統下提出了三支決策模型；Sun等［9］在雙論域概率粗糙集下提出了三支決策方法；Xu等［10］提出了具有排序和參考元組的三支決策雙論域模型；袁路妍等［11］提出了雙論域三支決策的增量式更新方法。

由于傳統的雙論域粗糙集模型在處理模糊含噪聲數據方面的不足，Yang等［12］提出了模糊概率雙論域粗糙集模型，使得在實際環境下的應用性能更加優越，受到了研究人員的青睞；Hu等［13］針對雙論域信息系統的動態性，提出了增量式的模糊概率雙論域粗糙集模型；劉丹等［14］在Hu的基礎上進行改進，提出了矩陣策略的增量式模糊概率雙論域粗糙集；Yang等［15］將模糊概率雙論域粗糙集推廣至多粒度空間，提出了多粒度模糊概率雙論域粗糙集模型。

然而，當前已有的模糊概率雙論域粗糙集沒有關于三支決策方面的研究。由于三支決策模型在近似和決策方面的優越性，因此這限制了模糊概率雙論域粗糙集的實用化推廣。本文將提出模糊概率雙論域粗糙集的三支決策模型，并提出一種分類算法的應用。首先介紹了模糊概率雙論域粗糙集；其次在其基礎上定義了雙論域信息系統的決策動作和決策代價，構建了貝葉斯決策模型；再次以最小化決策代價為原理，推導出了雙論域信息系統模糊概率關系下決策區域的三元劃分，即三支決策模型；最后利用三支決策對論域的區域劃分原理，提出了雙論域信息系統的模糊概率三支決策分類算法。進行雙論域信息系統的實驗證明了所提出分類算法的有效性和優越性。

1 基本理論

在粗糙集理論［1-3］中，信息系統S表示為S=(U，A)，其中U為全體對象集，A為全體屬性集，屬性子集I?A確定的等價關系為EA，對于論域中的對象x∈U在EA誘導確定的等價類表示為[x]EA，考慮近似對象集X?U，在等價關系EA下確定的上近似(X)和下近似(X)分別定義如式（1）和（2）所示。

在某些實際應用環境，信息系統往往包含了2個論域，這類信息系統稱之為雙論域信息系統［4］，典型的如個信息化推薦信息系統。

定義1［4］設雙論域信息系統D表示為D=(U，V)，其中U和V分別為信息系統的2個論域，R為論域U和V誘導確定的二元關系，?x∈U在二元關系R下確定的相似類定義為R(x)={y∈V|(x，y)∈R}。

定義2［4］雙論域信息系統D=(U，V)，R為論域U和V誘導確定的二元關系。對象集Y?V關于R的下近似集和上近似集分別定義式（3）和（4）所示。稱(Y)和(Y)為對象集Y?V在二元關系R下的雙論域粗糙集。

當U=V，那么雙論域粗糙集退化為傳統的粗糙集，因此雙論域粗糙集是傳統粗糙集的進一步推廣，傳統粗糙集是雙論域粗糙集的特例。

2 雙論域模糊概率三支決策模型

近年來，學者們對雙論域粗糙集模型提出了多種擴展模型，其中雙論域模糊概率粗糙集是其研究熱點［12-15］。本節將雙論域模糊概率粗糙集進一步擴展，提出一種雙論域模糊概率三支決策模型。

定義3［12］雙論域信息系統，Fλ為論域U和V誘導確定的模糊二元關系，Fλ：U×V→[0，1]，定義?x∈U基于Fλ的相似類Fλ(x)定義為

Fλ(x)={y∈V|F(x，y)≥λ}，

式中：F(x，y)表示對象x與y之間的模糊相似度；λ為模糊閾值，滿足0≤λ≤1，下文中在不引起混淆的情形，將省略λ標記。

定義4［12］雙論域信息系統，F為論域U和V誘導確定的模糊二元關系，對于0≤λ≤1，0≤β<α≤1，對于Y?V關于模糊二元關系F的模糊概率下近似集(Y)和模糊概率上近似集(Y)分別定義式（5）和（6）所示。

式中：P(Y|F(x))=稱為Y?V關于模糊二元關系F基于參數λ、α和β的模糊概率粗糙集。

在定義4中，參數λ、α和β可以被視為給定的最小閾值。對于實際應用環境下的決策，這些參數通常是由決策者預先選擇并代表著其需求。

在傳統的分類決策模型中，決策對象的判定結果為滿足或不滿足決策標準，然后將對象集劃分為2個不相交的決策區域，即滿足決策準則對象的正區域集和不滿足決策準則對象的負區域集N。然而，這種二元分類方法通常會存在一些分類錯誤。因此，這種二元分類方法的主要局限是它們對分類的要求過于嚴格。

三支決策模型是由學者姚一豫基于概率粗糙集提出的一種新的決策模型。根據一組評估標準，以三元分類的方式描述了該模型的基本思想［8］。假設非空有限對象集U和非空有限屬性集A，三支決策模型基于屬性A將集合U劃分為3個不相交的區域，即正區域集，負區域集N和邊界域集，分別代表了3種不同的分類決策結果?；谠撍枷?，接下來將提出基于雙論域模糊概率粗糙集的三支決策模型。

設雙論域信息系統，對象子集族Ω={Y1，Y2，…，Yk}，其中Yk?V，代表了論域V中的k個狀態。設Z={d1，d2，…，dm}表示決策者的m種可能動作行為。P(Yj|F(x))是給定狀態Yj下特征描述集F(x)與對象x(x∈U)的條件概率。?(di|Yj)是在狀態Yj的情況下做出決策di的成本或代價。假設決策者對目標x(x∈U)的特征描述集F(x)采取動作行為di，則預期決策代價C(di|F(x))為：

因此，如果存在di，使得C(di|F(x))的決策代價最小，則di為對象x(x∈U)的最優決策，為x的最小決策代價。

基于貝葉斯決策過程會得到以下最小代價決策規則：

1）執行決策P(Y)，當且僅當

C(dp|F(x))≤C(db|F(x))，C(dp|F(x))≤C(dn|F(x))；

2）執行決策B(Y)，當且僅當

C(db|F(x))≤C(dp|F(x))，C(db|F(x))≤C(dn|F(x))；

3）執行決策N(Y)，當且僅當

C(dn|F(x))≤C(dp|F(x))，C(dn|F(x))≤C(db|F(x))。

通常決策代價滿足

?(dp|Y)≤?(db|Y)≤?(dn|Y)，

?(dn|Yc)≤?(db|Yc)≤?(dp|Yc)。

同時P(Y|F(x))+P(Yc|F(x))=1，因此

1）對于執行決策P(Y)，即

2）對于執行決策B(Y)，即

3）對于執行決策N(Y)，即那么：

1）當P(Y|F(x))≥α且P(Y|F(x))≥γ，有x∈P(Y)；

2）當P(Y|F(x))≤α且P(Y|F(x))≥β，有x∈B(Y)；

3）當P(Y|F(x))≤β且P(Y|F(x))≤γ，有x∈N(Y)。

同時，若代價滿足如下關系

此時有0≤β<γ<α≤1，因此雙論域信息系統最小代價決策規則可以簡化表示為：

1）當P(Y|F(x))≥α，則x∈P(Y)；

2）當β

3）當P(Y|F(x))≤β，則x∈N(Y)。

因此基于雙論域模糊概率關系的三支決策模型定義如下。

定義5雙論域信息系統，F為論域U和V誘導確定的模糊二元關系，對于0≤λ≤1，對于?x∈U關于Y?V的模糊概率關系的三支決策區域集分別定義為

P(Y)={x∈U|P(Y|F(x))≥α}，

B(Y)={x∈U|β

N(Y)={x∈U|P(Y|F(x))≤β}。

3 雙論域模糊概率三支決策分類

學者們將三支決策模型應用于數據的分類，提出了多種基于三支決策的分類算法［16］，基于當前的可獲取的分類準則，它將目標對象的分類決策判定為屬于特定類、不屬于特定類以及待定，即當前條件可以確定分類的，直接將分類結果確定為某個類，對于那些處于類與類邊緣的對象，暫時進行待定狀態，待后續更多的分類信息被獲取則進一步進行分類。受此啟發，本節將提出雙論域信息系統下的三支決策分類模型，具體如算法1所示。

算法1雙論域模糊概率三支決策分類算法。

輸入：雙論域信息系統，閾值0≤λ≤1，類別Yi?V（1≤i≤m）的決策代價?(d*|Yi)，*=p，b，n；待分類目標對象x∈U。

輸出：x∈U的分類類別。

Step1：計算雙論域模糊概率關系Fλ；

Step2：根據決策代價?(d*|Yi)計算類別Yi?V的決策閾值αi和βi；

Step3：計算x∈U基于Fλ的相似類Fλ(x)；

Step4：對于每個決策類Yi?V，如果P(Yi|Fλ(x))≥α，那么x∈P(Yi)；

Step5：對于每個決策類Yi?V，如果β

Step6：對于每個決策類Yi?V，如果P(Yi|Fλ(x))≤β，那么x∈N(Yi)；

Step7：對于所有Yt，選擇P(Yt|Fλ(x))最大值對應的Y作為最終決策結果，其中Yt∈{Yi?V|x∈P(Yi)}；

Step8：返回x∈U的分類類別Y。

算法1主要計算量集中在雙論域模糊概率關系計算流程，因此整個算法1的時間復雜度為O(|U|×|V|)。

4 實驗分析

本節將通過仿真實驗驗證所提出的雙論域模糊概率三支決策分類算法的有效性。實驗在Windows 10和Intel（R） Core（TM） i3-7100 CPU的個人主機上進行，CPU頻率為3.90 GHz，內存為8 GB。實驗使用的數據集如表1所示，其中數據集1和2下載于http：//grouplens.org/datasets/ movielens/，數據集3下載于http：//www.ieor.berkeley.edu/goldberg/jesterdata/，數據集4下載于UCI數據集https：//archive.ics.uci.edu/ml/index.php。

表1 實驗數據集

為了消除數據集屬性量綱帶來的影響，實驗前將數據集進行歸一化處理，歸一化方法為

式中：a(x)表示對象x∈U在論域V下屬性a的屬性值；min(a)表示屬性a下所有對象的最小值；max(a)表示屬性a下所有對象的最大值；a'(x)為歸一化之后的值，滿足0≤a'(x)≤1。本實驗中各個類別的分類代價?(d*|Yi)采用在區間［0，1］進行隨機選取的方式，并滿足決策代價的基本大小關系。

針對本文提出的三支決策分類方法，本實驗提出4種模型評估指標，具體如下定義：

式中：Ac、Pr、Re分別表示準確度、精度和召回率；NPP、NBP和NNP分別表示原本屬于類別Y采取動作dp、db和dn對象的數量；NPN、NBN和NNN分別表示原本不屬于Y采取動作、和對象的數量。

理想情況下，當一個模型具有較高的精度和召回率時，它在分類方面會表現得更好。但是在本文所提出的分類算法中，0≤λ≤1是一個可變參數，它的取值不同對模型的分類性能有著很重要的影響，為了選擇合適的實驗參數，本實驗將λ在0和1之間以0.1為步長分別進行取值，利用本文的三支決策分類算法進行分類計算，各個數據集的精度和的實驗結果如圖1和圖2所示。

圖1 不同λ下精度實驗結果

圖2 不同λ下實驗結果

從圖1和圖2可以發現，隨著λ取值的增加，模型分類的精度值也隨之增加，但達到0.7之后開始趨于穩定。對于，隨著λ取值的增加，數據集MovieLens 1M、MovieLens 1M和Wdbc的值逐漸增加，達到0.7之后開始趨于穩定，因此綜合起來λ=0.7是一個較佳的取值。

為了驗證本文所提出分類算法的優越性，本實驗選擇了機器學習領域3種常用的分類器進行分類比較，這3種分類器分別為支持向量機（SVM）、樸素貝葉斯（NB）和k近鄰（kNN，k=3）。表2所示的是各個數據集在三種對比分類器和本文分類算法下的精度實驗結果，表3所示的是各個數據集在3種對比分類器和本文分類算法下的實驗結果。

表2 各個數據集精度實驗結果

表3 各個數據集實驗結果

從表2可以發現，本文分類算法在大部分數據集下的分類結果精度值均高于其余3種分類算法。因此從分類精度視角可以看出本文分類算法的性能更優。

從表3可以發現，數據集Jester下本文算法的值低于其余分類算法，其余數據集下本文分類算法的結果最高。這主要是由于本文提出的三支決策分類算法引入了分類邊界域，即對于不確定類別的對象進行延遲分類，待后續有充分的分類信息時進行進一步分類決策。

由于本文所提出的三支決策分類算法建立在代價的基礎上，因此接下來計算各個分類算法的誤分類代價結果，誤分類代價即分類算法分類錯誤對象的代價之和，具體結果如表4所示。

表4 各個分類算法誤分類代價

從表4可以發現，各個數據集下本文分類算法的誤分類代價是最低的，尤其對于數據集Jester，其分類精度并不是最高的，但是誤分類代價最低，這主要是由于對比的3種分類算法對每個對象進行了確定的分類，因此誤分類產生的代價會比較高，而本文算法將暫時不能確定分類的對象進行延遲分類，減少了錯誤分類的情形，因此也降低了誤分類的代價，因此本文算法的誤分類能力整體更優。

綜合所有實驗結果，證明了本文所提出的三支決策分類算法在雙論域信息系統的分類方面具有較優的分類性能。

5 結束語

當前的雙論域模糊概率粗糙集還未有三支決策的相關研究，針對這一問題，文中在模糊概率粗糙集基礎上定義了雙論域信息系統的決策動作和決策代價，以貝葉斯決策最小化代價為原理，推導出了雙論域信息系統模糊概率關系下決策區域的三支決策模型，最后提出了雙論域信息系統的模糊概率三支決策分類算法。實驗分析證明了所提出分類算法的有效性和優越性。接下來將進一步對雙論域信息系統模糊概率三支決策模型進行增量式更新方法的研究，提升現實動態數據處理的有效性。