一种基于数组的高效等价类划分算法

樊艳英++张自敏++陈冠萍

摘要：粗糙集理论是建立在等价类的基础上的，等价类划分算法的优劣会直接影响到属性约简和规则提取的效率.针对等价类基数排序算法中存在重复计算和空间开销较大的问题，提出了一种基于数组的等价类划分算法. 算法的时间复杂度为O（|U||C|），空间复杂度为O|U|.最后通过具体案例验证了算法的执行过程。结果表明算法高效且正确可行。

关键词：粗糙集；属性约简；等价类划分；基数排序；规则提取

中图分类号：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提出的，该理论是一种处理不完备、不精确和不确定知识的数学工具[1]。跟其他处理不精确，不完备，不确定的理论相比，粗糙集无需其他先验知识，只需要提供其所处理的数据集，即可对这些数据进行推理，分析，和处理.正是由于粗糙集有这些方面的优势，引起了国内外科学家的关注，并致力于粗糙集的研究和应用推广.目前，粗糙集在社会很多领域的应用都取得了很好的效果.属性约简是粗糙集研究的重要内容之一[2]。属性约简就是在保持数据库分类能力不变的条件下删除其中不重要和不相关的数据[3]。

通常粗糙集进行属性约简要判断数据分类能力是否发生变化是建立在计算等价类的基础上的，因此求等价类的算法的优劣是影响后续属性约简或规则提取算法效率的重要因素之一.因此设计出低空间复杂度和时间复杂度的等价类划分算法是一件值得探索的工作.

目前不少专家学者对等价类都进行了深入研究[5].同时提出了很多种等价类划分算法。赵军[7]采用了快速排序法划分等价类U/C，其时间复杂度为O（ | C ||U| log |U| ） 。刘少辉等人在文献[8]还进一步研究了正区域的渐增式计算方法，由此设计了完备的属性约简算法，该算法时间复杂度为O（ | C| 2 |U| log | U | ） 。徐章艳等人在文献[9]对等价类划分算法进行改进，采用链式基数排序算法划分等价类U/C，其时间复杂度为O（ | C| |U| ） .

为进一步降低等价类划分算法时间复杂度，减小空间开销，提高等价类算法的执行效率，我们在研究现有等价类划分算法基础上，提出了一种基于数组的等价类划分算法。最后通过具体的案例验证算法的正确性和高效性。

1 基本概念

定义1[4] 决策表

一个信息表可以表示为S=，其中U是论域，C是条件属性集，D是决策属性集，V= 是属性的值域，其中，Va是属性a的值域，f： U×（∪DC∪D）→V是信息决策表函数。当D≠?时，该信息表示一个决策表。

定义2[6] 等价类

每一个属性子集P?∪D?C∪D 决定了一个二元不可区分关系

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]中给出了链式基数排序算法（在本文称之为算法1），经研究发现该算法存在着重复运算现象。在第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]，FR[ 2]，FR[ 3]进行同样的操作。以此循环，当比较完最后一个属性时，事实上就已经完成了等价类的划分。整个执行过程类似于一棵树的生产过程.也就是说实际上我们只要对算法1中的步骤3进行改进，在第3步循环完后即可生成所需的等价类。无需再进行后续的步骤4，步骤5.因此改进后的算法复杂度更加低，算法更简单。

3 新算法描述

改进后的算法如下

算法2 一种改进的高效等价类划分算法

输入：决策表S=U={u1，u2，u3……un}，

输出：对应的划分U/C

步骤1 for（i=1，i

{ 步骤1.1 if i==1；

执行第一趟划分：求第1个属性的值的个数K，并创建K个动态数组，根据第1个属性值分别把各实例放入相应的数组中；

Else

步骤1.2

设由第i-1趟分配所产生的数组序列为：arry1，arry2，arry3……arryk；

令T=1；

For each arryj （j=1，2，……k） //对上一趟产生的任意数组执行以下操作

{ 步骤1.2.1 令P=T；

创建数组arryt；同时把 arryj的第一个元素放入arryt中；

T=T+1；

令 L=length（arryj） //求数组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数组中的第1个元素ci值相等 则把arryj中的第M个元素归入arryb中，

令e=1，终止循环，转步骤1.2.2

}

If （e==0）

则创建一个新的动态数组arryT，同时把arryj中的第M个元素归入新数组arryT中；

T=T+1； }}

