基于空间划分的优化聚类算法及相关技术研究

论文题目: 基于空间划分的优化聚类算法及相关技术研究

论文类型: 博士论文

论文专业: 计算机软件与理论

作者: 孙焕良

导师: 于戈

关键词: 知识发现,决策支持,数据挖掘,空间划分,聚类分析,数据流,数据流挖掘,滑动窗口,演化分析,孤立点检测

文献来源: 东北大学

发表年度: 2005

论文摘要: 数据挖掘是在海量的数据中提取隐含的、未知的、潜在有用的知识或信息模式的决策支持方法，是20世纪90年代初针对“数据丰富、知识贫乏”问题应运而生的一种新技术。为了有效地从海量数据中提取信息，数据挖掘算法必须具有良好的可伸缩性，也就是说，数据挖掘算法的运行时间必须是可预计的、可接受的。 在众多方法中，基于空间划分的方法是一种有效处理海量数据的数据挖掘方法，其主要应用于聚类分析算法与孤立点检测算法。然而，现有的基于空间划分的方法却存在如下问题：第一，由于空间划分时产生的单元数与维数呈指数增长，该方法多适用于维数相对较低的数据。第二，在一些基于空间划分的数据挖掘方法中，如基于单元的聚类算法，如果划分粒度越细，则聚类精度越高，但同时粒度越细生成的单元数也越多，造成算法效率下降。如果划分的粒度变粗，则算法精度难以保证。 针对目前基于空间划分的方法存在的问题，本文提出了一种新的基于空间划分的索引结构CD-Tree。为了降低空间复杂度，在保持单元间关系的条件下，CD-Tree只保存了非空单元，使得聚类与孤立点检测过程易于实现。文中给出了CD-Tree详细定义，设计了CD-Tree的构建、节点删除、树合并等相关算法，分析了CD-Tree相关算法的时间复杂度，并与其它存储结构的时间复杂度进行了对比。通过理论分析，对于空间划分问题，CD-Tree结构要优于其它可用于存储划分后单元的结构。 CD-Tree适用于当空间划分产生较多的空单元情况，而空单元的数量与数据的偏斜程度有关，数据偏斜程度越高，则生成的空单元数越多。为了确定CD-Tree的适用条件，需要一个度量来衡量空间划分下的数据偏斜程度。现有的衡量数据偏斜的度量不能用于衡量空间划分下的数据偏斜程度，本文提出了一种新的偏斜度的度量DSF(Data Skew Factor)。DSF相当于划分后空单元所占的比例，可用来估计生成非空单元数目。另外，DSF还可用于优化CD-Tree结构及在数据流聚类中动态调整划分的粒度。 在CD-Tree及DSF基础上，本文研究了基于空间划分的优化聚类算法及相关技术，具体包括：基于空间划分的聚类算法；基于空间划分的数据流聚类算法；基于空间划分的孤立点检测算法。 在基于空间划分的聚类算法方面，分析现有的基于空间划分的聚类方法的特

论文目录:

独创性声明

学位论文版权使用授权书

摘要

ABSTRACT

目录

第一章 前言

1.1 问题提出

1.2 数据挖掘概述

1.2.1 数据挖掘过程

1.2.2 数据挖掘方法分类

1.2.3 数据挖掘的主要研究问题

1.3 本文研究的问题及组织结构

1.3.1 研究的问题

1.3.2 本文的工作

1.3.3 本文的结构组织

第二章 相关概念与技术

2.1 聚类分析算法概述

2.1.1 相似性度量方法

2.1.2 数据挖掘对聚类典型要求

2.1.3 典型聚类算法

2.1.3.1 层次聚类方法

2.1.3.2 划分聚类方法

2.1.3.3 基于密度的聚类方法

2.1.3.4 基于空间划分的聚类方法

2.1.4 聚类算法小结

2.2 数据流聚类算法概述

2.2.1 数据流聚类分析特点

2.2.2 数据流聚类算法

2.2.2.1 数据流聚类理论与实践

2.2.2.2 通过数据流窗口维护方差和k-Medians

2.2.2.3 聚类演化数据流的一个框架

