Standard Kmean Cluster的实现[Java]
Kmean Cluster是一种机器学习中常用的无监督分析方法，例如，在最近的项目中，要从数以百万、千万计的高维图像特征中提取具有代表性的视觉词，就用到了此类技术。
Kmean并不是一种高效的算法，理论可以证明，在欧几里得空间中的Kmean问题是NP-Hard（即使聚类数仅为2）。假设单个向量维度为d，向量数为n，目标聚类数为k，则算法的时间复杂度=n^(dk+1)*logn。
kmean的示意图如下：
一些启发式的算法对Standard Kmean的效率进行了优化，常见的包括：
基于最大期望的算法（EM algorithm）：采用概率的方式将输入向量分配到各个聚类当中（而非Standard Kmean中的绝对分配），并且采用高斯分布代替Standard Kmean中的算术平均值计算聚类中心。Kmean++：通过选取初始聚类集合来达到更好的效果filtering algorithm：通过使用kd树来加速Kmean效率其它优化算法：诸如coresets、triangle inequ以及Escape local optima等算法
尽管如此，经典的Standard Kmean仍然是使用频率较高的聚类算法，在数据量不大或者demo阶段被广为使用，下面给出java实现的代码：
Standard Kmean在大数据量时其表现往往不尽如人意，后续我会附上kd random forest的优化算法
