这两天在完善自己系统的过程中要实现一个查找异常的功能，于是在朋友的指点下学习并实现了异常点查找的一个基本算法“局部异常因子算法-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(); ?>