這兩天在完善自己系統的過程中要實現一個查找異常的功能，于是在朋友的指點下學習并實現了異常點查找的一個基本算法“局部異常因子算法-Local Outlier Factor(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的可達距離的平均值的倒數，有點復雜，不過多讀幾遍還是蠻好理解的，就不舉例子了。
如題所示，是一篇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 ListNode>
*/
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)算法的具體實現解析的文章就介紹到這了,更多相關PHP局部異常因子算法-Local Outlier Factor(LOF)算法內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
