基于鏈表結構的啟發式屬性約簡算法

梁 寶 華

(巢湖學院計算機與信息工程學院　安徽 合肥 238000)

?

基于鏈表結構的啟發式屬性約簡算法

梁 寶 華

(巢湖學院計算機與信息工程學院安徽 合肥 238000)

屬性約簡是粗糙集理論研究的主要內容之一，正區域計算是多數屬性約簡算法的關鍵。為了減少正區域的計算時間，提出基于鏈表存儲的正區域計算方法。將屬性值相同的數據存儲在鏈表同一結點對象中，收集過程中不斷刪除基數為1的子劃分，通過降低樣本數據的規模來減少計算耗時，加速屬性約簡。同時，給出不可區分對象對數定義，并以此度量屬性重要性，設計一種高效的啟發式屬性約簡方法。通過實例和實驗與經典約簡算法進行性能測試比較，結果證實該算法在時間和空間效果上切實有效、可行。

粗糙集屬性約簡鏈表正區域不可區分對象對數

0　引　言

RoughSet作為一種處理不確定、不精確數據的有力數學工具[1]，已廣泛應用于機器學習、模式識別和數據挖掘等領域。屬性約簡是RoughSet研究的核心問題之一，也是知識獲取的關鍵步驟。在保持區分能力不變的情況下，用較少屬性表示數據集的特征?，F有的屬性約簡算法有基于正區域屬性約簡算法[2]、基于信息熵的約簡算法[3]、基于差別矩陣的屬性約簡算法[4,5]及其他啟發式屬性約簡算法[6,7,12]。

多數屬性約簡算法先對挖掘的決策表進行簡化，因為此過程效率高低影響整個算法的時間和空間性能。目前，求簡化決策表效率較高的算法有文獻[2]基于基數排序的屬性約簡算法，時間復雜度為O(|C‖U|)、基于文獻[8]快速排序思想的屬性約簡算法，時間復雜度為O(|C‖U‖log(U)|)。為了更進一步縮短求解簡化決策表時間，本文提出基于鏈表結構的快速求正區域方法，比文獻[2]的算法效率略有提高。在求解屬性約簡過程中，本文采用不可區分對象對數的函數，作為衡量屬性重要性的依據，既達到差別矩陣算法的直觀性、易理解性的優點，又避免了差別矩陣需大量空間存儲信息矩陣的缺點，提高了時間和空間處理效率。

1　相關概念

定義1一個信息系統IS=(U,A,V,f)，其中U為所有挖掘對象的集合；A是所有屬性的集合，A=C∪D，C為條件屬性集，D為決策屬性集，V為全體屬性的值域集，f為U×A→V的信息函數，定義f(x,a)為x在屬性a上的對應值。若P?A，則不可分辨關系為：

IND(P)={(x,y)∈U×U|?a∈P,f(x,a)=f(y,a)}，構成U的一個劃分用U/IND(P)。

定義2給定決策表T=(U,A,V,f)，對于任意子集X?U和不可分辨關系IND(P)：

下近似：

(1)

上近似：

(2)

定義3決策表T=(U,A,V,f)中，P?C，D的P正區域記為：

(3)

定義4決策表T=(U,A,V,f)中，P?C，D的P負區域記為：

NEGP(D)=U′-POSP(D)

(4)

其中U′為簡化后的無重復數據。

定義5[4]在簡化決策表T′=(U′,C,D,V,f)中，決策表的分明矩陣(簡稱簡化分明矩陣)M′=mi,j，其元素定義如下：

(5)

性質1設P?C,|U/Pi|=1，則U/Pi中的元素均屬于正區域POSP(D)。

證明：由IND(P)定義可知，若x1∈U,x2∈U∧f(x1,P)=f(x2,P)，則x1、x2屬于同類劃分，若f(x1,D)=f(x2,D)，則由POSP(D)定義可知，x1、x2屬于正區域元素，否則，屬于負區域元素。因為|U/Pi|=1，所以，U/P的第i個劃分中只有一個元素，設此元素為x。假設x屬于負區域，則可找到另一元素y，使得f(x,P)=f(y,P)且f(x,D)≠f(y,D)，但x∈U/Pi∧|U/Pi|=1，說明f(x,P)是唯一的，所以上述假設不成立，故x必屬于正區域元素。證畢。

