这两天在完善自己系统的过程中要实现一个查找异常的功能，于是在朋友的指点下学习并实现了异常点查找的一个基本算法“局部异常因子算法-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的版本。因为对迭代器理解的不是很好，所以迭代器实现部分改成了一般函数，有机会再进行完善。
如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
|
<?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)算法内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/u013914886/article/details/70194318
