樊艷英++張自敏++陳冠萍

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

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

中圖分類號：TP18 文獻標志碼：A 文章編號：1009-3044（2016）01-0074-03

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

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

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

為進一步降低等價類劃分算法時間復雜度，減小空間開銷，提高等價類算法的執(zhí)行效率，我們在研究現(xiàn)有等價類劃分算法基礎上，提出了一種基于數(shù)組的等價類劃分算法。最后通過具體的案例驗證算法的正確性和高效性。

1 基本概念

定義1[4] 決策表

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

定義2[6] 等價類

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

IND（P）={（x，y）∈U×U，?a∈P |，f（x，a）=f（y，a）}

而IND（P）構成了U的一個劃分，用U/IND（P）表示，簡記為U/P， U/P的任何元素[x]p={y|?a∈P ，f（x，a）=f（y，a）}稱為等價類。

2 算法分析

徐章艷教授在文獻[9]中給出了鏈式基數(shù)排序算法（在本文稱之為算法1），經(jīng)研究發(fā)現(xiàn)該算法存在著重復運算現(xiàn)象。在第3步中，對論域U中的所有對象，按照每個屬性的取值進行歸類（即把在該屬性值上取值相等的實例歸為一隊），事實上這當中存在著重復運算。因為第i趟收集的隊列結果是可以作為下一趟（i+1）趟收集的基礎的。

下面用算法1對決策表進行等價類劃分，決策表如表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對決策表進行第一趟分配：

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趟分配依然是對論域U進行分配，結果如下：

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] .

后面的依次類推，也就是該算法每一趟的分配收集都是獨立進行的。事實上第i+1趟分配是可以再第i趟分配的基礎上進行的。

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

3 新算法描述

改進后的算法如下

算法2 一種改進的高效等價類劃分算法

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

輸出：對應的劃分U/C

步驟1 for（i=1，i

{ 步驟1.1 if i==1；

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

Else

步驟1.2

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

令T=1；

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

{ 步驟1.2.1 令P=T；

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

T=T+1；

令 L=length（arryj） //求數(shù)組arryj的長度

步驟1.2.2 For （M=1，M

{ 令E=0；

For（b=p，b

{ if （f（arryj[M]，ci）==f（arryb[0]，ci）） //如果arryj中第M個實例的屬性ci的取值與arryb數(shù)組中的第1個元素ci值相等 則把arryj中的第M個元素歸入arryb中，

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

}

If （e==0）

則創(chuàng)建一個新的動態(tài)數(shù)組arryT，同時把arryj中的第M個元素歸入新數(shù)組arryT中；

T=T+1； }}

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

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

4 算例分析

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

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

第1趟循環(huán)：

屬性a的值的個數(shù)為4個（分別為：1，2，3，4），同時生成4個動態(tài)隊列

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對等價類進行劃分）

Front[10]生成2個動態(tài)數(shù)組

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

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

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

Front[12]生成1個動態(tài)數(shù)組

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

Front[13]生成1個動態(tài)數(shù)組

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

由上可知第2次循環(huán)共生成6個數(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對第2次循環(huán)生成的各數(shù)組進行劃分

由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}

同時分別釋放掉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]所占的內存空間

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

由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}

同時釋放掉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]

算法結束。

最終生成的數(shù)組

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

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

5 結束語

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

參考文獻：

[1] 王曉宇， 徐章艷， 張偉. 一種基于知識粒度單調性的屬性約簡算法[J]. 計算機應用與軟件， 2013， 31（11）： 38-41.

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

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

[4] 王學恩， 韓崇昭， 韓德強， 等. 粗糙集研究綜述[J]. 控制工程， 2013， 20（1）： 1-5.

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

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

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

[8] 劉少輝， 盛秋戩， 吳斌. Rough 集高效算法的研究[J]. 計算機學報， 2003， 26（5）： 524-529.

[9] 徐章艷， 劉作鵬， 楊炳儒. 一個復雜度為max（O（|C|| U|）， O（|C| 2|U/C|））的快速屬性約簡算法[J]. 計算機學報， 2006， 29（3）： 391-399.