偏向参数在仿射传播算法中的作用与意义

第一章绪论

1.1选题背景与意义
以互联网为代表的计算机信息科学技术的高速发展，带动着人们的化产、生沾领域的快速发展，大量的数据信息被人们广泛应用到科学研究、军事领域、政府公务、管观企业、幵发工程以及电子商务等各大领域，这些数据在各自的领域都有着极其重要的作用，无一不和人们的生活密切相关。以前，人从外界获取信息的途径主要是通过自己的感觉器官，经过思维、分析、判断來认识客观世界中的各种事物；通过视觉获得色彩、形状、大小信息，通过触觉获得材质、温度、湿度等信息；通过听觉获得声音信息等。经过综合思维从各个方面获得的信息之后，人就认识了各种客观事物，这样的“模式识另”工作每时每刻都发生在人们的常生活中。随着计算机的出现，人们希望计算机能具有人的识别能力，替代人类完成现实生活的一部分识别活动，因此，“模式识别”这门学科在20世纪中后期得到了快速发展。表征各种事物和现象的形式是多种多样的（数值的、逻辑关系的或者文字的），模式识别的主要工作就是对这些形式多样的信息进行处理并分析，完成对事物（现象）的描述、辨别、分类，最后进行解释说明，它是信息科学技术和人工智能的重要组成部分。
对象或模式必须转换成计算机所能接受的形式后，计算机才能通过自身的功能将其识别或分类。常生活中，描述待识别模式的形式大多是非电信号，如声音、温度、灰度、压力、色彩等，需要将这些用不同形式的非电信号表示的信息通过特定的传感器先转换成电信号，然后再把模拟信号转换成数字信号，最后转换成计算机能够识别的数字量。输入对象的信息通常情况下有三种类型：二维图像、一维图像和物理参数或逻辑值。经过测量、采样和量化，将一维波形或者二维图像用矩阵或向量表示，这样就完成了信息的获取过程。进行预处理的目的是想方设法去除在信息获取过程中的噪声和干扰，并且人为的添加一些有用信息，复原由各种因素造成的退化现象。直接从信息获取模块得到的原始数据量一般会很大，没有办法进行直接处理，因此需要对原始的数据进行变换和选择，得到反映原始信息本质特征的信息，这搜信息组成的向量就是特征向量。这样就完成了特征提取与选择的过程。
将待识别的模式分配到各自最合适的模式类中，设计出分类判别规则的过程就是分类器的设计过程。分类器旳使用过程就是分类决策。模式识别有两种学习模式：种是无监督的学习方法，另一种是有监督的学习方法。这两种学习方法的主要区别在于是否预先知道训练样本旳标签，即训练样本所属的类别。通常情况下，有监督的学习需要预先知道大量样本的类标签或者约束条件，而现实生活中的数据往往是无法预知的，没有预先知道的先验知识，因此，无监督的学习应用的更广泛-些。聚类分析就是一种无监督的分类过程，在分类的过程中样本集没有任何对分类有约束的先验知识，仅依靠样本集本身具有的特征作为划分类别的准则，将大规模的数据对象集合根据一定的关联规则分成多个不同的子集合，将相似性高的数据对象聚集到同一个类中，相异性高的数据对象聚集到不同的类中。数据对象间的相似程度是根据所描述数据对象的属性来决定的，我们经常采用的描述数据之间相似性的方法是距离函数，同一对象间的相似度使用不同的距离函数进行测量，也会得到不同的结果。如果从机器视觉的角度研究聚类，聚类就属于一种无导师指导的学习，这与分类有着很大的不同，这种学习将不依赖于带标号的类的训练和预先定义的类的实例。聚类分析从数学的角度为人们提供了一种细致地，准确地分析数据的工具，成为了统计学的分支之一，是一种无导师监督的学习方法。在现实生活中，聚类分析有着重要的应用价值，例如模式识别、web文档的分类、市场分割、空间数据分析、以及生物学研究等。
聚类分析从提出到现在已经被学者研究了许多年，到目前为止，研究人员提出了许多有关聚类的算法从整体上所有的算法可归纳为：基于划分的方法，将一个具有个对象的数据集合划分成个子集合，《是事先指定的聚类数目，划分的具体过程就是首先将原始数据集构造成《个划分子类，然后根据一定的重定位方法，使得对象在不同的类间进行移动，直到满足事先规定的准则。最经典的划分方法就是均值算法，在此基础上，人们又研究出一系列的改进算法；基于层次的方法，分解的最终结果是把初始的数据集合构造成聚类树。基于层次的方法根据分解的方向又可分为自顶向下和自底向上的方法，自顶向下的分解称为分裂，自底向上的分解称为凝聚；基于密度的方法，依据给定的数据对象集合的分布密度进行聚类，对于给定类中的数据对象，如果数据点的密度在给定区域中超过了一定的阈值则继续进行聚类，最后找出大密度的区域，这样聚类结架的分布就与数据对象的分布密度相关；基于网格的方法，这种方法是首先把给定的样本集划分成定规模的单兀格，聚类运算就是在所有单元格之间进行的，聚类速度阵依赖于样本集的规模大小，而只和量化空间中每维的本兀数目有关，单元格的大小决定了聚类的精度；基于模型的方法，这种聚类方法是在假设数据对象是根据一的概率分布生成为前提，它假定每个聚类子集都是一个数学模型，然后寻找数据与数学模型之间的最佳组合。这类算法的最终聚类数目是根据统计数据自动决定，噪声和孤立点也是根据统计数字进行分析，不受人的主观判断的影响。

