聚类分析中的相似性度量及其应用研究

摘要

在机器学习研究中，聚类作为一种无监督学习方式，得到了来自统计学、计算机科学等领域研究者的广泛关注，它不但是数据挖掘的重要组成部分，也是模式识别领域中备受关注的基础问题。在聚类分析中，数据元素是按照相互之间的相似性进行分类的。聚类的目标就是最大化同类数据元素之间相似性的同时，最大化不同类数据元素之间的差异性。并且，由于聚类的无监督特性，对于聚类结果合理性的判断也是需要探讨的课题。综合来看，聚类分析涉及到三类相似性度量，即数据对象之间的相似性、类对象之间的相似性以及不同聚类结果之间的相似性。因此，采用聚类分析方法来完成图像处理任务时，相似性度量是其中的关键问题。
　　本文首先对聚类分析的概念、处理过程、算法分类、相似性度量问题以及聚类在图像处理中的应用作了简要概述。然后本文以信息论中的经典理论为依据，从信息的角度分别对聚类分析中三类相似性度量问题进行了探讨，并针对图像处理中的几类问题，即图像聚类、轮廓编组、图像过分割的处理以及图像分割的评估，验证了所提出方法的合理性和有效性。本文的主要创新点简要概括为:
　　第一，数据对象之间的相似性度量之一——采用Bregman散度处理复杂数据对象的相似性度量。在对图像数据进行相似性度量时，需要同时考虑两方面的问题，即如何对图像数据进行表示，以及采用何种度量方法评价两个图像数据对象之间的相似程度。本文提出在信息瓶颈理论框架下，将“词袋”模型的图像表示与Bregman散度度量相结合，实现了更具有语义信息的图像内容聚类。该方法概括来说有以下三个特点:采用“词袋”模型的图像表示可以利用多种先进的特征提取算法（如各种兴趣点检测技术）捕捉到图像中更丰富的内容信息，并产生基于视觉单词的特征分布;根据信息瓶颈理论，图像聚类的目标是使得聚类后图像变量与特征变量之间的互信息损失量最小;采用Bregman散度聚类算法最小化互信息损失量，算法步骤与k-means相似，且Bregman算法中的KL距离对应着k-means算法中的欧氏距离。
　　第二，数据对象之间的相似性度量之二——利用数据对象之间的多元相似性关系提高聚类算法的抗干扰能力。对于用聚类方法来进行轮廓编组，我们提出在基于信息的聚类方法的框架下，通过多特征编组线索来计算数据对象之间的“集合相似度”，而不再限于二元相似性度量值，得到的度量量值也称为多特征相似度或多元相似度。然后，我们将多元相似度值作为输入，用信息聚类的方法来对边缘特征进行编组。实验结果表明，相对于二元相似度，基于多元相似度的轮廓编组质量在相同误差或干扰条件下（如存在特征描述误差及背景噪声数据）有明显的提高。
　　第三，类对象之间的相似性度量——提出将信息学习理论中定义的信息势和Renyi“交叉”熵用于聚类中子类间的相似性度量。对于一些容易产生过分割的算法，我们可在初始分割的基础上，根据类间信息熵的大小，采用聚合迭代的方法得到层次化的聚类结构。实验结果显示，在几种具有代表性的人造数据集上，基于信息熵的类间距离度量方法比三种传统度量方法（单联接、完全联接和平均联接）有更好的层次化聚类效果。此外，我们测试了在图像过分割的情况下，类间信息熵对于子分割区域的合并效果。
　　第四，不同聚类结果之间的相似性度量——扩展传统的正则化互信息度量指标，使其应用于算法聚类结果与多个标准聚类结果进行比较的情况。在实际应用中，对于某一幅图像，人为标定的标准分割结果通常不是唯一的，不同的测试对象会根据主观经验得出不同粒度等级下的分割结果。为了体现分割结果的不确定性和多样性，充分利用人为标定的分割信息，聚类结果之间的相似性度量应扩展为可处理包含多幅标准分割图像的情况，因此我们提出了一种基于信息论的相似性度量指标，正则化联合互信息评估指标，可看作是正则互信息的扩展。通过在Berkeley图像分割数据库上的测试，我们验证了正则化联合互信息评估指标在量化评估分割算法上的合理性。

目录

声明

致谢

摘要

第一章 绪论

1．1 聚类分析概述

1．2 聚类分析中涉及相似性度量的关键问题

1．2．1 数据的表示

1．2．2 度量数据元素之间的相似性或距离

1．2．3 建立算法模型

1．2．4 评估聚类结果

1．3 现有相似性度量方法所存在的问题

1．4 本文的研究内容

1．5 本文的章节安排

1．6 本章小结

第二章 基础理论和相关研究

2．1 聚类分析中的相似性度量方法

2．1．1 数据对象之间的相似关系

2．1．2 类对象之间的相似关系

2．1．3 不同聚类结果之间的相似关系

2．2 聚类方法应用于图像处理任务的研究现状

2．2．1 图像聚类

2．2．2 轮廓编组

2．2．3 图像分割

2．3 本章小结

第三章 结合“词袋’’模型与KL距离的图像聚类方法

3．1 本章引言

3．2 “词袋”模型的图像表示

3．3 基于信息瓶颈理论和Bregman散度的图像聚类方法

3．3．1 信息瓶颈理论

3．3．2 Bregman散度聚类方法

3．4 实验结果与分析

3．5 本章小结

第四章 基于信息聚类和多特征相似性度量的轮廓编组方法

4．1 本章引言

4．2 基于信息的聚类算法

4．3 多特征相似性聚类的轮廓编组方法

4．3．1 多特征编组线索

4．3．2 多特征相似性聚类的轮廓编组方法

4．4 实验与分析

4．5 本章小结

第五章 类间信息熵指导下的层次聚类方法

5．1 本章引言

5．2 基于信息的学习

5．2．1 Renyi熵与非参数估计

5．2．2 ITL在机器学习中的应用

5．3 类间信息熵指导下的层次聚类方法

5．4 实验结果

5．5 本章小结

第六章 图像分割的正则化联合互信息评估指标

6．1 本章引言

6．2 相关工作介绍

6．2．1 聚类结构评估的正则化互信息度量指标

6．2．2 图像分割的PR指标评估方法

6．3 图像分割的正则化联合互信息评估指标

6．3．1 联合互信息的定义

6．3．2 联合互信息与多元共享信息之间的关系

6．3．3 正则化联合互信息(NJMI)

6．4 实验结果

6．5 本章小结

第七章 总结与展望

7．1 全文总结

7．2 研究展望

参考文献

作者简历

学位论文数据集