● 摘要
聚类作为无监督学习方法，是数据挖掘的一项重要技术。随着大数据的涌现，聚类分析方法在大数据分析中得到关注。划分式聚类是最常用的一种聚类方法，如何有效确定初始聚类中心成为划分式聚类算法的关键；外部评价指标是常用的评价聚类算法性能的指标，然而当聚类结果存在类偏斜现象时，传统外部评价指标无法对其有效性进行度量。如何对存在类偏斜的聚类结果进行有效评价亟需解决。本文针对K-medoids聚类算法的初始中心选择方法，及现有聚类外部评价在评价类偏斜问题时的缺陷进行研究，主要工作及创新点如下：
提出一种Num-近邻方差优化的K-medoids聚类算法。该算法利用样本所处位置的局部样本分布信息，通过计算样本的局部方差，选取方差最小的样本作为K-medoids的初始中心，充分利用了方差隐含的对象结构信息，将密集区域的样本作为K-medoids聚类算法的初始中心。UCI数据集和人工模拟数据集的实验表明，该算法具有良好的聚类效果，较强的抗噪性能，而且适用于较大规模数据集的聚类分析。
提出方差优化初始中心的K-medoids算法，该算法分别以距离均值和相应样本的标准差为邻域半径，选取方差值最小且其间距离不低于邻域半径的样本为K-medoids的初始聚类中心。UCI数据集和人工模拟数据集的实验表明，该算法花费较少的时间可以得到结构更加紧密的类簇，且适用于较大规模数据集。
提出一种基于相依表的外部评价指标和两种基于样本对的外部评价指标。基于相依表的新指标同时考虑灵敏度和特异度，将特异度引入聚类性能评价，以期避免现有外部评价指标因为没有考虑特异度信息而造成的无法度量聚类结果中的类偏斜现象，且适用于评价任意分布数据集的聚类结果。利用样本对信息定义敏感度、特异度和精度，并利用新定义的敏感度、特异度和精度定义两种基于样本对的外部评价指标。UCI数据集和人工模拟数据集的实验表明，新提出的基于相依表的指标可以评价有类偏斜现象的聚类结果的有效性，基于样本对的外部评价指标评价聚类结果更加客观，其中基于样本对新指标中引入特异度的外部评价指标是一种较为理想的评价方法。