K均值聚类算法的Java版实现代码示例

1.简介

K均值聚类算法是先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

2.什么是聚类

聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程，聚类就是一种发现这种内在结构的技术，聚类技术经常被称为无监督学习。

3.什么是k均值聚类

k均值聚类是最著名的划分聚类算法，由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k，k由用户指定，k均值算法根据某个距离函数反复把数据分入k个聚类中。

4.实现

Java代码如下：

package org.alGorithm;import java.util.ArrayList;import java.util.Random;public class Kmeans {private int k;// 分成多少簇 private int m;// 迭代次数 private int dataSetLength;// 数据集元素个数，即数据集的长度 private ArrayList<float[]> dataSet;// 数据集链表 private ArrayList<float[]> center;// 中心链表 private ArrayList<ArrayList<float[]>> cluster;// 簇 private ArrayList<float> jc;// 误差平方和，k越接近dataSetLength，误差越小 private Random random;public void setDataSet(ArrayList<float[]> dataSet) {this.dataSet = dataSet;}public ArrayList<ArrayList<float[]>> getCluster() {return cluster;}public Kmeans(int k) {if (k <= 0) {k = 1;}this.k = k;}private void init() {m = 0;random = new Random();if (dataSet == null || dataSet.size() == 0) {initDataSet();}dataSetLength = dataSet.size();if (k > dataSetLength) {k = dataSetLength;}center = initCenters();cluster = initCluster();jc = new ArrayList<float>();}private void initDataSet() {dataSet = new ArrayList<float[]>();// 其中{6,3}是一样的，所以长度为15的数据集分成14簇和15簇的误差都为0 float[][] dataSetArray = new float[][] { { 8, 2 }, { 3, 4 }, { 2, 5 },         { 4, 2 }, { 7, 3 }, { 6, 2 }, { 4, 7 }, { 6, 3 }, { 5, 3 },         { 6, 3 }, { 6, 9 }, { 1, 6 }, { 3, 9 }, { 4, 1 }, { 8, 6 } };for (int i = 0; i < dataSetArray.length; i++) {dataSet.add(dataSetArray[i]);}}private ArrayList<float[]> initCenters() {ArrayList<float[]> center = new ArrayList<float[]>();int[] randoms = new int[k];Boolean flag;int temp = random.nextint(dataSetLength);randoms[0] = temp;for (int i = 1; i < k; i++) {flag = true;while (flag) {temp = random.nextint(dataSetLength);int j = 0;// 不清楚for循环导致j无法加1 // for(j=0;j<i;++j) // { // if(temp==randoms[j]); // { // break; // } // } while (j < i) {if (temp == randoms[j]) {break;}j++;}if (j == i) {flag = false;}}randoms[i] = temp;}// 测试随机数生成情况 // for(int i=0;i<k;i++) // { // System.out.println("test1:randoms["+i+"]="+randoms[i]); // } // System.out.println(); for (int i = 0; i < k; i++) {center.add(dataSet.get(randoms[i]));// 生成初始化中心链表}return center;}private ArrayList<ArrayList<float[]>> initCluster() {ArrayList<ArrayList<float[]>> cluster = new ArrayList<ArrayList<float[]>>();for (int i = 0; i < k; i++) {cluster.add(new ArrayList<float[]>());}return cluster;}private float distance(float[] element, float[] center) {float distance = 0.0f;float x = element[0] - center[0];float y = element[1] - center[1];float z = x * x + y * y;distance = (float) Math.sqrt(z);return distance;}private int minDistance(float[] distance) {float minDistance = distance[0];int minLocation = 0;for (int i = 1; i < distance.length; i++) {if (distance[i] < minDistance) {minDistance = distance[i];minLocation = i;} else if (distance[i] == minDistance) // 如果相等，随机返回一个位置 {if (random.nextint(10) < 5) {minLocation = i;}}}return minLocation;}private void clusterSet() {float[] distance = new float[k];for (int i = 0; i < dataSetLength; i++) {for (int j = 0; j < k; j++) {distance[j] = distance(dataSet.get(i), center.get(j));// System.out.println("test2:"+"dataSet["+i+"],center["+j+"],distance="+distance[j]);}int minLocation = minDistance(distance);// System.out.println("test3:"+"dataSet["+i+"],minLocation="+minLocation); // System.out.println(); cluster.get(minLocation).add(dataSet.get(i));// 核心，将当前元素放到最小距离中心相关的簇中}}private float errorSquare(float[] element, float[] center) {float x = element[0] - center[0];float y = element[1] - center[1];float errSquare = x * x + y * y;return errSquare;}private void countRule() {float jcF = 0;for (int i = 0; i < cluster.size(); i++) {for (int j = 0; j < cluster.get(i).size(); j++) {jcF += errorSquare(cluster.get(i).get(j), center.get(i));}}jc.add(jcF);}private void setNewCenter() {for (int i = 0; i < k; i++) {int n = cluster.get(i).size();if (n != 0) {float[] newCenter = { 0, 0 };for (int j = 0; j < n; j++) {newCenter[0] += cluster.get(i).get(j)[0];newCenter[1] += cluster.get(i).get(j)[1];}// 设置一个平均值 newCenter[0] = newCenter[0] / n;newCenter[1] = newCenter[1] / n;center.set(i, newCenter);}}}public void printDataArray(ArrayList<float[]> dataArray,       String dataArrayName) {for (int i = 0; i < dataArray.size(); i++) {System.out.println("print:" + dataArrayName + "[" + i + "]={"           + dataArray.get(i)[0] + "," + dataArray.get(i)[1] + "}");}System.out.println("===================================");}private void kmeans() {init();// printDataArray(dataSet,"initDataSet"); // printDataArray(center,"initCenter"); // 循环分组，直到误差不变为止 while (true) {clusterSet();// for(int i=0;i<cluster.size();i++) // { // printDataArray(cluster.get(i),"cluster["+i+"]"); // } countRule();// System.out.println("count:"+"jc["+m+"]="+jc.get(m)); // System.out.println(); // 误差不变了，分组完成 if (m != 0) {if (jc.get(m) - jc.get(m - 1) == 0) {break;}}setNewCenter();// printDataArray(center,"newCenter"); m++;cluster.clear();cluster = initCluster();}// System.out.println("note:the times of repeat:m="+m);//输出迭代次数}public void execute() {long startTime = System.currentTimeMillis();System.out.println("kmeans begins");kmeans();long endTime = System.currentTimeMillis();System.out.println("kmeans running time=" + (endTime - startTime)         + "ms");System.out.println("kmeans ends");System.out.println();}}