题目：自适应亲和传播聚类算法的研究与应用

?????? 俗话说：“人以群分，物以类聚” 。聚类分析就是利用计算机来实现这一目的的一种技术。它包括两个基本内容：模式相似性的度量和聚类算法。其输入是一组未划分的数据，事先不知道如何分类，也可能不知道要分成几类，但通过统计分析数据间的关系，制定合理的聚类规则，进行合理划分，从而确定每个数据所属的类别，最后按照相似性大小，把各数据聚集成为一些簇。以保证簇内数据的相似性较大，簇间数据的相似性较小。 ??????? 2007年 Frey与 Dueck给出了一种新的聚类分析方法， 称为“亲和传播聚类”（Affinity Propagation，AP）。亲和传播聚类(与 K-Means相比)不需要事先指定聚类数和初始聚类中心，并且最终的聚类中心必定是原始数据中确切存在的数据点，而不是由多个数据点求平均而得到的聚类中心(K-Means)。经试验证明，利用它对数据进行聚类可以得到较小的误差等优点。目前该算法已被应用于人脸图像检索、基因外显子发现、最优航线搜索等方面。 ??????? 亲和传播聚类相对于其他聚类方法具有许多优势，并在实践应用中也取得了一定的效果，但是该算法还处于发展初期，仍然存在一些尚未解决的关键问题，尤其在下面几个方面：1)? 亲和传播聚类在聚类前是无法预知最终的聚类数，也不能保证得到聚类结果就是最优聚类结果；2)? 亲和传播聚类是一种非监督聚类方法，无法完成半监督学习，即利用少量已标记样本，指导聚类过程；3)? 亲和传播聚类的时间复杂度和空间复杂度严重受制于样本个数，无法处理图像分割等大规模数据。 ??????? 本文就以上这些问题一一展开论述、分析以及研究，并试图结合目前的一些其他技术（如：半监督学习理论、自适应聚类技术等） ，解决该算法存在的一些问题。本文主要做了下述工作： ??????? (l) 对聚类分析及其分类进行系统的叙述， 对国内外关于聚类分析的方法和应用作了简要介绍。 ??????? (2)? 深入的研究了亲和传播聚类算法思想、聚类过程和应用，并且阐述了亲和传播聚类算法研究的现状以及目前存在的问题和挑战。 ??????? (3)? 详细介绍了目前几种主要的聚类评价函数，包括外部评价法、内部评价法、相对评价法，并阐述各种具有代表性的评价方法的特征及其对划分优化的作用，总结了聚类评价方法的应用问题。 ??????? (4)? 针对亲和传播聚类算法难以得到最优聚类结果的问题，提出了半监督自适应亲和传播聚类算法（SAAP）。它可以结合少量标记样本信息，从偏向参数与聚类数目之间的关系入手研究亲和传播聚类算法，实现自适应地扫描有效聚类数空间，最后根据评价函数找到最优聚类结果，解决算法中存在的聚类精度低、运算速度慢、最终聚类数目与真实情况不相符等缺点。 ??????? (5)? 针对亲和传播聚类算法不适合大规模数据处理，特别是图像分割问题，提出了基于亲和传播算法的处理大规模彩色图像分割的方法。首先对原始图像进行颜色空间变换，再进行数据采样，对采样数据进行指定聚类数的亲和传播聚类(APGNC)，进而将聚类结果扩展至整幅图像，最后结合形态学方法对聚类结果进行区域合并，得到修正的分割结果。解决亲和传播聚类难于处理大规模彩色图像分割和分割效果差等问题。