图上的随机游走学习

论文摘要

传统的处理机器学习和数据挖掘问题的方法都需要很强的前提假设或者大量的先验知识,所以当现实问题与前提假设不一致时或者先验知识不足够时就会导致传统方法性能的降低。近年来大量的令传统方法无能为力的学习问题不断涌现出来,而随机过程中的随机游走(Random Walk)就是处理这类棘手问题的一种有效方法。随机游走在计算机学科的信息检索领域已经得到了成功的应用,现在正被越来越多地应用到机器学习和数据挖掘等领域。在此背景下,我们提出图上的随机游走学习,创造性地将随机游走作为一项基本技术,用于改善传统的有监督学习,半监督学习和无监督学习中的困难问题,本论文的具体贡献如下。(1)随机游走分类器模型。基于图上的随机游走理论,我们提出了随机游走基础分类器模型、互补的随机游走分类器模型、组合随机游走分类器模型,详细地分析了这些模型下的最优分类器的设置和性能,给出了各种模型对应的有效分类器实现方法,从理论上证明了我们提出的组合方法可以大大提升基础分类器的性能。(2)多层随机游走框架。在简单随机游走理论的启发下,我们提出一个统一的半监督学习框架——多层随机游走,通过构建各种组件级的随机游走模型,可以产生一系列对应的多分类标签传播算法。多层随机游走框架不仅囊括了目前为止的绝大多数标签传播算法,而且还能产生更多新的高效的组件传播算法,这些结果被我们从正则化的角度得到进一步的证实。另外针对有标签数据不平衡分布情况,我们提出了一种简单的平衡策略,可用于改进任何标签传播算法的分类性能。实验结果证明多层随机游走框架下的组件传播算法和平衡策略都是非常有效的。(3)随机游走的细胞自动机聚类。借鉴随机游走的思想,受蚂蚁分巢居住行为的启发,使用细胞自动机的形式提出了蚂蚁睡眠模型( )。在此模型上设计一个蚂蚁随机游走聚类算法(RWAC),该算法用人工蚂蚁代表一个数据对象,让整个蚂蚁群体在随机游走中动态地、自适应地、自组织地形成多个独立的子群体,使不同类别的蚂蚁之间相互分离,而同类的蚂蚁之间高度紧密地排列,从而达到对数据聚类的目的。在蚂蚁随机游走聚类算法中我们提出了蚂蚁贪婪游走的策略和对参数的自适应的更新方法,对加快聚类速度和提高聚类质量有非常显著的效果。模拟实验充分显示出,蚂蚁随机游走聚类算法与其它蚂蚁聚类算法相比,在模型上更直观,操作上更简单,具有高效、自组织性和鲁棒性的优点,适用于解决高维、复杂的聚类问题。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 机器学习
• 1.1.1 机器学习的发展阶段
• 1.1.2 机器学习的研究内容
• 1.1.3 机器学习的参考资料
• 1.2 文章涉及的相关技术
• 1.2.1 近邻技术
• 1.2.2 核方法
• 1.2.3 流形学习
• 1.3 随机游走相关知识
• 1.3.1 随机游走
• 1.3.2 图上的随机游走
• 1.4 本文的主要研究工作
• 1.4.1 贡献和创新
• 1.4.2 研究意义
• 1.4.3 文章组织
• 第二章 图上的随机游走理论
• 2.1 背景介绍
• 2.2 随机过程
• 2.3 图论基础
• 2.4 随机游走
• 2.5 拉普拉斯算子
• 2.6 图上的拉普拉斯算子
• 2.7 图上的格林算子
• 2.8 往返时间
• 2.9 应用领域
• 第三章 随机游走分类器模型
• 3.1 背景介绍
• 3.2 符号及基本假设
• 3.3 随机游走基础分类器模型
• 3.3.1 图论表示
• 3.3.2 随机游走分类器
• 3.3.3 互补随机游走分类器对
• 3.4 组合分类器模型
• 3.4.1 互补组合分类器
• 3.4.2 互补懒散组合分类器
• 3.4.3 多划分组合分类器
• 3.4.4 多划分懒散组合分类器
• 3.4.5 懒散组合分类器的损失
• 3.5 随机游走分类器模型的进一步改进
• 3.5.1 核化角度
• 3.5.2 流形角度
• 3.5.3 正则化角度
• 3.6 组合分类算法的实现
• 3.6.1 组合分类算法
• 3.6.2 算法时间复杂度分析
• 3.6.3 多分类的类别判断函数
• 3.7 本章小结
• 第四章 多层次随机游走
• 4.1 背景介绍
• 4.2 多层次随机游走框架
• 4.2.1 多层次随机游走
• 4.3 ML2+组件间随机游走模型
• 4.3.1 与其它Label Propagation 算法的关系
• 4.3.2 MRW 的正则化观点
• 4.4 MRW 组件传播算法MCP
• 4.4.1 MCP 的正则化观点
• 4.5 平衡策略
• 4.6 实验
• 4.6.1 算法演示
• 4.6.2 UCI 数据集上的比较
• 4.6.3 平衡策略的测试
• 4.7 本章小结
• 第五章 基于随机游走的细胞自动机聚类算法
• 5.1 背景介绍
• 5.2 蚂蚁睡眠模型
• 5.2.1 蚂蚁尸体堆积模型
• 5.2.2 蚂蚁睡眠模型
• 5.3 基于随机游走更新规则的细胞自动机聚类算法
• 5.3.1 聚类算法框架
• 5.3.2 参数的设置
• 5.3.3 游走策略的选择
• 5.4 实验结果
• 5.4.1 算法演示
• 5.4.2 人工数据
• 5.4.3 真实数据
• 5.5 本章小结
• 第六章 结束语
• 6.1 全文总结
• 6.2 工作展望
• 参考文献
• 致谢
• 在学期间的研究成果及发表的论文