基于可拓关联函数的数据流聚类算法研究

摘要

随着传感器技术的日益普及和信息社会的快速发展,许多新兴应用领域中出现了实时连续、海量无限和快速变化的数据,这些数据以不同的更新速率连续地流进和流出计算机系统,学术界将它们定义为数据流。面对这种新型的数据形式,仍然运用传统的数据挖掘方法对其进行分析和研究显然是不恰当的。因此,迫切需要开发出新的技术和新的方法以解决目前的窘境。聚类是数据挖掘领域中一项非常重要的技术,对数据流进行聚类分析有相当大的现实意义。迄今为止,已有许多优秀的数据流聚类算法被相继提出,它们在一定程度上解决了数据流聚类分析的难题。
　　本文的研究内容集中于如何设计出一种高效率、高质量的数据流聚类算法。文章总结了相关的聚类理论和技术并且对现有的数据流聚类算法进行了分析和比较,在此基础上,针对数据流本身所具有的特点提出了一种高效、准确的数据流聚类算法EXCluStream。该算法借鉴了CluStream算法经典的在线—离线两阶段框架,并且根据可拓学的物元和经典域概念修改了微簇聚类特征结构。EXCluStream算法的聚类过程是:在线阶段使用本文所提出的基于可拓关联函数的聚类算法CABDF进行微簇的初始化,然后,当新数据点到来时,根据其关联度取值的情况将该数据点划分至关联度最大的簇中,以上过程进行的同时需要计算机每隔一段固定的时间就将微簇聚类特征以快照的形式存储于金字塔结构中以便于后续的分析。离线阶段将从硬盘中取出用户指定时间范围内的所有微簇,选取含有一定数目的微簇作为虚拟点,再次调用CABDF算法进行聚类。倘若用户需要对数据流的演变进行分析和比较,那么通过在线阶段存储下来的快照就可以做到。通过实验表明,本文所设计出的CABDF算法具有聚类质量高、可扩展性好的特点,除此之外,数据流聚类算法EXCluStream也达到了聚类纯度高、单遍扫描、实时返回结果的要求,该算法适用于大规模的动态数据集聚类的分析和研究。

目录

封面

目录

中文摘要

英文摘要

1 绪论

1.1 研究的背景和意义

1.2 国内外研究现状

1.3 本文的研究内容及创新点

1.4 论文的组织结构

2 聚类方法综述

2.1 聚类分析相关理论

2.2 传统聚类方法

2.3 其他聚类方法和技术

2.4 本章小结

3 数据流聚类方法综述

3.1 数据流聚类相关理论

3.2 数据流聚类相关技术

3.3 数据流聚类典型算法及比较

3.4 本章小结

4 基于可拓关联函数的数据流聚类算法

4.1 可拓学基础知识

4.2 本文算法的可拓学支撑概念

4.3 算法概念匹配说明

4.4 CABDF 算法

4.5 EXCluStream 算法

4.6 算法对离群点的处理

4.7 本章小结

5 实验设计与分析

5.1 实验环境和数据集说明

5.2 CABDF 算法的实验验证

5.3 EXCluStream 算法的实验验证

5.4 本章小结

6 总结与展望

6.1 本文工作总结

6.2 问题与展望

参考文献

攻硕期间发表的科研成果目录

致谢