一種新的決策表屬性值分類方法

汪小燕，程澤凱，申元霞

（安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032）

一種新的決策表屬性值分類方法

汪小燕，程澤凱，申元霞

（安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032）

在粗糙集值約簡算法中，常常需要對決策表的條件屬性值進(jìn)行分類?；赟kowron分辨矩陣，提出一種新的屬性值分類矩陣。通過該矩陣可以方便的獲取決策表中各條件屬性的沖突記錄集和重復(fù)記錄集，并能夠確保對這些沖突記錄集和重復(fù)記錄集的條件屬性值進(jìn)行處理后，決策表中剩下的條件屬性值被刪除后不會(huì)產(chǎn)生新的沖突記錄和重復(fù)記錄。理論分析與實(shí)例表明：該方法能有效處理決策表屬性值分類。

粗糙集；決策表；分辨矩陣；分類；值約簡

波蘭數(shù)學(xué)家Pawlak在1982年提出的粗糙集理論是一種處理不確定、不精確和不完全數(shù)據(jù)的一種新的數(shù)學(xué)工具，主要用于知識的簡化及知識依賴性的分析[1]。在粗糙集理論中，為了從決策表中獲取有價(jià)值的知識，通常采取屬性約簡和值約簡的方法，值約簡是粗糙集理論中非常重要的研究課題，目前有很多學(xué)者提出了多種值約簡算法[2-10]。在值約簡算法中，一般首先對決策表的屬性值進(jìn)行分類，根據(jù)屬性值分類后的決策表，對屬性值約簡，最后得出分類規(guī)則。傳統(tǒng)的屬性值分類方法是對決策表中的每條記錄逐列考察各個(gè)條件屬性。通過刪除某一個(gè)條件屬性的值來判斷是否會(huì)產(chǎn)生沖突記錄或重復(fù)記錄，或沖突記錄與重復(fù)記錄都不會(huì)產(chǎn)生，根據(jù)刪除條件屬性后產(chǎn)生記錄的結(jié)果將決策表中的屬性值分為三類。為了能夠加快決策表的屬性值分類，從整體上對各個(gè)條件屬性的值分類，在Skowron分辨矩陣的基礎(chǔ)上，提出一種屬性值分類矩陣，根據(jù)該分類矩陣確定條件屬性的沖突記錄集和重復(fù)記錄集，對沖突記錄集和重復(fù)記錄集中的對象在對應(yīng)的條件屬性值上做相應(yīng)處理后，決策表中剩下的屬性值就是第三類屬性值，避免了對第三類屬性值的判斷。

1　相關(guān)概念

下面給出文中所涉及到的一些相關(guān)概念。

定義1[2]一個(gè)信息系統(tǒng)（也稱信息表）表示為S=。這里，U是對象的集合，也稱為論域，R是屬性集合，表示屬性r的值域，f：U×R→V是一個(gè)信息函數(shù)，它指定U中的每一個(gè)對象x的屬性值，即對x∈U，r∈R，有f（x，r）∈Vr。如果屬性集R可以分為條件屬性集C和決策屬性集D，即R=C∪D，C∩D=?，D≠?，則該信息系統(tǒng)稱為決策系統(tǒng)或決策表。

定義2屬性集A的不可分辨關(guān)系IND（A）為：IND（A）＝{（x，y）∈U×U|?a∈A，f（x，a）=f（y，a）}，U/IND（A）表示不可分辨關(guān)系IND（A）在U上導(dǎo)出的劃分，也可表示為U/A。

定義3分辨矩陣由Skowron提出[2]，其定義為：令S=是一個(gè)信息系統(tǒng)，U為論域且，R=C∪D是屬性集合，子集C和D分別是條件屬性集和決策屬性集，r（x）是對象x在屬性r上的值，D（x）是記錄x在D上的值，則分辨矩陣記為

顯然，分辨矩陣是一個(gè)按主對角線對稱的矩陣，在建立分辨矩陣的時(shí)候，只需要考慮其上三角（或下三角）部分就可以了。

2　決策表屬性值分類方法

