基于改进KNN-DPC算法的科技创新人才分类研究*

张文宇 刘 嘉 杨 媛 朱钰婷 于 瑞

（1.西安邮电大学经济与管理学院 西安710061）（2.中国航天系统科学与工程研究院 北京 100081）

1 引言

党的十九大报告提出，人才是实现民族振兴、赢得国际竞争主动的战略资源。科技创新人才作为从事系统性科学和技术知识的发现、生产和应用活动的创造性人力资源，是科学技术这一先进生产力的集中体现。对于各个领域存在的科技创新人才，要充分发挥其具备的能力和素质，就要对科技创新人才进行精准分类。因此，研究科技创新人才的分类问题对我国科技创新人才的发展、社会化建设有着十分重要的作用。目前，科技创新人才的理论研究大多集中在培养阶段，杨颖［1］基于新的时代背景构建出科技创新人才的培养机制。彭干三［2］在产学研融合视角下对我国科技创新人才培养过程中存在的问题提出意见。然而，科技创新人才的分类问题研究相对较少，陆一［3］等提出了三种选拔与培养类型的二维分类体系，以此来探究高校背景下创新人才的培养分类模式。邴浩［4］提出了一种政策分类的新方法来提升高校创新人才分类过程中政策的实施效果。以上的相关研究大部分是基于理论的定性研究阶段，相关的定量研究很少，这导致科技创新人才分类研究的量化和精细化不足，不能充分挖掘科技创新人才的数据信息，从而对实际中科技创新人才的分类指导性不强。

在大数据背景下，充分利用海量数据资源，突出量化分析是科技创新人才分类研究的重要发展方向。因此，通过对科技创新人才数据的收集，从而对样本数据进行数据挖掘与分析是提高人才分类效果的重要途径。已有的研究表明聚类算法是数据挖掘中研究分类问题的有效方法，传统聚类算法可被划分为分割聚类、密度聚类，以及基于传播的方法等［5～7］。Alex Rodriguez和Alessandro Laio［8］提出的一种密度峰值聚类算法DPC，该聚类算法具有计算速度快，无需迭代等特点，可以很好地描述数据分布，同时在算法复杂度上也比一般的K-means算法的复杂度低。尽管DPC算法优势明显，但其对高维数据的处理以及非中心点的归类仍存在一些局限，针对DPC算法的缺点，近两年许多学者都对DPC算法进行改进。张伟［9］将DPC算法和Chame-leon算法的优点相结合提出了E_CFSFDP算法，虽避免了将包含多个密度峰值的一个类聚成多类，但其计算量大且不利于处理高维数据。谢娟英［10］提出两种基于K近邻的样本分配策略的快速密度峰值算法KNN-DPC，其算法对噪声数据具有非常好的鲁棒性，但由于该算法的聚类过程与DPC相同，故DPC算法的缺陷在该算法中仍存在。

针对上述问题，本文提出的结合主成分的改进K近邻优化的密度峰值聚类算法IKDPC将主成分分析法融入聚类算法中对高维数据降维，克服了聚类算法中高维数据对聚类结果的影响，为了更好地描述每个样本在空间中的分布情况给出了新的局部密度的计算方法，并对原有样本点的分配过程进行了改进，有效提高了算法的聚类结果，使该算法能更好地应用于实际分类领域。首先，本文在阐述科技创新人才的定义及内涵的基础上，定性分析出科技创新人才的特点并构建出科学合理的评价指标体系；然后，通过IKDPC算法对科技创新人才进行量化分类研究，根据收集资料和调研获得的样本评价指标数据，对科技创新人才进行实例验证并分析其结果，并通过IKDPC算法与其他算法的分析比较表明IKDPC算法的优势，从而为提高科技创新人才培养过程中人才层次分类的效果提供依据。

2 科技创新人才及其评价指标体系

2.1 科技创新人才的定义及内涵

