一种基于概率密度的数据流聚类算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于概率密度的数据流聚类算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：数据流具有数据量无限且流速快等特点，使得传统的聚类算法不能直接应用于数据流聚类问题。针对该问题，提出了一种基于概率密度的数据流聚类算法。此方法不需要存储全部的历史数据，只需要存储新到达的数据并对其应用EM算法，利用高斯混合模型增量式地更新概率密度函数。实验表明，该算法对于解决数据流聚类问题非常有效。
关键词：数据流；聚类；高斯混合模型；概率密度
中图分类号：TP311.13文献标识码：A
文章编号：1001-9081(2007)04-0881-03
0引言
随着科学技术的飞速发展，许多技术领域都存在源源不断的规模庞大的数据流。所谓数据流就是大量连续到达的潜在无限的数据的有序序列，这些数据或其摘要信息只能按照顺序存取并被读取一次或有限次。典型的数据流有高速公路传感器网络的监测信息数据，电信公司大型交换机上的通话记录数据以及气象、环境的监测数据等。由于数据流的特殊性，在短时间内有大量的数据到达，使得传统的数据查询、分析、挖掘等算法不能直接应用于数据流，促使人们设计新的算法来适应数据流模型。
数据流聚类是数据流挖掘中一个重要研究内容。聚类[1]就是将数据对象集合划分为多个类或簇（cluster），在同一个簇中的对象之间有较高的相似度，而不同簇中的对象差别较大。传统的聚类算法可以分为如下几类[2]：划分方法（partitioningmethod）,层次方法（hierarchicalmethod），基于密度的方法（density―basedmethod），基于网格的方法（grid―basedmethod），和基于模型的方法（model―basedmethod）。然而这些方法都需要多遍扫描数据集合，不能直接应用到数据流聚类上。因为数据流的速度很快，对算法的响应要求很高，所以数据流算法经常采用用精度换时间的方法，尽量在对数据的一次访问中获得较优的解。因此，与传统的聚类算法相比,数据流聚类要满足以下三个要求：1）在满足聚类要求的情况下，尽可能少地扫描数据集，最好是一遍扫描[3];2）快速增长地处理新到达的数据，对数据流进行概化或有选择的舍弃;3）每一次记录的处理时间尽可能短，要能够跟上数据流的速度。
1数据流聚类的框架
Clustream算法[4]把数据流聚类分为两个部分：在线的micro―cluster过程和离线的macro―cluster过程。在线的micro―cluster过程对数据流进行初级聚类，阶段性地存储数据流详细的摘要信息，对数据采用增量式的处理和更新，这一过程不需要用户输入任何参数（如时间范围或簇的个数）。由于此阶段仅仅处理摘要信息，所以可以处理流速较大的数据流。离线的macro―cluster过程通过用户输入参数来对在线过程存储的摘要信息进行聚类。通常用户感兴趣的是最近的数据而不是全部历史数据，因此微聚类按金字塔时间框架所产生的时间序列及时以快照的形式存储。这一框架兼顾了离线的macro―cluster在不同时间段恢复摘要信息的能力，以便能够得到用户感兴趣的不同时间范围内数据流的聚类结果。
本文采用了基于概率密度的数据流聚类算法。该算法仅需要存储新到达的数据，没必要存储全部的历史数据，
依靠新到达的数据和历史数据的概率密度，增量式地更新概率密度函数[5]。此思想源于概率密度更新理论和高斯混合模型[6]（Gaussianmixturemodels）。本算法沿用了Clustream算法解决数据流聚类问题的思想，把聚类过程分为两个阶段：在线的进程和离线的进程。记录当前数据流摘要信息的进程为在线的进程，记为pdmicro―cluster（probability―densitymicro―cluster）；而离线的查询响应进程称为pdmacro―cluster（probability―densitymacro―cluster）。
2pdmicro―cluster过程
本文算法是一种确定性和随机性的增量式聚类算法，它分为一个合并阶段和一个更新阶段。在合并阶段算法减少了簇的数目；在更新阶段，算法接受新的更新，并试图在不增大簇半径的情况下保持最多的k个簇。
2.1算法的理论基础
下面首先给出本文中使用的一些符号
2.2根据新到达的数据更新高斯混合模型
2.2.1如何确定协方差矩阵相等
2.2.2如何确定平均数向量相等
2.2.3合并或创建分量
3pdmacro―cluster过程
在线的pdmicro―cluster过程快速有效地保存了数据流实时的摘要统计信息，而离线的pdmacro―cluster过程只需要在线过程存储的摘要信息。因而在此过程中，用户可以根据自己的需要输入参数：时间范围h和聚类的数目k。使用K―means[8]方法作为算法的离线聚类过程。K―means算法选择k个点作为随机种子，并且为了更新簇的划分，反复地为每一个种子分配数据集中的点。在每一次反复过程中，原来的种子被每一个划分的中心所代替。
在本文算法中，K―means方法需要做如下修改:
1)在初始化阶段，种子不再是随机的选择，而是根据概率按照已给微聚的点的数目成比例的抽样，相应的种子是微聚类的中心。
2)在划分阶段，种子到微聚类的距离认为是种子到相应的微聚类中心的距离。
3)在种子调整阶段，一个给定划分的新的种子被认定为在此划分中微聚类加权的中心。
另外，由于pdmacro―cluster过程的相对独立，可采取任意一种支持加权聚类的算法来进行。
4聚类质量比较
使用KDD－CUP98CharitableDonation数据[4]来进行算法的测试。此数据曾经被用来测试一次扫描的聚类算法，包含了95412条给予直接邮件求助的人的捐助记录，并且把有类似捐助行为的捐助者进行聚类。我们只用每条记录中的56个信息进行测试，根据数据输入的次序作为流的次序，并且假定它们有速度。
所有的实验都在Pentium4，256M内存，WindowsXP环境下进行，聚类质量用距离平方和SSQ[9]来衡量。SSQ是一种比较k―划分聚类质量的方法，它通过计算所有点到各自的聚类中心的距离来衡量算法所给出的k―划分的质量。SSQ值越小，说明算法聚类质量越好。使用k―means方法作为本文算法和Clustream算法的离线聚类过程来比较两个程序的初始聚类质量，然后比较两个程序算出的SSQ值。
所有的实验结果表明，本文算法比Clustream更稳定并有较好的聚类质量。图1给出了部分实验结果，其中流速＝2000是指每个时间单元有2000个数据流入。每一个算法运行10次来计算它们平均的SSQ值。根据SSQ值的大小来看，本文算法优于Clustream。在不同时间的平均SSQ值，都比Clustream的要小。
5结语
针对数据流数据量大且流速快的特点，本文讨论了基于概率密度的数据流聚类算法。此算法的理论基础源于高斯混合模型，合并概率相等的高斯分量，利用数据流的统计结构，仅需要存储新到达的数据，离线的过程使用k―means方法，实验表明此算法对于解决数据流聚类问题非常有效。
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。