2.2.2.4 投影聚类高维数据流的框架

2.2.3 普适数据流挖掘方法

2.2.4 数据流聚类算法小结

2.3 孤立点检测算法概述

2.3.1 孤立点的概念

2.3.2 典型孤立点检测算法

2.3.2.1 基于距离的孤立点检测算法

2.3.2.2 基于密度的孤立点检测算法

2.3.3 孤立点检测小结

2.4 多维索引结构

2.4.1 R-tree及R~*-tree索引

2.4.2 SS-tree和SR-tree

2.4.3 索引技术小结

2.5 本章小结

第三章 空间划分的索引结构CD-Tree

3.1 问题提出

3.2 CD-Tree定义

3.3 CD-Tree相关算法

3.3.1 CD-Tree的创建算法

3.3.2 CD-Tree的单元点查询算法

3.3.3 单元删除算法

3.3.4 CD-Tree的合并算法

3.3.5 CD-Tree上的近邻查询算法

3.4 CD-Tree相关算法的代价分析

3.5 数据偏斜度DSF

3.5.1 数据偏斜度概念

3.5.2 偏斜度实验分析

3.6 本章小结

第四章 基于空间划分的聚类算法

4.1 问题提出

4.2 相关工作

4.3 相关概念

4.4 基于CD-Tree的聚类算法

4.5 CD-Tree的聚类算法性能优化

4.5.1 分支结点数据点总数剪枝策略

4.5.2 分支结点数据对象个数最大值剪枝策略

4.6 实验分析

4.6.1 CDT与CL的比较

4.6.2 基于CD-Tree的算法性能比较

4.6.3 剪枝算法的适用性分析

4.6.4 二维数据的聚类结果

4.7 本章小结

第五章 基于空间划分的数据流聚类算法

5.1 问题提出

5.2 问题定义

5.3 CDS-Tree

5.3.1 CDS-Tree定义

5.3.2 CDS-Tree相关算法

5.3.2.1 CDS-Tree构建算法

5.3.2.2 CDS-Tree合并算法

5.4 CDS-Tree在滑动窗口上的更新

5.4.1 桶的更新

5.4.2 粒度调整

5.5 离线聚类与演化分析

5.6 实验分析

5.6.1 可伸缩性测试

5.6.2 精度测试

5.6.3 内存的使用情况

5.6.4 粒度调整

5.6.5 数据流的演化分析

5.7 本章小结

第六章 基于空间划分的孤立点检测算法

6.1 问题提出

6.2 基于单元的孤立点检测算法

6.3 基于CD-Tree的孤立点检测算法

6.4 基于CD-Tree和聚簇技术的磁盘算法

6.5 CD-Tree结构优化

6.6 实验分析

6.6.1 有效性验证

6.6.2 算法性能比较

6.7 本章小结

第七章 结束语

7.1 本文的主要贡献与结论

7.2 进一步的工作

参考文献

致谢

攻博期间发表的文章

攻博期间参加和完成的科研项目

作者简介

发布时间: 2006-10-25

参考文献

• [1].基于计算智能的聚类技术及其应用研究[D]. 冯永.重庆大学2006
• [2].基于计算智能的聚类组合算法研究[D]. 杨燕.西南交通大学2006
• [3].聚类分析中的最佳聚类数确定方法研究及应用[D]. 周世兵.江南大学2011

相关论文

• [1].面向聚类的数据可视化方法及相关技术研究[D]. 任永功.东北大学2006
• [2].基于网格和密度的数据流聚类方法研究[D]. 单世民.大连理工大学2006
• [3].时间序列与聚类挖掘相关技术研究[D]. 刘兵.复旦大学2006
• [4].聚类分析中若干关键技术及其在电信领域的应用研究[D]. 牛琨.北京邮电大学2007
• [5].基于网格方法的聚类算法研究[D]. 孙玉芬.华中科技大学2006

标签：知识发现论文;  决策支持论文;  数据挖掘论文;  空间划分论文;  聚类分析论文;  数据流论文;  数据流挖掘论文;  滑动窗口论文;  演化分析论文;  孤立点检测论文;