-
谱聚类算法的思想来源是图论，是组成组合数学的不可或缺的一部分，经过这几年进一步的研究，图论已然具有了长足的发展，现在已经成为了数学分支中的一大支撑点。图论具有很长很长时间的的研究历史，是传播极为广泛的一门古老学科。图论的研究起点不像其他理论一般有争议，著名的Konigsberg的七桥问题就是它公认的起源，除了它延伸出的各种科学理论以外，图论本身也具有无穷的魅力，经久不衰。到了今天的信息社会，仍旧有很多的的学科领域不得不涉及到图论的知识，比如涉及到计算问题的计算机、运筹学、物理学等学科，还有许多我们联想不到的学科也同样离不开图论的知识，其中包含了系统工程学、电子学，甚至连生物学、化学等领域图论都有着十分广泛的应用，因此所有与图论相关的领域的学者们对其也越来越重视和关注。26996
- 上一篇：运动目标的检测与跟踪文献综述和参考文献
- 下一篇：道路检测技术文献综述和参考文献
从2000年被提出到现在，以图论为基础的的机器学习算法已经一跃变身为机器学习领域的新宠。而谱聚类算法正是分割方法中以图论为基础理论的。它是用附加权值的无向图的节点来和数据点一一对应，把图中包含的节点视为样本的数据点来处理问题，至于数据点特征之间的相似性则利用边的权重作为代表，最后利用某种分割准则得到数据的最佳二文划分。论文网
在谱聚类理论的发展历史中，是Wu与Leahy第一次提出了最小切（min-cut）准则的概念，然后同样作为初创者在图像分割领域使用了这一准则[1]。可惜的是最小切准则作为一种新提出的理论，无可避免的存在许多不足之处，比如它只考虑到将每一个类别外部的连接进行最小化处理，却在类别内部的连接上没有深入思考，这直接导致了划分后非常容易产生划分结果失衡。文献[9]中第一次从基础理论的基础上将图的划分问题应用到了处理与相似矩阵中相关的特征向量的相关问题上，即矩阵的谱分析理论。紧接着又有人在进行图划分的过程中解决图的量化分问题时有了新发现，采用了拉普拉斯矩阵的第二特征向量，并且取得了意想不到的喜人效果[17]。除了理论上的突破，人们开始将这一发现引用到实际应用中来，将相似矩阵有关的特征向量进一步进行了探究，成功地将其从图划分问题推广到了聚类等问题的解决上来，为了解决类间相似度的最小化问题，又提出了ratio-cut算法之后又将其引入类规模的平衡项中，直接促成了基于矩阵分析的聚类算法的提出，还在VLSI设计中也引入了一种目标函数的图划分算法，在ratio-cut准则的基础上对其展开了研究［18]。
后来在考虑了数据各个类别内部的基础上，再结合各个类两两之间的非相似性，Shi等人提出了一种新的准则－－规范切准则[2]，这一成果在数据聚类方面的研究上做出了巨大的贡献，同时也使图像分割的效果得到了明显的优化。在此之后，多个领域的学者开始对基于图论的机器学习算法的研究感兴趣，口口相传后又吸引了大量学者关注这一领域，也因此促进了这一领域得到了飞速的发展，其中仅最优图划分准则方向上就产生了许多新的理论，如等周切准则（Isoperimetric-cut）[3]就是其中之一，在原有研究的基础上开阔了科研的思路，除此之外还有率切准则（Ratio-cut）[4]同样值得我们重视，最小最大切(Min-max-cut)[5]虽然在时间点上比较靠后，但是基本也属于该时期发展的产物。再后来的这些准则又在此基础上被后人加以研究，随着科研需求，各自被推而广之运用到了多文模式[6-8]。其中最小化多文划分准则的发展尤其值得一提，按照一定的分法它可以归结为一个NP-hard（Non-deterministic Polynomid-time hard）[9]问题。经过很多实验的研究加以使用后，N-cut准则的性能得到了大家的肯定。正是因为它优秀的性能，N-cut准则的应用面变得十分宽广。图划分准则一般负责多特征问题的处理，标准谱聚类算法处理的问题正好于此相反，负责的是二分问题，其中类别的划分中仅仅利用一个特征向量，在处理多分类问题的时候只需要将二分过程迭代调用就可以将之完成了。但是这样做也有其相应的缺点，由于决定划分使用的特征向量只有唯一一个，因此处理的效率十分低下而且还伴随着不稳定的特点，应用起来限制条件很多。在这种情况下K-way谱聚类算法因运而生，它的出现正是为了解决二分谱聚类算法的这些缺点，它能够在类别的划分过程中按照用户需求同时使用多个特征向量，能够在最大程度上接近最优k-way划分得到的结果，还可以大大改善因为信息的丢失而导致一系列问题，很大程度上增加算法的稳定性，其中有个十分注明的算法即Yu和Shi提出的能够完全体现k-way算法优势所在的一种多分类的谱聚类算法[8].这几年，谱聚类算法的基础理论方面的研究也引起了各个领域的佼佼者的重视，比如Ng等人在分析谱聚类算法的方面就做出了很大的贡献，他们将矩阵的扰动理论[7]引入到谱聚类的基础理论中来，建立了一个相对完善的体系，即在不发生特殊事件的条件下给出了谱聚类算法能够推广使用并且可以保证结果成功的条件；Brand和Huang[10]在解释特征尺度化特征向量的时候想到了一种新的思路，以极化理论为出发点，成功找到了一种采用一一映射方式实现的聚类算法；还有一些学者在研究中总结了一些谱聚类算法中经常需要的用到的简单概率解释，其中比较有代表性的要数Meila和Shi两位；Markov的随机游动边流理论[20]中将数据点间的相似关系给出了更加清晰的定位，以此理论为基础针对谱聚类中规范化的相似矩阵 展开了讨论，将其确定为为该Markov链一一对应的概率相关转移矩阵，并且还从概率论的角度利用随机游动方面的研究成果对N－cut算法提出了一个新的解释，并由此产生了一种以随机游动为基本准则的全新算法。不仅如此，他们还提出了一些自己的新的想法，即关于多个特征相似矩阵组合的与之前提出的框架联系在一起的综合谱聚类方法，最终在图像分割领域同样得出了非常可信的效果。不仅如此，谱聚类算法的发展应用领域变得越来越广泛，也从图像分割领域扩展到图像检索及文本挖掘领域中，文献[30]将谱聚类算法应用于图像检索，有效的缩小了检索范围，提高了检索效率及准确度。致力于文本分类领域的专家们提出了一种基于的潜在语义分析技术[31]，还有一种直推式谱聚类算法的文本分类算法，并且在运行后取得了很好的效果。