2　快速計算正、負區域算法及其分析

2.1快速求正、負區域算法(算法1)

屬性約簡過程，大體進行三步：(1) 數據預處理，將數據離散化；(2) 將決策表簡化(可得到相應的正、負區域)；(3) 屬性約簡。由此可知，簡化決策表是屬性約簡過程的關鍵環節。若能得到有效的簡化決策表，可減少約簡的搜索空間。為了快速、有效得到簡化決策表，很多學者做了相關研究，效果較好的有文獻[2,6]。其中，文獻[2]的基數排序算法每次對數據收集時未能將已區分對象進行剪枝，后期約簡未能充分利用前期結果，浪費大量時間。

對數據存儲的常見形式有數組和鏈表，數組便于查找，找一個元素的時間復雜度為O(1)，但數組不便于插入與刪除。對于有n個元素的數組來說，要刪除數組中第i個元素，為了節省空間，要騰出第i個位置的空間，由于數組間元素是連續存儲的，所以需將第i+1個后面的所有元素均依次向前移動一個位置，然后刪除第n個元素所在的空間，平均時間復雜度為O(n/2)。若采用鏈表方式存儲，刪除一個元素需O(1)時間即可。

在求正、負區域及簡化決策表時，對于U/P(P?C)的劃分中基數為1的子劃分對象為可區分對象，無需參與下一步的劃分過程，應將此對象加入正區域集，并在U中刪除此對象。為了方便刪除操作，可利用鏈表的結構特征，這樣可有效加速求簡化決策表的進度和減少搜索空間。算法1具體描述如下：

算法中涉及到的鏈表結點數據結構為：

structList{

data;

//數據在條件屬性Ci上的取值

set;

//在Ci上取值data的數據集合

count;

//為集合set的數據個數

next;

//下一指針

}

輸入：U,C,D

輸出：簡化決策表U′,POS,NEG

Step1初始化條件U′=U；POS=?，NEG=?；

Step2將決策表按條件屬性C1進行劃分，將樣本在C1上取值相同的結點存儲同一子劃分中，并用鏈表List連接所有子劃分。

