粗糙集的规则获取方法在远程教育算法中的实现研究

杨慧 丁正生

【摘 要】

粗糙集理论被广泛应用于不确定环境下不确定或不相容数据的信息处理和规则获取。本文研究了基于粗糙集的规则获取方法，结合线性搜索和排序方法，实现了远程教育算法DLA（Distance Learning Algorithm），对现代远程教学实践有普遍的指导意义。

【关键词】 粗糙集；规则获取；属性约简；远程教育算法；识别指数

【中图分类号】 G40-057 【文献标识码】 A 【文章编号】 1009—458x（2015）08—0053—05

一、简介

计算机和网络技术的普及，为教育事业提供了更加优越的硬件和软件，计算机和网络技术正逐步应用和渗透到以教师讲授为基础的传统课堂上，并潜移默化地改变着互动性低的传统教学模式，逐步形成了依附于互联网技术的开放式、互动式教学模式，即远程教育模式。现代远程教育的开展和普及，是实现终身学习的重要途径。

粗糙集（Rough Sets）理论是1982年最先由波兰数学家Z. Pawlak提出的一种分析数据的数学理论和方法，被广泛应用于处理不确定、不精确性问题和不相容数据。粗糙集理论将知识看作是关于论域的划分， 并根据近世代数学中的等价关系来分析和研究知识，模糊性和不确定性的概念也是在知识分类的基础上定义的。自粗糙集理论被提出后，其逐步渗透到人工智能、数据挖掘、机器学习和模式识别等研究领域 [1][2][3]。

远程教育已成为改革传统教育模式的动力和有效手段，也是教育改革的研究重点[4]。针对目前远程教育中个性化教学水平较低的问题，有学者提出了一种基于粗糙集的Web学习者聚类算法，并应用粗糙集的约简方法解决了学习者特征数据中的属性冗余问题，但对由不相关属性（冗余属性）引起的误导现象十分敏感[5]。聚类算法为远程教育中学生的个性特征及学习状态评估提供了一种有效的评价手段，可以根据聚类分析结果给出针对性的辅导与学习策略。传统的K均值聚类算法在初始聚类中心选取上具有随机性，且聚类具有不确定性和时间复杂度较高的缺点[6]。利用网格聚类的思想对K均值聚类算法进行改进，可以克服K值随机性带来的不确定性以及传统网格聚类方法造成的簇丢失缺陷。

远程教育的推广过程和研究过程，依然面临着很多挑战。一方面，远程学习者海量的在线测验数据需要处理；另一方面，现有的课程教授模式使在线学生和教育者之间缺少联系和信息回馈的问题越来越凸显。针对这两个问题，很自然地可以联想到粗糙集理论中很重要的研究领域——数据约简和规则获取。在包含海量数据的信息系统中，很多属性信息对于规则的提取都是多余的，如果能将冗余的属性和信息删除，则信息系统的潜在知识清晰度和运行效率都可以得到大幅提高；而粗糙集理论中的数据约简可以将原始信息表的冗余数据和信息通过给定的算法消去，得到一个约简，然后从这个约简后的信息系统中提取有效的决策规则[7][8]。因此，可以用粗糙集的规则获取方法，解决远程教育的上述两个问题。针对这两个问题，本文重点研究了如何用结合粗糙集理论的决策树来建立一个约简信息表，剔除冗余信息，得到决策规则，进一步研究远程教育算法DLA[9]的实现，可以让通过远程教育进行网上学习者评估课程的重点章节，教育者也能对课程内容安排做相应的调整。

二、粗糙集的基本概念

粗糙集是一种处理含糊和不确定性问题的数学工具[10]。给定一个有不同属性的对象集为[U=x1，x2，…，xn]的信息表，可以分别按照条件属性、决策属性进行分类。每一个基于决策属性的等价类定义了一个概念。我们使用[Des（Xi）]来表示等价类[Xi]的描述，即描述属性集[Xi]的属性值集合。

[Y]是一个概念，定义其下近似[Y]和上近似[Y]如下：

[Y=e∈Ue∈Xi且Xi⊆Y]

[Y][=e∈UE∈Xi且Xi Y≠ϕ]

