基于近邻传播聚类的职业能力评价模型

段桂芹，邹臣嵩

(1.广东松山职业技术学院计算机与信息工程学院，广东 韶关 512126；2.广东松山职业技术学院电气工程学院，广东 韶关 512126)

0 引 言

数据挖掘能够从教学数据中分析出有价值的信息，是辅助教学管理的重要手段[1]。作为一种经典的无监督数据挖掘技术，聚类分析目前被广泛地应用在教育领域的多项研究与实践中[2-5]。孙小素等人[6]利用聚类分析对学生个人能力进行分类，用Fisher判别方法校验聚类分析的科学性，保证了学生成绩评价的科学性和高效性。丁鹏飞[7]利用相关分析方法确定了5个聚类因子，将具有相似性的学生划分为4种类型。彭琳钧等人[8]在对学生综合能力因子分析的基础上，使用K-means算法对部分数据进行标注，用训练后的SVM模型对其他数据进行分类。张甜等人[1]提出了一种基于改进的聚类的成绩分析方法，对学生的课程成绩进行相关性分析。但是，由于K-means聚类算法在实际应用中其类簇数目依赖于人工经验，聚类质量易受人为因素影响，因此需要引入相关指标对聚类质量进一步评价。肖自乾等人[9]根据肘部法则对学生成绩数据进行分析，计算不同k值时的平均畸变程度。郭鹏等人[10]使用改进的K-means算法结合CH指标对学生成绩聚类划分后的效果进行评估。谷欣超等人[11]使用全局K-means聚类算法对学生成绩进行聚类，得到不同聚类个数下的成绩分类结果，并结合I Index指标自动地确定出最优聚类数目，实现对学生多科成绩数据的无监督分类。段桂芹等人[12]提出了一种改进K-medoids算法，结合DB指标设计了聚类质量评价模型，有效地挖掘出学生多门课程成绩的分布情况。

在借鉴上述科研成果的基础上，本文提出一种新的聚类内部评价指标，给出了簇内紧密度和簇间分离度新的计算方法，结合近邻传播算法设计了一种职业能力聚类模型，以某高校学生能力数据为样本，完成职业能力聚类分析，验证了模型的实用性。

1 近邻传播算法

近邻传播算法(Affinity Propagation， AP)是Frey等人[13]于2007年在“Science”上提出的一种新的快速聚类算法，具有无需选择初始聚类中心，无需依赖人工经验预设聚类数k等优点。AP算法是一种近邻之间互传信息的聚类方法[14-16]，在算法执行过程中，可自动寻找聚类中心。该算法的基本结构是：先使用欧氏距离公式计算出样本集的相似度矩阵；再循环交替更新样本的吸引度和归属度，在此过程中，当迭代次数超过最大值，或者类代表点连续多次迭代保持不变时，AP算法视为结束，此时可将其余样本分配至相应簇中完成聚类[17-19]。AP算法由4步构成，具体描述如下：

Step1使用式(1)计算集合中样本xi和xj间的欧氏距离：

(1)

其中，i=1,2,…,N;j=1,2,…,N;l表示样本的特征维度。

Step2使用式(2)取欧氏距离相反数作为样本的相似度值s(i,k)，得到相似度矩阵S：

(2)

其中，p(k)是相似度矩阵对角线上的数值，也是样本xk能否成为簇中心的评判标准，p(k)越大，说明样本xk被选作簇中心代表的几率越大，本文借鉴了文献[13]推荐的在无先验知识前提下取S矩阵的中值作为偏向参数p的默认值。

Step3交替更新吸引度r与归属度a，生成优质簇中心代表。其中，吸引度r(i,k)表示样本xk对xi的吸引程度，该值越大意味着xk成为xi簇中心的可能性越大；归属度a(i,k)表示样本xi对xk的归属程度，该值越大说明样本xi选择xk作为其簇中心的可能性越大。吸引度r与归属度a的交替更新过程如式(3)、式(4)所示：

r(i,k)=s(i,k)-maxk′≠k{a(i,k′)+s(i,k′)}

(3)

其中，a(i,k′)表示除xk外其他样本对xi的归属度值，s(i,k′)表示除xk外其他样本对xi的吸引度，即xi外其他样本都在争夺xi的所有权，r(i,k)是xk成为xi的簇中心的累积证明。

(4)

其中，r(k，k)表示xk的自吸引度，a(k，k)表示xk的自归属度，r(i′，k)表示xk作为除xi外其他样本的簇中心的相似度值。a(i，k)表示取所有大于等于0的吸引度值加上xk的自吸引度作为簇中心的可能程度，即xk在这些吸引度值大于0的样本点的支持下，xi选择xk作为其簇中心的累积证明。

