徐 曄, 許晴媛, 李進(jìn)金

(1.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院 福建 漳州 363000; 2.閩南師范大學(xué) 數(shù)據(jù)科學(xué)與智能應(yīng)用福建省 高校重點(diǎn)實(shí)驗(yàn)室 福建 漳州 363000; 3.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 福建 漳州 363000; 4.閩南師范大學(xué) 福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室 福建 漳州 363000)

0 引言

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

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

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

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

1 基本概念

1.1 集覆蓋問題

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

1.2 覆蓋信息系統(tǒng)及其屬性約簡(jiǎn)問題

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

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

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

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

定義6設(shè)ζ={Cj:1≤j≤m}是論域U上的一族覆蓋,(U,ζ)是一個(gè)覆蓋信息系統(tǒng)。對(duì)于任意的P?ζ,若Cov(P)≤Cov(ζ),則稱P是(U,ζ)的一個(gè)覆蓋協(xié)調(diào)集。若對(duì)于?Cj∈P,Cov(P-{Cj})≤Cov(ζ)均不成立,則稱P是(U,ζ)的一個(gè)覆蓋約簡(jiǎn)集。

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

2 覆蓋信息系統(tǒng)的集覆蓋模型

在本節(jié)中首先定義關(guān)于覆蓋信息系統(tǒng)(U,ζ)的相關(guān)矩陣M,然后通過矩陣M誘導(dǎo)出關(guān)于覆蓋信息系統(tǒng)(U,ζ)的集覆蓋模型(U′,S′),并給出覆蓋信息系統(tǒng)(U,ζ)與其誘導(dǎo)的集覆蓋模型(U′,S′)之間的一些聯(lián)系。

定義8設(shè)(U,ζ)是一個(gè)覆蓋信息系統(tǒng),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|}。定義一個(gè)f行m列的矩陣M,其中f=n2-|R|,M中的行由U′中元素構(gòu)成,M中的列由ζ中元素構(gòu)成,M的第i行第j列元素Mij取值為

稱M為覆蓋信息系統(tǒng)(U,ζ)的相關(guān)矩陣。

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

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

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

定理2設(shè)(U,ζ)是一個(gè)覆蓋信息系統(tǒng),M為(U,ζ)的相關(guān)矩陣。令ui=(xp,xo)∈U′,若Mij=1,則Cj可以區(qū)分對(duì)象對(duì)ui=(xp,xo)∈U′。

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

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

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

接下來,給出一個(gè)由覆蓋信息系統(tǒng)誘導(dǎo)的區(qū)分集合的定義。

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

定理4設(shè)(U,ζ)是一個(gè)覆蓋信息系統(tǒng),ζ={Cj:1≤j≤m},U′={(xp,xo):(xp,xo)?R,xp∈U,xo∈U},S′={SCj:1≤j≤m},(U′,S′)為(U,ζ)誘導(dǎo)的集覆蓋模型。S″?S′是集覆蓋模型(U′,S′)的一個(gè)集覆蓋,當(dāng)且僅當(dāng)P={Cj:SCj∈S″}是覆蓋信息系統(tǒng)(U,ζ)的一個(gè)覆蓋協(xié)調(diào)集。

證明1) 充分性。設(shè)S″?S′是集覆蓋模型(U′,S′)的一個(gè)集覆蓋,則∪S″=U′。令P={Cj:SCj∈S″},由定義6可知,要證明P是(U,ζ)的一個(gè)覆蓋協(xié)調(diào)集,需要證明Cov(P)≤Cov(ζ),即需要證明對(duì)于?xq∈U,有ΔP(xq)?Δζ(xq)。對(duì)于?(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,ζ)的一個(gè)覆蓋協(xié)調(diào)集。

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

推論2設(shè)(U,ζ)是一個(gè)覆蓋信息系統(tǒng),ζ={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′)的一個(gè)極小集覆蓋,當(dāng)且僅當(dāng)P={Cj:SCj∈S″}是覆蓋信息系統(tǒng)(U,ζ)的一個(gè)覆蓋約簡(jiǎn)集。

證明由定理4容易得證。

3 基于集覆蓋模型的覆蓋信息系統(tǒng)約簡(jiǎn)算法

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

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

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

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

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

接下來,給出基于SCHA的覆蓋信息系統(tǒng)屬性約簡(jiǎn)問題的求解步驟。

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

輸出: 覆蓋信息系統(tǒng)(U,ζ)的一個(gè)約簡(jiǎn)RED。

步驟1: 令RED=?。

步驟2: 根據(jù)定義8構(gòu)造(U,ζ)的相關(guān)矩陣M,設(shè)矩陣M的行數(shù)和列數(shù)分別為α、β。

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

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

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

步驟8: 輸出RED。

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

