基于标记点的快速谱聚类算法研究

《基于标记点的快速谱聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据指导小组成员名单黄萱菁教授张珥杰教授牛军钰教授万方数据目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯．．1ABSTRACT⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．2第一章引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯41．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．41．2本文工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．51．3本文组织⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．5第二章研究背景及相关工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．62．1谱聚类算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．62．2谱聚类加速算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102，2。l相似度矩阵的随机采样算法⋯⋯

2、⋯⋯⋯⋯⋯⋯102．2．2基于Nystrom的特征值分解加速算法⋯⋯⋯⋯⋯．112．2。3随机SVD算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯132．2．4并行化算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．132．3已有算法的局限性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．14第三章基于标记点的谱聚类算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．163．1弓l言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．163．2样本的稀疏编码表述⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯．163．2．1标记点的选择及距离计算⋯⋯⋯⋯⋯⋯⋯⋯．．183．2．2基于标记点的稀疏编码方法与其它方法的差异⋯⋯．．203．2．3相似度矩阵的稀疏编码表述⋯⋯⋯

3、⋯⋯⋯⋯⋯2l3．3幂迭代聚类方法⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．233．4结合稀疏编码的幂迭代方法⋯⋯⋯⋯⋯⋯⋯⋯⋯．．253．5子空间迭代方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯263．6算法复杂度分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28第四章实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．324．1实验准备⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯324．2评价标准⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．334．3数据集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．334．4实验结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯354．5LSISC在图像分割中的应用⋯⋯⋯⋯⋯⋯⋯⋯⋯．．42第五章总结和展望⋯⋯⋯

4、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．475．1本文总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯475．2未来展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯47万方数据参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．49攻读学位期间发表的论文⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．53致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．54万方数据复旦大学硕士学位论文基于标记点的快速谱聚类算法研宄摘要谱聚类算法是近年来机器学习和模式识别领域最重要也是最热门的基础算法之一。谱聚类算法将聚类问题转换为图的分割问题，通过对相应的拉普拉斯矩阵的特征向量进行聚类，找到对图的最优划分。凭借其良好的聚类结果和简单

5、的实现细节，谱聚类算法越来越广泛地被研究人员运用在图像分割、人脸识别、语音分析等领域。然而由于在计算过程中需要维护一个大小与样本数量二次相关的拉普拉斯矩阵并对其进行特征值分解，谱聚类在处理大量样本时需要耗费过多的时间和内存空间。谱聚类性能上的缺陷限制了其从实验室走向工业化应用的步伐。本文分析了当前主流的谱聚类加速算法的优缺点，从改进谱聚类在大数据集下的运行性能的角度出发，根据稀疏编码理论，提出了一种基于标记点和子空问迭代的快速谱聚类算法。本文提出的算法在普通样本与随机抽取的标记样本之间建立相似度关系，利用稀疏编码的方式将这种关系重新定义为样本的特征

6、，并将该特征存储在稀疏的扁平矩阵内。该方法继而结合子空间迭代算法，能够在不生成拉普拉斯矩阵的前提下计算出拉普拉斯矩阵的主要特征向量。理论分析和实验显示，本文提出的算法能够在保证甚至改进聚类准确率的前提下达到与样本数量线性相关的时间复杂度和空间复杂度，在多个数据集上能够比目前主流的谱聚类加速算法更快地得到更高准确率的结果。本文还对该算法在图像分割领域进行了实验，并对算法未来进一步的发展进行了讨论。关键词：谱聚类，稀疏编码，算法，图像分割，标记点中图分类号：TPl81万方数据ABSTRACTSpectralclusteringisoneofthemos

7、timportantandmostpopularfundamentalalgorithmsinthefieldofmachinelearningandpatternrecognition．Spectralclusteringconvertstheproblemfromclusteringtofindingthebestpartitionoftheconnectivitygraph．Spectralclusteringfullyusestheeigenvectorsofthesimilaritymatrixdescribingthesimilarit

8、ybetweensamplepairstofindtheclusterinformationofthegraph．With