考虑到更新吸引度r与归属度a过程中，会出现振荡现象，故此处引入了阻尼参数λ来降低震荡幅度，校正迭代过程中的吸引度归属度，设阻尼参数λ∈[0,1)，迭代次数为t，校正后的交替更新过程如式(5)、式(6)所示：

r(i,k)t+1=(1-λ)×r(i,k)t+1+λ×r(i,k)t

(5)

a(i,k)t+1=(1-λ)×a(i,k)t+1+λ×a(i,k)t

(6)

其中，r(i,k)t、r(i,k)t+1分别表示第t和t+1次迭代的吸引度，a(i,k)t、a(i,k)t+1分别表示第t和t+1次迭代的归属度。

Step4确定簇中心代表。将吸引度和归属度之和最大的样本xk作为xi所在簇的中心代表，聚类数k应满足的条件如式(7)所示：

k=argmax{a(i,k)+r(i,k)}

(7)

2 改进的内部评价指标

内部评价指标是指与外部信息无任何关联，利用数据集的内在属性特征来评价聚类算法的优劣。通过计算数据总体相似度、簇间平均相似度或簇内平均相似度来评价聚类质量。在评价过程中，通常将“簇内紧凑，簇间分散”作为内部评价的重要标准，经典的内部评价指标XB[20]的表达式如式(8)所示，其特点描述如下：

(8)

XB指标将数据集中簇内各样本与簇中心的距离平方和作为簇内的紧密度，使用最小簇中心距离的平方作为整个样本集的分离度，将簇内紧密度与簇间分离度的比值作为指标的表达式[21-22]，可以看出，XB指标越小，则各簇间距离越大，簇间越分散，簇内越紧凑，聚类质量越高。然而，当数据集为环形数据时，其簇中心的重叠度较大，各簇间的中心距离趋近于0，由于簇间相似度极高，应将二者视为一个聚类，以实现高质量聚类划分。而实际上，这种合并式聚类会导致簇中心重叠的簇全部被合并成一个聚类，明显偏离实际结果，导致聚类评价结果无效。

为了便于理解，对图1中的数据集进行讨论，该数据集由多个环形结构的簇构成，各簇中心极为接近，在计算该数据集的簇间距离时，由于簇中心点趋于重叠，必然会出现簇间距离近似于0的情况，当以“簇内紧密，簇间分离”的标准进行评判时，意味着此时各簇极为相似，从聚类划分的角度来看，为提高聚类质量应将两簇合而为一，但经过多次合并，图1最终将全部合并为一个簇，这显然与实际聚类结果有着明显偏差。而本文用簇内全部样本与簇中心的距离之和表示簇内紧密度，用任意两簇间样本距离和的最小值表示簇间分离度，则可以从几何特征上确保各簇的结构差异性，进而避免簇间距离为0现象的发生，最大程度地反映出簇间的相似程度，克服了环形数据因中心点重叠而导致的聚类结果合并等问题，通过平衡簇内紧密度和簇间分离度之间的关系[23]，确保最优聚类的划分，改进后的指标Improve-XB(以下简称IXB)定义及公式如下：

图1 环形人工数据集

定义1 簇内紧密度(Compactness)：数据集中全部样本与所归属簇的簇中心距离之和。

(9)

其中，x为簇Ci的簇内样本，vi是该簇的簇中心，k表示样本集被划分后的簇个数。

定义2 簇间分离度(Separation)：任意两簇间样本距离和的最小值。

(10)

其中，xm和xn为分属2个不同簇的任意样本。

定义3 IXB指标：簇内紧密度与簇间分离度的比值与其倒数之和。

(11)

从式(9)、式(10)可以看出，当k值增加时，簇间分离度与簇内紧密度的比值Sep/Comp增加，而Comp/Sep则反之，从式(11)可以看出IXB指标值越大，说明簇间越分散，同时簇内越紧凑，聚类质量越好。

定义4 最优聚类数kopt：IXB(k)取最大值时的聚类数目。

kopt=argmax{IXB(k)}

(12)

其中，k∈[2，kmax]，kmax由AP算法给出。

3 实验测试

本文的测试环境为：Intel(R) Core(TM) i7-10750H CPU @2.6 GHz 2.59 GHz，16 GB内存，Win10(64位)专业版，测试平台为Matlab 2011b，实验由IXB指标的有效性测试和实用性测试2个部分组成。

3.1 IXB指标的有效性测试

本实验针对新评价指标IXB的有效性进行测试，具体为：分别使用AP算法、改进K中心点算法[24]和快速K-medoids算法[25]结合XB指标、IXB指标对表1中的UCI数据集进行聚类数正确率对比测试，对比测试结果详见表2，其中，AP算法的阻尼参数范围是[0.5,1)，测试中使用其缺省值0.5，最大迭代次数为900次，文献[24]、文献[25]算法的密度参数由样本集自身决定，无需人工设定。

