dbscan.zip_DBSCAN_DBSCAN算法_DBSCAN聚类算法_DBScan java_clustering jav

package ynu.chl.dbscan; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileInputStream; import java.io.FileWriter; import java.io.InputStreamReader; import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Date; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.TreeMap; import java.util.Vector; public class Dbscan { public static final int MAX_DISTANCE = 999999; public static long running = 0; ArrayList<DataObject> dataList = new ArrayList<DataObject>(); ArrayList<DataObject> noiseList = new ArrayList<DataObject>(); HashMap<Integer, ArrayList<DataObject>> clusterList = new HashMap<Integer, ArrayList<DataObject>>(); int clusterID = 0; // public static final int INTERVAL = 60 * 60; // 时间间距，单位秒 double Radius = 958; // 区域半径 int MinPoints = 100; // int noiseNum = 0; String filePath = ""; String readPath="D:\\DBSCAN\\month\\10\\2015-10-12.csv"; String outPath="D:\\"; // 由于自己到自己的距离是0,所以自己也是自己的neighbor public Vector<DataObject> getNeighbors(DataObject p, ArrayList<DataObject> objects) { Vector<DataObject> neighbors = new Vector<DataObject>(); Iterator<DataObject> iter = objects.iterator(); while (iter.hasNext()) { DataObject q = iter.next(); if (getDistance(p, q) <= Radius) { neighbors.add(q); } } return neighbors; } public void dbscanDeep(DataObject p) { /* * if (p.getCid()!=-1) return; */ p.setVisited(true); Vector<DataObject> neighbors = getNeighbors(p, dataList); if (neighbors.size() < MinPoints) { if (p.getCid() == -1) { p.setCid(0); // cid初始为-1,表示未分类；分类后设置为一个正数；设置为0表示噪声。 noiseList.add(p); noiseNum++; return; } } else { if (p.getCid() == -1) { p.setCid(p.nodeNum); // System.out.println("新簇群：" + p.nodeNum + // "---路段ID："+p.roadID+"---路段名："+ p.roadName); ArrayList<DataObject> list = new ArrayList<DataObject>(); list.add(p); int center = -1; for (int i = 0; i < neighbors.size(); i++) { if (neighbors.get(i).getCid() > 0) { center = neighbors.get(i).getCid(); if (center != p.nodeNum && clusterList.get(center) != null) { list.addAll(clusterList.get(center)); clusterList.remove(center); } } else { neighbors.get(i).setVisited(true); neighbors.get(i).setCid(p.nodeNum); list.add(neighbors.get(i)); } } clusterList.put(p.nodeNum, list); } } } public static void main(String[] args) { running = System.currentTimeMillis(); Dbscan ds = new Dbscan(); ds.readTxtFile();// 输入文件路径 for (int i = 0; i < ds.dataList.size(); i++) { if (ds.dataList.get(i).isVisited) continue; ds.dbscanDeep(ds.dataList.get(i)); } ds.clusterList.put(0, ds.noiseList); ds.out_list(); System.out.println("数据量:" + ds.dataList.size());// 数据总数：74677 System.out.println("噪点:"+ds.noiseNum); System.out.println("参数: 半径" + ds.Radius + "m 密度为" + ds.MinPoints); System.out.println("运行时间:" + ((System.currentTimeMillis() - running) / 1000.00) + "s"); } public void readTxtFile() { try { String encoding = "UTF8"; File file = new File(readPath); if (file.isFile() && file.exists()) { // 判断文件是否存在 InputStreamReader read = new InputStreamReader( new FileInputStream(file), encoding);// 考虑到编码格式 BufferedReader bufferedReader = new BufferedReader(read); String lineTxt = null; int i = 0; while ((lineTxt = bufferedReader.readLine()) != null) { if (i == 0 || lineTxt.trim().equals("")) { i++; continue; } String[] strs = lineTxt.split(","); if (strs.length > 3) { DataObject obj = new DataObject(); obj.nodeNum = dataList.size() + 1; obj.number = strs[2];// 去掉双引号 obj.dateStr = strs[1]; obj.longitude = strs[4]; obj.latitude = strs[3]; //obj.roadID = strs[4]; //obj.roadName = strs[5];// 去掉双引号 dataList.add(obj); } else { System.out.println("数据取值出错！"); } i++; } read.close(); } else { System.out.println("找不到指定的文件"); } } catch (Exception e) { System.out.println("读取文件内容出错"); e.printStackTrace(); } } public void out_list() { try { Iterator iter = clusterList.keySet().iterator(); int length = clusterList.size(); // System.out.println(length + "***********"); int i = 1; int[] countNum = new int[length]; Integer[] countKey = new Integer[length]; ArrayList<Integer> newKeyObject = new ArrayList<Integer>(); for (int j = 0; j < length; j++) { Integer key = (Integer) iter.next(); ArrayList<DataObject> v = clusterList.get(key); countKey[j] = key; countNum[j] = v.size(); } // System.out.println(countKey[0]+" "+countKey[1]+" "+countKey[2]+" "+countKey[3]+" "+countKey[4]+" "+countKey[5]+" "+countKey[6]+" "+countKey[7]+" "+countKey[8]+" "); newKeyObject = sortedKey(countNum, countKey); // System.out.println(newKeyObject.equals(null) + "*********" // + newKeyObject.toString() + "&&&" + newKeyObject.get(0) // + " " + newKeyObject.get(1) + " " + newKeyObject.get(2)); for (int j = 0; j < length; j++) { if (newKeyObject.get(j) == null) continue; ArrayList<DataObject> v = clusterList.get(newKeyObject.get(j)); // System.out.println("====" + v.size()); if (v.size() < MinPoints || newKeyObject.get(j).toString().equals("0")) continue; System.out.println("======" + v.size()); File file = new File(outPath + "/cluster" + i + ".txt"); BufferedWriter ow = new BufferedWriter(new FileWriter(file)); if (newKeyObject.get(j).toString().equals("0")) { } else { System.out.println("聚类 " + i + " 的主要路段,共" + v.size() + "个"); ow.write("上车时间,上车点经度,上车点纬度,所属类别\r\n"); for (int k = 0; k < v.size(); k++) { ow.write(v.get(k).dateStr + "," + v.get(k).longitude + "," + v.get(k).latitude + "," + i + "\r\n"); } } ow.close(); i++; } } catch (Exception e) { e.printStackTrace(); } } // 根据地球上两点间GPS经纬度坐标，计算两点间几何距离。 private static double EARTH_RADIUS = 6378137;// 地球半径--单位:米 private static double rad(double d) { return d * Math.PI / 180.0; } // 可以根据需要进行调整，如加入时间的维度 // 两点之间"距离"的算法，可以根据需要进行调整，如加入时间的维度 public static double getDistance(DataObject p, DataObject q) { double radLat1 = rad(Double.valueOf(p.latitude)); double radLat2 = rad(Double.valueOf(q.latitude)); double a = radLat1 - radLat2; double b = rad(Double.valueOf(p.longitude)) - rad(Double.valueOf(q.longitude)); double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2))); s = s * EARTH_RADIUS; // System.out.println("s="+s); return s; } public ArrayList<Integer> sortedKey(int[] original, Integer[] key) { ArrayList<Integer> sortedData = new ArrayList<Integer>(); ArrayList<Integer> clssifyNum = new ArrayList<Integer>(); for (int i = 0; i < original.length; i++) { if (key[i] != null) { sortedData.add(original[i]); clssifyNum.add(key[i]); } } for (int i = 1; i < sortedData.size(); i++) { if (sortedData.get(i) > sortedData.get(i - 1)) { int temp = sortedData.get(i); Integer tempObject = clssifyNum.get(i); int j = i; while (j > 0 && sortedData.get(j - 1) < temp) { sortedData.set(j, sorted