【作者】 张强；

【导师】 徐沁；

【作者基本信息】 安徽大学 ， 计算机科学与技术， 2020， 硕士

【摘要】 过去几十年,研究者们提出了大量适用于硬聚类的聚类有效性指标。然而,现有的聚类评价方法会受到各种数据特征的影响。例如,带有噪声的数据、不同密度的数据、任意形状的数据等等都可能影响内部指标的性能。针对以上问题,本文在分析影响聚类算法性能的主要因素的基础上研究了聚类有效性评价,提出了三种新的聚类有效性内部指标。主要工作内容如下:(1)为了克服现有的度量方法作为单连接聚类的簇内紧密度的缺点,本文使用最小生成树的最长边作为簇内紧密度,提出了一种针对单链接算法的综合聚类有效性指标(synthetical clustering validity index,简称SCV)。该指标根据统计方法的不同又可以分为amSCV、gmSCV两种。(2)SCV指标在评价单链接算法时表现良好,但是不适用其他层次聚类算法。为此,本文提出了一种广义综合聚类有效性指标(generalized synthetical clustering validity index,简称GSCV)。该指标采用自适应相似性度量策略对聚类结果进行评价,避免了聚类算法与内部指标之间的相似性度量方法的不兼容性造成的内部指标性能下降的情况。根据统计方法的不同,GSCV指标又可以分为amGSCV、gmGSCV两种。本文分别在15个模拟数据集(具有不同维数、空间分布、重叠度和规模)和4个真实数据集上验证新指标的性能,并与其他七个常用的内部指标进行了对比。实验结果表明:SCV、GSCV指标能够准确获取在簇密度、偏态分布、几何结构等方面不同的数据集的最优聚类数目。(3)SCV指标和GSCV指标可以统一为一个聚类有效性指标框架(Hierarchical clustering validity framework,简称HCVF)来评价层次聚类。然而,由于HCVF建立于层次聚类算法生成的层次结构基础之上,因此该框架只能用于评价层次聚类算法生成的聚类结果。为解决这一问题,本文对子类概念进行了延伸以使新指标能够适用于非层次聚类算法。此外,本文引入了图论对HCVF框架进行了改进,该方法在捕获数据集的空间结构的同时降低了新指标使用的时间复杂度。改进后的聚类有效性指标(Graph-based clsutering validity index,GBCV)继承了HCVF框架的优点,并且适用于非层次聚类算法、大幅度降低了使用内部指标的时间复杂度。本文分别在12个模拟数据集(具有不同维数、空间分布、重叠度和规模)和6个真实数据集上验证新指标的性能,并与其他七个常用的内部指标进行了对比。实验结果表明:GBCV指标能够准确获取在簇密度、偏态分布、几何结构等方面不同的数据集的最优聚类数目。更多还原

【Abstract】 In the past few decades,researchers have proposed a large number of clustering validity indexes suitable for hard clustering.However,the existing validity methods are affected by data characteristics.For example,noise,density,geometry shape,etc may affect the performance of internal index.In view of the above problems,this thesis analyzes the main factors that affect the performance of clustering algorithm and further studies clustering validation,and proposes three new internal indexes.The main work content is depicted as follows:(1)To overcome the disadvantages of the existing measurements as the intra-cluster compactness for the single-linkage agglomerative hierarchical clustering,this thesis uses the longest edge of the minimum spanning tree as inter-cluster compactness,and put forward a synthetical clustering validity index(SCV)for single-linkage algorithm.According to the different statistical methods,this index can be divided into am-SCV and gm-SCV.(2)SCV index performs well in evaluating single-linkage algorithm,but it is not applicable to other hierarchical clustering algorithms.To this end,this thesis proposes a generalized synthetical clustering validity(GSCV)index.This index adopts the self-adaptive similarity measurement strategy to evaluate the clustering results,which avoids the performance degradation of the internal index caused by the incompatibility of the similarity measurement method between the clustering algorithm and the internal index.According to different statistical methods,GSCV index can be divided into am-GSCV and gm-GSCV.This thesis verifies the performance of the new indexes on 15 artificial datasets(with different dimensions,spatial distribution,overlap,and size)and 4 real datasets,and compare them with seven other commonly-used internal indexes.The experimental results show that SCV and GSCV index can accurately obtain the optimal clustering number of clustering results of different data sets with different density,skewness distribution and geometric structure.(3)SCV and GSCV index can be unified into a hierarchical clustering validityframework(HCVF)to evaluate hierarchical clustering algorithms.However,HCVF is based on the hierarchical structure generated by hierarchical clustering algorithms,so the framework can only be used to evaluate the clustering results generated by hierarchical clustering algorithms.To solve this problem,this thesis extends the subclass concept so that the new index can be applied to non-hierarchical clustering algorithm.In addition,this thesis introduces graph theory to improve the HCVF framework,which can not only capture the spatial structure of the data set,but also reduce the time complexity of using the new clustering validity index.The improved graph-based clsutering validity index(GBCV)inherits the advantages of the HCVF framework.Moreover,it is suitable for non-hierarchical clustering algorithm and greatly reduces the time complexity of using internal index.This thesis verifies the performance of the new indexes on 12 artificial datasets(with different dimensions,spatial distribution,overlap,and size)and 6 real datasets,and compare them with seven other commonly-used internal indexes.The experimental results show that SCV and GSCV index can accurately obtain the optimal clustering number of clustering results of different data sets with different density,skewness distribution and geometric structure.更多还原