中文摘要：

分类是机器学习中最为基础和核心的研究内容，但是传统的分类方法往往存在着前提假设过强或者先验知识要求过多等限制条件。图上的随机游走作为一种直观易理解又应用广泛的数学理论，为研究者们提供了一条崭新且具有充分潜力的解决途径。本项目研究将图上的随机游走作为一项基本技术，为带无标签数据和不带无标签数据的两种分类问题分别提出一种基于图上随机游走的解决方案，即多层次随机游走标签传播学习模型和随机游走分类器模型。这两种分类模型不但能分别覆盖大部分的标签传播半监督学习算法和多数基于核方法和流形一致性假设的分类器，而且我们还可以在此基础上，进一步结合其统一的几何表示、代数解析以及正则化理论，设计新的标签传播算法和随机游走分类器。本项目的研究可以为图上随机游走学习提供坚实的数学理论基础，提高已有分类算法的效率和性能，并大大推动图上随机游走在机器学习和数据挖掘领域应用的成熟性和广泛性。

结论摘要：

分类是机器学习中最为基础的核心研究内容,但是传统的分类方法往往存在着前提假设过强或先验知识要求过多等限制。图上的随机游走作为一种直观易理解又应用广泛的数学理论,为研究者们提供了一条崭新而具有潜力的解决途径。本项目研究将图上的随机游走作为一项基本技术,为带无标签数据和不带无标签数据的两种分类问题分别提出一种基于图上随机游走的解决方案。 我们提出一种基于图上随机游走的半监督学习模型。该随机游走半监督学习模型不但具有直观的几何解释，统一的代数表达形式，而且还有正则化理论的支持。从这一学习模型，我们可以从理论上设计和分析更高效的半监督学习算法。 我们设计一种基于图上随机游走的多层组件传播算法，该算法具有清晰的时间序列上的状态转化、更好地利用已知标签数据、并且能以较快的速度保证收敛性，从而取得更好的学习性能。我们提出了一种多层组件传播的半监督分类算法，不仅证明了算法的解的收敛性，还与其它算法进行比较，从实验上验证其性能的优越性。 我们提出一种基于图上随机游走的分类器模型。该随机游走分类器模型覆盖了大部分具有二次形式的分类算法，统一大量基于核方法和基于流形一致性假设的分类器，并进行正则化方面的扩展。在此模型下设计了监督式谱空间分类器，通过引入中间流形桥，取得了比其他多种著名分类器具有更加优越的分类性能。 我们提出了一种基于图上随机游走的分类器模型的组合随机游走分类器框架，尽最大可能地有效利用了训练数据信息，减少训练数据中噪声干扰。在该框架下使用懒散游走分类器设计了一种优化的组合懒散分类器，并将其用于亚细胞中蛋白质定位预测，取得了比SVM等预测方法更好的结果。 我们提出了一种基于图上随机游走的半监督学习模型的多种群蚂蚁半监督分类算法。该算法通过蚂蚁种群信息素的变化来动态更新随机最大生成树，从而达到逐步逼近数据内在流形结构，取得比标签传播等半监督算法更好的分类效果。 我们设计了一种基于双层随机游走的半监督聚类算法，用于处理既有必连约束又有不连约束的多类别半监督聚类问题。该算法通过建立受限的随机游走模型来确定每个点对约束的影响范围和影响程度。在大量数据集上的实验结果表明我们的算法优于同类半监督聚类算法。 我们还将随机游走学习的上述理论成果应用到社交网络发现、中医药数据挖掘、蛋白质定位预测、生物序列挖掘、并发系统建模等领域中，取得了很好应用效果。