復(fù)合決策粗糙建模與計算方法研究

汪琳娜，楊 新，楊習(xí)貝

1.四川工商學(xué)院 電子信息工程學(xué)院，成都 611745

2.Department of Computer Science,University of Regina,Regina,Saskatchewan,S4S 0A2

3.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756

4.江蘇科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003

1 引言

粗糙集理論是一種處理不確定性信息的粒計算模型之一，最早是由波蘭數(shù)學(xué)家Pawlak[1]在集合論的基礎(chǔ)上提出。該理論可以在缺少任何先驗信息的基礎(chǔ)上對數(shù)據(jù)進(jìn)行有效處理，目前已廣泛應(yīng)用于醫(yī)療診斷、模式識別和人工智能等領(lǐng)域[2-5]。

在大數(shù)據(jù)時代數(shù)據(jù)類型通常呈現(xiàn)出多樣化等特點。經(jīng)典粗糙集通過二元等價關(guān)系對全體論域進(jìn)行劃分，運用嚴(yán)格的代數(shù)包含運算定義上近似集和下近似集，對不確定的知識進(jìn)行刻畫。但是在實際信息系統(tǒng)中，數(shù)據(jù)類型包含名義型、數(shù)值型、集值型、區(qū)間型和缺失型等，經(jīng)典粗糙集不能有效處理以上類型的數(shù)據(jù)。為解決此問題，各種不同的二元關(guān)系被相繼提出，如鄰域關(guān)系[6]、偏序關(guān)系[7]、相容關(guān)系[8]、容差關(guān)系[9]等。針對各種單一類型數(shù)據(jù)，可以分別運用以上關(guān)系在粗糙集中對對象進(jìn)行?；幚?，但是如何在粗糙集中同時對多種類型數(shù)據(jù)進(jìn)行融合處理仍然是當(dāng)前研究難點之一。目前有部分學(xué)者針對此問題開展了相關(guān)研究。Zhang等[10]通過嚴(yán)格的交運算針對等價關(guān)系、鄰域關(guān)系、容差關(guān)系和特征關(guān)系定義了復(fù)合二元關(guān)系，進(jìn)而提出了一種能夠融合名義型、數(shù)值型、集值型和缺失型4種數(shù)據(jù)類型的復(fù)合粗糙集模型，給出了計算上下近似集的矩陣計算方法。Qian等[11]在多粒度空間下給出了融合多種關(guān)系的多粒度粗糙集模型，并進(jìn)一步提出了悲觀和樂觀的多粒度決策粗糙集模型。Chen等[12]在概率粗糙集模型下給出了廣義的復(fù)合概率粗糙集模型，并且研究了復(fù)雜數(shù)據(jù)下的最大分布約簡問題。通過定義復(fù)合優(yōu)勢關(guān)系，羅川等[13]建立了基于復(fù)合有序二元關(guān)系的粗糙集模型。從以上研究可以發(fā)現(xiàn)，在粗糙集視角下處理復(fù)雜數(shù)據(jù)的關(guān)鍵是定義能夠合理融合多種數(shù)據(jù)類型的復(fù)合關(guān)系。但是以上關(guān)于復(fù)雜數(shù)據(jù)融合的研究都沒有考慮代價敏感的決策粗糙集方法。

Yao等[14]提出的決策粗糙集（Decision-theoretic Rough Set，DTRS）通過引入貝葉斯決策理論，在考慮期望決策風(fēng)險代價最小的情況下給出了計算閾值的合理數(shù)學(xué)公式表達(dá)，為代價敏感的粗糙集決策提供了切實可行的方法。近年來，決策粗糙集以及由其導(dǎo)出的三支決策理論已經(jīng)廣泛地用來解決郵件過濾、石油投資、圖像處理等問題[15-20]。本文以決策粗糙集模型為研究對象，采用多個二元關(guān)系處理各種類型的數(shù)據(jù)，然后在矩陣視角下探討了不同二元關(guān)系的融合機(jī)制，并提出了基于量化復(fù)合關(guān)系的決策粗糙集模型及其矩陣計算方法，最后通過UCI數(shù)據(jù)集驗證和分析了模型的有效性和穩(wěn)定性。

