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

在线提供www.sciencedirect.com

科学直通车

Procedia Computer Science 83（2016）560 - 567

第七届环境系统，网络和技术国际会议（ANT 2016）

DENCLUE-IM：大数据聚类的新方法

Hajar REHIOUIlowast;, Abdellah IDRISSI, Manar ABOUREZQ, Faouzia ZEGRAARI

计算机科学实验室（LRI）计算机科学系理学院

拉巴特的穆罕默德五世大学

摘要

每天，社交网络中由多个源，以及移动设备生成大量数据。这种多样的数据源产生异构数据，这些数据以高频率产生。允许更好地使用和利用这种复杂数据的技术之一是群集。在性能和速度响应时间之间找到折衷方案是对这种巨大数据进行分类的主要挑战。为此，我们提出了一种有效的算法，它是DENCLUE的改进版本，称为DENCLUE-IM。背后的想法是通过避免DENCLUE中的关键步骤来加速计算，这是登山算法的一步。本文使用大数据集的实验结果证明了我们提出的算法的效率。

关键词：大数据;聚类;基于密度的聚类;DENCLUE。

copy;2016作者。由Elsevier BV发布这是CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/).

会议计划主席负责的同行评审

介绍

技术革命每天产生数十亿字节的异构数据。根据研究所IDC 1的调查，2011年创建了1.8个zettabyte数据，2012年为2.8个zettabytes，2020年将增加到40个zettabytes。这一大量复杂数据可以作为大数据的一部分，需要更先进的技术来更好地存储，使用和分析。

有几个命题来定义大数据 2。最广泛使用的定义是Gartner 3提出的定义，它基于3 V的概念：Volume数量，Velocity速度和Variety多样性。

数量：世界上的数据量呈指数增长。例如，根据2012年的统计数据4，Twitter每天产生7TB数据，Facebook产生10TB数据。这些海量数据将成为未来的主要挑战。

bull;

lowast;通讯作者。电话： 212-674-206-349。

电子邮件地址：rehioui.hajar@gmail.com

1877-0509copy;2016作者。由Elsevier BV发布这是CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/).

会议议程主席负责的同行评审：10.1016 / j.procs.2016.04.265

速度：数据创建的速度和高频率是一个真正的挑战，特别是在实时应用中。我们必须注意，每小时生成数千TB的数据 5。

bull;

多样性：从社交网络，智能手机，传感器等产生大量数据。结果，产生了异构数据。

bull;

在这种背景下，研究人员已经朝着为大数据定义添加其他V的方向前进。胡布尔等人。 6建议对信息的正确性和准确性的研究是必要的，然后包括第四个V的准确性。J. Gantz和D. Reinsel 7考虑了另一个有价值的V.分析后提取的数据值比数据本身更重要。可变性是NIST 8提出的第六个V，它指的是影响相同信息含义的转换，在其他情况下引用。

如上所述，大数据产生异构数据（Variety），这使得难以利用。为了克服这些限制，可以将聚类方法视为有前途的解决方案。通常，大数据中的挑战是提供一种聚类方法，该方法在合理的运行时间内产生可接受的聚类质量。为此，基于密度的聚类方法得到了广泛的应用，这要归功于它们对大型数据库（Volume）进行分类的能力，以及它们省略噪声数据的效率（Veracity）。

在这方面，M。Ester等人。 9提出了一种DBSCAN方法作为一种新的基于密度的聚类算法

空间数据库。基于这项工作，在文献中提出了许多DBSCAN变体，如OPTICS 10，ST-DBSCAN 11，MR-DBSCAN 12等。但是DBSCAN及其变体仅在空间数据上有效运行，并且对于大尺寸数据有其局限性。为了克服这些缺点，DENCLUE算法由A. Hinneburg和DA Keim提出 13。

然而，DENCLUE算法在执行时间方面受到损害。这是由于爬山方法将收敛减慢到局部最大值。这就是为什么在目前的贡献中，我们的目标是改进该算法，以便在合理的响应时间内获得聚类。

本文的结构如下。我们在下一节介绍DENCLUE算法。我们在第3节中提出了改进。我们在第4节中公布实验结果，在第5节中总结。

数据聚类

被称为无监督分类的聚类是将一组数据分类为同类组（聚类）的过程。每个群集中的元素应该相似。因此，同一群集（类内）中的个体之间的相似性必须在不同群集（群际间）之间小而高。这种相似性被认为是距离测量。在数学上，数据聚类的最终目标是将一组未标记的对象O = o₁，o₂，...，o_n 划分为k个聚类。每个对象的特征在于特征向量X = x₁，x₂，...，x_p ，其中p是其维度。文献中开发了大量聚类方法，可以根据某些特定标准 16对其进行分组 14,15。但一般来说，它们分为五个系列 17,18，如图1所示。

基于模型

集群

基于网格的聚类

基于密度

集群

分区聚类

分区聚类：这种类型的聚类是最简单的聚类，其功能是将数据划分为多个聚类。为了达到这个目标，形成并组装初始组以便具有最终的簇。

bull;

分层聚类：此类型组对象为聚类树，此类算法分为两类，分裂（从上到下）和凝聚（从下到上） 19。第一种类型将所有数据放入单个集群中，然后将其分层次分割，直到形成最终集群。第二种类型将数据库的每个对象放在一个集群中，然后在递归之后将它们合并，直到形成最后的集群。基于密度的聚类：在此类型中，对象基于其密度区域进行分类。基于密度的算法能够发现任意形状的类并省略嘈杂的对象。

