張 杰，張燕蘭*，林藝東

（1.閩南師范大學(xué) 計算機(jī)學(xué)院，福建 漳州 363000；2.廈門大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，福建 廈門 361005）

由Pawlak[1]提出的粗糙集理論是一種處理不確定信息的重要工具，在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和知識發(fā)現(xiàn)等領(lǐng)域有重要的應(yīng)用。在粗糙集理論中，數(shù)據(jù)通常由信息系統(tǒng)來表示，并且由一組特征來描述。然而，這些特征中有許多是冗余的，這使得分類過程更加困難。因此，通過選擇相關(guān)的特征來減少冗余的特征的數(shù)量是很有必要的。屬性約簡的主要目的是去除數(shù)據(jù)集中的冗余信息，這不僅可以減少學(xué)習(xí)算法的運(yùn)行時間，在某些情況下還可以提供更好的分類精度。

在經(jīng)典的粗糙集中，很多學(xué)者已對屬性約簡作了深入的研究[2-4]并取得了重要的結(jié)果。例如，錢宇華等提出了4種尋找屬性約簡的加速算法[5]。然而，基于經(jīng)典Pawlak粗糙集模型的屬性約簡方法只適用于離散型數(shù)據(jù)，并不能直接應(yīng)用于連續(xù)型數(shù)據(jù)。換句話說，屬性約簡之前需要對連續(xù)型數(shù)據(jù)進(jìn)行離散化，而這會造成信息損失和丟失[6]。為此，很多學(xué)者提出了覆蓋粗糙集、相似關(guān)系粗糙集和鄰域粗糙集等廣義粗糙集模型[7-13]。Chen等提出了一種基于覆蓋粗糙集模型的屬性約簡方法[14]，此方法可以用來處理數(shù)值型數(shù)據(jù)，而且不需要對數(shù)值型數(shù)據(jù)離散化，只需轉(zhuǎn)化為一個覆蓋決策系統(tǒng)即可。在此基礎(chǔ)上，Chen等又提出了另一種基于覆蓋粗糙集模型的屬性約簡方法[14]，但是，該算法非常耗時。為了克服這個缺點(diǎn)，Wang等簡化了文獻(xiàn)[14]中辨識矩陣的構(gòu)造，提出了一種更有效的尋找屬性約簡的CDA算法[15]。CDA算法可以有效地處理中等規(guī)模的數(shù)據(jù)集，然而，CDA算法的計算復(fù)雜度隨著樣本和屬性的增加呈指數(shù)增長，且CDA算法可能會得到一個空的特征子集，因此，對于較大數(shù)據(jù)集，需要更有效的屬性約簡方法。于是，Chen等提出了一種基于圖的覆蓋決策信息系統(tǒng)屬性約簡的CDG算法[16]，結(jié)果表明CDG算法比文獻(xiàn)[15]中CDA算法更高效。

本研究在文獻(xiàn)[15]的基礎(chǔ)上研究覆蓋決策信息系統(tǒng)屬性約簡的問題，并在文獻(xiàn)[16]的約簡理論框架下研究基于圖的覆蓋信息系統(tǒng)屬性約簡的新方法，采用的策略是：首先計算覆蓋決策信息系統(tǒng)的辨識集，進(jìn)而得到一個超圖的關(guān)聯(lián)矩陣；然后，基于貪心法求該超圖的極小頂點(diǎn)覆蓋；最后，通過連續(xù)型數(shù)據(jù)實(shí)驗(yàn)分析得知新算法的時間復(fù)雜度為O(|U||A|)，其中|U|與|A|的含義分別是論域的大小、屬性集的大小，這比CDG算法的時間復(fù)雜度O(|U|2|A|)更低。

1 預(yù)備知識

1.1 覆蓋決策信息系統(tǒng)的屬性約簡

