廖啟明，龍鵬飛

長沙理工大學(xué) 計算機與通信工程學(xué)院，長沙 410114

基于屬性重要性的粗糙集屬性約簡方法

廖啟明，龍鵬飛

長沙理工大學(xué) 計算機與通信工程學(xué)院，長沙 410114

粗糙集理論[1]是由波蘭數(shù)學(xué)家Z.Pawlak在1982年提出的，該理論是一種刻畫不完整性和不確定性的數(shù)學(xué)工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律。其主要思想是在保持分類能力不變的前提下，通過知識約簡，導(dǎo)出問題的決策或分類規(guī)則。

屬性約簡是粗糙集知識發(fā)現(xiàn)的核心內(nèi)容之一，它描述了信息系統(tǒng)屬性集中的每個屬性是否都是必要的以及如何刪除不必要的知識，從而減少數(shù)據(jù)挖掘要處理的信息量，提高數(shù)據(jù)挖掘的效率。目前，求解約簡的算法主要有兩種：一種是基于差別矩陣的算法[2]；另一種是基于屬性重要性的算法。文獻[3]采用分辨矩陣和邏輯運算相結(jié)合的方法求解屬性約簡集和核，需要浪費大量的存儲空間。文獻[4]中算法是從屬性集中逐漸刪除重要度較小的屬性而得到約簡，但只能依次從最小重要度的屬性刪除，判斷，再刪除，再判斷，計算復(fù)雜度高。文獻[5]設(shè)計了基于屬性重要性的逐步約簡算法，利用在決策系統(tǒng)中已獲得的正區(qū)域逐步縮小數(shù)據(jù)處理范圍。本文的主要思想是：通過計算單個屬性的重要性，取重要性大于零的屬性作為核，然后以核為基礎(chǔ)計算條件屬性集中除核以外其他屬性的重要性，取重要性最大的屬性加入到核集中形成新的集合RED，再以RED為基礎(chǔ)依次循環(huán)下去直至剩下所有屬性的重要性都為零，得出的集合REDn即為屬性約簡。

1 基本概念

定義1一個信息系統(tǒng)S，表示為S=(U，Α，V，f)，其中U={X1，X2，…，Xn}是論域；Α是屬性集合；V=∪νa，?a∈Α，νa表示屬性的值域；f=U×Α→V是一個信息函數(shù)，它對一個對象的每一個屬性賦予一個信息值，即x∈U，a∈Α有f(x，a)∈νa。

定義2在信息系統(tǒng)S中，對于每個屬性子集B?Α可以定義一個不可分辨的關(guān)系IND(B)：IND(B)={(x，y)∈U×U:?b∈B，b(x)=b(y)}稱為由B構(gòu)造的不可分辨關(guān)系。

關(guān)系IND(B)構(gòu)成U的一個劃分，用U/IND(B)表示，簡記為U/B。

定義3在信息系統(tǒng)S中，對于屬性集X?U，R為等價關(guān)系，定義2個子集：

分別稱它們?yōu)閄的R下近似和R上近似。

定義5P和Q為U上的等價關(guān)系，當(dāng)POSp(Q)=POSp-r(Q)，稱r∈P為P中Q可省略的，反之，r為P中Q不可省略的。

定義6當(dāng)P中任意r都為Q不可省略時，稱P為Q獨立的，當(dāng)S為P上的Q獨立子簇，并且滿足POSs(Q)=POSp(Q)，稱S為P的Q簡化。

定義7P中所有Q不可省略原始關(guān)系簇記為redQ(P)稱為P的Q核，記做Coreα(P)：Coreα(P)=∩redQ(P)。

2 屬性重要性分析及計算

信息系統(tǒng)I=(U，Α)，X是Α中的屬性子集，屬性x∈Α，當(dāng)x加入到集合X使得其分辨程度越大，就說明屬性x對集合X的重要性越大[6]。

定義8設(shè)S=(U，Α，V，f)為信息系統(tǒng)，X?Α，?x∈(Α-X)的重要性定義為：

|X|-|X∪{x}|代表不可分辨率，分辨率的增加是因為把屬性x加入到集合X中。也就是一些在X中難以識別的到了X∪{x}中就變得容易分辨了，而且可以表示為：(|X|-|X∪{x}|)/X=1-|X∪{x}|/X。

定理1[7]設(shè)S=(U，Α，V，f)為信息系統(tǒng)，P?Α，若|U/P|= |U/Α|，且?x∈P有SigP-x(x)＞0，則P為Α的一個約簡。

令X?Α，如果X-CORE(X)≠?，CORE(X)=RED(X)的充分必要條件是SigCORE(X)(x)=0，x∈X-CORE(X)。

3 屬性約簡算法

3.1 算法分析

第一步，求核。通過求條件屬性集C中每一個屬性x對整個條件屬性集C的重要性SigC(x)來確定屬性核CORE(X)，重要性SigC(x)>0的屬性為核屬性。

第二步，通過向?qū)傩院薈ORE(X)中依次加入重要性大的屬性來確定屬性集X的最小約簡，其詳細步驟如下：

（1）把a加入到屬性集R中，計算其重要性，選擇重要性最大的屬性；

（2）如果兩個屬性有相同的重要性，取離散值小的屬性。

3.2 算法詳細設(shè)計