文獻(xiàn)[3-5]提出不同的值約簡算法，對決策表的屬性值分類都是采用對決策表中的每條記錄逐個(gè)刪除各個(gè)條件屬性值的方法。如果刪除某條記錄的一個(gè)條件屬性，產(chǎn)生了沖突記錄，則該屬性是核值屬性，需要保留該記錄的原屬性值；如果沒有產(chǎn)生沖突記錄但是有重復(fù)記錄，則在該記錄的此屬性值上標(biāo)記為“*”；如果既不產(chǎn)生沖突記錄也不產(chǎn)生重復(fù)記錄，則在該記錄的此屬性值上標(biāo)記為“？”。這種屬性值分類方法易于理解，但對每條記錄的任意一個(gè)條件屬性刪除時(shí)，都要在整個(gè)決策表中觀察是否產(chǎn)生沖突記錄或重復(fù)記錄，還是沖突記錄和重復(fù)記錄都不產(chǎn)生。為了改進(jìn)原有的屬性值分類方法，可以在決策表屬性值分類時(shí)，將保留原值的核值屬性所對應(yīng)的記錄集和標(biāo)記為“*”的屬性值對應(yīng)記錄集先提取出來，那么剩下的就是第三類屬性值。

在新的決策表屬性值分類方法中，需要用到屬性值分類的矩陣，該矩陣是在Skowron分辨矩陣的基礎(chǔ)上，增加相同決策類對象的比較，并且對決策屬性也進(jìn)行比較，如果兩個(gè)對象的決策屬性不同，則將決策屬性也寫入到屬性值組合中。所提出的用于屬性值分類的矩陣，定義如下。

定義4S=是一個(gè)信息系統(tǒng)，U為論域且，，R=C∪D是屬性集合，子集C和 D分別是條件屬性集和決策屬性集，r（x）是對象x在屬性r上的值，則用于屬性值分類的矩陣記為

為了加快屬性值分類，現(xiàn)提出如下屬性值分類算法：

輸入：決策信息系統(tǒng)S=，U為論域，R=C∪D是屬性集合，子集C和D分別是條件屬性集和決策屬性集

輸出：屬性值分類表

命題1在屬性值分類矩陣中，若屬性組合Mij中包含決策屬性且Mij=2（|·|表示Mij中包含的屬性個(gè)數(shù)），c是一條件屬性且c∈Mij，則Mij所對應(yīng)的行列對象在屬性c上要保留原值。

證明若屬性組合Mij中包含決策屬性且，設(shè)條件屬性c∈Mij，由定義4知Mij所對應(yīng)的行列對象決策屬性不同，且只有一個(gè)條件屬性不同，如果刪除Mij所對應(yīng)的行列對象的c屬性值，則這兩個(gè)對象一定成為沖突記錄，c為核值屬性，所以Mij所對應(yīng)的行列對象在c屬性上要保留原值。

定義5在屬性值分類矩陣中，若屬性組合Mij中包含決策屬性且，c是一條件屬性且c∈Mij，則所有只包含c屬性和決策屬性的Mij對應(yīng)的行列對象的并集，稱為c沖突記錄集，記為Tc。

命題3令S=是一個(gè)信息系統(tǒng)，U為論域且，c為一條件屬性，若c存在沖突記錄集Tc和重復(fù)記錄集Fc，則U-Tc-Fc中的所有對象刪除c屬性后都不會(huì)產(chǎn)生沖突記錄和重復(fù)記錄。

定義7令S=是一個(gè)信息系統(tǒng)，U為論域且，R=C∪D是屬性集合，子集C和D分別是條件屬性集和決策屬性集，c為一條件屬性，若c存在沖突記錄集Tc和重復(fù)記錄集Fc，則稱UTc-Fc為c無沖突重復(fù)記錄集。

由定義7知，若c只存在沖突記錄集Tc，不存在重復(fù)記錄集Fc，則U-Tc為c無沖突重復(fù)記錄集；若c不存在沖突記錄集Tc，只存在重復(fù)記錄集Fc，則U-Fc為c無沖突重復(fù)記錄集。若c不存在沖突記錄集Tc和重復(fù)記錄集Fc，則U為c無沖突重復(fù)記錄集。

決策表屬性值分類的新方法步驟描述：（1）對決策表進(jìn)行屬性約簡，去掉決策表中重復(fù)記錄；（2）根據(jù)約簡后的決策表，按照屬性值分類矩陣的生成算法生成屬性值分類矩陣；（3）掃描屬性值分類矩陣，對任意條件屬性c，看是否存在沖突記錄集Tc和重復(fù)記錄集Fc，如果存在，分別記錄沖突記錄集Tc和重復(fù)記錄集Fc；（4）根據(jù)第（3）步的結(jié)果，對任意條件屬性c，若存在沖突記錄集Tc，則在約簡后的決策表中，保留沖突記錄集中c屬性的原值；（5）根據(jù)第（3）步的結(jié)果，對任意條件屬性c，若存在重復(fù)記錄集Fc，則在約簡后的決策表中，將重復(fù)記錄集中屬性所對應(yīng)的值標(biāo)記為“*”；（6）決策表中剩余的條件屬性值，也就是去除該屬性后，既不會(huì)產(chǎn)生沖突記錄也不會(huì)產(chǎn)生重復(fù)記錄的屬性值，將這些屬性值標(biāo)記為“?”。最后得出屬性值分類的決策表。

