基于集覆蓋理論的覆蓋信息系統屬性約簡方法

徐 曄, 許晴媛, 李進金

(1.閩南師范大學 計算機學院 福建 漳州 363000; 2.閩南師范大學 數據科學與智能應用福建省 高校重點實驗室 福建 漳州 363000; 3.閩南師范大學 數學與統計學院 福建 漳州 363000; 4.閩南師范大學 福建省粒計算及其應用重點實驗室 福建 漳州 363000)

0 引言

粗糙集理論是用于處理各種不確定性信息的有效工具[1-2],已成功應用在機器學習、模式識別等人工智能領域。然而,現實中的各類信息系統具有不同類型的屬性,如數值屬性、集值屬性、缺失屬性等,經典粗糙集理論在處理這些數據時具有局限性。因此,人們提出許多方法去推廣經典粗糙集理論,例如多粒度近似空間的模糊粗糙集[3]、多粒度決策粗糙集[4]、覆蓋粗糙集[5]等。其中,覆蓋粗糙集是一個比較重要的推廣方向。

覆蓋信息系統屬性約簡問題是覆蓋粗糙集方向的重要研究課題,探索覆蓋信息系統的屬性約簡方法是當前的研究熱點[6-10]。其中,文獻[6]通過產生相同上、下近似最小覆蓋的方法得到屬性約簡,為覆蓋信息系統屬性約簡提供了一種有效的方法;文獻[7]利用區分矩陣求解覆蓋信息系統的屬性約簡;文獻[8]在文獻[6]的基礎上利用信息熵刻畫了覆蓋約簡的粗糙性。

集覆蓋問題是一個優化問題,已廣泛應用于航空人員調度、運輸車輛路線安排、服務位置、制造作業分配、操作人員選擇等領域。解決集覆蓋問題的經典算法有人工蜂群算法[11]、DNA計算方法[12]、貪心算法[13]及近似算法[14]等。改進集覆蓋問題的經典算法是當前的研究熱點[15-17],例如文獻[16]針對unicost集覆蓋問題,提出一種改進的基于配置檢查的算法。近年來,出現了集覆蓋問題與粗糙集屬性約簡問題的交叉研究。其中,文獻[18]提出利用集覆蓋問題解決傳統粗糙集屬性約簡問題;文獻[19-20]提出利用集覆蓋問題解決粗糙集擴展領域的屬性約簡問題。反過來,利用粗糙集理論來解決集覆蓋問題的方法也相繼被提出[21-24]。

本文提出一種把覆蓋信息系統的屬性約簡問題轉化為集覆蓋問題的方法,并應用集覆蓋理論來研究覆蓋信息系統的屬性約簡問題。通過構造覆蓋信息系統的相關矩陣誘導出覆蓋信息系統的集覆蓋模型,進而建立集覆蓋問題與覆蓋信息系統屬性約簡問題之間的聯系,得出集覆蓋模型的一個極小覆蓋恰是原覆蓋信息系統的一個屬性約簡集,從而可以借助高效的集覆蓋理論來求解覆蓋信息系統的屬性約簡問題。集覆蓋啟發式算法(set covering heuristic algorithm,SCHA)[25]在解決集覆蓋問題上具有較高的精度與較好的性能,本文給出了基于SCHA求解覆蓋信息系統屬性約簡的算法,并通過一個實例驗證了所提方法的可行性和有效性。本文工作豐富了集覆蓋理論與覆蓋粗糙集理論的交叉研究,為覆蓋信息系統的屬性約簡問題帶來了新的思路與方法,同時拓展了集覆蓋理論的應用領域。

1 基本概念

1.1 集覆蓋問題

定義1設E={xq:1≤q≤y}是一個非空有限對象集合,S={Sw:1≤w≤r}是E的若干非空子集構成的集族。若∪S=E,則稱S為E的一個集覆蓋,稱(E,S)為一個集覆蓋模型。集覆蓋問題在于求解S的一個非空子集S′,使得∪S′=E,且S′的任意真子集都不是E的覆蓋。S′也稱為E關于覆蓋S的一個極小覆蓋。

1.2 覆蓋信息系統及其屬性約簡問題

定義2[26]給定一個論域U={xi:1≤i≤n},設C={Xk:Xk?U,1≤k≤t}。如果C中的所有子集都不為空,且∪C=U,則稱C是U的一個覆蓋。

定義3[26]設U={xi:1≤i≤n},C={Xk:1≤k≤t}是U的一個覆蓋。?xi∈U,記(xi)C=∩{Xk:Xk∈C,xi∈Xk},記Cov(C)={(xi)C:xi∈U},則Cov(C)也是U的一個覆蓋,稱Cov(C)為C誘導的覆蓋。

