我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java实现 基于密度的局部离群点检测------lof算法

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java实现 基于密度的局部离群点检测------lof算法

算法概述

算法:基于密度的局部离群点检测(lof算法)

输入:样本集合D,正整数K(用于计算第K距离)

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

过程:

  1. 计算每个对象与其他对象的欧几里得距离
  2. 对欧几里得距离进行排序,计算第k距离以及第K领域
  3. 计算每个对象的可达密度
  4. 计算每个对象的局部离群点因子
  5. 对每个点的局部离群点因子进行排序,输出。

算法Java源码

本算法包括两个类文件,一个是:DataNode,另一个是:OutlierNodeDetect

DataNode的源码


package com.bigdata.ml.outlier;
 
import java.util.ArrayList;
import java.util.List;
 

public class DataNode {
	private String nodeName; // 样本点名
	private double[] dimensioin; // 样本点的维度
	private double kDistance; // k-距离
	private List<DataNode> kNeighbor = new ArrayList<DataNode>();// 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<DataNode> getkNeighbor() {
		return kNeighbor;
	}
 
	public void setkNeighbor(List<DataNode> 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;
 

public class OutlierNodeDetect {
	private static int INT_K = 5;//正整数K
 
	// 1.找到给定点与其他点的欧几里得距离
	// 2.对欧几里得距离进行排序,找到前5位的点,并同时记下k距离
	// 3.计算每个点的可达密度
	// 4.计算每个点的局部离群点因子
	// 5.对每个点的局部离群点因子进行排序,输出。
	public List<DataNode> getOutlierNode(List<DataNode> allNodes) {
 
		List<DataNode> kdAndKnList = getKDAndKN(allNodes);
		calReachDis(kdAndKnList);
		calReachDensity(kdAndKnList);
		calLof(kdAndKnList);
		//降序排序
		Collections.sort(kdAndKnList, new LofComparator());
 
		return kdAndKnList;
	}
 
	
	private void calLof(List<DataNode> kdAndKnList) {
		for (DataNode node : kdAndKnList) {
			List<DataNode> 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);
		}
	}
 
	
	private void calReachDensity(List<DataNode> kdAndKnList) {
		for (DataNode node : kdAndKnList) {
			List<DataNode> 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);
		}
	}
	
	
	private void calReachDis(List<DataNode> kdAndKnList) {
		for (DataNode node : kdAndKnList) {
			List<DataNode> 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);
				}
			}
		}
	}
 
	
	private double getKDis(String nodeName, List<DataNode> nodeList) {
		double kDis = 0;
		for (DataNode node : nodeList) {
			if (nodeName.trim().equals(node.getNodeName().trim())) {
				kDis = node.getkDistance();
				break;
			}
		}
		return kDis;
 
	}
 
	
	private double getRD(String nodeName, List<DataNode> nodeList) {
		double kDis = 0;
		for (DataNode node : nodeList) {
			if (nodeName.trim().equals(node.getNodeName().trim())) {
				kDis = node.getReachDensity();
				break;
			}
		}
		return kDis;
 
	}
	
	
	private List<DataNode> getKDAndKN(List<DataNode> allNodes) {
		List<DataNode> kdAndKnList = new ArrayList<DataNode>();
		for (int i = 0; i < allNodes.size(); i++) {
			List<DataNode> tempNodeList = new ArrayList<DataNode>();
			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;
	}
	
	
	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 temp = Math.pow(dimA[i] - dimB[i], 2);
				dis = dis + temp;
			}
			dis = Math.pow(dis, 0.5);
		}
		return dis;
	}
 
	
	class DistComparator implements Comparator<DataNode> {
		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;  
		}
	}
 
	
	class LofComparator implements Comparator<DataNode> {
		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<DataNode> dpoints = new ArrayList<DataNode>();
 
		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));
 
		dpoints.add(new DataNode("m", m));
		dpoints.add(new DataNode("n", n));
		dpoints.add(new DataNode("o", o));
		dpoints.add(new DataNode("p", p));
		dpoints.add(new DataNode("q", q));
 
		OutlierNodeDetect lof = new OutlierNodeDetect();
 
		List<DataNode> 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

到此这篇关于Java实现 基于密度的局部离群点检测------lof算法的文章就介绍到这了,更多相关Java实现离群点检测------lof算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java实现 基于密度的局部离群点检测------lof算法

下载Word文档到电脑,方便收藏和打印~

下载Word文档

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录