英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
局部加权集合聚类
摘要
由于可以将多个基本聚类集合成更好，功能更加强大的聚类方式，因此近年来集合聚类技术引起了越来越多的关注。尽管取得了显著的成功，但对大多数现有集合聚类方法的一个限制：它们通常无论可靠性如何，都相同地对待所有基本聚类，这使得它们容易受到低质量基本聚类的影响。虽然在（全局）评估以及加权基本聚类做了很多工作和取得了较大的进展，但是这些方法倾向于将每个基本聚类视为个体，而忽略了同一基本聚类内的局部多样性。如何评估集群的可靠性并利用集合中的局部多样性来提高共识性能仍然是一个悬而未决的问题，尤其是在无法访问数据特征或数据分布的特定假设的情况下。为了解决这个问题，本文提出了一种基于集成驱动的聚类不确定性估计和局部加权策略的集成聚类方法。特别地，每个集群的不确定性是通过熵判据考虑在整个合奏簇标签估计得到的。本方法引入了一种新的集合驱动的聚类有效性度量，并且提出了局部加权的联合关联矩阵，作为不同聚类集合的总结。随着利用集合的场景及条件的多样性，进一步提出了两个新的共识函数。对各种现实世界数据集的广泛实验证明了所提方法优于现有技术。
引言
数据聚类仍是数据挖掘以及机器学习领域的一个基础却富有挑战性的一个问题。其目的是发现给定数据集的固有结构并将数据集划分为一定数量的同类组，即簇。在过去的几十年中，通过利用各种技术已经开发了大量的聚类算法。每一种聚类算法均有其优势以及缺陷，并且在特定的应用场景中效果极佳。没有某一种单一的聚类算法可以处理所有类型的数据结构和簇形状。对于给定的数据集，应用不同的聚类算法，甚至同一算法初始化时使用不同的参数，可能导致不同的聚类结果。然而，在没有先验知识的情况下，确定哪种算法对于给定的聚类任务是合适的算法是非常困难的。即使使用给定的聚类算法，也很难确定其合适的参数。
由不同算法提供的分类器（或具有不同初始化和参数的相同算法）产生的不同聚类可以反映数据的不同视角。为了在多个聚类中利用互补和丰富的信息，集成聚类技术已成为数据聚类的强大工具，近年来引起了越来越多的关注。集成聚类旨在结合多种聚类方式以获得可能更好和更强大的聚类结果，这在发现奇异的聚类，处理噪声以及集成来自多个分布式源的聚类解决方案方面显示出优势。在集合聚类中，每个输入聚类被称为基本聚类，而最终聚类结果被称为共识聚类。
在集合聚类中，基本聚类的品质在共识过程中起着至关重要的作用。低质量（甚至是病态）基础群集可能会严重影响共识结果。为了处理低质量的基本聚类，有人做了一些评估和加权基本聚类以增强共识性能。然而，这些方法是基于隐含的假设而开发的，即相同基本群集中的所有群集具有相同的可靠性。它们通常将每个基本聚类视为一个个体，并为每个基本聚类分配全局权重，而不管其内部聚类的多样性。然而，由于现实世界数据集的噪声和固有复杂性，同一聚类过程中的不同群集可能具有不同的可靠性。因此，需要尊重集合的局部多样性并处理集群的不同可靠性。最近有些研究人员提出通过考虑聚类中数据对象之间的欧几里德距离来评估聚类的可靠性。该方法需要访问原始数据特征，其效率很大程度上依赖于数据集的数据分布。但是，在集合聚类的一般公式中，往往无法访问原始数据特征。可以提出无需访问数据特征或依赖于有关数据分布的特定假设，这里的关键问题是如何评估集群的可靠性并相应地对它们进行加权，以提高共识聚类的准确性和稳定性。为了解决上述问题，本文提出了一种基于集合驱动的群集不确定性估计和局部加权策略的集成聚类方法。我们的方法的整个流程如图1所示。
图1 提出方法的流程图
我们利用集群级别的集合多样性，将集群的不确定性和有效性整合到局部加权方案中，以提高共识性能。群集可被视为在相应的基本群集中的本地区域。本文提出，在不需要访问数据特征的情况下，基于熵的标准，针对整个集合中的聚类标签估计每个聚类的不确定性。特别地，对于给定的一个聚类，我们通过考虑如何将该聚类内的对象分组到多个基本聚类中来研究其不确定性。基于聚类不确定性估计，然后提出集合驱动的聚类索引（ECI）来测量聚类的可靠性。在本文中，我们认为集合中不同群集的群体可以为评估每个群集提供有效的指示。通过ECI测量对集合中的聚类进行评估和加权，我们进一步提出了LWCA矩阵的概念，它将局部自适应性结合到传统的联合关联（CA）矩阵中，并作为不同聚类集合的总结。最后，为了实现最终的聚类结果，我们提出了两种新的共识函数，分别称为局部加权证据积累（LWEA）和局部加权图分割（LWGP），其中利用了聚类的多样性并结合了局部加权策略。
为了阐述清晰明了，我们总结了本文的主要贡献如下：
- 我们提出通过使用熵标准考虑集合中所有集群标签的分布来估计集群的不确定性，这不需要访问原始数据特征并且不对数据分布做出假设。
- 我们提出了一个集合驱动的集群有效性指数来评估和加权集合中的集群，这提供了集群级别的可靠性指示，并在本地加权方案中起着至关重要的作用。
- 我们提出了两种新的共识函数来构造基于集合驱动的聚类不确定性估计和局部加权策略的最终聚类。
- 我们已经对各种现实世界的数据集进行了广泛的实验，证明了所提出的集合聚类方法在聚类质量和效率方面的优越性。
相关背景知识
2.1 熵
在这一小节中，我们简要回顾一下熵的基本概念。在信息论中，熵是与随机变量相关的不确定性的度量。 熵的正式定义在定义1中提供。
定义1：对于离散随机变量X，熵定义为:
(1)
联合熵是与一组随机变量相关的不确定性的度量。 联合熵的正式定义在定义2中提供。
定义2：对于一对离散随机变量（X,Y），联合熵定义为:
(2)
当且仅当两个随机变量X和Y彼此独立时，它保持= 。 因此，给定n个独立的随机变量X1，...，Xn，我们有:
(3)
2.2 集成聚类问题的公式化
在本节中，我们将介绍集成聚类问题的一般表述。设是一个数据集，其中是第i个数据对象，N是数据集的对象个数。考虑数据集O有M个分类，每个被视为基本聚类，由一定数量的聚类组成。在形式上，我们将M基群的集合表示如下：
(4)
其中：
(5)
表示在中的第m个基本聚类，表示在中的第i个群集，表示中群集的数目。
为方便起见，我们将集合中所有集群的集合表示为：
(6)
关于集合聚类算法的输入信息的差异，存在两个不同的问题公式。在第一种方案中，整体聚类系统仅将多个基本聚类作为输入，并且不去访问原始数据特征。在另一个公式中，集合聚类系统将多个基本聚类和原始数据特征作为输入。在本文中，我们遵循集合聚类问题的第一个公式，这也是大多数现有集合聚类方法的通用实践方法。因此，在我们的公式中，输入是聚类集合，输出是共识聚类。
局部加权集合聚类
在本文中，我们提出了一种基于集合驱动的群集不确定性估计和局部加权策略的新的集合聚类方法。 在本节中，我们将详细描述我们方法的每个步骤。
3.1 测量集合中的集群不确定性
在集合聚类的一般公式中，无法访问原始数据特征。为了评估每个集群的可靠性，我们借助熵的概念来提供整个集合中的集群标签。
正如2.1节中所介绍的，熵是与随机变量相关的不确定性的度量。每个集群都是一组数据对象。给定一个簇，以及一个基本集群，如果簇不属于集群，那么有可能中的某一个对象属于集群的不同的簇。因此可以通过考虑中的对象如何聚集在中来计算相对于的不确定性（或熵）。
定义3：给定集合，簇相对于基本集群的不确定性可表示为： (7)
且
（8）
关于基群集的群集不确定性的正式定义在定义3中给出。正如它所定义的对于任意i，j以及m，。因此我们可以得到。当中所用对象均属于相同的集群，的不确定性达到其最小值。当中对象均属于不同的集群，的不确定性变大。
根据公式（3），在不失一般性的基础上，假设集合中的基本聚类是独立的，可以通过总结相对于M基的不确定性来计算相对于整个集合的不确定性（或熵）。 它的正式定义在定义4中给出。
定义4：给定集合，集群相对于整个集合的不确定性计算为：
（9）
直观地说，的不确定性与关于中的对象如何聚集在多个基本聚类的集合中的不确定性有关。如果中的对象属于每个基本聚类中的相同聚类，可以看作所有基本聚类都认为中的对象应该被分配到同一聚类，那么的不确定性就会达到它最低限度，此时的值为0. 当的不确定性变大时，表明中的对象不太可能在考虑多个基本聚类的集合的情况下处于同一聚类中。
3.2 集成驱动集群的有效性
在获得聚类集合中每个聚类的不确定性（或熵）后，我们进一步提出了ECI的概念，它通过考虑它们对集合的不确定性来测量聚类的可靠性。
定义5：给定具有M个基本聚类的集合， 的集合驱动聚类索引（ECI）可被定义为：
（10）
根据此定义，由于，因此，显然，群集的不确定性较小会导致更高的ECI值。
当的不确定性达到其最小值，，它的ECI的值相对应的会达到其最大值1. 当其集群的不确定性无穷大接近集群的ECI趋近于零。参数在计算ECI时被用到，进而调整集群不确定性对指数的影响。当将设置为较大值时，高不确定性群集的ECI值与低不确定性群集的ECI值之间的差异将缩小。因此，建议取值在[0.2,1]这一范围内。
3.3 通过局部加权重新确定联合关联矩阵
CA矩阵最早被Fred以及Jain提出，它反映了两个对象在整体中被分组到同一个簇中的次数。
定义6：给定集合，共同关联（CA）矩阵可以表示为：
（11）
（12）
（13）
CA矩阵是用于处理集合聚类问题的经典且广泛使用的工具，尽管取得了显着的成功，但CA矩阵的一个限制是它对集合中的所有集群和所有基本集群进行了相同的处理，并且缺乏评估和加权集合成员的可靠性的能力。Huang等人，利用NCAI指数对基本聚类进行加权，从而构建加权CA矩阵，然而，他们只考虑基本聚类的可靠性，但仍然忽略了同一基本聚类内的簇。与整体处理每个基本聚类的（全局）加权策略不同，我们通过基于集合驱动的聚类有效性的局部加权策略来重新定义CA矩阵，并提出LWCA矩阵的概念。
定义7：给定集合，局部加权的协同关联矩阵（LWCA）可表示为：
(14)
(15)
(16)
(17)
可以将一个簇看做基本群集的本地区域，为了考虑簇的不同可靠性，加权项被合并以通过ECI测量将权重分配给簇。直觉是指更可靠的聚类（具有更高的ECI值）中共同出现的对象更可能属于真正群集中的相同簇。利用局部加权策略，LWCA矩阵不仅考虑两个对象在多个基本聚类中在同一聚类中出现的次数，而且还反映了整体中聚类的可靠性。
3.4 共识函数
在本文中，基于集合驱动的聚类不确定性估计和局部加权策略，我们进一步提出了两个新的共识函数，即LWEA和LWGP，它们将在后文中被详细介绍。
- 局部加权证据积累：在本小节中，我们介绍了基于分层凝聚聚类的共识函数，它的名称为LWEA。
分层凝聚聚类是一种广泛使用的聚类技术，它通常将相似性矩阵作为输入并迭代地执行区域合并以实现树形图，即聚类的分层表示。
在这里，我们利用LWCA矩阵（参见定义7）作为初始相似性矩阵，表示为：
（18）
（19）
N个初始数据对象看作N个初始区域，在
全文共6785字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2526]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
