窦慧莉，宋晶晶

（江苏科技大学 计算机学院，江苏 镇江 212100）

0 引言

属性约简［1-2］是一种基于粗糙集［3-4］的特征选择方法，在机器学习等众多领域中又被称为属性降维。一般而言，属性约简这一概念适用于各种类型的粗糙集模型，其目的是获得满足给定约束条件的最小属性子集。作为一种数据预处理方法，属性约简可以从数据中筛选有竞争力的属性，为后续的学习任务带来理想的泛化能力。

为了进一步将属性约简推向实用，约简的搜索效率［5-6］一直是众多学者关心的问题。已有研究大多是从样本的视角出发，利用粗糙集方法中相关度量本身的单调性结构［7-8］，通过不断减少约简搜索进程中所需扫描的样本，来达到快速求解约简的目的。然而，这种策略忽略了数据中隐含的属性结构信息。针对这一问题，本文提出一种基于模糊粗糙集的快速约简求解方案。模糊粗糙集模型［9-10］能够更为精准地利用样本间的相似度刻画样本的信息粒化结果，更适合处理实际工程中广泛存在的连续型数据，采用模糊粗糙集进行约简求解，并利用参数依赖的高斯核函数来计算样本间的相似度，有助于实现多粒度视角下的数据分析。与样本层面的加速机制相比，本文所提方法是从数据的属性层面出发，通过计算属性间的相似度，揭示属性内在的结构信息，进而利用该信息减少算法执行过程中所需遍历的属性个数，实现属性的快速降维。

本文提出的基于模糊粗糙集的属性约简这一降维方法在实际应用中具有独特的优势，该方法无须数据以外的任何先验知识，能够直接根据模糊粗糙相关度量准则，对实际问题中的各项指标进行重要度评估，进而依据约简的定义，挑选出比较重要的指标。对于高校课程考核管理来说，课程是支持学生毕业要求达成和能力培养的基本单元，课程目标达成度评价贯穿人才培养的始终，同时也是衡量学生是否达到本专业毕业要求的重要依据。在现有的课程考核管理体系中，考核指标（可视作粗糙集方法中的“属性”）日趋复杂，同时，积累了大量的原始课程数据。从这些数据中筛选出有效的考核指标，为课程教学质量的提升提供客观的辅助性决策也是教育大数据挖掘的一项重要任务。利用本文提出的基于模糊粗糙集的快速约简求解方法能够帮助管理人员挑选出对于课程目标达成度的考核结果影响比较大的指标，这对于工程教育专业认证、本科教学合作评估等工作有着至关重要的参考意义。

1 模糊粗糙集模型与约简算法

对于一个分类任务，利用决策属性d可以定义一个二元关系INDd=｛（x，y）∈U×U：d（x）=d（y）｝，表示论域U 上根据决策属性 d所得到的等价关系，据此可诱导出论域U上一个形如U/INDd=｛X1，X2，…，Xq｝的划分，其中Xp∈U/INDd是第p个由具有相同标签的样本构成的决策类。

在分类任务中，决策属性d上的取值一般是符号型的，而条件属性上的取值却往往是连续甚至是混合型的，此时等价关系不再适用。鉴于此，已有学者从样本间相似性出发，设计了形式多样的模糊关系［11-13］，并通过构造模糊粗糙集模型进行数据分析。在这些模糊关系中，基于高斯核函数的模糊关系使用非常广泛。给定一个决策系统DS，∀B⊆ AT，∀x，y∈U，可以使用高斯核函数［14］来计算样本x与y之间的相似度：

其中，||x-y||B表示样本x与y之间的欧氏距离，σ是一个高斯核参数。

定义3中的约简是一个能够保证模糊粗糙依赖度不被降低的最小条件属性子集。为了求得定义3中的约简，目前已经涌现出了很多不同类型的搜索策略［15-18］，其中，启发式方法因迭代速度较快而受到了广泛关注。将定义2中的模糊粗糙依赖度作为启发式信息，可给出如下属性重要度定义。

