数据挖掘-机器学习：Kmean聚类思想

一、概述 

        数据聚类是对于静态数据分析的一门技术，在许多领域内都被广泛地应用，包括机器学习、数据挖掘、模式识别、图像分析、信息检索以及生物信息等。聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集，这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离等。

         K-means是一种基于距离的迭代式算法[1]。它将n个观察实例分类到k个聚类中，以使得每个观察实例距离它所在的聚类的中心点比其他的聚类中心点的距离更小。

 

其中，距离的计算方式可以是欧式距离（2-norm distance）：

        二维的公式

          d = sqrt((x1-x2)^2+(y1-y2)^2)

         三维的公式

      d=sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2)

 

     或者是曼哈顿距离（Manhattan distance,1-norm distance）

        N维的空间

        其中两点的曼哈顿距离为：|x1-y1|+|x2-y2|+|x3-y3|+|x4-y4|+……+|xn-yn|     

        另外，（两点的坐标分别为（x1,x2,……,xn）、（y1,y2,……,yn））

 

二、思想

    1.简单的K-means

      1）所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，我们就有了一个初始的聚类结果，这是一次迭代的过程。

      2）我们每个聚类中心都至少有一个观测实例，这样，我们可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。然后继续运行2）。

      3）如此往复2），直到前后两次迭代得到的聚类中心点一模一样。

这样，算法就稳定了，这样得到的k个聚类中心，和距离它们最近的观测点构成k个聚类，就是我们要的结果。

    2.改进的K-means：k-d tree

      把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。

上面的表述中，有三步：

      1)选择特征的方法

      计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。

      2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。

      第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。

      替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。

      3)达到什么条件算法结束

      实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。

 

    3.改进的K-means：ball tree

 

三、实现

     java实现：