前言：本站為你精心整理了區(qū)分鏈表屬性約簡改進算法范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

摘要屬性約簡是粗糙集理論中核心內(nèi)容之一，本文首先分析了區(qū)分矩陣的特性，給出經(jīng)典的區(qū)分矩陣算法。然后，鑒于區(qū)分矩陣存在的空間復(fù)雜度高的缺點，提出一種基于區(qū)分鏈表的屬性約簡改進算法，將對象數(shù)為n的區(qū)分矩陣大小由n(n-1)/2至少壓縮到|U/R|*（|U/R|-1）/2，降低了算法的空間復(fù)雜度，更適用于大數(shù)據(jù)量的情況。

關(guān)鍵詞粗糙集；區(qū)分矩陣；屬性約簡；區(qū)分線性表

1引言

粗糙集(RoughSet,RS)理論是Z.Pawlak提出的一種處理不一致、不完整數(shù)據(jù)和不精確知識表達等各種不完備信息的數(shù)學(xué)理論[1]。其中屬性約簡是粗糙集理論中核心內(nèi)容之一，現(xiàn)已證明是典型的NP難題[2，3]。所謂屬性約簡是指在保證信息系統(tǒng)分類能力或決策能力不變的條件下，刪除屬性集中的冗余屬性。屬性約簡在分類學(xué)習(xí)及分類數(shù)據(jù)挖掘中具有重要的作用，目前國內(nèi)外學(xué)術(shù)界在屬性約簡方面已經(jīng)做了大量研究，并得到了許多有效的算法[4~6]。文獻[4]深入分析了算法低效性的根源,給出了高效的約簡算法；文獻[5]給出了基于信息論的方法；文獻[6]利用正區(qū)域的啟發(fā)式信息給出了兩種屬性相對約簡算法；其中應(yīng)用較多的是基于華沙大學(xué)數(shù)學(xué)家Skowron提出差別矩陣[7]以及在此基礎(chǔ)上的一些改進[9~11]，由于這種基于區(qū)分矩陣方法易于解釋和計算核屬性,同時也便于約簡，該方法為屬性約簡算法提供了一種很好的思路。然而，基于區(qū)分矩陣的屬性約簡算法對對象數(shù)為n的區(qū)分矩陣大小為n(n-1)/2，不適用于大數(shù)據(jù)量的情況，所以本文給出了一種改進算法，將空間復(fù)雜度至少壓縮到|U/R|*（|U/R|-1）/2，該算法大大降低了算法的空間復(fù)雜度，適用于大數(shù)據(jù)量的情況。

2基本概念

定義1[2]：設(shè)U為一個有限的非空論域，R為U上的等價關(guān)系。等價關(guān)系R把集合U劃分為多個互不相交的子集，每一個子集稱為一個等價類，用[x]R表示，[x]R={y∈U|xRy}，其中x∈U，x∈y稱為關(guān)于R的等價關(guān)系，論域U上的所有等價類的集合用U/R來表示。

定義2[2]：令R為一族等價關(guān)系，rR,如果IND(R)=IND(R-{r}),則稱r為R中不必要的；否則r為R中必要的[2]，若R中任意一個等價關(guān)系r都是必要的，則稱R是獨立的，否則稱R是依賴的。

定義3[8]：設(shè)，若Q是獨立的，且IND(Q)=IND(P)，則Q是等價關(guān)系族P的一個約簡。

定義4[8]：設(shè)P和Q是論域U上的等價關(guān)系，Q的P正域記作POSP(Q)，定義為：

Q的P正域是U中所有根據(jù)U/P的信息準(zhǔn)確分類到關(guān)系Q的等價關(guān)系中去的對象構(gòu)成的集合。

定義5[8]：設(shè)P和Q是論域U上的等價關(guān)系，R∈P，若

POSP(Q)=POS(P-{R})(Q)

則稱R為P中Q不必要的，否則稱R為P中Q必要的。

若P中任意一關(guān)系R都是Q必要的，則稱P是Q獨立的(相對于Q獨立的)。

定義6[2]：設(shè)SP，S為P的Q約簡，當(dāng)且僅當(dāng)S是P的Q是獨立的子集，且POSS(Q)=POSP(Q).P的Q約簡稱為相對約簡。

定義7：區(qū)分矩陣是華沙大學(xué)數(shù)學(xué)家Skowron[7]提出的，對于系統(tǒng)S=(U,A),其中A=C∪D,a(x)是x在屬性a上的值,區(qū)分矩陣M為：

同時分辨矩陣中的核就是組合數(shù)為1的屬性。

3基于區(qū)分鏈表的屬性約簡改進算法

區(qū)分矩陣的空間復(fù)雜度為n(n-1)/2,保存著論域中兩兩對象的可區(qū)分屬性.在論域關(guān)于屬性集劃分中，同一個等價類的對象兩兩在區(qū)分矩陣中的元素為空，而且與其他等價類的對象所構(gòu)成的區(qū)分矩陣中的元素完全相同，因此從每一個等價類中只取一個對象構(gòu)造的新的論域，其約簡與原來的相同,而空間復(fù)雜度最多為|U/R|*（|U/R|-1）/2.

