k-means均值聚类

###k-均值聚类###

本质上是一个迭代算法，需要多个map/reduce阶段，需要根据不同的质心执行多次，直至其收敛，通过多次迭代相同的mapreduce找到最优的簇。

基本上来说，再给定k大于0和一个包括需要聚类的N个d-维对象集合.

- 聚类是将N个d-维对象分组为k个类似对象簇的过程

- 同一个簇中的对象彼此相似，而不同簇中的对象彼此相异

总的来说，k-means是一个基于距离的聚类算法：比如找出共同行为的一组行为产生者或根据文档内容的相似对文档完成聚类.

###案例分析###

k-means的首要问题：如何确定k值（由输入数据生成多少个组或簇）？那么具体的工作如下：提供一个包含N个d-维点和希望的簇数K作为输入，这里面我们会考虑欧氏空间中的点（k-means可以适用于任何空间），

p1=（a11，a12，…,a1d）

p2=（a21，a22，…,a2d）

…

pn=（an1，an2，…,and）

若是在2-维环境，上面对应的数据即变为每行表示一个点（x，y）

p1=（1，1）

p2=（2，1）

p3=（1，2）

p4=（5，5）

p5=（6，5）

p6=（5，6）

p7=（7，7）

p8=（9，6）

这里面我们选择k个簇质心（初始化簇心的方法很多，最简单的一种：从n个点的样本中随机选择k个点），接下来通过对输入集合中各个点到这k个中心点的距离，然后将各个点分配到与其聚类最近的簇中心，在完成所有对象的分配，重新计算k个质心位置，下面就反复迭代直到簇质心不再变化或变化非常小（重复前面两个过程 计算距离分配簇心，在计算质心位置）

###结论###

从根本来说，k-means是一种数据挖掘算法的无监督学习。根据对象的属性或特性将N个对象聚类、分类或分组到K个组；我们通常做法让数据与相应簇质心间距离的平方和最小：将｛X1，X2，…,Xn｝划分为K个簇｛C1，C2，…Cn｝，找出这些簇的位置€I(i=1,2,3...,k)使得数据点到簇质心的距离最小

###应用###

预测类似购买行为、类似访问模式分组日志聚类、保险欺诈行为

k-means距离函数

欧氏距离、曼哈顿距离、内积空间、最大模、自定义距离函数

、、、java欧氏距离

public class EuclideanDistance｛

public static double calculateDistance（Vector center，Vector data）｛

double sum=0.0；

int length=data.length；

for（int i=0；i<length;I++){

sum+=Math.pow((center[i]-data[i]),2.0);

}

return Math.sqrt(sum);

｝

｝

、、、