科技创新人才是从事系统性科学和技术知识的生产、促进、传播和应用活动的创造性人力资源［11］。根据科技创新人才的定义可知科技创新人才具体应包括以下五部分内涵。

1）具有较高的知识修养水平；

2）具有积极的创新实践能力；

3）具有良好的环境适应能力；

4）具有健康的身体状况；

5）具有健全的心理与人格素质。

2.2 科技创新人才的评价指标体系

本文对科技创新人才的素质从知识修养水平、创新实践能力、环境适应能力、身体状况和心理与人格素质五个部分构建评价指标体系，再根据对相关文献和资料的研究，确定这五个部分的三级指标［12］。科技创新人才评价指标体系如表1所示。

表1 科技创新人才评价指标体系

3 DPC算法

DPC算法通过搜索合适的局部密度较大的点作为类簇中心，再将类簇的标签从高密度点向低密度点依次传播来实现数据样本的聚类划分。该算法能够快速发现任意形状数据集的密度峰值，并高效进行样本点分配和离群点剔除［11］。DPC算法引入了样本数据点xi的局部密度ρi和数据点xi到局部密度比它大且距离它最近的样本数据点xj的距离δi，其定义如式（1）和（2）所示：

数据集，IS={1,2,…,N}，为相应指标集，dij=dist(xi,xj)表示数据点xi和xj之间的欧式距离。参数dc＞0为截断距离。

对于ρi最大的样本数据点xi，其δi=minjdij。

对于较小的数据集，由式（1）估计的密度可能会受统计误差的影响，此时采用式（3）来估计其局部密度［9］。

为了获取数据的聚类中心，DPC算法首先将每个点的ρ值和δ值于坐标平面内绘制出，然后将ρ值和δ值都较大的点作为聚类中心［8］。然而，对于分布稀疏的数据，通过ρ值和δ值难以确定其聚类中心，此时DPC算法使用γ=ρ×δ来获取，其中，γi值越大，xi越有可能成为聚类中心。将所有点的γ值降序排列，并与坐标平面上绘出。由于聚类中心的γ值较大，而其他点的γ值较小且呈平滑趋势，故可以使用一条平行于横线的直线将其分开，使得直线上方的γ值所对应的点即为聚类中心。当聚类中心找出后，将剩余点分配到其高密度最近领所属的类中。

4 IKDPC算法

4.1 IKDPC算法思想

高维数据的聚类分析存在着很多困难，重点表现在：1）高维数据稀疏性对于信息的识别造成一定的困难；2）随着维数升高，计算量呈现指数型增长，这导致了对于聚类分析的结果计算更加困难［13］。因此，本文在聚类分析中融入了降维思想，选取已广泛应用的主成分分析方法，对科技创新人才样本数据进行降维后再聚类，可以获得良好的聚类效果。

主成分分析（PCA）是模式识别过程中广泛应用的特征生成和降低维数的方法，它是在数据信息丢失最少的原则下，对高维变量空间进行降维处理，同时，使得高维数据点的可见性成为可能［14］。本文通过对科技创新人才评价指标体系的样本数据集进行主成分分析，计算出相关系数指标，得出主成分对原始指标数据的方差贡献率及累计方差贡献率，当累计方差贡献率达到或者超过85%，即m满足：≥85%，且特征值大于1，从而求出科技创新人才评价指标体系的主成分指标m（m＜p），然后对所求出的m个主成分指标数据进行聚类分析。

为了克服克服传统DPC算法的缺陷，本文引入相似性系数来调节个点对当前点的密度贡献权重，提出带有相似性系数的高斯核函数来计算其局部密度［15］。对于每个样本数据点xi，其局部密度ρi定义如下：

其中，σ取数据量的2%［9］，r为相似性系数，表示密度函数与数据点相似度的关系程度，该值越大，距离点xi越近的点对其密度ρi的贡献权重越大。样本数据点xi的距离δi计算方式与DPC算法相同。对于聚类中心的选取，考虑到ρ和δ值可能处于不同的数量级，因此，对两者进行归一化处理以有效获得聚类中心γi，γi定义如下：

