数据聚类算法的实证分析外文翻译资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

数据聚类算法的实证分析

Pranav Nerurkara, Archana Shirkeb, Madhav Chandanec, Sunil Bhirudd

VJTI计算机工程与信息技术，孟买 印度 400019

VJTI计算机工程与信息技术，孟买 印度 400019

VJTI计算机工程与信息技术，孟买 印度 400019

VJTI计算机工程与信息技术，孟买 印度 400019

摘要：执行聚类以获得对数据的深入了解，其数量使得人类分析成为问题。因此，聚类算法已经成为用于执行探索性数据分析的学习工具。聚类被定义为一组对象，与不在同一组中的对象相比，它们具有更高的相似度。然而，关于用于聚类的合适的相似性度量存在模糊性。已经提出了与量化相似性相关的多个度量，例如欧几里德距离，数据空间中的密度等，使得聚类成为多目标优化问题。在本文中，从理论角度研究不同的聚类方法，以了解它们在海量数据集的背景下的相关性，并且根据经验，这些方法已经在人工基准上进行了测试，以突出它们的优点和缺点。

关键词：聚类算法; 社区结构; 无监督学习。

1 引言

随着社会的数字化转型步伐加快，技术的普及越来越多，简化了有效记录数据的过程。低成本传感器，RF-ID，支持互联网的销售点终端是侵入我们生活的此类数据捕获设备的一个例子。这些设备的易用性以及由此产生的操作简化已经生成了以前不存在的数据存储库。今天，存在许多领域，每秒产生大量数据，并且处理和存储这些领域是社交网络，传感器网络，云存储等。这促进了机器学习，模式识别，统计数据分析和一般数据科学。

尽管这样的数量为学术界和工业界提供了巨大的机会，但它也代表了有效分析和检索的问题[1]。为了减轻这种操作所需的指数时间和空间，数据被压缩成有意义的摘要，即探索性数据分析[E.D.A.]，它将消除在无监督学习文献中存储数据的需要，这种摘要等同于“聚类”。 E.D.A.有助于可视化并促进更好地理解数据。它利用机器学习，模式识别和信息检索的交叉方法。聚类分析是其中执行的主要任务。

数据中的聚类是客观地使用相异性度量来定义的，例如编辑距离，欧氏或非欧几里德数据空间中的密度，使用Minkowski度量计算的距离，邻近度量或概率分布。所有测量都同意应该为集群中的对象分组设置阈值，并且超过这样的阈值的对象不同并且应该与集群分离。聚类可以更好地表示数据，因为群集中的所有对象的属性变化较小，可以有效地进行汇总。聚类已经在其他领域中找到了应用，例如估计数据中的缺失值或识别数据中的异常值。

因此，聚类是一种元学习方法，用于深入了解数据和各种领域，例如市场研究，电子商务，社交网络分析和搜索结果聚合等。存在用于将数据组织成群集的多种算法，但是没有针对所有问题的通用解决方案。对于“最佳”算法没有达成共识，因为每个算法都是根据某些假设设计的，并且有自己的偏差。这些算法可以分组为诸如基于分区，分层，基于密度，基于网格，基于消息传递，基于神经网络，基于概率和生成模型的方法。然而，就复杂性而言，它是NP难分组问题，因此现有算法依赖于近似技术或启发式来减少搜索空间以便找到最优解。对于正确性或聚类有效性，没有普遍认可的客观标准，并且这些算法中的每一种在解决无监督聚类的挑战性问题方面都有其自身的缺点和成功[3] [4]。

受这些原因的推动，本文对现有的聚类算法进行了回顾，以突出其主要优点和缺点。第二部分介绍了这些算法的理论方面，第三部分包含使用这些算法进行的实验，第四部分对结果进行了总结。

2 聚类算法的类型

各种聚类算法可以在文献[1] [3] [4]中找到，并且基于算法设计者的观点大致分为几类，重点是基础聚类标准：

2.1 基于分区的聚类算法[5]

