2.2.1 局部异常因子基本原理

LOF方法是基于密度的异常检测方法，用于解决如图2-8所示的多种密度下异常点检测的问题。图中，C_H与C_L分别为高密度与低密度的高质量数据点簇，而且同时存在两个数据样本O₁与O₂。样本O₁接近高密度数据簇C_H。样本O₂接近低密度数据簇C_L。由于样本O₁与O₂所处位置的密度均小于其邻域数据簇的密度，因此被判断为异常点。LOF方法正是通过数据样本及其周围样本的局部密度的相似度，判断数据样本是否为异常点。该方法基于异常数据样本的局部密度远低于其周围样本的局部密度这一前提假设，首先为选中的数据样本划定具有k个近邻的最小集合（第k距离邻域），然后将该集合的半径（第k距离）赋予该集合中每个数据样本，以计算其异常程度的局部密度（局部可达密度），最后通过计算集合中所有数据样本的平均局部密度与选中数据样本的局部密度的比值，即LOF值，判断该数据样本是否异常。LOF值越大，表明该数据样本为异常点的可能性越大。

图2-8 多种密度下的数据特征分布

对于数据样本集D内任意一样本p，其LOF计算的基本流程如下。

（1）通过欧式距离计算样本p与样本o∈D之间的真实距离为d（p，o）。当样本o满足如下条件时：①至少有k个o′∈D且o′≠p，满足d（p，o′）≤d（p，o）；②至多有k-1个o′∈D且o′≠p，满足d（p，o′）＜d（p，o），可得样本p的第k距离d_k（p）=d（p，o）。

（2）查询样本p的第k距离邻域，表示为：

式中，d（p，q）为样本p与样本q之间的真实距离。

（3）计算样本p关于样本o的可达距离：

式中，d_k（o）为样本o的第k距离。如图2-9所示，样本o₁到样本p的第6可达距离为d（p，o₁），样本o₂到样本p的第6可达距离为d₆（o₂）。

图2-9 可达距离示意

（4）计算样本p的局部可达密度为：

即p的第k距离邻域内的所有点到p的平均可达距离的倒数。由式（2-18）可知，平均可达距离越小，样本的局部可达密度越大，说明样本属于同一簇的可能性越大；反之，样本可能是异常点。

（5）计算样本p的局部异常因子：

若LOF_k（p）≈1，说明样本p的局部可达密度与其邻域样本的密度相近，属于同一簇；若LOF_k（p）＜1，说明样本p的局部可达密度高于其邻域样本密度，p为密集点；若LOF_k（p）＞1，说明样本p的局部可达密度小于其邻域样本密度，p为异常点，而且LOF_k（p）越大，样本p的异常程度越大。