這兩天在完善自己系統(tǒng)的過程中要實(shí)現(xiàn)一個(gè)查找異常的功能，于是在朋友的指點(diǎn)下學(xué)習(xí)并實(shí)現(xiàn)了異常點(diǎn)查找的一個(gè)基本算法“局部異常因子算法-Local Outlier Factor(LOF)算法”。

首先，找相關(guān)說明看看這是個(gè)什么東西吧。

我參考了這一篇文章： 異常點(diǎn)/離群點(diǎn)檢測算法——LOF

大致明白了lof算法是在講什么，我的理解還有很多不完善的地方，不過還是作為一個(gè)初學(xué)者寫出來供大家批評(píng)指正。

根據(jù)我的理解大致描述如下：

1、 k-distance，點(diǎn)p的第k距離就是距離點(diǎn)p第k遠(yuǎn)的那個(gè)點(diǎn)的距離，k可以是任意值。在實(shí)際生活中可能會(huì)這樣：小明說“小紅家是離我家第五近的，小趙、小錢、小孫、小李家都比她家離我家近”所以此處小紅家距離小明家的距離就是小明家k為5時(shí)的第k距離。

2、k-distance neighborhood of p，第k距離領(lǐng)域，按照上面的例子就是{小趙、小錢、小孫、小李、小紅}，把離p最近的k個(gè)點(diǎn)放入一個(gè)數(shù)組就是第k距離領(lǐng)域了。

3、reach-distance：可達(dá)距離。點(diǎn)o到點(diǎn)p的第k可達(dá)距離分兩種情況，一種是p在o的第k距離領(lǐng)域那個(gè)數(shù)組中，這時(shí)候可達(dá)距離等于第k距離，第二種就是p離點(diǎn)o比較遠(yuǎn)，不在o的第k距離領(lǐng)域中，此時(shí)的可達(dá)距離即為真實(shí)距離。依然使用上述的例子，小趙家在小明家的第k鄰域中，所以可達(dá)距離就是第k距離，就是小紅家的距離，而二狗子家里小明家很遠(yuǎn)，可達(dá)距離就是真實(shí)距離了。

4、local reachability density：局部可達(dá)密度。點(diǎn)p的局部可達(dá)密度是指點(diǎn)p第k距離鄰域中所有成員到點(diǎn)p的可達(dá)距離的平均值的倒數(shù)，有點(diǎn)復(fù)雜，不過多讀幾遍還是蠻好理解的，就不舉例子了。

5、local outlier factor：局部離群因子。點(diǎn)p的局部離群因子即為領(lǐng)域中所有點(diǎn)的局部可達(dá)密度的平均數(shù)比點(diǎn)p的局部可達(dá)密度，不做解釋。到這里為止就是我對(duì)lof算法的一個(gè)大致理解，具體講解還要看上面我參考的那篇文章，寫的很清楚。

接下來我找了網(wǎng)上的一篇對(duì)此算法的實(shí)現(xiàn)，很遺憾沒有php版本，于是我就找到了這篇文章：基于密度的局部離群點(diǎn)檢測（lof算法） （Java 實(shí)現(xiàn)）

如題所示，是一篇Java實(shí)現(xiàn)，于是我就在大神的基礎(chǔ)上對(duì)其進(jìn)行修改，改成了一個(gè)php的版本。因?yàn)閷?duì)迭代器理解的不是很好，所以迭代器實(shí)現(xiàn)部分改成了一般函數(shù)，有機(jī)會(huì)再進(jìn)行完善。

如下：