在本節(jié)中，先介紹覆蓋粗糙集和圖論的幾個基本概念。稱S=(U,A)是一個信息系統(tǒng)，其中U和A分別是非空有限論域和屬性集。對于任意屬性a∈A，稱a:U→Va是信息函數(shù)，其中Va稱為屬性a的值域。決策信息系統(tǒng)的形式為S=(U,A,wi0oi0o)，其中(U,A)是一個信息系統(tǒng)，A是條件屬性集，d:U→Vd是決策屬性，且d?A。

眾所周知，經(jīng)典粗糙集只能用于處理離散型數(shù)據(jù)。然而，在許多實(shí)際的情況中經(jīng)常要面臨連續(xù)型數(shù)據(jù)的情況。現(xiàn)在回顧相關(guān)文獻(xiàn)中處理連續(xù)型數(shù)據(jù)的屬性約簡方法[14-15，17]。

定義1[17]設(shè)U為論域，C是U的子集族，如果C中不含空集，且∪C=U，則稱C為U的一個覆蓋。

定義2[14]設(shè)C={K1,K2,...,Kn}為U的一個覆蓋，對于每一個x∈U，令Cx=∩{Kj|Kj∈C,x∈Kj}，則Cov(C) ={Cx|x∈U}也是U的一個覆蓋，稱Cov(C)為C誘導(dǎo)的覆蓋。設(shè)Δ ={Ci|i= 1,2,…,m}為U的一族覆蓋，?x∈U，記Δx=∩{(Ci)x|(Ci)x∈Cov(Ci) ,i= 1,2,…,m}，那么Cov(Δ) ={Δx|x∈U}也是U的一個覆蓋，稱Cov(Δ)為Δ的誘導(dǎo)覆蓋。?X?U，X相對于Δ的上、下近似算子定義如下：

通常，對每個數(shù)值型屬性a∈A，可以定義每個樣本x∈U的鄰域。Na(x,ε) ={y∈U|d(x,y)ε}，其中d( ?, ?)是一個距離函數(shù)，ε是指定的閾值。通常，d(x,y) =|a(x) -a(y)|。顯然，Na={Na(x,ε)|x∈U}是U的一個覆蓋，Δ ={Na|a∈A}是U的一個覆蓋族。因此，可以獲得一個覆蓋決策信息系統(tǒng)S=(U,Δ,q0a4umg)。

例1 設(shè)S=(U,A,m0m0ywk)為一個由連續(xù)型屬性組成的決策信息系統(tǒng)（見表1），其中U={x1,x2,x3,x4,x5}，A={a1,a2,a3,a4}，d是決策屬性。

表1 數(shù)值型數(shù)據(jù)表Table 1 Table of numerical data

令閾值ε= 0.20，可以獲得以下覆蓋決策信息系統(tǒng)S=(U,Δ,0cakgmw):

另外，U/d={{x1,x3},{x2,x4,x5}}，記D1={x1,x3}，D2={x2,x4,x5}。

例2（續(xù)例1） 覆蓋決策信息系統(tǒng)S的辨識矩陣如表2所示。為簡單起見，我們對集合使用無分隔符形式，例如，用C1C2C4表示{C1,C2,C4}。

表2 覆蓋決策信息系統(tǒng)S的辨識矩陣Table 2 Discernibility matrix of S

在覆蓋決策信息系統(tǒng)S=(U,Δ,ymku0yu)中，覆蓋C1,C2,…,Cm分別對應(yīng)于m個布爾變量C*1,C*2,…,C*m，則定義辨識函數(shù)fS如下:

這種簡化析取形式的每一個合取式被稱為主蘊(yùn)涵[18]。Wang等通過析取和合取運(yùn)算證明了覆蓋決策信息系統(tǒng)的約簡計算可以轉(zhuǎn)化為布爾函數(shù)的主蘊(yùn)涵的計算[18]。

表3 點(diǎn)的鄰域Table 3 The neighborhood of a point

1.2 超圖的頂點(diǎn)覆蓋

