1 package com.data.algorithm;  2   3 import java.util.ArrayList;  4 import java.util.List;  5   6 /**  7  * *********************************************************  8  * <p/>  9  * Author:     XiJun.Gong 10  * Date:       2017-01-17 15:57 11  * Version:    default 1.0.0 12  * Class description： 13  * <p/> 14  * ********************************************************* 15  */ 16 public class Kmeans { 17     private final double exp = 1e-6; 18  19     private List<KMeanData> topk; 20  21     public List<KMeanData> getTopk() { 22         return topk; 23     } 24  25     public void setTopk(List<KMeanData> topk) { 26         this.topk = topk; 27     } 28  29     class KMeanData { 30  31         private float x;    //x坐标 32         private float y;    //y坐标 33         private int flag;   //隶属于哪一个簇 34  35         public int getFlag() { 36             return flag; 37         } 38  39         public void setFlag(int flag) { 40             this.flag = flag; 41         } 42  43         public float getX() { 44             return x; 45         } 46  47         public void setX(float x) { 48             this.x = x; 49         } 50  51         public float getY() { 52             return y; 53         } 54  55         public void setY(float y) { 56             this.y = y; 57         } 58     } 59  60     public boolean max(float a, float b) { 61         return a > b + exp ? true : false; 62     } 63  64     public float distance(KMeanData a, KMeanData b) { 65  66         return (float) Math.sqrt(Math.pow(a.getX() - b.getX(), 2) 67                 + Math.pow(a.getY() - b.getY(), 2)); 68     } 69  70     public boolean Kequal(KMeanData a, KMeanData b) { 71         if (Math.abs(a.getY() - b.getY()) < exp && Math.abs(a.getX() - b.getX()) < exp) 72             return true; 73         return false; 74     } 75  76     public KMeanData[] produce(int size, int range) { 77         KMeanData[] kmData = http://www.mamicode.com/new KMeanData[size]; 78         for (int i = 0; i < size; i++) { 79             kmData[i] = new KMeanData(); 80             kmData[i].setX((float) (Math.random() * range)); 81             kmData[i].setY(((float) Math.random() * range)); 82             kmData[i].setFlag(0); 83         } 84         return kmData; 85     } 86  87     public void kprint(KMeanData[] data, final int k) { 88         for (int i = 1; i <= k; i++) { 89             System.out.println("第" + i + "簇集合: ( " + this.topk.get(i - 1).getX() + " , " + this.topk.get(i - 1).getY() + " )"); 90             for (int j = 0; j < data.length; j++) { 91                 if (data[j].getFlag() == i) { 92                     System.out.print("( " + data[j].getX() + " , " + data[j].getY() + " )"); 93                 } 94             } 95             System.out.println("\n"); 96         } 97     } 98  99     public KMeanData[] kmeans(KMeanData[] data, final int k) {100         if (null == data || data.length < 1) {101             System.out.println("data is empty");102             return null;103         }104         if (k > data.length) {105             System.out.println("k " + k + " is too larger than data size " + data.length);106             return null;107         }108        /*随机选取k个点*/109         topk = new ArrayList<KMeanData>();110         int stride = data.length / k;111         //均值步长取k的初始簇112         for (int i = 0; i < data.length; i += stride) {113             data[i].setFlag((i / stride) + 1);114             topk.add(data[i]);115         }116         //聚合117         while (true) {118             for (int i = 0; i < data.length; i++) {119                 float min = (float) 1e9, dist;120                 int pos = 0;121                 for (KMeanData kter : topk) {122                     if (!Kequal(kter, data[i]) && min > (dist = distance(data[i], kter))) {123                         min = dist;124                         pos = i;125                     }126                 }127                 data[pos].setFlag((i / stride) + 1);128             }129             //重新计算质心130             KMeanData[] ntopk = new KMeanData[k + 1];131             int[] kcnt = new int[k + 1];132             for (int i = 0; i < data.length; i++) {133                 kcnt[data[i].getFlag()]++;134                 ntopk[data[i].getFlag()] = new KMeanData();135                 ntopk[data[i].getFlag()].setX(ntopk[data[i].getFlag()].getX() + data[i].getX());136                 ntopk[data[i].getFlag()].setY(ntopk[data[i].getFlag()].getY() + data[i].getY());137             }138             for (int i = 1; i <= k; i++) {139                 ntopk[i].setX(ntopk[i].getX() / kcnt[i]);140             }141             //判断一下是否是已经收敛了142             boolean flag = false;143             for (int i = 0; i < k; i++) {144                 if (!Kequal(topk.get(i), ntopk[i + 1])) {145                     flag = true;146                     topk.set(i, ntopk[i + 1]);147                 }148             }149             if (!flag) break;150         }151         return data;152     }153 }

 1 package com.data.algorithm; 2  3  4 /** 5  * ********************************************************* 6  * <p/> 7  * Author:     XiJun.Gong 8  * Date:       2017-01-17 17:57 9  * Version:    default 1.0.010  * Class description：11  * <p/>12  * *********************************************************13  */14 public class Main {15     public static void main(String args[]) {16         Kmeans kmeans = new Kmeans();17         kmeans.kprint(kmeans.kmeans(kmeans.produce(100, 60), 10), 10);18     }19 }