加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

LOF局部离群点算法原理及scala实现

(2020-06-13 11:03:21)
标签：

lof

杂谈

 分类： 大数据处理
本文参考:

       在数据挖掘方面，经常需要在做特征工程和模型训练之前对数据进行清洗，剔除无效数据和异常数据。异常检测也是数据挖掘的一个方向，用于反作弊、伪基站、金融诈骗等领域。
　　异常检测方法，针对不同的数据形式，有不同的实现方法。常用的有基于分布的方法，在上、下α分位点之外的值认为是异常值（例如图1），对于属性值常用此类方法。基于距离的方法，适用于二维或高维坐标体系内异常点的判别，例如二维平面坐标或经纬度空间坐标下异常点识别，可用此类方法。
LOF局部离群点算法原理及scala实现
　    这次要介绍一下一种基于距离的异常检测算法，局部异常因子LOF算法（Local Outlier Factor）。
　　用视觉直观的感受一下，如图2，对于C1集合的点，整体间距，密度，分散情况较为均匀一致，可以认为是同一簇；对于C2集合的点，同样可认为是一簇。o1、o2点相对孤立，可以认为是异常点或离散点。现在的问题是，如何实现算法的通用性，可以满足C1和C2这种密度分散情况迥异的集合的异常点识别。LOF可以实现我们的目标。
LOF局部离群点算法原理及scala实现

     LOF算法的相关定义：
1、 d(p,o)：两点p和o之间的距离

2、k-distance：第k距离
比如下面，距离p第5远的点有2个在圆上
LOF局部离群点算法原理及scala实现

3、k-distance neighborhood of p： 第k距离领域
点p的第k距离邻域Nk(p)，就是p的第k距离即以内的所有点，包括第k距离。因此p的第k邻域点的个数LOF局部离群点算法原理及scala实现

4、reach-distance：可达距离
LOF局部离群点算法原理及scala实现
这意味着，点o到点p的第k可达距离，至少是o的第k距离，或者为o、p间的真实距离。
这也意味着，离点o最近的k个点，o到它们的可达距离被认为相等，且都等于LOF局部离群点算法原理及scala实现
LOF局部离群点算法原理及scala实现

5、local reachability density：局部可达密度
LOF局部离群点算法原理及scala实现

表示点p的第k领域内点到p的平均可达距离的倒数。
注意，是p的邻域点Nk(p)Nk(p)到p的可达距离，不是p到Nk(p)Nk(p)的可达距离，一定要弄清楚关系。并且，如果有重复点，那么分母的可达距离之和有可能为0，则会导致lrd变为无限大，下面还会继续提到这一点。
　　这个值的含义可以这样理解，首先这代表一个密度，密度越高，我们认为越可能属于同一簇，密度越低，越可能是离群点。如果p和周围邻域点是同一簇，那么可达距离越可能为较小的dk(o)dk(o)，导致可达距离之和较小，密度值较高；如果p和周围邻居点较远，那么可达距离可能都会取较大值d(p,o)d(p,o)，导致密度较小，越可能是离群点

6、local outlier factor：局部离群因子
LOF局部离群点算法原理及scala实现
表示点p的邻域点Nk(p)Nk(p)的局部可达密度与点p的局部可达密度之比的平均数。
　　　　如果这个比值越接近1，说明p的其邻域点密度差不多，p可能和邻域同属一簇；如果这个比值越小于1，说明p的密度高于其邻域点密度，p为密集点；如果这个比值越大于1，说明p的密度小于其邻域点密度，p越可能是异常点。
　　现在概念定义已经介绍完了，现在再回过头来看一下lof的思想，主要是通过比较每个点p和其邻域点的密度来判断该点是否为异常点，如果点p的密度越低，越可能被认定是异常点。至于密度，是通过点之间的距离来计算的，点之间距离越远，密度越低，距离越近，密度越高，完全符合我们的理解。而且，因为lof对密度的是通过点的第k邻域来计算，而不是全局计算，因此得名为“局部”异常因子，这样，对于图1的两种数据集C1和C2，lof完全可以正确处理，而不会因为数据密度分散情况不同而错误的将正常点判定为异常点。

7、scala实现

