基于通用约束正则化的谱聚类方法研究

摘要

谱聚类方法以其简单高效的特点，在聚类分析领域及其相关的数据挖掘与机器学习应用中占据越来越重要的地位。同时，适当的在聚类过程中加入先验约束，可进一步提高谱聚类的准确性。目前，现有的带约束的聚类方法不能分别将同组约束（Must-Link）和非同组约束（Cannot-Link）以统一的形式有效嵌入到谱聚类求解过程之中。这篇文章中，针对带约束的数据聚类问题，我们提出了一个通用的数据间约束的正则化方法（Unified Spectral Regularization），并形成了一个基于通用正则化约束的谱聚类计算框架。
　　本文的方法不同于以往的基于半正定规划求解的带约束谱方法，本方法实现了更高效的正则化的谱松弛过程，能将同组约束和非同组约束以通用的正则项的形式嵌入到谱聚类的最优化求解目标函数中，并可以直接应用于多标签的聚类问题。在本文提出的计算框架中，通过求解正则化的谱分解问题，我们可以快速地求得松弛条件下的全局最优解，再通过加权的K-means聚类方法对松弛的最优解进行最小整数误差的取整近似，可以得到最优的聚类划分结果。本文提出的方法主要有以下贡献：
　　1）通用的约束正则化嵌入形式，使得同组约束和非同组约束可以同时对聚类结果产生正向的引导作用；
　　2）可对接不同相似度矩阵的高可扩展性的带约束谱聚类计算框架；
　　3）相对现有方法显著提高了聚类准确度和计算时间等性能。我们在场景视频数据集和UCI数据集中与现有最好的带约束聚类方法以及现有最新的基于约束正则化的谱聚类方法进行了多个方面的实验和验证，实验结果表示本文提出的方法在聚类准确度和计算性能以及对约束信息的充分利用等方面都有超越现有最新方法的表现。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题背景

1.2 国内外研究现状

1.3主要工作和贡献

1.4 本文的内容和结构

第二章 谱聚类算法理论背景

2.1 聚类算法分类概述

2.2谱聚类的图和矩阵基础

2.3 谱聚类算法模型流程概述

第三章 带约束的谱聚类算法模型设计

3.1 问题描述

3.2 归一化割准则

3.3 无约束的谱聚类

3.4 带约束的2值谱聚类

3.5带约束的K值谱聚类

3.6 径向基函数生成相似度矩阵

第四章 实验结果及性能分析

4.1 实验设置

4.2 聚类效果对比实验

4.3 约束正则化方法对比实验

4.4 相似度矩阵对比实验

4.5 约束类型对比实验

4.6 实验结论

第五章 总结和展望

5.1 总结

5.2 展望

参考文献

发表论文和参加科研情况说明

致谢