bull;

bull;

基于网格的聚类：在这种类型的聚类中，数据被划分为对象网格。此类型将算法应用于网格，而不是直接将其应用于数据库。

bull;

基于模型的聚类：此类型基于数据由概率分布生成的假设。这些方法旨在为每个集群发出模型假设，然后找到数据与模型的最佳拟合。

bull;

在这项工作中，我们特别关注基于密度的聚类算法。这一系列方法已经证明了它在聚类方面的效率，因为它可以找到任意形状的簇并且还可以检测噪声对象。在这种情况下，我们专注于DENCLUE算法。与文献 17,13中所证明的其他基于密度的算法相比，该方法的特征在于其快速响应时间。

• 1. DEWNCLUE

DENCLUE 13（基于DENsity的CLUstEring）被认为是核密度估计（KDE） 20,21,22的特例。KDE是一种非参数估计技术，旨在找到密集区域点。DENCLUE的作者开发了这种算法来对大型多媒体数据库进行分类，因为这种类型的数据库包含大量噪声，并且需要聚类高维特征向量。

原则上，DENCLUE通过两个阶段运行，即预聚类步骤和聚类步骤，如图2所示。第一步是构建数据库的映射（超矩形）。此映射用于加速密度函数的计算。至于第二步，它允许从高度填充的立方体（其中点的数量超过参数中确定的阈值xi;的立方体）以及它们相邻的填充立方体中识别聚类。

DENCLUE基于计算它们之间点的影响。这些影响函数的总和代表密度函数。基于两点x和y之间的距离存在许多影响函数;但我们将专注于高斯函数的这项工作。

从 13导出的等式（1）示出了两个点x和y之间的影响函数。

(1)

其中d（x，y）是x和y之间的欧氏距离，sigma;代表含邻域的半径

x.

从 13中提取的等式（2）表示密度函数。

(2)

其中D表示数据库上的点集，N表示其基数。

为了确定聚类，DENCLUE计算数据库中每个点的密度吸引子。该吸引子被认为是密度函数的局部最大值。这个最大值是通过Hill Climbing算法找到的，该算法基于梯度上升方法 22，如公式（3）所示，在 13中给出。

(3)

当f d（xk）lt;f d（xk 1）与k时，计算结束 N，然后我们将xlowast;= xk作为密度吸引子。

isin;

形成具有密度吸引子的路径的点被称为吸引点。通过考虑密度吸引子及其吸引点来制造簇。

该算法的优势在于选择用于呈现数据的结构。A. Hinneburg和DA Keim 13选择使用超矩形的概念。超矩形由超立方体构成。每个超立方体由特征向量点的维度（即，标准的数量）和密钥表示。通过使用立方体键，并且仅考虑填充的多维数据集，此结构允许DENCLUE对数据进行简单的操作。

图2：DENCLUE过程。

但是，在群集质量和执行时间方面，在DENCLUE中使用Hill Climbing存在局限性。我们强调登山不会精确地收敛到最大值，这是最接近的。为了克服这些限制，我们在之前的工作 23中实现了两种算法：DENCLUE-SA和DENCLUE-GA。它们基于两种有前途的元启发式算法取代爬山算法：模拟退火（SA）和遗传算法（GA）。尽管这两种算法具有良好的聚类性能，但它们在运行时执行方面受到了影响。为了在大数据框架中有效地调整DENCLUE算法，我们在这项工作中开发了DENCLUE算法的改进版本，我们将其称为DENCLUE-IM。它将在下文介绍。

建议的聚类方法：DENCLUE-IM

如上所述，DENCLUE-IM是我们对DENCLUE的改进。这种改进包括基于Hill Climbing算法修改步骤。在DENCLUE算法中被认为是关键的这一步骤基于梯度计算。对每个点进行这些计算以找到其密度吸引子。在合理的时间内对每个点进行计算并不明显，尤其是在大型数据库上运行时。如算法1中所示，我们的方法允许找到密度吸引子的等效项，其将表示超立方体中包含的所有点，而不是针对数据集中的每个点进行的计算（参见等式3）。表示为x_Hcube的超立方体的代表将被认为是该超立方体中具有最高密度的点，如等式4所示。

forall;x isin; C_p f_D(x) le; f_D(x_Hcube), (4)

其中C_p 是构造的超矩形中给定填充的超立方体。

因此，每个超立方体构成由其x_Hcube表示的初始簇。当且仅当其代表之间存在路径时，才会合并这些群集x_Hcube 。

算法1.DENCLUE-IM算法

输入：数据集，sigma;和xi;

步骤1.在每边都是2sigma;的地图中获取数据集，仅考虑填充的多维数据集。

步骤2.计算每个填充的多维数据集的平均值。

步骤3.找到高度填充的多维数据集。

步骤4.通过它们之间的距离确定每个高度填充的立方体与其他立方体（高度或仅填充的立方体）之间的连接。如果d（平均值（c₁），平均值（c₂））lt;4sigma;，则连接两个立方体。

步骤5.在确定群集时，仅考虑连接到高度填充的多维数据集的高度填充的多维数据集和多维数据集。

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

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