張 杰，張燕蘭*，林藝東

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

定義2[14]設(shè)C={K1,K2,...,Kn}為U的一個(gè)覆蓋，對(duì)于每一個(gè)x∈U，令Cx=∩{Kj|Kj∈C,x∈Kj}，則Cov(C) ={Cx|x∈U}也是U的一個(gè)覆蓋，稱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的一個(gè)覆蓋，稱Cov(Δ)為Δ的誘導(dǎo)覆蓋。?X?U，X相對(duì)于Δ的上、下近似算子定義如下：

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

例1 設(shè)S=(U,A,syggg00)為一個(gè)由連續(xù)型屬性組成的決策信息系統(tǒng)（見(jiàn)表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,Δ,syggg00):

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

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

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

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

這種簡(jiǎn)化析取形式的每一個(gè)合取式被稱為主蘊(yùn)涵[18]。Wang等通過(guò)析取和合取運(yùn)算證明了覆蓋決策信息系統(tǒng)的約簡(jiǎn)計(jì)算可以轉(zhuǎn)化為布爾函數(shù)的主蘊(yùn)涵的計(jì)算[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是一個(gè)集合K?V，且K與H的每條邊交非空。換句話說(shuō)，頂點(diǎn)覆蓋是一組覆蓋所有邊的頂點(diǎn)集合。如果K的任意子集均不是頂點(diǎn)覆蓋，則頂點(diǎn)覆蓋K是極小的。極小頂點(diǎn)覆蓋是頂點(diǎn)數(shù)目最少的頂點(diǎn)覆蓋。超圖H的所有極小頂點(diǎn)覆蓋的集合用T(H)表示。與粗糙集中的屬性約簡(jiǎn)方法相似，超圖的所有極小頂點(diǎn)覆蓋也可以通過(guò)邏輯表達(dá)式得到。

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

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

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

定義5[16]設(shè)S=(U,Δ,syggg00)為覆蓋決策信息系統(tǒng)，其中Δ ={C1,C2,…,Cm}，Μ′是S的可分辨識(shí)集，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可能是一個(gè)傳統(tǒng)的圖，但在大多數(shù)情況下，它是一個(gè)超圖。因此，如果不存在歧義，我們就把定義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}。

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

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

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

例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)的屬性約簡(jiǎn)算法

在實(shí)際應(yīng)用中，沒(méi)有必要找出覆蓋決策信息系統(tǒng)的所有約簡(jiǎn)，只需要找到一個(gè)約簡(jiǎn)。此外，相較于效率來(lái)說(shuō)，找到約簡(jiǎn)是否為最小并不是很重要。在大多數(shù)文獻(xiàn)中，粗糙集屬性約簡(jiǎn)算法得到的是次優(yōu)約簡(jiǎn)。在本小節(jié)中，將給出一種新的基于圖的覆蓋決策系統(tǒng)屬性約簡(jiǎn)的近似算法，其中生成覆蓋決策表的超圖是構(gòu)造上述約簡(jiǎn)算法的關(guān)鍵步驟之一。接下來(lái)將用關(guān)聯(lián)矩陣的簡(jiǎn)單表示設(shè)計(jì)一個(gè)快捷計(jì)算超圖的算法。超圖H=(V,ε)的關(guān)聯(lián)矩陣是一個(gè)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)矩陣是一個(gè)由3 行(對(duì)應(yīng)于3 條邊E1～E3)和4 列(對(duì)應(yīng)于4 個(gè)頂點(diǎn)V1～V4)組成的矩陣，見(jiàn)表4。

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

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

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

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

輸出：超圖MH。

1.forx∈Udo

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

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

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

5.end if

6.end for

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

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

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

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

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

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

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

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

輸出：一個(gè)約簡(jiǎn)Red。

1.生成超圖MH=(V,ε)；//參見(jiàn)算法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}//能覆蓋簡(jiǎn)化圖G的所有邊

7.Red Red -{v}

8.end if

9.輸出Red。

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

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

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

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

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

表5記錄了從UCI公開(kāi)數(shù)據(jù)集中選取10個(gè)常見(jiàn)的數(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 約簡(jiǎn)后的屬性數(shù)量Table 6 Number of attributes after reduction

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

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

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

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

4 結(jié)論

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