超圖是傳統(tǒng)圖的泛化，超圖里的邊可以連接任意數(shù)量的頂點(diǎn)。一般，超圖H可以表示為(V,ε)，其中V是所有頂點(diǎn)元素的集合，ε是V的非空子集族，ε的元素被稱為超邊或者邊，用E表示。而超圖H的頂點(diǎn)覆蓋K是一個集合K?V，且K與H的每條邊交非空。換句話說，頂點(diǎn)覆蓋是一組覆蓋所有邊的頂點(diǎn)集合。如果K的任意子集均不是頂點(diǎn)覆蓋，則頂點(diǎn)覆蓋K是極小的。極小頂點(diǎn)覆蓋是頂點(diǎn)數(shù)目最少的頂點(diǎn)覆蓋。超圖H的所有極小頂點(diǎn)覆蓋的集合用T(H)表示。與粗糙集中的屬性約簡方法相似，超圖的所有極小頂點(diǎn)覆蓋也可以通過邏輯表達(dá)式得到。

2 基于圖的覆蓋決策信息系統(tǒng)的屬性約簡

從引理1和引理2可以看出，覆蓋決策信息系統(tǒng)的屬性約簡與超圖的極小頂點(diǎn)覆蓋之間存在聯(lián)系。在本節(jié)中，我們首先介紹由覆蓋決策信息系統(tǒng)誘導(dǎo)出的超圖，然后討論導(dǎo)出超圖的極小頂點(diǎn)覆蓋與覆蓋決策信息系統(tǒng)屬性約簡之間的關(guān)系，最后，提出一種基于圖的覆蓋決策信息系統(tǒng)屬性約簡的近似算法。

2.1 覆蓋決策信息系統(tǒng)中的超圖

定義5[16]設(shè)S=(U,Δ,muke0s0)為覆蓋決策信息系統(tǒng)，其中Δ ={C1,C2,…,Cm}，Μ′是S的可分辨識集，M*={M∈M′|M≠Δ}。令V= Δ,ε=M*，稱H=(V,ε)為S的誘導(dǎo)圖。

定義5是在文獻(xiàn)[3]的基礎(chǔ)上給出的，僅適用于分類數(shù)據(jù)。回想一下，超圖是傳統(tǒng)圖的泛化。覆蓋決策信息系統(tǒng)的誘導(dǎo)圖H可能是一個傳統(tǒng)的圖，但在大多數(shù)情況下，它是一個超圖。因此，如果不存在歧義，我們就把定義5中的誘導(dǎo)圖稱為超圖。

例5（續(xù)例1） 易知：M*={{C2,C4},{C1,C2,C4},{C1,C3,C4}}。S誘導(dǎo)的超圖H=(V,ε)為：ε={{C2,C4},{C1,C2,C4},{C1,C3,C4}}，V={C1,C2,C3,C4}。

通過引理1、引理2以及定義5，可得到下面的結(jié)果。

定理1[16]設(shè)H=(V,ε)為覆蓋決策信息系統(tǒng)S誘導(dǎo)的一個超圖，則Red(S)=T(H)。

定理1給出一個覆蓋決策信息系統(tǒng)屬性約簡的圖模型?？梢钥吹?，求一個覆蓋決策信息系統(tǒng)的所有約簡可以看作是求一個超圖極小頂點(diǎn)覆蓋集，這為我們提供了獲取覆蓋決策信息系統(tǒng)屬性約簡的新方法。

例6（續(xù)例5） 知：Re d(S) ={{C4},{C1,C2},{C2,C3}}。從例4 誘導(dǎo)的超圖所有極小頂點(diǎn)覆蓋集合為：T(H)={{C4},{C1,C2},{C2,C3}}。

因此，有Red(S) =T(H)。

2.2 覆蓋決策信息系統(tǒng)的屬性約簡算法