根據(jù)以上結(jié)論，屬性約簡算法描述如下：

設(shè)屬性集X?Α，屬性x∈X。

輸入：信息系統(tǒng)S=(U，Α，V，f)。

輸出：屬性約簡RED(X)。

步驟1計算屬性核CORE(X)，?x∈X，計算SigX-{x}(x)，其值大于0的屬性為核屬性，CORE(X)可能為空；

步驟2RED(X)=CORE(X)；

步驟3當(dāng)IND(RED(X))=IND(X)，轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟4；

步驟4 ?x∈X-RED(X)，計算SigRED(X)(x)，取x1使其滿足：

如果有兩個值相同，取屬性特征少的屬性；

步驟5RED(X)=RED(X)∪{x1}，轉(zhuǎn)到步驟3；

步驟6輸出最小約簡RED(X)。

3.3 算法復(fù)雜度分析

通過計算，對決策表進行劃分的時間復(fù)雜度為O(n2)，計算條件屬性的重要性花費的時間滿足劃分基礎(chǔ)上的線性關(guān)系，所以求屬性核的時間復(fù)雜度為O(n2)。接著，由于在屬性約簡的過程中依次添加非核屬性也沒有額外的時間開銷，因此整個算法的時間復(fù)雜度為O(n2)。

4 實例及分析

決策表如表1所示，條件屬性集C={Τype，F(xiàn)abric，Style，Color}，決策屬性集為D。用a，b，c，d分別代表條件屬性Τype，F(xiàn)abric，Style，Color。

表1 關(guān)于女性服裝銷售情況調(diào)查表

條件屬性集C對決策表1的劃分：

根據(jù)公式可計算：

由上可以得出CORE(C)={b，d}。

令R=CORE(C)，R對U的劃分：

以上計算得出的重要性結(jié)果都為零，所以，信息系統(tǒng)的約簡RED(C)=CORE(C)={b，d}。

5 結(jié)束語

本文通過計算屬性的重要度來確定核屬性，較之通過分辨矩陣來求核屬性，節(jié)省了大量的儲存空間。而在約簡過程中采用迭代方法，利用減小選擇屬性集的大小來提高屬性約簡的效率，通過實驗證明方法計算簡單，能夠保證得出最小約簡。后面的工作是如何進一步降低算法的復(fù)雜度。

[1]Pawlak Z.Rough sets[J].International Journal of Computer& Information Sciences，1982，11：341-356.

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

[3]饒泓，夏葉娟，李娒竹.基于分辨矩陣和屬性重要度的規(guī)則提取算法[J].計算機工程與應(yīng)用，2008，44（23）：163-165.

[4]李永華，蔣蕓，王小菊.一種基于Rough集的屬性約簡的改進算法[J].計算機應(yīng)用，2008（8）.

[5]杜金蓮，遲忠先，翟巍.基于屬性重要性的逐步約簡算法[J].小型微型計算機系統(tǒng)，2003（6）.

[6]Leung Y，Wu Weizhi，Zhang Wenxiu.Knowledge acquisition in incomplete information systems：a rough set approach[J].European Journal of Operational Research，2006，168（2）：164-180.

[7]丁軍，高學(xué)東.一種信息系統(tǒng)的快速屬性約簡算法[J].計算機工程與應(yīng)用，2007，43（14）：173-176.

LIAO Qiming,LONG Pengfei

School of Computer&Communication Engineering,Changsha University of Science and Τechnology,Changsha 410114,China

Attribute reduction in information system is an important step during knowledge acquisition using Rough set.Τhis paper focuses on the research of feature selection,deleting superfluous attributes in an information system.Τhe new algorithm begins with the attribute significance,adopting iterative feature selection standard,making the selected feature attribute set get smaller,thus it acquires the reduction of information system.Τhe experiment demonstrates that this method is feasible and effective.

information system;attribute significance;attribute reduction;core attribute

信息系統(tǒng)中的屬性約簡是粗糙集知識發(fā)現(xiàn)的一個重要步驟。致力于研究一個信息系統(tǒng)中的特征選擇、刪除冗余屬性。新的算法從屬性重要性出發(fā)，采用迭代特征選擇的標(biāo)準(zhǔn)，使得選擇特征屬性集不斷縮小，獲得信息系統(tǒng)的約簡。通過實驗證明該方法可行，有效。

信息系統(tǒng)；屬性重要性；屬性約簡；核屬性

A

ΤP311

10.3778/j.issn.1002-8331.1111-0320

LIAO Qiming,LONG Pengfei.Rough set reduction method of attribute based on importance of attribute.Computer Engineering and Applications,2013,49（15）：130-132.

國家自然科學(xué)基金（No.10926189，No.10871031）；湖南省自然科學(xué)衡陽聯(lián)合基金（No.10JJ8008）；湖南省教育廳重點項目（No.10A015）。

廖啟明（1987—），男，碩士，研究方向為數(shù)據(jù)挖掘，人工智能；龍鵬飛（1960—），男，教授，研究方向為面向?qū)ο蠹夹g(shù)，軟件開發(fā)技術(shù)，XML技術(shù)等。E-mail：liaoqiming1987@163.com

2011-11-17

2011-12-21

1002-8331（2013）15-0130-03

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120425.1720.044.html