大数据挖掘聚类方法综合研究外文翻译资料

 2022-12-20 21:20:48

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

大数据挖掘聚类方法综合研究

Divya Pandove ,Dr. Shivani Goel Thapar University Patiala, India1

摘要：技术进步使我们能够在相对较短的时间内存储和处理大量数据项。 “大数据”一词仅指工业和研究界经常使用的大量数据。这里的重点不仅仅是数据的收集，而是对收集的数据进行仔细分析，以便获得有意义的结果。有各种方法来处理巨大的传入数据流。一种方法是将数据聚类成紧凑的单元。这不仅减小了数据的大小，而且有助于以更有效的方式利用它。本文对基本聚类算法进行了概述和比较，并提出了聚类方法对各种规模数据集的适用性。还给出了聚类算法演化的简要介绍。

关键词：聚类算法，分层聚类，k均值聚类，BFR，CURE

  1. 数据聚类和聚类策略的介绍

聚类是用于将数据项累积到组中的过程的术语。这些数据项表示为点。检查各个点，并以按照一定规则计算出来的距离为依据，将其放置在不同的簇中。重点是同一群集中的点应该具有彼此的距离很小，而不同群集的成员点应该彼此相距很远。

根据基本差异，聚类策略可分为两部分：

  1. 分层或凝聚算法

这种方法基于检查各种数据点的接近程度。亲密度的定义是主观的，可以从许多闭合的定义中找到。在开始时，每个点自己形成一个簇。然后基于所选择的衡量相似度的标准迭代地合并这些簇。群集的合并基于预先定义的特定标准而结束。最后一次迭代给出了明确定义的聚类。

  1. 点分配算法

这种方法有很多变种。它们背后的基本原则仍然是将点分配给它们最适合的集群。通常，在过程本身的开始估计初始簇数。各种技术的变化在于群集或决策的组合和分裂，如果它们是异常值，那么哪些点将保持未分配。

  1. 分层方法

这种方法最适合小型数据集。但它可以用于实现其他方法。从每个点自己构成一个簇。随着时间的推移，较小的簇的不断组合形成较大的簇。考虑的要点是：

  1. 集群的表示
  2. 要合并的集群的选择
  3. 什么时候停止合并

在处理完这些要点之后，接下来的步骤包括一个while循环，它运行直到所有可以合并的集群合并在一起。

    1. 分层聚类的效率

每个迭代步骤涉及计算两个簇之间的距离，以便找到合并的最佳匹配。这涉及大量计算。因此算法效率不高。它适用于小规模数据集。虽然，为了获得更好的结果，进行了许多变化。该算法具有三次时间复杂度。初始步骤需要O()时间。之后的步骤需要的时间。 时间的和是O()，是的立方。

    1. 控制的补充规则

此类方法常用的标准是距质心最小距离。最小距离的测量方法没有很好地定义。可以有许多规则可以从中选择最适合的控制方法。其中一些是：

  1. 从不同的簇中选择两个点，它们之间的距离被视为任意两点之间的最小距离。这成为所有簇和所有点的参考的最小距离。
  2. 将两个簇之间的所有点的距离的平均值作为两个簇之间的距离。
  3. 定义簇的半径，使其给出质心和簇中所有点之间的最大距离。比较两个簇并组合时半径最小的簇。
  4. 簇的直径也可以定义为簇中任意两点之间的最大距离。合并具有最低组合直径的那些。

在簇中，半径和直径不像圆圈那样直接相关。它们可能彼此成比例，但这也取决于点的性质。

  1. 点指派方法
    1. K-Means算法

K-means算法是典型的点分配算法。该方法初始假设了簇的数量。该数字被视为k，可以通过反复试验推断出来。选择正确的k值是k-means中的基础。如果采用诸如平均直径或半径的标准，则该值增长直到假设的簇数保持不变或大于形成的实际簇数。如果假设的簇小于簇的实际数量，则值会危险地上升，如图2所示。

为了选择正确的值，k可以取值为1,2,4,8，......直到我们得到两个值v和2v，在这两个值之间平均直径或半径几乎没有减小。k的值位于v / 2和v。现在二进制搜索可用于定位k的值。将总聚类作为，可以在()聚类操作中找到k的最佳匹配。在选择k的初始值之后，将这些点作为聚类的质心。然后将剩余的点表示为“p”。然后使用For循环检查这些点，这是该方法的核心。对于每个p，找到最接近它的质心，并将p添加到相应质心的簇中。质心也因此被调整。算法步骤如图3所示。

    1. 布拉德利，法耶兹和雷纳（BFR）的算法