區(qū)分矩陣Matrix的某元素Matrix[i][j]，是區(qū)分對象U[i]與U[j]的條件屬性集，由于在合取吸取運算中，參數(shù)i、j并沒有實際價值，因此改用區(qū)分鏈表List來取代區(qū)分矩陣。在構(gòu)造區(qū)分鏈表前，先定義存儲核屬性的變量core，可區(qū)分兩對象的條件屬性集若只有一個屬性Ri，則屬性Ri是核屬性，那么Ri存儲到變量core，在接下來的區(qū)分鏈表的構(gòu)造過程中，若區(qū)分屬性集包括已經(jīng)提取出來的核屬性，直接約去，不插入到區(qū)分鏈表中；否則，插入到區(qū)分鏈表的表尾。為減少區(qū)分鏈表的大小，可以在每產(chǎn)生一個核屬性Rj，進入變量core后，化簡區(qū)分鏈表List，若List中的元素List[k]包含屬性Rj則直接刪除元素List[k]。對應(yīng)算法如下：

for(p=U;p->next!=NULL;p=p->next)

for(q=p->next;q!=NULL;q=q->next)

{

x=對象p、q的可區(qū)分屬性集；

if（|x|==1）則x進入核變量core；

elseif（x不包含核變量core中已有的任何一個核屬性）

List.Add(x);

在得到了核和區(qū)分鏈表后，首先，將核加入到候選約簡中；然后，統(tǒng)計區(qū)分鏈表中各屬性出現(xiàn)的次數(shù)，將出現(xiàn)次數(shù)最多的屬性R加入到侯選約簡中，刪除區(qū)分鏈表中出現(xiàn)R的所有節(jié)點，依次循環(huán)，直到區(qū)分鏈表為空，此時侯選約簡就是所求約簡。對應(yīng)算法如下：

C_reduce=core;

While(1)

{

if(List=Null)break;

else

{

遍歷List,統(tǒng)計各條件屬性出現(xiàn)的次數(shù)；

選擇出現(xiàn)次數(shù)最多的那個屬性R；

C_reduce=C_reduce{R};

刪除List中所有出現(xiàn)R的的節(jié)點；

}

}

4實例分析

設(shè)如下表1[12]給定的決策表，求所有約簡及核。

UConditionalattributesdecisions

abcd

x12201

x21200

x31201

x40000

x51010

x62011

而應(yīng)用本文給出的算法,區(qū)分線性表只有{b,c}一個元素,計算過程如下:首先得到區(qū)分屬性集{a}，a進入核變量，在隨后生成的區(qū)分屬性集中只要含有a，則直接約掉，{b,c}進入?yún)^(qū)分線性表，采用啟發(fā)式算法，可得到約簡{a,b}。而基于區(qū)分矩陣的屬性約簡算法構(gòu)造的區(qū)分矩陣如下：

本算法相對于傳統(tǒng)方法，大大減少了區(qū)分矩陣所需要的存儲空間。

5結(jié)論

近年來Rough集理論以其獨特的優(yōu)勢正贏得越來越多的專家學(xué)者關(guān)注,在理論研究方面日趨成熟,并在許多領(lǐng)域取得了較為成功的應(yīng)用，屬性約簡算法是粗糙集理論的核心內(nèi)容之一，其中，區(qū)分矩陣作為屬性約簡的主要方法之一已經(jīng)受到越來越多的學(xué)者關(guān)注，因此，本文深入研究分析了區(qū)分矩陣算法，基于區(qū)分線性表，提出一種改進的屬性約簡算法。

參考文獻

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

[2]張文修,吳偉志.粗糙集理論介紹和研究綜述[J].模糊系統(tǒng)與數(shù)學(xué),2000,15(4):1-12

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

[4]劉少輝.Rough集高效算法的研究.計算機學(xué)報(J),2003,26(5):524-529

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

[6]張騰飛,肖健梅,王錫淮.粗糙集理論中屬性相對約簡算法.電子學(xué)報(J),2005,33(11):2080-2083

[7]SkowronA.RauszerC.TheDiscerni-bilityMatricsandFunctionsinInformationSystem(J),IntelligentDecisionSupportHandbookofApplicationsandAdvancesoftheRoughSetsTheoryDordrecht:KluwerAcademicPublishers,1992:331-362

[8]李雄飛,李軍.數(shù)據(jù)挖掘與知識發(fā)現(xiàn)[M].高等教育出版社,2003

[9]范敏,劉文奇.基于粗集可辨識矩陣的屬性約簡算法[J].計算機工程與應(yīng)用,2004,38(13):79-80

[10]WANGJue,WANGJu.ReductionAlgorithmBasedonDisernibilityMatrix:TheOrderedAttributesMethod[J].put.Sci.&Technol,2001,16(6):489-504

[11]王兵,陳善本.一種基于差別矩陣的屬性約簡完備算法[J].上海交通大學(xué)學(xué)報,2004,38(1):43-46