粗糙集理論，是繼概率論、模糊集、證據(jù)理論之后的又一個(gè)處理不確定性的數(shù)學(xué)工具。作為一種較新的軟計(jì)算方法，粗糙集近年來越來越受到重視，其有效性已在許多科學(xué)與工程領(lǐng)域的成功應(yīng)用中得到證實(shí)，是當(dāng)前國際上人工智能理論及其應(yīng)用領(lǐng)域中的研究熱點(diǎn)之一。本文是一篇科技信息雜志投稿的論文范文，主要論述了一種基于數(shù)組的高效等價(jià)類劃分算法。

　　摘要：粗糙集理論是建立在等價(jià)類的基礎(chǔ)上的，等價(jià)類劃分算法的優(yōu)劣會(huì)直接影響到屬性約簡(jiǎn)和規(guī)則提取的效率.針對(duì)等價(jià)類基數(shù)排序算法中存在重復(fù)計(jì)算和空間開銷較大的問題，提出了一種基于數(shù)組的等價(jià)類劃分算法. 算法的時(shí)間復(fù)雜度為O(|U||C|)，空間復(fù)雜度為O|U|.最后通過具體案例驗(yàn)證了算法的執(zhí)行過程。結(jié)果表明算法高效且正確可行。

　　關(guān)鍵詞：粗糙集,屬性約簡(jiǎn),等價(jià)類劃分,基數(shù)排序,規(guī)則提取

　　An Efficient Equivalence Partitioning Algorithm Based on Array

　　FAN Yan-ying1， ZHANG Zi-min2， CHEN Guan-ping1

　　(1.College of computer and Information Engineering， HeZhou University， Hezhou 542899， China; 2.Multimedia Technology Center， HeZhou University， Hezhou 542899， China)

　　Abstract： Rough set theory is based on Equivalence class，The good and bad of equivalence partitioning algorithm will directly affect the efficiency of the attribute reduction and rule extraction.Aiming at the problem of duplicate computing and large space overhead existed in the equivalence class of Radix Sort， propose an equivalence partitioning algorithm based on array.The time complexity of the algorithm is O (|U||C|)， The space complexity is O|U|. Finally， verify the process of algorithm by specific examples. The results show that the algorithm is correct and feasible

　　Key words： rough set; attribute reduction; equivalence partitioning; radix sort organization

　　粗糙集是在1982 年由波蘭著名學(xué)者Pawlak Z提出的，該理論是一種處理不完備、不精確和不確定知識(shí)的數(shù)學(xué)工具[1]。跟其他處理不精確，不完備，不確定的理論相比，粗糙集無需其他先驗(yàn)知識(shí)，只需要提供其所處理的數(shù)據(jù)集，即可對(duì)這些數(shù)據(jù)進(jìn)行推理，分析，和處理.正是由于粗糙集有這些方面的優(yōu)勢(shì)，引起了國內(nèi)外科學(xué)家的關(guān)注，并致力于粗糙集的研究和應(yīng)用推廣.目前，粗糙集在社會(huì)很多領(lǐng)域的應(yīng)用都取得了很好的效果.屬性約簡(jiǎn)是粗糙集研究的重要內(nèi)容之一[2]。屬性約簡(jiǎn)就是在保持?jǐn)?shù)據(jù)庫分類能力不變的條件下刪除其中不重要和不相關(guān)的數(shù)據(jù)[3]。

　　通常粗糙集進(jìn)行屬性約簡(jiǎn)要判斷數(shù)據(jù)分類能力是否發(fā)生變化是建立在計(jì)算等價(jià)類的基礎(chǔ)上的，因此求等價(jià)類的算法的優(yōu)劣是影響后續(xù)屬性約簡(jiǎn)或規(guī)則提取算法效率的重要因素之一.因此設(shè)計(jì)出低空間復(fù)雜度和時(shí)間復(fù)雜度的等價(jià)類劃分算法是一件值得探索的工作.