表1 UCI样本实验数据

表2 评价指标的聚类数对比测试

观察表2可知，在5个UCI数据集上，3种聚类算法结合IXB的聚类数正确率分别为80%、80%、60%；3种聚类算法结合XB指标所得的聚类数正确率分别为60%、60%、40%，可以看出，IXB评价指标的聚类数正确率明显高于原XB指标。

3.2 IXB指标实用性测试

本实验使用入侵检测数据集KDD CUP99[26]从检测率、分类正确率、漏报率、误报率4个方面验证新指标IXB的实用性。其中，训练集包含5种攻击类型，共10325条记录，测试集从corrected中随机选取，共2845条记录，数据预处理采用文献[27]所提出的降维方法，整理后的数据如表3所示。

表3 KDD CUP99数据集

为了完成不同聚类数条件下的入侵检测指标对比，设置AP算法的阻尼参数λ在[0.5,1)区间内的步长为0.05，最大迭代次数为900次，结合IXB指标，得出表3训练集的最优聚类范围是[22,29]。测试集的各项检测结果如表4所示，可以看出，当聚类数为26时，入侵检测率达到最大值93.89%，当聚类数为26和27时，测试集的分类正确率同为最大值95.43%，当聚类数为26时，漏报率达到最低，为4.26%，当聚类数为27时，误报率达到最低，为4.27%。

表4 测试集的入侵检测结果 单位：%

综合上述2个实验部分结果，可以得出：本文所提出的改进聚类质量评价指标能够反映出样本集的最佳聚类数目或最优聚类范围，具有较好的实用性，可应用于具体案例。

4 基于近邻传播算法与IXB指标的职业能力聚类模型

使用近邻传播算法与IXB指标构建的职业能力聚类模型由确定簇中心和确定最优聚类划分2个部分构成，模型结构如图2所示，模型的描述具体如图2所示。

图2 职业能力聚类模型

4.1 模型结构

4.1.1 确定簇中心

1)使用式(1)、式(2)得到学生职业能力的相似度矩阵。

2)使用式(3)、式(4)交替更新吸引度r与归属度a，得到簇中心代表。

3)设置阻尼参数λ、总迭代参数t，使用式(5)、式(6)降低震荡幅度，校正吸引度与归属度。

4)将满足公式(7)的候选点作为簇中心代表点，重复执行本环节中的步骤3，再次校正全部样本的吸引度和归属度，筛选出簇中心代表点，将其它样本划分至相应簇中，获取聚类数上限值kmax。

4.1.2 确定最优聚类划分

1)将聚类数上限值作为聚类数初值，即k=kmax。

2)使用式(9)、式(10)计算簇内紧密度与簇间分离度，使用式(11)计算IXB指标。

3)令k=k-1，重复执行本环节中的步骤2，依次计算k={2，3，…，kmax}的IXB指标，使用式(12)获取最优聚类数kopt，并将IXB指标最大时的聚类结果作为最优聚类划分输出。

4.2 模型在职业能力聚类中的应用

4.2.1 样本描述

遵照高职院校“工学结合”的教学特点，我校同用人单位、行业协会专家、一线教师一起，根据物联网应用技术专业的岗位需求，完成了相关岗位的职业能力描述，设计了由基本素质、专业核心技能、专业知识构成的职业能力表(详见表5)和职业能力等级标准(详见表6)，并对我校2018级物联网应用技术专业80名学生第2～4学期的职业能力进行了采集，样本数据详见表7。

表5 物联网应用技术专业职业能力表

表6 职业能力等级标准

表7 学生职业能力样本数据

4.2.2 聚类结果输出

本节使用聚类模型对表7的80名学生从职业能力的3个方面进行了聚类分析，具体为：基本素质属性(A1～A12)、专业核心技能属性(B1～B6)和专业知识属性(C1～C5)。模型中AP算法的阻尼参数为0.95，总迭代次数为900次，运行环境为Matlab 2011b，所得IXB指标与k值对应关系如表8所示，关系图如图3所示，最大聚类数、最优聚类数和IXBmax指标如表9所示。由IXB指标的特征可知，该值最大时的k值即为最优聚类数，此时的聚类结果为最优划分，各分项职业能力的最优聚类划分情况如图4所示，详细划分结果详见表10。

表8 k值与IXB指标对应关系表

表9 各职业能力的最大聚类数和最优聚类数

图3 k值与IXB指标关系图

图4 各簇数据最优划分情况

4.3 聚类结果分析

