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

MuDi-Stream：用于持续数据流的多密度聚类算法

摘要: 基于密度的方法已经成为用于聚类数据流的有价值的方法。最近，已经发明了用于对大量的数据流进行聚类的基于密度的算法。然而，现有的基于密度的数据流聚类算法不是一点问题也没有，当超度一定的数据密度的范围时，聚类的质量急剧下降。在本文中，开发了一种称为MuDi-Stream的新方法。它是一个在线离线算法，有四个主要组件。在在线阶段，它保持关于演变的多密度数据流的简要信息以核心微型集群的形式。离线阶段使用了适当的基于密度的聚类算法生成最终聚类。基于网格的方法用作异常值缓冲器以处理噪声和多密度数据，并且还用于减少聚类的合并时间。使用不同的质量度量在各种合成和真实世界数据集上评估该算法，并且进一步比较可缩放性结果。实验结果表明，本文提出的方法提高了多密度环境下的聚类质量。

1. 引言

当前产生大量数据的能力和存储这些数据的不可能性促进了数据流挖掘方法的发展。数据流聚类最近一直是一个积极的研究课题。由于我们能够产生比可用存储空间更多的数据，需要不止一次查看数据的传统挖掘方法是不可用的。尽管提出了许多技术，但是很少有人解决了数据流聚类的问题（Chen et al。，2012）。

聚类的重要类型之一是基于密度的算法。基于密度的聚类算法可以找到非球形形状簇，并且可用于识别噪声（Han等人，2011）。在过去几年中，已经提出了一些针对数据流扩展基于密度的聚类的建议（Amini等，2014）。

数据流聚类算法的一些突出的方法包括：DenStream（Cao等人，2006），FlockStream（Forestiero等人，2013），D流（Chen和Tu，2007; Tu和Chen，2009） MR-Stream（Wan等人，2009）。这些算法应用两个突出的技术，包括密度微聚类（Amini和Wah，2011）和基于密度网格（Amini等人，2011）的方法来聚类演进的数据流。他们有在线和离线阶段。在在线阶段，他们保持关于数据流的摘要信息，而在离线阶段，使用基于密度的聚类算法在摘要数据上形成最终聚类。这些算法能够在发现数据流时发现任意形状簇，同时检测噪声。

然而，聚类算法中的挑战之一是检测数据中的多密度簇。多密度簇是指以各种密度形成的簇。多密度的集群在实际数据集中非常普遍。例如，地理数据集显然具有不同密度的位置属性，并且在聚类中应考虑这种多样性。

现有方法（Cao等人，2006; Forestiero等人，2013; Chen和Tu，2007）在聚类多密度数据中的共同问题是使用全局参数，并且导致聚类质量的显着降低。图1a描述了DenStream聚类算法对多密度数据集的结果。可以观察到，五个簇被不准确地检测为三个。如果为聚类半径值选择大的值，则三个小簇被分组为一个簇，而两个大簇被正确地检测到（图1b）。如果基于密度的算法的聚类半径值被认为是小的，则两个大的簇被检测为噪声（图1c）。

与聚类多密度数据集相关的问题已经被积极研究。已经提出了用于多密度数据聚类的一些算法;然而，它们不适用于数据流由于以下缺点：（1）它们中的一些需要两遍数据，例如GMDBSCAN（Xiaoyun等人，2008）和ISDBSCAN（Carmelo等人，2013）。在这些算法中，提取关于数据分布的有用信息，然后基于提取的信息对数据进行聚类。这种技术对于数据流是不切实际的，因为它连续到达并且聚类算法必须在单次扫描中执行，（2）一些现有的多密度聚类算法需要整个数据（Esfandani等人，2012），（3）算法，如Karypis et al。（1999）和Esfandani和Abolhassani（2010）具有较高的执行时间，使得它们不适用于需要快速处理时间的数据流。

