C#代码实现LOF局部异常因子算法

---

1、简介

在数据挖掘方面，经常需要在做特征工程和模型训练之前对数据进行清洗，剔除无效数据和异常数据。异常检测也是数据挖掘的一个方向，用于反作弊、伪基站、金融诈骗等领域。
　　异常检测方法，针对不同的数据形式，有不同的实现方法。常用的有基于分布的方法，在上、下α分位点之外的值认为是异常值，对于属性值常用此类方法。基于距离的方法，适用于二维或高维坐标体系内异常点的判别，例如二维平面坐标或经纬度空间坐标下异常点识别，可用此类方法。
这次要介绍一下一种基于距离的异常检测算法，局部异常因子LOF算法（Local Outlier Factor），其在中等高维数据集上执行异常值检测的另一种比较有效的算法。

2、算法定义

LOF算法（Local Outlier Factor，局部离群因子检测方法），是一种无监督的离群检测方法，是基于密度的离群点检测方法中一个比较有代表性的算法。该算法会给数据集中的每个点计算一个离群因子LOF，通过判断LOF是否接近于1来判定是否是离群因子。若LOF远大于1，则认为是离群因子，接近于1，则是正常点。

3、算法思想

LOF通过计算一个数值score来反映一个样本的异常程度。这个数值的大致意思是：一个样本点周围的样本点所处位置的平均密度比上该样本点所在位置的密度。比值越大于1，则该点所在位置的密度越小于其周围样本所在位置的密度，这个点就越有可能是异常点。关于密度等理论概念，详见下面介绍。
　　用视觉直观的感受一下下图，对于C1集合的点，整体间距，密度，分散情况较为均匀一致，可以认为是同一簇；对于C2集合的点，同样可认为是一簇。o1、o2点相对孤立，可以认为是异常点或离散点。现在的问题是，如何实现算法的通用性，可以满足C1和C2这种密度分散情况迥异的集合的异常点识别。LOF可以实现我们的目标。

4、C#完整代码实现LOF：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace text
{public class LOFPoint{public int Index { get; set; }public double[] Coordinates { get; set; }public double KDistance { get; set; }//第K距离public List<double> ReachabilityDistance { get; set; }//可达距离public double LocalReachabilityDensity { get; set; }//LRDpublic double LOF { get; set; }}public class LocalOutlierFactor{/// <summary>/// 数据和K个相邻点/// </summary>/// <param name="points"></param>/// <param name="k"></param>public static void ComputeLOF(List<LOFPoint> points, int k){//1、计算每一个点到全部点的距离var distances = ComputeDistances(points);//2、获取到距离最近的K个点var knn = FindKNearestNeighbors(distances, k);//3、计算第K距离foreach (var point in points){var neighbors = knn[point.Index];double maxDistance = 0;foreach (int neighborIndex in neighbors){double distance = distances[point.Index, neighborIndex];if (distance > maxDistance)maxDistance = distance;}point.KDistance = maxDistance;//每个点的第K距离}//4、计算点到K个最近点的可达距离foreach (var point in points){var neighbors = knn[point.Index];List<double> rds = new List<double>();//到K个邻近点的可达距离foreach (int neighborIndex in neighbors){double distance = distances[point.Index, neighborIndex];if (distance > point.KDistance)rds.Add(distance);elserds.Add(point.KDistance);}point.ReachabilityDistance = rds;}//5、计算局部可达密度LRDforeach (var point in points){double sumOfReachabilityDistances = 0;var neighbors = knn[point.Index];for (int i = 0; i < k; i++){sumOfReachabilityDistances += point.ReachabilityDistance[i];}point.LocalReachabilityDensity = neighbors.Count / sumOfReachabilityDistances;}//6、计算局部离群因子LOFforeach (var point in points){double sumOfLOFs = 0;var neighbors = knn[point.Index];foreach (int neighborIndex in neighbors){sumOfLOFs += points[neighborIndex].LocalReachabilityDensity;}point.LOF = sumOfLOFs / (neighbors.Count * point.LocalReachabilityDensity);}}/// <summary>/// 计算距离/// </summary>/// <param name="points"></param>/// <returns></returns>static double[,] ComputeDistances(List<LOFPoint> points){double[,] distances = new double[points.Count, points.Count];for (int i = 0; i < points.Count; i++){for (int j = i + 1; j < points.Count; j++){double distance = EuclideanDistance(points[i].Coordinates, points[j].Coordinates);distances[i, j] = distances[j, i] = distance;}}return distances;}/// <summary>/// 寻找邻居点/// </summary>/// <param name="distances"></param>/// <param name="k"></param>/// <returns></returns>static List<int>[] FindKNearestNeighbors(double[,] distances, int k){List<int>[] knn = new List<int>[distances.GetLength(0)];for (int i = 0; i < distances.GetLength(0); i++){knn[i] = Enumerable.Range(0, distances.GetLength(0)).Select(j => new { Index = j, Distance = distances[i, j] }).Where(x => x.Distance != 0).OrderBy(x => x.Distance).Take(k).Select(x => x.Index).ToList();}return knn;}/// <summary>/// 计算两点距离/// </summary>/// <param name="x"></param>/// <param name="y"></param>/// <returns></returns>static double EuclideanDistance(double[] x, double[] y){double sumSquaredDifferences = 0;for (int i = 0; i < x.Length; i++){double diff = x[i] - y[i];sumSquaredDifferences += diff * diff;}return Math.Sqrt(sumSquaredDifferences);}}
}