import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Kmeans {
 private class Node {
 int label;// label 用來記錄點屬于第幾個 cluster
 double[] attributes;

 public Node() {
 attributes = new double[100];
 }
 }

 private class NodeComparator {
 Node nodeOne;
 Node nodeTwo;
 double distance;

 public void compute() {
 double val = 0;
 for (int i = 0; i < dimension; ++i) {
 val += (this.nodeOne.attributes[i] - this.nodeTwo.attributes[i]) * 
                             (this.nodeOne.attributes[i] - this.nodeTwo.attributes[i]);
 }
 this.distance = val;
 }
 }

 private ArrayList<Node> arraylist;
 private ArrayList<Node> centroidList;
 private double averageDis;
 private int dimension;
 private Queue<NodeComparator> FsQueue = 
                 new PriorityQueue<NodeComparator>(150, // 用來排序任意兩點之間的距離，從大到小排
 new Comparator<NodeComparator>() {
 public int compare(NodeComparator one, NodeComparator two) {
 if (one.distance < two.distance)
 return 1;
 else if (one.distance > two.distance)
 return -1;
 else
 return 0;
 }
 });

 public void setKmeansInput(String path) {
 try {
 BufferedReader br = new BufferedReader(new FileReader(path));
 String str;
 String[] strArray;
 arraylist = new ArrayList<Node>();
 while ((str = br.readLine()) != null) {
 strArray = str.split(",");
 dimension = strArray.length;
 Node node = new Node();
 for (int i = 0; i < dimension; ++i) {
 node.attributes[i] = Double.parseDouble(strArray[i]);
 }
 arraylist.add(node);
 }
 br.close();
 } catch (IOException e) {
 e.printStackTrace();
 }
 }

 public void computeTheK() {
 int cntTuple = 0;
 for (int i = 0; i < arraylist.size() - 1; ++i) {
 for (int j = i + 1; j < arraylist.size(); ++j) {
 NodeComparator nodecomp = new NodeComparator();
 nodecomp.nodeOne = new Node();
 nodecomp.nodeTwo = new Node();
 for (int k = 0; k < dimension; ++k) {
 nodecomp.nodeOne.attributes[k] = arraylist.get(i).attributes[k];
 nodecomp.nodeTwo.attributes[k] = arraylist.get(j).attributes[k];
 }
 nodecomp.compute();
 averageDis += nodecomp.distance;
 FsQueue.add(nodecomp);
 cntTuple++;
 }
 }
 averageDis /= cntTuple;// 計算平均距離
 chooseCentroid(FsQueue);
 }

 public double getDistance(Node one, Node two) {// 計算兩點間的歐氏距離
 double val = 0;
 for (int i = 0; i < dimension; ++i) {
 val += (one.attributes[i] - two.attributes[i]) * (one.attributes[i] - two.attributes[i]);
 }
 return val;
 }

 public void chooseCentroid(Queue<NodeComparator> queue) {
 centroidList = new ArrayList<Node>();
 boolean flag = false;
 while (!queue.isEmpty()) {
 boolean judgeOne = false;
 boolean judgeTwo = false;
 NodeComparator nc = FsQueue.poll();
 if (nc.distance < averageDis)
 break;// 如果接下來的元組，兩節(jié)點間距離小于平均距離，則不繼續(xù)迭代
 if (!flag) {
 centroidList.add(nc.nodeOne);// 先加入所有點中距離最遠(yuǎn)的兩個點
 centroidList.add(nc.nodeTwo);
 flag = true;
 } else {// 之后從之前已加入的最遠(yuǎn)的兩個點開始，找離這兩個點最遠(yuǎn)的點，
 // 如果距離大于所有點的平均距離，則認(rèn)為找到了新的質(zhì)心，否則不認(rèn)定為質(zhì)心
 for (int i = 0; i < centroidList.size(); ++i) {
 Node testnode = centroidList.get(i);
 if (centroidList.contains(nc.nodeOne) || getDistance(testnode, nc.nodeOne) < averageDis) {
 judgeOne = true;
 }
 if (centroidList.contains(nc.nodeTwo) || getDistance(testnode, nc.nodeTwo) < averageDis) {
 judgeTwo = true;
 }
 }
 if (!judgeOne) {
 centroidList.add(nc.nodeOne);
 }
 if (!judgeTwo) {
 centroidList.add(nc.nodeTwo);
 }
 }
 }
 }

 public void doIteration(ArrayList<Node> centroid) {

 int cnt = 1;
 int cntEnd = 0;
 int numLabel = centroid.size();
 while (true) {// 迭代，直到所有的質(zhì)心都不變化為止
 boolean flag = false;
 for (int i = 0; i < arraylist.size(); ++i) {
 double dis = 0x7fffffff;
 cnt = 1;
 for (int j = 0; j < centroid.size(); ++j) {
 Node node = centroid.get(j);
 if (getDistance(arraylist.get(i), node) < dis) {
 dis = getDistance(arraylist.get(i), node);
 arraylist.get(i).label = cnt;
 }
 cnt++;
 }
 }
 int j = 0;
 numLabel -= 1;
 while (j < numLabel) {
 int c = 0;
 Node node = new Node();
 for (int i = 0; i < arraylist.size(); ++i) {
 if (arraylist.get(i).label == j + 1) {
 for (int k = 0; k < dimension; ++k) {
 node.attributes[k] += arraylist.get(i).attributes[k];
 }
 c++;
 }
 }
 DecimalFormat df = new DecimalFormat("#.###");// 保留小數(shù)點后三位
 double[] attributelist = new double[100];
 for (int i = 0; i < dimension; ++i) {
 attributelist[i] = Double.parseDouble(df.format(node.attributes[i] / c));
 if (attributelist[i] != centroid.get(j).attributes[i]) {
 centroid.get(j).attributes[i] = attributelist[i];
 flag = true;
 }
 }
 if (!flag) {
 cntEnd++;
 if (cntEnd == numLabel) {// 若所有的質(zhì)心都不變，則跳出循環(huán)
 break;
 }
 }
 j++;
 }
 if (cntEnd == numLabel) {// 若所有的質(zhì)心都不變，則 success
 System.out.println("run kmeans successfully.");
 break;
 }
 }
 }

 public void printKmeansResults(String path) {
 try {
 PrintStream out = new PrintStream(path);
 computeTheK();
 doIteration(centroidList);
 out.println("There are " + centroidList.size() + " clusters!");
 for (int i = 0; i < arraylist.size(); ++i) {
 out.print("(");
 for (int j = 0; j < dimension - 1; ++j) {
 out.print(arraylist.get(i).attributes[j] + ", ");
 }
 out.print(arraylist.get(i).attributes[dimension - 1] + ") ");
 out.println("belongs to cluster " + arraylist.get(i).label);
 }
 out.close();
 System.out.println("Please check results in: " + path);
 } catch (IOException e) {
 e.printStackTrace();
 }
 }

 public static void main(String[] args) {
 Kmeans kmeans = new Kmeans();
 kmeans.setKmeansInput("c:/kmeans.txt");
 kmeans.printKmeansResults("c:/kmeansResults.txt");

 }
}