　　目前不少專家學(xué)者對(duì)等價(jià)類都進(jìn)行了深入研究[5].同時(shí)提出了很多種等價(jià)類劃分算法。趙軍[7]采用了快速排序法劃分等價(jià)類U/C，其時(shí)間復(fù)雜度為O( | C ||U| log |U| ) 。劉少輝等人在文獻(xiàn)[8]還進(jìn)一步研究了正區(qū)域的漸增式計(jì)算方法，由此設(shè)計(jì)了完備的屬性約簡(jiǎn)算法，該算法時(shí)間復(fù)雜度為O( | C| 2 |U| log | U | ) 。徐章艷等人在文獻(xiàn)[9]對(duì)等價(jià)類劃分算法進(jìn)行改進(jìn)，采用鏈?zhǔn)交鶖?shù)排序算法劃分等價(jià)類U/C，其時(shí)間復(fù)雜度為O( | C| |U| ) .

　　為進(jìn)一步降低等價(jià)類劃分算法時(shí)間復(fù)雜度，減小空間開銷，提高等價(jià)類算法的執(zhí)行效率，我們?cè)谘芯楷F(xiàn)有等價(jià)類劃分算法基礎(chǔ)上，提出了一種基于數(shù)組的等價(jià)類劃分算法。最后通過具體的案例驗(yàn)證算法的正確性和高效性。

　　1 基本概念

　　定義1[4] 決策表

　　一個(gè)信息表可以表示為S=，其中U是論域，C是條件屬性集，D是決策屬性集，V= 是屬性的值域，其中，Va是屬性a的值域，f： U×(∪DC∪D)→V是信息決策表函數(shù)。當(dāng)D≠?時(shí)，該信息表示一個(gè)決策表。

　　定義2[6] 等價(jià)類

　　每一個(gè)屬性子集P?∪D?C∪D 決定了一個(gè)二元不可區(qū)分關(guān)系

　　IND(P)={(x，y)∈U×U，?a∈P |，f(x，a)=f(y，a)}

　　而IND(P)構(gòu)成了U的一個(gè)劃分，用U/IND(P)表示，簡(jiǎn)記為U/P， U/P的任何元素[x]p={y|?a∈P ，f(x，a)=f(y，a)}稱為等價(jià)類。

　　2 算法分析

　　徐章艷教授在文獻(xiàn)[9]中給出了鏈?zhǔn)交鶖?shù)排序算法(在本文稱之為算法1)，經(jīng)研究發(fā)現(xiàn)該算法存在著重復(fù)運(yùn)算現(xiàn)象。在第3步中，對(duì)論域U中的所有對(duì)象，按照每個(gè)屬性的取值進(jìn)行歸類(即把在該屬性值上取值相等的實(shí)例歸為一隊(duì))，事實(shí)上這當(dāng)中存在著重復(fù)運(yùn)算。因?yàn)榈趇趟收集的隊(duì)列結(jié)果是可以作為下一趟(i+1)趟收集的基礎(chǔ)的。 　　下面用算法1對(duì)決策表進(jìn)行等價(jià)類劃分，決策表如表1所示。

　　表1 決策表

　　[&a&b&c&d&D&X1&1&1&1&1&0&X2&2&2&2&1&1&X3&1&1&1&1&0&X4&2&3&2&3&0&X5&2&2&2&1&1&X6&3&1&2&1&0&X7&1&2&3&2&2&X8&2&3&1&2&3&X9&3&1&2&1&1&X10&1&2&3&2&2&X11&3&1&2&1&1&X12&2&3&1&2&3&X13&4&3&4&2&1&X14&1&2&3&2&3&X15&4&3&4&2&2&]

　　算法1對(duì)決策表進(jìn)行第一趟分配：

　　FR[0] →X 1→X 3→X 7→X 10→X 14←end [ 0] [9] ，

　　FR [1] →X 2→X 4→X 5→X 8→X 12←end[ 1] [9]，

　　FR [2] →X 6→X 9→X 11←end[ 2] [9] ，

　　FR [3] →X 13→X 15←end[ 3] [9] .

　　第2趟分配依然是對(duì)論域U進(jìn)行分配，結(jié)果如下：

