[机器学习]无监督学习——K-Means算法_k-means 算法的作用

1.K-Means算法的定义。
k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
2.K-Means在无监督学习中发挥的作用
无监督学习中常用的K-Means算法是一种聚类算法，所谓聚类，即根据相似性原则，将具有较高相似度的数据对象划分至同一类簇，将具有较高相异度的数据对象划分至不同类簇。而与监督学习不同的是，无监督学习的样本不带有标记。而分类过程为有监督过程，即存在有先验知识的训练数据集。K-Means算法将数据可以自动进行分类。
3.K-Means算法的实现步骤

3.1.随机的初始化类簇中心（根据需求假设由K个类簇中心 k∈N，K<M(样本数量)）
用u1,u2,…uk来表示随机选择的K的类簇中心
3.2.遍历数据集计算出每个样本最近的类簇中心

for every x(i) 1<=i<=m
	for k=1;k<=K;k++
	compute min dist（x(i),uk）计算出x(i)到K个类族最小的距离
 c(i) = k                                  把K的值赋给c(i) 注：x(i)与c(i)是一个i
1
2
3
4

3.3更改类簇中心
计算出属于k个簇样本的平均值，重新赋值给uk。

 for (k=1;k<=K;k++)
    for(i=1;i<=m;i++){
    	int count = 0;
    	if(c(i) = k){
    		u[k] = u[k] +x(i);
    		count++;}
    	 			}
    	 u[k] = u[k]/count;
    }
1
2
3
4
5
6
7
8
9

3.4.重复3.2，3.3步骤。这样大致就可以得到k个簇。
4.代价函数
4.1Uc(i)的定义：每一个样本与对应的簇的中心点的值
4.2代价函数：

for i=1;i<=m;i++
	计算x(i)与Uc(i)的距离和的平均值
1
2

4.3代价函数优化
通过3.2步骤 找到新的一组c(1)…c(m)来min J
通过3.3步骤 找到新的一组u1…uk来 min J

5.注意
5.1.随机初始化，避免得到局部最优解

5.2 运行算法m次，找出使代价函数K个最小的类簇中心

6如何选择的K值
6.1根据实际需求来选择
6.2根据拐点定理 来选择拐点的k值