在實(shí)際應(yīng)用中，沒有必要找出覆蓋決策信息系統(tǒng)的所有約簡，只需要找到一個約簡。此外，相較于效率來說，找到約簡是否為最小并不是很重要。在大多數(shù)文獻(xiàn)中，粗糙集屬性約簡算法得到的是次優(yōu)約簡。在本小節(jié)中，將給出一種新的基于圖的覆蓋決策系統(tǒng)屬性約簡的近似算法，其中生成覆蓋決策表的超圖是構(gòu)造上述約簡算法的關(guān)鍵步驟之一。接下來將用關(guān)聯(lián)矩陣的簡單表示設(shè)計一個快捷計算超圖的算法。超圖H=(V,ε)的關(guān)聯(lián)矩陣是一個m×n的矩陣MH=(mij)m×n，其中|ε| =m，|V| =n。若邊Ei和頂點(diǎn)vj是關(guān)聯(lián)的，則mij= 1；否則，mij= 0。

例7（續(xù)例4） 例4 所示的超圖關(guān)聯(lián)矩陣是一個由3 行(對應(yīng)于3 條邊E1～E3)和4 列(對應(yīng)于4 個頂點(diǎn)V1～V4)組成的矩陣，見表4。

表4 例4中超圖H的關(guān)聯(lián)矩陣Table 4 Incidence matrix of hypergraph H of example 4

下面給出生成覆蓋決策信息系統(tǒng)的超圖的算法：

算法1 生成覆蓋決策信息系統(tǒng)的超圖（CDG1）

輸入：一個決策信息系統(tǒng)S=(U,Δ,ueqsquw)和ε；//ε是一個閾值；

輸出：超圖MH。

1.forx∈Udo

2.if d(x)≠d(y)then

3.M'(x,y) ={|data - title(data)| >ε}//title(data)對原數(shù)據(jù)集的每一行復(fù)制并平鋪

4.MH G(M'(x,y))

5.end if

6.end for

7.刪除MH多余的行，且刪除和等于0或|A|的那一行。

由于CDG1算法僅有一層循環(huán)，其計算的時間復(fù)雜度為O(|U||A|)，相較于文獻(xiàn)[16]中算法1的時間復(fù)雜度O(|U|2|A|)更低。值得注意的是由算法1生成的辨識集M' ={M'(x,y)|x,y∈U}與定義4中定義的辨識集不一樣。但是，M′比定義4中M更容易實(shí)現(xiàn)，因?yàn)閷τ谌魏胃采wC∈Δ都不需要再計算Cx。事實(shí)上，它們有如下關(guān)系：

命題2[16]令H=(V,ε)和H' =(V,ε')是兩個超圖，滿足任何E∈ε，E' ∈ε'，則E' ?E。如果K?V是H'的極小頂點(diǎn)覆蓋，那么K也是H的一個頂點(diǎn)覆蓋。

根據(jù)命題1和2，得到以下結(jié)果：

定理2[16]設(shè)S=(U,A,iqy0cim)為決策信息系統(tǒng)。M'和M分別是由算法1和定義4生成的兩個辨識集。如果P?Δ是M'的一個約簡，則POSP(d)= POSΔ(d)。

定理2為我們構(gòu)造新的屬性約簡算法提供了基礎(chǔ)。結(jié)合定理1可知，由算法1導(dǎo)出超圖的極小頂點(diǎn)覆蓋可以得到一個決策表的近似約簡。根據(jù)上述結(jié)果，我們設(shè)計一種新的覆蓋決策信息系統(tǒng)屬性約簡近似算法2。

算法2 基于圖的覆蓋決策信息系統(tǒng)的約簡算法（CDG2）

輸入：一個決策信息系統(tǒng)S=(U,A∪kqo0gkq)和ε；

輸出：一個約簡Red。

1.生成超圖MH=(V,ε)；//參見算法1

2.令Red= ?

3.whileε≠?do

4.v0= arg max{dMH(v)|v∈Vx}，

Red[Red,v0]；//去掉E中被Red所覆蓋的邊，并仍記為E

5.end while