1,1
2,1
1,2
2,2
6,1
6,2
7,1
7,2
1,5
1,6
2,5
2,6
6,5
6,6
7,5
7,6

There are 4 clusters!
(1.0, 1.0) belongs to cluster 1
(2.0, 1.0) belongs to cluster 1
(1.0, 2.0) belongs to cluster 1
(2.0, 2.0) belongs to cluster 1
(6.0, 1.0) belongs to cluster 3
(6.0, 2.0) belongs to cluster 3
(7.0, 1.0) belongs to cluster 3
(7.0, 2.0) belongs to cluster 3
(1.0, 5.0) belongs to cluster 4
(1.0, 6.0) belongs to cluster 4
(2.0, 5.0) belongs to cluster 4
(2.0, 6.0) belongs to cluster 4
(6.0, 5.0) belongs to cluster 2
(6.0, 6.0) belongs to cluster 2
(7.0, 5.0) belongs to cluster 2
(7.0, 6.0) belongs to cluster 2

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.text.DecimalFormat;
import java.util.ArrayList;

public class Hierarchical {
 private double[][] matrix;
 private int dimension;// 數(shù)據(jù)維度

 private class Node {
 double[] attributes;

 public Node() {
 attributes = new double[100];
 }
 }

 private ArrayList<Node> arraylist;

