改进的模糊K—Prototypes聚类算法在研究生培养质量评估中的应用

乔秀峰 张德珍 吴迅 张俊

[摘 要] 研究生教育在从追求招生数量到重视培养质量的背景下，如何有效而准确地评估研究生培养质量，成为当前各高校面临的重要课题。文章提出一种改进的模糊K-Prototypes聚类算法，可准确分析研究生培养质量情况。该算法首先提取相应的研究生培养质量影响因素属性，构建研究生培养质量评估指标，从而形成分析数据集；其次，为了解决研究生培养数据密度不均的问题，提出改进算法；最后利用改进的聚类算法对分析数据集进行聚类分析。以一所具体高校为例，验证提出算法的有效性和改进后聚类效果，为科学有效的研究生培养质量评估提供辅助决策方法支持。

[关键词] 研究生教育； 培养质量评估； 模糊K-Prototypes聚类

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2018. 07. 077

[中图分类号] G647 [文献标识码] A [文章编号] 1673 - 0194（2018）07- 0185- 06

1 引 言

提高研究生培养质量是高等教育改革最核心的任务[1]，而如何对培养质量进行客观科学的评估则是任务的难点所在。一些学者进行了探索性研究，对高校研究生培养质量评估，采用了主成分分析方法、层次分析评价模型、模糊综合评价模型等传统方法，如Chen等人在文献[2]中提出了改进的层次分析方法构建的教育质量评价模型的理论与应用； Liu等人在文献[3]中采用层次分析及模糊的方法对研究生培养质量评估中学生综合职业能力方面的评价作了研究；Hu等人在文献中提出用主成分分析和Elman神经网络对研究生培养质量中关于教学质量方面的评估进行了研究。这些文献分别提出基于模糊综合评价的高等职业教育评价模型和基于模糊综合评价法的高等工程教育综合评估研究。上述方法有其积极有效的一面，但一般通过专家为评估对象打分，评估结果主观性较强，往往不能较好反映实际值。

针对研究生培养质量数据类型多样化及数据具有模糊边界特征的特点，将模糊K-Prototypes聚类算法应用于研究生培养质量评估中，同时，由于研究生培养质量数据呈现密度不均现象，提出了改进的模糊K-Prototypes聚类算法，采用密度与最大最小距离方法以及高密度点的方法，将数据集划分成不同的密度区域，从而得到数值属性与分类属性的初始聚类中心，以此提高聚类结果的准确性。以武汉理工大学2015级研究生培养质量相关的数据集为实验数据，对其进行聚类分析，获得关于影响研究生培养质量的主要因素，从而为研究生培养质量评估提供有效的决策支持方法。

2 研究生培养质量评估指标

武汉理工大学的研究生教育综合管理系统经过多年系统性建设，涵盖了研究生从入学到毕业整个培养过程信息，是研究生培养质量聚类分析的基础。该系统数据库包含了学生的学籍、课业、学术论文发表、科研、指导教师基本信息及其论文发表、科研项目、科研成果等详细数据，而不同属性之间又可能存在关联性，特征属性的选取，将直接影響聚类结果。考虑到本文的目标是对研究生培养质量数据进行聚类分析，参考已有文献研究成果，影响研究生培养质量的主要因素，包括研究生的分析能力、创造力、实践能力、综合能力、科研成果情况、学习成绩、学位论文情况、导师因素、学术氛围环境等。

基于上述特征属性集，结合武汉理工大学对于研究生培养质量评估的实际需求，本文构建了如下多因素多层次的研究生培养质量评估指标体系。

本文将基于改进模糊K-Prototypes聚类算法构建研究生培养质量聚类分析模型，本研究将所评估指标作为模型的输入变量，对研究生培养质量进行聚类分析，从中获取每类研究生培养质量的整体特征，进而发现影响研究生培养质量的主要影响因素。

3 模糊K-prototypes 聚类算法

假设混合属性数据集为X={X1，X2，…，Xn}，其中有n个样本数据，每个样本数据有m个属性，则混合属性集合中的每个样本数据可以记为Xi={x■■x■■，…，x■■，x■■，…，x■■}，前p个属性表示数值型数据，后m-p个属性表示分类型数据。

定义1相异度度量：假定X与Y表示两个样本，则数值属性的相异度与分类属性相异度计算公式分别为式（1）和式（3）。

对于数值型属性，采用传统的方法欧氏距离来计算，则两个样本相异度定义如下：

d1（Xi，Yj）=■（c■■-x■■）2，1≤r≤p（1）

