PHP局部异常因子算法-Local Outlier Factor(LOF)算法的具体实现解析

这篇文章主要介绍了PHP局部异常因子算法-Local Outlier Factor(LOF)算法的具体实现解析,本文通过案例和文字解析一步步解释了该项技术的实现,以下就是详细内容,需要的朋友可以参考下

这两天在完善自己系统的过程中要实现一个查找异常的功能，于是在朋友的指点下学习并实现了异常点查找的一个基本算法“局部异常因子算法-Local Outlier Factor(LOF)算法”。

首先，找相关说明看看这是个什么东西吧。

大致明白了lof算法是在讲什么，我的理解还有很多不完善的地方，不过还是作为一个初学者写出来供大家批评指正。

根据我的理解大致描述如下：

1、 k-distance，点p的第k距离就是距离点p第k远的那个点的距离，k可以是任意值。在实际生活中可能会这样：小明说“小红家是离我家第五近的，小赵、小钱、小孙、小李家都比她家离我家近”所以此处小红家距离小明家的距离就是小明家k为5时的第k距离。

2、k-distance neighborhood of p，第k距离领域，按照上面的例子就是{小赵、小钱、小孙、小李、小红}，把离p最近的k个点放入一个数组就是第k距离领域了。

3、reach-distance：可达距离。点o到点p的第k可达距离分两种情况，一种是p在o的第k距离领域那个数组中，这时候可达距离等于第k距离，第二种就是p离点o比较远，不在o的第k距离领域中，此时的可达距离即为真实距离。依然使用上述的例子，小赵家在小明家的第k邻域中，所以可达距离就是第k距离，就是小红家的距离，而二狗子家里小明家很远，可达距离就是真实距离了。

4、local reachability density：局部可达密度。点p的局部可达密度是指点p第k距离邻域中所有成员到点p的可达距离的平均值的倒数，有点复杂，不过多读几遍还是蛮好理解的，就不举例子了。

5、local outlier factor：局部离群因子。点p的局部离群因子即为领域中所有点的局部可达密度的平均数比点p的局部可达密度，不做解释。
到这里为止就是我对lof算法的一个大致理解，具体讲解还要看上面我参考的那篇文章，写的很清楚。

如题所示，是一篇Java实现，于是我就在大神的基础上对其进行修改，改成了一个php的版本。因为对迭代器理解的不是很好，所以迭代器实现部分改成了一般函数，有机会再进行完善。

如下：