在定义 4 中，若 Sigσ(a，B，d)的值越高，则表明属性a越重要，越应该被加入约简池，即此时a越应被选中，从而成为约简的组成部分。

2 基于模糊粗糙集的快速降维方法

属性约简的时间效率是衡量约简算法质量的重要标准之一。传统的启发式贪心搜索在最坏的情况下，需要遍历n（n+1）/2次属性（n为条件属性个数）。然而实际上，这其中有许多遍历是冗余的，会带来不必要的时间消耗。例如，在算法执行过程中，若候选属性与已选属性具有较高的相似度，此时，再将候选属性加入约简池中，并不会带来模糊相似关系的显著变化，也就是说加入这类属性后，模糊粗糙依赖度的改变幅度相当有限。

为了减小遍历属性的时间消耗，本文将以条件属性间的相似度为切入点，对条件属性进行预先分组。这样，在搜索进程中，只需要考察那些与约简池中的属性不在同一组中的属性，就可以大大减少需要遍历的属性个数。与传统的启发式贪心搜索算法相比，本文算法在每一轮迭代进程中不需要遍历每一个候选属性，而是以属性的分组为遍历的基本单位，进行属性筛选。具体算法流程见算法1。

假设m表示论域中的样本数，n表示条件属性个数。设条件属性被分成l组（1≤l≤n），每组的属性个数为N1，N2，…，Nl，则在最坏情况下，算法1需要遍历属性的个数为m+（m-N1）+（m-N1-N2）+…+1，这显然少于传统的启发式贪心搜索算法在最坏情况下所需的遍历次数。

3 数据分析及测试

为了全面验证本文所提方法的合理性及有效性，本节将从两个不同的视角进行数据层面上的分析。首先，面向工程教育专业认证这一重点工作中的课程目标达成度考核问题，利用所提算法的降维策略，对课程考核的过程性指标进行筛检，从而找出对课程考核至关重要的指标，以体现算法的合理性。其次，将所提算法与一些流行的属性约简算法在公开数据集上进行对比分析，来检验方法的有效性。

3.1 实例分析

在高校的教务管理数据库系统中，课程成绩数据具有复杂性高、规模庞大等特点。每门课程由于所在专业不同，对应的考核点与目标也不尽相同，这给课程目标达成度的考核工作带来了极大挑战。

通过多年的经验积累以及对高校教务数据的持续跟踪，可以发现在课程目标达成度分析这一实际工作任务中，并非所有考核指标对于达成度的分析都是积极有效的。换言之，从庞杂的数据库系统中，挖掘出那些有效的考核指标，不仅可以极大减少数据的存储规模，而且有望为后续达成度分析报告的形成提供坚实的历史参照。

表1统计了江苏科技大学2020级人工智能专业中10门核心课程及10个考核指标的评价值，这些数据来源于问卷调查、座谈交流、督导专家评价三种盲评方式，每一项评价值都是三种评价方式对应评价值的加权平均，三种评价方式的权重分别为30%，20%和50%，最终得分以百分制记录。问卷调查来源于专业中60名学生的访问调查，取学生的平均打分值；座谈交流来源于教学中期检查的评价结果；督导专家评价来源于学校和学院共10名专家的平均评价结果，是建立在课堂教学录像回放与教学资料检查基础上而得出的。

具体课程包括：离散数学（课程1）、数据结构（课程2）、矩阵理论与应用（课程3）、操作系统（课程4）、计算机组成原理（课程5）、最优化理论与算法（课程6）、数据库原理及应用（课程7）、编译原理（课程8）、粒计算理论与方法（课程9）、数字图像处理与计算机视觉（课程10）；具体考核指标包括：学生评教（指标1）、考试命题（指标2）、平时作业（指标3）、题库建设（指标4）、综合作业（指标5）、成绩评定（指标6）、课内实践（指标7）、课外实践（指标8）、课堂管理（指标9）、创新能力（指标10）。最终的“考核结果”源于学院和学校督导组专家的综合评定。

显然，表1中所示的数据都是以百分制记录的，可以视作是连续值，此时可采用基于高斯核函数的相似度来计算课程间的相似度，因此定义1所示的模糊粗糙集模型可以用于分析如表1所示的数据。

