這兩天在完善自己系統(tǒng)的過程中要實(shí)現(xiàn)一個(gè)查找異常的功能，于是在朋友的指點(diǎn)下學(xué)習(xí)并實(shí)現(xiàn)了異常點(diǎn)查找的一個(gè)基本算法“局部異常因子算法-Local Outlier Factor(LOF)算法”。
1、 k-distance，點(diǎn)p的第k距離就是距離點(diǎn)p第k遠(yuǎn)的那個(gè)點(diǎn)的距離，k可以是任意值。在實(shí)際生活中可能會(huì)這樣：小明說(shuō)“小紅家是離我家第五近的，小趙、小錢、小孫、小李家都比她家離我家近”所以此處小紅家距離小明家的距離就是小明家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è)大致理解，具體講解還要看上面我參考的那篇文章，寫的很清楚。
接下來(lái)我找了網(wǎng)上的一篇對(duì)此算法的實(shí)現(xiàn)，很遺憾沒有php版本，于是我就找到了這篇文章：基于密度的局部離群點(diǎn)檢測(cè)（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;
}
private function 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 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,找到給定點(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)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
