Java實(shí)現(xiàn) 基于密度的局部離群點(diǎn)檢測(cè)------lof算法
算法概述
算法:基于密度的局部離群點(diǎn)檢測(cè)(lof算法)
輸入:樣本集合D,正整數(shù)K(用于計(jì)算第K距離)
輸出:各樣本點(diǎn)的局部離群點(diǎn)因子
過程:
- 計(jì)算每個(gè)對(duì)象與其他對(duì)象的歐幾里得距離
- 對(duì)歐幾里得距離進(jìn)行排序,計(jì)算第k距離以及第K領(lǐng)域
- 計(jì)算每個(gè)對(duì)象的可達(dá)密度
- 計(jì)算每個(gè)對(duì)象的局部離群點(diǎn)因子
- 對(duì)每個(gè)點(diǎn)的局部離群點(diǎn)因子進(jìn)行排序,輸出。
算法Java源碼
本算法包括兩個(gè)類文件,一個(gè)是:DataNode,另一個(gè)是:OutlierNodeDetect
DataNode的源碼
package com.bigdata.ml.outlier; import java.util.ArrayList; import java.util.List; /** * * @author zouzhongfan * */ public class DataNode { private String nodeName; // 樣本點(diǎn)名 private double[] dimensioin; // 樣本點(diǎn)的維度 private double kDistance; // k-距離 private List<DataNode> kNeighbor = new ArrayList<DataNode>();// k-領(lǐng)域 private double distance; // 到給定點(diǎn)的歐幾里得距離 private double reachDensity;// 可達(dá)密度 private double reachDis;// 可達(dá)距離 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; /** * 離群點(diǎn)分析 * * @author zouzhongfan * 算法:基于密度的局部離群點(diǎn)檢測(cè)(lof算法) * 輸入:樣本集合D,正整數(shù)K(用于計(jì)算第K距離) * 輸出:各樣本點(diǎn)的局部離群點(diǎn)因子 * 過程: * 1)計(jì)算每個(gè)對(duì)象與其他對(duì)象的歐幾里得距離 * 2)對(duì)歐幾里得距離進(jìn)行排序,計(jì)算第k距離以及第K領(lǐng)域 * 3)計(jì)算每個(gè)對(duì)象的可達(dá)密度 * 4)計(jì)算每個(gè)對(duì)象的局部離群點(diǎn)因子 * 5)對(duì)每個(gè)點(diǎn)的局部離群點(diǎn)因子進(jìn)行排序,輸出。 **/ public class OutlierNodeDetect { private static int 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 List<DataNode> getOutlierNode(List<DataNode> allNodes) { List<DataNode> kdAndKnList = getKDAndKN(allNodes); calReachDis(kdAndKnList); calReachDensity(kdAndKnList); calLof(kdAndKnList); //降序排序 Collections.sort(kdAndKnList, new LofComparator()); return kdAndKnList; } /** * 計(jì)算每個(gè)點(diǎn)的局部離群點(diǎn)因子 * @param 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); } } /** * 計(jì)算每個(gè)點(diǎn)的可達(dá)距離 * @param kdAndKnList */ 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); } } /** * 計(jì)算每個(gè)點(diǎn)的可達(dá)密度,reachdis(p,o)=max{ k-distance(o),d(p,o)} * @param kdAndKnList */ private void calReachDis(List<DataNode> kdAndKnList) { for (DataNode node : kdAndKnList) { List<DataNode> tempNodes = node.getkNeighbor(); for (DataNode tempNode : tempNodes) { //獲取tempNode點(diǎn)的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); } } } } /** * 獲取某個(gè)點(diǎn)的k-距離(kDistance) * @param nodeName * @param nodeList * @return */ 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; } /** * 獲取某個(gè)點(diǎn)的可達(dá)距離 * @param nodeName * @param nodeList * @return */ 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; } /** * 計(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 List<Node> */ 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,找到給定點(diǎn)NodeA與其他點(diǎn)NodeB的歐幾里得距離,并記錄在NodeB點(diǎn)的distance變量中。 for (int j = 0; j < allNodes.size(); j++) { DataNode nodeB = new DataNode(allNodes.get(j).getNodeName(), allNodes .get(j).getDimensioin()); //計(jì)算NodeA與NodeB的歐幾里得距離(distance) double tempDis = getDis(nodeA, nodeB); nodeB.setDistance(tempDis); tempNodeList.add(nodeB); } //2,對(duì)所有NodeB點(diǎn)中的歐幾里得距離(distance)進(jìn)行升序排序。 Collections.sort(tempNodeList, new DistComparator()); for (int k = 1; k < INT_K; k++) { //3,找到NodeB點(diǎn)的前5位的歐幾里得距離點(diǎn),并記錄到到NodeA的kNeighbor變量中。 nodeA.getkNeighbor().add(tempNodeList.get(k)); if (k == INT_K - 1) { //4,找到NodeB點(diǎn)的第5位距離,并記錄到NodeA點(diǎn)的kDistance變量中。 nodeA.setkDistance(tempNodeList.get(k).getDistance()); } } kdAndKnList.add(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 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; } /** * 升序排序 * @author zouzhongfan * */ 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; } } /** * 降序排序 * @author zouzhongfan * */ 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 };// 孤立點(diǎn) 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())); } } }
測(cè)試
測(cè)試結(jié)果如下:
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
到此這篇關(guān)于Java實(shí)現(xiàn) 基于密度的局部離群點(diǎn)檢測(cè)------lof算法的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)離群點(diǎn)檢測(cè)------lof算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
spring的xml文件打開沒有namespace等操作選項(xiàng)的解決方案
這篇文章主要介紹了spring的xml文件打開沒有namespace等操作選項(xiàng)的解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-09-09SpringBoot重啟后,第一次請(qǐng)求接口請(qǐng)求慢的問題及解決
這篇文章主要介紹了SpringBoot重啟后,第一次請(qǐng)求接口請(qǐng)求慢的問題及解決,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-05-05Java 實(shí)現(xiàn)瀏覽器下載文件及文件預(yù)覽
這篇文章主要介紹了Java 實(shí)現(xiàn)瀏覽器下載文件及文件預(yù)覽,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06Java Map 按照Value排序的實(shí)現(xiàn)方法
Map是鍵值對(duì)的集合接口,它的實(shí)現(xiàn)類主要包括:HashMap,TreeMap,Hashtable以及LinkedHashMap等。這篇文章主要介紹了Java Map 按照Value排序的實(shí)現(xiàn)方法,需要的朋友可以參考下2016-08-08