从粗糙集的视角对表1进行分析时，可将不同的课程视作不同的样本，将不同指标视作不同的条件属性，将考核结果视作决策属性。下面，使用算法1对表1进行降维分析和求解。

表1 课程考核达成度指标Table 1 Achievement index of course examination

（1）首先，基于10门课程在所有考核指标上的评价值，计算模糊粗糙依赖度，所得结果为0.923 1。

（2）其次，根据这10门课程在所有考核指标上的评价值，计算不同考核指标之间的相似度，从而实现对考核指标的分组。此处采用K-means聚类算法，将考核指标划分到不同的组中。经过计算，分组情况为：G1=｛指标1，指标4，指标7｝，G2=｛指标2，指标3，指标5，指标8，指标9｝，G3=｛指标6｝，G4=｛指标10｝。

（3）计算不同课程间的模糊相似关系，并以此为基础计算“考核结果”对每个指标的模糊粗糙依赖度。经过计算，“考核结果”对每个指标的模糊粗糙依赖度分别为：0.031 6，0.103 2，0.060 4，0.034 0，0.042 4，0.051 8，0.058 6，0.063 1，0.075 3，0.073 2。根据算法1中的步骤4），指标2被选中，说明在课程目标达成度的考核工作中，考试命题这一指标是至关重要的。

（4）因为所得到的模糊粗糙依赖度显然小于原始模糊粗糙依赖度0.923 1，所以需要继续选择相应的考核指标。需要注意的是，在继续选取考核指标时，不再遍历“指标2”所在的组（即G2）中的其他指标，而是从其余组中遍历其他指标，以此类推，直至满足约简的约束条件。

（5）利用算法1，不断迭代地进行搜索，最终指标2、4、5、6依次被选中。这一结论说明对于这10门课程来说，考试命题、题库建设、综合作业、成绩评定这4个指标对于课程目标达成度的考核结果的影响是比较重要的。

上述结论从一个侧面反映了目前对于教师课程考核时存在的一个倾向性问题，即考核结果的达标程度大多依赖于与学生成绩紧密关联的一些指标，却往往忽略了实践、创新能力等灵活性较大的指标。

值得说明的是，利用模糊粗糙集这一工具对课程考核数据进行分析，属于教育大数据背景下一个较为新颖的尝试，为分析的简便起见，这一实例中仅仅将考核结果粗略地划分为“合格”与“基本合格”。若考核结果为6级计分制或其他更为复杂的形式，即数据的监督信息表现为多类，此时模糊粗糙集方法依然适用。

3.2 对比分析

为了验证所提算法相较于其他先进算法的有效性，本小节选取了8组UCI数据集，进行实验对比分析，数据集的具体情况如表2所示。

表2 数据集描述Table 2 Description of data sets

在本组实验中，分别选择0.01，0.02，0.03，…，0.20共20个不同的高斯核函数参数进行测试。同时，使用10折交叉验证方法［19］进行约简求解，并对比了4种算法：基于传统模糊粗糙集的约简求解［20］，基于邻域粗糙集的约简求解［21］，基于集成选择器的约简求解［22］，基于知识变化率的约简求解［23］。最后，给出不同约简搜索所需的时间消耗、约简结果的分类性能。在利用所提算法对属性进行分组时，K-means算法中设置K=3。

3.2.1 时间消耗对比

在实验比对时，为确保公平性，5种算法均遵循以下步骤：使用10折交叉验证方法在训练集中搜索约简，记录相应的时间消耗，并计算其平均值。表3是5种算法的平均时间消耗情况，时间消耗最短的用粗体表示。

观察表3，不难得出以下结论：

表3 不同算法求解约简的平均时间消耗对比（秒）Table 3 Time consumption of different algorithms for deriving reducts（seconds）

