密切关系传播(affinity propagation或AP)算法是一种基于代表点的聚类算法,即从数据点集合中识别出一组代表点作为聚类中心。AP算法在因子图上迭代地传播消息直到收敛。其因子图中包含描述数据点和代表点的隶属关系的变量节点,描述数据点之间相似度和描述代表点约束条件的因子节点。　　AP算法具有如下优点:(I)通过指定每个数据点成为代表点的可能性,产生自适应数据集大小的聚类数;(ii)可在数据集的相似度矩阵中引入约束,并不受数据维数影响。AP算法仍有如下问题需要研究:(I)降低时间复杂度问题;(ii)参数学习问题。　　为解决上述问题:　　(I)本文提出了AP重复点算法,将数据点的重复度属性引入AP算法,并在因子图模型上推导出消息传播机制。降低了算法处理重复点数据集时的时间复杂度。　　(ii)本文提出AP修剪消息算法,通过在迭代中减少不必要的消息传播,降低了算法的时间复杂度。　　(iii)本文提出了自动设定聚类数的AP算法,和基于AP算法的高斯混合模型(Gaussianmixture model或GMM)参数估计方法,提高了GMM参数估计的效率和精度。　　(iv)本文研究了如何将上述算法应用于图像标注中。研究了能够自适应不同复杂度的图像表示方法;研究了图像标注中的训练集优化算法以及研究了基于Bayes通用背景模型的高斯图特征提取。通过使用上述方法,提高了图像标注的精度,降低了时间复杂度。