利用式（4）、式（2）计算出个点的ρ和δ值，式（5）计算出相应的γi值，然后通过γ值决策图选取较大的前M个γ值对应的点获得聚类中心。

由于聚类中心往往出现在高密度区域，故将各聚类中心某邻域内的点看作核心点，而将其他点看作非核心点。核心点的获取方法为先将剩余点分配到距其最近的聚类中心所在的类中，然后计算各局部类Cm中所有点与其类中心cenm间的平均距离um，若xi以下式（7），即xi∈Cm在cenm的θum邻域内，则xi为核心点。

其中，|Cm|为第m个局部类Cm中的所有数据点的数目，为点xi∈Cm与cenm间的距离；θ与数据集大小N有关，取N‰；Xcore为核心点集合。

对于剩余各点，本文设计了两种全新的分配策略，策略一是以核心点集合Xcore中每个点为中心，不断地搜索未分配的KNN并将之分配到该点所在的局部类中。策略二则是根据式（8）计算xi和xj的相似度sij，表示两点距离大小，距离越近，sij越高。每个点的归属由其KNN分布决定，若xi的KNN中属于Cm的点越多且与xi的距离越近，则sij值越大，此时xi被分配到到Cm的概率Pim也越大。的计算如式（9）：

综上所述，本文提出的IKDPC算法首先在聚类分析中融入了主成分分析法对高维数据进行降维处理，进而在传统DPC算法中引入相似性系数来调节样本数据点的密度贡献权重以计算其局部密度，最后设计了全新的两种样本数据点的分配策略，有效提高了数据的聚类效率和聚类质量。

4.2 具体算法步骤

IKDPC算法步骤如下。

输入：数据集S，样本近邻数K，相似性系数r。

输出：聚类结果。

Step1：对样本评价指标数据集S使用主成分分析方法，选取前m个主成分指标，该选取满足累计贡献率在[8 5%,100%]区间；

Step2：对选取的m个主成分指标新数据集应用改进的DPC算法进行聚类；

Step2.1：计算新数据集中各个数据点间的欧式距离dij，根据式（4）和式（2）计算每个数据点的ρ和δ值；

Step2.2：通过对计算的ρ和δ进行归一化处理，得到γ，进而构建决策图获得聚类中心；

Step3：使用式（6）和式（7）提取核心点，并采用策略一将待分类点归类：

Step3.1：将核心点集合Xcore至于队列Q；

Step3.2：取队列头xa，将其从Q删除，然后查找其K个最近邻KNNa；

Step3.3：若x′∈KNNa未被分配，Step4则将x′分配到xa所在的类中，并将x′添加至Q尾；否则转Step3.2；

Step3.4：若Q=∅，终止该策略；

Step4：根据策略二分配剩余k个点：

Step4.1：依式（8）和式（9）计算每个点的Pim(i=1,2,…,k)，

将该结果存入矩阵Pk×M，同时将的值以及类别号m分别存至向量MP和MI；

Step4.2：若MP中有非零值，则将值最大点xo归入MI(0)所表示的类中，转到Step4.3，否则终止该策略；

Step4.3：更新P、MP、MI，令MI(0)=0。对于未分配的点xp∈KNNo，更新P[p][m]、MP(p)、MI(p)。

Step4.4：若MP中所有元素均为0，则终止；否则转Step4.3；

Step5：若仍然没有被处理的点可以看作噪声点，将其归入到最近邻所在的类中去。

5 实证研究

5.1 数据收集及整理

本文通过阅读相关研究文献、人物传记提取杰出科技创新人才的评价指标，然后设计发放科技创新人才评价调研问卷，整个过程符合调查抽样随机性的原则，问卷发放的对象主要是科研院所及高校人员，调研的结果能反映科技创新人才素质的真实情况。最后将调研问卷的结果进行整理打分，以科技创新人才评价指标体系中的24个评价指标反映出样本人员所对应的指标得分（分数越高代表对应的素质越高，每个指标的满分为5分）。经过去噪、去除不合理样本等预处理，最终共收集科技创新人才有效样本指标数据352例，科技创新人才样本指标数据如下表2。