受此观察的影响，本文提出了一种多密度数据流聚类算法。 MuDi-Stream提供了几个贡献：（i）基于网格和微聚类聚类的混合方法被应用于捕获数据点的概要信息。基于网格的方法用于绘制离群值并形成具有不同半径的新的微群集。这有利于提高多密度数据的质量以及合并时间的显着减少。事实上，MuDi-Stream代替了使用网格映射任务将点分配给适当的离群点微团的详尽搜索。 （ii）引入一些新概念，包括微核距离，核心微群集和核心相邻以便处理多密度数据流。 （iii）MuDi-Stream由四个主要组分组成：MM组分，FCM组分，PGCM组分和FFC组分。前三个组件用于在线阶段，而最后一个组件与离线阶段相关。它们执行四个重要任务，包括合并或映射，形成核心微型集群，修剪网格和核心微型集群，以及形成最终集群。 （iv）提出了一种称为M-DBSCAN的基于密度的聚类算法，用于从摘要数据形成具有各种密度的最终聚类的离线阶段。 （v）使用各种评估指标对综合和现实世界数据集进行了一系列全面的实验。结果证明，与DenStream相比，所提出的方法明显改善了多密度环境中的聚类结果（Cao et al。，2006）。我们的算法具有比现有方法更好的聚类质量，效率和可扩展性。

本文的其余部分安排如下。相关工作的概述在第2节介绍第3节中的初步之前提出。所提出的方法在第4节中解释。第5节阐述评估设置，第6节提供实验结果。最后，第7节总结了本文。

1. 相关工作

在本节中，我们从两个方面分析相关工作。 一个是与基于密度的数据流聚类算法有关，另一种是多密度数据集的聚类算法。

2.1:基于密度的数据流聚类算法

已经开发了基于密度的聚类算法来发现具有任意形状的簇。 它们基于形状中的密集区域找到簇。 如果两个点足够接近并且它们周围的区域是密集的，则这两个数据点连接并且有助于构建簇。 DBSCAN（Ester等人，1996），OPTICS Ankerst等人，1999和DENCLUE（Hinneburg和Keim，1998）是这种方法的实例。 最近，基于密度的方法被用于聚类演化数据流（Cao et al。，2006; Forestiero et al。，2013; Chen and Tu，2007; Wan et al。，2009; Amini et al。，2014）。

DenStream（Cao等人，2006）扩展了微群（Aggarwal等人，2003）概念，并引入异常群和潜在的微群以区分真实数据和异常值。它是一种具有在线和离线相位的密度微聚类方法。对于在线阶段的初始化，Den-Stream在第一个初始点使用DBSCAN算法，并形成初始潜在微群。当新的数据点到达时，它被添加到最近的现有潜在微群或异常群。如果数据点无法连接到其中任何一个，则会创建一个新的异常值微群集，并将其放置在异常值缓冲区中。离线阶段采用DBSCAN来确定记录的潜在微簇上的最终簇。 DenStream具有修剪方法，其中它检查离群值缓冲器中的离群值 - 微群集的权重。它不能聚集具有不同密度的数据流，因为在在线它形成微群而不考虑密度分布。离线阶段还使用DBSCAN（Ester，2013）形成最终集群，其不能覆盖多密度数据。此外，合并过程是耗时的。

FlockStream（Forestiero等人，2013）是基于密度的聚类算法，基于生物启发模型。它是基于植绒模型（Kennedy等，2001），其中代理是微群集，它们独立工作，但一起形成群集。它考虑映射到虚拟空间的每个数据点的代理。如果代理访问他们加入的另一个代理以在它们彼此相似的情况下形成群集，则代理在它们的预定义可见性范围内移动固定时间。它合并在线和离线阶段，因为代理随时形成集群。事实上，它不需要执行离线聚类以获得聚类结果。由于FlockStream只将每个新点与其代理可见性距离中的其他代理进行比较，因此它减少了每个点的邻域中的比较数。可见度距离具有由用户定义的阈值。类似地，因为存在单个距离，算法不能以高质量对多密度数据进行聚类。代理具有一些规则以便在虚拟空间中移动，例如内聚，分离，和比对（Forestiero等，2013）。 这些规则随时间对每个代理执行。 FlockStream有三种代理：新数据点的基本代表性代理，以及分别基于潜在和异常微群的p代表和o代表代理。 实际上，当相似的基本试剂彼此合并时，它们基于它们的重量形成p代表性或o代表性试剂。 即使Flock-Stream与DenStream相比减少了比较次数，但仍然具有高计算时间。