定義4[26]設ζ={Cj:1≤j≤m}是論域U上的一族覆蓋。對于任意的x∈U,記Δζ(x)=∩{(x)Cj:1≤j≤m},稱Cov(ζ)={Δζ(x):x∈U}為ζ誘導的覆蓋,稱(U,ζ)為一個覆蓋信息系統。設β?ζ,若對于任意的x∈U,有Δβ(x)?Δζ(x),則記Cov(β)≤Cov(ζ)。

定義5給定一個論域U={xi:1≤i≤n},設ζ={Cj:1≤j≤m}是論域U上的一族覆蓋,定義U上的一個關系R={(xo,xp):xo∈Δζ(xp),xo∈U,xp∈U}。

定義6設ζ={Cj:1≤j≤m}是論域U上的一族覆蓋,(U,ζ)是一個覆蓋信息系統。對于任意的P?ζ,若Cov(P)≤Cov(ζ),則稱P是(U,ζ)的一個覆蓋協調集。若對于?Cj∈P,Cov(P-{Cj})≤Cov(ζ)均不成立,則稱P是(U,ζ)的一個覆蓋約簡集。

定義7設(U,ζ)是一個覆蓋信息系統,若P={Pz:1≤z≤e}是(U,ζ)的所有約簡集,則稱Core(ζ)={P1∩P2∩…∩Pn}是(U,ζ)的核屬性集。

2 覆蓋信息系統的集覆蓋模型

在本節中首先定義關于覆蓋信息系統(U,ζ)的相關矩陣M,然后通過矩陣M誘導出關于覆蓋信息系統(U,ζ)的集覆蓋模型(U′,S′),并給出覆蓋信息系統(U,ζ)與其誘導的集覆蓋模型(U′,S′)之間的一些聯系。

定義8設(U,ζ)是一個覆蓋信息系統,U={xi:1≤i≤n},ζ={Cj:1≤j≤m},R={(xo,xp):xo∈Δζ(xp),xo∈U,xp∈U}。令U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U},記U′={ui:1≤i≤n2-|R|}。定義一個f行m列的矩陣M,其中f=n2-|R|,M中的行由U′中元素構成,M中的列由ζ中元素構成,M的第i行第j列元素Mij取值為

稱M為覆蓋信息系統(U,ζ)的相關矩陣。

注: 因為U={xi:1≤i≤n}中有n個元素,U′中的元素為(xp,xo)的形式,所以U′中元素個數最多為n2個。由于U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U},故U′中元素個數等于f=n2-|R|。

定理1設(U,ζ)是一個覆蓋信息系統,M為(U,ζ)的相關矩陣,M中不存在所有列的值全為0的行。

證明設存在第i行所有列的值全為0,ui=(xp,xo)∈U′,則對于?Cj∈ζ,Mij=0,有xo∈(xp)Cj。根據Δζ(x)=∩{(x)Cj:1≤j≤m},可得xo∈Δζ(xp)。根據定義5,ui=(xp,xo)∈R,與定義8中U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U}矛盾。因此,矩陣M中不存在所有列的值全為0的行。

定理2設(U,ζ)是一個覆蓋信息系統,M為(U,ζ)的相關矩陣。令ui=(xp,xo)∈U′,若Mij=1,則Cj可以區分對象對ui=(xp,xo)∈U′。

證明令ui=(xp,xo)∈U′,若存在Mij=1,則存在Cj∈ζ使得xo?(xp)Cj,故xo?Δζ(xp)。因此,Cj可以區分對象對ui=(xp,xo)∈U′。

推論1設(U,ζ)是一個覆蓋信息系統,U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U}={ui:1≤i≤n2-|R|}。對于U′中的任意一個元素ui=(xp,xo),都存在一個覆蓋Cj使得xo?(xp)Cj。

證明由定理1與定理2容易得證。

接下來,給出一個由覆蓋信息系統誘導的區分集合的定義。

定義9設(U,ζ)是一個覆蓋信息系統,U′={ui:1≤i≤n2-|R|},令SCj=∪{ui:Mij=1,ui∈U′},則SCj為U′中所有能被Cj區分的ui構成的集合,稱SCj為Cj誘導的區分集合。

定理4設(U,ζ)是一個覆蓋信息系統,ζ={Cj:1≤j≤m},U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U},S′={SCj:1≤j≤m},(U′,S′)為(U,ζ)誘導的集覆蓋模型。S″?S′是集覆蓋模型(U′,S′)的一個集覆蓋,當且僅當P={Cj:SCj∈S″}是覆蓋信息系統(U,ζ)的一個覆蓋協調集。