2 決策粗糙集

定義1[1]一個具有單一數(shù)據(jù)類型的信息系統(tǒng)（簡稱為單類信息系統(tǒng)）可以定義為一個四元組S=(U,AT,V,f)：U是非空有限的對象集合；AT是非空有限的屬性集合，中每個屬性的類型相同；是值域，Va是對象在屬性a下的所有可能取值；f:U×A→V是一個映射函數(shù)，使得?a∈AT,x∈U,f(x,a)∈Va。

定義2[1]設(shè)S是一個單類信息系統(tǒng)。，EA是論域U上由A誘導(dǎo)出的一個等價關(guān)系，定義為：

根據(jù)式（1），論域U在等價關(guān)系EA下被分成若干等價類，記為，其中[x]EA稱為包含對象x的等價類。?X?U，經(jīng)典粗糙集的上下近似集可以定義為：

針對經(jīng)典粗糙集模型缺乏容錯能力的問題，引入概率近似空間可以得到概率粗糙集模型。

定義3[14]設(shè)S是一個單類信息系統(tǒng)。給定一對閾值對 (α,β)，其中 0≤β＜α≤1，則概率粗糙集模型的上下近似集可以定義為：

下面以二分類問題為例。在單類信息系統(tǒng)S中，可以用具有2個狀態(tài)的集合Ω={X,?X}和3個行動的集合A={aP,aB,aN}來描述貝葉斯決策過程。其中狀態(tài)集中X和?X互補(bǔ)，行動集中aP、aB、aN分別表示將對象分類到正域、邊界域和負(fù)域的決策動作。給定一個損失函數(shù)矩陣如下：

其中，λPP,λBP,λNP分別表示當(dāng)狀態(tài)為X時采取行動aP、aB、aN下的損失，λPN,λBN,λNN分別表示當(dāng)狀態(tài)為?X時采取行動aP、aB、aN下的損失。因此可以給出分別采取行動aP、aB、aN下的期望損失為：

根據(jù)貝葉斯決策準(zhǔn)則，我們會選擇期望損失最小的行動集作為最佳的行動方案。通過推導(dǎo)（詳細(xì)過程可參見文獻(xiàn)[14]），可以得到關(guān)于閾值對 (α,β)的具體計算公式如下：

3 復(fù)合決策粗糙集模型

經(jīng)典決策粗糙集模型只能運用等價關(guān)系處理名義型數(shù)據(jù)的分類和決策問題。在本章中，討論了多種類型共存的復(fù)雜數(shù)據(jù)的三種融合策略，并提出了一種基于量化復(fù)合關(guān)系的決策粗糙集擴(kuò)展模型，探討針對復(fù)雜數(shù)據(jù)的代價敏感決策問題。

例1表1給出了一個復(fù)合信息系統(tǒng)CS示例，其中論域，屬性其中AT′前4個屬性子集的數(shù)據(jù)類型分別為名義型、數(shù)值型、區(qū)間型、集值型，第5個屬性子集為名義型的決策屬性。

表1 復(fù)合信息系統(tǒng)

定義5[10]設(shè)R是一個二元關(guān)系，則可以給出U上關(guān)于R的關(guān)系矩陣，其中：

其中RCi表示同一數(shù)據(jù)類型在屬性集Ci上的二元關(guān)系，上式也可簡記為：

其中RCi表示同一數(shù)據(jù)類型在屬性集Ci上的二元關(guān)系，上式也可簡記為：

在復(fù)合信息系統(tǒng)下，以上給出了關(guān)于多個二元關(guān)系的交-復(fù)合關(guān)系和并-復(fù)合關(guān)系。交-復(fù)合關(guān)系比較嚴(yán)格，要求兩個對象要滿足每一個二元關(guān)系，容易造成粒化過細(xì)；并-復(fù)合關(guān)系相對寬松，只要求兩個對象滿足其中任一個二元關(guān)系，但容易造成?；^粗。因此為了得到可以量化的復(fù)合關(guān)系，給出以下定義。

其中k表示二元關(guān)系的數(shù)量（每一個數(shù)據(jù)類型對應(yīng)一個二元關(guān)系）表示兩個對象間滿足二元關(guān)系的總數(shù)量。此時關(guān)于QCRC的復(fù)合關(guān)系矩陣MQRCC=的元素可以表示為：

