论文部分内容阅读
传统的基于全维空间的离群点挖掘技术受“维灾”影响，不再适用于高维数据。为了从高维数据中发现有意义的离群点，学者们提出将高维空间的数据投影到子空间上进行离群点挖掘。子空间离群点挖掘目的是在任何可能的属性子集中检测离群点，对于高维数据而言穷举所有可能的子空间进行离群点挖掘是不可行的。事实上，并非所有子空间都存在离群点，如果子空间中数据随机均匀分布，则该子空间不存在离群点，就可在离群点挖掘过程中忽略处理。关联子空间离群点挖掘正是在这个基础上提出的，旨在搜寻分布不均的、更可能存在离群点的、关联性高的子空间进行离群点挖掘。 已有的局部关联子空间离群点挖掘方法的主要局限是:(1)无法反映子空间的关联程度，对子空间是否关联进行0-1判断导致子空间选取不准确，且采用类似穷举的方式搜索子空间导致时间复杂度高。(2)未考虑大量不大可能构成数据点关联子空间的属性的影响，在全维属性集合中搜索子空间，导致不必要的时间开销，且所得子空间质量降低致使离群点挖掘精度降低。 针对上述问题，本文采用数据点及其邻域在各维属性投影上的最大非均匀分布程度衡量子空间的关联性，采用自底向上的方式搜索子空间。为了进一步提高算法的有效性，根据数据点及其局部邻域在属性投影上的取值分布计算属性的局部信息熵，只选取局部信息熵高的属性构成候选属性集合，并基于该候选属性集合搜索子空间。论文主要工作如下: (1)提出局部关联子空间离群点挖掘算法RSOM(Outlier Mining in RelevantSubspaces)。采用数据点及其邻域在各维属性投影上的最大非均匀分布程度衡量子空间的关联程度，以增加子空间选取的鲁棒性，进而提高离群点挖掘精度;采用自底向上的方式搜索子空间，以降低子空间搜索的时间复杂度。实验结果表明，RSOM大大降低了时间开销，显著地提高了离群点挖掘精度。 (2)提出基于局部信息熵的关联子空间离群点挖掘算法LERSOM(LocalInformation Entropy based Outlier Mining in Relevant Subspaces)。从信息熵的角度考虑离群点在某些属性上取值的不确定性，根据数据点及其局部邻域在属性投影上的取值分布计算属性的局部信息熵，只选局部信息熵高的属性构成数据点的候选属性集合进行离群点挖掘，减少了需要处理的子空间数量并提高了所得子空间的质量。实验结果表明，LERSOM获得较高的挖掘精度，且时间开销减半。 (3)采用模块化的设计方式，设计并实现了关联子空间离群点挖掘原型系统，在可视化环境下进行实验操作，以便检验本文所提方法的效果和性能。对系统的测试结果表明，系统运行良好，达到预期目标。