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();
?>
到此这篇关于PHP局部异常因子算法-Local Outlier Factor(LOF)算法的具体实现解析的文章就介绍到这了,更多相关PHP局部异常因子算法-Local Outlier Factor(LOF)算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
c++ Bellman-Ford算法的具体实现
Bellman-Ford算法用于解决有边数限制的最短路问题,且可以应对有负边权的图 其时间复杂度为O(nm),效率较低 代码实现: #include<iostream> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f using namespace std; const int N=1e4+10; const int M=510; int m,n,k,dis[M],backup[M]; //m条边
-
Java实现雪花算法的原理和实战教程
目录 SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法.其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id.在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的,后面的代码中有详细的注解. 这 64 个 bit 中,其中 1 个 bit 是不用的,然后用其中的 41 bit 作为毫秒数,用 10 bit 作为工作机器 id,12 bit 作为序列号. 给大家举个例子吧,比如下面那个 64 bit 的 long 型数字: 第一
-
异常点/离群点检测算法——LOF解析
局部异常因子算法-Local Outlier Factor(LOF) 在数据挖掘方面,经常需要在做特征工程和模型训练之前对数据进行清洗,剔除无效数据和异常数据.异常检测也是数据挖掘的一个方向,用于反作弊.伪基站.金融诈骗等领域. 异常检测方法,针对不同的数据形式,有不同的实现方法.常用的有基于分布的方法,在上.下α分位点之外的值认为是异常值(例如图1),对于属性值常用此类方法.基于距离的方法,适用于二维或高维坐标体系内异常点的判别,例如二维平面坐标或经纬度空间坐标下异常点识别,可
-
java排序算法图文详解
目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 一.堆排序的基本思想是: 二.代码示例 七.归并排序 总结 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(Str
-
Python 语言实现六大查找算法
目录 一.顺序查找算法 二.折半查找算法 三.插补查找算法 四.哈希查找算法 五.分块查找算法 六.斐波那契查找算法 七.六种查找算法的时间复杂度 一.顺序查找算法 顺序查找又称为线性查找,是最简单的查找算法.这种算法就是按照数据的顺序一项一项逐个查找,所以不管数据顺序如何,都得从头到尾地遍历一次.顺序查找的优点就是数据在查找前,不需要对其进行任何处理(包括排序).缺点是查找速度慢,如果数据列的第一个数据就是想要查找的数据,则该算法查找速度为最快,只需查找一次即可:如果查找的数据是数据列的最后一
-
Java实现常见排序算法的优化
冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个元素已经是最大的了.即最后一个元素已经有序了. 优化一: 优化的思路就是每一次扫描遍历一次数组.如果某次的扫描之后没有发生数组元素的交换的话.那么说明数组的元素已经是有序的了, 就可以直接跳出循环.没有继续扫描的必要了. 优化二:如果数组的尾部已经局部有
-
PHP局部异常因子算法-Local Outlier Factor(LOF)算法的具体实现解析
这两天在完善自己系统的过程中要实现一个查找异常的功能,于是在朋友的指点下学习并实现了异常点查找的一个基本算法"局部异常因子算法-Local Outlier Factor(LOF)算法". 首先,找相关说明看看这是个什么东西吧. 我参考了这一篇文章: 异常点/离群点检测算法--LOF 大致明白了lof算法是在讲什么,我的理解还有很多不完善的地方,不过还是作为一个初学者写出来供大家批评指正. 根据我的理解大致描述如下: 1. k-distance,点p的第k距离就是距离点p第k远的那个点的
-
Python实现异常检测LOF算法的示例代码
目录 背景 LOF算法 1.k邻近距离 2.k距离领域 3.可达距离 4.局部可达密度 5.局部异常因子 LOF算法流程 LOF优缺点 Python实现LOF PyOD Sklearn 大家好,我是东哥. 本篇和大家介绍一个经典的异常检测算法:局部离群因子(Local Outlier Factor),简称LOF算法. 背景 Local Outlier Factor(LOF)是基于密度的经典算法(Breuning et. al. 2000), 文章发表于 SIGMOD 2000, 到目前已经有 3
-
Java实现 基于密度的局部离群点检测------lof算法
算法概述 算法:基于密度的局部离群点检测(lof算法) 输入:样本集合D,正整数K(用于计算第K距离) 输出:各样本点的局部离群点因子 过程: 计算每个对象与其他对象的欧几里得距离 对欧几里得距离进行排序,计算第k距离以及第K领域 计算每个对象的可达密度 计算每个对象的局部离群点因子 对每个点的局部离群点因子进行排序,输出. 算法Java源码 本算法包括两个类文件,一个是:DataNode,另一个是:OutlierNodeDetect DataNode的源码 package com.bigdat
-
归并算法之有序数组合并算法实现
归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组.实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部.再将另一个数组剩下的所有元素,直接放入归并数组尾部.算法的简单实现,需要注意的是对参数的校验,判断数组是否有序. public class MergeOrderedArray { public static int[
-
JavaScript中数据结构与算法(五)：经典KMP算法
KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右 后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上蛋疼的KMP是讲解很多,基本都是走的高大上路线看的你也是一头雾水,我试图用自己的理解用最接地气的方式描述 KMP KMP也是一种优化版的
-
Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)
一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }
-
JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法详解【凹多边形的分离轴检测算法】
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法.分享给大家供大家参考,具体如下: 概述 分离轴定理是一项用于检测碰撞的算法.其适用范围较广,涵盖检测圆与多边形,多边形与多边形的碰撞:缺点在于无法检测凹多边形的碰撞.本demo使用Js进行算法实现,HTML5 canvas进行渲染. 详细 一.准备工作,熟悉分离轴定理 算法原理 从根本上来讲,分离轴定理(以及其他碰撞算法)的用途就是去检测并判断两个图形之间是否有间隙.分离轴定理中用到的方法使算法本身显得十分独特. 我所听到过分
-
JS/HTML5游戏常用算法之碰撞检测 像素检测算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 像素检测算法.分享给大家供大家参考,具体如下: 使用像素碰撞检测法算是最精确的算法了,当然,带来的代价也是比较明显的,那就是效率上的低下.除非是在极为特殊的情况下,要求使用非常精确的碰撞,否则,一般情况下在游戏中是不建议使用这种算法,特别是在运行效率不太高的HTML5游戏中. 一般来说在使用像素碰撞检测之前会使用AABB矩形包围盒先检测两个精灵是否有碰撞,如果AABB包围盒检测没有碰撞,那一定是没有碰撞到,反之,则不一定,需要进一步进行像素检
-
JS/HTML5游戏常用算法之碰撞检测 地图格子算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 地图格子算法.分享给大家供大家参考,具体如下: 这种算法经常用于RPG(早期的<最终幻想>.<DQ>.<仙剑奇侠传>).SLG(<炎龙骑士团>.<超级机器人大战>).PUZ(<俄罗斯方块>.<宝石谜阵>)类型的游戏.这类游戏中,通常情况下整个地图都是由一些地图块元素组成,在制作的时候首先给制作出地图所需要的最基本的元素进行编号,然后把这些编号的地图块组合起来就可以根据需
-
人工智能机器学习常用算法总结及各个常用算法精确率对比
本文讲解了机器学习常用算法总结和各个常用分类算法精确率对比.收集了现在比较热门的TensorFlow.Sklearn,借鉴了Github和一些国内外的文章. 机器学习的知识树,这个图片是Github上的,有兴趣的可以自己去看一下: 地址:https://github.com/trekhleb/homemade-machine-learning 简单的翻译一下这个树: 英文 中文 Machine Learning 机器学习 Supervised Learning 监督学习 Unsupervised