论文部分内容阅读
在机器学习和数据挖掘领域中,人们常遇到大量的无标记数据。对这些数据进行标记时,可能需要耗费大量的人力物力,如会谈中说话人语音的分割与识别,GPS数据中的道路检测和电影片段中不同男演员或女演员的分组等问题。因此,利用少量样本的先验知识来解决这些问题,已成为机器学习领域的研究热点。半监督聚类(SSC)利用少量样本的监督信息和大量未标记样本进行学习,来完成对数据聚类的。自然地,它也能应用于无监督聚类,以达到提高无监督聚类性能的目的,故半监督聚类已逐渐成为机器学习和数据挖掘中的重要研究内容之一。本文紧紧围绕半监督聚类研究的两个核心─学习算法与度量学习对半监督聚类算法展开较深入的研究。借助机器学习领域中流行的判别分析技术和核技巧,提出了相应的SSC改进模型,并将其拓展到无监督学习方法之中。本文的主要贡献总结如下:(1)提出了基于成对约束的判别型半监督聚类分析方法(DSCA)。该方法从线性判别分析入手,通过利用监督信息和大量无标记样本,同时执行聚类和降维。现有的半监督聚类方法要么只关注监督信息对聚类的帮助,忽略了对数据的降维,要么分离了聚类与降维。DSCA迭代执行聚类和降维克服上述问题,并有机地将聚类和降维刻画在一个联合框架中。同时,通过提出了基于成对约束的K均值聚类方法(PCBKM),克服了成对约束(cannot-link约束和must-link约束)的违反问题。在本文所用数据集上的实验结果表明,在使用相同的成对约束条件下,与其它同类的半监督学习方法相比,DSCA方法相对更有效地提高了聚类性能。(2)借助当前普遍使用的核方法,针对现有的半监督聚类算法难以提高不同聚类样本之间分离性的缺点,提出了基于度量学习的自适应半监督聚类核方法(SCKMM)。该方法主要有以下四个特点:i)将度量学习引入非线性半监督聚类中扩大不同聚类样本之间的分离性;ii)将聚类结果作为迭代执行度量学习和半监督聚类的桥梁,有效地提高聚类精度;iii)针对核聚类算法中核参数调节的手工依赖问题,利用cannot-link约束和must-link约束构造了一个目标函数来自动优化高斯核参数。这种设计理念有助于在简化算法和使数学上易处理的同时,探究超参数对算法推广性能的影响,最终为类似的超参数求解提供了一个可供选择的途径;iv)初步考察了带有噪声的cannot-link约束和must-link约束对半监督学习算法性能的影响。现有的半监督学习算法通常假设给定的成对约束是正确的,并依此进行算法设计,而忽略了带噪声的成对约束。本文采用随机地翻转cannot-link约束和must-link约束,生成噪声成对约束,从而进一步研究带有噪声的约束对算法性能的影响。实验验证了在相同噪声成对约束的条件下,所提出的算法比其它半监督算法更为鲁棒。(3)发展出了一个更为广泛的判别式聚类学习框架,其具有如下特点:i)有效地集成了广义的线性判别分析(GLDA)和正则化软K均值(RSKM)。在该框架下,数据的聚类隶属度取值在0和1之间而不是简单的两个值(0和1)。而由Chris Ding所发展出的线性判别分析引导的自适应维数约减算法(LDA-Km)成为了该框架的特例之一;ii)通过将最大熵作为正则化项,所提出的基于判别分析的正则化软K均值(ResKmeans)方法与其它同类工作相比,更能有效地提高聚类性能;iii)从理论上证明了GLDA和软K均值优化的目标函数的等价性;iv)GLDA推广了著名的线性判别分析方法(LDA);V)ResKmeans不仅推广了同类工作,同时也自然地容纳了现有的聚类方法,包括高斯混合和模糊C均值等。