Java实现 基于密度的局部离群点检测

Java实现 基于密度的局部离群点检测

算法概述

算法：基于密度的局部离群点检测（lof算法）

输入：样本集合D，正整数K（用于计算第K距离）

输出：各样本点的局部离群点因子

过程：

计算每个对象与其他对象的欧几里得距离

对欧几里得距离进行排序，计算第k距离以及第K领域

计算每个对象的可达密度

计算每个对象的局部离群点因子

对每个点的局部离群点因子进行排序，输出。

算法java源码

本算法包括两个类文件，一个是：DataNode，另一个是：OutlierNodeDetect

DataNode的源码

package com.bigdata.ml.outlier;

import java.util.ArrayList;

import java.util.List;

/**

*

* @author zouzhongfan

*

*/

public class DataNode {

private String nodeName; // 样本点名

private double[] dimensioin; // 样本点的维度

private double kDistance; // k-距离

private List kNeighbor = new ArrayList();// k-领域

private double distance; // 到给定点的欧几里得距离

private double reachDensity;// 可达密度

private double reachDis;// 可达距离

private double lof;// 局部离群因子

public DataNode() {

}

public DataNode(String nodeName, double[] dimensioin) {

this.nodeName = nodeName;

this.dimensioin = dimensioin;

}

public String getNodeName() {

return nodeName;

}

public void setNodeName(String nodeName) {

this.nodeName = nodeName;

}

public double[] getDimensioin() {

return dimensioin;

}

public void setDimensioin(double[] dimensioin) {

this.dimensioin = dimensioin;

}

public double getkDistance() {

return kDistance;

}

public void setkDistance(double kDistance) {

this.kDistance = kDistance;

}

public List getkNeighbor() {

return kNeighbor;

}

public void setkNeighbor(List kNeighbor) {

this.kNeighbor = kNeighbor;

}

public double getDistance() {

return distance;

}

public void setDistance(double distance) {

this.distance = distance;

}

public double getReachDensity() {

return reachDensity;

}

public void setReachDensity(double reachDensity) {

this.reachDensity = reachDensity;

}

public double getReachDis() {

return reachDis;

}

public void setReachDis(double reachDis) {

this.reachDis = reachDis;

}

public double getLof() {

return lof;

}

public void setLof(double lof) {

this.lof = lof;

}

}

OutlierNodeDetect.java的源码如下：

package com.bigdata.ml.outlier;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.List;

/**

* 离群点分析

*

* @author zouzhongfan

* 算法：基于密度的局部离群点检测（lof算法）

* 输入：样本集合D，正整数K（用于计算第K距离）

* 输出：各样本点的局部离群点因子

* 过程：

* 1）计算每个对象与其他对象的欧几里得距离

* 2）对欧几里得距离进行排序，计算第k距离以及第K领域

* 3）计算每个对象的可达密度

* 4）计算每个对象的局部离群点因子

* 5）对每个点的局部离群点因子进行排序，输出。

**/