释放 数组arryj所占空间；}

算法分析：该算法在对每个对象属性值的比较过程中，逐步逼近生成等价类，在最后一个属性进行比较排序的过程中，实际上也就完成了对等价类的划分。同时在对某一个数组进行划分完毕后，立刻释放该数组所占空间，这样就减少了空间开销。该算法解决了文献[9]对属性进行比较过程中的重复运算问题以及产生空队列的问题。因此算法相对于文献[9]的效率会更高些（相当于无需执行文献[9]的第4，5步）。该算法的时间复杂度为O（|U||C|），空间复杂度为O|U|.

4 算例分析

我们同样以文献[9] 中的决策表（表1）为例说明该算法计算U/{a，b，c，d}的过程。

进入算法执行for的第一次循环（即根据属性a对等价类进行划分）

第1趟循环：

属性a的值的个数为4个（分别为：1，2，3，4），同时生成4个动态队列

Front[10]={X1，X3，X7，X10，X14}

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

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

Front[13]={X13，X15}

第2趟循环（即根据属性b对等价类进行划分）

Front[10]生成2个动态数组

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

Front[11]，生成2个动态数组

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

Front[12]生成1个动态数组

Front[24]= {X6，X9，X11} 同时释放Front[12]占的空间

Front[13]生成1个动态数组

Front[25]= {X13，X15} 同时释放Front[13]占的空间

由上可知第2次循环共生成6个数组

即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次循环，同样根据属性c对第2次循环生成的各数组进行划分

由Front[20]划分生产Front[30]= {X1，X3}，

由Front[21]划分生产Front[31]= {X7，X10，X14}

由Front[22]划分生产Front[32]= {X2，X5}，

由Front[23]划分生产Front[33]={X4}，Front[34]={X8，X12}，

由Front[24]划分生产Front[35]= {X6，X9，X11}

由Front[25]划分生产Front[36]= {X13，X15}

同时分别释放掉Front[20]，Front[21]，Front[22]，Front[23]，Front[24]，Front[25]所占的内存空间

第4此循环，同样根据属性d对第3次循环生成的各数组进行划分

由Front[30]划分生产Front[40]= {X1，X3}，

由Front[31]划分生产Front[41]= {X7，X10，X14}

由Front[32]划分生产Front[42]= {X2，X5}，

由Front[33]划分生产Front[43]= {X4}，

由Front[34]划分生产Front[44]= {X8，X12}，

由Front[35]划分生产Front[45]= {X6，X9，X11}，

由Front[36]划分生产Front[46]= {X13，X15}

同时释放掉Front[30]，Front[31]，Front[32]，Front[33]，Front[34]，Front[35]，Front[36]

算法结束。

最终生成的数组

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

就是U/{a，b，c，d}划分所生成的等价类。

5 结束语

本文在研究徐章艳教授文献[9]中等价类划分算法的基础上，给出了一个基于数组的等价类划分算法。该算法在对属性进行比较排序的过程中逐渐逼近生成等价类，同时算法边生成新数组边释放原数组所占的空间。因此新的等价类划分算法能够避免重复运算以及节省空间开销。算法的时间复杂度为O（|U||C|），空间复杂度为O|U|.最后通过案例分析验证了算法的执行过程。结果表明算法正确可行。

参考文献：

[1] 王晓宇， 徐章艳， 张伟. 一种基于知识粒度单调性的属性约简算法[J]. 计算机应用与软件， 2013， 31（11）： 38-41.

[2] 周建华， 徐章艳， 章晨光. 改进的差别矩阵的快速属性约简算法[J]. 小型微型计算机系统， 2014， 35（4）： 831-835.

[3] 陈超， 陈性元， 永伟， 等. 基于粗糙集理论的冗余规则处理方法[J]. 计算机工程与设计， 2014， 35（1）： 21-25.

[4] 王学恩， 韩崇昭， 韩德强， 等. 粗糙集研究综述[J]. 控制工程， 2013， 20（1）： 1-5.

[5] 葛浩， 李龙澍，杨传健. 基于Swapping 技术的启发式属性约简[J]. 小型微型计算机系统， 2014， 35（7）： 1620-1624.

[6] 周江卫， 冯博琴， 刘洋. 一种新的快速求核算法[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.