由上式可知，量化復(fù)合關(guān)系滿足自反性，不一定滿足對稱性和傳遞性。

由定理1可知，量化復(fù)合關(guān)系是并-復(fù)合關(guān)系和交-復(fù)合關(guān)系的推廣形式。下面基于量化復(fù)合關(guān)系給出復(fù)合決策粗糙集的定義。

定義9給定一個復(fù)合信息系統(tǒng)CS，則復(fù)合決策粗糙集的上下近似集可以定義為：

下面給出復(fù)合決策粗糙集的一些性質(zhì)。

4 近似集的矩陣計算

通過對多個二元關(guān)系的量化融合處理，可以利用閾值θ有效控制數(shù)據(jù)融合的效果，并運用復(fù)合決策粗糙集對復(fù)合信息系統(tǒng)進(jìn)行代價敏感分類和決策。下面采用布爾矩陣分析二元關(guān)系融合處理的過程，并給出了一種新的復(fù)合決策粗糙近似集的矩陣直觀計算方法。

定義10[10]設(shè)U={x1,x2,…,xn}是一個非空有限的對象集合，X是U的任意一個非空子集，即，則X可以表示為布爾矩陣如下：

其中V(X)為X在U上的特征矩陣，T為矩陣的轉(zhuǎn)置運算。

例2在表1中，給定一個復(fù)合信息系統(tǒng)CS，其中論域U={x1,x2,x3,x4,x5,x6}。假設(shè)X={x1,x2,x4, }x6，則X在U上的特征矩陣為V(x)=[1,1,0,1,0,1]T。

表1中存在名義型、數(shù)值型、區(qū)間型、集值型數(shù)據(jù)，因此可以分別運用等價關(guān)系、鄰域關(guān)系、偏序關(guān)系、相容關(guān)系計算不同類型屬性集合下的二元關(guān)系。

（1）如果屬性集Ci是名義型數(shù)據(jù)，則采用定義2中的等價關(guān)系計算關(guān)系矩陣。

（2）如果屬性集Ci是數(shù)值型數(shù)據(jù)，則采用歐氏距離空間下的鄰域關(guān)系[6]計算關(guān)系矩陣，可以表達(dá)為：

（3）如果屬性集Ci是區(qū)間型數(shù)據(jù)，則采用偏序關(guān)系[7]計算關(guān)系矩陣，可以表達(dá)為：

（4）如果屬性集Ci是集值型數(shù)據(jù)，則采用相容關(guān)系[8]計算關(guān)系矩陣，可以表達(dá)為：

例3假設(shè)鄰域關(guān)系中的δ=0.1，根據(jù)以上4種二元關(guān)系，可以對表1中的數(shù)據(jù)分別計算得到各自的關(guān)系矩陣如下：

由以上4個關(guān)系矩陣可以得到交-復(fù)合關(guān)系CR?C下的復(fù)合關(guān)系矩陣為：

假設(shè)量化閾值θ=0.7，則量化復(fù)合關(guān)系QCRC下的復(fù)合關(guān)系矩陣為：

文獻(xiàn)[10]和[13]中均是運用特征矩陣、關(guān)系矩陣及其誘導(dǎo)矩陣三者的數(shù)量積運算和截矩陣計算粗糙集的上下近似集。與以上文獻(xiàn)不同，下面給出一個更加簡潔的矩陣計算近似集的方法。根據(jù)文獻(xiàn)[21]，首先給出復(fù)合決策粗糙集的一個等價定義。

定義12給定一個復(fù)合信息系統(tǒng)CS，則復(fù)合決策粗糙集的上下近似集還可以定義為：

定義13假設(shè)一個矩陣Mn×1，則兩個截矩陣可以表示為：

根據(jù)以上定義的特征矩陣、復(fù)合關(guān)系矩陣和截矩陣，下面在不計算誘導(dǎo)矩陣的前提下給出更加直觀的矩陣計算復(fù)合決策粗糙近似集的方法。

