基于區(qū)分鏈表的屬性約簡(jiǎn)改進(jìn)算法
摘 要 屬性約簡(jiǎn)是粗糙集理論中核心內(nèi)容之一,本文首先分析了區(qū)分矩陣的特性,給出經(jīng)典的區(qū)分矩陣算法。然后,鑒于區(qū)分矩陣存在的空間復(fù)雜度高的缺點(diǎn),提出一種基于區(qū)分鏈表的屬性約簡(jiǎn)改進(jìn)算法,將對(duì)象數(shù)為n的區(qū)分矩陣大小由n(n-1)/2至少壓縮到|U/R|x|U/R|-1)/2,降低了算法的空間復(fù)雜度,更適用于大數(shù)據(jù)量的情況。
關(guān)鍵詞 粗糙集;區(qū)分矩陣;屬性約簡(jiǎn);區(qū)分線性表
1 引言
粗糙集(Rough Set ,RS) 理論是 Z.Pawlak 提出的一種處理不一致、不完整數(shù)據(jù)和不精確知識(shí)表達(dá)等各種不完備信息的數(shù)學(xué)理論[1]。其中屬性約簡(jiǎn)是粗糙集理論中核心內(nèi)容之一,現(xiàn)已證明是典型的NP難題[2,3]。所謂屬性約簡(jiǎn)是指在保證信息系統(tǒng)分類(lèi)能力或決策能力不變的條件下,刪除屬性集中的冗余屬性。屬性約簡(jiǎn)在分類(lèi)學(xué)習(xí)及分類(lèi)數(shù)據(jù)挖掘中具有重要的作用,目前國(guó)內(nèi)外學(xué)術(shù)界在屬性約簡(jiǎn)方面已經(jīng)做了大量研究,并得到了許多有效的算法[4~6]。文獻(xiàn)[4] 深入分析了算法低效性的根源,給出了高效的約簡(jiǎn)算法;文獻(xiàn)[5]給出了基于信息論的方法;文獻(xiàn)[6]利用正區(qū)域的啟發(fā)式信息給出了兩種屬性相對(duì)約簡(jiǎn)算法;其中應(yīng)用較多的是基于華沙大學(xué)數(shù)學(xué)家Skowron提出差別矩陣[7]以及在此基礎(chǔ)上的一些改進(jìn)[9~11],由于這種基于區(qū)分矩陣方法易于解釋和計(jì)算核屬性,同時(shí)也便于約簡(jiǎn),該方法為屬性約簡(jiǎn)算法提供了一種很好的思路。然而,基于區(qū)分矩陣的屬性約簡(jiǎn)算法對(duì)對(duì)象數(shù)為n的區(qū)分矩陣大小為n(n-1)/2,不適用于大數(shù)據(jù)量的情況,所以本文給出了一種改進(jìn)算法,將空間復(fù)雜度至少壓縮到|U/R|x|U/R|-1)/2,該算法大大降低了算法的空間復(fù)雜度,適用于大數(shù)據(jù)量的情況。
2 基本概念
定義1[2]:設(shè)U為一個(gè)有限的非空論域,R為U上的等價(jià)關(guān)系。等價(jià)關(guān)系R 把集合U 劃分為多個(gè)互不相交的子集,每一個(gè)子集稱(chēng)為一個(gè)等價(jià)類(lèi),用[x]R表示,[x]R={y∈U|xRy},其中x∈U,x∈y稱(chēng)為關(guān)于R 的等價(jià)關(guān)系,論域U上的所有等價(jià)類(lèi)的集合用U/ R來(lái)表示。
定義2[2]:令R為一族等價(jià)關(guān)系,r R,如果 IND(R)= IND(R-{r}),則稱(chēng)r為R中不必要的;否則r為R中必要的[2],若R中任意一個(gè)等價(jià)關(guān)系r都是必要的,則稱(chēng)R是獨(dú)立的,否則稱(chēng)R是依賴(lài)的。
定義3[8]:設(shè),若Q是獨(dú)立的,且IND(Q)=IND(P),則Q是等價(jià)關(guān)系族P的一個(gè)約簡(jiǎn)。
定義4[8]:設(shè)P和Q是論域U上的等價(jià)關(guān)系,Q的P正域記作POSP(Q),定義為:
Q的P正域是U中所有根據(jù)U/P的信息準(zhǔn)確分類(lèi)到關(guān)系Q的等價(jià)關(guān)系中去的對(duì)象構(gòu)成的集合。
定義5[8]:設(shè)P和Q是論域U上的等價(jià)關(guān)系,R∈P,若
POSP(Q) =POS(P-{R})(Q)
則稱(chēng)R為P中Q不必要的,否則稱(chēng)R為P中Q必要的。
若P中任意一關(guān)系R都是Q必要的,則稱(chēng)P是Q獨(dú)立的(相對(duì)于Q獨(dú)立的)。
定義6[2]:設(shè) SP,S為P的Q約簡(jiǎn),當(dāng)且僅當(dāng)S是P的Q是獨(dú)立的子集,且POSS(Q) =POSP(Q). P的Q約簡(jiǎn)稱(chēng)為相對(duì)約簡(jiǎn)。
定義7:區(qū)分矩陣是華沙大學(xué)數(shù)學(xué)家Skowron[7]提出的,對(duì)于系統(tǒng)S=(U,A),其中A=C∪D, a(x)是x在屬性a上的值,區(qū)分矩陣M為:
同時(shí)分辨矩陣中的核就是組合數(shù)為1的屬性。
3 基于區(qū)分鏈表的屬性約簡(jiǎn)改進(jìn)算法
區(qū)分矩陣的空間復(fù)雜度為n(n-1)/2,保存著論域中兩兩對(duì)象的可區(qū)分屬性.在論域關(guān)于屬性集劃分中,同一個(gè)等價(jià)類(lèi)的對(duì)象兩兩在區(qū)分矩陣中的元素為空,而且與其他等價(jià)類(lèi)的對(duì)象所構(gòu)成的區(qū)分矩陣中的元素完全相同,因此從每一個(gè)等價(jià)類(lèi)中只取一個(gè)對(duì)象構(gòu)造的新的論域,其約簡(jiǎn)與原來(lái)的相同,而空間復(fù)雜度最多為|U/R|x|U/R|-1)/2.
區(qū)分矩陣Matrix的某元素Matrix[i][j],是區(qū)分對(duì)象U[i]與U[j]的條件屬性集,由于在合取吸取運(yùn)算中,參數(shù)i、j并沒(méi)有實(shí)際價(jià)值,因此改用區(qū)分鏈表List來(lái)取代區(qū)分矩陣。在構(gòu)造區(qū)分鏈表前,先定義存儲(chǔ)核屬性的變量core,可區(qū)分兩對(duì)象的條件屬性集若只有一個(gè)屬性Ri,則屬性Ri是核屬性,那么Ri存儲(chǔ)到變量core,在接下來(lái)的區(qū)分鏈表的構(gòu)造過(guò)程中,若區(qū)分屬性集包括已經(jīng)提取出來(lái)的核屬性,直接約去,不插入到區(qū)分鏈表中;否則,插入到區(qū)分鏈表的表尾。為減少區(qū)分鏈表的大小,可以在每產(chǎn)生一個(gè)核屬性Rj,進(jìn)入變量core后,化簡(jiǎn)區(qū)分鏈表List,若List中的元素List[k]包含屬性Rj則直接刪除元素List[k]。對(duì)應(yīng)算法如下:
for(p=U;p->next !=NULL;p=p->next)
for(q=p->next;q!=NULL;q=q->next)
{
x= 對(duì)象p、q的可區(qū)分屬性集;
if(|x|==1) 則進(jìn)入核變量core;
else if(x不包含核變量core中已有的任何一個(gè)核屬性)
List.Add(x);
}
在得到了核和區(qū)分鏈表后,首先,將核加入到候選約簡(jiǎn)中;然后,統(tǒng)計(jì)區(qū)分鏈表中各屬性出現(xiàn)的次數(shù),將出現(xiàn)次數(shù)最多的屬性R加入到侯選約簡(jiǎn)中,刪除區(qū)分鏈表中出現(xiàn)R的所有節(jié)點(diǎn),依次循環(huán),直到區(qū)分鏈表為空,此時(shí)侯選約簡(jiǎn)就是所求約簡(jiǎn)。對(duì)應(yīng)算法如下:
C_reduce=core;
While(1)
{
if(List=Null) break;
else
{
遍歷List,統(tǒng)計(jì)各條件屬性出現(xiàn)的次數(shù);
選擇出現(xiàn)次數(shù)最多的那個(gè)屬性R;
C_reduce=C_reduce {R};
刪除List中所有出現(xiàn)R的的節(jié)點(diǎn);
}
}
4 實(shí)例分析
設(shè)如下表1[12]給定的決策表,求所有約簡(jiǎn)及核。
U
Conditional attributes
decisions
a
b
c
d
x1
2
2
0
1
x2
1
2
0
0
x3
1
2
0
1
x4
0
0
0
0
x5
1
0
1
0
x6
2
0
1
1
而應(yīng)用本文給出的算法,區(qū)分線性表只有{b,c}一個(gè)元素,計(jì)算過(guò)程如下:首先得到區(qū)分屬性集{a},a進(jìn)入核變量,在隨后生成的區(qū)分屬性集中只要含有a,則直接約掉,{b,c}進(jìn)入?yún)^(qū)分線性表,采用啟發(fā)式算法,可得到約簡(jiǎn){a,b}。而基于區(qū)分矩陣的屬性約簡(jiǎn)算法構(gòu)造的區(qū)分矩陣如下:
本算法相對(duì)于傳統(tǒng)方法,大大減少了區(qū)分矩陣所需要的存儲(chǔ)空間。
5 結(jié)論
近年來(lái)Rough 集理論以其獨(dú)特的優(yōu)勢(shì)正贏得越來(lái)越多的專(zhuān)家學(xué)者關(guān)注,在理論研究方面日趨成熟,并在許多領(lǐng)域取得了較為成功的應(yīng)用,屬性約簡(jiǎn)算法是粗糙集理論的核心內(nèi)容之一,其中,區(qū)分矩陣作為屬性約簡(jiǎn)的主要方法之一已經(jīng)受到越來(lái)越多的學(xué)者關(guān)注,因此,本文深入研究分析了區(qū)分矩陣算法,基于區(qū)分線性表,提出一種改進(jìn)的屬性約簡(jiǎn)算法。
參考文獻(xiàn)
[1] Pawlak Z. Rough Sets(J). International Journal of Computer and Information Science, 1982, 11(5): 341-356
[2] 張文修,吳偉志. 粗糙集理論介紹和研究綜述[J ] . 模糊系統(tǒng)與數(shù)學(xué),2000 ,15 (4) :1-12
[3] 王國(guó)胤. Rough 集理論與知識(shí)獲取[M] . 西安:西安交通大學(xué)出版社,2001
[4] 劉少輝. Rough集高效算法的研究. 計(jì)算機(jī)學(xué)報(bào)(J), 2003,26(5):524-529
[5] 王國(guó)胤, 于 洪, 楊大春. 基于條件信息熵的決策表約簡(jiǎn)(J) . 計(jì)算機(jī)學(xué)報(bào) ,2002, 25( 7 ): 759-766
[6] 張騰飛, 肖健梅, 王錫淮. 粗糙集理論中屬性相對(duì)約簡(jiǎn)算法. 電子學(xué)報(bào)(J) ,2005, 33(11):2080-2083
[7] Skowron A. Rauszer C. The Discerni-bility Matrics and Functions in Information System(J), Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory Dordrecht: Kluwer Academic Publishers, 1992: 331-362
[8] 李雄飛, 李軍. 數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M]. 高等教育出版社,2003
[9] 范 敏,劉文奇.基于粗集可辨識(shí)矩陣的屬性約簡(jiǎn)算法[J ].計(jì)算機(jī)工程與應(yīng)用,2004 ,38 (13) :79 - 80
[10] WANGJue ,WANGJu. Reduction Algorithm Based on Disernibility Matrix: The Ordered Attributes Method [ J ] . J . Comput . Sci . &Technol ,2001 ,16 (6) :489 - 504
[11] 王兵,陳善本.一種基于差別矩陣的屬性約簡(jiǎn)完備算法[J ].上海交通大學(xué)學(xué)報(bào),2004,38(1):43- 46