算法描述

（1）任意選擇k個數據對象作為初始聚類中心
（2）根據簇中對象的平均值，將每個對象賦給最類似的簇
（3）更新簇的平均值，即計算每個對象簇中對象的平均值
（4）計算聚類準則函數E
（5）重復2-4步驟，直到準則函數E值不再進行變化

代碼

public class Cluster {public String clusterName; // 類簇名private Medoid medoid; // 類簇的質點private ArrayList<DataPoint> dataPoints; // 類簇中各樣本點public Cluster(String clusterName) {this.clusterName = clusterName;this.medoid = null; // will be set by calling setCentroid()dataPoints = new ArrayList<DataPoint>();}public void setMedoid(Medoid c) {medoid = c;}public Medoid getMedoid() {return medoid;}public void addDataPoint(DataPoint dp) { // called from CAInstancedp.setCluster(this);// 標注該類簇屬于某點,計算歐式距離this.dataPoints.add(dp);}public void removeDataPoint(DataPoint dp) {this.dataPoints.remove(dp);}public int getNumDataPoints() {return this.dataPoints.size();}public DataPoint getDataPoint(int pos) {return (DataPoint) this.dataPoints.get(pos);}public String getName() {return this.clusterName;}public ArrayList<DataPoint> getDataPoints() {return this.dataPoints;}
}

public class ClusterAnalysis {public Cluster[] clusters;// 所有類簇private int miter;// 迭代次數private ArrayList<DataPoint> dataPoints = new ArrayList<DataPoint>();// 所有樣本點private int dimNum;//維度public ClusterAnalysis(int k, int iter, ArrayList<DataPoint> dataPoints,int dimNum) {clusters = new Cluster[k];// 類簇種類數for (int i = 0; i < k; i++) {clusters[i] = new Cluster(i+"");}this.miter = iter;this.dataPoints = dataPoints;this.dimNum=dimNum;}public int getIterations() {return miter;}public ArrayList<DataPoint>[] getClusterOutput() {ArrayList<DataPoint> v[] = new ArrayList[clusters.length];for (int i = 0; i < clusters.length; i++) {v[i] = clusters[i].getDataPoints();}return v;}public void startAnalysis(double[][] medoids) {setInitialMedoids(medoids);double[][] newMedoids=medoids;double[][] oldMedoids=new double[medoids.length][this.dimNum];while(!isEqual(oldMedoids,newMedoids)){for(int m = 0; m < clusters.length; m++){//每次迭代開始情況各類簇的點clusters[m].getDataPoints().clear();}for (int j = 0; j < dataPoints.size(); j++) {int clusterIndex=0;double minDistance=Double.MAX_VALUE;for (int k = 0; k < clusters.length; k++) {//判斷樣本點屬于哪個類簇double eucDistance=dataPoints.get(j).testEuclideanDistance(clusters[k].getMedoid());if(eucDistance<minDistance){minDistance=eucDistance;clusterIndex=k;}}//將該樣本點添加到該類簇clusters[clusterIndex].addDataPoint(dataPoints.get(j));}for(int m = 0; m < clusters.length; m++){clusters[m].getMedoid().calcMedoid();//重新計算各類簇的質點}for(int i=0;i<medoids.length;i++){for(int j=0;j<this.dimNum;j++){oldMedoids[i][j]=newMedoids[i][j];}}for(int n=0;n<clusters.length;n++){newMedoids[n]=clusters[n].getMedoid().getDimensioin();}this.miter++;}}private void setInitialMedoids(double[][] medoids) {for (int n = 0; n < clusters.length; n++) {Medoid medoid = new Medoid(medoids[n]);clusters[n].setMedoid(medoid);medoid.setCluster(clusters[n]);}}private boolean isEqual(double[][] oldMedoids,double[][] newMedoids){boolean flag=false;for(int i=0;i<oldMedoids.length;i++){for(int j=0;j<oldMedoids[i].length;j++){if(oldMedoids[i][j]!=newMedoids[i][j]){return flag;}}}flag=true;return flag;}
}

public class DataPoint {private double dimension[]; //樣本點的維度private String pointName; //樣本點名字private Cluster cluster; //類簇private double euDt;//樣本點到質點的距離public DataPoint(double dimension[], String pointName) {this.dimension = dimension;this.pointName = pointName;this.cluster = null;}@Overridepublic String toString() {String result = "Point_id=" + pointName + "  [";for (int i = 0; i < dimension.length; i++) {result += String.format("%.2f",dimension[i]) + " ";}return result.trim()+"] clusterId: "+cluster.clusterName;}public void setCluster(Cluster cluster) {this.cluster = cluster;}public double calEuclideanDistanceSum() {double sum=0.0;Cluster cluster=this.getCluster();ArrayList<DataPoint> dataPoints=cluster.getDataPoints();for(int i=0;i<dataPoints.size();i++){double[] dims=dataPoints.get(i).getDimensioin();for(int j=0;j<dims.length;j++){double temp=Math.pow((dims[j]-this.dimension[j]),2);sum=sum+temp;}}return Math.sqrt(sum);}public double testEuclideanDistance(Medoid c) {double sum=0.0;double[] cDim=c.getDimensioin();for(int i=0;i<dimension.length;i++){double temp=Math.pow((dimension[i]-cDim[i]),2);sum=sum+temp;}return Math.sqrt(sum);}public double[] getDimensioin() {return this.dimension;}public Cluster getCluster() {return this.cluster;}public double getCurrentEuDt() {return this.euDt;}public String getPointName() {return this.pointName;}
}

