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

作者在 2022-04-06 11:10:15 发布以下内容

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

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

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

我参考了这一篇文章: 异常点/离群点检测算法——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算法的一个大致理解,具体讲解还要看上面我参考的那篇文章,写的很清楚。

接下来我找了网上的一篇对此算法的实现,很遗憾没有php版本,于是我就找到了这篇文章:基于密度的局部离群点检测(lof算法) (Java 实现)

如题所示,是一篇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)算法的具体实现解析的文章就介绍到这了。

默认分类 | 阅读 941 次
文章评论,共0条
游客请输入验证码
浏览7087次
文章分类
文章归档
最新评论