核k-means优化方法研究

作     者：樊淑炎 

作者单位：中国矿业大学 

学位级别：硕士

导师姓名：许新征

授予年度：2017年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：核k-means算法 混合蛙跳算法 聚类有效性指标 混合核函数 相似性度量 聚类分析 

摘      要：聚类分析是数据挖掘研究的重要内容之一,是识别数据内在结构的一种重要手段。k-means算法具有简单高效的特点,成为被广泛研究的聚类算法之一。由于现实数据的复杂流形分布,基于欧氏距离的k-means算法不能很好地处理。作为一种基于核的聚类算法,核k-means算法可以有效地处理非线性可分的数据。如何提前确定聚类数目、选择核函数及确定核参数,是影响核k-means算法性能的关键因素。另外,随着数据量的增大,需要花费更多的时间以及内存满足核k-means算法运行的需求。所以本文从以上几个方面着手,对核k-means算法进行研究以提高其性能,本文的主要研究内容如下:首先,针对利用经验值确定聚类数目和核参数的盲目性,本文提出了一种基于混合蛙跳算法的自适应核k-means算法(Self-adaptive Kernel k-means Algorithm based on the Shuffled Frog Leaping Algorithm,SFLA-SAKKM)。并且根据数据集的内在结构设计了一种适用于核空间的有效性指标KBWP(Kernel Between-Within Proportion)。将聚类数目和核参数看作青蛙的位置信息,将KBWP指标看作适应度,利用混合蛙跳算法进行局部和全局优化,直到达到最大迭代次数。最大适应度对应的聚类数目和核参数是最佳的。实验结果表明SFLA-SAKKM提高了核k-means算法的性能。其次,本文研究使用混合核函数解决核k-means算法的核函数选择的问题,混合核函数将学习能力强的局部核函数和泛化能力强的全局核函数进行线性组合,运用到核k-means算法中,提出了混合核k-means算法(Hybrid Kernel k-means)。为了进一步解决核k-means算法在处理大规模数据时存在计算复杂度高,内存需求大的问题,本文从数据集中随机采样若干个数据点,数量远远小于数据点总数,在采样数据点和所有数据点之间构造一个核矩阵,然后运用Nystr?m的思想逼近整个数据集的核矩阵,来降低算法的复杂度,进而提出了求解大规模数据的混合核k-means算法(Hybrid Kernel k-means for Large Data)。再次,通过考虑数据集的局部和全局结构,本文提出一种新的基于相似性度量的局部多核k-means算法(a Novel Locally Multiple Kernel k-means based on Similarity Measure,LMKKM),以解决具有复杂结构或多尺度的数据集的聚类问题。本文提出的相似性度量满足聚类假设的要求,通过考虑局部和全局结构更合理地描述数据点之间的关系。先根据局部分布,为每个数据点自适应地生成高斯核的局部尺度参数。为了兼顾数据集的全局结构,引入密度因子。实验表明LMKKM可以有效地处理具有复杂结构或多尺度的数据集的聚类问题。最后,总结本文提出的核k-means优化方法,对核k-means算法的下一步研究进行了展望。