一种基于k近邻图的稀有类检测算法

来源：软件学报杂志2016年第9期北京时间：

作者：王淞,黄浩,余果,梁楠,王黎维,孙月明

单位：王淞，武汉大学 计算机学院, 湖北 武汉 43007211,黄浩，武汉大学 计算机学院, 湖北 武汉 43007202,余果，武汉大学 中南医院, 湖北 武汉 43007203,梁楠，武汉大学 计算机学院, 湖北 武汉 43007204,王黎维，武汉大学 国际软件学院, 湖北 武汉 43007205,孙月明，武汉大学 计算机学院, 湖北 武汉 43007206

摘要：稀有类检测的目标是为无类别标签的数据集中的每个类，特别是仅含少量数据样本的稀有类，寻找到至少一个数据样本以证明数据集中存在这些类.该技术在金融欺诈检测及网络入侵检测等现实问题中具有广泛的应用场景.但是，现有的稀有类检测算法往往存在以下问题：（1）时间复杂度比较高；或（2）对原始数据集需要一定的先验知识，如数据集中各类数据样本所占比例等.提出了一种基于k邻近图的无先验快速稀有类检测算法KRED，通过利用稀有类数据样本在小范围内紧密分布所造成的与周边数据分布的不一致性来定位稀有类.为此，KRED将给定数据集转化为k邻近图，并计算图中各顶点入度和边长的变化.最后，将以上变化最大的顶点对应的数据样本作为稀有类的候选样本.实验结果表明：KRED有效提高了发现数据集中各个类的效率，明显缩短了算法运行所需时间.

关键词：稀有类检测;k邻近图;数据分布;变化系数;入度

基金资助：国家自然科学基金（61502347，61272275，61202033，61070013，U1135005）；中央高校基本科研业务费专项资金（2042015kf0038）；武汉大学人才计划/引进人才科研启动经费