对于分类型属性，采用海明距离来计算两个样本的相异度定义为：

？啄（x■■-y■■）=0，x■■=y■■1，x■■≠y■■（2）

d2（Xi，Yj）=■？啄（x■■-y■■），p+1≤r≤m（3）

则每个样本数据间的相异度计算方法定义为：

d（X，Y）=■（x■■-y■■）2+γ·■？啄（x■■-y■■）（4）

定义2聚类中心：从数据集X中选择K个样本对象作为初始聚类中心点，每次迭代更新的聚类中心可表示为Z={Z1，Z2，Z3，…，Zk}，每个样本对象到聚类中心的距离记为d（Xi，Zj）。在聚类的过程中，样本对象会被划分到离聚类中心最近的类中，则最终会被划分成K个聚类集合。

（1）数值属性的聚类中心计算公式为：

z■■=■（wil）α·x■■/■（wil）α（5）

若Xi=Zl，则wij=1；

若Xi=Zl且j≠l，则wij=0；

若Xi≠Zl，则

wij=■（d（Xi，Zj）/d（Xi，Zl））■■（6）

其中1≤l≤k且1≤j≤p。

（2）分类属性的聚类中心选择特征值密度最大值作为聚类中心，满足如下定义：

z■■=Clj/Nt，1≤l≤k且1≤j≤p（7）

其中参数Clj表示第t个划分类中属性j的每个特征值的频率数，参数Nt表示第t个划分类的样本数。

则模糊K-prototypes聚类算法的目标函数F（W，Z）定义如下：

F（W，Z）=■■（wij）α（d1（Xi，Yj）+γ·d2（Xi，Yj））=

■■（wij）α■（x■■-z■■）2+γ·■？啄（x■■，z■■） （8）

