K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
k-means 算法接受参数 k ；然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
假设要把样本集分为c个类别，算法描述如下：
（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式(即相似性度量方式：可以是欧式距离，可以是余弦相似度等，可参考https://www.jianshu.com/p/a0dfcdf07f18)。
k-Means的简单实现如下：
import java.util.LinkedList;
import java.util.List;
/**
* K-Means Clustering:
* step: 1. random choose k samples as center of each Clustering.
* step: 2. calculate distances of samples to each center,
* and cluster them into coresponding centers.
* step: 3.recalculate all centers by obtaining the centroid of each cluster.
* if all centers never change or several times have been iterated,
* stop the iteration and return results. Else continue step 2.
*
* @author QuanMaster 2018年1月24日 下午8:29:08
*
*/
public class Algorithm_kMeans {
//最大迭代次数。
public static final int MAX_ITER_TIMES = 10;
public Clusters kMeans(int k, List<DataNode> samples){
Clusters clusters = null;
if(samples.size() < k){
System.out.println("lack of samples!");
return clusters;
}
double[][] centers = new double[k][];
//初始化k个聚类的中心
for(int i = 0; i < k; i++){
centers[i] = samples.get(i).getFeatures();
}
for(int i = 0; i < MAX_ITER_TIMES; i++){
clusters = clusterWithCenters(centers, samples);
System.out.println("\n\nAfter " + (i+1) +"-th iterator:");
System.out.println(clusters);
if(!updateCenters(centers, clusters)) break;
}
return clusters;
}
/**
* cluster according to current centers.
*
* @param centers
* @param samples
* @return
*/
private Clusters clusterWithCenters(double[][] centers, List<DataNode> samples){
Clusters cluster = new Clusters(centers.length);
samples.forEach(s->{
double[] features = s.getFeatures();
double min = Double.MAX_VALUE;
int index = 0;
for(int i =0; i < centers.length; i++ ){
index = min > MLUtils.euclideanDistance(centers[i], features) ? i : index;
}
cluster.insertDataNodeIntoCluster(index, s);
});
return cluster;
}
/**
* update centers during each iterator.
*
* @param centers
* @param clusters
* @return
*/
private boolean updateCenters(double[][] centers, Clusters clusters){
boolean updated = false;
for(int i = 0; i < centers.length; i++){
if(!MLUtils.isSameArray(centers[i],reObtainCentroidForCluster(clusters.clusters[i])))
updated = true;
}
return updated;
}
/**
* 计算每个簇上的样本的平均值作为当前簇的几何中心。
* @param cluster
* @return
*/
private double[] reObtainCentroidForCluster(List<DataNode> cluster){
int dimension = cluster.get(0).getFeatures().length;
int clusterSize = cluster.size();
double[] newCentroid = new double[dimension];
cluster.forEach(node->{
double[] features = node.getFeatures();
for(int i=0; i < dimension; i++){
newCentroid[i] += features[i];
}
});
for(int i=0; i < dimension; i++){
newCentroid[i] /= clusterSize;
}
return newCentroid;
}
/**
* Object defined for Clustring results.
* @author zhaoshiquan 2018年1月24日 下午8:03:48
*
*/
class Clusters{
private int k = 1;
private List<DataNode>[] clusters;
Clusters(int k){
this.k = k;
this.clusters = new LinkedList[k];
}
public int getK() {
return k;
}
public void setK(int k) {
this.k = k;
}
public List<DataNode>[] getClusters() {
return clusters;
}
public void setClusters(List<DataNode>[] clusters) {
this.clusters = clusters;
}
@Override
public String toString() {
return "Clusters [k=" + k + ", clusters=" + clusters + "]";
}
public void insertDataNodeIntoCluster(int k, DataNode node){
this.clusters[k].add(node);
}
}
}
算法优点
K-Means聚类算法的优点主要集中在:
1.算法快速、简单;
2.对大数据集有较高的效率并且是可伸缩性的;
3.时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(nkt) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目。[1]
算法缺点
k-means 算法缺点
① 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献中，是根据方差分析理论，应用混合 F统计量来确定最佳分类数，并应用了模糊划分熵来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵的 RPCL 算法，并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。
② 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献 中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。
③ 从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