證明1) 充分性。設S″?S′是集覆蓋模型(U′,S′)的一個集覆蓋,則∪S″=U′。令P={Cj:SCj∈S″},由定義6可知,要證明P是(U,ζ)的一個覆蓋協調集,需要證明Cov(P)≤Cov(ζ),即需要證明對于?xq∈U,有ΔP(xq)?Δζ(xq)。對于?(xq,xo)∈U′,由定義8可得xo?Δζ(xq)。又由于U′=∪S″,故(xq,xo)∈S″,從而?Cj∈P,使得xo?(xq)Cj,故xo?ΔP(xq),所以ΔP(xq)?Δζ(xq),則Cov(P)≤Cov(ζ)。因此,P是(U,ζ)的一個覆蓋協調集。

2) 必要性。設P?ζ是覆蓋信息系統(U,ζ)的一個覆蓋協調集,Cov(P)≤Cov(ζ),則?xq∈U,有ΔP(xq)?Δζ(xq)。令S″=∪{SCi:Ci∈P},對于?(xq,xo)∈U′,根據定義8可得xo?Δζ(xq),從而xo?ΔP(xq),(xq,xo)∈S″,故U′?S″。因S″=∪{SCi:Ci∈P}?U′,從而S″=U′,即S″是集覆蓋模型(U′,S″)的一個集覆蓋。

推論2設(U,ζ)是一個覆蓋信息系統,ζ={Cj:1≤j≤m},U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U},S′={SCj:1≤j≤m},(U′,S′)為(U,ζ)的集覆蓋模型。S″?S′是集覆蓋模型(U′,S′)的一個極小集覆蓋,當且僅當P={Cj:SCj∈S″}是覆蓋信息系統(U,ζ)的一個覆蓋約簡集。

證明由定理4容易得證。

3 基于集覆蓋模型的覆蓋信息系統約簡算法

由上述討論可知,求解覆蓋信息系統的屬性約簡問題可以轉化為求解集覆蓋模型的極小集覆蓋問題。本文選擇SCHA來求解覆蓋信息系統的屬性約簡,其在解決SCP上具有更高的精度與更好的性能。下面給出SCHA中用于解決SCP的4個完備策略。

完備策略1:設E={xq:1≤q≤y},S={Sw:1≤w≤r},若?Sw=E,則選擇Sw作為最優化覆蓋中唯一一個集合Sw。

完備策略2:設?x∈E,x只屬于Sw,Sw∈S,則選擇Sw作為最優化覆蓋中的一個集合元素。

完備策略3:若?S′w和Sw,S′w≠Sw,S′w?Sw,則S′w可以被排除。

完備策略4:設?xp,xq∈E,xp≠xq,用Sn(xp)來表示所有含xp的Sw的集合,若Sn(xp)?Sn(xq),則可以將xq從E中刪除。

接下來,給出基于SCHA的覆蓋信息系統屬性約簡問題的求解步驟。

輸入: 一個覆蓋信息系統(U,ζ),其中U={xi:1≤i≤n},ζ={Cj:1≤j≤m}。

輸出: 覆蓋信息系統(U,ζ)的一個約簡RED。

步驟1: 令RED=?。

步驟2: 根據定義8構造(U,ζ)的相關矩陣M,設矩陣M的行數和列數分別為α、β。

步驟3: 對于矩陣M的第j列(j=1,2,…,β),計算此列中所有行的元素和,若此列中所有行的元素和等于α,則RED=RED∪{Cj},轉到步驟8。

步驟4: 對于矩陣M的第i行(i=1,2,…,α),計算此行中所有列的元素和,若此行中所有列的元素和為1,則找出該行中元素值等于1的列,設該列為Sj,則RED=RED∪{Cj},將此列從矩陣中刪除,令β=β-1,更新矩陣。

步驟7: 找到矩陣M中所有行元素和最大的列,假定為第j列,令RED=RED∪{Cj},將i從1一直取到α,去除Mij=1所在的行,并且在遍歷結束后去除第j列,令α=α-α′,β=β-1,更新矩陣,并返回步驟3。

步驟8: 輸出RED。

在基于SCHA求解覆蓋信息系統(U,ζ)的屬性約簡前,首先需要獲得(U,ζ)的相關矩陣M,下面給出生成覆蓋信息系統(U,ζ)的相關矩陣M的求解算法。

算法1生成覆蓋信息系統相關矩陣的算法