public class Medoid{private double dimension[]; // 質點的維度private Cluster cluster; //所屬類簇private double etdDisSum;//Medoid到本類簇中所有的歐式距離之和public String toString() {String result ="  [";DecimalFormat decimalFormat=new DecimalFormat("0.000000");for (int i = 0; i < dimension.length; i++) {result += decimalFormat.format(dimension[i]) + " ";}return result.trim()+"] clusterId: "+cluster.clusterName;}public Medoid(double dimension[]) {this.dimension = dimension;}public void setCluster(Cluster c) {this.cluster = c;}public double[] getDimensioin() {return this.dimension;}public Cluster getCluster() {return this.cluster;}public void calcMedoid() {// 取代價最小的點calcEtdDisSum();double minEucDisSum = this.etdDisSum;ArrayList<DataPoint> dps = this.cluster.getDataPoints();for (int i = 0; i < dps.size(); i++) {double tempeucDisSum = dps.get(i).calEuclideanDistanceSum();if (tempeucDisSum < minEucDisSum) {dimension = dps.get(i).getDimensioin();minEucDisSum=tempeucDisSum;}}}// 計算該Medoid到同類簇所有樣本點的歐斯距離和private void calcEtdDisSum() {double sum=0.0;Cluster cluster=this.getCluster();ArrayList<DataPoint> dataPoints=cluster.getDataPoints();for(int i=0;i<dataPoints.size();i++){double[] dims=dataPoints.get(i).getDimensioin();for(int j=0;j<dims.length;j++){double temp=Math.abs(dims[j]-this.dimension[j]);sum=sum+temp;}}etdDisSum= sum;}
}

public class TestMain {public static List<double[]> readTxt(String fileName){List<double[]> list=new ArrayList<>();try {File filename = new File(fileName); // 讀取input.txt文件InputStreamReader reader = new InputStreamReader(new FileInputStream(filename)); // 建立一個輸入流對象readerBufferedReader br = new BufferedReader(reader);String line = "";line = br.readLine();while (true) {line = br.readLine();if(line==null) break;String[] temp=line.split(",");double[] c=new double[temp.length];for(int i=0;i<temp.length;i++){c[i]=Float.parseFloat(temp[i]);}list.add(c);}} catch (Exception e) {e.printStackTrace();}return list;}public static void writeTxt(String content){try { // 防止文件建立或讀取失敗，用catch捕捉錯誤并打印，也可以throw/* 讀入TXT文件 */File writename = new File("src/km/output.txt"); // 相對路徑，如果沒有則要建立一個新的output。txt文件BufferedWriter out = new BufferedWriter(new FileWriter(writename));out.write(content); // \r\n即為換行out.flush(); // 把緩存區內容壓入文件out.close(); // 最后記得關閉文件} catch (Exception e) {e.printStackTrace();}}public static void main (String args[]){ArrayList<DataPoint> dataPoints = new ArrayList<DataPoint>();List<double[]> list=readTxt("src/km/t2.txt");for(int i=0;i<list.size();i++){dataPoints.add(new DataPoint(list.get(i),String.valueOf(i)));}long s=System.currentTimeMillis();ClusterAnalysis ca=new ClusterAnalysis(5,200,dataPoints,5);double[][] cen={list.get(22),list.get(3),list.get(45),list.get(156),list.get(96)};ca.startAnalysis(cen);StringBuilder stringBuilder=new StringBuilder();ArrayList<DataPoint>[] v = ca.getClusterOutput();System.out.println("K-中心點聚類算法運行時間"+(System.currentTimeMillis()-s)+"ms");for (int ii=0; ii<v.length; ii++){ArrayList tempV = v[ii];stringBuilder.append("\n").append("-----------Cluster").append(ii).append("---------").append("\n");stringBuilder.append("Mid_Point:  ").append(ca.clusters[ii].getMedoid()).append("  Points_num:  "+ca.clusters[ii].getDataPoints().size()).append("\n");System.out.println(ca.clusters[ii].getMedoid()+"  Points_num:  "+ca.clusters[ii].getDataPoints().size());Iterator iter = tempV.iterator();while(iter.hasNext()){DataPoint dpTemp = (DataPoint)iter.next();stringBuilder.append(dpTemp).append("\n");}}writeTxt(stringBuilder.toString());}}