一、 什么是离群点分析
1、什么是离群点？
在样本空间中，与其他样本点的一般行为或特征不一致的点，我们称为离群点。
2、离群点产生的原因？
第一， 计算的误差或者操作的错误所致，比如：某人的年龄-999岁，这就是明显由误操作所导致的离群点；
第二， 数据本身的可变性或弹性所致，比如：一个公司中CEO的工资肯定是明显高于其他普通员工的工资，于是CEO变成为了由于数据本身可变性所导致的离群点。
3、为什么要对离群点进行检测？
“一个人的噪声也许是其他的信号”。换句话说，这些离群点也许正是用户感兴趣的，比如在欺诈检测领域，那些与正常数据行为不一致的离群点，往往预示着欺诈行为，因此成为执法者所关注的。
4、离群点检测遇到的困难？
第一， 在时间序列样本中发现离群点一般比较困难，因为这些离群点可能会隐藏在趋势、季节性或者其他变化中；
第二， 对于维度为非数值型的样本，在检测过程中需要多加考虑，比如对维度进行预处理等；
第三， 针对多维数据，离群点的异常特征可能是多维度的组合，而不是单一维度就能体现的。
二、 几类离群点检测方法
1、基于统计分布的离群点检测
这类检测方法假设样本空间中所有数据符合某个分布或者数据模型，然后根据模型采用不和谐校验（discordancy test）识别离群点。不和谐校验过程中需要样本空间数据集的参数知识（eg:假设的数据分布），分布的参数知识（eg:期望和方差）以及期望的离群点数目。
不和谐校验分两个过程：工作假设和备选假设
工作假设指的是如果某样本点的某个统计量相对于数据分布的是显著性概率充分小，那么我们则认为该样本点是不和谐的，工作假设被拒绝，此时备用假设被采用，它声明该样本点来自于另一个分布模型。
如果某个样本点不符合工作假设，那么我们认为它是离群点。如果它符合备选假设，我们认为它是符合某一备选假设分布的离群点。
基于统计分布的离群点检测的缺点：
第一， 在于绝大多数不和谐校验是针对单个维度的，不适合多维度空间；
第二， 需要预先知道样本空间中数据集的分布特征，而这部分知识很可能是在检测前无法获得的。
2、基于距离的离群点检测
基于距离的离群点检测指的是，如果样本空间D中至少有N个样本点与对象O的距离大于dmin,那么称对象O是以{至少N个样本点}和dmin为参数的基于距离的离群点。
其实可以证明，在大多数情况下，如果对象O是根据基于统计的离群点检测方法发现出的离群点，那么肯定存在对应的N和dmin，是它也成为基于距离的离群点。
Eg:假设标准正态分布，如果离均值偏差3或更大的对象认为是离群点，根据正态曲线概率密度函数， P（|x-3|<=dmin）<1-N/总点数，即P（3-dim=<x<=3+dmin）<1-N/总点数，假设dmin=0.13,则该dmin领域表示[2.87,3.13]的范围，假设总点数=10000, N=12.
基于距离的离群点检测的缺点:
要求数据分布均匀，当数据分布非均匀时，基于距离的离群点检测将遇到困难。
3、基于密度的局部离群点检测
什么是局部离群点？
一个对象如果是局部离群点，那么相对于它的局部领域，它是远离的。
不同于前面的方法，基于密度的局部离群点检测不将离群点看做一种二元性质，即不简单用Yes or No来断定一个点是否是离群点，而是用一个权值来评估它的离群度。
它是局部的，意思是该程度依赖于对象相对于其领域的孤立情况。这种方法可以同时检测出全局离群点和局部离群点。
通过基于密度的局部离群点检测就能在样本空间数据分布不均匀的情况下也可以准确发现离群点。
4、基于偏差的离群点检测
基于偏差的离群点检测，它通过检查一组对象的主要特征来识别离群点，“偏差”这种特征的点我们认为是离群点。
通常有两种技术：
第一， 顺序异常技术
第二， 采用OLAP数据立方体技术
三、 基于密度的局部离群点检测
前面介绍了什么叫做基于密度的局部离群点检测，以及它的优势。现在详细介绍下它的一些概念。
1、 对象p的第k距离
对于正整数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的局部空间区域范围，那么对于对象密度较大的区域，k-distance(p)值较小，而对象密度较小的区域，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)为半径的区域内所有对象的集合（不包括P本身）。由于可能同时存在多个第k距离的数据，因此该集合至少包括k个对象。
可以想象，离群度较大的对象Nkdis(p)(p)范围往往比较大，而离群度小的对象Nkdis(p)(p)范围往往比较小。对于同一个类簇中的对象来说，它们涵盖的区域面积大致相当。
3、 对象p相对于对象o的可达距离
可达距离reachdisk(p,o)=max{ k-distance(o),d(p,o)},即k-distance(o)和d(p,o)值较大的那个。
4、 局部可达密度是基于p的k最近邻点的平均可达密度的倒数。如下
可以发现，如果对象p的离群度较小，那么对于同一类簇的数据对象reachdisk(p,o)取k-distance(o)可能性较大，因此它们的Lrdk(p)值波动性较小；而如果对象p的利群度较大，那么reachdisk(p,o)取d(p,o)的可能性较大，对于同一类簇的数据对象，它们的Lrdk(p)值波动性也比较大，并且Lrdk(p)值较小。
5、 局部离群点因子（LOF）
它代表了p为离群点的程度。如果对象p的离群程度较大，则它k领域中大多数是离对象p较远且处于某一个类簇的数据对象，那么这些数据对象的lrd应该是偏大，而对象p本身的lrd是偏小，最后所得的LOF值也是偏大。反之，如果对象p的离群程度较小，对象o的lrd和对象p的lrd相似，最后所得的lof值应该接近1.
四、 算法实现
算法：基于密度的局部离群点检测（lof算法） 输入：样本集合D，正整数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;