輸入: 一個覆蓋信息系統(U,ζ),其中U={xi:1≤i≤n},ζ={Cj:1≤j≤m}。

輸出: 覆蓋信息系統(U,ζ)的相關矩陣M。

1:for (p=1;p<=n;p++){

2: for (o=1;o<=n;o++){

3:i=1,a=0;

4: for (j=1;j<=m;j++){

5: if(xo?(xp)Cj){

6:Mij=1;

7:a=a+1;

8: } else {

9:Mij=0;

10: }

11: }∥end for

12: if(a= =0) 刪除第i行;

13: elsei=i+1;

14: }∥end for

15:}∥end for

注:在算法1中,a代表可以區分(xp,xo)的Cj的個數。若a=0,則表示所有Cj均不能區分(xp,xo),故第12行相當于刪去R中元素。算法最終得到U′={(xp,xo):(xp,xo)?R,xp,xo∈U}。

根據上述基于SCHA的覆蓋信息系統屬性約簡問題的求解步驟,下面給出基于SCHA求解覆蓋信息系統一個屬性約簡的相關算法。

算法2基于SCHA的覆蓋信息系統屬性約簡算法

輸入: 一個覆蓋信息系統(U,ζ),其中U={xi:1≤i≤n},ζ={cj:1≤j≤m}。

輸出: 覆蓋信息系統(U,ζ)的一個屬性約簡。

1:求(U,ζ)的相關矩陣M;

2:RED=?;

3:α=矩陣M的行數;

4:β=矩陣M的列數;

5:HasGetRED=false;

6:while (HasGetRED= =false){

7: for (j=1;j<=RED∪SCj;j++){

8: if(當前Cj列所有行的元素和= =β) {

9:RED=RED∪SCj;

10:HasGetRED=true;

11: returnRED;∥算法結束

12: }∥end if

13: }∥end for

14: for (i=1;i<=α;i++){

15: if(第i行所有列的元素和==1){

16:Mark=元素值為1的元素對應的列號;

17:RED=RED∪SMark;

18:M=M刪除Mark列;

19:β=β-1;

20: }∥end if

21: }∥end for

22: for(j=1;j<=β;j++){

23: for (j′=j;j′ <=β;j′++){

24: if(第j列元素為1的元素所在的行構成的集合 ? 第j′列元素為1的元素所在的行構成的集合){

25:M=M刪除第j列;

26:S′ =S′-SCj′;

27:β=β-1;

28: }∥end if

29: }∥end for

30: }∥end for

31: for(i=1;i<=α;i++) {

32: for (i′=i;i′<=α;i′++){

33: if (第i行元素為1的元素所在的列構成的集合?第i′行元素為1的元素所在的列構成的集合){

34:M=M刪除第i′行;

35:α=α-1;

36: }∥end if

37: }∥end for

38: }∥end for

39:Mark=所有行元素和最大的列號;

40:RED=RED∪SMark;

41:α′=Mark列所有行的元素和;

42:Mark2←Mark列元素值為1的元素對應行號的集合;

43:M←M刪除Mark2中的行;

44:α=α-α′;

45:β=β-1;

46:S′=S′-SMark;

47:}∥end while

48:將RED中的SCj轉化成對應的Cj存入P中。

注:在算法2中,第2行對應基于SCHA的覆蓋信息系統屬性約簡問題的求解步驟1,第3行、第4行對應求解步驟2,第5～13行對應求解步驟3,第14～21行對應求解步驟4,第22～30行對應求解步驟5,第31～38行對應求解步驟6,第39～47行對應求解步驟7,第48行對應求解步驟8。

設m為(U,ζ)的相關矩陣M的行數,n為(U,ζ)的相關矩陣M的列數,則完備策略1的時間復雜度為O(mn),完備策略2的時間復雜度為O(mn),完備策略3的時間復雜度為O(m2n),完備策略4的時間復雜度為O(mn2)。

文獻[7]提出的覆蓋信息系統約簡方法是目前較新的方法之一,與文獻[7]不同,本文不需要構造區分矩陣,并且若給定的覆蓋信息系統具有符合完備策略1的屬性,則本文算法將不再進行后續完備策略2～4的計算,即算法的時間復雜度有可能最小為O(mn)。

4 實例

例1考慮房子評估問題。{價格,結構,顏色,環境}為4個待評估屬性集,價格屬性值域為{高,中,低},結構屬性值域為{合理,一般,差},顏色屬性值域為{好,差},環境屬性值域為{安靜,輕度吵鬧,吵鬧,非常吵鬧}。設有6套房子U1={x1,x2,x3,x4,x5,x6},表1是某公司若干位專家對這6套房子的評估信息表(注:每位專家的評估數據都十分重要,故會出現有的房子某個屬性取值為整個值域的情況。例如,房子x3、x4和x6的價格屬性值域均為{高,中,低})。為了方便公司對房子進行評估,需要篩選掉冗余屬性集(不影響最終分類結果的屬性),以減輕評估的工作量。

