基于衰减窗口与剪枝链表树的高维数据流聚类算法研究

作     者：王冬秀 

作者单位：华东师范大学 

学位级别：硕士

导师姓名：江红

授予年度：2010年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：数据流 高维 聚类 衰减窗口 剪枝链表树 

摘      要：近几年来,随着以互联网为代表的计算机信息技术的普及,数据呈飞速增长的趋势,人们积累的信息量达到了TB级,甚至PB级。在现实生活中,许多数据是以动态的“连续数据流的形式出现的,它不同于传统的数据被存在静态介质中,可以被多次访问。数据流的特点是：(1)数据规模大;(2)维数高;(3)到达速度快;(4)潜在无序性;(5)每个元素只能被访问一次。因此,许多传统的聚类算法已经无法获得有意义的聚类结果,针对高维数据流普遍存在的“维度灾难问题,本文将重点围绕如下几个问题展开： (1)如何设计有效的聚类算法,适应持续快速到来的高维数据流? (2)在聚类过程中,如何发现更多的聚类,提高聚类效果? (3)在聚类过程中,如何降低内存消耗? (4)在聚类过程中,如何提高算法的效率,减少算法的运行时间? 本文在对经典的数据流聚类算法进行学习和研究后,针对经典算法存在的不足,进行了改进和提高,提出了一种新的高维数据流聚类算法。主要工作包括以下三个方面： (1)为了有效地控制内存规模,在聚类过程中减少内存消耗,本文提出了一种概要数据结构—剪枝链表树,简称PL-Tree,用来保存数据流的摘要信息,在有任何聚类请求时,能够在线输出近似的聚类结果。本文采用核心技术数据淘汰和剪枝策略,有效地控制了内存规模,提高了算法的运行效率。 (2)为了设计一种高效的聚类算法,适应持续到来的高维数据流,本文基于PL-Tree概要数据结构,提出了一种基于衰减窗口与剪枝链表树的高维数据流聚类算法,简称PLStream算法。同时,为了减小历史数据对聚类结果的影响,利用衰减窗口及衰减因子对历史数据逐步进行衰减。最后用实验证明该算法的有效性。 (3)为了说明新算法的有效性,本文算法与经典算法CELL TREE算法进行了比较,实验表明,该算法在空间伸缩性和聚类效果方面都有较显著地提高。