<?php class DataNode { private $nodeName; // 樣本點(diǎn)名 private $dimensioin; // 樣本點(diǎn)的維度 private $kDistance; // k-距離 private $kNeighbor = array();// k-領(lǐng)域 private $distance; // 到給定點(diǎn)的歐幾里得距離 private $reachDensity;// 可達(dá)密度 private $reachDis;// 可達(dá)距離private $lof;// 局部離群因子public function __construct() { $num = func_num_args(); //獲得參數(shù)個(gè)數(shù)$args = func_get_args(); //獲得參數(shù)列表數(shù)組switch($num){case 0: break;case 2:$this->__call(’__construct2’, $args);break;} } public function __call($name, $arg) //根據(jù)函數(shù)名調(diào)用函數(shù){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;//正整數(shù)K// 1.找到給定點(diǎn)與其他點(diǎn)的歐幾里得距離 // 2.對(duì)歐幾里得距離進(jìn)行排序，找到前5位的點(diǎn)，并同時(shí)記下k距離 // 3.計(jì)算每個(gè)點(diǎn)的可達(dá)密度 // 4.計(jì)算每個(gè)點(diǎn)的局部離群點(diǎn)因子 // 5.對(duì)每個(gè)點(diǎn)的局部離群點(diǎn)因子進(jìn)行排序，輸出。 public function getOutlierNode($allNodes) { $kdAndKnList = $this->getKDAndKN($allNodes); $this->calReachDis($kdAndKnList); $this->calReachDensity($kdAndKnList); $this->calLof($kdAndKnList); //降序排序 $kdAndKnList = $this->rsortArr($kdAndKnList); return $kdAndKnList; }/** * 計(jì)算每個(gè)點(diǎn)的局部離群點(diǎn)因子 * @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; }/** * 計(jì)算每個(gè)點(diǎn)的可達(dá)距離 * @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; } /** * 計(jì)算每個(gè)點(diǎn)的可達(dá)密度,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點(diǎn)的k-距離 $kDis = $this->getKDis($tempNode->getNodeName(), $kdAndKnList); if ($kDis < $tempNode->getDistance()) { $tempNode->setReachDis($tempNode->getDistance()); } else { $tempNode->setReachDis($kDis); } endforeach; endforeach; }/** * 獲取某個(gè)點(diǎn)的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;} privatefunction strcomp($str1,$str2){ if($str1 == $str2){ return TRUE; }else{ return FALSE; } } /** * 獲取某個(gè)點(diǎn)的可達(dá)距離 * @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;} /** * 計(jì)算給定點(diǎn)NodeA與其他點(diǎn)NodeB的歐幾里得距離（distance）,并找到NodeA點(diǎn)的前5位NodeB，然后記錄到NodeA的k-領(lǐng)域（kNeighbor）變量。 * 同時(shí)找到NodeA的k距離，然后記錄到NodeA的k-距離（kDistance）變量中。 * 處理步驟如下： * 1,計(jì)算給定點(diǎn)NodeA與其他點(diǎn)NodeB的歐幾里得距離，并記錄在NodeB點(diǎn)的distance變量中。 * 2,對(duì)所有NodeB點(diǎn)中的distance進(jìn)行升序排序。 * 3,找到NodeB點(diǎn)的前5位的歐幾里得距離點(diǎn)，并記錄到到NodeA的kNeighbor變量中。 * 4,找到NodeB點(diǎn)的第5位距離，并記錄到NodeA點(diǎn)的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,找到給定點(diǎn)NodeA與其他點(diǎn)NodeB的歐幾里得距離，并記錄在NodeB點(diǎn)的distance變量中。 for ($j = 0; $j < count($allNodes); $j++) { $nodeB = new DataNode($allNodes[$j]->getNodeName(), $allNodes[$j]->getDimensioin()); //計(jì)算NodeA與NodeB的歐幾里得距離(distance) $tempDis = $this->getDis($nodeA, $nodeB); $nodeB->setDistance($tempDis);array_push($tempNodeList,$nodeB);//$tempNodeList.add(nodeB); } //2,對(duì)所有NodeB點(diǎn)中的歐幾里得距離（distance）進(jìn)行升序排序。$tempNodeList = $this->sortArr($tempNodeList); $neighArr = array(); for ($k = 1; $k <= self::$INT_K; $k++) { //3,找到NodeB點(diǎn)的前5位的歐幾里得距離點(diǎn)，并記錄到到NodeA的kNeighbor變量中。 array_push($neighArr ,$tempNodeList[$k]);if ($k == self::$INT_K - 1) { //4,找到NodeB點(diǎn)的第5位距離，并記錄到NodeA點(diǎn)的kDistance變量中。 $nodeA->setkDistance($tempNodeList[$k]->getDistance());} } $nodeA->setkNeighbor($neighArr); array_push($kdAndKnList,$nodeA); } return $kdAndKnList; } /** * 計(jì)算給定點(diǎn)A與其他點(diǎn)B之間的歐幾里得距離。 * 歐氏距離的公式： * d=sqrt( ∑(xi1-xi2)^2 ) 這里i=1,2..n * xi1表示第一個(gè)點(diǎn)的第i維坐標(biāo),xi2表示第二個(gè)點(diǎn)的第i維坐標(biāo) * n維歐氏空間是一個(gè)點(diǎn)集,它的每個(gè)點(diǎn)可以表示為(x(1),x(2),...x(n)), * 其中x(i)(i=1,2...n)是實(shí)數(shù),稱為x的第i個(gè)坐標(biāo),兩個(gè)點(diǎn)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 );// 孤立點(diǎn) $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(); ?>

到此這篇關(guān)于PHP局部異常因子算法-Local Outlier Factor(LOF)算法的具體實(shí)現(xiàn)解析的文章就介紹到這了,更多相關(guān)PHP局部異常因子算法-Local Outlier Factor(LOF)算法內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！