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

package org.algorithm;import java.util.ArrayList;import java.util.Random;/**  * K均值聚类算法  */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;	/**    * 设置需分组的原始数据集    *    * @param dataSet    */	public void setDataSet(ArrayList<float[]> dataSet) {		this.dataSet = dataSet;	}	/**    * 获取结果分组    *    * @return 结果集    */	public ArrayList<ArrayList<float[]>> getCluster() {		return cluster;	}	/**    * 构造函数，传入需要分成的簇数量    *    * @param k    *      簇数量,若k<=0时，设置为1，若k大于数据源的长度时，置为数据源的长度    */	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]);		}	}	/**    * 初始化中心数据链表，分成多少簇就有多少个中心点    *    * @return 中心点集    */	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;	}	/**    * 初始化簇集合    *    * @return 一个分为k簇的空数据的簇集合    */	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;	}	/**    * 计算两个点之间的距离    *    * @param element    *      点1    * @param center    *      点2    * @return 距离    */	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;	}	/**    * 获取距离集合中最小距离的位置    *    * @param distance    *      距离数组    * @return 最小距离在距离数组中的位置    */	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));			// 核心，将当前元素放到最小距离中心相关的簇中		}	}	/**    * 求两点误差平方的方法    *    * @param element    *      点1    * @param center    *      点2    * @return 误差平方    */	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);			}		}	}	/**    * 打印数据，测试用    *    * @param dataArray    *      数据集    * @param dataArrayName    *      数据集名称    */	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("===================================");	}	/**    * Kmeans算法核心过程方法    */	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();	}}

package org.test;import java.util.ArrayList;import org.algorithm.Kmeans;public class KmeansTest {	public static void main(String[] args) 	  {		//初始化一个Kmean对象，将k置为10 		Kmeans k=new Kmeans(10);		ArrayList<float[]> dataSet=new ArrayList<float[]>();		dataSet.add(new float[]{1,2});		dataSet.add(new float[]{3,3});		dataSet.add(new float[]{3,4});		dataSet.add(new float[]{5,6});		dataSet.add(new float[]{8,9});		dataSet.add(new float[]{4,5});		dataSet.add(new float[]{6,4});		dataSet.add(new float[]{3,9});		dataSet.add(new float[]{5,9});		dataSet.add(new float[]{4,2});		dataSet.add(new float[]{1,9});		dataSet.add(new float[]{7,8});		//设置原始数据集 		k.setDataSet(dataSet);		//执行算法 		k.execute();		//得到聚类结果 		ArrayList<ArrayList<float[]>> cluster=k.getCluster();		//查看结果 		for (int i=0;i<cluster.size();i++) 		    {			k.printDataArray(cluster.get(i), "cluster["+i+"]");		}	}}