其中W=（wij）n×k是一个n×k的模糊划分矩阵，满足：0≤wij≤1且■wij=1，参数γ来调节数值属性和分类属性的权重比例的大小，α为模糊系数，且满足α∈[1，∞）。

模糊K-prototypes均值聚类算法以下列具体步骤进行迭代：

输入：混合属性数据集为X，基本参数分别为最大迭代次数T，聚类数目K，误差阈，模糊系数α，权重系数γ；

输出：K个聚类集合。

步骤 1：从数据集中随机选取个初始聚类中心；

步骤2：用式（4）计算每个样本数据与初始聚类中心的相异度，然后将样本数据划分到最近的聚类中心中；

步骤3：用式（6）计算模糊划分矩阵W；

步骤4：更新数值属性与分类属性的聚类中心。对于数值型属性，采用式（5）和（6）进行计算，对于分类型属性，采用式（7）进行计算；

步骤5：采用式（8）计算目标函数值；

步骤6：如果新的目标函数值与原来的目标函数值之差的绝对值小于误差阈，且迭代次数大于T，则停止并输出聚类结果，否则，再次更新迭代次数T=T+1，并转步骤3。

4 算法的改进

由于初始聚类中心的随机选择，容易使聚类结果随着不同的选择而变化，导致结果不稳定，同时模糊K-Prototypes聚类算法不易发现密度不均的数据集。针对以上问题，本文对数值属性与分类属性分别采用不同的方法进行初始聚类中心的选择，假设样本数据集为X，聚类数目是K，则具体选择原则如下：

（1）数值属性。采取密度与最大最小距离的方法对数值属性进行初始聚类中心的选择，首先选择数据集中最大的密集点，作为第一个初始聚类中心点，其次再选择距离第一个初始聚类中心点最远的点作为第二个初始点，因此得到相距最远的两个点Xi与Yj，然后再计算每个样本点与已确定的每个初始聚类中心的距离，从中选取最小距离的样本数据，最后再从最小距离的样本数据中寻找最大距离的样本点作为聚类中心，直到满足设定的聚类数目。

根据以上相关描述给出密度与最大最小距离算法：

Input：A set of numerical data：X， Number of Clusters：K

Output：Clusters

1.X={X1，X2，…，Xn}，P={P1，P2，…，Pn}

2.R←■■d（Xi，Yi）/■i

3.For Xi in X DO

4.For XJ in X DO

5.If d（Xi，Yi）≤R Then

6.Pi=Pi+1

7.End for

8.End for

9.Z1←numerical data of Max（Pi）

10.Clusters= Clusters U{Z1}

11.For Xi in X DO

12.dist ←d（Xi，Z1）

13.End for

14.Z2←numerical data of Max（dist）

15.Clusters= Clusters U{Z2}，already← the size of

Clusters

16.For i= already to K

17.For Zi in Clusters

18.For Xi in X

19./*dmin is a set of Minimum distance*/

20.dmin←Min（d（Z1，Xi），…，d（Zi，Xi））

21.End for

22.End for

23.Zi←numerical data of Max（dmin）

24.Clusters=Clusters U{Zi}，i=i+1

25.End for

26.Return Clusters

（2）分類属性。借鉴文献Bai提出的分类属性初始聚类中心选择的方法，主要思想为：首先选择一个高密度点，作为第一个初始聚类中心，其次再选择一个密度高并且距离第一个初始聚类中心远的点作为初始聚类中心的标本，然后根据该标本构建初始聚类中心的候选集，最后从候选集中选择初始聚类中心，直到满足设定的聚类数目。

根据以上相关描述给出高密度点的算法：

Input：A set of categorical data：X，Number of categorical data： n，Number of Clusters：K，A set of attribute：A

Output：Clusters

1. For Xi in X

2.For Ai in A

3./*VAi is the value set of attribute Ai*/

4.For qj in VAi

5.If F（Xi，Ai）==qj Then

6.frij=frij+1

7.End for

8.End for

9.End for

10.For Xi in X

11.dens（Xi） ←■（frij/n-1）

12.End for

13.Z←categorical data of Max（dens（Xi））

14.For i= 1 to K

15.For Xi in X

16.exemplar（Xi）←dens（Xi）+d（Xi，Z）

17.End for

18.U←categorical data of Max（exemplar（Xi））

19.For Xi in X

20.t←d（Xi，U）

21.St=St U{Xi}

22.End for

23.Zi←■（Den（y）+d（y，Z）-d（y，U））

24.Clusters=Clusters U{Zi}，i=i+1

25.End for

26.Return Clusters

在改进的模糊K-Prototypes聚类算法中，参数的选择对于聚类效果至关重要，其中模糊系数以及权重比例系数取值的选取，至今仍是一个未定论的问题，参考已有学者研究成果，本文最终确定α选取为2，γ选取为1.1。

5 实验与分析

从武汉理工大学研究生综合管理系统数据库中选取2015级共1 028名研究生作为样本数据，对于每个研究生的培养质量情况，参考该高校的终期考核结果，将研究生分为优秀、良好、中等、差四个类别。对所改进的模糊K-Prototypes算法使用C#语言编程实现，开发环境为Microsoft VS2010。

5.1 数据预处理

由于提出的算法适用于混合属性，因此为了使不同数值数据相对有意义且减少数据之间的差异，采用最小最大规范化，对每个样本的数值属性用如下公式进行规范化。

X■■=■（9）

其中，X■■为样本对象中某一属性归一化后的值，Xij为归一化前的值，Ximin表示同一属性中所有样本数据的最小值，Ximax表示同一属性中所有样本数据的最大值。

5.2 实验过程

将提出的改进模糊K-Prototypes聚类算法应用到研究生培养质量评估中，具体的聚类过程如下：

第一步，将每个研究生个体看作一个样本对象，根据筛选得到的特征属性，从数据库中提取相应的分析数据集，其中包含了数值型属性的数据以及分类型属性的数据，如表1至表2所示，从表1中可以看出数值属性之间数据的差异较大，因此对数值型属性进行归一化，得到归一化后数据的部分结果如下表3所示。

第二步：聚类算法中涉及到的基本参数分别取值为：K=4，α=2，γ=1.1，采用提出改进的初始聚类中心方法；

第三步：根据上一步得到的初始聚类中心，在此基础上逐个计算样本对象与初始聚类中心之间的相异度，根据相异度的大小，對不同的样本对象进行划分，最终得到不同的类，每个类中包含特征相似的对象。

5.3 聚类结果分析

本文采用正确率（Accuracy）来评估算法的聚类质量，设样本集的样本数为n，Ai表示样本正确分到i类的样本数，K为聚类数目，则正确率的计算公式表示如下：

Accuracy=■Ai/n，1≤i≤k（10）

由于不同的权重系数会影响聚类效果，选取不同的值对改进的模糊K-Prototypes聚类算法进行实验分析，实验结果如下表5所示。

从表4中可以看出，当权重系数为0.9时，改进的模糊K-Prototypes聚类算法达到最佳的聚类结果，同时验证了改进算法在研究生培养质量评估应用中的有效性。

对模糊K-Prototypes聚类算法和改进后的聚类算法进行对比实验，由于模糊K-Prototypes聚类算法的初始聚类中心是随机选择的，不同的初始聚类中心对算法会产生不同的聚类效果，因此对权重系数选取不同的取值，同时选取相同的实验次数进行实验，最终得到平均正确率，改进前后模糊K-Prototypes聚类算法的聚类效果对比。当权重系数为1.3时，模糊K-Prototypes聚类算法的正确率达到最高，然而通过对比分析实验结果，在不同权重系数的取值下，改进后的模糊K-Prototypes聚类算法正确率都高于未改进前的算法，由此，体现了改进算法的优越性。

5.4 实例结果分析与评估

由上述的聚类实验结果可知，改进的模糊K-Prototypes聚类算法在研究生培养质量评估的应用中最高正确率达到78.54%，则本文以最好的聚类效果为例，对每类中研究生所体现出的共性特征进行描述分析。从学生的整体成绩水平、答辩情况、论文情况、综合技能、参与科研项目情况以及学生导师的学术水平情况等多个方面进行对比分析，通过整理和统计数据，得到部分相关统计。为了更清楚地显示各个类之间的群体特征，则研究生培养质量数据聚类统计结果如表5所示，得到如下结论。

（1）第一类中一共有162名研究生。通过整体的共同特征可以看出，整体的平均成绩处于中等偏上，但是答辩成绩都低于其他类中的整体水平，而且发现该类学生98.2%没有发表论文，同时94.5%的学生科研成果情况较差，在综合技能方面，40.9%的同学处于较差的水平，学生的导师学术水平较其他类偏低，导师类别博导占63.6%。总的来说，这类研究生的培养质量较差。

（2）第二类中一共有87名研究生。该类学生的整体平均成绩与答辩成绩都高于其他类的整体水平，在发表论文方面，83.9%的研究生发表过一类等级的论文，发表论文较为优秀，发表论文的检索等级多为SCI，同时均已发表过两篇或多篇EI级别的论文，其中发表3篇以上论文的学生占4.6%，在学生科研成果情况方面，48.6%的学生处于中等水平，但是在综合技能方面却一般，这类学生的导师水平较高，且88.6%的导师是博导。总的来说，这类研究生的培养质量较优秀。

（3）第三类中一共有367名研究生。该类学生的整体平均成绩与答辩成绩都处于中等偏上水平，在校期间69.5%的学生发表过二类等级以上的论文，其中发表3篇以上的占1.09%，但是在科研成果以及综合技能方面，研究生都处于较差的水平，学生的导师学术水平处于中等偏上，且75.6%的导师是博导。总的来说，这类研究生的培养质量良好。

（4）第四類中一共有412名研究生。从学生的平均成绩来看，该类学生整体成绩处于中等偏下的水平，学生整体答辩情况处于中等水平，发表论文方面，29.4%的学生发表过论文，且23.54%的研究生发表情况一般，发表过三类等级的论文，在校期间，整体科研情况处于中等水平，但56.5%的研究生综合技能较差，学生的导师学术水平处于中等水平，且该类学生大多数导师是博导。总的来说，这类研究生的培养质量处于中等。

由此，根据上述结论得出以下建议：

（1）导师的学术水平是影响研究生培养质量的重要因素，因此，学校要加强对导师的定期考核，不断促进导师自身的学术水平。

（2）发表论文情况与学生答辩情况成正相关，因此，学校要鼓励学生积极发表高质量水平的论文，为学位论文的撰写打下坚实的基础。

（3）学生的综合技能水平都较差，学校应该培养学生的综合素质，从侧面引导学生的主动性与创造能力，从而有效地促进研究生培养质量的提高。

6 结 语

针对研究生培养质量数据的特点，提出了改进的模糊K-Prototypes聚类算法，并将该算法应用到研究生培养质量评估中，同时构建了研究生培养质量评估指标，实验结果表明，不仅验证了算法的有效性，而且体现了改进后算法的优越性。使用该算法，对研究生培养质量进行聚类分析之后，将其划分成不同类别的研究生，从中获得每类研究生群体培养质量的特征，找到影响研究生培养质量的主要因素，为高校管理部门提供决策支持，同时起到监控、监督的作用。

主要参考文献

[1]金丽，万洪英，刘海清，等.研究生培养过程监控和预警系统应用初探[J].研究生教育研究，2011，5（3）：31-36.

[2]张钰莎.数据挖掘技术在教学质量评估中的应用研究[D].广州：暨南大学，2012.

[3]蔡捷.数据挖掘聚类算法的研究及其在研究生培养质量评估中的应用[D].南京：东南大学，2014.