6.if Red -{v}//能覆蓋簡化圖G的所有邊

7.Red Red -{v}

8.end if

9.輸出Red。

該算法的主要思想是基于求超圖極小頂點(diǎn)覆蓋的貪心法[9，14]，步驟1～8 的時間復(fù)雜度為O(|U||A|)。因此，CDG2的時間復(fù)雜度為O(|U||A|)，比文獻(xiàn)[16]中算法2的時間復(fù)雜度O(|U|2|A|)更低。為了驗(yàn)證該算法的有效性，將其與文獻(xiàn)[16]中的CDG的算法進(jìn)行了比較。比較的指標(biāo)有：生成辨識集的運(yùn)行時間、生成約簡集的運(yùn)行時間、約簡的程度。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)準(zhǔn)備

所有的算法都是在Python3.6中實(shí)現(xiàn)的，并在裝有Windows 7的個人電腦上運(yùn)行，其他要素為：雙核處理器，采用串行編程，CPU 主頻為2.4 GHZ，睿頻為3.0 GHZ，內(nèi)存為10 GB。實(shí)驗(yàn)選用10個公開的數(shù)據(jù)集進(jìn)行驗(yàn)證。具體的數(shù)據(jù)集描述見表5。

3.2 實(shí)驗(yàn)比較

表5記錄了從UCI公開數(shù)據(jù)集中選取10個常見的數(shù)據(jù)集，有小樣本，也有高維小樣本，以檢驗(yàn)本文算法在真實(shí)數(shù)據(jù)集上的有效性。具體實(shí)驗(yàn)結(jié)果如表6～8所示。

表5 實(shí)驗(yàn)數(shù)據(jù)集Table 5 Experimental data set

表6 約簡后的屬性數(shù)量Table 6 Number of attributes after reduction

表7 辨識集的運(yùn)行時間Table 7 Running time of identification data set ms

表6為CDG2算法和CDG算法對10個數(shù)據(jù)集具體的約簡結(jié)果。從表中可以看出，本文提出的CDG2算法和CDG算法都可以獲得極小的屬性子集，CDG2算法在獲得的極小屬性子集的數(shù)目上也保持著優(yōu)勢，實(shí)際上它們均能獲得一個真正的約簡集。

表8為CDG2算法和CDG算法在8個數(shù)據(jù)集上產(chǎn)生約簡集的運(yùn)行時間。從表中可以看出，本研究提出的CDG2算法在Aggregation 數(shù)據(jù)集上得到約簡集的時間是CDG 算法的14.24%，在Car 數(shù)據(jù)集上得到約簡集的時間是CDG算法的21.23%，在Glass數(shù)據(jù)集上得到約簡集的時間優(yōu)勢更加明顯。由此可見，CDG2算法計算約簡運(yùn)行時間均小于CDG算法，這些數(shù)據(jù)結(jié)果進(jìn)一步表明CDG2算法是一種高效的屬性約簡方法。綜上可知，CDG2算法優(yōu)于CDG算法。

表8 約簡集的運(yùn)行時間Table 8 Running time of reduced set ms

4 結(jié)論

屬性約簡是粗糙集領(lǐng)域重要的研究內(nèi)容之一。本研究提出了一個基于圖的覆蓋決策信息系統(tǒng)屬性約簡的貪心算法，該算法可以直接處理數(shù)值型數(shù)據(jù)。此外，與文獻(xiàn)[16]的CDG算法相比，CDG2算法方法更適合處理高維大數(shù)據(jù)集，同時，CDG2算法有較低的時間復(fù)雜度，并通過實(shí)例和數(shù)值型實(shí)驗(yàn)驗(yàn)證了該算法的有效性，該方法可以看作是一種局部逼近最優(yōu)的特征選擇策略。然而，如何進(jìn)一步獲得最小頂點(diǎn)覆蓋以生成一個盡可能接近最優(yōu)解的最小特征子集，這是我們后續(xù)的主要研究方向之一。