为了更准确、深入地对聚类结果进行分析研究，本文分别从学生的职业发展和企业的人才选择2个角度对表10的最优聚类划分进行分析，并给出相关建议。

表10 数据划分结果

4.3.1 学生的职业发展

将表10中“专业核心技能”的聚类结果结合表7的具体学情信息进行分析，第1类学生共25人，他们的B2、B5、B6职业能力突出，能力值都在4.3以上，建议此类同学将Android程序设计、物联网系统仿真设计、嵌入式Linux应用开发等课程作为选修课程，将物联网应用系统测试与程序开发岗位作为择业方向。第2类学生共26人，与第1类学生相比，他们的“B2、B5、B6”能力值都低于3.5，但是“B1、B3、B4”能力值都在4.0以上，结合具体学情发现他们对终端设备安装、通信组网兴趣浓厚，在软硬件安装调试过程中，能够对出现的故障进行分析、解决与总结，因此建议此类同学将智能家居系统安装与配置、RFID应用技术、物联网项目方案设计等课程作为今后的选修课程，将物联网系统集成与运维岗位作为择业方向。第3类学生共29人，他们的各项专业核心技能值在2.5～3.3之间，相比前2类学生，他们的专业潜能优势并不明显，建议这类学生主动寻找自己的学科兴趣，重视专业实践，提升专业技能。

将表10中“专业知识”的聚类结果结合表7的具体学情信息进行分析，第1类学生有12人，他们对专业知识的掌握程度较其他同学更加牢固，C1～C5的能力值都在4.2以上，有能力在本科院校继续深造，因此，对于计划选择“专插本”的学生来说，可以考虑在相关理论课程方面投入更多的时间与精力，校方也可以为此类学生创造更为有利的学习条件。此外，观察表10的聚类划分结果，可以发现一个有趣的现象，这类学生的“专业核心技能”和“基本素质”也都被划分为同一类，这一结果与教师评价、学生互评、师生座谈等多渠道反馈的实际学情基本相符，从未来就业角度来看，他们的就业面更宽、更广，可塑性更强。“专业知识”的第2类和第3类分别为20人和22人，从聚类结果来看，这2类学生的簇间距离小、相似度较大，C1～C5的能力值都在3.3～4.1之间，共同特点是对电工电子技术、传感器、RFID应用技术等基础知识掌握得比较牢固，但却存在一定程度的“偏科”现象，第2类学生对单片机、嵌入式技术的掌握程度优于第3类，第3类学生的计算机网络、操作系统等专业知识背景略好于第2类，建议这2类学生可以在感兴趣的课程上投入更多的精力，进一步强化自己的优势学科。第4类学生有16人，他们的共同特点是专业基础知识掌握得相对较好，和第2、第3类学生相比，他们的专业课知识略显薄弱，对无线传感网、数据库、嵌入式技术相关专业知识的认知存在明显不足，建议这类学生积极查漏补缺，弥补专业知识上的短板。第5类学生有10人，他们C1～C5的能力值都在2.2以下，在专业知识的基本认知方面存在严重不足，尤其对主流物联网设备器件的认知能力有待提升，建议他们改变目前的学习方式，认清自身的薄弱环节，同时也需要师生们给予他们更多的关心，帮助他们树立好正确的学习观念。

4.3.2 企业的人才选择

企业在人才选择过程中，除了可以将学生在“专业核心技能”和“专业知识”特征项中表现出的职业倾向性作为主要参考依据，还可以结合表10中“基本素质”的聚类结果综合分析。例如某企业在招聘系统集成相关岗位时，可以先将“专业核心技能”中B1、B3、B4能力值突出的第2类学生和“专业知识”中C3、C4、C5能力值突出的第3类学生作为候选者，再根据岗位的具体需求，对候选者的“基本素质”进行二次筛选，如果岗位倾向于售后服务，则可将环境适应能力、出差意向(A5)和独立工作解决问题能力(A6)作为二次筛选的重要依据；如果岗位倾向于售前咨询、方案设计，则可将语言沟通能力(A3)和独立工作和书面表达能力(A4)作为二次筛选的重要依据。

5 结束语

本文使用近邻传播算法和改进的XB评价指标设计了一个学生职业能力聚类分析评价模型，从基本素质、专业核心技能、专业知识3个职业能力维度给出了学生最优聚类数目，客观准确地完成了职业能力数据的最优聚类划分，解决了经典聚类算法在教育数据挖掘中存在的聚类数目过于依赖人工经验等问题，实现了高职学生职业能力数据的建模、分析与评价。该模型可用于高职学生职业能力(综合素质)评价与职业倾向性预测，能够为教学反馈与人才的分层分类培养提供理论支撑，能够为学生的职业生涯规划和企事业人力资源的合理配置提供客观、科学的参考依据。