这种方法是k-means算法的改进，适用于聚集大量数据。它假设群集的形状必须正常分布在质心周围。群集的均值和标准差可能因不同维度而不同。此方法也从选择k点开始。然后以块的形式读取所有点。然后将这些块分割成适当的大小。大小应该可以在主存储器中处理。主存储器还包含k个簇的摘要以及其他数据。此数据包含三种类型的对象：

  1. 丢弃集：这些可以看作具有简单摘要的集群的元数据。摘要表示的点将被丢弃，并且在主存储器中没有表示。
  2. 压缩集：这些是彼此接近但不与任何集群相关的点的摘要。压缩集表示的点也不会在主存中显式出现。
  3. 保留集：此集包含的点，既不能分配给集群，也不能用压缩集表示。这些点完全按照输入文件中的表示存储在主存储器中。图4显示了主存储器中对象的细节。

在BFR中，数据的处理方式如下所述：

  1. 所有靠近群集质心的点都会添加到群集中。
  2. 不接近任何质心的点聚集在保留的集合中。任何聚类算法（例如分层聚类）都可用于此目的。群集摘要将添加到压缩集中。单点集群被分配给保留集。
  3. 现在聚类新点和先前保留的集合，形成迷你集群。迷你集群也是由旧的压缩集形成的。这些不能与任何k个集群合并，但可以相互合并。
  4. 不在保留集中的点，即分配给迷你集群或集群的点被分配给辅助存储器。
  5. 对于最后一块输入数据，需要处理压缩和保留的集合。它们可以被视为大纲并且永远不会再聚集，或者可以将保留集中的每个点分配给最近的质心所属的簇。现在可以将每个小型簇合并到其质心与小型簇的质心最近的簇汇中。关于点p与给定簇的距离的的计算标准，可以再次使用用于控制k均值算法中的k值的任何技术。图5包含BFR算法的步骤。
    1. CURE算法

该算法用于聚类大规模数据集。它没有对簇的形状做出任何假设。分布可以是环形，S形或奇怪的弯曲形式。簇由一组表示点而不是质心表示.CURE算法的第一步是采集一小部分数据样本并在主存储器中创建簇。理论上，可以应用任何聚类方法，但是大多数情况下应用分层聚类，因为CURE被用来处理形状奇特的簇。然后，从每个簇中选择一组点作为代表点。这些点之间的距离应该是可能取到的最大值。然后，代表点在其当前位置与其簇的质心之间移动固定距离。在CURE算法的完成阶段，如果两个簇各自的代表点足够接近，则它们将被合并。 “关闭”的定义是用户提供的距离。合并继续，直到没有足够接近的簇。

CURE的最后一步是点分配。每个点p来自二级存储器并与代表点进行比较。点p被分配给最接的代表点所属的簇。图6表示CURE算法的算法步骤。

  1. 聚类算法的演化

在详细讨论了基本的聚类算法之后，重要的是要简要讨论在这些方法之后出现的聚类策略以及它们之前存在的聚类策略。最初，决策树学习是一种用于处理大型数据集的流行技术。Bowyer等致力于使用所有相关的和独立的数据集开发单一的决策系统。后来Patel等使用了一种将遗传算法和决策树相结合的混合方法。他们提出了一种优化的决策树，不仅提高了效率，而且提高了性能。

然后，这种方法被各种聚类技术所取代。许多革命性的算法被提出，如BIRCH（平衡迭代层次结构）和CLARANS。这些方法专注于大型数据集。例如，BIRCH动态地聚合多维数据点。它旨在通过单次数据扫描找到一个好的集群，并使用额外的扫描来改善簇的质量。一种称为GLC 的算法被提出。这种方法处理混合类型的数据集。另一种技术PROXIMUS在数据集中发现了模式。它压缩事务集，从而加快了挖掘关联规则的形成，从而提高了聚类效率。在处理动态数据集时，基本的聚类策略并不十分有效。为了使分层方法在实际应用中更有效，提出了一种混合方法。它被命名为“用于概念挖掘的流分层聚类”，并阐述了一种新的算法，该算法从大量数据集中提取语义内容。该算法在硬件本身中实现，以便处理高速率的数据。

