• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
123456833 显示全部楼层 发表于 2021-8-14 15:13:18 |阅读模式 打印 上一主题 下一主题
这两天在美满本身材系的过程中要实现一个查找非常的功能,于是在朋侪的指点放学习并实现了非常点查找的一个根本算法“局部非常因子算法-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的版本。由于对迭代器理解的不是很好,以是迭代器实现部分改成了一样平常函数,有时机再举行美满。
如下:
  1. <?php
  2.         class DataNode {  
  3.         private  $nodeName; // 样本点名  
  4.     private  $dimensioin; // 样本点的维度  
  5.     private  $kDistance; // k-距离  
  6.     private  $kNeighbor = array();// k-领域  
  7.     private $distance; // 到给定点的欧几里得距离  
  8.     private $reachDensity;// 可达密度  
  9.     private $reachDis;// 可达距离  
  10.   
  11.     private $lof;// 局部离群因子  
  12.   
  13.     public function __construct() {  
  14.        
  15.                                 $num = func_num_args();   //获得参数个数
  16.                 $args = func_get_args();   //获得参数列表数组
  17.                 switch($num){
  18.                         case 0:
  19.                               
  20.                                 break;
  21.                         case 2:
  22.                                 $this->__call('__construct2', $args);
  23.                                 break;
  24.                 }
  25.       
  26.     }  
  27.        
  28.          public function __call($name, $arg) //根据函数名调用函数
  29.         {
  30.                 return call_user_func_array(array($this, $name), $arg);
  31.         }
  32.        
  33.          public function __construct2($nodeName, $dimensioin)
  34.         {
  35.                 $this->nodeName = $nodeName;  
  36.                                 $this->dimensioin = $dimensioin;  
  37.         }
  38.   
  39.     public function getNodeName() {  
  40.         return $this->nodeName;  
  41.     }  
  42.   
  43.     public function setNodeName($nodeName) {  
  44.         $this->nodeName = $nodeName;  
  45.     }  
  46.   
  47.     public function getDimensioin() {  
  48.         return $this->dimensioin;  
  49.     }  
  50.   
  51.     public function setDimensioin($dimensioin) {  
  52.         $this->dimensioin = $dimensioin;  
  53.     }  
  54.   
  55.     public function getkDistance() {  
  56.         return $this->kDistance;  
  57.     }  
  58.   
  59.     public function setkDistance($kDistance) {  
  60.         $this->kDistance = $kDistance;  
  61.     }  
  62.   
  63.     public function getkNeighbor() {  
  64.         return  $this->kNeighbor;  
  65.     }  
  66.   
  67.     public function setkNeighbor($kNeighbor) {  
  68.         $this->kNeighbor = $kNeighbor;  
  69.     }  
  70.   
  71.     public function getDistance() {  
  72.         return $this->distance;  
  73.     }  
  74.   
  75.     public function setDistance($distance) {  
  76.         $this->distance = $distance;  
  77.     }  
  78.   
  79.     public function getReachDensity() {  
  80.         return  $this->reachDensity;  
  81.     }  
  82.   
  83.     public function setReachDensity($reachDensity) {  
  84.         $this->reachDensity = $reachDensity;  
  85.     }  
  86.   
  87.     public function getReachDis() {  
  88.         return $this->reachDis;  
  89.     }  
  90.   
  91.     public function setReachDis($reachDis) {  
  92.         $this->reachDis = $reachDis;  
  93.     }  
  94.   
  95.     public function getLof() {  
  96.         return $this->lof;  
  97.     }  
  98.   
  99.     public function setLof($lof) {  
  100.         $this->lof = $lof;  
  101.     }  
  102.   
  103. }
  104.         class OutlierNodeDetect {  
  105.     private static $INT_K = 5;//正整数K  
  106.   
  107.     // 1.找到给定点与其他点的欧几里得距离  
  108.     // 2.对欧几里得距离进行排序,找到前5位的点,并同时记下k距离  
  109.     // 3.计算每个点的可达密度  
  110.     // 4.计算每个点的局部离群点因子  
  111.     // 5.对每个点的局部离群点因子进行排序,输出。  
  112.     public function getOutlierNode($allNodes) {  
  113.         $kdAndKnList =  $this->getKDAndKN($allNodes);
  114.          $this->calReachDis($kdAndKnList);  
  115.          $this->calReachDensity($kdAndKnList);  
  116.          $this->calLof($kdAndKnList);  
  117.         //降序排序  
  118.          $kdAndKnList = $this->rsortArr($kdAndKnList);
  119.   
  120.         return $kdAndKnList;  
  121.     }  
  122.   
  123.     /**
  124.      * 计算每个点的局部离群点因子
  125.      * @param kdAndKnList
  126.      */  
  127.     private function calLof($kdAndKnList) {  
  128.          foreach($kdAndKnList as $node):   
  129.             $tempNodes = $node->getkNeighbor();  
  130.             $sum = 0.0;   
  131.             foreach($tempNodes as $tempNode):  
  132.                 $rd = $this->getRD($tempNode->getNodeName(), $kdAndKnList);  
  133.                 $sum = $rd / $node->getReachDensity() + $sum;  
  134.             endforeach;  
  135.             $sum = $sum / (double) self::$INT_K;  
  136.             $node->setLof($sum);  
  137.          endforeach;  
  138.     }  
  139.   
  140.     /**
  141.      * 计算每个点的可达距离
  142.      * @param kdAndKnList
  143.      */  
  144.     private function calReachDensity($kdAndKnList) {
  145.         foreach($kdAndKnList as $node):  
  146.             $tempNodes = $node->getkNeighbor();  
  147.             $sum = 0.0;  
  148.             $rd = 0.0;  
  149.                         foreach($tempNodes as $tempNode):                         
  150.                 $sum = $tempNode->getReachDis() + $sum;  
  151.             endforeach;  
  152.             $rd = (double) self::$INT_K / $sum;  
  153.             $node->setReachDensity($rd);  
  154.         endforeach;  
  155.     }  
  156.       
  157.     /**
  158.      * 计算每个点的可达密度,reachdis(p,o)=max{ k-distance(o),d(p,o)}
  159.      * @param kdAndKnList
  160.      */  
  161.     private function calReachDis($kdAndKnList) {
  162.                 //for (DataNode node : kdAndKnList) {
  163.        foreach($kdAndKnList as $node):  
  164.             $tempNodes = $node->getkNeighbor();  
  165.             //for (DataNode tempNode : tempNodes) {  
  166.             foreach($tempNodes as $tempNode):  
  167.                 //获取tempNode点的k-距离  
  168.                 $kDis = $this->getKDis($tempNode->getNodeName(), $kdAndKnList);
  169.                                  
  170.                 if ($kDis < $tempNode->getDistance()) {  
  171.                     $tempNode->setReachDis($tempNode->getDistance());  
  172.                 } else {  
  173.                     $tempNode->setReachDis($kDis);  
  174.                 }  
  175.             endforeach;  
  176.         endforeach;  
  177.     }  
  178.   
  179.     /**
  180.      * 获取某个点的k-距离(kDistance)
  181.      * @param nodeName
  182.      * @param nodeList
  183.      * @return
  184.      */  
  185.     private function getKDis($nodeName,$nodeList) {  
  186.         $kDis = 0;  
  187.         //for (DataNode node : nodeList) {  
  188.         foreach($nodeList as $node):  
  189.             if ($this->strcomp(trim($nodeName),trim($node->getNodeName()))) {  
  190.                 $kDis =$node->getkDistance();  
  191.                 break;  
  192.             }  
  193.         endforeach;  
  194.         return $kDis;  
  195.   
  196.     }  
  197.        
  198.        
  199.         private        function strcomp($str1,$str2){
  200.                 if($str1 == $str2){
  201.                         return TRUE;
  202.                 }else{
  203.                         return FALSE;
  204.                 }
  205.         }
  206.   
  207.     /**
  208.      * 获取某个点的可达距离
  209.      * @param nodeName
  210.      * @param nodeList
  211.      * @return
  212.      */  
  213.     private function getRD($nodeName, $nodeList) {  
  214.         $kDis = 0;  
  215.         //for (DataNode node : nodeList) {  
  216.         foreach($nodeList as $node):  
  217.             //if (nodeName.trim().equals(node.getNodeName().trim())) {  
  218.             if ($this->strcomp(trim($nodeName),trim($node->getNodeName()))) {  
  219.                 $kDis = $node->getReachDensity();  
  220.                 break;  
  221.             }  
  222.         endforeach;  
  223.         return $kDis;  
  224.   
  225.     }  
  226.       
  227.     /**
  228.      * 计算给定点NodeA与其他点NodeB的欧几里得距离(distance),并找到NodeA点的前5位NodeB,然后记录到NodeA的k-领域(kNeighbor)变量。
  229.      * 同时找到NodeA的k距离,然后记录到NodeA的k-距离(kDistance)变量中。
  230.      * 处理步骤如下:
  231.      * 1,计算给定点NodeA与其他点NodeB的欧几里得距离,并记录在NodeB点的distance变量中。
  232.      * 2,对所有NodeB点中的distance进行升序排序。
  233.      * 3,找到NodeB点的前5位的欧几里得距离点,并记录到到NodeA的kNeighbor变量中。
  234.      * 4,找到NodeB点的第5位距离,并记录到NodeA点的kDistance变量中。
  235.      * @param allNodes
  236.      * @return List<Node>
  237.      */  
  238.     private function getKDAndKN($allNodes) {  
  239.         $kdAndKnList = array();  
  240.         for ($i = 0 ; $i <  count($allNodes); $i++) {  
  241.             $tempNodeList = array();
  242.             $nodeA = new DataNode($allNodes[$i]->getNodeName(), $allNodes[$i]->getDimensioin());  
  243.             //1,找到给定点NodeA与其他点NodeB的欧几里得距离,并记录在NodeB点的distance变量中。  
  244.             for ($j = 0; $j < count($allNodes); $j++) {  
  245.                 $nodeB = new DataNode($allNodes[$j]->getNodeName(), $allNodes[$j]->getDimensioin());  
  246.                 //计算NodeA与NodeB的欧几里得距离(distance)  
  247.                 $tempDis = $this->getDis($nodeA, $nodeB);  
  248.                 $nodeB->setDistance($tempDis);
  249.                                 array_push($tempNodeList,$nodeB);                               
  250.                 //$tempNodeList.add(nodeB);  
  251.             }  
  252.             //2,对所有NodeB点中的欧几里得距离(distance)进行升序排序。
  253.                         $tempNodeList = $this->sortArr($tempNodeList);                         
  254.                                
  255.                                        
  256.                         $neighArr = array();
  257.             for ($k = 1; $k <= self::$INT_K; $k++) {  
  258.                 //3,找到NodeB点的前5位的欧几里得距离点,并记录到到NodeA的kNeighbor变量中。
  259.                                 array_push(        $neighArr ,$tempNodeList[$k]);       
  260.                                        
  261.                 if ($k == self::$INT_K - 1) {  
  262.                     //4,找到NodeB点的第5位距离,并记录到NodeA点的kDistance变量中。  
  263.                     $nodeA->setkDistance($tempNodeList[$k]->getDistance());
  264.                 }  
  265.             }  
  266.                        
  267.                         $nodeA->setkNeighbor($neighArr);
  268.             array_push($kdAndKnList,$nodeA);  
  269.         }  
  270.                
  271.         return $kdAndKnList;  
  272.     }  
  273.       
  274.     /**
  275.      * 计算给定点A与其他点B之间的欧几里得距离。
  276.      * 欧氏距离的公式:
  277.      * d=sqrt( ∑(xi1-xi2)^2 ) 这里i=1,2..n
  278.      * xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标
  279.      * n维欧氏空间是一个点集,它的每个点可以表示为(x(1),x(2),...x(n)),
  280.      * 其中x(i)(i=1,2...n)是实数,称为x的第i个坐标,两个点x和y=(y(1),y(2)...y(n))之间的距离d(x,y)定义为上面的公式.
  281.      * @param A
  282.      * @param B
  283.      * @return
  284.      */  
  285.     private function getDis($A, $B) {  
  286.         $dis = 0.0;  
  287.         $dimA = $A->getDimensioin();  
  288.         $dimB = $B->getDimensioin();  
  289.         if (count($dimA) == count($dimB)) {  
  290.             for ($i = 0; $i < count($dimA); $i++) {  
  291.                 $temp = pow($dimA[$i] - $dimB[$i], 2);  
  292.                 $dis = $dis + $temp;  
  293.             }  
  294.             $dis = pow($dis, 0.5);  
  295.         }  
  296.         return $dis;  
  297.     }  
  298.        
  299.        
  300.     //Distance比较
  301.     private function compareAandB($arr,$A, $B) {  
  302.         if(($arr[$A]->getDistance()-$arr[$B]->getDistance())<0)     
  303.                 return -1;   
  304.             else if(($arr[$A]->getDistance()-$arr[$B]->getDistance())>0)   
  305.                 return 1;   
  306.             else return 0;   
  307.     }  
  308.   
  309.     //lof比较
  310.     private function compareAandBLof($arr,$A, $B) {
  311.                        
  312.         if(($arr[$A]->getLof()-$arr[$B]->getLof())<0)     
  313.                 return -1;   
  314.             else if(($arr[$A]->getLof()-$arr[$B]->getLof())>0)   
  315.                 return 1;   
  316.             else return 0;   
  317.     }  
  318.   
  319.     private function changeAandB($arr,$A, $B) {  
  320.         $tempChange =  $arr[$A];
  321.                 $arr[$A] = $arr[$B];
  322.                 $arr[$B] = $tempChange;
  323.                 return $arr;
  324.     }  
  325.   //Distance升序
  326.     private function sortArr($arr) {
  327.                 for($i = 0;$i < count($arr);$i ++){
  328.                         for($j = $i + 1;$j < count($arr);$j ++){
  329.                                 if($this->compareAandB($arr,$i, $j)>0){
  330.                                         $arr=$this->changeAandB($arr,$i, $j);
  331.                                 }
  332.                         }
  333.                 }
  334.                 return $arr;
  335.     }  
  336.   //lof降序
  337.     private function rsortArr($arr) {
  338.                 for($i = 0;$i < count($arr);$i ++){
  339.                         for($j = $i + 1;$j < count($arr);$j ++){
  340.                                 if($this->compareAandBLof($arr,$i, $j)<0){
  341.                                         $arr=$this->changeAandB($arr,$i, $j);
  342.                                                
  343.                                 }
  344.                         }
  345.                 }
  346.                 return $arr;
  347.     }  
  348.   
  349.     public static function main() {  
  350.            
  351.   
  352.         $dpoints = array();  
  353.   
  354.         $a = array( 2, 3 );  
  355.         $b = array( 2, 4 );  
  356.         $c = array( 1, 4 );  
  357.         $d = array( 1, 3 );  
  358.         $e = array( 2, 2 );  
  359.         $f = array( 3, 2 );  
  360.   
  361.         $g = array( 8, 7 );  
  362.         $h = array( 8, 6 );  
  363.         $i = array( 7, 7 );  
  364.         $j = array( 7, 6 );  
  365.         $k = array( 8, 5 );  
  366.   
  367.         $l = array( 100, 2 );// 孤立点  
  368.   
  369.         $m = array( 8, 20 );  
  370.         $n = array( 8, 19 );  
  371.         $o = array( 7, 18 );  
  372.         $p = array( 7, 17 );  
  373.         $yichen = array( 8, 21 );
  374.   
  375.         array_push($dpoints,new DataNode("a", $a));  
  376.         array_push($dpoints,new DataNode("b", $b));  
  377.         array_push($dpoints,new DataNode("c", $c));  
  378.         array_push($dpoints,new DataNode("d", $d));  
  379.         array_push($dpoints,new DataNode("e", $e));  
  380.         array_push($dpoints,new DataNode("f", $f));  
  381.   
  382.         array_push($dpoints,new DataNode("g", $g));  
  383.         array_push($dpoints,new DataNode("h", $h));  
  384.         array_push($dpoints,new DataNode("i", $i));  
  385.         array_push($dpoints,new DataNode("j", $j));  
  386.         array_push($dpoints,new DataNode("k", $k));  
  387.   
  388.         array_push($dpoints,new DataNode("l", $l));  
  389.   
  390.         array_push($dpoints,new DataNode("m", $m));  
  391.         array_push($dpoints,new DataNode("n", $n));  
  392.         array_push($dpoints,new DataNode("o", $o));  
  393.         array_push($dpoints,new DataNode("p", $p));  
  394.         array_push($dpoints,new DataNode("yichen", $yichen));  
  395.   
  396.         $lof = new OutlierNodeDetect();  
  397.   
  398.         $nodeList = $lof->getOutlierNode($dpoints);
  399.                
  400.                 foreach($nodeList as $node):   
  401.            echo($node->getNodeName() . "--" . round($node->getLof(),4));
  402.                    echo("<br>");
  403.         endforeach;  
  404.   
  405.       
  406.   
  407.     }  
  408. }
  409. OutlierNodeDetect::main();
  410. ?>
复制代码
到此这篇关于PHP局部非常因子算法-Local Outlier Factor(LOF)算法的具体实现解析的文章就先容到这了,更多相关PHP局部非常因子算法-Local Outlier Factor(LOF)算法内容请搜索脚本之家以前的文章或继续浏览下面的相关文章渴望大家以后多多支持脚本之家!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作