Step3for(i= 2 toi< |C|){

Step3.1將List中的每個結點元素，按條件屬性Ci劃分，同類的樣本編號放在同一結點的set中，若產生了新的加細劃分，則相應產生新結點。

Step3.2連接鏈表，但要對子劃分基數為1的劃分加入POS中，且在List中刪除此結點，實現剪枝。

Step4掃描鏈表List的每個結點，若某結點的set中數據有D值不同的，則選擇set中第一個數據加入NEG，否則加入POS。

Step5POS并NEG得到簡化決策表U′。

2.2算法1時間和空間復雜度分析

算法1的step1的時間復雜度為O(1)；Step2的時間復雜度為O(|U|)；Step3的時間復雜度為max(O((|C|-1)×(|U′|+|Ci|)))，其中Step3.1的時間復雜度O(|U′|)，由于U′在劃分過程中，不斷剪枝，所以|U′|≤|U|；Step3.2的時間復雜度為|Ci|；Step4的為O(|U′|)，因為最后List中鏈表的結點個數與簡化決策表中的元素個數相同，掃描List每個結點所需時間為O(|U′|)；Step5的為O(1)，僅僅是將POS與NEG合并。

綜上所得，時間復雜度為：

O(|U|)+ O(|U′|)+max(O((|C|-1)×(|U′|+|Ci|)))

由于|U′|≤|U|，且|U′|越來越小，故時間復雜度為O(|C‖U|)。

算法所需的空間，鏈表中共有的結點數實現就是樣本按條件屬性C劃分得到的子劃分個數，即O(|U/C|)，而每個結點4個成員，其中data、count和next共需空間O(4×|U/C|)，最終簡化決策表空間O(|U/C‖C|)，所以空間復雜度為max(O(4×|U/C|),O(|U/C‖C|))。

3　啟發式屬性約簡算法

3.1屬性重要性度量

在進行數據約簡時，通常先計算屬性重要性，并以此為啟發式信息選擇最易區分的屬性加入約簡集。差別矩陣算法以對象間可區分的屬性出現的頻率作為依據，選擇屬性，此類算法直觀、易理解，但需浪費大量的空間。為此，許多學者關注于改進差別矩陣[9-11]，試圖減少差別矩陣元素。根據定義5可知，改進差別矩陣表中，正區域中所有按D劃分屬于不同子劃分的數據進行比較，所有負區域中的每個數據與正區域的每個數據進行比較，但負區域中的所有數據相互間無需比較。與經典的差別矩陣相比，元素個數大大減少，但數據量還是比較龐大。經研究發現，可借助差別矩陣的直觀性等優點，但無需建立差別矩陣方法。

(6)

(7)

性質2根據定義5的改進差別矩陣，對于某具體的簡化決策表，其差別矩陣中元素個數一定，設為Mcount，則：

(8)

(9)

3.2啟發式屬性約簡算法(算法2)

以不可區分對數DM(Ci)為啟發式信息，設計屬性約簡算法(算法2)，具體如下：

structDList{

data；

//數據在條件屬性Ci上的取值

List；

//在Ci上取值data的數據集合

count；

//為集合List中的數據個數

structDList*next；

//下一指針

}

輸入：簡化決策表U′，POS，NEG

輸出：Core

Step1初始化C′=C，Core=?，Count=0；

Step2while(Count++<|C|‖DList!=NULL) {foreachCiinC′ {

Step2.1求U′/Ci，且用DList鏈表存儲每個子劃分且按D進行劃分，再按條件屬性取不同值建立不同的List鏈表，并將List.count為0的結點刪除；

Step2.2計算DM(Ci)；對DList.count數是0的結點剪枝。

Step2.3計算Min(DM(Ci))，C′=C=Ck，

Core=Core∪CK//Ck為取值最小的條件屬性

}

}

Step3輸出Core;

算法2的主要時間用在求屬性重要度量方面。在求DM(Ci)時，主要掃描DList鏈表，DList的長度即為條件屬性Ci劃分所得的等價類數目|U′/Ci|，每個子劃分再按決策屬性D劃分，最好情況下是一個條件屬性就可將所有樣本區分，時間復雜度為：

4　算法實例與實驗分析

4.1算法實例

4.1.1求正、負區域及簡化決策表過程

為進一步說明上述算法原理，下面用表1所示的數據介紹算法運行過程。

表1　決策表U

(1)POS=?,NEG=?；

(2)U/a分四類，構成的DList鏈表為:

(3) 在(2)基礎上將各結點中的樣本按條件屬性b進行劃分，并建立相應的鏈表得到：

根據性質1可知，U中的10、4、9、11數據已經在鏈表中刪除，同時加入了POS中，即POS={4,9,10,11}；

(4) 同理可得，繼續按條件屬性c、d劃分得到：

POS={3,4,9,10,11}；

(5) 再將List中各結點的數據進行按D值劃分，若有D值不同的，則將結點中的第一個數據樣本加入到NEG中，否則加入到POS中，得到NEG={7,8}；POS={1,2,3,4,9,10,11,13}；U′的樣本數據為{1,2,3,4,7,8,9,10,11,13}，具體簡化決策表如表2所示。

表2　簡化決策表U′

對于決策表U，采用文獻[2]方法，每個條件屬性需按關鍵字收集，包括屬性共4個，需比較次數60，移動60次，得到U/C；最后再按決策屬性D不同值收集，將C值相同而D值不同的所有子劃分中第一個元素加入NEG，將C值相同且D值也相同的所有子劃分第一個元素加入POS中，需比較15次，10次移動，總共需145次。若采用本文算法1，按屬性a收集需15次比較，15次移動，再按屬性b、c和d收集，分別需比較次數11、10和10，共46次比較，移動次數即為刪除結點次，故需5次；此時，已有5個結點在POS中，再將U/C的5個子劃分中元素進行比較，需5次比較5次移動得到POS和NEG，共56次比較和移動。

4.1.2屬性約簡過程

在上述簡化決策表、正負區域基礎上，建立DList鏈表得：

(1)DList(a):

DList(b):

子劃分中帶下劃線的表明按D劃分屬于同類的。且最后一個結點被刪除，因為其count為1。

DList(c):

DList(d):

Min(DM(a),DM(b),DM(c),DM(d))=8，所以選a或b屬性加入Core。

(2) 設第一個選擇的屬性為b，則將DList(b)繼續按屬性a、c或d劃分，得到：

DM(b,d)= 0+0=0，所以將d加入Core，此時所有樣本已經區分，故約簡集為Core={b,d}。同理可得，其他約簡集有{a,b,c}。

4.2實驗分析

求解簡化決策表、正負區域是屬性約簡的關鍵環節，現將算法[1]與文獻[2]算法進行比較。在AMDAthlonⅡX2 2402.78GHz,RAM1.5G，VC6.0環境下編程，采用UCI數據庫中5個數據集為測試數據(D1:forestfires，D2:adult，D3:abalone，D4:mushroom，D5:poker_hand)，其中正區域記錄數為Pi，負區域記錄數為Ni，簡化表記錄數為Si)，執行過程中數據對比情況如表3所示。

