面向跨类型离群检测的度量空间索引构建方法研究

The traditional customized outlier detection algorithms usually support single data type only, so that we have to develop corresponding outlier detection systems for every data type. With the variety challenge of big data, it is urgent to study the universal outlier detection algorithm for various data types. This project aims to establish a theoretical framework of universal outlier detection based on metric space index, optimize the use of distance triangle inequality, make some breakthroughs such as the insufficient available information caused by the higher abstraction, and the low reuse rate of distance information, then solve some key problems such as defining the goals of pivot selection, reducing the pivot candidate set, improving index efficiency. Specifically, at first, completely on the basis of distance, we will research an index based metric space outlier detection model. Following that, fast randomly sampling based pivot selection target and selection algorithm will be devised. Furthermore, we will study a heterogeneous multilevel metric space index construction algorithm and develop a prototype system to carry out verified experiments with the UCI dataset and examples of various data types. The research results are expected to provide new ideas for the analysis and mining of cross data type, also offer useful reference for the selection of pivots and index construction in this field.

传统专用离群检测算法通常仅支持单一数据类型，针对各类数据特点研发相应的离群检测系统。面对大数据时代数据类型多样性挑战，迫切需要开展面向跨类型数据的离群检测算法研究。本项目旨在建立基于度量空间索引的跨类型离群检测理论框架，充分利用距离三角不等性，突破高层次抽象导致的可用信息过少、距离信息重用率低等瓶颈，解决支撑点选取目标不明确、候选范围过大、单层索引效率低下等问题。主要研究内容包括：首先，在完全基于距离的前提下，研究基于索引的度量空间离群检测模型；其次，基于快速随机抽样，研究索引所用全局支撑点的选取目标及高效选取算法；最后，研究面向离群检测的异构多层次度量空间索引构建方法，并研发原型系统，结合多种类型的UCI数据集及实例，验证所提模型和算法的有效性。本项目的研究将为跨类型数据的分析挖掘提供新的思路，为本领域的支撑点选取及索引构建问题提供有益借鉴。

面对大数据时代数据类型多样性挑战，针对单一数据特点研发的传统专用离群检测算法难以同时胜任多种数据类型。在此背景下，本项目开展面向跨类型数据的离群检测算法研究，建立了基于度量空间索引的跨类型离群检测理论框架，充分利用距离三角不等性，突破高层次抽象导致的可用信息过少、距离信息重用率低等瓶颈，解决索引建立开销大且效率低下的问题。.项目进展顺利，各项研究计划均已完成。主要研究内容包括：基于索引的度量空间离群检测模型，基于快速随机抽样的多重支撑点选取算法，异构多层次度量空间索引构建方法，并研发了原型系统，面向多种应用领域进行探索。项目利用索引建立阶段支撑点与数据集所有对象的距离计算结果，进一步计算出离群检测的预阈值，创造性地使数据集首个数据块在离群检测时即可用预阈值排除部分非离群点，减少了距离计算次数，在4个常用数据集上的实验结果表明其检测效率较不使用预阈值时平均提高约12%。另一方面，项目从如何确定支撑点处于密集区域开展研究，提出了一种基于自适应截止距离的密度峰值的支撑点选取算法，以快速获得合适的支撑点，并基于该算法开发了一种改进的离群点检测算法，实验结果表明其较不使用该支撑点选取算法减少了53%的距离计算次数。在建立多层次索引方面，项目研究了同时建立一维映射索引、候选支撑点空间索引，配合相应的剪枝规则，利用距离三角不等性，最终实现加速离群检测过程。项目成果主要包括发表/录用学术论文4篇（其中SCI 3篇、EI 1篇），PCT 1项，实用新型专利2项，获软件著作权登记1项，申请中国发明专利7项，获奖励2项，培养本科生6人，线下参加国内外学术合作交流11次。.本项目的研究为跨类型数据的分析挖掘提供了新的思路，为数据挖掘领域的支撑点选取及度量空间索引构建问题提供有益借鉴。