这些算法的一般原则是一个集群应该包含至少一个对象，并且每个对象必须完全属于一个组，即集群。群集数量k由用户预先指定，使其成为监督算法，尽管已经建议许多策略来估计理想的群集数量，例如经验方法，其中，其中n = | N | 点和弯头方法，其中k被固定为k v / s平均值图上的转折点到质心的距离。在这些k分区算法中要最小化的目标函数是SSE，即距离和的平方。

(1)

其中为集群的质心。

流行的k分区算法是K-Means，它表示一个质心作为集群中对象的算术平均值[6]。该算法在该类别中是最受欢迎的，尽管它具有缺点，因为它无法找到非凸形簇或处理更高维度的非数字属性。时间复杂度为O（kN），使其适用于大型数据集，但理论上该算法可以采用无限次迭代进行收敛，其基于均值的appraoch对噪声数据或具有异常值的数据敏感。取决于欧几里德距离度量的算法由于距离在更高维度上膨胀而受到“维度诅咒”的影响。D.Arthur等人的K-Means 。2007年通过在相互最大距离处初始化种子簇质心来提供对K-Means的改进。与具有多个重复的随机初始化相比，该技术提供了更好的结果。D. Sculley等的Mini Batch K-Means。在每次聚类迭代中使用随机采样的原始数据子集。与原始K-Means算法相比，该方法以精确度略微降低为代价改善了计算时间。

为了克服基于均值的方法中对噪声的敏感性，K-Mediods算法通过位于质心附近的对象来表示聚类。围绕Mediods（PAM）[7]的分区是基于mediods的分区最流行的方法，但是它具有O（k（n-k）2）的计算时间复杂度，因此不能很好地扩展到大数据集。提出了修改版的PAM，如CLARA（带采样的PAM）[8]和CLARANS [9]。CLARA的计算时间复杂度为O（ks2 k（n-k）），CLARANS具有O（n2），因此两种方法都不适用于大型数据集。

内核K-Means [10]涉及将点从欧几里德空间转换为高维内核空间。内核选择可以基于Mercer的标准。R.B.F. 或高斯是考虑的共同选择。核K-Means相对于K-Means的优势在于找到非凸簇，尽管以计算时间为代价。BFR算法[11]被实现用于在数据上单次通过中检测大数据集中的簇。该算法强烈假设聚类具有正常分布的对象，并且由此无法在与随机形状的轴或聚类倾斜的角度处找到聚类。

2.2 模糊聚类

模糊聚类算法将一组隶属系数分配给每个元素，其对应于群集的“归属性”或隶属度，即软群集。模糊C-Means算法由Dunn于1973年[17]并由Bezdek于1981年修改[18]，最小化了方程中的目标函数。式4为此目的，式5定义了归属度umij和Eqn。式6定义了簇的质心Cj。

(2)

其中是观察属于集群的程度，j是的中心，m是定义群集模糊水准的真实数字。

(3)

(4)

该算法最小化了集群内方差，但可以收敛到局部最优解。它取决于种子的初始化，并且不同的初始化可能导致不同的结果。必须在高级中指定簇k的数量，这是另一个缺点。

2.3 基于模型的聚类算法[19]

传统的聚类算法分层和基于分区的聚类依赖于启发式，而基于模型的算法假设数据是由多个概率分布（高斯或多项式）的混合生成的，其参数均值，协方差矩阵将使用期望最大化算法进行估计。贝叶斯信息标准或Akaike信息标准可用于选择最佳数量的簇。该算法的主要缺点是类似于k均值，它也可以根据k种子的初始分配收敛到局部最优解。对于这些方法，目标函数不是凸的。而且，优化标准理论上可以采用无限次迭代来收敛，并且必须预先确定合适的阈值。如果对象的概率没有改变超过该阈值，则可以停止算法。公式6是先验概率，表示来自源c的实例的百分比。公式7给出了来自源c的属性j的平均值，即期望值。公式8给出了表示源c中属性j，k的协方差的协方差矩阵。

2.4 基于密度的聚类算法