分层方法应用于人工神经网络，以识别高度相似的大数据集。出现了诸如SOM（自组织特征映射）网络和学习矢量量化（LVQ）网络的技术。当LVQ使用监督学习时，SOM接受无监督输入。它将大型数据集分类为更小的单位，从而缩短了计算时间。最近，在2012年，王使用物理科学的概念提出了一种聚类算法。此方法生成对象之间的交互，然后将它们分组以形成簇。与K-Means，CURE，BIRCH和CHAMELEON的对比表明，该算法比所有算法都更有效。“使用关联网络分析大型生物数据集”中描述了另一种独特的方法。该算法将表格等中收集的数据转换为称为ANets的关联网络。之后，它可以生成关联规则。完成此工作后，可以将任何聚类算法应用于它们。唯一的限制是数据集在语法和语义上应该是正确的，以获得所需的结果。

这些就是一些随着时间的推移而发展的聚类技术。为了提出新技术，已经对各种基本方法做了无数的排列和组合，但是其中大多数的核心仍然是基本算法，例如Hierarchical和Kmeans。

  1. 研究结果

上面讨论的各种方法具有许多重叠的特性。这些属性有助于根据数据量指示相应算法的适用性。已经识别了一些共同特性，例如合并各种聚类的标准，基于其可以对质心的识别或关于簇的数量和形状的初始假设进行区分。出现的细微差别是每种方法中读取数据点的方式。数据大小大致分为小型，中型，大型和超大型。所有确定的属性有助于确定最适合的方法和数据大小之间的关系。这些总结在表1中。表1以更系统和客观的方式概述了各种方法的优点和缺点。可以清楚地看到在各种方法中应用各种共同特性的区别。

区分基于分层和点分配的方法的第一个标准是用于合并较小的簇以形成较大的簇的标准。分层方法使用“接近度”度量，而所有点分配方法使用最佳拟合的顺序。此外，找到簇的质心并在它们周围形成簇这一共同特性，仅由k-means和BFR算法使用，而不是通过分层和CURE方法。在某些方法中有许多初步假设，而在其他方法中则没有。例如，k-means和BFR算法假设初始簇数，分层方法假定每个点本身都是一个簇，CURE使用表示点。分层方法和k均值算法不对质心周围的数据分布做出假设，而BFR假设数据正常分布在质心周围。 CURE算法通过处理数据来扩展其适用性，数据奇怪地以环形，S形或奇怪的弯曲形式分布。

重要的考虑因素是读取数据的方式。这决定了各种方法的处理能力。分层方法和k-means算法一次读取单个数据点，花费更多的处理时间，所以它们适用于小数据集。BFR从主存储器中读取数据块。 CURE通过定义代表点来采用不同的方法。所有这些点都有助于确定通过某种方法能有效聚类的数据大小。分层方法最适合少量数据。因此，当需要完成数据内的数据聚类时，该方法也用于其他方法的子循环中。中等大小的数据可以定义为容易对簇的数量进行初始假设的数据。当要处理中等大小的数据时，最好的算法是k-means算法，即点赋值类的基本方法。当要处理大量数据时应用BFR。这里巨大的数据块将数据点分配给各种集合。主要目的是以块的形式处理大量数据，以最大限度地缩短处理时间.CURE是一种大数据处理方法。它通过代表点在不同阶段工作。此方法使用最新技术，可以加快处理速度。

各种聚类技术的发展带来了更好的观点。它表明，随着大数据领域知识的不断增长，出现了许多新的算法。虽然他们所有人都有自己的不同，但他们倾向于使用一些概念或其他基本聚类算法。进一步观察到，通过分析数据集的类型和模式需要相关的方式，出现了对给定方法的需求。表2给出了各种作者给出的基本聚类算法的比较。

  1. 结论

由于数据量的增加，有必要找到用于数据分析的最佳技术。

本文阐述了聚类这种大型数据集的各种技术。讨论并比较了基本的大数据聚类技术。讨论的各种算法有许多相似之处和不同之处。它们可以单独使用，也可以相互组合使用。算法的选择取决于数据类型和处理能力以及要求。处理的未来强调各种算法的混合，因为它将结合基本算法的优点并消除缺点。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19487]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章