異常檢測原理與實驗

最近需要對欺詐報價進行識別處理，簡單的模型就是給定很多不同數據集，需要找出每個spu下可能存在的欺詐數據，比如{20,22,30},其中的欺詐數據可能就是30。其實加以抽象，屬于異常檢測范圍。

異常檢測是發現與大部分對象不同的對象，其中這些不同的對象稱為離群點。一般異常檢測的方法主要有數理統計法、數據挖掘方法。一般在預處理階段發生的異常檢測，更多的是依托數理統計的思想完成的。
一、基于模型
　　首先判斷出數據的分布模型，比如某種分布（高斯分布、泊松分布等等）。然后根據原始數據（包括正常點與離群點），算出分布的參數，從而可以代入分布方程求出概率。例如高斯分布，根據原始數據求出期望u和方差？，然后擬合出高斯分布函數，從而求出原始數據出現的概率；根據數理統計的思想，概率小的可以當做離群點。

優點：

方法簡單，無需訓練，可以用在小數據集上。

缺點：

發現離群點效果差，離群點對模型參數影響大，造成區分效果差。需要數值化

import java.util.List;
 
/**
 * 實現描述：計算正態分布
 *
 * @author jin.xu
 * @version v1.0.0
 * @see
 * @since 16-9-9 下午12:02
 */
public class Gauss {
    public double getMean(List<Double> dataList) {
        double sum = 0;
        for (double data : dataList) {
            sum += data;
        }
        double mean = sum;
        if (dataList.size() > 0) {
            mean = sum / dataList.size();
        }
        return mean;
    }
 
    public double getStd(List<Double> dataList, double mean) {
        double sum = 0;
        for (double data : dataList) {
            sum += (data - mean) * (data - mean);
        }
        double std = sum;
        if (dataList.size() > 0) {
            std = sum / dataList.size();
        }
        return Math.sqrt(std);
    }
 
    public double getProbability(double data, double meam, double std) {
        double tmp = (1.0 / (Math.sqrt(2 * 3.141592653) * std)) * Math.exp(-(Math.pow(data - meam, 2) / (2 * Math.pow(std, 2))));
        return tmp;
    }
}

二、基于近鄰度
　需要度量對象之間的距離，離群點一般是距離大部分數據比較遠的點。一般這種方法是計算每個點與其距離最近的k個點的距離和，然后累加起來，這就是K近鄰方法。

優點：

原理簡單，無需訓練，可用在任何數據集

缺點：

需要計算距離，計算量大，K的選定以及多于K個離群點聚集在一起導致誤判。

public class KNN {
    
    public static double process(int index,Position position, int k, List<Position> positionList) {
        List<Double> distances = Lists.newArrayList();
        for (int i = 0; i < positionList.size(); ++i) {
            if (i != index) {
                distances.add(Math.sqrt(Math.pow((positionList.get(i).getX() - position.getX()), 2)+Math.pow((positionList.get(i).getY()-position.getY()),2)));
            }
        }
        Collections.sort(distances);
        k = k < distances.size() ? k : distances.size();
 
        double knnDistance = 0.0;
        for (int i = 0; i < k; ++i) {
            knnDistance += distances.get(i);
        }
        return knnDistance;
    }
 
    private static class Position{
        int x;
        int y;
 
        public int getX() {
            return x;
        }
 
        public void setX(int x) {
            this.x = x;
        }
 
        public int getY() {
            return y;
        }
 
        public void setY(int y) {
            this.y = y;
        }
    }
 
}

三、基于密度
　低密度區域的數據點可以當做某種程度上的離群點?；诿芏鹊暮突诮彽氖敲芮邢嚓P的，簡單來說，密度和近鄰的距離成反比。一般的度量公式如下：

density(x,k)表示包含x的k近鄰的密度，distance(x,y)表示x到y的距離，N(x,k)表示x的k近鄰集合。

優點：

相對準確

缺點：

需要度量密度，需要設定閾值


四、基于聚類
　　丟棄遠離其他聚類簇的小聚類簇。需要給出小聚類簇的大小閾值、聚類簇距離閾值。常用的聚類方法比較多，比如K-means(變種K-models)、EM、層次聚類算法（分裂型和歸約型）。具體方法說明可見：漫話數據挖掘。

優點：

引入數據挖掘聚類的方法，在樣本充足的情況下準確度會相對較高

缺點：

需要訓練，計算量大，原理相對復雜

需要建立適當的模型，需要充足的訓練樣本

總之異常檢測的通用方法大致有４種：基于模型、k近鄰、基于密度和基于聚類的。實際使用數據是線上的報價，由于每個SPU下報價有限，聚類不適合，所以用基于模型的和k近鄰的做了試驗；基于密度的和K近鄰差不多，而且需要密度范圍的距離閾值，就沒有選擇。此外，涉及的實驗數據是公司的，代碼是興趣使然，所以就不公布具體實驗數據。