监督信息在图学习中的有效利用

摘要

基于图的学习方法近年来受到越来越多研究者的关注，它不仅有着深厚的图论理论作基础，而且还指明了数据间的联系与数据本身同样重要这一提高现有学习算法性能的关键。监督信息对于机器学习中的有监督学习和半监督学习，既是重要的信息来源，又是最终的学习目的。
　　本文将对应到图上的监督信息划分为两类——点约束和边约束，并把机器学习中的有监督分类和半监督聚类分别视为具有点约束的学习问题和具有边约束的学习问题，重点从图的角度讨论这两类学习算法对监督信息的利用方式。
　　传统的有监督分类算法用基于属性的方法估计从数据到类别的映射函数，只利用了顶点上的信息。虽然核方法引入了数据间的两两关系，但也只利用了数据的条件属性，没有把顶点上的监督信息扩展到边上加以利用。类似地，大多半监督聚类算法用点对约束限制可行解的搜索范围或者学习一个合适的度规，从而使聚类结果尽可能满足事先给定的约束条件，但却鲜少考虑把边上的监督信息的扩展到顶点上加以利用。本文提出将已知的监督信息在图的点边结构上进行传递，从而提高有监督分类和半监督聚类算法对监督信息的有效利用。
　　首先，我们提出了一种统一的非线性分类框架，称为流形映射机，它由监督式流形映射，分类器构建和测试数据扩展三部分构成。该分类框架将顶点间的类别关系融入到边的权重上（点—边），然后有监督地将不同类别的数据在新的低维特征空间中分离开来（边—点），有利于后续分类器的构建，是一种“点—边—点”的途径。为了使测试数据映射到目标空间后能达到类似的效果，我们在数据的原始流形和目标流形之间搭建了一个“桥”，通过最小化测试数据从原始流形和目标流形映射到该中间“桥”上的差异，确定测试数据在目标流形上的最佳映射。此外，我们还讨论了流形映射机与几种著名流形学习算法之间的联系，证明了该框架可行性和广泛性。
　　其次，在流形映射机框架的前提下，我们提出了一种监督式谱空间分类器。该分类器用线性融入监督信息的方式，将输入数据映射到低维的监督式谱空间中。然后，S3C分别采用了三种不同的分类算法用于分类器构建。在测试数据扩展阶段，我们证明了S3C通过构建流形桥所推得的测试数据最佳映射与Nystr(o)m方法具有相同的形式。大量基于人工数据集和真实数据集的实验结果显示，S3C的分类性能显著优于其它多种经典的分类算法。
　　最后，我们提出了一种局部约束传播的半监督聚类算法，可用于处理既有必连约束又有不连约束的多类别半监督聚类问题。该算法先确定每个约束顶点的影响范围（边—点），然后根据每个无约束边所连接的顶点与有约束顶点之间的相似度，将约束边的影响成比例地传播开去（点—边），因而是一种“边—点—边”的途径。我们将每个顶点的传播范围及其影响程度定义为介于细粒度顶点和粗粒度簇之间的一种中间结构，称之为“组件”。通过评估各个组件传播范围的准确程度，算法还可以自适应地调节各个点对约束在不同组件上的传播强度，使得置信度高的组件受到的约束影响较大，而置信度低的组件则受到的约束影响较小。大量基于UCI数据库，文本文档，手写数字，英文字符，人脸识别和图像分割数据集上的实验证明，局部约束传播半监督聚类算法比其它经典的半监督聚类算法更准确，也更高效。

目录

摘要

第一章 绪论

1．1 人工智能

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 结论

第三章 流形映射机分类框架

3．1 引言

3．2 支持向量机

3．2．1 线性支持向量机

3．2．2 非线性支持向量机

3．2．3 多分类问题

3．3 流形映射机

3．3．1 监督式流形映射

3．3．2 分类器构建

3．3．3 测试数据扩展

3．4 M3与流形学习的联系

3．4．1 等度规映射

3．4．2 局部线性嵌入

3．4．3 邻居维持嵌入

3．4．4 局部保持投影

3．5 结论

第四章 监督式谱空间分类器

4．1 引言

4．2 监督式谱空间分类器

4．2．1 监督式谱空间变换

4．2．2 分类器构建

4．2．3 测试数据扩展

4．2．4 行归一化

4．2．5 算法小结与时间复杂度分析

4．3 实验

4．3．1 人工数据集

4．3．2 真实数据集

4．3．3 参数讨论

4．3．4 单一模式与批量模式

4．4 结论

第五章 图上的标签传播算法

5．1 直推学习的图模型

5．2 标签传播算法

5．3 正则化框架

5．4 标签传播与随机游走的联系

5．5 总结

第六章 局部约束传播半监督聚类算法

6．1 引言

6．2 SCRAWL原型

6．2．1 算法演示

6．2．2 组件构建

6．2．3 组件聚类

6．3 SCRAWL算法

6．3．1 软组件的构建

6．3．2 自适应的约束传播

6．3．3 有限的组件数目

6．3．4 算法小结

6．4 实验

6．4．1 实验数据

6．4．2 实验设计

6．4．3 实验结果

6．5 结论

第七章 结束语

7．1 全文总结

7．2 工作展望

参考文献

致谢

在学期间的研究成果及发表的学术论文