论文部分内容阅读
数据挖掘,又称数据库中的知识发现,是指从大型数据库或数据仓库中提取隐含的、事先未知的、潜在有用的信息或模式。它融合了数据库、人工智能、机器学习和统计学等多个领域的理论和技术,是数据库研究中的一个很有应用价值的新领域。而聚类分析是数据挖掘中很重要的分析手段。聚类是依据事物的某些属性将其聚集成类。使类间相似性尽量小,类内相似性尽量大,即“物以类聚,人以群分”。聚类本身是一个发现过程,其结果可以解释数据分布的本质特征,同时也为应用其他的数据挖掘及分析技术奠定了基础。在当今的经济生活中,许多庞大的机构每天都会产生数以百万记的记录。在科学研究中,科学数据的采集通常每天都会产生十亿字节的数据。对于达到这个数量级的数据,应用数据挖掘技术,特别是聚类分析手段来提取人们感兴趣的知识和模式来说是非常有意义的。但现有的挖掘复杂数据模型的算法都不能在有效的时间内完成挖掘任务,因为在传统的数据挖掘过程中,被考虑的数据假设已经被载入一个稳定且很少更新的数据库中,而面对大量、无限和快速的数据流时,数据挖掘系统应该是以数据到来的速度来处理和挖掘数据的。克服这样的状态需要我们转换我们的观念,将挖掘数据库中的静态数据转换为挖掘动态的数据流。在众多的针对数据流的单层聚类算法中,当首推由Stanford大学stream小组的Sudipto Guha等人开发的STREAM算法。STREAM算法经过四年左右的改进,已经成为单层数据流聚类算法的经典之作。Guha等人不仅在实践中体现了STREAM算法的可行性,而且在理论上证明了单层数据流聚类框架的时间空间复杂性。如果单独从满足数据流的自身特点出发,单层数据流聚类算法可以说是显示出很强的优势。但是聚类是一个应用性很强的问题,我们应该将我们的视角转向实用角度。在现实的数据流应用中,数据量不仅浩瀚如海,而且数据通常变化很大。我们在满足聚类质量的同时,还要满足用户从不同应用角度获取聚类结果的要求。而单层数据流聚类算法恰恰忽略了这些方面。在思考单层数据流聚类算法局限性的原因后,我们自然而然的需要突破这个框架,设计一个更加行之有效的算法框架。于是,双层数据流聚类框架应运而生。本文的主要工作是设计和实现了双层数据流聚类框架。它包括两部分——快速计算层和精确分析层。为了更加有效地存储保留数据流中数据点的摘要信息,我们在框架中<WP=48>引入了两个概念:微簇和金字塔时间框架。数据点的摘要信息以微簇的形式保留,并按照金字塔时间框架进行存储,它们为数据流进入框架第一层奠定了良好的基础。快速计算层是在线收集和预处理数据流的过程,是整个双层数据流聚类框架的基础。这个过程不依靠任何用户的输入,例如聚类数目或者是聚类过程所需的粒度。它的目标就是保持在足够高的粒度级(时间的和空间的)上的摘要信息,使它们能够在第二层(精确分析层)中被有效的使用。算法在任意时刻都保持总数为q的微簇。当一个微簇i被第一次创建的时候,我们就创建一个唯一的标识id附在这个簇上。如果两个微簇被合并,那么就合并这两个簇的标识创建一个标识列表来标识这个组合的簇。利用子算法InitClus创建初始的q个微簇后,微簇的在线更新过程将被启动。每当一个新的数据点到达,微簇就要根据变化做出相应的更新。每个数据点或者被一个微簇吸收,或者需要自己创建一个簇。我们首先考虑的就是数据点能不能被当前存在的微簇吸收。先找到数据点和微簇重心的距离,寻找离数据点最近的簇。如果数据点对应于一个孤立点或数据点对应于一个新簇的开端,数据点不属于簇。如何判断是否应该创建一个全新的簇呢?为了准确判断,我们引入最大边界和最大边界因子这两个概念。我们将使用的簇特征向量计算其最大边界来判断当前数据点是否属于其最邻近的微簇。如果数据点落在微簇的最大边界之中,根据簇特征向量加法原则,这个数据点将加入微簇当中;如果此数据点不在的最大边界中,那么就要创建一个新的微簇,包含这个数据点,并被赋予一个新的标识。为了维持足够的内存空间,我们或者删除一个旧的微簇,或是连接合并两个旧的微簇。在数据流的每个数据点的到来执行更新过程中,我们要进行金字塔时间框架存储操作。对于任意整数i,在每个被整除的时钟时刻,我们要将当前的微簇集合连同他们的标识和标识列表一起存贮起来,并根据它们被存储的时间进行索引。随着数据流量的不断增大,框架第一层算法所得到的微簇的内部结构特征也在不断变化,我们有必要在数据流聚类的中后期对框架第一层算法所输出的中间结果应用基于密度的评估方法进行校正。作为双层数据流聚类框架中辅助可选的方法,基于密度的评估方法可以更好的规约快速计算层所得到的中间结果,为精确分析层提供有力的支持。精确分析层可以看作是双层数据流聚类框架的离线分析部分。在精确分析层上,我们有更多的自主性,可以在各种不同的范围中进行更加精确的聚类分析。我们采用改进的k平均技术来实现精确分析层算法。设当前时钟时间为tc,用户定义的时间范围为h,根据微簇的减法属性计算微簇的集合,(是用户特定的时间范围h的预定?