一种快速的离群点检测方法  

A novel method for rapidly outlier detection

作　　者：冯震[1,2] 付敬奇[1] 熊南[1] 

机构地区：[1]上海大学机电工程与自动化学院,上海200072 [2]湖北师范大学机电与控制工程学院,湖北435002

出　　处：《电子测量与仪器学报》2016年第11期1726-1734,共9页Journal of Electronic Measurement and Instrumentation

摘　　要：离群点检测已在许多领域得到了广泛的应用,支持向量数据描述(SVDD)是一种流行的离群点检测方法,但其训练阶段需要二次规划求解,以及决策阶段计算与支持向量数量呈线性关系等导致该方法具有较高时间复杂度。本文提出了一种快速SVDD离群点检测方法,首先在训练阶段利用训练集约简和二阶逼近的序列最小优化(SMO)算法降低训练时间,然后在决策阶段通过分析决策函数表达式,利用获取超球球心原像的方式降低决策时间,使得该方法的时间复杂度显著降低。利用标准的公用数据集验证提出的方法,结果表明该方法的时间复杂度明显优于传统的方法。Outlier detection is widely used in many fields. Support vector data description（ SVDD） method is a popular method for outlier detection. However,SVDD needs to solve quadratic programming problem in the training phase and the time complexity of SVDD is linear in the number of support vectors in the decision-making phase,which lead to the high time complexity of the method. Therefore,a fast SVDD algorithm for outlier detection is proposed in this paper. Firstly,training set reduction strategy and the Sequential Minimal Optimization（ SMO）algorithm based on the second order approximation are combined to accelerate the training speed of SVDD.Secondly,through the analysis of the expression decision function,the decision time is reduced by acquiring the pre-image of SVDD hyper-sphere center. Thus the time complexity of the method is significantly reduced. The proposed method is verified by standard public datasets. The experimental results show that the time complexity of the proposed method is obviously better than that of the traditional method.

关 键 词：支持向量数据描述 离群点 序列最小优化算法 原像 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TN911.23[自动化与计算机技术—计算机科学与技术]