卓雪雪，朱蒼璐

（安徽三聯(lián)學(xué)院計(jì)算機(jī)工程學(xué)院,安徽 合肥 230000）

0 引言

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

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

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

然而，當(dāng)前已有的模糊概率雙論域粗糙集沒有關(guān)于三支決策方面的研究。由于三支決策模型在近似和決策方面的優(yōu)越性，因此這限制了模糊概率雙論域粗糙集的實(shí)用化推廣。本文將提出模糊概率雙論域粗糙集的三支決策模型，并提出一種分類算法的應(yīng)用。首先介紹了模糊概率雙論域粗糙集；其次在其基礎(chǔ)上定義了雙論域信息系統(tǒng)的決策動(dòng)作和決策代價(jià)，構(gòu)建了貝葉斯決策模型；再次以最小化決策代價(jià)為原理，推導(dǎo)出了雙論域信息系統(tǒng)模糊概率關(guān)系下決策區(qū)域的三元?jiǎng)澐郑慈Q策模型；最后利用三支決策對(duì)論域的區(qū)域劃分原理，提出了雙論域信息系統(tǒng)的模糊概率三支決策分類算法。進(jìn)行雙論域信息系統(tǒng)的實(shí)驗(yàn)證明了所提出分類算法的有效性和優(yōu)越性。

1 基本理論

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

在某些實(shí)際應(yīng)用環(huán)境，信息系統(tǒng)往往包含了2個(gè)論域，這類信息系統(tǒng)稱之為雙論域信息系統(tǒng)［4］，典型的如個(gè)信息化推薦信息系統(tǒng)。

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

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

當(dāng)U=V，那么雙論域粗糙集退化為傳統(tǒng)的粗糙集，因此雙論域粗糙集是傳統(tǒng)粗糙集的進(jìn)一步推廣，傳統(tǒng)粗糙集是雙論域粗糙集的特例。

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

近年來，學(xué)者們對(duì)雙論域粗糙集模型提出了多種擴(kuò)展模型，其中雙論域模糊概率粗糙集是其研究熱點(diǎn)［12-15］。本節(jié)將雙論域模糊概率粗糙集進(jìn)一步擴(kuò)展，提出一種雙論域模糊概率三支決策模型。

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

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

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

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

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

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

在傳統(tǒng)的分類決策模型中，決策對(duì)象的判定結(jié)果為滿足或不滿足決策標(biāo)準(zhǔn)，然后將對(duì)象集劃分為2個(gè)不相交的決策區(qū)域，即滿足決策準(zhǔn)則對(duì)象的正區(qū)域集和不滿足決策準(zhǔn)則對(duì)象的負(fù)區(qū)域集N。然而，這種二元分類方法通常會(huì)存在一些分類錯(cuò)誤。因此，這種二元分類方法的主要局限是它們對(duì)分類的要求過于嚴(yán)格。

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

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

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

基于貝葉斯決策過程會(huì)得到以下最小代價(jià)決策規(guī)則：

1）執(zhí)行決策P(Y)，當(dāng)且僅當(dāng)

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

2）執(zhí)行決策B(Y)，當(dāng)且僅當(dāng)

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

3）執(zhí)行決策N(Y)，當(dāng)且僅當(dāng)

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

通常決策代價(jià)滿足

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

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

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

1）對(duì)于執(zhí)行決策P(Y)，即

2）對(duì)于執(zhí)行決策B(Y)，即

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

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

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

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

同時(shí)，若代價(jià)滿足如下關(guān)系

此時(shí)有0≤β<γ<α≤1，因此雙論域信息系統(tǒng)最小代價(jià)決策規(guī)則可以簡(jiǎn)化表示為：

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

2）當(dāng)β

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

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

定義5雙論域信息系統(tǒng)，F(xiàn)為論域U和V誘導(dǎo)確定的模糊二元關(guān)系，對(duì)于0≤λ≤1，對(duì)于?x∈U關(guān)于Y?V的模糊概率關(guān)系的三支決策區(qū)域集分別定義為

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