表2 科技创新人才评价指标数据

5.2 实证结果分析

首先把整理好的352例科技创新人才的24项评价指标数据导入SPSS中进行主成分分析，结果见表3。

表3 主成分分析解释总差异

从表3中可以看出，第一成分到第五成分特征值都大于1，并且累计方差贡献率达到86.001%，可知这5个成分包含原始24个成分信息量的86.001%，可以反映原始数据的主要信息。因此，本文提取前5个成分作为主成分指标进行接下来的聚类分析。聚类结果以表4展示如下。

表4 科技创新人才主成分指标聚类结果

根据表4可以看出A类样本人数为106人，聚类中心点为9号样本点，分析其主成分指标得分情况可知此样本人员各个主成分指标分数都较高，因此A类样本代表的是综合全面型的科技创新人才；B类样本人数为95人，聚类中心点为82号样本点，分析其主成分指标得分情况可知此样本人员主成分2和3分数显著，即他的受教育程度较高且知识运用能力强，因此B类样本代表的是具有良好教育背景的知识应用型科技创新人才；C类样本人数为82人，聚类中心点为175号样本点，分析其主成分指标得分情况可知此样本人员主成分4分数显著，即他拥有丰富的知识存储量，因此C类样本代表的是拥有知识积累型的科技创新人才；D类样本人数为69人，聚类中心点为175号样本点，分析其主成分指标得分情况可知此样本人员主成分5分数显著，即他具有较强的想象力，因此D类样本代表的是创新思维型的科技创新人才。结合以上分析可知本文算法能够得到较好的科技创新人才分类结果。

5.3 算法实例分析

为了验证数据降维对聚类效果的提升，分别将DPC算法和IKDPC算法在1～24个科技创新人才评价指标成分张成的数据集中进行聚类，使用分错率（CER）、ERRORRATE和调整Rand系数（Adjusted Rand Index，ARI）三个指标综合衡量聚类效果，结果如表5所示，科技创新人才在降维过程中维数超过5时各项指标都产生了大幅度变化，各个指标均不理想。

表5 DPC和IKDPC的样本指标数据聚类对比

最后，为了对比本文提出的IKDPC算法的有效性，本文将聚类算法研究中广为采用的聚类精度（Clustering Accuracy，ACC）、调整互信息系数（Adjusted Mutual Information，AMI）、ARI这三个指标作为聚类算法性能度量评价标准［16～17］。其中，ACC与AMI的取值范围均为[0,1]，ARI的 取值范围为[- 1,1]，各指标值越大，越表示聚类质量越高。本论文算法与其他算法对样本数据进行验证，三个指标的比较结果见表6。

表6 各算法有效性比较

综上所述，本文算法能够克服高维数据对聚类过程的不利影响，聚类结果区分性强且聚类有效性高，能够应用于科技创新人才的实际分类问题。

6 结语

本文针对科技创新人才分类问题，运用定性与定量相结合的方法，先通过资料收集和调研问卷的方式整理制定出相关科技创新人才的评价指标体系，然后提出IKDPC算法对样本指标进行聚类分析，与传统聚类方法相比，该方法能够对高维数据降维，提取指标维数中的主成分指标，并且给出了新的适用于任意数据集的局部密度计算方法，以及两种不同的剩余点分配策略。采用本文方法对科技创新人员进行聚类分析，充分挖掘聚类信息，客观合理地将科技创新人才进行分类，对不同类别的科技创新人才制定不同的培养计划，能够为科技创新人才培养过程中的分类提供科学化的决策支持。本文方法具有一定的通用性，也可以用于其他类似人员的分类问题，例如医学人才分类、军事人才分类等。