 private class Model {
 int x = 0;
 int y = 0;
 double value = 0;
 }

 private Model minModel = new Model();

 private double getDistance(Node one, Node two) {// 計算兩點間的歐氏距離
 double val = 0;
 for (int i = 0; i < dimension; ++i) {
 val += (one.attributes[i] - two.attributes[i]) * (one.attributes[i] - two.attributes[i]);
 }
 return Math.sqrt(val);
 }

 private void loadMatrix() {// 將輸入數(shù)據(jù)轉(zhuǎn)化為矩陣
 for (int i = 0; i < matrix.length; ++i) {
 for (int j = i + 1; j < matrix.length; ++j) {
 double distance = getDistance(arraylist.get(i), arraylist.get(j));
 matrix[i][j] = distance;
 }
 }
 }

 private Model findMinValueOfMatrix(double[][] matrix) {// 找出矩陣中距離最近的兩個簇
 Model model = new Model();
 double min = 0x7fffffff;
 for (int i = 0; i < matrix.length; ++i) {
 for (int j = i + 1; j < matrix.length; ++j) {
 if (min > matrix[i][j] && matrix[i][j] != 0) {
 min = matrix[i][j];
 model.x = i;
 model.y = j;
 model.value = matrix[i][j];
 }
 }
 }
 return model;
 }

 private void processHierarchical(String path) {
 try {
 PrintStream out = new PrintStream(path);
 while (true) {// 凝聚層次聚類迭代
 out.println("Matrix update as below: ");
 for (int i = 0; i < matrix.length; ++i) {// 輸出每次迭代更新的矩陣
 for (int j = 0; j < matrix.length - 1; ++j) {
 out.print(new DecimalFormat("#.00").format(matrix[i][j]) + " ");
 }
 out.println(new DecimalFormat("#.00").format(matrix[i][matrix.length - 1]));
 }
 out.println();
 minModel = findMinValueOfMatrix(matrix);
 if (minModel.value == 0) {// 當(dāng)找不出距離最近的兩個簇時，迭代結(jié)束
 break;
 }
 out.println("Combine " + (minModel.x + 1) + " " + (minModel.y + 1));
 out.println("The distance is: " + minModel.value);

 matrix[minModel.x][minModel.y] = 0;// 更新矩陣
 for (int i = 0; i < matrix.length; ++i) {// 如果合并了點 p1 與 p2，則只保留 p1,p2 其中之一與其他點的距離，取較小值
 if (matrix[i][minModel.x] <= matrix[i][minModel.y]) {
 matrix[i][minModel.y] = 0;
 } else {
 matrix[i][minModel.x] = 0;
 }
 if (matrix[minModel.x][i] <= matrix[minModel.y][i]) {
 matrix[minModel.y][i] = 0;
 } else {
 matrix[minModel.x][i] = 0;
 }
 }
 }

 out.close();
 System.out.println("Please check results in: " + path);
 } catch (Exception e) {
 e.printStackTrace();
 }
 }

 public void setInput(String path) {
 try {
 BufferedReader br = new BufferedReader(new FileReader(path));
 String str;
 String[] strArray;
 arraylist = new ArrayList<Node>();
 while ((str = br.readLine()) != null) {
 strArray = str.split(",");
 dimension = strArray.length;
 Node node = new Node();
 for (int i = 0; i < dimension; ++i) {
 node.attributes[i] = Double.parseDouble(strArray[i]);
 }
 arraylist.add(node);
 }
 matrix = new double[arraylist.size()][arraylist.size()];
 loadMatrix();
 br.close();
 } catch (IOException e) {
 e.printStackTrace();
 }
 }