<?php  	class DataNode {  	private  $nodeName; // 样本点名      private  $dimensioin; // 样本点的维度      private  $kDistance; // k-距离      private  $kNeighbor = array();// k-领域      private $distance; // 到给定点的欧几里得距离      private $reachDensity;// 可达密度      private $reachDis;// 可达距离        private $lof;// 局部离群因子        public function __construct() {  					$num = func_num_args();   //获得参数个数                $args = func_get_args();   //获得参数列表数组                switch($num){                        case 0:                                                              break;                        case 2:                                $this->__call('__construct2', $args);                                break;                }           }  		public function __call($name, $arg) //根据函数名调用函数        {                return call_user_func_array(array($this, $name), $arg);        }		public function __construct2($nodeName, $dimensioin)        {                $this->nodeName = $nodeName;  				$this->dimensioin = $dimensioin;          }      public function getNodeName() {          return $this->nodeName;      }        public function setNodeName($nodeName) {          $this->nodeName = $nodeName;      }        public function getDimensioin() {          return $this->dimensioin;      }        public function setDimensioin($dimensioin) {          $this->dimensioin = $dimensioin;      }        public function getkDistance() {          return $this->kDistance;      }        public function setkDistance($kDistance) {          $this->kDistance = $kDistance;      }        public function getkNeighbor() {          return  $this->kNeighbor;      }        public function setkNeighbor($kNeighbor) {          $this->kNeighbor = $kNeighbor;      }        public function getDistance() {          return $this->distance;      }        public function setDistance($distance) {          $this->distance = $distance;      }        public function getReachDensity() {          return  $this->reachDensity;      }        public function setReachDensity($reachDensity) {          $this->reachDensity = $reachDensity;      }        public function getReachDis() {          return $this->reachDis;      }        public function setReachDis($reachDis) {          $this->reachDis = $reachDis;      }        public function getLof() {          return $this->lof;      }        public function setLof($lof) {          $this->lof = $lof;      }    }     	class OutlierNodeDetect {      private static $INT_K = 5;//正整数K        // 1.找到给定点与其他点的欧几里得距离      // 2.对欧几里得距离进行排序，找到前5位的点，并同时记下k距离      // 3.计算每个点的可达密度      // 4.计算每个点的局部离群点因子      // 5.对每个点的局部离群点因子进行排序，输出。      public function getOutlierNode($allNodes) {          $kdAndKnList =  $this->getKDAndKN($allNodes);          $this->calReachDis($kdAndKnList);           $this->calReachDensity($kdAndKnList);           $this->calLof($kdAndKnList);          //降序排序           $kdAndKnList = $this->rsortArr($kdAndKnList);          return $kdAndKnList;      }        /**      * 计算每个点的局部离群点因子      * @param kdAndKnList      */      private function calLof($kdAndKnList) {           foreach($kdAndKnList as $node):               $tempNodes = $node->getkNeighbor();              $sum = 0.0;               foreach($tempNodes as $tempNode):                  $rd = $this->getRD($tempNode->getNodeName(), $kdAndKnList);                  $sum = $rd / $node->getReachDensity() + $sum;              endforeach;              $sum = $sum / (double) self::$INT_K;              $node->setLof($sum);           endforeach;      }        /**      * 计算每个点的可达距离      * @param kdAndKnList      */      private function calReachDensity($kdAndKnList) {         foreach($kdAndKnList as $node):              $tempNodes = $node->getkNeighbor();              $sum = 0.0;              $rd = 0.0;  			foreach($tempNodes as $tempNode):  			                $sum = $tempNode->getReachDis() + $sum;              endforeach;              $rd = (double) self::$INT_K / $sum;              $node->setReachDensity($rd);          endforeach;      }            /**      * 计算每个点的可达密度,reachdis(p,o)=max{ k-distance(o),d(p,o)}      * @param kdAndKnList      */      private function calReachDis($kdAndKnList) { 		//for (DataNode node : kdAndKnList) {       foreach($kdAndKnList as $node):              $tempNodes = $node->getkNeighbor();              //for (DataNode tempNode : tempNodes) {              foreach($tempNodes as $tempNode):                  //获取tempNode点的k-距离                  $kDis = $this->getKDis($tempNode->getNodeName(), $kdAndKnList); 				                 if ($kDis < $tempNode->getDistance()) {                      $tempNode->setReachDis($tempNode->getDistance());                  } else {                      $tempNode->setReachDis($kDis);                  }              endforeach;          endforeach;      }        /**      * 获取某个点的k-距离（kDistance）      * @param nodeName      * @param nodeList      * @return      */      private function getKDis($nodeName,$nodeList) {          $kDis = 0;          //for (DataNode node : nodeList) {          foreach($nodeList as $node):              if ($this->strcomp(trim($nodeName),trim($node->getNodeName()))) {                  $kDis =$node->getkDistance();                  break;              }          endforeach;          return $kDis;        }  			private	function strcomp($str1,$str2){ 		if($str1 == $str2){ 			return TRUE; 		}else{ 			return FALSE; 		} 	}       /**      * 获取某个点的可达距离      * @param nodeName      * @param nodeList      * @return      */      private function getRD($nodeName, $nodeList) {          $kDis = 0;          //for (DataNode node : nodeList) {          foreach($nodeList as $node):              //if (nodeName.trim().equals(node.getNodeName().trim())) {              if ($this->strcomp(trim($nodeName),trim($node->getNodeName()))) {                  $kDis = $node->getReachDensity();                  break;              }          endforeach;          return $kDis;        }            /**      * 计算给定点NodeA与其他点NodeB的欧几里得距离（distance）,并找到NodeA点的前5位NodeB，然后记录到NodeA的k-领域（kNeighbor）变量。      * 同时找到NodeA的k距离，然后记录到NodeA的k-距离（kDistance）变量中。      * 处理步骤如下：      * 1,计算给定点NodeA与其他点NodeB的欧几里得距离，并记录在NodeB点的distance变量中。      * 2,对所有NodeB点中的distance进行升序排序。      * 3,找到NodeB点的前5位的欧几里得距离点，并记录到到NodeA的kNeighbor变量中。      * 4,找到NodeB点的第5位距离，并记录到NodeA点的kDistance变量中。      * @param allNodes      * @return List<Node>      */      private function getKDAndKN($allNodes) {          $kdAndKnList = array();          for ($i = 0 ; $i <  count($allNodes); $i++) {              $tempNodeList = array();            $nodeA = new DataNode($allNodes[$i]->getNodeName(), $allNodes[$i]->getDimensioin());              //1,找到给定点NodeA与其他点NodeB的欧几里得距离，并记录在NodeB点的distance变量中。              for ($j = 0; $j < count($allNodes); $j++) {                  $nodeB = new DataNode($allNodes[$j]->getNodeName(), $allNodes[$j]->getDimensioin());                  //计算NodeA与NodeB的欧几里得距离(distance)                  $tempDis = $this->getDis($nodeA, $nodeB);                  $nodeB->setDistance($tempDis);				array_push($tempNodeList,$nodeB);				                //$tempNodeList.add(nodeB);              }              //2,对所有NodeB点中的欧几里得距离（distance）进行升序排序。			$tempNodeList = $this->sortArr($tempNodeList);  															$neighArr = array();            for ($k = 1; $k <= self::$INT_K; $k++) {                  //3,找到NodeB点的前5位的欧几里得距离点，并记录到到NodeA的kNeighbor变量中。 				array_push(	$neighArr ,$tempNodeList[$k]);						                if ($k == self::$INT_K - 1) {                      //4,找到NodeB点的第5位距离，并记录到NodeA点的kDistance变量中。                      $nodeA->setkDistance($tempNodeList[$k]->getDistance());                }              }  						$nodeA->setkNeighbor($neighArr);            array_push($kdAndKnList,$nodeA);          }  		        return $kdAndKnList;      }            /**      * 计算给定点A与其他点B之间的欧几里得距离。      * 欧氏距离的公式：      * d=sqrt( ∑(xi1-xi2)^2 ) 这里i=1,2..n      * xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标      * n维欧氏空间是一个点集,它的每个点可以表示为(x(1),x(2),...x(n)),      * 其中x(i)(i=1,2...n)是实数,称为x的第i个坐标,两个点x和y=(y(1),y(2)...y(n))之间的距离d(x,y)定义为上面的公式.      * @param A      * @param B      * @return      */      private function getDis($A, $B) {          $dis = 0.0;          $dimA = $A->getDimensioin();          $dimB = $B->getDimensioin();          if (count($dimA) == count($dimB)) {              for ($i = 0; $i < count($dimA); $i++) {                  $temp = pow($dimA[$i] - $dimB[$i], 2);                  $dis = $dis + $temp;              }              $dis = pow($dis, 0.5);          }          return $dis;      }  		    //Distance比较    private function compareAandB($arr,$A, $B) {          if(($arr[$A]->getDistance()-$arr[$B]->getDistance())<0)                     return -1;                else if(($arr[$A]->getDistance()-$arr[$B]->getDistance())>0)                    return 1;                else return 0;       }        //lof比较    private function compareAandBLof($arr,$A, $B) { 			        if(($arr[$A]->getLof()-$arr[$B]->getLof())<0)                     return -1;                else if(($arr[$A]->getLof()-$arr[$B]->getLof())>0)                    return 1;                else return 0;       }        private function changeAandB($arr,$A, $B) {          $tempChange =  $arr[$A]; 		$arr[$A] = $arr[$B];		$arr[$B] = $tempChange;		return $arr;    }    //Distance升序    private function sortArr($arr) { 		for($i = 0;$i < count($arr);$i ++){			for($j = $i + 1;$j < count($arr);$j ++){				if($this->compareAandB($arr,$i, $j)>0){					$arr=$this->changeAandB($arr,$i, $j);				}			}		}		return $arr;    }    //lof降序    private function rsortArr($arr) { 		for($i = 0;$i < count($arr);$i ++){			for($j = $i + 1;$j < count($arr);$j ++){				if($this->compareAandBLof($arr,$i, $j)<0){					$arr=$this->changeAandB($arr,$i, $j);										}			}		}		return $arr;    }         public static function main() {                       $dpoints = array();            $a = array( 2, 3 );          $b = array( 2, 4 );          $c = array( 1, 4 );          $d = array( 1, 3 );          $e = array( 2, 2 );          $f = array( 3, 2 );            $g = array( 8, 7 );          $h = array( 8, 6 );          $i = array( 7, 7 );          $j = array( 7, 6 );          $k = array( 8, 5 );            $l = array( 100, 2 );// 孤立点            $m = array( 8, 20 );          $n = array( 8, 19 );          $o = array( 7, 18 );          $p = array( 7, 17 );          $yichen = array( 8, 21 );           array_push($dpoints,new DataNode("a", $a));          array_push($dpoints,new DataNode("b", $b));          array_push($dpoints,new DataNode("c", $c));          array_push($dpoints,new DataNode("d", $d));          array_push($dpoints,new DataNode("e", $e));          array_push($dpoints,new DataNode("f", $f));            array_push($dpoints,new DataNode("g", $g));          array_push($dpoints,new DataNode("h", $h));          array_push($dpoints,new DataNode("i", $i));          array_push($dpoints,new DataNode("j", $j));          array_push($dpoints,new DataNode("k", $k));            array_push($dpoints,new DataNode("l", $l));            array_push($dpoints,new DataNode("m", $m));          array_push($dpoints,new DataNode("n", $n));          array_push($dpoints,new DataNode("o", $o));          array_push($dpoints,new DataNode("p", $p));          array_push($dpoints,new DataNode("yichen", $yichen));            $lof = new OutlierNodeDetect();            $nodeList = $lof->getOutlierNode($dpoints);		 		foreach($nodeList as $node):              echo($node->getNodeName() . "--" . round($node->getLof(),4));		  echo("<br>");        endforeach;                 }  } OutlierNodeDetect::main(); ?>

到此这篇关于PHP局部异常因子算法-Local Outlier Factor(LOF)算法的具体实现解析的文章就介绍到这了。