聚类分析作为一种无监督学习方法,是机器学习领域重要研究方向之一。近年来,数据聚类正在蓬勃发展,聚类分析已成功应用于图像处理,文本挖掘,生物信息学等诸多领域。本文重点研究聚类分析中两个关键问题：相似性度量和聚类算法的设计及应用。聚类的目的是发现相似对象的集合,因此如何度量对象间的相似性是聚类分析中的一个关键问题。本文基于现有的高斯型相似度计算模型,提出了新的相似度计算模型,并针对数据特征对相似度的影响进行了讨论,将本质维数作为新的特征来改善相似性度量。在聚类算法设计及应用方面,针对不同的聚类问题,设计快速有效的聚类算法是十分必要的。本文分析了现有聚类算法的优缺点,提出了一种快速的基于相似度矩阵的聚类算法,并将其应用到图像分割中。考虑到现实中大多数图像受到了噪声干扰,为了降低噪声对图像分割和其他后续图像分析带来的影响,提出了一种基于稀疏表示的混合噪声去噪算法。本文的主要工作包括：(1)提出一种加权的自适应高斯型相似性度量方法。传统的高斯型相似度适用于同密度簇的聚类问题,而且对于数据中的野值点不够鲁棒。考虑到实际数据中野值点和不同密度簇的存在,提出了一种新的鲁棒的高斯型相似度计算方法。基于已有的自适应高斯型相似度度量,新的相似度根据数据点的邻域信息对每个数据点赋以权值,并通过降低野值点的权重来降低野值点与其他数据点的相似度。实验表明新的相似性度量能更好地反映类内和类间数据点的相似性关系,得到更加满意的聚类结果。(2)提出一种基于本质维数的相似性度量。相似性度量不仅依赖于相似度计算公式,还依赖于数据的特征。数据集中的每个类可以看作是一个子流形,通过定义反映流形拓扑结构的数据特征来对各个子流形进行划分。本质维数可以用于区分不同的流形结构,位于同一流形的数据点的本质维数应该保持致,具有不同本质维数的数据点通常也可以认为分布在不同的流形上。通过数据点的邻域信息来估计数据点的本质维数,将本质维数作为数据的新的特征,结合数据的原始特征来计算新的相似度。实验表明,基于新的相似度的聚类结果要优于单独使用本质维数或者原始特征的相似度得到的聚类结果。(3)对于具有复杂结构的数据集,只通过无监督的方法改变相似性度量很难达到满意的聚类结果。半监督聚类是利用有限的标签数据对全部数据的聚类过程进行指导,从而可以得到更好的聚类结果。本文提出一种基于近邻传播算法的半监督聚类算法。近邻传播算法是基于相似度矩阵的聚类算法,新算法根据约束对先验信息调整相似度矩阵,进而改善聚类结果。实验结果表明,通过加入少量先验约束对信息,半监督近邻传播算法较大程度地改善了无监督近邻传播算法的聚类结果。(4)基于VVittgenstein的家族相似性,提出了一种基于相似度矩阵的聚类算法。已有的基于相似度矩阵的聚类算法要么时间复杂度较高,要么需要调节的参数较多。新算法通过相似度矩阵构建邻接矩阵,然后在邻接矩阵中发现连通分支进而对数据进行划分。与常用的基于相似度矩阵的谱聚类算法相比,新算法无需计算特征向量,大大降低了时间消耗。而且,在给定相似度矩阵的基础上,新算法不需要设置任何参数。实验结果表明,新的聚类算法适用于图像分割问题。(5)为了降低噪声对图像分割和其他后续图像分析带来的影响,提出了一种基于稀疏表示的混合噪声去噪算法。该算法有效地结合了中值型滤波检测算法和字典学习算法,采用三阶段方法来优化本文提出的l1-l0去噪模型。新算法利用双重稀疏表示对图像进行二次重构,可以达到更好的去噪效果。实验结果表明新算法在去除脉冲噪声和高斯脉冲混合噪声上比现有算法有了明显改进。