英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
大数据的聚类算法调查：分类和实证分析
摘要 聚类算法已经成为可用的并且强大的元学习工具，并能准确地分析由现代应用产生的大量数据。具体而言，他们的主要目标是将数据分类成簇，使得在同一簇的数据根据某一度量标准具有很高的相似性。在聚类领域有大量的知识，并且这些知识也试图被用于分析和分类大量的应用。然而，大数据的聚类算法在从业者中造成混乱的主要问题之一是对它们性质的定义缺乏共识和正式分类。为了缓解这一问题，这篇文章介绍了聚类的概念和算法，对现存的聚类算法做了简单的调查研究，并从理论和经验角度提供一些比较。从理论而言，我们开发了一个基于之前研究中提出过的主要属性的分类框架，根据经验，我们进行了广泛的实验，使用大量的真实海量数据集来比较每个类别的经典算法。被选中的聚类算法的有效性通过许多内部和外部有效性以及稳定性，运行时间和可伸缩性标准来测量。此外，我们强调了一组对大数据来说性能最好的聚类算法。
关键词：聚类算法；无监督学习；大数据
第一节：简介
当前处于数字时代，伴随着互联网和网络世界技术（例如强大的数据服务器）等技术取得的重大进步和发展，数十年前我们人类还不能够很好的利用来自不同来源和服务的大量数据。海量数据是由人和物一起相互作用而产生的。针对那些来自Twitter，Google，Verizon，23andMe，Facebook，WiKipedia，以及每一个大量用户群里留下数据痕迹和遗留的数据；不同的团体对这些数据潜在的利益和对这些信息的分析所花费的代价进行了争辩。这些数据来源于网络上不同的服务。像传感器网络，云存储，社交网络等，这样的服务和资源提供了大量的数据，同时也需要管理和重复利用或者分析这些数据的方方面面。尽管这些数据可以为人们或者大公司所用，但利用起来依旧十分困难，因此大量数据或者大数据仍有其自身的缺陷。它们需要大的存储空间，这使得各种操作比如说分析操作，过程化操作，检索操作，变得十分困难并且时间开销很大。克服这些困难问题的一种方法是使大数据以紧凑格式聚集，结果仍然是整个数据的信息样式。这样的聚类技术旨在产生高质量的聚类/概要。因此，他们将使普通用户到企业界的研究人员从中大大受益，因为他们可以提供一种高效的工具来处理大数据，如关键系统（以检测网络攻击）。
本文的主要目的是基于真实的海量数据对聚类技术进行实验，为读者提供适合分析不同类别的数据的可用聚类技术。本文不涉及模拟工具。然而，它具体着重每个类的有效算法的使用和实现。它还提供了来自各种大数据集的实验结果。在处理大数据时需要注意一些方面，因此这项工作将帮助研究人员以及从业者选择适合大数据的技术和算法。与传统聚类算法相比，数据容量是大数据聚类算法需要首先考虑的一个显而易见的重要特征，所以在存储系统上需要做出很大的改变。大数据的另一个重要特征是速度，该要求导致对在线处理数据的高需求，其中需要处理速度来处理数据流。多样化是大数据的第三个特征，不同的数据类型，比如说各种各样的数据源像传感器，移动电话等产生的文本，图像和音频。三V（Volume，Velocity，Variety）是大数据的核心特征，是我们在选择聚类技术时要考虑的因素；
尽管在文献[1]，[2]，[7]和[38]中提到的聚类算法对于诸多领域是可用的，比如说机器学习，数据挖掘，信息检索，模式识别，生物信息学，以及语义本体学；它使用户难以决定哪一个算法将是最适合于给定的大数据集。这是因为在调查中会有许多的限制：（i）算法的特性没有得到很好的研究;（ii）该领域产生了许多新的算法，而在这些调查中没有考虑；（iii）一种算法比另一种算法更有优势。由于这些原因，本文试图回顾聚类算法的领域，实现以下目标：
- 提出一个分类框架，系统地将现有聚类算法的集合分类，并从理论的角度比较它们的优点和缺点
- 提出一个完整的分类学聚类评价测量用于实证研究。
- 进行实证研究，分析每个类别最具代表性的理论和经验观点的算法。
因此，本调查提出了聚类算法的分类法，并提出了一个分类框架，涵盖针对大数据选择合适算法的主要考虑因素。它进一步进行涉及每个类别的最有代表性的聚类算法 ，大量的评价度量和10个交通数据集的实验。本文的其余部分安排如下。第II部分提供了对所有类别聚类算法的综述。第III部分描述已经提出的分类框架的标准和属性。第IV部分，我们基于已经提出的分类框架进行归纳和比较不同的聚类算法，第V部分，介绍聚类评估方法的分类，描述实验的框架以及实验的结果，在第VI部分，我们总结这篇文章，并展望未来的研究；
第二节：聚类算法的种类
由于存在多种的聚类算法，本节介绍一个分类框架，将文献中发现的各种聚类算法分组到不同的类别中。所提出的分类框架是一个算法设计者从他的角度开发的，该角度关注于一般聚类过程中的技术细节。因此，不同聚类算法的过程可以大致分类如下：
基于分区：在这一类算法中，所有的簇被迅速确定，初始组被指定并朝着同一单元重新分配。换句话说，分区算法将数据对象划分为多个分区，其中每个分区表示一个集群。这些集群应满足以下要求：（1）每个组必须包含至少一个对象，（2）每个对象必须属于一个组。例如，在K-means算法中，中心是所有点的平均值和表示算术平均值的坐标。在K-medoids算法中，靠近中心的所有对象表示一个簇。还有许多其他分区算法，如K-modes，PAM，CLARA，CLARANS和FCM。
基于层次：数据根据接近度以层次方式组织。近似度由中间节点获得。树状图表示数据集，其中个别数据由叶节点呈现。随着层次继续，初始簇逐渐分成几个簇。分层聚类方法可以是聚集（自底向上）或分裂（自上而下）。聚集聚类从每个聚类的一个对象开始，并递归地合并两个或更多个最合适的聚类。分割聚类从将数据集作为一个聚类开始，并递归地分割最合适的聚类。随着过程继续，直到达到停止标准（通常是所请求的集群数目k）。然而，分层方法有个主要的缺点，其涉及这样的事实，即一旦执行步骤（合并或拆分），这就不能被撤消。BIRCH，CURE，ROCK和Chameleon是这一类别中众所周知的算法。
- 基于密度：在这类算法中，基于数据的密度，连接性和边界的区域来进行分配。他们与最近的点相关联。被定义为连接的密集分量的簇在密度增长的任何方向上增长。因此，基于密度的算法能够发现任意形状的聚类。此外，这提供了对异常值的自然保护。因此，分析点的总体密度以确定影响特定数据点的数据集的功能。DBSCAN，OPTICS，DBCLASD和DENCLUE就是使用这样的方法来过滤掉噪声（多个）并且发现任意形状的簇的算法。
- 基于网络：数据对象的空间被划分为网格。这种方法的主要优点是数据能被快速的处理，因为它通过数据集一次来计算网格的统计值。累积的网格数据使基于网格的聚类技术独立于采用均匀网格来收集区域统计数据的数据对象的数量， 并且在网格上而不是直接地对数据库执行聚类。基于网格的方法的性能取决于网格的大小，这通常远小于数据库的大小。然而，对于高度不规则的数据分布，使用单个均匀网格可能不足以获得所需的聚类质量或满足时间要求。Wave-Cluster和STING是此类别的典型示例。
- 基于模型：这种方法优化给定的数据和一些（预定义）数学模型之间的拟合。它是基于数据是由基本概率混合分布而生成的假设。此外，它生成基于标准统计自动确定聚类的数量，考虑噪声（异常值）并且因此产生鲁棒聚类的方法。有两种主要的方法是基于基于模型的方法：统计和神经网络方法。MCLUST可能是最着名的基于模型的算法，但也有其他好的算法，如EM（使用混合密度模型），概念聚类（如COBWEB）和神经网络方法（如自组织特征映射）。该统计方法使用概率措施确定概念或集群。概率描述通常用于表示每个原始的概念。神经网络方法使用一组连接的输入/输出单元，其中每个连接具有与它相关联的权重。神经网络有若干属性，这使它们能够广泛用来做聚类。首先，神经网络是固有的并行和分布式处理架构。第二，神经网络通过调整它们的互连权重来学习，以便最佳地适合数据。这允许他们正常化或原型化。模式充当各种集群的特征（或属性）提取器。第三，神经网络处理数字向量且仅需要由定量特征表示的对象模式。许多聚类任务仅处理数字数据，或者如果需要，可以将其数据转换为定量特征。聚类的神经网络方法倾向于将每个簇表示为样本。样本充当集群的原型，并且不一定必须对应于特定对象。可以基于一些距离度量将新对象分配给其样本最相似的集群。
图1提供了上述五类分类之后的聚类算法分类的概述。
第三节：基准聚类方法的标准
我们评估大数据的聚类方法时，需要使用特定的标准来评估每个算法相对于大数据三维属性（包括Volume ,Velocity和Variety）的相对优势和弱点。在本文中，我们定义这些属性并编译每个属性的关键标准。
- Volume 是指聚类算法处理大量数据的能力。为了指导关于Volume属性的合适的聚类算法的选择，考虑以下标准：（i）数据集的大小，（ii）处理高维度（iii）处理异常值/噪声数据。
- Variety是指聚类算法处理不同类型数据（数值，分类和层次）的能力。为了指导关于Variety属性的合适的聚类算法的选择，考虑以下标准：（i）数据集的类型（ii）簇形状。
- Velocity指聚类算法对大数据处理的速度。为了指导关于Velocity属性的合适的聚类算法的选择，考虑以下标准：（i）算法的复杂性和（ii）运行时间性能。
接下来，我们详细解释大数据的每个属性的相应标准：
- 数据集类型：大多数传统的聚类算法被设计为聚焦于数值数据或分类数据。在现实世界中收集的数据通常包含数字的和分类的。将传统的聚类算法直接应用于这些类型的数据是困难的。聚类算法对纯数值数据或纯分类数据能有效地工作，其中大多数算法对混合分类和数值数据类型表现不佳。
- 数据集大小：数据集的大小对聚类质量有重大影响。当数据大小较小时，一些聚类方法比其他聚类方法更有效，反之亦然。
- 输入参数： “实用”聚类的理想特征是具有较少参数的特征，因为大量参数可能影响聚类质量，因为它们取决于参数的值。
- 处理异常值/噪声数据：成功的算法通常能够处理离群值/噪声数据，因为大多数实际应用中的数据不是纯的。此外，噪声使得算法难以将其聚类到合适的群集中。因此，这影响了算法提供的结果。
- 时间复杂度：大多数聚类方法必须使用若干次以提高聚类质量。因此，如果过程耗时太长，那么处理大数据的应用程序可能变得不切实际。
- 稳定性：任何聚类算法的重要特征之一是对数据生成相同分区的能力，而不考虑模式呈现给算法的顺序。
- 处理高维度：这是集群分析中特别重要的特性，因为许多应用程序需要分析包含大量特征（维度）的对象。例如，文本文档可以包含数千个词语或关键字作为特征。这是富有挑战性的，许多维度可能不相关。随着维度的数量增加，数据变得越来越稀疏，使得点对之间的距离测量变得无意义，并且数据中的任何地方的点的平均密度可能较低。
- 聚类形状：一个好的聚类算法应该能够处理真实数据及其各种各样的数据类型，并且产生任意形状的聚类。
第四节：备选的聚类算法
本节旨在为大数据找到良好的候选聚类算法，所谓良好的，是指满足大部分第三节列出的那些标准算法。表1提供了我们基于所述标准对第II节中描述的各种方法进行的评价的概述。在此评估之后，下一步是基于所提出的标准从每个类别中选择最合适的聚类算法，以便为大数据提供基准。以这种方式，从每个方法中选择最佳算法，并且将正确地评估这些被选择的算法。该过程产生以下选择：FCM [6]，BIRCH [40]，DENCLUE [17]，OptiGird [18]和EM [8]。
本节详细讨论每个选定的算法，介绍它的工作原理，它的优点和缺点，以及它需要的输入参数。
表1 关于大数据属性和第III节中描述的其他标准的聚类算法分类
A . Fuzzy-Cmeans（FCM）
FCM [6]是一种基于K-means概念的将数据集分割成簇的模糊聚类的代表性算法。FCM算法是一种“软”聚类方法，将对象根据置信度分配给相应的聚类。因此，对象可以属于具有不同置信度的多个簇。它试图找到每个群集中最具有特征的点，设为一个群集的中心 ; 然后计算群集中每个对象的相似度。模糊的c-means 算法也是最小化群内方差。然而，它继承K-means的诸多问题，因为最小值只是一个局部的，最终的集群取决于权重的初始选择。
FCM算法遵循K-means算法的相同原理，即它迭代地搜索聚类中心并更新对象的相似度。主要的区别在于，不是对数据点应属于哪个集群做出硬判决，而是为对象分配范围从0到1的值，以测量对象属于某个集群的可能性。模糊规则表明数据点对所有聚类的相似度值的和必须为1.相似度越高，对象就越有可能属于该聚类。FCM聚类通过使等式1中所示的目标函数最小化来获得：
J是目标函数，n是数据量，c为定义的聚类数，mu;ik是将对象i分配给聚类k的可能性大小，m是模糊性因子（mlt;1）,|pi-vk|是欧几里得距离公式，由等式2定义第i个对象到第k个聚类的中心距离vk；
第k个聚类的中心通过公式3进行更新：
使用原始的公式4计算模糊可能性：
该算法已被扩展用于聚类RGB彩色图像，其中等式2中给出的距离计算被修改如下：
如前所述，这有一个迭代过程（见FCM伪代码）。
FCM伪代码:
输入：给定数据集，设置期望的簇数C ，模糊参数 m （m是gt;1的常数）和停止条件，初始化模糊分区矩
全文共13793字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[143294]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
