空间离群点挖掘技术的研究

论文摘要

空间离群点是与其空间邻域中其它空间对象的非空间属性值存在明显差异的空间对象。空间离群点挖掘是空间数据挖掘的一个重要分支,在交通控制、遥感图像分析、气象预报和人口统计数据分析等应用中可揭示重要现象。随着传感器设备技术的发展,数据采集设备的数量越来越多,精度越来越高,采集的项目也越来越多,因此数据量越来越大,维数越来越高。然而现有的空间离群点挖掘算法主要是针对单维或中低维的中小规模数据量的挖掘,难以适应高维大数据量的挖掘,并且现有算法没有充分考虑空间数据的特点,挖掘的不是真正意义上的空间离群点,而是全局离群点。算法存在用户依赖性大,检测精度低,挖掘效率低等局限。此外,随着网络技术、传感器技术和无线通信技术的发展,数据的采集、收集、保存和处理都呈现分散状态,因此,基于分布环境的数据挖掘也引起人们的关注,但基于分布环境的空间离群点挖掘算法还未见报道。本文将根据空间数据自身的特点,研究属性划分方法和属性的权值设置方法,空间离群程度的度量方法,实现挖掘精度高、用户依赖性少的高效的空间离群点挖掘算法。针对现有算法主要局限在数值型属性数据处理上的不足,通过将非数值型数据转化为数值型数据,实现基于混合型属性的统一算法。针对高维大数据量,采用剪枝策略、基于子空间的离群点挖掘和集成学习的方法实现高维大数据量的挖掘:针对分布环境下的空间离群点挖掘,提出了基于隐私保护的空间离群点挖掘算法。论文的主要贡献如下:（1）提出基于属性划分的方法解决局部离群点的挖掘问题。一般的局部离群点的挖掘采用的是满维属性的挖掘方法,如LOF（Local Outlier Factor）方法,其结果是局部邻域的确定非常耗时,由于所有维属性不加区分地等同看待,所以离群度度量的准确性受到影响,影响了挖掘的精度和速度。提出将数据对象的属性划分为标识属性、环境属性和固有属性,标识属性起着标识对象的作用,如数据对象名称等;环境属性决定了对象所处环境,如地理位置、时间、序列等,可利用环境属性确定邻域;固有属性是数据对象特有属性,包括行为属性和状态属性,决定了对象的行为和状态特征,可利用该类属性确定对象的离群程度。（2）提出空间数据对象的离群程度的新的度量方法,即基于空间数据特性的空间局部离群系数SLOF（Spatial Local Outlier Factor）的度量方法;提出基于空间离群度的空间离群点挖掘算法ASLOF（Algodthm based on SLOF）。将数据对象的属性分为标识属性、空间属性和非空间属性,利用空间属性确定空间邻域、建立空间索引,利用非空间属性确定对象的离群程度,并在离群度的度量中引入属性的权值,提高度量精度,据此提出了基于空间离群度的空间离群点挖掘算法。理论证明和实验测试结果表明,ASLOF在挖掘的精度、用户依赖性和算法性能上均优于现有算法。（3）提出混合属性的统一的空间离群度的度量方法和挖掘算法。从离群点性质入手,通过统计分类属性的频度,将分类属性转化为数值型,并通过属性的权值设置和属性的标准化等处理后,实现基于混合属性的空间离群点的统一挖掘算法。实验结果表明,算法可有效实现混合属性的空间离群度的统一度量计算和有效挖掘。（4）提出基于集成学习的子空间离群点集成的高维大数据量的空间离群点快速挖掘算法S2OEAHL（Subspace Spatial Outlier Ensemble Algorithm baSed High-dimensional Large data sets）。由于很多空间数据对象的标识属性中含有空间对象所在的地域标识,根据地域标识构建对象的层次编码树,基于层次编码树,实现数据的分区和对象的快速检索,通过计算分区的上下界和使用包围盒检测方法,剪除明显不含有离群点的分区,保留可能含有离群点的分区作为候选分区,实现了分区的快速剪枝,从而降低数据处理数量。对候选分区采用子空间挖掘方法,为避免与属性维度成指数关系的大量搜索,采用指定子空间挖掘和基于子空间权值的集成融合方法来解决高维数据的离群点挖掘问题。算法的实现中采用了基于单维子空间的离群系数挖掘方法,并利用优化计算的方法求得被检测对象所对应的各属性的权值,在此基础上通过集成融合函数求得被检测对象的离群度,根据离群度的排序可获得所求离群点。理论证明和实验结果均表明算法的有效性和计算的高效性。（5）提出基于分布环境的隐私保护的空间离群点挖掘算法DPPASLOF（DistribuIcd Privacy Preserving Algorithm based on SLOF）。算法中利用空间数据的局部性,发挥各数据方的主动参与的能力,借助于空间索引技术和隐私保护协议以提高搜索能力和隐私保护能力。理论证明算法的安全性,计算的高效性和低通信代价。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 论文的主要研究内容及创新之处
• 1.2.1 论文的主要研究内容
• 1.2.2 论文主要贡献点
• 1.3 论文的组织结构
• 1.4 本章小结
• 第二章 离群点挖掘技术
• 2.1 离群点挖掘方法的分类
• 2.1.1 基于分布的离群点
• 2.1.2 基于深度的离群点
• 2.1.3 基于聚类的离群点
• 2.1.4 基于距离的离群点
• 2.1.5 基于密度的离群点
• 2.2 基于距离的离群点挖掘
• 2.2.1 基于索引的离群点挖掘算法
• 2.2.2 基于块嵌套循环的离群点挖掘算法
• 2.2.3 基于单元格的离群点挖掘算法
• 2.2.4 基于随机化嵌套循环和简单剪枝规则算法
• 2.3 基于密度的离群点挖掘
• 2.4 离群点挖掘研究热点及发展趋势
• 2.4.1 高维大数据集中离群点的挖掘
• 2.4.2 空间离群点的挖掘
• 2.4.3 时序离群点的挖掘
• 2.4.4 离群点挖掘的应用
• 2.5 本章小结
• 第三章 基于SLOF的空间离群点挖掘算法
• 3.1 基于属性划分的局部离群点挖掘
• 3.2 空间离群点挖掘的特性
• 3.2.1 空间数据特性
• 3.2.2 空间对象属性划分
• 3.2.3 空间离群点挖掘
• 3.3 基于SLOF的空间离群点挖掘算法
• 3.3.1 SLOF的计算
• 3.3.2 基于SLOF算法的形式化
• 3.3.3 ASLOF算法描述
• 3.3.4 算法复杂度分析
• 3.4 实验测试及分析
• 3.4.1 合成数据集1的测试结果与分析
• 3.4.2 合成数据集2的测试结果与分析
• 3.4.3 实际数据集的测试结果与分析
• 3.5 本章小结
• 第四章 混合属性数据的空间离群点挖掘
• 4.1 基于分类属性的离群点挖掘技术
• 4.1.1 基于信息熵理论的离群点挖掘
• 4.1.2 基于频繁模式的离群点挖掘
• 4.1.3 基于属性值频度的离群点挖掘
• 4.2 属性类型及标准化
• 4.2.1 属性类型
• 4.2.2 属性值的标准化
• 4.3 混合类型变量间的相异度计算
• 4.3.1 传统方法
• 4.3.2 改进方法
• 4.4 MASLOF算法
• 4.4.1 分类属性的数值化算法
• 4.4.2 基于混合属性的空间离群点挖掘算法
• 4.5 实验结果与分析
• 4.6 本章小结
• 第五章 高维大数据集的空间离群点快速挖掘算法
• 5.1 高维大数据量的离群点快速挖掘技术
• 5.1.1 高维离群点挖掘研究
• 5.1.2 离群点快速挖掘算法研究
• 5.1.3 高维空间大数据量离群点的挖掘研究
• 5.2 基于层次结构的剪枝策略
• 5.2.1 层次编码结构
• 5.2.2 基于层次编码结构的快速剪枝策略
• 5.3 属性的权值确定
• 5.4 基于子空间的空间离群度度量和挖掘算法
• 5.4.1 基于离群子空间的空间离群度度量
• 5.4.2 基于离群子空间的空间离群点挖掘算法
• 5.5 基于集成学习的空间离群点挖掘
• 5.5.1 基于集成学习的快速空间离群点挖掘算法
• 5.5.2 分区和剪枝
• 5.5.3 基于子空间的空间离群点挖掘
• 5.5.4 属性的权值的计算
• 5.5.5 子空间的集成
• 5.5.6 算法复杂度分析
• 5.6 实验结果与分析
• 5.6.1 实际数据集测试结果与分析
• 5.6.2 合成数据集测试结果与分析
• 5.7 本章小结
• 第六章 分布式环境下隐私保护的空间离群点挖掘
• 6.1 相关概念与定义
• 6.2 隐私保护的安全多方计算协议
• 6.3 DPPASLOF算法
• 6.3.1 问题形式化
• 6.3.2 索引和数据结构
• 6.3.3 DPPASLOF算法描述
• 6.3.5 算法的安全性分析
• 6.3.6 算法的复杂度分析
• 6.3.7 算法的通信开销分析
• 6.4 本章小结
• 第七章 结束语
• 7.1 工作总结
• 7.2 下一步的研究方向
• 致谢
• 参考文献
• 攻读博士学位期间发表的学术论文与课题