　　FR [0] →X 1→X 3→X 6→X 9→X 11←end[ 0] [9]，

　　FR [1] →X 7→X 10→X 14→X 2→X 5←end [ 1] [9] ，

　　FR [2] →X 4→X 8→X 12→X 13→X 15←end[ 2] [9] .

　　后面的依次類推，也就是該算法每一趟的分配收集都是獨(dú)立進(jìn)行的。事實(shí)上第i+1趟分配是可以再第i趟分配的基礎(chǔ)上進(jìn)行的。

　　以第1趟收集結(jié)果來分析：FR[0]隊(duì)列中的任何元素{ X 1→X 3→X 7→X 10→X 14}和FR[1]隊(duì)列中的任何元素{ X 2→X 4→X 5→X 8→X 12}都是不可能歸為一個(gè)等價(jià)類的。因?yàn)樗麄冊(cè)趯傩詀上的取值不同(即X 1，X 3等不可能與FR[ 1]中X 2，X 4等屬于同一個(gè)等價(jià)類)。因此我們可以在第1趟分配的基礎(chǔ)上進(jìn)行第2趟分配。具體操作為在第1趟的FR[ 0]隊(duì)列中，比較屬性b的值，把在隊(duì)列中屬性值B相同的再細(xì)分成更小隊(duì)列，完成后釋放FR[ 0]所占用的空間，同理，對(duì)FR[ 1]，F(xiàn)R[ 2]，F(xiàn)R[ 3]進(jìn)行同樣的操作。以此循環(huán)，當(dāng)比較完最后一個(gè)屬性時(shí)，事實(shí)上就已經(jīng)完成了等價(jià)類的劃分。整個(gè)執(zhí)行過程類似于一棵樹的生產(chǎn)過程.也就是說實(shí)際上我們只要對(duì)算法1中的步驟3進(jìn)行改進(jìn)，在第3步循環(huán)完后即可生成所需的等價(jià)類。無需再進(jìn)行后續(xù)的步驟4，步驟5.因此改進(jìn)后的算法復(fù)雜度更加低，算法更簡(jiǎn)單。

　　3 新算法描述

　　改進(jìn)后的算法如下

　　算法2 一種改進(jìn)的高效等價(jià)類劃分算法

　　輸入：決策表S=U={u1，u2，u3……un}，

　　輸出：對(duì)應(yīng)的劃分U/C