// LOF的数据节点
class LOFDataNode(inputDataName: String, inputDataVector: ArrayList[Int]) {
  var nodeName = inputDataName // 样本点名称
  var dataVector = inputDataVector // 样本点的数据向量

  var kDistance = 0.0 // k-距离
  var kNeighbor = new ArrayList[LOFDataNode]() // k-领域
  var distance = 0.0 // 到给定点的欧几里得距离
  var reachDensity = 0.0 // 可达密度
  var reachDistance = 0.0 // 可达距离
  var lof = 0.0 // 局部离群因子

  def getNodeName(): String = {
    this.nodeName
  }

  def getDataVector(): ArrayList[Int] = {
    this.dataVector
  }

  def setKDistance(kDistance: Double) = {
    this.kDistance = kDistance
  }

  def getKDistance(): Double = {
    this.kDistance
  }

  def setKNeighbor(kNeighbor: ArrayList[LOFDataNode])= {
    this.kNeighbor = kNeighbor
  }

  def getKNeightbor(): ArrayList[LOFDataNode] = {
    this.kNeighbor
  }

  def setDistance(distance: Double) = {
    this.distance = distance
  }

  def getDistance(): Double = {
    this.distance
  }

  def setReachDensity(reachDensity: Double) = {
    this.reachDensity = reachDensity
  }

  def getReachDensity(): Double = {
    this.reachDensity
  }

  def setReachDistance(reachDistance: Double) = {
    this.reachDistance = reachDistance
  }

  def getReachDistance(): Double = {
    this.reachDistance
  }

  def setLof(lof: Double) = {
    this.lof = lof
  }

  def getLof(): Double = {
    this.lof
  }

}

// Factor局部离群点检测算法
class LOFDetect {

  // 获取离群点功能的主逻辑
   // 注意1：输入的值DataVector值不能重复
   // 1.找到给定点与其他点的欧几里得距离
   // 2.对欧几里得距离进行排序，找到前k位的点，并同时记下k距离
   // 3.计算每个点的可达密度
   // 4.计算每个点的局部离群点因子
   // 5.对每个点的局部离群点因子进行排序，输出
  def getOutlierNode(allNodes: ArrayList[LOFDataNode], k: Int): ArrayList[LOFDataNode] = {
    val kdAndKnList = getKDistanceAndKNeighbor(allNodes, k)
    calcReachDistance(kdAndKnList)
    calcReachDensity(kdAndKnList, k)
    calcLof(kdAndKnList, k)

    // 降序排列
    val lofComparator = new Ordering[LOFDataNode]{
      override def compare(x: LOFDataNode, y: LOFDataNode): Int = {
        val distDiff = x.getLof() - y.getLof()
        if(distDiff < 0){
          1
        }else if(distDiff > 0){
          -1
        }else{
          0
        }
      }
    }
    kdAndKnList.sort(lofComparator)

    kdAndKnList
  }

  // 计算每个点的局部离群点因子
  def calcLof(kdAndKnList: ArrayList[LOFDataNode], k: Int) = {
    for(i <- 0 until kdAndKnList.size){
      val tempNodes = kdAndKnList.get(i).getKNeightbor()
      var sum = 0.0

      for(j <- 0 until tempNodes.size){
        val rd = getReachDensity(tempNodes.get(j).getNodeName(), kdAndKnList)
        sum += DecimalCalculator.div(rd, kdAndKnList.get(i).getReachDensity(), 10)
      }
      sum = DecimalCalculator.div(sum, k, 10)
      kdAndKnList.get(i).setLof(sum)
    }
  }

  // 获取某个点的可达密度
  def getReachDensity(nodeName: String, nodeList: ArrayList[LOFDataNode]): Double = {
    var kDis = 0.0

    breakable({
      for(i <- 0 until nodeList.size()){
        if(nodeName.trim() == nodeList.get(i).getNodeName().trim()){
          kDis = nodeList.get(i).getReachDensity()
          break
        }
      }
    })

    kDis
  }

