汪小燕，程澤凱，申元霞

（安徽工業(yè)大學計算機科學與技術學院，安徽馬鞍山243032）

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

汪小燕，程澤凱，申元霞

（安徽工業(yè)大學計算機科學與技術學院，安徽馬鞍山243032）

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

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

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

1　相關概念

下面給出文中所涉及到的一些相關概念。

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

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

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

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

2　決策表屬性值分類方法

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

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

定義4S=是一個信息系統(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中包含的屬性個數(shù)），c是一條件屬性且c∈Mij，則Mij所對應的行列對象在屬性c上要保留原值。

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

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

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

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

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

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

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

3　實例

例如某一約簡后的決策表見表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獲得的重復記錄集，將對象5，6在屬性a上標記為*，將對象6，7在屬性b上標記為*，將對象1，2在屬性d上標記為*，表1中剩下的條件屬性值標記為？。屬性值分類后的決策表如表3所示。

表1　屬性約簡后的決策表

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

表3　屬性值分類表

4　結語

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

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

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

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

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

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

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

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

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

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

[10]蘭聰花，王逢娟.一種新的基于區(qū)分矩陣的值約簡算法[J].工業(yè)儀表與自動化裝置，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

責任編輯：艾淑艷

2014－05－28

國家青年科學基金資助項目（61300059）；安徽省高校自然科學基金資助項目（KJ2012Z024；KJ2012Z031）

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