　　步驟1 for(i=1，i　　{ 步驟1.1 if i==1;

　　執(zhí)行第一趟劃分：求第1個(gè)屬性的值的個(gè)數(shù)K，并創(chuàng)建K個(gè)動(dòng)態(tài)數(shù)組，根據(jù)第1個(gè)屬性值分別把各實(shí)例放入相應(yīng)的數(shù)組中;

　　Else

　　步驟1.2

　　設(shè)由第i-1趟分配所產(chǎn)生的數(shù)組序列為：arry1，arry2，arry3……arryk;

　　令T=1;

　　For each arryj (j=1，2，……k) //對(duì)上一趟產(chǎn)生的任意數(shù)組執(zhí)行以下操作

　　{ 步驟1.2.1 令P=T;

　　創(chuàng)建數(shù)組arryt’;同時(shí)把 arryj的第一個(gè)元素放入arryt’中;

　　T=T+1;

　　令 L=length(arryj) //求數(shù)組arryj的長(zhǎng)度

　　步驟1.2.2 For (M=1，M　　{ 令E=0;

　　For(b=p，b　　{ if (f(arryj[M]，ci)==f(arryb’[0]，ci)) //如果arryj中第M個(gè)實(shí)例的屬性ci的取值與arryb’數(shù)組中的第1個(gè)元素ci值相等 則把a(bǔ)rryj中的第M個(gè)元素歸入arryb’中，

　　令e=1，終止循環(huán)，轉(zhuǎn)步驟1.2.2

　　}

　　If (e==0)

　　則創(chuàng)建一個(gè)新的動(dòng)態(tài)數(shù)組arryT’，同時(shí)把a(bǔ)rryj中的第M個(gè)元素歸入新數(shù)組arryT’中;

　　T=T+1; }}

　　釋放 數(shù)組arryj所占空間;}

　　算法分析：該算法在對(duì)每個(gè)對(duì)象屬性值的比較過程中，逐步逼近生成等價(jià)類，在最后一個(gè)屬性進(jìn)行比較排序的過程中，實(shí)際上也就完成了對(duì)等價(jià)類的劃分。同時(shí)在對(duì)某一個(gè)數(shù)組進(jìn)行劃分完畢后，立刻釋放該數(shù)組所占空間，這樣就減少了空間開銷。該算法解決了文獻(xiàn)[9]對(duì)屬性進(jìn)行比較過程中的重復(fù)運(yùn)算問題以及產(chǎn)生空隊(duì)列的問題。因此算法相對(duì)于文獻(xiàn)[9]的效率會(huì)更高些(相當(dāng)于無需執(zhí)行文獻(xiàn)[9]的第4，5步)。該算法的時(shí)間復(fù)雜度為O(|U||C|)，空間復(fù)雜度為O|U|.

　　4 算例分析

　　我們同樣以文獻(xiàn)[9] 中的決策表(表1)為例說明該算法計(jì)算U/{a，b，c，d}的過程。

　　進(jìn)入算法執(zhí)行for的第一次循環(huán)(即根據(jù)屬性a對(duì)等價(jià)類進(jìn)行劃分)

　　第1趟循環(huán)：

　　屬性a的值的個(gè)數(shù)為4個(gè)(分別為：1，2，3，4)，同時(shí)生成4個(gè)動(dòng)態(tài)隊(duì)列 　　Front[10]={X1，X3，X7，X10，X14}

　　Front[11]={X2，X4，X5，X8，X12}

　　Front[12]={X6，X9，X11}

　　Front[13]={X13，X15}

　　第2趟循環(huán)(即根據(jù)屬性b對(duì)等價(jià)類進(jìn)行劃分)

　　Front[10]生成2個(gè)動(dòng)態(tài)數(shù)組

　　Front[20]={X1，X3}， Front[21]={X7，X10，X14}分完釋放Front[10]占的空間

　　Front[11]，生成2個(gè)動(dòng)態(tài)數(shù)組

　　Front[22]={X2，X5}， Front[23]={X4，X8，X12}分完釋放Front[11]占的空間

　　Front[12]生成1個(gè)動(dòng)態(tài)數(shù)組

　　Front[24]= {X6，X9，X11} 同時(shí)釋放Front[12]占的空間

　　Front[13]生成1個(gè)動(dòng)態(tài)數(shù)組

　　Front[25]= {X13，X15} 同時(shí)釋放Front[13]占的空間

　　由上可知第2次循環(huán)共生成6個(gè)數(shù)組

　　即Front[20]={X1，X3}， Front[21]={X7，X10，X14}

　　Front[22]={X2，X5}， Front[23]={X4，X8，X12}

　　Front[24]= {X6，X9，X11}

　　Front[25]= {X13，X15}

　　第3次循環(huán)，同樣根據(jù)屬性c對(duì)第2次循環(huán)生成的各數(shù)組進(jìn)行劃分

　　由Front[20]劃分生產(chǎn)Front[30]= {X1，X3}，

　　由Front[21]劃分生產(chǎn)Front[31]= {X7，X10，X14}

　　由Front[22]劃分生產(chǎn)Front[32]= {X2，X5}，

　　由Front[23]劃分生產(chǎn)Front[33]={X4}，F(xiàn)ront[34]={X8，X12}，

　　由Front[24]劃分生產(chǎn)Front[35]= {X6，X9，X11}

　　由Front[25]劃分生產(chǎn)Front[36]= {X13，X15}

　　同時(shí)分別釋放掉Front[20]，F(xiàn)ront[21]，F(xiàn)ront[22]，F(xiàn)ront[23]，F(xiàn)ront[24]，F(xiàn)ront[25]所占的內(nèi)存空間

　　第4此循環(huán)，同樣根據(jù)屬性d對(duì)第3次循環(huán)生成的各數(shù)組進(jìn)行劃分

　　由Front[30]劃分生產(chǎn)Front[40]= {X1，X3}，

　　由Front[31]劃分生產(chǎn)Front[41]= {X7，X10，X14}

　　由Front[32]劃分生產(chǎn)Front[42]= {X2，X5}，

　　由Front[33]劃分生產(chǎn)Front[43]= {X4}，

　　由Front[34]劃分生產(chǎn)Front[44]= {X8，X12}，

　　由Front[35]劃分生產(chǎn)Front[45]= {X6，X9，X11}，

　　由Front[36]劃分生產(chǎn)Front[46]= {X13，X15}

　　同時(shí)釋放掉Front[30]，F(xiàn)ront[31]，F(xiàn)ront[32]，F(xiàn)ront[33]，F(xiàn)ront[34]，F(xiàn)ront[35]，F(xiàn)ront[36]

　　算法結(jié)束。

　　最終生成的數(shù)組

　　{X1，X3}，{X7，X10，X14}，{X2，X5}，{X4}，{X8，X12}，{X6，X9，X11}，{X13，X15}

　　就是U/{a，b，c，d}劃分所生成的等價(jià)類。

　　5 結(jié)束語

　　本文在研究徐章艷教授文獻(xiàn)[9]中等價(jià)類劃分算法的基礎(chǔ)上，給出了一個(gè)基于數(shù)組的等價(jià)類劃分算法。該算法在對(duì)屬性進(jìn)行比較排序的過程中逐漸逼近生成等價(jià)類，同時(shí)算法邊生成新數(shù)組邊釋放原數(shù)組所占的空間。因此新的等價(jià)類劃分算法能夠避免重復(fù)運(yùn)算以及節(jié)省空間開銷。算法的時(shí)間復(fù)雜度為O(|U||C|)，空間復(fù)雜度為O|U|.最后通過案例分析驗(yàn)證了算法的執(zhí)行過程。結(jié)果表明算法正確可行。

　　參考文獻(xiàn)：

　　[1] 王曉宇， 徐章艷， 張偉. 一種基于知識(shí)粒度單調(diào)性的屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2013， 31(11)： 38-41.

　　[2] 周建華， 徐章艷， 章晨光. 改進(jìn)的差別矩陣的快速屬性約簡(jiǎn)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2014， 35(4)： 831-835.

　　[3] 陳超， 陳性元， 永偉， 等. 基于粗糙集理論的冗余規(guī)則處理方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2014， 35(1)： 21-25.

　　[4] 王學(xué)恩， 韓崇昭， 韓德強(qiáng)， 等. 粗糙集研究綜述[J]. 控制工程， 2013， 20(1)： 1-5.

　　[5] 葛浩， 李龍澍，楊傳健. 基于Swapping 技術(shù)的啟發(fā)式屬性約簡(jiǎn)[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2014， 35(7)： 1620-1624.

　　[6] 周江衛(wèi)， 馮博琴， 劉洋. 一種新的快速求核算法[J]. 西安交通大學(xué)學(xué)報(bào)， 2007， 41(6)： 688-691.

　　[7] 趙軍， 王國胤， 吳中福. 一種高效的屬性核計(jì)算方法[J]. 小型微型計(jì)算機(jī)， 2003， 24(11)： 1590-1593.

　　[8] 劉少輝， 盛秋戩， 吳斌. Rough 集高效算法的研究[J]. 計(jì)算機(jī)學(xué)報(bào)， 2003， 26(5)： 524-529.

　　相關(guān)期刊簡(jiǎn)介：《科技信息》雜志是經(jīng)國家新聞出版署批準(zhǔn)、山東省科技廳主管、山東省技術(shù)開發(fā)服務(wù)中心主辦的國內(nèi)公開發(fā)行的旬刊雜志。國際標(biāo)準(zhǔn)刊號(hào)：ISSN1001-9960，國內(nèi)統(tǒng)一刊號(hào)：CN37-1021/N，郵發(fā)代號(hào)：24-72，是省級(jí)刊物、山東省優(yōu)秀期刊。