package org.algorithm;
import java.util.ArrayList;
import java.util.Random;
/** 
 * K均值聚類算法 
 */
public class Kmeans {
	private int k;
	// 分成多少簇 
	private int m;
	// 迭代次數(shù) 
	private int dataSetLength;
	// 數(shù)據(jù)集元素個(gè)數(shù)，即數(shù)據(jù)集的長度 
	private ArrayList<float[]> dataSet;
	// 數(shù)據(jù)集鏈表 
	private ArrayList<float[]> center;
	// 中心鏈表 
	private ArrayList<ArrayList<float[]>> cluster;
	// 簇 
	private ArrayList<float> jc;
	// 誤差平方和，k越接近dataSetLength，誤差越小 
	private Random random;
	/** 
   * 設(shè)置需分組的原始數(shù)據(jù)集 
   * 
   * @param dataSet 
   */
	public void setDataSet(ArrayList<float[]> dataSet) {
		this.dataSet = dataSet;
	}
	/** 
   * 獲取結(jié)果分組 
   * 
   * @return 結(jié)果集 
   */
	public ArrayList<ArrayList<float[]>> getCluster() {
		return cluster;
	}
	/** 
   * 構(gòu)造函數(shù)，傳入需要分成的簇?cái)?shù)量 
   * 
   * @param k 
   *      簇?cái)?shù)量,若k<=0時(shí)，設(shè)置為1，若k大于數(shù)據(jù)源的長度時(shí)，置為數(shù)據(jù)源的長度 
   */
	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>();
	}
	/** 
   * 如果調(diào)用者未初始化數(shù)據(jù)集，則采用內(nèi)部測(cè)試數(shù)據(jù)集 
   */
	private void initDataSet() {
		dataSet = new ArrayList<float[]>();
		// 其中{6,3}是一樣的，所以長度為15的數(shù)據(jù)集分成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]);
		}
	}
	/** 
   * 初始化中心數(shù)據(jù)鏈表，分成多少簇就有多少個(gè)中心點(diǎn) 
   * 
   * @return 中心點(diǎn)集 
   */
	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循環(huán)導(dǎo)致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;
		}
		// 測(cè)試隨機(jī)數(shù)生成情況 
		// 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 一個(gè)分為k簇的空數(shù)據(jù)的簇集合 
   */
	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;
	}
	/** 
   * 計(jì)算兩個(gè)點(diǎn)之間的距離 
   * 
   * @param element 
   *      點(diǎn)1 
   * @param center 
   *      點(diǎn)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 
   *      距離數(shù)組 
   * @return 最小距離在距離數(shù)組中的位置 
   */
	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) // 如果相等，隨機(jī)返回一個(gè)位置 
			{
				if (random.nextint(10) < 5) {
					minLocation = i;
				}
			}
		}
		return minLocation;
	}
	/** 
   * 核心，將當(dāng)前元素放到最小距離中心相關(guān)的簇中 
   */
	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));
			// 核心，將當(dāng)前元素放到最小距離中心相關(guān)的簇中
		}
	}
	/** 
   * 求兩點(diǎn)誤差平方的方法 
   * 
   * @param element 
   *      點(diǎn)1 
   * @param center 
   *      點(diǎn)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;
	}
	/** 
   * 計(jì)算誤差平方和準(zhǔn)則函數(shù)方法 
   */
	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);
	}
	/** 
   * 設(shè)置新的簇中心方法 
   */
	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];
				}
				// 設(shè)置一個(gè)平均值 
				newCenter[0] = newCenter[0] / n;
				newCenter[1] = newCenter[1] / n;
				center.set(i, newCenter);
			}
		}
	}
	/** 
   * 打印數(shù)據(jù)，測(cè)試用 
   * 
   * @param dataArray 
   *      數(shù)據(jù)集 
   * @param dataArrayName 
   *      數(shù)據(jù)集名稱 
   */
	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"); 
		// 循環(huán)分組，直到誤差不變?yōu)橹?
		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);//輸出迭代次數(shù)
	}
	/** 
   * 執(zhí)行算法 
   */
	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) 
	  {
		//初始化一個(gè)Kmean對(duì)象，將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});
		//設(shè)置原始數(shù)據(jù)集 
		k.setDataSet(dataSet);
		//執(zhí)行算法 
		k.execute();
		//得到聚類結(jié)果 
		ArrayList<ArrayList<float[]>> cluster=k.getCluster();
		//查看結(jié)果 
		for (int i=0;i<cluster.size();i++) 
		    {
			k.printDataArray(cluster.get(i), "cluster["+i+"]");
		}
	}
}