如果一个元素属于[Y]-[Y]，则不能确定它是否在[Y]中，因此引入一个[Y]的判别式指标的概念来度量[U]中的这个元素属于[Y]的程度[11]，其定义如下：

[αQ1（Y）=1-Y-YU]

对于给定的信息表，并不是所有的属性都是分类所必需的，条件属性存在一个最小子集，得到这个最小子集的过程就是一个计算约简的过程。

设[S=（U，A）]是一个信息系统，其中[U]为对象集，[U=x1，x2，…，xn]，[A]为属性集，[A=a1，a2，…，ap]，对[a∈A]，如果[IND（A-a）=IND（A）]，则称属性[a]在[A]中是不必要的（多余的），否则称属性[a]在[A]中是必要的。

若每个属性[a∈A]在[A]中都是必要的，则称属性集[A]是独立的，否则称它为依赖的，可以对其约简。在本文中应用了相对约简的方法[12]。

给定[P]和[Q]为[U]中的等价关系，定义[Q]的[P]正域[posp（Q）]如下：

[posp（Q）=X∈U/QPX]

由定义可以看出，[Q]的[P]正域是由所有的根据分类[U]/[P]的信息被准确地分到关系[Q]的等价类中去的对象组成的集合。针对决策信息系统，重点研究条件属性关于决策属性的正域。

三、远程教育算法DLA

远程教育算法DLA在评估某一个课程的各部分内容的重要性方面，着重于一个概念，即[Des（Y）=Fail]，即想要找出是什么导致了在线学生不能通过考试，从而为教学双方提供及时和有效的反馈，将粗糙集的属性约简融入算法中，可归纳为以下5步：

1. 对决策表中的原始数据进行预处理；

2. 利用粗糙集算法，进行属性约简，得到条件属性关于决策属性的约简；

3. 初始化变量，只要条件属性的个数不为零，那么进行下一步；

4. 执行当型循环。在当型循环中先计算条件属性的判别式指标，将最高的指标值存入结果，且这个条件属性从条件属性集中移去。之后，输出决定性的或非决定性的决策规则，从而决定一个新的论域。照此循环下去，直到新的论域变成空集，则执行下一步；

5. 输出所有决定性和非决定性的决策规则[13][14]。

四、远程教育算法DLA的实现

WebCT（Web Course Tools）[15]是由加拿大英属哥伦比亚大学的计算机科学系为高校开发的异步课程传递及管理系统，包括一系列可以自动与课程内容紧密集成的强大学习工具。 学生做作业、进行小测验和期末考试都在互联网上进行。 如果某个学生未通过期末考试，需要进行重修，此时，学生会关心哪些章节比较薄弱，在下一轮重修中应该将主要精力放在哪些内容上，课程教授者也可以据此调整课程内容。 本文以利用WebCT系统进行某一门课程学习的数据库作为实例， 研究粗糙集的属性约简和规则获取算法如何在远程教育算法DLA中实现，从而辅助教学双方更有效地进行远程教学和学习。 数据库见表1，其中有145名学生、6次小测验和1次期末考试。

利用粗糙集理论，将数据库中各次小测验成绩作为条件属性，将期末考试成绩作为决策属性，可以先对属性进行约简，找出决策属性的关键条件属性， 即对期末成绩起决定作用的小测验， 进而得到小测验所对应的相关章节即为学生学习的重点。 最后由属性约简后的数据表导出所有的决策规则，为新学生的学习提供反馈指导的同时，课程教授者也可以相应调整教学资源。以下为利用粗糙集对DLA算法实现的过程：

1. 对信息表进行预处理，学生关心这门功课是否及格，因此可以把表1进行如下处理：用P表示Pass， 即成绩大于等于60分；F表示Fail， 即成绩低于60分。将情况相同的学生归为一类，由此得到一个简单表（表2）。将原有的145条记录分成了八类，表中的学生总人数变成了113，另外29名在每次小测验都通过的学生，期末成绩逻辑上应该是Pass，3名在每次小测验中都没有通过的学生，他们的期末成绩逻辑上应该是Fail， 因此不做考虑。

2. 约简。以各次小测验成绩为条件属性，以期末成绩为决策属性，进行属性约简，本质上是要剔除掉对于决策属性为冗余的条件属性。 为了实现这一步，用粗糙集理论结合线性搜索和排序方法来完成。 以表2为例，所有属性的集合

