復合決策粗糙建模與計算方法研究

汪琳娜，楊 新，楊習貝

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

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

3.西南交通大學 信息科學與技術學院，成都 611756

4.江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003

1 引言

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

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

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

2 決策粗糙集

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

定義2[1]設S是一個單類信息系統。，EA是論域U上由A誘導出的一個等價關系，定義為：

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

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

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

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

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

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

3 復合決策粗糙集模型

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

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

表1 復合信息系統

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

其中RCi表示同一數據類型在屬性集Ci上的二元關系，上式也可簡記為：

其中RCi表示同一數據類型在屬性集Ci上的二元關系，上式也可簡記為：

在復合信息系統下，以上給出了關于多個二元關系的交-復合關系和并-復合關系。交-復合關系比較嚴格，要求兩個對象要滿足每一個二元關系，容易造成粒化過細；并-復合關系相對寬松，只要求兩個對象滿足其中任一個二元關系，但容易造成粒化過粗。因此為了得到可以量化的復合關系，給出以下定義。

其中k表示二元關系的數量（每一個數據類型對應一個二元關系）表示兩個對象間滿足二元關系的總數量。此時關于QCRC的復合關系矩陣MQRCC=的元素可以表示為：

由上式可知，量化復合關系滿足自反性，不一定滿足對稱性和傳遞性。

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

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

下面給出復合決策粗糙集的一些性質。

4 近似集的矩陣計算

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

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

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

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

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

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

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

（3）如果屬性集Ci是區間型數據，則采用偏序關系[7]計算關系矩陣，可以表達為：

（4）如果屬性集Ci是集值型數據，則采用相容關系[8]計算關系矩陣，可以表達為：

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

由以上4個關系矩陣可以得到交-復合關系CR?C下的復合關系矩陣為：

假設量化閾值θ=0.7，則量化復合關系QCRC下的復合關系矩陣為：

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

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

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

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

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

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

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

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

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

步驟2按照不同數據類型根據不同的二元關系分別計算他們的關系矩陣

步驟3計算量化復合關系矩陣MQCRC；

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

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

由以上分析可以得出，算法時間花費主要集中在構建關系矩陣。

例4對表1中的復合信息系統CS，根據例1～3的結果和定義14，假設代價矩陣為：

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

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

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

5 實驗分析

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

表2 數據集信息

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

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

6 結束語

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

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