多维数据流聚类算法的分析与实现

摘要

随着计算机科学的逐步成熟和信息社会需求的提高，人们需要在日益庞大的信息中发现对决策有用的知识，数据挖掘作为一门新兴的交叉学科应运而生；随着信息技术的高速发展和互联网逐渐深入和广泛的应用，人们所面对的信息越来越多地包含以流的形式产生的数据，数据挖掘不仅仅需要处理存放在数据库中的那些“过时”的静态数据，而且面对着一种新的数据形式——在线实时数据流。数据流是由一系列连续且有序的数据组成的序列，具有数据量无限、到达速度快、不可再现等特点。因此，如何有效地处理数据流，成为数据挖掘面临的新挑战，也得到这一研究领域的广泛关注。 由于存储空间的有限性与数据流的无限性，使得存储数据流中的全部数据以提供精确的挖掘结果是不实际的。因此，在数据流处理模型中，数据流挖掘算法只存储数据流的概要信息，并随着流中数据不断到来，不断更新流概要，同时根据用户的查询要求，利用所维护的数据流概要信息，为用户提供近似的查询结果。 数据挖掘中聚类分析是一个重要的课题，并在数据挖掘的发展趋势中发挥着重要的作用。数据挖掘技术是面向应用的，它最终需要应用到现实世界中的数据上，而真实数据往往具备许多属性，这就造成数据挖掘所处理的往往是多维数的数据。针对数据的多维性，不同的聚类算法采取了不同的处理技术。 针对多维数据流的聚类算法必须满足更高的要求，在处理多维数数据的同时，还要保证算法的时间、空间效率以适应数据流。对此，本文主要进行具有多维数的数据流环境下的聚类分析方法的研究，研究内容可概括为以下三个方面： (1)针对多维数据流的特点，探讨了数据流挖掘中的窗口机制，分析了典型的多维数据流聚类算法CellTree算法的优缺点，提出了一种新的内存模型结构LISTTREE。 (2)基于数据结构LISTTREE提出一种新的多维数据流聚类算法LTC，并利用多线程编程方法极大程度地模拟在线处理数据流，以检验新算法。 (3)对CellTree算法和LTC算法进行了对比实验，通过对实验结果详细全面的比较，分析了这两个算法的效率和聚类效果。 实验表明，LTC算法不仅对数据流具有良好的适应性，而且比CellTree算法具有更高的时间、空间效率，并且达到了更好的聚类效果。因此，LTC算法在数据流挖掘领域具有重要的研究价值和意义。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 数据流挖掘技术概述

1.2 多维数据流聚类技术

1.2.1数据流聚类中的多维处理

1.2.2数据流挖掘中的窗口机制

1.3 本文的研究内容

1.3.1提出问题

1.3.2解决方法

1.4本文的组织结构

第2章多维数据流聚类模型LIST TREE

2.1 Cell Tree算法介绍

2.1.1算法描述

2.1.2算法存在的问题

2.2 聚类模型LIST TREE

2.2.1模型结构

2.2.2模型特点

2.3 本章小结

第3章 多维数据流聚类算法LTC

3.1 算法总体框架

3.2 算法的数据淘汰与剪枝策略

3.3 算法详细描述

3.3.1模型初始化阶段

3.3.2模型维护阶段

3.3.3聚类输出阶段

3.4本章小结

第4章 实验分析及结果讨论

4.1 实验环境与实验数据

4.2 LTC算法在线数据流处理模拟实验

4.3 LTC算法与CelI Tree算法比较实验

4.4 本章小结

结论

论文的主要工作

展望

参考文献

攻读硕士学位期间所发表的学术论文

致谢