public class OutlierNodeDetect {

private static int INT_K = 5;//正整数K

// 1.找到给定点与其他点的欧几里得距离

// 2.对欧几里得距离进行排序，找到前5位的点，并同时记下k距离

// 3.计算每个点的可达密度

// 4.计算每个点的局部离群点因子

// 5.对每个点的局部离群点因子进行排序，输出。

public List getOutlierNode(List allNodes) {

List kdAndKnList = getKDAndKN(allNodes);

calReachDis(kdAndKnList);

calReachDensity(kdAndKnList);

calLof(kdAndKnList);

//降序排序

Collections.sort(kdAndKnList, new LofComparator());

return kdAndKnList;

}

/**

* 计算每个点的局部离群点因子

* @param kdAndKnList

*/

private void calLof(List kdAndKnList) {

for (DataNode node : kdAndKnList) {

List tempNodes = node.getkNeighbor();

double sum = 0.0;

for (DataNode tempNode : tempNodes) {

double rd = getRD(tempNode.getNodeName(), kdAndKnList);

sum = rd / node.getReachDensity() + sum;

}

sum = sum / (double) INT_K;

node.setLof(sum);

}

}

/**

* 计算每个点的可达距离

* @param kdAndKnList

*/

private void calReachDensity(List kdAndKnList) {

for (DataNode node : kdAndKnList) {

List tempNodes = node.getkNeighbor();

double sum = 0.0;

double rd = 0.0;

for (DataNode tempNode : tempNodes) {

sum = tempNode.getReachDis() + sum;

}

rd = (double) INT_K / sum;

node.setReachDensity(rd);

}

}

/**

* 计算每个点的可达密度,reachdis(p,o)=max{ k-distance(o),d(p,o)}

* @param kdAndKnList

*/

private void calReachDis(List kdAndKnList) {

for (DataNode node : kdAndKnList) {

List tempNodes = node.getkNeighbor();

for (DataNode tempNode : tempNodes) {

//获取tempNode点的k-距离

double kDis = getKDis(tempNode.getNodeName(), kdAndKnList);

//reachdis(p,o)=max{ k-distance(o),d(p,o)}

if (kDis < tempNode.getDistance()) {

tempNode.setReachDis(tempNode.getDistance());

} else {

tempNode.setReachDis(kDis);

}

}

}

}

/**

* 获取某个点的k-距离（kDistance）

* @param nodeName

* @param nodeList

* @return

*/

private double getKDis(String nodeName, List nodeList) {

double kDis = 0;

for (DataNode node : nodeList) {

if (nodeName.trim().equals(node.getNodeName().trim())) {

kDis = node.getkDistance();

break;

}

}

return kDis;

}

/**

* 获取某个点的可达距离

* @param nodeName

* @param nodeList

* @return

*/

private double getRD(String nodeName, List nodeList) {

double kDis = 0;

for (DataNode node : nodeList) {

if (nodeName.trim().equals(node.getNodeName().trim())) {

kDis = node.getReachDensity();

break;

}

}

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

*/

private List getKDAndKN(List allNodes) {

List kdAndKnList = new ArrayList();

for (int i = 0; i < allNodes.size(); i++) {

List tempNodeList = new ArrayList();

DataNode nodeA = new DataNode(allNodes.get(i).getNodeName(), allNodes

.get(i).getDimensioin());

//1,找到给定点NodeA与其他点NodeB的欧几里得距离，并记录在NodeB点的distance变量中。

for (int j = 0; j < allNodes.size(); j++) {

DataNode nodeB = new DataNode(allNodes.get(j).getNodeName(), allNodes

.get(j).getDimensioin());

//计算NodeA与NodeB的欧几里得距离(distance)

double tempDis = getDis(nodeA, nodeB);

nodeB.setDistance(tempDis);

tempNodeList.add(nodeB);

}

//2,对所有NodeB点中的欧几里得距离（distance）进行升序排序。

Collections.sort(tempNodeList, new DistComparator());

for (int k = 1; k < INT_K; k++) {

//3,找到NodeB点的前5位的欧几里得距离点，并记录到到NodeA的kNeighbor变量中。

nodeA.getkNeighbor().add(tempNodeList.get(k));

if (k == INT_K - 1) {

//4,找到NodeB点的第5位距离，并记录到NodeA点的kDistance变量中。

nodeA.setkDistance(tempNodeList.get(k).getDistance());

}

}

kdAndKnList.add(nodeA);

}

return kdAndKnList;

}

/**

* 计算给定点A与其他点B之间的欧几里得距离。

* 欧氏距离的公式：

* d=sqrt( ∑(xi1-xi2)^2 ) 这里i=1,2..n

* xi1表示第一个点的第i维坐标,umVDyiNdwxi2表示第二个点的第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 double getDis(DataNode A, DataNode B) {

double dis = 0.0;

double[] dimA = A.getDimensioin();

double[] dimB = B.getDimensioin();

if (dimA.length == dimB.length) {

for (int i = 0; i < dimA.length; i++) {

double temhttp://p = Math.pow(dimA[i] - dimB[i], 2);

dis = dis + temp;

}

dis = Math.pow(dis, 0.5);

}

return dis;

}

/**

* 升序排序

* @author zouzhongfan

*

*/

class DistComparator implements Comparator {

public int compare(DataNode A, DataNode B) {

//return A.getDistance() - B.getDistance() < 0 ? -1 : 1;

if((A.getDistance()-B.getDistance())<0)

return -1;

else if((A.getDistance()-B.getDistance())>0)

return 1;

else return 0;

}

}

/**

* 降序排序

* @author zouzhongfan

*

*/

class LofComparator implements Comparator {

public int compare(DataNode A, DataNode B) {

//return A.getLof() - B.getLof() < 0 ? 1 : -1;

if((A.getLof()-B.getLof())<0)

return 1;

else if((A.getLof()-B.getLof())>0)

return -1;

else return 0;

}

}

public static void main(String[] args) {

java.text.DecimalFormat df =new java.text.DecimalFormat("#.####");

ArrayList dpoints = new ArrayList();

double[] a = { 2, 3 };

double[] b = { 2, 4 };

double[] c = { 1, 4 };

double[] d = { 1, 3 };

double[] e = { 2, 2 };

double[] f = { 3, 2 };

double[] g = { 8, 7 };

double[] h = { 8, 6 };

double[] i = { 7, 7 };

double[] j = { 7, 6 };

double[] k = { 8, 5 };

double[] l = { 100, 2 };// 孤立点

double[] m = { 8, 20 };

double[] n = { 8, 19 };

double[] o = { 7, 18 };

double[] p = { 7, 17 };

double[] q = { 8, 21 };

dpoints.add(new DataNode("a", a));

dpoints.add(new DataNode("b", b));

dpoints.add(new DataNode("c", c));

dpoints.add(new DataNode("d", d));

dpoints.add(new DataNode("e", e));

dpoints.add(new DataNode("f", f));

dpoints.add(new DataNode("g", g));

dpoints.add(new DataNode("h", h));

dpoints.add(new DataNode("i", i));

dpoints.add(new DataNode("j", j));

dpoints.add(new DataNode("k", k));

dpoints.add(new DataNode("l", l));

dumVDyiNdwpoints.add(new DataNode("m", m));

dpoints.add(new DataNode("numVDyiNdw", n));

dpoints.add(new DataNode("o", o));

dpoints.add(new DataNode("p", p));

dpoints.add(new DataNode("q", q));

OutlierNodeDetect lof = new OutlierNodeDetect();

List nodeList = lof.getOutlierNode(dpoints);

for (DataNode node : nodeList) {

System.out.println(node.getNodeName() + " " + df.format(node.getLof()));

}

}

}

测试

测试结果如下：

l  39.3094

n  0.8867

h  0.8626

j  0.8626

f  0.8589

a  0.8498

d  0.8498

m  0.8176

o  0.8176

g  0.7837

b  0.7694

c  0.7694

i  0.7518

k  0.7518

e  0.7485

p  0.7459

q  0.7459

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。