表3　求U/C記錄比較對照表

由表3可知，因選擇的各數據集除D1有少量重復數據外，其他的測試數據均無重復數據，所以D2、D3、D4和D5數據簡化前后無變化，且正區域的記錄數等于簡化決策表的樣本數。雖然算法1與文獻[2]求正區域的時間復雜度均為O(|C‖U|)，但算法1在求解時不斷剔除已區分的樣本。對于D2共15個屬性，收集過程中第2個屬性加入時已有107條數據可區分，第3個屬性加入時有1675條數據區分，到第4個屬性時已區分所有樣本，其余屬性就無需繼續比較，所用時間相當于文獻[2]的1/5。對于D4，效果不明顯，將前10個屬性逐趟收集，幾乎沒有可區分對象，直至第21個屬性加入時有3764條數據已區分，導致求解效果不明顯。由此可看出，在按條件屬性不同值收集時，若某屬性的加入能夠區分的樣本越多，采用算法1時，求正、負區域的速度越快，因為算法1對已區分的樣本進行修剪，不參加下次的運算，減少搜索空間。

算法1的優勢體現在求正區域上，在算法1的基礎上，利用算法2對數據進行屬性約簡。算法2利用了差別矩陣算法的直觀性、可理解性，但又沒有差別矩陣算法所需的大量空間，所以算法2的優勢又表現在空間的開銷上。同樣，用D1-D5的數據進行實驗，得到算法2、文獻[2]算法和文獻[10]算法進行比較，如圖1所示。

圖1　各種算法時間性能對比

由圖1可知，算法2比文獻[2]算法略有提高，是因為在計算正區域時，能夠有效剔除已區分的樣本，且明顯較文獻[10]算法的約簡時間效果好。從圖中還可得，當|U|越大，且|C|越小時，文獻[10]算法越顯得不足。在|U‖C|較小時，算法2比文獻[2]算法挖掘時間效果顯示明確，但隨著數據對象個數及條件屬性個數增加，算法2的優勢越來越不明顯。在對樣本D4、D5運算時，出現了挖掘時間呈下降趨勢，而文獻[10]一起呈上升趨勢，是因為文獻[10]的時間復雜度為O(|U|2|C|)，它隨著|U|的增加，時間增速較文獻[2]和算法2要快。

空間上，算法2較文獻[10]也有優勢，具體如表4所示。

表4　多種算法空間占用比較

所示(Spacei為各算法所需空間，以MB為單位；RLi為各算法約簡后的屬性個數)。由表4可知，算法2在空間效果上比文獻[10]也有很大改觀。主要是因為文獻[10]需大量空間存儲二進制的信息矩陣。