群集被定义为连接的密集组件，其可以在任何方向上生长，直到密度继续高于阈值。这导致自动避免异常值并检测任意形状的良好分离的簇。基于这种方法的流行方法是Kriegel等的DBSCAN[23]，OPTICS [24]。DBSCAN可以找到非线性可分离的集群，并且不需要集群的初始值来继续。它使用欧氏距离测量来计算空间点之间的距离，因此对维数的诅咒敏感。DBSCAN所需的参数定义了一个点周围的邻域半径和邻域中一个点的最小邻居MinPts。

在DBSCAN中，在xi和其他点之间计算成对距离。对于xi的邻域中的每个点，如果Nptsle;MinPts，则将其标记为核心点。然后对于每个核心点，创建一个新集群或将其分配给集群（如果尚未分配）。递归查找其所有密度连接点，并将它们分配给与核心点相同的集群。迭代数据集中剩余的未访问点。在所有迭代结束时，未分配的点是异常值。

OPTICS是DBSCAN的扩展，旨在解决检测不同密度的簇的缺点。它接受邻域N（P）中的DBSCAN和MinPts的参数。它还为每个被称为核心距离的点定义了一个新的度量，Minpts（P）= C，如公式12所示和可到达距离Minpts（o，p）= R，如公式13所示。

OPTICS根据其基于密度的聚类结构生成聚类排序。

3 实验

第二部分从理论的角度研究了聚类算法，在本节中，它们对聚类基准数据集的性能是为实证评估提供的。

3.1 数据集

选择的数据集是CURE-T2-4K和CLUTO-T8-8K，它们是ClueMiner公开可用的人工生成基准。 可以通过可视化来识别聚类，但聚类算法的性能产生不同的结果。

(a) CURE-T2-4K (b) CLUTO-T8-8K

图1 用于聚类的人工基准数据集

表1 数据集的描述

3.2 实验结果

3.2.1 基于分区的聚类算法

图2中的K-Means，图3中的K-Means 和图4中的RBF内核的K-Means的结果应用于数据集，表明沿轴对称的簇的检测优于不规则形簇。

(a) CURE-T2-4K (b) CLUTO-T8-8K

图2 基于K-means算法的聚类分析

(a) CURE-T2-4K (b) CLUTO-T8-8K

图3 基于K-means 算法的聚类分析

(a) CURE-T2-4K (b) CLUTO-T8-8K

图4 基于kernel K-means算法的聚类分析

3.2.2 模糊聚类算法

必须预先指定簇的数量，并且通过模糊器参数m来控制聚类重叠。使用多次重复进行随机初始化以避免收敛到局部最小值。该方法对噪声敏感并且簇围绕轴对称。未检测到不规则形状的簇。

(a) CURE-T2-4K (b) CLUTO-T8-8K

图5 模糊C均值聚类

3.2.3 基于模型的聚类算法

在数据集上评估基于模型的聚类算法的性能，其中通过10交叉折叠交叉验证选择最终模型配置。将初始种子随机分配12次以避免局部最佳。

(a) CURE-T2-4K (b) CLUTO-T8-8K

图6 基于模型的聚类算法的聚类结果

基于混合模型的聚类在CURE-T2-4K中检测到8个聚类，在CLUTO-T8-8K中检测到24个聚类，如图2所示，错误聚类的实例分别为50.23％和60.66％。这种方法的缺点是最初规定了簇的数量。

3.2.4 基于密度的聚类算法

DBSCAN是参数依赖的并且检测到不规则形状的簇。它有效地处理了噪音。关键的缺点是为特定数据集找到正确的ε和MinPts值。具有不规则密度且分离不良的簇在两个数据集中合并以产生超级簇。OPTICS不是参数敏感的，可以有效识别集群。

(a) CURE-T2-4K (b) CLUTO-T8-8K

图7：DBSCAN算法的聚类结果

(a) CURE-T2-4K (b) CLUTO-T8-8K

图8：OPTICS算法的聚类结果

3.3 实验结果总结

表2 聚类算法评估

名称 时间复杂度 参数 检测Asym聚类