融合iForest和LOF的大规模多维数据离群点检测方法研究

• 作 者: 程张玉
• 机 构: 武汉理工大学
• 出 处: 武汉理工大学
• 发表日期: 2020年01期
• 关键词: 离群点检测

离群点检测作为数据挖掘技术下的一个重要子项，被广泛应用于网络入侵检测、工业系统故障检测、智能家居系统及医疗诊断等领域。随着数据在规模和维度上的双重增长，如何在大规模多维数据集中准确高效地检测离群点成为一个非常关键且极具挑战性的课题。目前，常用的检测算法如孤立森林(Isolation Forest，iForest)、局部离群因子(Local OutlierFactor，LOF)等由于算法本身的局限性，在应用于大规模多维数据集的离群点检测时，在精度、效率以及泛化能力上的表现与其在常规规模低维数据集上的性能表现存在较大差距。孤立森林针对全样本和全特征空间进行双随机采样，不擅长检测局部离群点。局部离群因子算法本身较高的时间复杂度使其直接用于离群点占比非常稀少的大规模多维数据集检测时，效率较低。然而，拥有线性时间复杂度的孤立森林在大数据集处理上非常快速，且对于全局离群点的识别有着较高的精度。局部离群因子重点关注数据点的邻域信息，能有效避免数据密度分布不同对检测带来的影响。因此，本文提出了融合iForest和LOF的离群点检测方法(FSIF-HDLOF)，结合孤立森林和局部离群因子算法的优势来解决以上问题，即利用高效的孤立森林对原始数据集进行剪枝，再采用局部离群因子算法对剪枝后数据集进行更精确的检测。本文围绕上述方案从以下两个方面展开相关研究工作：
　　1)在剪枝阶段，本文提出基于数据降维和特征离群系数的孤立森林剪枝方法(FSIF)。孤立森林的算法性能容易受到大规模多维数据集中噪音和冗余特征的影响，因此，利用基于归一化互信息的特征选择算法(Normalized Mutual Information based Feature Selection，NMIFS)对原始数据集进行降维得到特征子集，再构建孤立树。在剪枝时，通过定义特征离群系数计算得到优化的剪枝阈值，剪枝掉高密度空间的数据点得到离群点候选集用于检测阶段的精确检测。
　　2)在检测阶段，本文提出基于邻域优化的局部离群因子方法(HDLOF)。由于局部离群因子采用欧式距离度量数据点相似度，并未考虑到不同特征对离群点检测的贡献各不相同，丢失了特征权重的重要信息。因此，设计了特征层面的信息熵加权策略，并对距离矩阵进行归一化，以此实现对数据点与其邻域关系的精准衡量。另一方面，局部离群因子的邻域超参数k通常采用随机或经验方式确定，对检测精度有较大影响且造成多余的邻域查询次数。为解决该问题，本文提出基于密度峰值的超参数优化策略，即利用基于密度峰值的聚类算法(Density Peaks Clustering Algorithm, DPCA)得到的数据集簇类信息计算簇类近邻数来针对性地设置超参数k。最后，通过自定义的加权融合公式判断离群点，进一步提高融合算法的检测精度。
　　本文所提出的融合iForest和LOF的大规模多维数据离群点检测方法，包含对iForest和LOF所做的优化，在真实数据集和合成数据集上的多组对比实验都表现出了良好的检测性能。综合来看，FSIF-HDLOF的检测精度更高、泛化能力更强，尤其在大数据量且低离群点比例的数据集上的离群点检测有着较大优势。同时，FSIF-HDLOF实现了检测精度和效率的良好平衡，能在获取比较好的离群点检测结果下保持较高的运行效率。