5　結　語

屬性約簡過程中，正區域計算是很多屬性約簡算法必不可少的一步。通過對正、負區域的計算，可得到簡化決策表，剔除冗余數據，加速屬性約簡進度。文獻[2]的基數排序算法雖然效率較高，但未能在求簡化決策表過程中進行剪枝，本文算法1可有效得到正、負域及簡化決策表，且效率比文獻[2]的算法略高。在求屬性重要性度量時，引入DM(Ci)概念，充分利用差別矩陣算法的直觀、易理解的優點，但又無需建立信息矩陣，大大減少存儲空間。但目前的這些算法，只是針對靜態數據庫，而現實世界是不斷變化的，下一步是如何適應動態數據庫的屬性約簡。

[1]PawlakZ.Roughsets[J].InternationalJournalofComputerandInformationScience,1982,11(5):341-356.

[2] 徐章艷,劉作鵬.一個復雜度為的快速屬性約簡算法[J].計算機學報,2006,29(3):391-399.

[3] 王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機學報,2002,25(7):759-766.

[4] 楊明.一種基于改進差別矩陣的屬性約簡增量式更新算法[J].計算機學報,2007,30(5):815-822.

[5] 錢文彬,楊炳儒,徐章艷,等.基于差別矩陣的不一致決策表規則獲取算法[J].計算機科學,2013,40(6):215-218.

[6] 梁寶華,汪世義,蔡敏.基于順序表的啟發式屬性約簡算法[J].計算機工程,2012,38(2):51-53.

[7] 張文修,米據生,吳偉志.不協調目標信息系統的知識約簡[J].計算機學報,2003,26(1):12-18.

[8] 劉少輝,盛秋戩,吳斌,等.Rough集高效算法的研究[J].計算機學報,2003,26(5):524-529.

[9] 葛浩,李龍澍,楊傳健.基于簡化差別矩陣的增量式屬性約簡[J].四川大學學報:工程科學版,2013,45(1):116-124.

[10] 楊傳健,葛浩,李龍澍.垂直劃分二進制可分辨矩陣的屬性約簡[J].控制與決策,2013,28(4):563-569.

[11] 黃國順,曾凡智,陳廣義,等.基于區分能力的HU差別矩陣屬性約簡算法[J].小型微型計算機系統,2012,33(8):1800-1804.

[12] 葛浩,李龍澍,楊傳健.基于差別集的啟發式屬性約簡算法[J].小型微型計算機系統,2013,34(2):380-385.

HEURISTICSATTRIBUTEREDUCTIONALGORITHMBASEDONLISTSTRUCTURE

LiangBaohua

(Institute of Computer and Information Engineering,Chaohu University,Hefei 238000,Anhui,China)

Attributereductionisoneofmaincontentsinroughsettheoryresearch,andpositiveregioncalculationisthekeyofmostattributereductionalgorithms.Inordertoreducethetimeofpositiveregioncalculation,weproposedtheliststorage-basedpositiveregioncalculationmethod.Themethodstoresthedatawithsameattributevaluetosamenodedataoflist,duringthedatacollectingperiod,itcontinuouslydeletesthesubdivisionswith1astheircardinalnumber,byreducingthescaleofsampledataitdecreasescalculationtimeconsumptionandspeedsuptheattributereduction.Atthesametime,wegavethedefinitionofthenumberofpairsofindistinguishabledata,andusedittomeasureattributeimportance,anddesignedanefficientheuristicattributereductionalgorithm.Bytestingandcomparingtheperformancesofexamplesandexperimentswiththatofclassicalreductionalgorithm,theresultsprovedthatthismethodwaseffectiveandfeasibleintemporalandspatialeffects.

RoughsetAttributereductionListPositiveregionPairsnumberofindistinguishabledata

2014-10-15。國家自然科學基金項目(60573174)；安徽省高等學校省級自然科學研究項目(KJ2013Z231)。梁寶華，副教授，主研領域：粗糙集，數據挖掘。

TP181

ADOI:10.3969/j.issn.1000-386x.2016.03.061