定義14給定一個復(fù)合信息系統(tǒng)CS，X是U的任意一個非空子集，即X?U，V(X)為X在U上的特征矩陣。QCRC是量化復(fù)合關(guān)系，由其誘導(dǎo)出的復(fù)合關(guān)系矩陣為MQCRC，M↓和M↑為兩個截矩陣，則基于量化復(fù)合關(guān)系的復(fù)合決策粗糙集上下近似集的矩陣計算方法可定義為：

定義14給出了基于布爾代數(shù)構(gòu)造復(fù)合決策粗糙近似集的方法，計算過程簡單直觀，為決策粗糙集中處理和運算復(fù)雜大數(shù)據(jù)提供了一個新的方法。具體計算過程如下所示。

算法1矩陣計算復(fù)合決策粗糙集的上下近似集

輸出：上下近似集的特征矩陣。

步驟1計算概念X的特征矩陣V(X)；

步驟2按照不同數(shù)據(jù)類型根據(jù)不同的二元關(guān)系分別計算他們的關(guān)系矩陣

步驟3計算量化復(fù)合關(guān)系矩陣MQCRC；

步驟4計算交矩陣和非交矩陣V(?X)；

步驟5根據(jù)截矩陣計算上下近似集的特征矩陣。

由以上分析可以得出，算法時間花費主要集中在構(gòu)建關(guān)系矩陣。

例4對表1中的復(fù)合信息系統(tǒng)CS，根據(jù)例1～3的結(jié)果和定義14，假設(shè)代價矩陣為：

則根據(jù)定義12可以計算出新閾值對α′=3，β′=0.75。可以用矩陣的方法得出復(fù)合決策粗糙集模型的下近似集為：

同理可得復(fù)合決策粗糙集模型的上近似集為：

根據(jù)以上矩陣計算結(jié)果，可以得到復(fù)合決策粗糙集模型的上下近似集為：

5 實驗分析

為了分析和驗證本文提出的復(fù)合決策粗糙集模型的有效性和矩陣方法的穩(wěn)定性，從UCI數(shù)據(jù)集中挑選了2組數(shù)值型數(shù)據(jù)集，并通過機(jī)器自動生成了2組多類型共存數(shù)據(jù)集，具體數(shù)據(jù)信息見表2所示。

表2 數(shù)據(jù)集信息

所有實驗都在PC電腦上運行，其配置為Intel?Core?i5-4210U CPU@1.70 GHz，12 GB內(nèi)存，Windows10 操作系統(tǒng)，Matlab2016a實驗平臺。在實驗中挑選了10組鄰域閾值參數(shù)δ，分別為0.05，0.1，…，0.5，并設(shè)置量化閾值θ=0.7來分析矩陣計算所用時間組成。具體實驗效果如圖1所示。

圖1中（a）、（b）、（c）、（d）分別描述4個數(shù)據(jù)集在復(fù)合決策粗糙集中近似集的矩陣計算時間組成。在圖1（a）和（b）中，可以觀察到在不同鄰域下的矩陣計算時間相差不大，而且關(guān)系矩陣計算時間占總計算時間比例都超過95%。在圖（c）和（d）中，給出了4種不同類型數(shù)據(jù)的關(guān)系矩陣和近似集的計算時間曲線。通過比較發(fā)現(xiàn)，4個關(guān)系矩陣花費時間從高到低分別是區(qū)間型、集值型、數(shù)值型和名義型。在不同鄰域閾值下，近似集的總計算時間沒有太大變化，說明矩陣算法在時間消耗方面比較穩(wěn)定。

6 結(jié)束語

針對經(jīng)典決策粗糙集不能有效處理復(fù)合信息系統(tǒng)中的分類和決策問題，本文通過深入研究多種二元關(guān)系的融合機(jī)制，提出了基于量化復(fù)合關(guān)系的決策粗糙集模型，并給出了一種新的矩陣計算上下近似集的方法，通過實例和UCI數(shù)據(jù)集分析了模型和算法的有效性和穩(wěn)定性。在以上研究中，數(shù)據(jù)類型沒有涉及音頻、視頻、文本等，下一步工作，計劃在多模態(tài)復(fù)合信息系統(tǒng)下運用決策粗糙集開展代價敏感決策研究。

圖1 近似集的矩陣計算時間分析