（1）所提算法在所有数据集上的时间消耗均低于传统的模糊粗糙集约简算法（文献［20］），这说明算法1从属性间相似性的角度出发，减少了需要评估的属性个数，这一策略能够显著地降低属性约简这一搜索过程的时间消耗。例如，对于数据集“QSAR Biodegradation”，所提算法的时间消耗仅为1.608 9 s，而文献［20］中的算法时间消耗需2.630 8 s。

（2）所提算法在所有数据集上的时间消耗均低于文献［21］和文献［23］中的方法，说明以模糊粗糙集为基本框架搭建的快速约简算法相较于以其他度量指标为框架的约简算法，在时间上占据更大优势。

（3）所提算法仅在两个数据集上的时间消耗稍劣于文献［22］所提的集成选择器。这说明算法1相较于集成策略来说，在时间消耗方面也具备一定的优势。

表4进一步展现了不同算法之间的加速比。观察表4，可以清晰地发现相较于文献［23］所提出的基于知识变化率约简求解算法，本文所提算法在加速比方面更具优势。

表4 求解约简所需时间的加速比(%)Table 4 Speed-up ratios related to elapsed time of deriving reducts（%）

3.2.2 分类性能对比

在本组实验中，根据不同算法求得的约简结果，采用 CART［24］与 KNN［25］这两种分类器在测试样本上进行分类学习。由于约简的求解是基于10折交叉验证实现的，因此本小节的实验结果也是对测试集进行分类后计算求得的均值。表5与表6分别展示了使用CART和KNN分类器之后得到的分类准确率。

表5 使用CART分类器时，不同算法对应约简的分类准确率对比Table 5 Classification accuracies with respect to different algorithms for deriving reducts using CART classificator

根据表5与表6不难得出以下结论：无论是采用CART还是KNN分类器，利用5种算法求得的约简所对应的分类准确率差异性不大。然而，在某些数据集上，所提算法对应的分类准确率却具有一定的优势。例如在“Forest Type Mapping”上，使用CART分类器，利用所提算法得到的分类准确率为0.860 9，较其他对比算法来说有一定幅度的提升。这一结果说明算法1在大幅降低属性降维时间消耗的同时，不仅没有降低分类准确率，反而在某些数据集上，能够挑选出具有较好分类性能的属性。

表6 使用KNN分类器时，不同算法对应约简的分类准确率对比Table 6 Classification accuracies with respect to different algorithms for deriving reducts using KNN classificator

表7与表8展示了分类稳定性的对比结果，本文中分类稳定性的计算类似于文献［22］中的计算方法。从表中可以得到与分类准确率相似的结论，即算法1在大幅降低属性降维时间消耗的同时，不仅没有降低分类稳定性，反而在某些数据集上，能够带来较高的分类稳定性。

表7 使用CART分类器时，不同算法对应约简的分类稳定性对比Table 7 Classification stabilities with respect to reducts obtained by different algorithms using CART classificator

表8 使用KNN分类器时，不同算法对应约简的分类稳定性对比Table 8 Classification stabilities with respect to reducts obtained by different algorithms using KNN classificator

通过3.2.1与3.2.2节的实验对比分析，可以清晰地看出，所提算法不仅在时间消耗上具有显著的优势，而且利用该算法所筛选出来的属性亦能够在测试集上提供较为满意的分类结果。该结论最终体现出了所提算法在效率和性能上的双效作用。

4 结论

属性约简作为一种有效的数据降维技术，受到了越来越多学者的重视。约简求解的时间因素，直接影响着属性约简这一降维方法在实际应用中的推广。本文从模糊粗糙集模型出发，基于数据中属性间的相似度，将条件属性划分到不同组，实现了属性搜索空间的压缩，从而大幅度降低搜索所需的时间消耗。实验结果表明，相较于现有的一些流行的约简求解算法，所提方法能够在保证分类性能的同时，提升约简求解的效率。这种基于模糊粗糙集约简的快速降维方法可面向高维数据，应用于在线流数据分析、推荐系统等对实时性要求较高的应用领域。

在今后的研究工作中将从以下方面展开讨论：（1）将所提算法拓展为一种通用的属性约简框架；（2）深入探究当算法面临噪声数据［26］时的有效性。