一、 什么是離群點分析
1、什么是離群點？
在樣本空間中，與其他樣本點的一般行為或特征不一致的點，我們稱為離群點。
2、離群點產(chǎn)生的原因？
第一， 計算的誤差或者操作的錯誤所致，比如：某人的年齡-999歲，這就是明顯由誤操作所導致的離群點；
第二， 數(shù)據(jù)本身的可變性或彈性所致，比如：一個公司中CEO的工資肯定是明顯高于其他普通員工的工資，于是CEO變成為了由于數(shù)據(jù)本身可變性所導致的離群點。
3、為什么要對離群點進行檢測？
“一個人的噪聲也許是其他的信號”。換句話說，這些離群點也許正是用戶感興趣的，比如在欺詐檢測領域，那些與正常數(shù)據(jù)行為不一致的離群點，往往預示著欺詐行為，因此成為執(zhí)法者所關注的。
4、離群點檢測遇到的困難？
第一， 在時間序列樣本中發(fā)現(xiàn)離群點一般比較困難，因為這些離群點可能會隱藏在趨勢、季節(jié)性或者其他變化中；
第二， 對于維度為非數(shù)值型的樣本，在檢測過程中需要多加考慮，比如對維度進行預處理等；
第三， 針對多維數(shù)據(jù)，離群點的異常特征可能是多維度的組合，而不是單一維度就能體現(xiàn)的。
二、 幾類離群點檢測方法
1、基于統(tǒng)計分布的離群點檢測
這類檢測方法假設樣本空間中所有數(shù)據(jù)符合某個分布或者數(shù)據(jù)模型，然后根據(jù)模型采用不和諧校驗（discordancy test）識別離群點。不和諧校驗過程中需要樣本空間數(shù)據(jù)集的參數(shù)知識（eg:假設的數(shù)據(jù)分布），分布的參數(shù)知識（eg:期望和方差）以及期望的離群點數(shù)目。
不和諧校驗分兩個過程：工作假設和備選假設
工作假設指的是如果某樣本點的某個統(tǒng)計量相對于數(shù)據(jù)分布的是顯著性概率充分小，那么我們則認為該樣本點是不和諧的，工作假設被拒絕，此時備用假設被采用，它聲明該樣本點來自于另一個分布模型。
如果某個樣本點不符合工作假設，那么我們認為它是離群點。如果它符合備選假設，我們認為它是符合某一備選假設分布的離群點。
基于統(tǒng)計分布的離群點檢測的缺點：
第一， 在于絕大多數(shù)不和諧校驗是針對單個維度的，不適合多維度空間；
第二， 需要預先知道樣本空間中數(shù)據(jù)集的分布特征，而這部分知識很可能是在檢測前無法獲得的。
2、基于距離的離群點檢測
基于距離的離群點檢測指的是，如果樣本空間D中至少有N個樣本點與對象O的距離大于dmin,那么稱對象O是以{至少N個樣本點}和dmin為參數(shù)的基于距離的離群點。
其實可以證明，在大多數(shù)情況下，如果對象O是根據(jù)基于統(tǒng)計的離群點檢測方法發(fā)現(xiàn)出的離群點，那么肯定存在對應的N和dmin，是它也成為基于距離的離群點。
Eg:假設標準正態(tài)分布，如果離均值偏差3或更大的對象認為是離群點，根據(jù)正態(tài)曲線概率密度函數(shù)， P（|x-3|<=dmin）<1-N/總點數(shù)，即P（3-dim=<x<=3+dmin）<1-N/總點數(shù)，假設dmin=0.13,則該dmin領域表示[2.87,3.13]的范圍，假設總點數(shù)=10000, N=12.
基于距離的離群點檢測的缺點:
要求數(shù)據(jù)分布均勻，當數(shù)據(jù)分布非均勻時，基于距離的離群點檢測將遇到困難。
3、基于密度的局部離群點檢測
什么是局部離群點？
一個對象如果是局部離群點，那么相對于它的局部領域，它是遠離的。
不同于前面的方法，基于密度的局部離群點檢測不將離群點看做一種二元性質，即不簡單用Yes or No來斷定一個點是否是離群點，而是用一個權值來評估它的離群度。
它是局部的，意思是該程度依賴于對象相對于其領域的孤立情況。這種方法可以同時檢測出全局離群點和局部離群點。
通過基于密度的局部離群點檢測就能在樣本空間數(shù)據(jù)分布不均勻的情況下也可以準確發(fā)現(xiàn)離群點。
4、基于偏差的離群點檢測
基于偏差的離群點檢測，它通過檢查一組對象的主要特征來識別離群點，“偏差”這種特征的點我們認為是離群點。
通常有兩種技術：
第一， 順序異常技術
第二， 采用OLAP數(shù)據(jù)立方體技術
三、 基于密度的局部離群點檢測
前面介紹了什么叫做基于密度的局部離群點檢測，以及它的優(yōu)勢?，F(xiàn)在詳細介紹下它的一些概念。
1、 對象p的第k距離
對于正整數(shù)k,對象p的第k距離可記作k-distance(p)。
在樣本空間中，存在對象o，它與對象p之間的距離記作d(p,o)。如果滿足以下兩個條件，我們則認為k-distance(p)= d(p,o)
1） 在樣本空間中，至少存在k個對象q,使得d(p,q)<= d(p,o);
2） 在樣本空間中，至多存在k-1個對象q,使得d(p,q)<d(p,o)
換句話說，滿足這兩個標準的k-distance(p)其實就是計算樣本空間中其他對象與對象p之間的距離，然后找到第k大的那個距離，即為k-distance(p)。顯而易見，如果使用k-distance(p)來量化對象p的局部空間區(qū)域范圍，那么對于對象密度較大的區(qū)域，k-distance(p)值較小，而對象密度較小的區(qū)域，k-distance(p)值較大。
2、 對象p的第k距離領域（k-distance neighborhood of an object p）
已知對象p的第k距離，那么，與對象p之間距離小于等于k-distance(p)的對象集合稱為對象p的第k距離領域，記作：Nkdis(p)(p)
該領域其實是以p為中心，k-distance(p)為半徑的區(qū)域內(nèi)所有對象的集合（不包括P本身）。由于可能同時存在多個第k距離的數(shù)據(jù)，因此該集合至少包括k個對象。
可以想象，離群度較大的對象Nkdis(p)(p)范圍往往比較大，而離群度小的對象Nkdis(p)(p)范圍往往比較小。對于同一個類簇中的對象來說，它們涵蓋的區(qū)域面積大致相當。
3、 對象p相對于對象o的可達距離
可達距離reachdisk(p,o)=max{ k-distance(o),d(p,o)},即k-distance(o)和d(p,o)值較大的那個。
4、 局部可達密度是基于p的k最近鄰點的平均可達密度的倒數(shù)。如下
可以發(fā)現(xiàn)，如果對象p的離群度較小，那么對于同一類簇的數(shù)據(jù)對象reachdisk(p,o)取k-distance(o)可能性較大，因此它們的Lrdk(p)值波動性較?。欢绻麑ο?/span>p的利群度較大，那么reachdisk(p,o)取d(p,o)的可能性較大，對于同一類簇的數(shù)據(jù)對象，它們的Lrdk(p)值波動性也比較大，并且Lrdk(p)值較小。
5、 局部離群點因子（LOF）
它代表了p為離群點的程度。如果對象p的離群程度較大，則它k領域中大多數(shù)是離對象p較遠且處于某一個類簇的數(shù)據(jù)對象，那么這些數(shù)據(jù)對象的lrd應該是偏大，而對象p本身的lrd是偏小，最后所得的LOF值也是偏大。反之，如果對象p的離群程度較小，對象o的lrd和對象p的lrd相似，最后所得的lof值應該接近1.
四、 算法實現(xiàn)
算法：基于密度的局部離群點檢測（lof算法） 輸入：樣本集合D，正整數(shù)K（用于計算第K距離） 輸出：各樣本點的局部離群點因子 過程：1）計算每個對象與其他對象的歐幾里得距離 2）對歐幾里得距離進行排序，計算第k距離以及第K領域 3）計算每個對象的可達密度 4）計算每個對象的局部離群點因子 5）對每個點的局部離群點因子進行排序，輸出。 |
-------------------------------------------------------------------
源碼：
package com.lof;
import java.util.ArrayList;
import java.util.List;
public class Node {
private String nodeName; // 樣本點名
private double[] dimensioin; // 樣本點的維度
private double kDistance; // k-距離
private List<Node> kNeighbor=new ArrayList<Node>();// k-領域
private double distance; //到給定點的歐幾里得距離
private double reachDensity;// 可達密度
private double reachDis;// 可達距離
private double lof;//局部離群因子
public Node(){
}
public Node(String nodeName,double[] dimensioin){
this.nodeName=nodeName;
this.dimensioin=dimensioin;
}
public String getNodeName() {
return nodeName;
}
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public double[] getDimensioin() {
return dimensioin;
}
public void setDimensioin(double[] dimensioin) {
this.dimensioin = dimensioin;
}
public double getkDistance() {
return kDistance;
}
public void setkDistance(double kDistance) {
this.kDistance = kDistance;
}
public List<Node> getkNeighbor() {
return kNeighbor;
}
public void setkNeighbor(List<Node> kNeighbor) {
this.kNeighbor = kNeighbor;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public double getReachDensity() {
return reachDensity;
}
public void setReachDensity(double reachDensity) {
this.reachDensity = reachDensity;
}
public double getReachDis() {
return reachDis;
}
public void setReachDis(double reachDis) {
this.reachDis = reachDis;
}
public double getLof() {
return lof;
}
public void setLof(double lof) {
this.lof = lof;
