图上的快速分类、聚类算法研究

In the past decade, researchers in the machine learning community have paid great attentions to graph-based learning methods. Many successful graph-based methods have been proposed for tasks such as semi-supervised learning, clustering, dimension reduction etc. However, typical graph construction methods have a running-time complexity of O(n^2) where n is the number of data points, and graph-based learning methods have a time complexity of O(n^3), thus, cannot be directly used for large-scale applications. In this research, we aim to address this computational challenge by designing graph-based methods with linear or near-linear complexity. Based on methods of graph sparsification, we approximate general graphs by a much simpler one, then design fast clustering and classification algorithms by tools of random algorithms and approximation algorithms. Using tools of spectral graph theory, we will analyze the error bound of the approximation and time complexity of the proposed algorithm. Finally, we will apply our methods to real world applications such as image segmentation and webpage classification.

过去十五年中，机器学习和模式识别领域对基于图的学习算法给予了极大的关注，产生了大量有代表性的工作，如：非线性降维、谱聚类、基于图的半监督学习等。然而，典型的对向量数据构图方法的时间复杂性为O(n^2)(n为样本数量)，典型的基于图的机器学习算法的时间复杂性为O(n^3)，因此无法在大规模实际问题中使用。本研究以改进现有构图算法和基于图的学习算法的复杂性为目的，旨在设计实现具有线性O(n)或近似线性O(n*log^k(n))(k为常数)时间复杂性的图算法，从而满足千万以上规模数据的应用的需要。实现上，我们将以近似算法和随机算法为主要工具、以对图结构进行稀疏化近似为核心方法来设计快速的构图算法以及图上的聚类、分类算法。此外，我们还将详细分析算法的时间和空间复杂性以及近似算法产生的误差。最后，我们将探索这一研究在网页分类和图像分割等问题中的应用，从而推动基于图的机器学习方法的实用化。

一直以来，基于图的机器学习方法在两方面存在着较严重的问题：第一，由于往往需要进行graph Lalacian matrix求逆、特征值分解等操作，计算复杂度较高；第二，方法性能通常不够稳定。在本项目中，我们从构图和基于图的机器学习方法两方面入手，针对这两个问题进行了较为深入的研究，并取得了一些积极的成果。针对计算复杂性问题，我们提出了基于Locality Sensitive Hashing的快速构图方法以及基于图的稀疏近似的快速分类方法。针对鲁棒性问题，我们提出了基于局部关系保持的构图方法，以及从理论和试验上证明基于最小张成树近似的半监督学习方法对与构图参数的鲁棒性。这些成果改进或超越了该领域现有的方法，为推进基于图的半监督学习方法的实用化做出了贡献。具体来说，我们在快速半监督分类方面的两个工作比传统方法在速度方面提升100倍以上，比现有快速方法速度提升10倍以上；并且，我们从理论和实验两方面验证了方法对构图参数的鲁棒性。目前，这两个工作已经分别在TNNLS（CCF B类）和AAAI（CCF A类）上发表，且相关算法已经开源；我们将这些方法应用于文档二值化、自然场景中的文字提取，交互式图像分割等问题中取得了良好的效果。在构图方法研究方面，我们关于快速构图和鲁棒构图的两个工作分别在ECML（CCF B类）和IEEE Transactions on Cybernetics（CCF B类）上发表。.此外，我们还与他人合作在计算机视觉、数据挖掘、信息安全等领域完成了一系列工作，这些工作发表在Pattern Recognition, IJCNN, Signal Processing Letter等主流国际期刊和会议上。