1 绪论
1.1 研究背景与意义
人们对数据感到不知所措，世界和人民生活中的数据似乎在不断增加并且看不到尽头，无所不在的计算机使得保存先前可能已经破坏过的东西变得容易，廉价的磁盘和在线存储使得推迟决定如何处理所有这些东西变得简单起来。近年来，数据库的无限制增长，使数据挖掘成为新业务技术的前沿领域。数据挖掘(Data Mining)技术是通过分析数据库中已存在的数据来解决问题，数据挖掘过程是发现数据模式的过程，该过程必须是自动的（或更常见的）或者是半自动的，发现的模式必须具有意义，因为它们会带来一些优势，通常是经济优势。
聚类(Clustering)是最基本的数据分析工具之一，具有广泛的应用前景。它可以作为一个独立的数据挖掘任务来揭示数据的内在特征，或者作为一个预处理步骤，将聚类结果进一步用于其他数据挖掘任务，如分类、预测、相关分析和异常检测。目前已经在数据挖掘、机器学习、模式识别以及科学、工程、社会、经济和生物医学数据分析等各个研究领域都对聚类进行了广泛的研究。根据其技术和思想的不同，聚类被分为图论聚类[1]、模糊聚类和动态聚类。聚类分析技术用于发现数据集中的自然群，并识别可能存在于其中的抽象结构，而不需要对数据的特征有任何背景知识。它们被广泛应用于生物信息学、计算机视觉、数据挖掘、基因表达分析、文本挖掘、超大规模集成电路设计[2]和网页聚类等领域。
在一般情况下，监督学习算法在聚类方面的准确率是优于无监督学习算法的。监督学习算法具有分类精度高的优点，但对有标签的样本集必须进行研究，这些样本集是由专家标记的，而且非常有限，成本比较高昂。相反，无监督学习算法可以处理大量的未标记样本，但分类精度较低。所以，监督学习算法尽管准确率很高，但是其在实际的应用中受到了很大的限制。于是，运用少量的监督信息来辅助聚类过程，提升聚类性能逐渐获得了研究人员的关注，并成为研究的热点内容。这也正是半监督学习算法的研究内容，半监督学习[3]提供了一个强大的框架，
用于在数据标签有限或获取标签的成本高昂时。与所有样本数据都需要标签的监督学习算法不同，半监督学习算法还可以使用未标记的样本数据来提高其性能。半监督算法通常提供一种从未标记的样本数据中了解数据结构的方法[4]，从而减少了对标签的需要。
..............................
1.2 国内外研究现状
1.2.1 谱聚类算法国内外研究现状
谱聚类是一种基于代数图论的聚类方法。近年来，由于其坚实的理论基础以及集群的良好表现，引起了学术界的广泛关注。谱聚类的最早研究始于 1973 年，Donath 和 Hoffman 提出了用邻接矩阵的特征向量来构建图分割[18]。同年，Fiedler证明了图 Laplacian 矩阵的第二特征向量与图的二路划分密切相关[19]，建议使用拉普拉斯第二特征向量进行图分割。Hagen 和 Kahng 发现了聚类、图划分和相似矩阵的特征向量之间的关系，并构造了一个相对比较高效的算法，他们在 1992年提出了比例割集准则[20]。2000 年，Shi 和 Malik 提出了标准割集准则[21]，此方法不仅考虑了集群之间的外部连接，还考虑了集群内部的连接，因此可以生成平衡的集群结果。然后，丁等人提出了最大最小割集准则(min/max cut)[22]；Ng 等人提出了经典的 NJW 算法[23]，这些算法是基于矩阵谱图理论对数据点进行分类的，因此称为谱聚类。自 2000 年以来，在数据挖掘领域，谱聚类被越来越多的人关注。到现在为止，谱聚类在计算机视觉[24-25]、集成电路设计[26]、负载平衡[27-28]、生物信息[29-30]和文本分类[31]等领域都有所应用。由于谱聚类的发展，在解决聚类的问题时又加了一些新的思想，因为谱聚类算法可以被很好地应用于实际问题，所以这对谱聚类算法的研究将会带来很大的价值。下面是对谱聚类算法的相关研究：
(1) Laplacian 矩阵的构造：拉普拉斯矩阵有两种，第一种是归一化拉普拉斯矩阵，归一化拉普拉斯矩阵包括对称形式和随机游走形式；第二种是非归一化拉普拉斯矩阵。Mohar 介绍了非归一化拉普拉斯矩阵的一些特征[32]。Shi 和 Malik研究了归一化拉普拉斯矩阵的特征[21]。拉普拉斯矩阵的谱为图分区提供了非常有用的信息。Luxburg 对拉普拉斯矩阵的特征进行了全面的总结[33]。是否应该使用非正规拉普拉斯矩阵或归一化拉普拉斯矩阵仍在讨论中。Ng 等人提供了归一化拉普拉斯矩阵更适合于谱聚类的证据[23]，这意味着归一化谱聚类的性能优于非归一化谱聚类。Higham Kibble 也指出，在某些条件下，在谱聚类中用非归一化拉普拉斯矩阵可以产生更好的聚类结果[34]。而 Luxburg 等人证明，从统计一致性理论的角度来看，归一化拉普拉斯矩阵的性能要优于非归一化拉普拉斯矩阵[35]。
(2) 聚类数目的确定：在大多数谱聚类算法中，必须人为的设置聚类的数量，并且聚类数目的确定对初始化非常敏感。如何准确估计聚类的数量是谱聚类面临的主要挑战之一。一些现有方法试图通过最小化聚类内部的一些基于距离的非相似性度量来获得最佳聚类数。Wang 提出了一种新的选择准则，其核心思想是选择集群数量作为聚类稳定性的最优值[36]。聚类稳定性的概念可以度量任何给定聚类算法的鲁棒性。受 Wang 方法的启发[36]，Fang 和 Wang 开发了一种基于bootstrap 的聚类不稳定性估计新方案，该方案中通过选择聚类的数量，使得相应的估计聚类不稳定性最小化[37]。Tepper等人介绍了一种感知驱动的聚类方法[38]，通过设置控制错误检测平均数的参数? 自动确定簇的数目。检测阈值很好地适应于接受/拒绝非集群数据，并且可以帮助找到正确的聚类数量。该方法只考虑点间距离，没有随机步长。
................................
2 聚类基础理论
2.1 聚类分析技术
2.1.1 聚类概念及相关定义
聚类是一种统计数据分析技术，它将相似的数据组合在一起，以识别数据中有用的模式。它是一种无监督学习模式，可用于植物和动物分类衍生、基因表达分析、异常值检测、降水预报验证、信用卡使用异常检测等。聚类可以被看成是最重要的无监督学习问题；因此，与其他所有此类问题一样，它所做的是在无标签数据集合中找到相应的结构。在某种程度上，将一系列对象组织为成员相似的类的过程称为聚类。对于一组对象来说，它们之间是“相似的”，而他们与属于其他组的对象则是“不相似”的。然而，聚类的完整定义并没有达成一致，一个经典的定义如下：
(1) 同一类别中的对象必须尽可能地相似；
(2) 不同类别中的对象必须尽可能地不同；
(3) 相似度和相异度的测量必须明确，且具有实际意义。
聚类分析是在相似性的基础上对对象、个体或变量进行识别和分类，它寻求最小化组内方差，并在组方差之间最大化。聚类分析的结果是多个具有相似内容的异构组，单个组内的个体相似，而不是组与组之间的实质性差异。聚类分析仅基于描述对象及其关系数据中的信息对数据对象进行分组，它的目标是使组内的对象彼此相似（或相关）并且与其他组中的对象不同（或不相关），聚类结束后组内对象越相似，组之间的差异越大，聚类越好或越明显[67]。数据可以被认为是空间中的点，其中坐标轴对应于变量。聚类分析将空间划分为区域，这是在数据中所发现的组的特征。聚类的主要优点是自动从故障中恢复数据，即在没有用户干预的情况下恢复。聚类的缺点是复杂度过高和无法从数据库损坏中恢复数据。对象的有序列表，具有集群的一些共同特征，如这些对象属于一个区间。两个集群之间的距离涉及两个集群的部分或全部元素，通过聚类方法可以确定如何计算距离，而相似度度量可以用来表示文档之间的相似度。
.............................
2.2 谱聚类理论及算法
谱聚类是聚类分析中一个非常热门的研究领域，它的主要思想是通过图拉普拉斯矩阵的特征分解得到图的划分，是一种基于图划分的聚类方法。本章主要从谱聚类的谱图理论、图划分方法、谱聚类算法以及目前谱聚类所存在的问题进行介绍。
2.2.1 图划分准则
聚类问题可以表示为在图上的划分问题，划分成的结果尽量使得两个子图之间的相似度最小，内部相似度最大，其聚类结果的优劣与划分准则的好坏直接相关，如图 2-2 所示，通过一种划分策略，可以将 H 单独划分为一类，其他所有点划分为另一类；或者可以通过另一种划分策略，将 H、A、B、C 划分为一类，而D、E、G、F 划分为另一类，很显然，第二种划分策略可以将无向图划分为比较均衡的两类。常见的划分准则有最小割基准则(Minimum cut)，规范割集准则(Normalized cut，Ncut)，比例割集准则(Ratio cut)，平均割集准则(Average cut)等。
.............................
3.1 半监督谱聚类的介绍..................................... 22
3.2 成对约束谱聚类算法........................................ 25
4 基于 Bethe Hessian 矩阵的主动学习算法 .......................... 35
4.1 基于 Bethe Hessian 矩阵的谱聚类算法................................... 35
4.2 主动选择策略............................. 39
5 总结与展望 .......................................... 48
5.1 总结................................... 48
5.2 展望................................... 48
4 基于 Bethe Hessian 矩阵的主动学习算法
4.1 基于 Bethe Hessian 矩阵的谱聚类算法
.............................
5 总结与展望
5.1 总结
本文主要针对约束谱聚类算法展开了研究。首先介绍了聚类方面以及谱聚类方面的背景知识，然后分析了现阶段这些算法的国内外研究现状，最后提出了一种新的约束谱聚类算法，基于共享近邻的成对约束谱聚类算法，该算法不仅提升了之前聚类算法在密度相差较大的簇中的聚类效果，而且相对现有算法具有更优的聚类性能。同时，为了解决聚类数目不确定问题和尺度参数敏感问题，本文将Bethe Hessian 矩阵用于谱聚类算法中，并用一种主动选择策略动态的选择约束对，使约束谱聚类算法更灵活，本文将 Bethe Hessian 矩阵谱聚类算法和主动选择策略相结合，可以形成一种有效的约束谱聚类算法，即解决了之前聚类算法无法解决的问题，又具有良好的聚类效果。具体的研究成果如下所述：
(1) 提出了一种基于共享近邻的成对约束谱聚类算法
通过分析现有的聚类算法和谱聚类算法的相关研究内容，指出了谱聚类算法存在的一些问题。即传统谱聚类算法无法很好地在密度相差较大的簇上进行聚类，本文利用了样本对之间的共享近邻信息改善了谱聚类存在的上述问题，同时将约束信息加入谱聚类中，以满足实际的聚类需要。最后通过在 UCI 标准数据集上的实验结果证明基于共享近邻的约束谱聚类算法可以取得更好的聚类效果。
(2) 提出了一种基于 Bethe Hessian 矩阵的主动约束谱聚类算法
现有的聚类算法依然无法很好的处理聚类数目不确定问题和尺度参数敏感问题，谱聚类算法的提出也并没有改善聚类中存在的这些问题。基于 Bethe Hessian 矩阵的主动约束谱聚类算法提出将 Bethe Hessian 矩阵代替谱聚类中的拉普拉斯矩阵，不仅解决了聚类数目难以确定的问题，也消除了参数对聚类性能的影响。并且在该算法中引入了非回溯矩阵，证明出了正则化参数具有可以确定的解，即可以通过谱径来求解正则化因子的值。该算法提出了一种新的主动选择策略，经过约束矩阵和聚类向量的多次迭代，通过最大化误差函数求解出每一步需要查询的样本对，将样本对的约束标签加入到约束矩阵中，最终求出聚类指示向量。主动选择策略在鲁棒性上优于随机选择策略，增强了聚类结果的稳定性。将主动选择和 Bethe Hessian 矩阵相结合，即解决了其他聚类算法无法解决的参数敏感和聚类数目难以确定问题，也提升了聚类的性能。