不确定数据的聚类分析与异常点检测算法

摘要

不确定数据作为一种新型的数据模型，被广泛应用于金融、基于位置的服务、移动物体监测、传感器网络等许多类型应用领域。近年来出现的面向不确定数据的分析处理技术已成为数据库、数据挖掘等领域的研究热点。不确定性的存在给研究人员带来了新的挑战:一方面，传统的数据挖掘技术中的基本概念都是面向确定数据的，需要扩展后应用于不确定数据;另一方面，不确定数据对应的可能世界模型中的实例数量是指数级增长的，会增加挖掘算法的复杂度并增加运行时间、内存占用率等资源消耗。
　　基于此，在了解和掌握数据挖掘基本概念和相关算法、不确定数据的产生背景及数据模型特点的基础上，本文主要研究了不确定数据的聚类和异常点检测问题，旨在为不确定数据提供更为多样的聚类分析和异常点检测功能。同时，对本文所提出的算法进行大量的相关实验分析，实验结果证明了提出算法的有效性和高效性。本文的主要贡献体现在以下几个方面:
　　(1)本文提出了一种障碍空间中不确定数据聚类算法OBS-UK-means(ObstacleUncertain K-means)，为了保证聚类准确性的前提下提高算法效率，分别提出了基于R树和Voronoi图的两种剪枝策略和最近距离区域的概念。通过实验验证了OBS-UK-means算法的高效性和准确性，同时证明了剪枝策略在不损害聚类有效性的情况下，能够有效的提高聚类效率。
　　(2)本文提出了基于密度的局部不确定数据异常点检测算法。首先提出了一个新的基于密度的局部异常点的定义，其次，为提高算法效率，提出基于动态规划的方法进行异常点检测。最后，设计相应的剪枝策略以降低存储代价并提高算法的效率。
　　(3)本文提出了基于不确定数据流参数可变的异常点检测算法。首先根据不确定数据流上异常点的性质，提出了可以有效检测不确定数据流中异常点的算法CUOD(Continuous Uncertain Outlier Detection)。其次为了提高算法效率，提出了通过估计异常点的概率而进行剪枝的算法PCUOD（Probability pruning forContinuous Uncertain Outlier Detection）。然后，为了满足用户在不同时刻对异常点查询参数有不同的需求，提出了不确定数据流中参数可变的异常点查询算法。
　　(4)本文提出了面向不确定数据流基于距离的异常点检测算法。首先针对特定的不确定数据模型提出了异常点的定义，同时设计动态存储结构，以满足算法在检测效率和存储空间两方面的要求。其次，为了降低近邻查询的代价以进一步提高算法的效率，提出了基于SM-tree（Statistics M-tree）的近邻查询算法。最后，为解决异常点定义中涉及的参数过多，造成用户难以得到理想查询结果的问题，提出了不确定数据流top-n异常点查询算法。
　　综上所述，针对分析不确定数据所面临的挑战，本文提出了几种面向不确定数据的聚类和异常点检测算法，是对现有不确定数据挖掘技术的有益补充。理论分析和实验结果均证明，本文所提出的算法在准确性、执行效率及存储代价等方面，均优于现有算法。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．1．1 不确定数据产生的原因

1．1．2 不确定数据模型

1．2 不确定数据面临的挑战

1．3 相关工作

1．3．1 确定数据聚类

1．3．2 不确定数据聚类

1．3．3 异常点检测

1．3．4 数据流异常点检测

1．4 本文的主要贡献

1．5 本文组织结构

第2章 障碍空间中不确定数据聚类算法

2．1 引言

2．2 问题定义

2．3 OBS-UK-Means算法描述

2．4 剪枝方法

2．4．1 基于R树的剪枝方法

2．4．2 基于Voronoi图的剪枝方法

2．4．3 最短距离区域

2．5 性能分析

2．5．1 数据集

2．5．2 效率测试

2．5．3 有效性测试

2．5．4 聚类质量

2．6 本章小结

第3章 不确定数据基于密度的局部异常点检测

3．1 引言

3．2 问题定义

3．3 不确定数据基于密度的局部异常点检测

3．3．1 异常点检测算法

3．3．2 剪枝算法

3．4 性能分析

3．4．1 剪枝率测试

3．4．2 效率测试

3．4．3 准确度测试

3．5 本章小结

第4章 不确定数据流上参数可变的异常点检测

4．1 引言

4．2 问题定义

4．3 不确定数据流上异常点检测

4．3．1 基础算法

4．3．2 异常点概率界限

4．3．3 k变化的查询

4．4 性能分析

4．4．1 运行时间

4．4．2 存储空间

4．4．3 准确度

4．5 本章小结

第5章 不确定数据流上基于距离的异常点检测

5．1 引言

5．2 问题定义

5．3 检测算法

5．3．1 算法架构

5．3．2 增量算法

5．3．3 S M-tree

5．4 Top-n异常点检测

5．5 性能分析

5．5．1 运行时间

5．5．2 存储空间

5．6 本章小结

第6章 结束语

6．1 本文工作的总结

6．2 未来工作展望

参考文献

致谢

攻博期间发表的文章

科研经历

作者简介