chen等为实时数据流提出了一种基于密度网格的聚类框架，称为D-Stream（Chen and Tu，2007）。我们称之为D-Stream I. D-Stream我有在线和离线阶段。在线阶段读取新的数据点，将其映射到网格中，并更新网格的特征向量。离线阶段调整每个时间间隔间隙中的群集。时间间隔是基于不同类型网格的最小转换时间定义的。 D流I首先更新网格的密度，然后基于基于密度的聚类的标准方法执行聚类。这个框架背后的一个重要动机是通过将它们视为偶发网格来处理异常值。零星网格是一种稀疏网格，其具有非常少的数据并且没有任何机会被转换为密集网格。 D流I基于密度阈值函数来定义密度阈值的下限。如果稀疏网格的密度小于密度阈值的下限，则认为它是散发网格。它还具有在每个时间间隔间隙中发生的修剪阶段。在此阶段，调整集群，并从网格列表中删除零星网格。 D-Stream我使用一个哈希表来保持网格列表。

作者在Tu和Chen（2009）中扩展了D-Stream I。 我们称之为D-Stream II。 该算法基于许多基于密度的聚类算法不考虑网格中数据的位置信息的观察。 D-Stream II的聚类过程类似于D-Stream I; 然而，在D流II中，两个密集网格在它们是强相关的情况下合并。 如果两个网格的网格景点高于预定义的阈值，则称其为强相关的。 它将网格列表保存在树中，而不是使表格的处理更快，并减少了内存空间。

李万等开发了一种基于密度的多种分辨率数据流聚类算法，称为MR流（Wan et al。，2009）。该算法通过在恒定时间运行离线分量来提高基于密度的数据流聚类算法的性能。 MR流确定用户生成群集的正确时间。它分割单元格中的数据空间和保持空间分割的树状数据结构。树数据结构使数据以不同的分辨率聚类。每个节点都有关于其父节点和子节点的摘要信息。 MR-Stream具有在线和离线阶段。在在线阶段，当新的数据点到达时，它被映射到其相关的网格单元。在树结构中，如果没有任何子节点，则为新数据点创建新的子节点，并且其更新父权的权重直到树的根。在每个时间间隔间隙中，树被修剪。离线阶段在用户定义的高度生成聚类。它确定在特定距离处的所有可达的密集小区，并将它们标记为一个簇。通过分别用尺寸和密度阈值检查它们的尺寸和密度来去除噪声群集。 MR-Stream引入了内存采样方法，以便定义运行离线组件的正确时间，从而提高了集群的性能。

HDC-Stream（Amini等人，2014）是用于物联网（IoT）应用的基于密度的数据流聚类算法。 该算法具有低处理时间，使其适合物联网设备的实时应用。 它使用混合方法并在三个不同的步骤中执行聚类。它有在线和在线阶段。 HDC-Stream的在线阶段连续读取新的数据记录，并将其添加到现有的微群集或将其映射到网格。 HDC-Stream定期删除修剪步骤中的异常值。 离线阶段由用户根据需要生成最终集群。 作者证明，它具有高质量，低时间复杂度的聚类数据流; 然而，它没有集群多密度数据的能力。

关于基于密度的聚类算法对数据流的完整调查可在Amini等人 （2014）。 在本文中，选择了一些显着的算法。 然而，所有这些算法的共同的问题是它们不能聚集具有不同密度的数据。 原因是他们考虑了用于基于密度的聚类的全局参数集合，这导致多密度环境中的低质量。

2.2 多密度数据集的聚类算法

GMDBSCAN（Xiaoyun等人，2008）是一种多密度聚类算法，它使用网格技术来定义多密度聚类。 该算法使用网格密度确定局部MinPts参数，并且通过相关的局部MinPts应用DBSCAN来对网格进行聚类。 基于它们的密度相似性来集群。 它是一个两遍聚类; 因此，不适用于数据流。

MSDBSCAN（Esfandani和Abolhassani，2010）是基于密度的聚类算法，其基于它们的邻居的位置定位DBSCAN中的核心点的概念。 它引入了称为局部核心距离（lcd）的核心点的新定义，其表示至少存在MinPts对象的距离。 MSDBSCAN计算所有数据点的lcd，然后如果数据点的lcd向量的值相似，则数据点是核心点。 该算法通过合并核心点构建大的簇。 MSDBSCAN的时间复杂度很高，这使得它不适用于数据流。

多DBSCAN（Huang等人，2009）通过确定ε的不同值来覆盖多密度数据集的问题。 它使用“必须链接约束”和“kth”最近距离来计算不同密度的ε值。 多DBSCAN使用离群值检测算法为每个密度分布选择最佳ε。 之后，使用计算的ε对数据集执行DBSCAN。

全文共10672字，剩余内容已隐藏，支付完成后下载完整资料

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