表1 房子評估信息表Table 1 House appraisal information sheet

用C1代表價格屬性,C1中各元素分別代表價格為高、中、低的房子集合,C1={{x1,x2,x3,x4,x6},{x3,x4,x6},{x3,x4,x5,x6}}。

用C2代表結構屬性,C2中各元素分別代表結構為合理、一般、差的房子集合,C2={{x1,x2,x3,x4,x5,x6},{x6}}。

用C3代表顏色屬性,C3中各元素分別代表顏色為好、差的房子集合,C3={{x1,x2,x3,x6},{x2,x3,x4,x5,x6}}。

用C4代表環境屬性,C4中各元素分別代表環境為安靜、輕度吵鬧、吵鬧、非常吵鬧的房子集合,C4={{x1,x2,x3,x6},{x2,x3,x4,x5,x6},{x6}}。

C1,C2,C3,C4構成U1的一個覆蓋族,令ζ1={C1,C2,C3,C4},則(U1,ζ1)是一個覆蓋信息系統?？傻忙う?(x1)={x1,x2,x3,x6},Δζ1(x2)={x2,x3,x6},Δζ1(x3)={x3,x6},Δζ1(x4)={x3,x4,x6},Δζ1(x5)={x3,x4,x5,x6},Δζ1(x6)={x6}。

通過算法1可以得出此覆蓋信息系統(U1,ζ1)的相關矩陣M1,如表2所示。

利用算法2對矩陣M1不斷進行簡化,可以得

表2 覆蓋信息系統(U1,ζ1)的相關矩陣M1Table 2 The correlation matrix M1 of covering information system(U1,ζ1)

到覆蓋信息系統(U1,ζ1)的覆蓋約簡集RED1,具體情況如下。

1) 通過遍歷矩陣M1,沒有發現符合基于SCHA的求解步驟3的列,則從求解步驟4開始分析。通過基于SCHA的求解步驟4發現,矩陣M1第11行所有列的元素和為1,其值為1的列為SC1,將第1列從矩陣M1中刪除,并將SC1并入RED1中,得到更新矩陣M2,如表3所示。

表3 經過求解步驟4后的更新矩陣M2Table 3 The update matrix M2 after solving step 4

2) 繼續進行基于SCHA的求解步驟5,通過求解步驟5發現,SC2與SC4符合求解步驟5簡化的條件,于是刪去SC2這列,得到更新矩陣M3,如表4所示。

3) 通過基于SCHA的求解步驟6,進一步得到更新矩陣M4,如表5所示。

表4 經過求解步驟5后的更新矩陣M3Table 4 The update matrix M3 after solving step 5

表5 經過求解步驟6后的更新矩陣M4Table 5 The update matrix M4 after solving step 6

4) 最后,通過基于SCHA的求解步驟7得到RED1={C1,C3,C4}。

根據定義4可得ΔRED1(x1)={x1,x2,x3,x6},ΔRED1(x2)={x2,x3,x6},ΔRED1(x3)={x3,x6},ΔRED1(x4)={x3,x4,x6},ΔRED1(x5)={x3,x4,x5,x6},ΔRED1(x6)={x6}。Cov(RED1)≤Cov(ζ1)成立,同時,Cov({C1,C3})≤Cov(ζ1),Cov({C1,C4})≤Cov(ζ1),Cov({C3,C4})≤Cov(ζ1)均不成立,可得RED1={C1,C3,C4}是覆蓋信息系統(U1,ζ1)的一個屬性約簡。{價格,顏色,環境}三個屬性是對評估結果具有影響力的屬性集,而{結構}屬性對評估結果沒有影響。因此,當公司在進行實際評估時可以不考慮{結構}屬性。

5 結語

本文研究了覆蓋信息系統屬性約簡問題與集覆蓋問題的相關性質,構造了覆蓋信息系統的相關矩陣,建立了覆蓋信息系統屬性約簡問題與集覆蓋問題之間的聯系,找到了將覆蓋信息系統屬性約簡問題轉化為集覆蓋問題的方法,從而可以借助豐富且高效的集覆蓋理論來研究覆蓋信息系統的屬性約簡問題。此外,對于有特殊性質的覆蓋信息系統屬性約簡問題,相應的集覆蓋解決方法是值得進一步研究的課題。