算法1生成覆蓋信息系統(tǒng)相關(guān)矩陣的算法

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

輸出: 覆蓋信息系統(tǒng)(U,ζ)的相關(guān)矩陣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代表可以區(qū)分(xp,xo)的Cj的個(gè)數(shù)。若a=0,則表示所有Cj均不能區(qū)分(xp,xo),故第12行相當(dāng)于刪去R中元素。算法最終得到U′={(xp,xo):(xp,xo)?R,xp,xo∈U}。

根據(jù)上述基于SCHA的覆蓋信息系統(tǒng)屬性約簡(jiǎn)問題的求解步驟,下面給出基于SCHA求解覆蓋信息系統(tǒng)一個(gè)屬性約簡(jiǎn)的相關(guān)算法。

算法2基于SCHA的覆蓋信息系統(tǒng)屬性約簡(jiǎn)算法

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

輸出: 覆蓋信息系統(tǒng)(U,ζ)的一個(gè)屬性約簡(jiǎn)。

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

2:RED=?;

3:α=矩陣M的行數(shù);

4:β=矩陣M的列數(shù);

5:HasGetRED=false;

6:while (HasGetRED= =false){

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

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

9:RED=RED∪SCj;

10:HasGetRED=true;

11: returnRED;∥算法結(jié)束

12: }∥end if

13: }∥end for

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

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

16:Mark=元素值為1的元素對(duì)應(yīng)的列號(hào);

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的元素所在的行構(gòu)成的集合 ? 第j′列元素為1的元素所在的行構(gòu)成的集合){

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的元素所在的列構(gòu)成的集合?第i′行元素為1的元素所在的列構(gòu)成的集合){

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

35:α=α-1;

36: }∥end if

37: }∥end for

38: }∥end for

39:Mark=所有行元素和最大的列號(hào);

40:RED=RED∪SMark;

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

42:Mark2←Mark列元素值為1的元素對(duì)應(yīng)行號(hào)的集合;

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

44:α=α-α′;

45:β=β-1;

46:S′=S′-SMark;

47:}∥end while

48:將RED中的SCj轉(zhuǎn)化成對(duì)應(yīng)的Cj存入P中。

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

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

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

4 實(shí)例

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

表1 房子評(píng)估信息表Table 1 House appraisal information sheet

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

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

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

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

C1,C2,C3,C4構(gòu)成U1的一個(gè)覆蓋族,令ζ1={C1,C2,C3,C4},則(U1,ζ1)是一個(gè)覆蓋信息系統(tǒng)?？傻忙う?(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可以得出此覆蓋信息系統(tǒng)(U1,ζ1)的相關(guān)矩陣M1,如表2所示。

利用算法2對(duì)矩陣M1不斷進(jìn)行簡(jiǎn)化,可以得

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

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

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

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

2) 繼續(xù)進(jìn)行基于SCHA的求解步驟5,通過求解步驟5發(fā)現(xiàn),SC2與SC4符合求解步驟5簡(jiǎn)化的條件,于是刪去SC2這列,得到更新矩陣M3,如表4所示。

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

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

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

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

根據(jù)定義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)成立,同時(shí),Cov({C1,C3})≤Cov(ζ1),Cov({C1,C4})≤Cov(ζ1),Cov({C3,C4})≤Cov(ζ1)均不成立,可得RED1={C1,C3,C4}是覆蓋信息系統(tǒng)(U1,ζ1)的一個(gè)屬性約簡(jiǎn)。{價(jià)格,顏色,環(huán)境}三個(gè)屬性是對(duì)評(píng)估結(jié)果具有影響力的屬性集,而{結(jié)構(gòu)}屬性對(duì)評(píng)估結(jié)果沒有影響。因此,當(dāng)公司在進(jìn)行實(shí)際評(píng)估時(shí)可以不考慮{結(jié)構(gòu)}屬性。

5 結(jié)語

本文研究了覆蓋信息系統(tǒng)屬性約簡(jiǎn)問題與集覆蓋問題的相關(guān)性質(zhì),構(gòu)造了覆蓋信息系統(tǒng)的相關(guān)矩陣,建立了覆蓋信息系統(tǒng)屬性約簡(jiǎn)問題與集覆蓋問題之間的聯(lián)系,找到了將覆蓋信息系統(tǒng)屬性約簡(jiǎn)問題轉(zhuǎn)化為集覆蓋問題的方法,從而可以借助豐富且高效的集覆蓋理論來研究覆蓋信息系統(tǒng)的屬性約簡(jiǎn)問題。此外,對(duì)于有特殊性質(zhì)的覆蓋信息系統(tǒng)屬性約簡(jiǎn)問題,相應(yīng)的集覆蓋解決方法是值得進(jìn)一步研究的課題。