 public void printOutput(String path) {
 processHierarchical(path);
 }

 public static void main(String[] args) {
 Hierarchical hi = new Hierarchical();
 hi.setInput("c:/hierarchical.txt");
 hi.printOutput("c:/hierarchical_results.txt");
 }
}

0.7,1.2
0.8,2
2,1
2.6,0.8
2.5,1.5

Matrix update as below: 
.00 .81 1.32 1.94 1.82
.00 .00 1.56 2.16 1.77
.00 .00 .00 .63 .71
.00 .00 .00 .00 .71
.00 .00 .00 .00 .00

Combine 3 4
The distance is: 0.6324555320336759
Matrix update as below: 
.00 .81 1.32 .00 1.82
.00 .00 1.56 .00 1.77
.00 .00 .00 .00 .00
.00 .00 .00 .00 .71
.00 .00 .00 .00 .00

Combine 4 5
The distance is: 0.7071067811865475
Matrix update as below: 
.00 .81 1.32 .00 .00
.00 .00 1.56 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00

Combine 1 2
The distance is: 0.806225774829855
Matrix update as below: 
.00 .00 1.32 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00

Combine 1 3
The distance is: 1.3152946437965907
Matrix update as below: 
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00
.00 .00 .00 .00 .00

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class DBSCAN {
 private int dimension;// 數(shù)據(jù)維度
 private double eps = 1.5;
 private int threshold = 3;
 private double distance[][];
 private Map<Integer, Integer> id = new HashMap<Integer, Integer>();
 private int countClusters = 0;
 private ArrayList<Integer> keyPointList = new ArrayList<Integer>();//
 private int[] flags;// 標(biāo)記邊緣點

 private class Edge {
 int p, q;
 double weight;
 }

 private class Node {
 double[] attributes;

 public Node() {
 attributes = new double[100];
 }
 }

 private ArrayList<Node> nodeList;
 private ArrayList<Edge> edgeList;

 private double getDistance(Node one, Node two) {// 計算兩點間的歐氏距離
 double val = 0;
 for (int i = 0; i < dimension; ++i) {
 val += (one.attributes[i] - two.attributes[i]) * (one.attributes[i] - two.attributes[i]);
 }
 return Math.sqrt(val);
 }

 public void loadEdges() {// 給所有在掃描半徑內(nèi)的核心點之間加邊，標(biāo)記邊界點并且自動忽略噪聲點
 edgeList = new ArrayList<Edge>();
 flags = new int[nodeList.size()];
 int[] countPoint = new int[nodeList.size()];
 for (int i = 0; i < countPoint.length; ++i) {
 countPoint[i] = 1;// 每一個點一開始都是核心點
 }
 for (int i = 0; i < nodeList.size(); ++i) {
 for (int j = i + 1; j < nodeList.size(); ++j) {
 distance[i][j] = getDistance(nodeList.get(i), nodeList.get(j));
 if (distance[i][j] <= eps) {// 兩點間距離小于掃描半徑
 countPoint[i]++;
 if (countPoint[i] > 0 && countPoint[i] < threshold) {
 flags[i] = j;// 記錄邊界點
 }
 if (countPoint[i] >= threshold) {// 如果記錄當(dāng)前點的掃描半徑內(nèi)密度值大于或等于給定閾值
 flags[i] = 0;
 if (!keyPointList.contains(i)) {
 keyPointList.add(i);
 }
 }
 countPoint[j]++;
 if (countPoint[j] > 0 && countPoint[j] < threshold) {
 flags[j] = i;// 記錄邊界點
 }
 if (countPoint[j] >= threshold) {// 如果記錄當(dāng)前點的掃描半徑內(nèi)密度值大于或等于給定