新的決策表屬性值分類方法在建立了屬性值分類矩陣后，對前兩類屬性值很容易判斷，并且避免了對第三類屬性值的判斷。

3　實(shí)例

例如某一約簡后的決策表見表1：其中條件屬性集C={a，b，d}，決策屬性集D={e}。為表1建立屬性值分類矩陣如表2所示。由表2知：Ta={2，3}，Tb={1，4}，Td={4，5}，F(xiàn)a={5，6}，F(xiàn)b={6，7}，F(xiàn)d={1，2}。根據(jù)表2獲得的沖突記錄集，將對象2，3在屬性a上保留原值，將對象1，4在屬性b上保留原值，將對象4，5在屬性d上保留原值，根據(jù)表2獲得的重復(fù)記錄集，將對象5，6在屬性a上標(biāo)記為*，將對象6，7在屬性b上標(biāo)記為*，將對象1，2在屬性d上標(biāo)記為*，表1中剩下的條件屬性值標(biāo)記為？。屬性值分類后的決策表如表3所示。

表1　屬性約簡后的決策表

表2　表1的屬性值分類矩陣

表3　屬性值分類表

4　結(jié)語

文中基于Skowron分辨矩陣，提出屬性值分類矩陣，利用該分類矩陣給出決策表中屬性值快速分類的方法，并通過實(shí)例給出了該方法具體實(shí)現(xiàn)，將該方法加入到值約簡算法中，可以提高值約簡的速度。

[1]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[2]王國胤.Rough集理論與知識獲取[M].西安：西安交通大學(xué)出版社，2003.

[3]常犁云，王國胤，吳渝.一種基于Rough Set理論的屬性約簡及規(guī)則提取方法[J].軟件學(xué)報(bào)，1999，10（11）：1206-1211.

[4]林嘉宜，彭宏，鄭啟倫.一種新的基于粗糙集的值約簡算法[J].計(jì)算機(jī)工程，2003，29（4）：70-71.

[5]楊振峰，郭景峰，常峰.一種基于粗集的值約簡方法[J].計(jì)算機(jī)工程，2003，29（9）：96-97.

[6]鄧少波，黎敏，關(guān)素潔，等.一種非相容決策表的屬性值與屬性約簡方法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（4）：1308-1310.

[7]鄂旭，邵良杉，張毅智，等.一種基于粗糙集理論的規(guī)則提取方法[J].計(jì)算機(jī)科學(xué)，2011，38（1）：232-235.

[8]杜躍，王治和，景永霞.基于關(guān)聯(lián)規(guī)則挖掘的粗糙集屬性值約簡算法研究[J].蘇州科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2008，25（1）：16-19.

[9]羅秋瑾，成蓉華，納靜.基于不可辨識矩陣的值約簡算法[J].云南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，20（6）：508-510.

[10]蘭聰花，王逢娟.一種新的基于區(qū)分矩陣的值約簡算法[J].工業(yè)儀表與自動(dòng)化裝置，2014（2）：113-116.

A new classification method for attribute values in a decision table

WANG Xiaoyan，CHENG Zekai，SHEN Yuanxia
（School of Computer Science&Technology，Anhui University of Technology，Ma’anshan 243032，China）

In rough set attribute value reduction,it is necessary to classify condition attribute values in a decision table.A new classification matrix for attribute values is put forward based on Skowron discernible matrix.By using this matrix,we can easily obtain the conflict record set and duplicate record set of each condition attribute in a decision table,and no more other conflict records or duplicate records can be produced after handling the corresponding condition attribute values of these conflict record sets and duplicate record sets and deleting the rest of condition attribute values in a decision table.The theoretical analysis and example show that this method can effectively deal with attribute value classification in a decision table.

rough set；decision table；discernible matrix；classification；value reduction

TP301

A

1672－0687（2016）01－0061－04

責(zé)任編輯：艾淑艷

2014－05－28

國家青年科學(xué)基金資助項(xiàng)目（61300059）；安徽省高校自然科學(xué)基金資助項(xiàng)目（KJ2012Z024；KJ2012Z031）

汪小燕（1974-），女，安徽桐城人，副教授，碩士，研究方向：數(shù)據(jù)挖掘，粗糙集理論，概念格。