英语原文共 26 页，剩余内容已隐藏，支付完成后下载完整资料
基于集群智能用于聚类演进数据流的单遍算法
摘要：现有的基于密度的数据流聚类算法使用的是两阶段方法，其中在线阶段处理原始数据收集汇总统计信息，脱机阶段通过使用汇总的统计信息生成群集的聚类数据。在本文中，我们提出一种采用分散式自下而上自我组织策略的多代理系统的数据流聚类的方法将相似的数据点分组。数据点与代理相关联并进行部署到二维空间，通过应用被称为植绒模型的生物启发模型进行数据模拟工作。代理以固定的时间移动到对应的空间，并且当他们遇到其他代理进入预定义的可视范围时，如果他们是相似的，他们可以决定组成一个群。群可以加入形成类似的群组。该策略允许合并基于密度的方法的两个阶段从而避免计算需要离线群集计算，因为集群代表一个聚类。实验结果表明，生物启发式方法可以在真实和合成数据集上获得非常好的结果。
关键词：数据流·基于密度的聚类·生物启发的植绒模型
- 引言
近年来，许多组织正在收集大量的数据，这些数据通常由一系列事件不断产生并且来自不同地点。信用卡事务流，电话记录，传感器网络数据，网络事务日志只是数据流的一些例子。设计和开发能够快速，高效，精确的从这些庞大的不能适应计算机的主存储器的数据集中提取知识的技术构成重大挑战。第一在数据到达时，数据只能被检查一次。其次，使用整个长时间的数据流可能会误导分析结果，究其原因是我们把过时的数据与最近的数据赋予同样的考虑权重。由于数据流是连续的信息序列，潜在的群集可能会随着时间而改变，从而在它们所处的时间范围内给出不同的计算结果。
传统的聚类方法不能够高效灵活的处理随着时间的推移不断演变的数据，因此，在过去的几年里，许多关于数据流聚类的提案被提出（Aggarwal等人2003,2006; Babock等人2003;Barbaraacute;2002; Cao等人.2006; Chen和Li2007; Guha等人.2000;奥卡拉汉等人2002; Guha等人2003; Nasraoui等人2003; Nasraoui和Coronel 2006;周等人2007）。 Aggarwal等人（2003）是第一个通过不断发展的流数据的特性解决在计算过程中无法修改数据流这个问题的人。他们建议流聚类算法应该分为两部分，一个线上微聚类组件在数据流中收集适当的统计数据，另一个线下的宏聚类组件使用存储的信息来提供聚类结果。然而，他们的算法-CluStream是基于K-means方法，只能找到球型聚类并且需要事先知道聚类的数量。由于基于密度的聚类算法（Ester等，1996）克服了这些局限性，基于密度的框架最近已经出现扩展到上述的两阶段方案（Cao等人.2006; Chen和Li 2007; Li和Chen2009; Li等人2009）。所有这些方法都使用衰减数据模型来处理不断变化的集群分布并发现流数据中的变化。
正如Li等人（2009年）所指出的那样，两阶段计划的离线组成部分是一个需要计算的步骤，因为它实际上必须应用一种聚类算法在概要上产生结果。另一个问题是要发现集群中的变化，离线部分必须频繁执行。Li等人（2009年）提出了在恒定时间内检测聚类演化的方案。
在这篇文章中，我们提出了一种综合生物启发式和基于密度的聚类方法来处理数据流，合并上述方案的在线和离线阶段，根据需求在没有加大运算量的情况下随时提供当前可用的聚类结果。该算法名为FlockStream，类似于前面提到的基于密度的方法，使用阻尼窗口模型来处理聚类演变，曹等人（2006年）同时将潜在和异常微聚类的概念引入生物启发框架。事实上，FlockStream采用了一个使用分散式自下而上的自组织策略的多代理系统来分类相似的数据点。每个数据点都与一个代理相关联。代理被部署到一个称为虚拟空间的二维空间中，并同时工作应用基于称为植绒模型的生物启发式模型的启发式策略（Eberhart等人2001）。代理在固定的时间内进入该空间，并在他们的时间遇到其他代理到预定义的可见性半径，如果它们是相似的他们可以决定形成一个集群则是群集（即微集群）。
因此，代理在二维空间中的移动不是随机的，而是被引导的通过相似性函数将代理聚集到他们更近的邻居。由于通过应用植绒规则可以创建类似的微簇，聚集起来形成一大批密集的微型集群。
FlockStream的主要贡献可以概括如下。
- FlockStream替换了对某个点的最近邻居的详尽搜索，需要将其分配给适当的微集群，由代理搜索并行工作。该方法完全分散为每个代理彼此独立行事，只以异步方式直接与其邻居沟通。局部性和异步性意味着该算法可以扩展到非常大的数据集。
- 由于每个代理只与其能见度范围内的其他代理进行交互，它不会与其他所有代理进行比较。因此，实现了一定计算量的减少。这个数字取决于它在虚拟空间中移动时遇到的代理数量。这意味着算法可以非常高效并且实现了相对于一定量的输入数据实现线性加速。
- 集群的代理可以聚集成一些相似群体的集群。因此上面提到的两阶段数据流聚类方法的方案被替换为一个单独的在线阶段，其中聚类结果始终可用。这意味着只要提供迄今计算的所有群集，就可随时满足用户需求的群集生成。
- 群集的演变本质可以通过显示代理在虚拟空间移动来跟踪。这使用户能够直观地检测到集群分布的变化，并为他提供了何时询问集群结果的见解。
- FlockStream可以通过减少代理移动到虚拟空间的时间让用户获得近似但更快的结果。
- 该方法对噪声有较强的鲁棒性。事实上，在实验结果中，我们发现当噪声存在时，FlockStream获得高质量的集群。
本文组织如下。下一节将回顾关于数据流聚类的主要建议。第3节描述了Cao等人(2006)的算法，为我们的方法带来启发。第4节介绍了植绒模型。第5节描述了我们的方法。第6节给出了合成实际生活数据集的方法的结果，并与Cao等人(2006)所获得的结果进行了比较。最后，第7节讨论了该方法的优点，并总结了本文的结论。
- 相关工作
在过去几年中，特别关注研究数据流聚类的有效方法（Aggarwal 2007）。第一种方法采用单通范例（Charikar等人.2003; Guha等人.2000; O#39;Callaghan等人.2002; Guha等人，2003）来处理那些只能被检测一次的数据流的要求。根据这种模式，当数据被扫描时，将过去数据的摘要进行存储以留下足够的内存来处理新的传入数据。这些算法应用了分而治之的技术，通过扩展k-Median算法将数据流分割成不相交的片段和簇。Guha等人（2003年）提供的近似误差的理论研究也被使用于每个片段使用扩展模式。这些方法的主要缺点是必须给出簇的数量作为输入参数，并且它们不能捕获数据流中的变化，因为过时的和最近的数据具有相同的权重。
为了考虑数据流的演变，Aggarwal等人（2003,2006）提出了一种基于两阶段模式的新模型：在线微聚类组件，它收集适当的数据流汇总统计信息，以及一个离线宏聚类组件，利用存储的信息提供聚类结果。摘要信息由两个结构定义：微聚类集群和金字塔时间框架。微聚类群集维护关于数据局部性的统计信息。此外，微聚类群集在时间上按照金字塔样式存储在快照中。这种模式提供了满足存储要求和从不同时间范围重用汇总统计数据的能力之间的折衷。所提出的算法CluStream使用微聚类群集结构来对流数据进行聚类。通过利用k均值和最近的相邻矩阵的思想在线建立微聚类群集。在任何时刻，假定存在q个微聚类群集。一般来说，q是一个非常大的簇包含的聚类数目的值。在开始时，使用k-means算法构建q个微簇。每当一个新的点X到达，从X到微簇中心的距离被计算出来，如果X位于其最大边界内，则被分配到最近的微簇。否则，将创建包含数据点X的新微集群。在这种情况下，由于微集群的数量必须保持不变，所以必须删除微集群，或者必须合并两个微集群。CluStream算法有两个主要的局限性：它不能发现任意形状的聚类，而聚类的k必须是固定的。
两阶段模式CluStream的鼓舞着许多数据流聚类算法来改善它(Wang等人 2004年),并允许多个数据流的聚类(Dai等人2006),并行(Beringher and Hullermeier2006)和分布式数据流(Sanghamitra等人 2006)。
最近，用来处理数据流的基于密度的聚类算法的优化已经被提出（Ester等人1996）。 基于密度的方法克服了CluStream的缺点，因为它们能够找到任何形状的聚类，并且不需要关于聚类数量的确定值。这方面的主要建议是Cao等人（2006）的DenStream算法，Li和Chen（2009）的D-Stream算法以及Li等人（2009年）的MR-Stream算法中提出的。
DenStream将在下一节详细介绍，它扩展的核心点的概念在DBSCAN（Ester等人，1996）中引入并采用，通过阻尼窗口模型来存储数据点的近似表示。
D-Stream采用基于将数据空间划分为离散化的网格的方法，在这些网格中映射新的数据点。衰减因子与每个数据点的密度相关联，以减少对历史数据的重要度，并对最近数据赋予更多权重。研究了时间范围，衰减因子和数据密度之间的关系，以保证高质量簇的生成。高维数据可能会迅速增加网格的数量。作者发现，实际上，许多网格是稀疏的或空的，因此他们开发了一种有效的技术来管理它们。实验报告具有40的最大维度。然而，随着维数增加，网格单元的数量呈指数增长。因此，即使空网格单元不需要明确存储，也可能有许多单元只包含一个点。这意味着D-Stream无法处理非常高维的数据，类似于基于网格的聚类方法，在高维数据上表现的性能较差（Tan 等人2006）。相反，DenStream算法，不会遇到这个问题。与CluStream的比较显示D-Stream相对于CluStream具有更好的性能。目前在DenStream和D-Stream之间没有比较。
与D-Stream类似，MR-Stream将搜索空间划分为单元格。每一次一个维度被分成两部分，一个单元格可以进一步划分为2d个子单元格，其中d是数据集维度。然而，用户定义的参数限制了可以完成的分区的最大值，并且使用四叉树结构来存储空间分区。树状结构允许在不同分辨率级别进行数据聚类。当处于在线阶段，在每个时间戳处，MR-Stream将新的传入数据分配给适当的单元并更新概要信息。离线组件在固定高度h处获得树的一部分，并在由h确定的分辨率级别执行聚类。为了发现数据的变化，作者提供了一个时间间隔值，记为tp ，用于检查一个单元格从密集到稀疏的变化。他们证明，通过对存储器开销进行抽样，从而可以获取演化的集群信息，从而可以在每个tp个区间内对树中的节点数进行采样。这给出了一个何时执行离线阶段的参考。 MR-Stream与D-Stream的比较显示了前一种方法性能更好。
已经提出了许多基于生物启发范例的聚类方法（Azzag等人2003; Folino等人2009; Hamdi等人2008; Handl和Meyer2007; Liu等人2004）。 它们都没有设计用于处理数据流。只有一个使用植绒模型对文档流进行聚类的方案CuiandPotok（2006）。与我们的方法类似，每个代理包含它所代表的数据点的特征向量。在这种情况下，数据点就是文档。通过周期性地改变每个代理的特征向量来模拟文档流。因此，它们既不总结也不考虑过去的信息，因为在之前固定的时间单位之后，旧的文档被丢弃，并且从头开始重新阐述新文档以生成新的集群。
下一节将详细介绍DenStream。事实上，我们的方法采用了DenStream引入的适用于植绒模型的概念。
- DenStream算法
DenStream（Cao等人2006）是一个基于密度的集群算法，提供数据使用汇总统计来捕获有关数据流性质的概要信息。这些统计数据被利用来生成具有任意形状的群集。该算法假定阻尼窗口模型对数据流进行聚类。在这个模型中，每个数据点的权重随着时间t通过衰落函数f（t）= 2-lambda;t 指数衰减，其中lambda;gt; 0。数据流的权重是常数
，其中v 是流的速度，即点的数量以一个时间单位到达。当lambda;呈现更高的值时，历史数据会降低其重要性。
作者扩展了DBSCAN（Ester 等人1996）中引入的核心点的概念并采用微集群的概念来存储数据点的近似表示。一个核心点是一个对象，其ε邻域中的点的总重量至少为整数mu;。聚类是一组具有聚类标签的核心对象。引入了微簇的三种定义：核心微簇，潜在核心微簇和异常微簇。
一组核心微簇（缩写为c-微簇）在时间t为一组具有时间戳T i1 ，...，T in的接近点pi1，...，pin定义为CMC（w，c，r），其中w是权重，c是中心，r是c-微群集的半径。权重
必须是wge;mu;
全文共16339字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15260]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
