英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
大数据聚类算法的综述：分类与实验分析
ADIL FAHAD1,4, NAJLAA ALSHATRI1, ZAHIR TARI1, (Member, IEEE), ABDULLAH ALAMRI1,
IBRAHIM KHALIL1, ALBERT Y. ZOMAYA2, (Fellow, IEEE), SEBTI FOUFOU3, AND ABDELAZIZ BOURAS3
1School of Computer Science and Information Technology,
Royal Melbourne Institute of Technology, Melbourne, VIC 3000, Australia
2Centre for Distributed and High Performance Computing, School of Information Technologies,
University of Sydney, Sydney, NSW 2006, Australia
3Department of Computer Science, College of Engineering, Qatar University, Doha 2713, Qatar
4Department of Computer Science, Al-Baha University, Al-Baha City 65431, Saudi Arabia CORRESPONDING AUTHOR: A. FAHAD (alharthi.adil@gmail.com)
摘要：聚类算法已经成为另一种强大的元学习工具，可以准确分析现代应用程序产生的海量数据。特别是，他们的主要目标是将数据分类到集群中，当某些对象的某些指标相似时，则把他们分类到同一个集群中。在聚类领域有广泛的知识体系，并且一直有人试图对它们进行分析和分类以获得更多的应用。在大数据中使用聚类算法的一个主要问题是会导致从业者混淆，因为他们的属性定义缺乏一致性，也缺乏正式的分类。为了缓解这些问题，本文引入了与聚类有关的概念和算法，对现有（聚类）算法进行简要的概述，并从理论和实验两个角度进行比较。 从理论角度来看，我们根据以前研究中指出的主要特性开发了一个分类框架。 在实验上，我们进行了大量实验，在这些实验中，我们使用大量数据集比较了每个类别中最具代表性的算法。聚类算法的有效性通过一系列内部和外部有效性指标，稳定性，运行时间和可扩展性测试来衡量。 另外，我们强调了处理大数据性能最佳的一组聚类算法。
关键词：聚类算法，无监督学习，大数据
- 导论
在当前的数字时代，随着互联网技术的迅速发展，比如强大的数据服务器技术，我们每天都会从许多不同的资源和服务中获得大量的信息和数据，而这些资源和服务几十年前还不能使用。大量的数据是由人员，事物及其相互作用产生的。在Twitter，Google，Verizon，23andMe，Facebook，维基百科以及大量用户留下数据的网站，各类团队一直在探索分析数据的潜在益处和成本。传感器网络，云存储，社交网络等服务和资源产生大量数据，并且还需要管理和重用数据。虽然海量的数据对于人们和企业来说可能非常有用，但它也可能存在问题。他们需要大容量存储器，而这个容量使诸如分析操作，处理操作，检索操作等操作非常困难并且非常耗时。 克服这些困难问题的一种方法是将大数据聚集为紧凑格式。这种聚类技术旨在产生高质量的集群/摘要。 因此，他们可以为普通用户，研究人员和企业界人士带来巨大收益，因为他们可以提供处理大数据（如防御系统（检测网络攻击））的高效工具。
本文的主要目标是通过在真实的大数据上进行实验，为读者提供对不同类别的聚类技术的适当分析。本文没有提到模拟工具。但是，它专门研究每一类中某种高效算法的使用和实现。它还提供各种大数据集的实验结果。有些方面在处理大数据时需要小心，因此这项工作将有助于研究人员和从业人员选择适合大数据的技术和算法。 与传统的数据聚类相比，数据量是处理大数据时的首要和明显的重要特征，因为这要求存储系统的体系结构有很大的变化。大数据的另一个重要特征是速度。即对数据的在线处理需求很高。种类是第三个特征,不同的数据类型,如文本、图像和视频,从各种来源,如传感器、手机等等。这三个V(量、速度和种类)是选择合适的聚类技术必须考虑的核心特征。
尽管文献[1]，[2]，[7]和[38]对各种领域（如机器学习，数据挖掘，信息检索，模式识别，生物信息学，语义本体论）中的聚类算法都有了调查，用户很难先验地决定哪一种算法对于给定的大数据集是最适合的。 这是因为现有调查中存在一些局限性：（i）算法的特征没有得到很好的研究; （2）该领域已经产生了许多新的算法，这些调查没有考虑到这些算法; （iii）没有进行严格的实验分析来确定一种算法相对于另一种算法的好处。 基于这些原因，本文试图回顾聚类算法领域并实现以下目标：
bull;提出一种分类框架，系统地将现有的聚类算法集合归类到分类中，并从理论的角度比较它们的优缺点。
bull;准备完整的评价指标用于实验。
bull;以理论和实验的角度，对每个类别的最具代表性的算法进行实验研究。
因此，这份调查提出了聚类算法的分类，并提出了一个分类框架，该框架涵盖了选择合适的大数据算法的主要因素。它进一步进行实验，包括每个类别最具代表性的聚类算法，大量评估指标和10个流量数据集。本文的其余部分安排如下。第二部分提供了聚类算法类别的回顾。 第三节描述了分类框架的标准和属性。 在第四节中，我们根据所提出的分类框架对不同的聚类算法进行分组和比较。第五部分介绍了聚类算法的评估指标的分类，介绍了实验框架并总结了实验结果。在第六部分，我们总结了这篇论文并讨论了未来的研究。
- 聚类算法分类
由于有很多聚类算法，本节介绍一个分类框架，将文献中找到的各种聚类算法分为不同的类别。 所提出的分类框架是从算法设计者的角度开发的，其重点在于聚类过程的技术细节。 因此，不同聚类算法的过程可以大致分类如下：
bull;基于分区的:在这种算法中，所有的集群都是快速确定的。初始组被指定并重新分配给一个联合。换句话说，分区算法将数据对象划分为多个分区，每个分区代表一个集群。这些集群应该满足以下要求:(1)每个组必须包含至少一个对象，并且。(2)每个对象必须属于一个组。例如，在K-means算法中，中心是所有点的坐标的算术平均值。在K-medoids算法中，靠近中心的对象表示集群。还有许多其他的分区算法，如k模式，PAM, CLARA, CLARANS和FCM。
bull;基于层次的:数据以分层的方式组织，这取决于邻近的媒介。接近度由中间节点获得。树状图表示数据集，其中单个数据由叶节点表示。随着分层的继续，初始集群逐渐分为几个集群。层次聚类方法可以是聚集性的(自底向上的)或分裂性的(自顶向下的)。聚集性的聚类从一个对象开始，然后递归地合并两个或多个最合适的集群。分裂性的聚类首先把数据集作为一个集群，然后递归地分割最适当的集群。该过程将继续，直到达到停止标准(通常为集群数量k)。但是，分层方法有一个主要的缺点，它一旦执行了一个步骤(合并或分割)，就无法撤消。BIRCH，CURE，ROCK和Chameleon是这一类著名的算法。
bull;基于密度的:在这种方法中，数据对象根据其密度、连通性和边界分开。它们与点最近的邻居关系密切。一个被定义为密集的集群，在向着密度引导的任何方向上生长。因此，基于密度的算法能够发现任意形状的集群。此外，这提供了一种对异常值的保护。因此，常常分析一个点的整体密度，以确定影响特定数据点的数据集的功能。DBSCAN，OPTICS，DBCLASD和DENCLUE都是使用这种方法来滤除噪音并发现任意形状的集群的算法。
bull;基于网格:数据对象的空间被划分为网格。这种方法的主要优点是它处理快速，因为它通过数据集一次性计算网格的统计值。积累的网格数据使得基于网格的聚类技术独立于使用统一网格收集区域统计数据的数据对象的数量，然后在网格上执行集群，而不是直接在数据库中执行。基于网格的方法的性能取决于网格的大小，而网格的大小通常比数据库的大小要小得多。然而，对于高度不规则的数据分布，使用单一的统一网格可能不足以获得所需的聚类质量或满足时间要求。Wave-Cluster和STING是这一类典型的例子。
bull;基于模型:这种方法优化了给定数据和一些(预定义的)数学模型之间的匹配。它基于数据是由潜在的概率分布的混合生成的假设。此外，它还产生了一种自动确定基于标准统计数据的集群数量的方法，将噪声(异常值)考虑在内，从而产生一个健壮的聚类方法。基于模型的方法有两种主要的方法:统计和神经网络方法。MCLUST可能是最著名的基于模型的算法，但也有其他好的算法，比如EM(它使用混合密度模型)、概念聚类(如COBWEB)和神经网络方法(例如自组织特征映射)。统计方法使用概率来确定概念或集群。概率描述通常被用来表示每个派生的概念。神经网络方法使用一组连接的输入/输出单元，其中每个连接都有一个与之相关的权重。神经网络有几个特性使得它们在聚类中很受欢迎。首先，神经网络具有并行和分布式处理架构。其次，神经网络通过调整它们的互连权重来学习，以便最适合数据。这使他们能够正常化或原型化。模式作为各种集群的特性(或属性)提取器。第三，神经网络处理数值向量，要求对象仅用数值特征来表示。许多聚类任务只处理数值数据，或者如果需要，可以将数据转换为数值特性。聚类的神经网络方法倾向于将每个集群表示为一个范例。范例作为集群的原型，并不一定要对应特定的对象。新的对象可以被分配到一个集群中，这种对象的范例是最相似的并且基于一些距离值。
图1提供了按照上述五种分类集群算法的概况。
- 标准的聚类方法
当评估大数据的聚类方法时，需要使用特定的标准来评估每一种算法相对于大数据的三维属性(包括数量、速度和种类)的相对优点和弱点。在本节中，我们定义了这些属性并综合了每个属性的关键标准。
bull;Volume指聚类算法处理大量数据的能力。为了选择针对数量属性的合适的聚类算法，考虑了以下标准:(i)数据集的大小，(ii)处理高维度和(iii)处理异常值/噪声数据。
bull;Variety是指聚类算法处理不同类型数据(数值、类别和层次)的能力。为了选择针对多样性属性的合适的聚类算法，我们考虑了以下标准:(i)数据集类型和(ii)簇形状。
bull;Velocity指的是聚类算法的速度。为了选择针对速度特性的合适的聚类算法的，考虑了以下标准:(i)算法复杂度和(ii)运行时长性能。
在接下来的内容中，我们详细解释了大数据的每个属性对应的标准:
1)数据集类型:大多数传统的聚类算法都是针对数值数据或分类数据而设计的。在现实世界中收集的数据通常包含数值和类别属性。传统的聚类算法很难直接应用到这些数据中。聚类算法在纯数值数据或纯分类数据上有效;它们中的大多数在混合分类和数值数据类型上表现不佳。
2)数据集大小:数据集的大小对聚类效果有较大影响。当数据大小比较小的时候，一些聚类方法比其他方法更有效，反之亦然。
3)输入参数:“实用”聚类的一个理想特征是参数较少，因为大量参数可能影响聚类效果，因为它们将依赖参数的值。
4)处理异常值/噪声数据:一个成功的算法通常能够处理异常值/噪声数据，因为大多数实际应用程序中的数据不纯。此外，噪声使得算法很难将对象聚类到合适的集群中。这就影响了算法的结果。
5)时间复杂度:大多数聚类方法必须多次使用以提高聚类效果。因此，如果过程耗时太长，那么处理大数据的应用程序就会变得不切实际。
6)稳定性:任何聚类算法的一个重要特征是，无论在何种顺序下，都可以生成相同的数据分区。
7)处理高维度:这在集群分析中尤其重要，因为许多应用程序需要对包含大量特性(维度)的对象进行分析。例如，文本文档可能包含数千个术语或关键字作为特性。由于维度的影响，这项任务很有挑战性。许多维度可能不相关。随着维数的增加，数据变得越来越稀疏，因此点对点之间的距离变得毫无意义，数据中任何地方的平均密度可能都很低。
8)集群形状:一个好的聚类算法应该能够处理真实数据和各种数据类型，从而产生任意形状的集群。
- 候选聚类算法
本节主要为大数据找到好的候选聚类算法。我们参考了那些满足第三节中大部分标准的算法。表1提供了我们根据所描述的标准对第二节中的各种方法进行的评价的概括。在此评估之后，下一步是根据所建议的标准从每个类别中选择最合适的聚类算法，以便对大数据进行测试。这样，从每个方法中选择了最好的算法，并对这些(选择的算法)进行了正确的评估。这个过程产生了以下选择:
FCM [6], BIRCH [40], DENCLUE [17], OptiGird [18] and EM [8].
本节将详细讨论每种选择的算法，说明它是如何工作的，它的优点和缺点，以及它所需要的输入参数。
- FUZZY-CMEANS (FCM)
FCM[6]是一种基于K-means概念的模糊聚类的代表性算法，它将数据集划分成集群。FCM算法是一种“软”聚类方法，它将对象分配给具有一定信度的集群。因此，一个对象可能属于多个不同信度。它试图找出每个集群中最具有特征的点，称为一个集群的中心;然后计算集群中每个对象的成员数量。模糊c-means算法最小化了集群内方差。然而，它继承了K-means的问题，因为最小值是局部的，而最终的集群取决于最初权重的选择。
FCM算法遵循K-means算法的相同原理，即迭代地搜索集群中心并更新对象的成员。主要的区别在于，它没有试图决定像素应该属于哪个集群，而是分配一个数值给对象，从0到1，以度量对象属
全文共13319字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13816]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
