基于鏈表結(jié)構(gòu)的啟發(fā)式屬性約簡算法

梁 寶 華

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

?

基于鏈表結(jié)構(gòu)的啟發(fā)式屬性約簡算法

梁 寶 華

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

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

粗糙集屬性約簡鏈表正區(qū)域不可區(qū)分對象對數(shù)

0　引　言

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

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

1　相關(guān)概念

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

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

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

下近似：

(1)

上近似：

(2)

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

(3)

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

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

(4)

其中U′為簡化后的無重復數(shù)據(jù)。

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

(5)

性質(zhì)1設P?C,|U/Pi|=1，則U/Pi中的元素均屬于正區(qū)域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屬于正區(qū)域元素，否則，屬于負區(qū)域元素。因為|U/Pi|=1，所以，U/P的第i個劃分中只有一個元素，設此元素為x。假設x屬于負區(qū)域，則可找到另一元素y，使得f(x,P)=f(y,P)且f(x,D)≠f(y,D)，但x∈U/Pi∧|U/Pi|=1，說明f(x,P)是唯一的，所以上述假設不成立，故x必屬于正區(qū)域元素。證畢。

2　快速計算正、負區(qū)域算法及其分析

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

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

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

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

算法中涉及到的鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)為：

structList{

data;

//數(shù)據(jù)在條件屬性Ci上的取值

set;

//在Ci上取值data的數(shù)據(jù)集合

count;

//為集合set的數(shù)據(jù)個數(shù)

next;

//下一指針

}

輸入：U,C,D

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

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

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

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

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

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

Step4掃描鏈表List的每個結(jié)點，若某結(jié)點的set中數(shù)據(jù)有D值不同的，則選擇set中第一個數(shù)據(jù)加入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中鏈表的結(jié)點個數(shù)與簡化決策表中的元素個數(shù)相同，掃描List每個結(jié)點所需時間為O(|U′|)；Step5的為O(1)，僅僅是將POS與NEG合并。

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

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

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

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

3　啟發(fā)式屬性約簡算法

3.1屬性重要性度量

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

(6)

(7)

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

(8)

(9)

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

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

structDList{

data；

//數(shù)據(jù)在條件屬性Ci上的取值

List；

//在Ci上取值data的數(shù)據(jù)集合

count；

//為集合List中的數(shù)據(jù)個數(shù)

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的結(jié)點刪除；

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

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

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

}

}

Step3輸出Core;

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

4　算法實例與實驗分析

4.1算法實例

4.1.1求正、負區(qū)域及簡化決策表過程

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

表1　決策表U

(1)POS=?,NEG=?；

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

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

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

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

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

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

表2　簡化決策表U′

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

4.1.2屬性約簡過程

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

(1)DList(a):

DList(b):

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

DList(c):

DList(d):

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

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

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

4.2實驗分析

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

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

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

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

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

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

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

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

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

5　結(jié)　語

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

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

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

[7] 張文修,米據(jù)生,吳偉志.不協(xié)調(diào)目標信息系統(tǒng)的知識約簡[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] 黃國順,曾凡智,陳廣義,等.基于區(qū)分能力的HU差別矩陣屬性約簡算法[J].小型微型計算機系統(tǒng),2012,33(8):1800-1804.

[12] 葛浩,李龍澍,楊傳健.基于差別集的啟發(fā)式屬性約簡算法[J].小型微型計算機系統(tǒng),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)。梁寶華，副教授，主研領(lǐng)域：粗糙集，數(shù)據(jù)挖掘。

TP181

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