  //  计算每个点的可达密度
  def calcReachDensity(kdAndKnList: ArrayList[LOFDataNode], k: Int) = {
    for(i <- 0 until kdAndKnList.size){
      val tempNodes = kdAndKnList.get(i).getKNeightbor()
      var sum = 0.0
      for(j <- 0 until tempNodes.size){
        sum += tempNodes.get(j).getReachDistance()
      }
      val rd = DecimalCalculator.div(k, sum, 10)
      kdAndKnList.get(i).setReachDensity(rd)
    }
  }

  // 计算每个点的可达密度,reachdis(p,o)=max{ k-distance(o),d(p,o)}
  def calcReachDistance(kdAndKnList: ArrayList[LOFDataNode])= {
    for(i <- 0 until kdAndKnList.size){

      val tempNodes = kdAndKnList.get(i).getKNeightbor()
      for(j <- 0 until tempNodes.size){
        val kDis = getKDistance(tempNodes.get(j).getNodeName(), kdAndKnList)

        if(kDis < tempNodes.get(j).getDistance()){
          tempNodes.get(j).setReachDistance(tempNodes.get(j).getDistance())
        }else{
          tempNodes.get(j).setReachDensity(kDis)
        }
      }
    }
  }

  //  获取某个点的k-距离
  def getKDistance(nodeName: String, nodeList: ArrayList[LOFDataNode]): Double = {
    var kDis = 0.0

    breakable({
      for(i <- 0 until nodeList.size()){
        if(nodeName.trim() == nodeList.get(i).getNodeName().trim()){
          kDis = nodeList.get(i).getKDistance()
          break()
        }
      }
    })

    kDis
  }

  // 计算给定点NodeA与其他点NodeB的欧几里得距离（distance）,并找到NodeA点的前5位NodeB，然后记录到NodeA的k-领域（kNeighbor）变量。同时找到NodeA的k距离，然后记录到NodeA的k-距离（kDistance）变量中。
  def getKDistanceAndKNeighbor(allNodes: ArrayList[LOFDataNode], k: Int): ArrayList[LOFDataNode] = {
    val kdAndKnList = new ArrayList[LOFDataNode]()

    for(i <- 0 until allNodes.size){
      val tempNodeList = new ArrayList[LOFDataNode]()
      val nodeA = new LOFDataNode(allNodes.get(i).getNodeName(), allNodes.get(i).getDataVector())

      // 找到给定点NodeA与其他NodeB的欧几里得距离，并记录在NodeB的distance变量中
      for(j <- 0 until allNodes.size){
        val nodeB = new LOFDataNode(allNodes.get(j).getNodeName(), allNodes.get(j).getDataVector())
        if(nodeB.getNodeName().trim() != nodeA.getNodeName().trim()){
          val distance = getDistance(nodeA, nodeB)
          nodeB.setDistance(distance)
          tempNodeList.add(nodeB)
        }
      }

      // 对所有NodeB点中的欧几里得距离进行升序排序
      val distComparator = new Ordering[LOFDataNode]{
        override def compare(x: LOFDataNode, y: LOFDataNode): Int = {
          val distDiff = x.getDistance() - y.getDistance()
          if(distDiff < 0){
            -1
          }else if(distDiff > 0){
            1
          }else{
            0
          }
        }
      }
      tempNodeList.sort(distComparator)

      // 找到NodeB中前k位的欧几里得距离点，并记录到NodeA的Neighbor变量中
      for(i <- 0 until k){
        nodeA.getKNeightbor().add(tempNodeList.get(i))
        if(i == k - 1){
          nodeA.setDistance(tempNodeList.get(i).getDistance())
        }
      }

      kdAndKnList.add(nodeA)
    }

    kdAndKnList
  }

 
  //  获取两个节点的欧几里得距离
  def getDistance(nodeA: LOFDataNode, nodeB: LOFDataNode): Double = {
    var distance = 0.0
    val nodeADataVector = nodeA.getDataVector()
    val nodeBDataVector = nodeB.getDataVector()

    if(nodeADataVector.size == nodeBDataVector.size){
      for(i <- 0 until nodeADataVector.size){
        distance += Math.pow(nodeADataVector.get(i) - nodeBDataVector.get(i), 2)
      }
      distance = Math.pow(distance, 0.5)
    }

    distance
  }

}

喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有