[R=Q1，Q2，Q3，Q4，Q5，Q6，Final]

[R]的正域为[POSR（F）=e1，e2，e3，e4，e5，e6，e7，e8]

为了计算[R]关于[Final]的约简，需要研究[R]是否是[F-]独立的。 使用当型循环分别移去[Q1]、[Q2]、[Q3]、[Q4]、[Q5]和[Q6]来检验其正域，如果每次小测验的正域不等于期末考试的正域，我们保留这个条件属性，以下是部分运算结果：

[POSR-Q1（F）=e1，e2，e3，e4，e5，e6，e7，e8=POSR（F）]

[U/IND（R-Q1）=e1，e7，e2，e3，e4，e5，e6，e8]

……

[U/IND（R-Q6）=e1，e7，e8，e2，e3，e4，e5，e6]

[POSR-Q6（F）=e1，e6，e7，e8≠POSR（F）]

由以上运算可以得出结论：[e3]、[e5]、[e6]是不可少的，因为其正域不等于[Final]的正域。 由此，信息表简化为表3。

3. 找出决策规则。 根据约简后的信息表，可以看出：

论域：[U=e1，e2，e3，e4，e5，e6，e7，e8]

失败范畴：[Y=e2，e3，e5，e6]

基于[Quiz3]的不可识别类是：

[Y1=e1，e6，e7，e8] [Des（Y1）=Quiz=P]

[Y2=e2，e3，e4，e5] [Des（Y2）=Quiz=F]

下近似[Y=] 上近似[Y=e1，e6，e7，e8，e2，e3，e4，e5]

识别指标：[αQ3=1-Y-YU=0.00]

同样，计算[Q5，Q6]的[α]指数，可以得到表4。

可以看出，[Quiz6]的识别值最高。也就是说，它最能决定一个成员是在范畴[Y]中的。因此，得到如下决策规则：

[Rule 1：Quiz6=F⇒Final=F]

从而以[Q6]为根节点的决策树[16]为：

[Q6]

[e1：P；e4：P；e7：P] [e2：F；e3：F；e5：F；e6：F；e8：F]

基于决策树，[Q6]取[F]值的新的约简表为表5。

不难看出[Q6]和[Q3]，具有较高的识别指数，因此得到第2条规则：

[Rule2：Quiz6=F，Quiz3=F⇒Final=F]

其对应的决策树如下所示：

[Q6]

[e1：P；e4：P；e7：P] [e2：F；e3：F；e5：F；e6：F；e8：F]

[Q3]

[e6：F；e8：P] [e2：F；e3：F；e5：F]

运用相同的方法可以得到：

[Rule3：Quiz6=F，Quiz5=F⇒Final=F]

以上的约简过程得出了3条决策规则。为了度量以上决策规则的可信度，引入分类强度[17]的概念对规则的可信度进行度量，可以用以下公式来计算：

[W=规则所覆盖的正例子规则所覆盖的例子（既包含正的，也包含负的）]

为了实现最后一步计算，再一次利用线性搜索，各规则的强度计算如表7。

表7 决策规则强度值表

[Rules＼&强度值W＼&[Rule1：Quiz6=F⇒Final=F]＼&56.52%＼&[Rule2：Quiz6=F，Quiz3=F⇒Final=F]＼&100.0%＼&[Rule3：Quiz6=F，Quiz5=F⇒Final=F]＼&100.0%＼&]

表7可以解释，如果一个在线学习的学生在小测验[Quiz6]中没有通过，那么该学生期末考试将有56.52%的可能不能通过；如果一个学生在[Quiz6]和[Quiz3]中都没有通过考试，那么该学生100%不能通过期末考试。 利用粗糙集理论进行数据约简，并获得决策规则的过程，可以通过对以往在线学习的学生的表现分析，为后来学习同一门网络课程的学生提供指导。

基于粗糙集的规则获取算法比WZY算法[18]更适用于WebCT远程教育系统， 二者的区别在于WZY算法不会输出非决定性规则，如本文中的[Rule1]， 而本文基于粗糙集的规则获取算法， 决定性规则和非决定性规则都会输出。 这些规则能告诉学生在线学习的重点章节。 此外，WebCT只关心决策属性的一个概念，即Fail，WZY算法则覆盖多个概念，因此计算起来复杂度较基于粗糙集的规则获取算法更高。

