山东大学 机器学习 K-means实验

K-means算法设计与实现

编程语言

C，C++，Java或者学过的其它编程语言

实验数据介绍

红酒数据集（Wine Data Set）http://archive.ics.uci.edu/ml/datasets/Wine

共178个数据，每个数据特征为13维

13个特征分别为：（13个化学成分，每个成分取值为实数）

1)  Alcohol

2)  Malic acid

3)  Ash

4)  Alcalinity of ash  

5)  Magnesium

6)  Total phenols

7)  Flavanoids

8)  Nonflavanoid phenols

9)  Proanthocyanins

10)  Color intensity

11)  Hue

12)  OD280/OD315 of diluted wines

13)  Proline  

实验完成要求

1. 编程实现K-means算法，并在红酒数据集上运行。
2. 设置不同K值，不同初始中心，在红酒数据集上进行实验比较。
3. 分析k-means的优缺点，并对其中一个或几个缺点进行改进。
4. 演示实验并提交代码，统计分析实验结果并上交实验报告；

实验步骤： 

1. 根据k均值算法的流程，首先实现样本的输入与随机打乱，定义Wine类对象，设置K值等准备工作。
2. 根据K的值选取样本作为中心，并根据距离关系划分到不同的簇中。
3. 根据划分样本，计算均值作为新的划分值。
4. 递归调用，直至依据停止更新，输出各中心点的特征值，以及属于该簇的样本数目。
5. 改变K值，观察。

代码：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Wine {
	private double[] data;
	public Wine(double[] data) {
		this.data = data;
	}
	public double[] getData() {
		return data;
	}
}
public class Kmeans {
	private Wine[] kCentralPoints;//保存K个划分的属性值
	private List<Wine>[] wineCluster;//保存分类后的wine对象
	private int K;
	private List<Wine> wineSet;//全体数据集合
	DecimalFormat df = new DecimalFormat("0.00");//用来格式化输出  
	
	public void inputdata(String file_path) {
		wineSet=new ArrayList<>();
		try {
			BufferedReader reader=new BufferedReader(new FileReader(new File(file_path)));
			String s=null;
			//逐行读取
			while((s=reader.readLine())!=null){
				String[] data_string = s.substring(2).split(",");//第一个值是类别，应剔除
				double[] data_double = new double[data_string.length];
				for(int i = 0;i < data_string.length;i++) {
					data_double[i] = Double.parseDouble(data_string[i]);
				} 
				wineSet.add(new Wine(data_double));
			}
			Collections.shuffle(wineSet);//打乱
			reader.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	@SuppressWarnings("unchecked")
	public void setK(int k){
		this.K=k;
		kCentralPoints=new Wine[k];
		wineCluster=new List[k];
		for (int i = 0; i < k; i++) {
			wineCluster[i]=new ArrayList<>();
		}
	}
	private double getDistance(Wine a,Wine b){
		double distance=0;
		double[] data_a = a.getData();
		double[] data_b = b.getData();
		for (int i = 0; i < data_a.length; i++) {
			distance+=Math.pow(data_a[i]-data_b[i], 2);
		}
		return Math.sqrt(distance);
	}	
	public void outputresult(){
		for(int i=0;i<K;i++){
			kCentralPoints[i]=wineSet.get(i);
		}
		kmeans();
		System.out.println(K+"个中心点的取值及此时的划分大小如下：");
		for (int i = 0; i < K; i++) {
			double[] cpdata=kCentralPoints[i].getData();
			System.out.printf("%4s","["+wineCluster[i].size()+"]");
			System.out.print("[");
			for (int j = 0; j < cpdata.length; j++) {
				System.out.printf("%9s",df.format(cpdata[j]));
			}
			System.out.println("]");
		}
	}
	@SuppressWarnings("unchecked")
	private void kmeans() {
		boolean finish = true;
		for(int i = 0;i < wineSet.size();i++){
			int belongTo = 0;
			double minDistance = Double.MAX_VALUE;
			Wine currentWine = wineSet.get(i);
			//与K个中心比较，距离最近的划分到该集合
			for (int j = 0; j < K; j++) {
				double currentDistance = getDistance(currentWine, kCentralPoints[j]);
				if (currentDistance<minDistance) {
					belongTo=j;
					minDistance=currentDistance;
				}
			}
			wineCluster[belongTo].add(currentWine);
		}
		//取该聚类的样本每一属性的平均值作为新的样本聚集中心
		for (int i = 0; i < K; i++) {
			double [] data_now = kCentralPoints[i].getData();
			double [] data_update = new double[data_now.length];
			for (int index = 0; index < data_now.length; index++) {
				double value=0;
				for(Wine awine : wineCluster[i])
					value += awine.getData()[index];	
				value /= wineCluster[i].size();
				data_update[index]=value;
				if(data_now[index]!=value) {
					finish=false;
				}
			}
			kCentralPoints[i] = new Wine(data_update);
		}
		if (!finish) {
			wineCluster=new List[K];//初始化
			for (int i = 0; i < K; i++) {
				wineCluster[i]=new ArrayList<>();
			}
			kmeans();
		}
	}
	public static void main(String[]args){
		Kmeans aKmeans=new Kmeans();
		aKmeans.inputdata("Wine dataset.txt");
		aKmeans.setK(5);
		aKmeans.outputresult();
	}
}