1.2 国内外的研究发展现状 10-11
1.3 论文研究内容 11-12
1.4 论文章节安排 12-14
第二章 仿射传播算法及发展 14-27
2.1 仿射传播算法 14-18
2.2 自适应的仿射传播算法 18-21
2.3 半监督的仿射传播聚类算法 21-24
2.4 相似性度量可变的仿射传播算法 24
2.5 基于拉普拉斯特征映射的仿射传播算法 24-26
2.6 小结 26-27
第三章 基于仿射传播算法的距离测度研究 27-44
3.1 距离测度概述 27-29
3.2 现有的仿射传播算法的距离测度 29-30
3.3 基于仿射传播算法的距离测度的对比研究 30-32
3.3.1 曼哈顿距离(Manhattan Distance) 30-31
3.3.2 特征距离 31-32
3.4 仿真结果与分析 32-43
3.5 小结 43-44
第四章 基于仿射传播聚类的偏向参数研究 44-53
4.1 偏向参数在仿射传播算法中的作用与意义 44-45
4.2 现有的偏向参数的设置方法 45-46
4.3 基于二分法的偏向参数的改进算法 46-49
4.4 仿真结果与分析 49-52
4.5 小结 52-53

总结

随着计算机信息技术的快速发展，越来越多的数据信息已经出现在人类学习生活的各个方面，研究人员相继述力：起了各个类别的数据库，如何将大量的数据信息按照一定的特征分类就显得尤为重要，特别是随着可联技术的兴起，最近几年兴起的物联网技术，无一不是将数据信息，物品信息相关起來，在这种大背景下，聚类分析技术得到了研究人员的高度重视。寻求种既能快速将样本集的样本对象分类，又能得到聚类质量较高的聚类结果的聚类方法，已经成为聚类分析算法研究人员关注的焦点。本文针对以上问题，在标准的仿射传播算法的基础上，提出了针对不同空间分而特征的样本集，需采用不同的趴离测度函数汁算样本点之问的相似度，以提高算法的聚类质量，最后采用二分法的搜索策略搜索偏向参数的空间，寻求最优的聚类结果，以提高算法的迭代时间。
概述了聚类分析算法的分类，最常用的聚类分析算法一均值的聚类算法，分析了均值算法的基本原理，以及算法的优点和不足之处，在此基础上提出了本文所要改进的算法一仿射传播算法。仿射传播算法是以数据点之间的相似度作为聚类的原始依据，初始的聚类中心也不需人为的指定，该算法根据数据点之间信息的传递來决定最终的聚类中心，因此，改善了均值算法对初始聚类中心敏感的缺陷，聚类结果比均值算法更能反映样本空间的原始特征。

参考文献

[1]令金模式识别导论[M].北京：等教出版社，5-10
[2]奥多.蒂斯，Koutroumbas，李品皎，等.模式识别[M].2010:128-135
[3J唐东明.聚类分析及沾应用研究[D].成都：电f科技火学，2010
[4]HuangJ. Z., Ng M. K., Rong H. Q.，et al. Automated Variable Weighting in k-Means TypeClustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005，27(5);657-668
[5]AmorimR. C., Mirkin B.. Minkowski Metric, Feature Weighting and Anomalous Clusterinitializing in K-Means Clustering[J]. Pattern Recognition. 2012, 45(3): 1061-1075
[6]FreyB. J., Dueck D.. Clustering by Passing Messages Between Data Points[J]. Science,2007, V315: 972-976
[7]DueckD.，Frey, B. J.. Non-Metric Affinity Propagation for Unsupervised ImageCategorization[A]. Proc. IEEE 11th International Conference on Computer Vision[C].Washington, DC, USA: IEEE Computer Society, 2007: 1-8
[8]JiangW., Ding F.，Xiang Q. L.. An Affinity Propagation Based Method for VectorQuantization[EB/OL]. . 0710.2037v2
[9]王军，张军英，李丹,等.自适应仿射传播聚类.自动化学报，2007，33(12):1242-1246
[10]肖宇，于剑.基于近邻传播算法的半监督聚类[J].软件学报,2008,19(11):2803-2813