当前位置 博文首页 > 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();
?>