B(Y)={x∈U|β

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

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

學(xué)者們將三支決策模型應(yīng)用于數(shù)據(jù)的分類，提出了多種基于三支決策的分類算法［16］，基于當(dāng)前的可獲取的分類準(zhǔn)則，它將目標(biāo)對(duì)象的分類決策判定為屬于特定類、不屬于特定類以及待定，即當(dāng)前條件可以確定分類的，直接將分類結(jié)果確定為某個(gè)類，對(duì)于那些處于類與類邊緣的對(duì)象，暫時(shí)進(jìn)行待定狀態(tài)，待后續(xù)更多的分類信息被獲取則進(jìn)一步進(jìn)行分類。受此啟發(fā)，本節(jié)將提出雙論域信息系統(tǒng)下的三支決策分類模型，具體如算法1所示。

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

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

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

Step1：計(jì)算雙論域模糊概率關(guān)系Fλ；

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

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

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

Step5：對(duì)于每個(gè)決策類Yi?V，如果β

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

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

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

算法1主要計(jì)算量集中在雙論域模糊概率關(guān)系計(jì)算流程，因此整個(gè)算法1的時(shí)間復(fù)雜度為O(|U|×|V|)。

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

為了消除數(shù)據(jù)集屬性量綱帶來的影響，實(shí)驗(yàn)前將數(shù)據(jù)集進(jìn)行歸一化處理，歸一化方法為

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

針對(duì)本文提出的三支決策分類方法，本實(shí)驗(yàn)提出4種模型評(píng)估指標(biāo)，具體如下定義：

式中：Ac、Pr、Re分別表示準(zhǔn)確度、精度和召回率；NPP、NBP和NNP分別表示原本屬于類別Y采取動(dòng)作dp、db和dn對(duì)象的數(shù)量；NPN、NBN和NNN分別表示原本不屬于Y采取動(dòng)作、和對(duì)象的數(shù)量。

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

圖1 不同λ下精度實(shí)驗(yàn)結(jié)果

圖2 不同λ下實(shí)驗(yàn)結(jié)果

從圖1和圖2可以發(fā)現(xiàn)，隨著λ取值的增加，模型分類的精度值也隨之增加，但達(dá)到0.7之后開始趨于穩(wěn)定。對(duì)于，隨著λ取值的增加，數(shù)據(jù)集MovieLens 1M、MovieLens 1M和Wdbc的值逐漸增加，達(dá)到0.7之后開始趨于穩(wěn)定，因此綜合起來λ=0.7是一個(gè)較佳的取值。

為了驗(yàn)證本文所提出分類算法的優(yōu)越性，本實(shí)驗(yàn)選擇了機(jī)器學(xué)習(xí)領(lǐng)域3種常用的分類器進(jìn)行分類比較，這3種分類器分別為支持向量機(jī)（SVM）、樸素貝葉斯（NB）和k近鄰（kNN，k=3）。表2所示的是各個(gè)數(shù)據(jù)集在三種對(duì)比分類器和本文分類算法下的精度實(shí)驗(yàn)結(jié)果，表3所示的是各個(gè)數(shù)據(jù)集在3種對(duì)比分類器和本文分類算法下的實(shí)驗(yàn)結(jié)果。

表2 各個(gè)數(shù)據(jù)集精度實(shí)驗(yàn)結(jié)果

表3 各個(gè)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

從表2可以發(fā)現(xiàn)，本文分類算法在大部分?jǐn)?shù)據(jù)集下的分類結(jié)果精度值均高于其余3種分類算法。因此從分類精度視角可以看出本文分類算法的性能更優(yōu)。

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

由于本文所提出的三支決策分類算法建立在代價(jià)的基礎(chǔ)上，因此接下來計(jì)算各個(gè)分類算法的誤分類代價(jià)結(jié)果，誤分類代價(jià)即分類算法分類錯(cuò)誤對(duì)象的代價(jià)之和，具體結(jié)果如表4所示。

表4 各個(gè)分類算法誤分類代價(jià)

從表4可以發(fā)現(xiàn)，各個(gè)數(shù)據(jù)集下本文分類算法的誤分類代價(jià)是最低的，尤其對(duì)于數(shù)據(jù)集Jester，其分類精度并不是最高的，但是誤分類代價(jià)最低，這主要是由于對(duì)比的3種分類算法對(duì)每個(gè)對(duì)象進(jìn)行了確定的分類，因此誤分類產(chǎn)生的代價(jià)會(huì)比較高，而本文算法將暫時(shí)不能確定分類的對(duì)象進(jìn)行延遲分類，減少了錯(cuò)誤分類的情形，因此也降低了誤分類的代價(jià)，因此本文算法的誤分類能力整體更優(yōu)。

綜合所有實(shí)驗(yàn)結(jié)果，證明了本文所提出的三支決策分類算法在雙論域信息系統(tǒng)的分類方面具有較優(yōu)的分類性能。

5 結(jié)束語

當(dāng)前的雙論域模糊概率粗糙集還未有三支決策的相關(guān)研究，針對(duì)這一問題，文中在模糊概率粗糙集基礎(chǔ)上定義了雙論域信息系統(tǒng)的決策動(dòng)作和決策代價(jià)，以貝葉斯決策最小化代價(jià)為原理，推導(dǎo)出了雙論域信息系統(tǒng)模糊概率關(guān)系下決策區(qū)域的三支決策模型，最后提出了雙論域信息系統(tǒng)的模糊概率三支決策分類算法。實(shí)驗(yàn)分析證明了所提出分類算法的有效性和優(yōu)越性。接下來將進(jìn)一步對(duì)雙論域信息系統(tǒng)模糊概率三支決策模型進(jìn)行增量式更新方法的研究，提升現(xiàn)實(shí)動(dòng)態(tài)數(shù)據(jù)處理的有效性。