最后，针对算法的扩展性问题，基于粗糙集理论给出增量规则获取算法的步骤：

1. 当有新样本加入时，首先检查它们是否与已有的规则集相容，是否能被已有规则集包含。如果相容且被包含，则规则集无须修正；如果相容但不被包含，则直接将新样本加入规则样本表，并用本文的算法约简带通配符的决策表；如果不相容，则转入下一步。

2. 在规则样本表里找到导致不相容的规则样本及其对应的实验样本的序号，将这些实验样本数据从原始决策表中取出来代替该规则样本，然后结合新加入的实验样表，得到带通配符的决策表，最后再利用本文的方法再次约简这个决策表。

利用已有的规则获取算法，将实验样本合并后提取为规则样本，以此代替原始决策表中的海量数据，并借助通配符进行约简，可以大大减少待约简的数据规模，提高了规则修正的效率。

五、 结论

本文通过运用粗糙集实现远程教育算法，对远程教育学习过程中的冗余数据进行了约简，获取了决策规则，并利用可信度对规则的强度进行了度量，克服了远程教育系统WebCT的信息反馈缺失问题。 一方面，参加远程教育的学习者根据历史经验，重点学习某一门课程的关键章节；另一方面，也可以让教育者就某些重要部分，对网站上的课程安排、教学内容设计等做出相应的调整，使网上的资源更加适应学习的要求，也更能反映出某门在线课程的重点和难点。 文中的结论不仅适用于互联网上的远程教学，也适用于实际教学中，能给教师提供直接的教学反馈。

与传统的规则获取算法不同，本文的规则获取算法，在数据库更新时，无须在原有的数据库内部重新进行属性约简及规则获取，在减少待约简的数据规模的同时，提高了规则修正的效率。 然而，针对原有决策表中含有不完全数据或者冲突样本的情形，如何对文中算法进行改进，有待进一步研究。

[参考文献]

[1][12] 张文修. 粗糙集理论与方法[M]. 北京：科学出版社，2001.

[2][7][10] 植小三，印勇，黄杨帆. 基于粗糙集理论的一种数据约简算法[J]. 云南民族学院学报（自然科学版），2003，12（2）：86-88.

[3][8][11] 艾丽军，占传杰，熊镇山. 基于Rough集实现判定树归纳分类算法的简化[J]. 盐城工学院学报（自然科学版），2004，17（3）：86-88：30-33.

[4] 温泉，江美英，覃俊. 远程教育中基于粗糙集的聚类算法[J]. 中南民族大学学报（自然科学版），2007，26（1）：84-88.

[5] 张德洪. 远程教育系统设计中的自动组卷算法研究[J]. 赤峰学院学报，2010，26（12）：45-47.

[6] 张晓芳. 聚类分析算法在远程教育系统中的应用研究[J]. 科技通报，2013，29（4）：106-109.

[9][15] Hongyan Geng and Maguire. A Rough Set Methodology to Support Learner Self-Assessment in Web-Based Distance Education， Rough sets， fuzzy sets， data mining， and granular computing ： 9th international conference， Berlin ； New York ： Springer， 2003.

[13][18] A. H. Liang， B. Maguire， and J. Johnson. Rough Set Based WebCT Learning. Proceeding of the 1st International conference on Web-Age Information Management， Shanghai， P. R. China， June 21-23， 2000. Springer-Verlag LNCS 1846.

[14] S.K.M. Wong， W.Ziarko， and R.L.Ye. Comparison of rough-set and statistical methods in inductive learning . International Journal of Man-Machine Studies， 1986， 24：52-72.

[16] 翟俊海，翟梦尧，李胜杰. 基于相容粗糙集技术的连续值属性决策树归纳[J]. 计算机科学，2012，39（11）：183-186.

[17] Yao Yu， Fu Zhong-liang， Zhao Xiang-hui，Cheng Wen-fang. Combining Classifier based on Decision Tree. 2009 WASE International Conference on information Engineering. 2009： 37-40.

收稿日期：2014-10-15

定稿日期：2015-05-13

作者简介：杨慧，在读博士，讲师；丁正生，教授。西安科技大学（710054）。

责任编辑 日 新