【机器学习】--Kmeans从初识到应用

一.前述

Kmeans算法一般在数据分析前期使用，选取适当的k，将数据分类后，然后分类研究不同聚类下数据的特点。

Kmeans算法是一种无监督的算法。

二.概念及原理

Kmeans原理：

随机选取k个中心点

      2 遍历所有数据，将每个数据划分到最近的中心点中

每个聚类的平均值，并作为新的中心点

      4 重复2-3，直到这k个中线点不再变化（收敛了），或执行了足够多的迭代。

二分Kmeans原理:

为了得到k个簇，将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇。

比如要分成5个组，第一次分裂产生2个组，然后从这2个组中选一个目标函数产生的误差比较大的，分裂这个组产生2个，这样加上开始那1个就有3个组了，然后再从这3个组里选一个分裂，产生4个组，重复此过程，产生5个组。这算是一中基本求精的思想。二分k均值不太受初始化的困扰，因为它执行了多次二分试验并选取具有最小误差的试验结果，还因为每步只有两个质心。

Kmeans++原理：

k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。

1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
2. 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3. 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大（该绿化选择）
4. 重复2和3直到k个聚类中心被选出来
5. 利用这k个初始的聚类中心来运行标准的k-means算法。

 样本点之间的相似度距离计算：

1.欧氏距离相似度（常用！！！）

2.Jaccard相似度（用于比较样本之间的相似性，系数值越大表示值越高）

3.余弦相似度

余弦相似度值在[-1,1]之间，值越趋近于1代表越相近，越趋近于-1，代表越相反，接近于0，代表两个向量正交。

常用计算文本相似性！！！

4.Pearson相似度

5.相对熵(K-L距离)

 总结：

对于高维空间点之间的度量，用欧氏距离。

对于集合度量Jaccard相似度。

     对于自然语言处理用余弦相似度。

Pearson相似度

利用Canopy计算初始类簇中心点。

步骤：

1.首先定义两个距离T1和T2，T1>T2.从初始的点的集合S中随机移除一个点P，然后对于还在S中的每个点I，计算该点I与点P的距离。

2.如果距离小于T1，则将点I加入到点P所代表的Canopy中，如果距离小于T2，则将点I从集合S中移除，并将点I加入到点P所代表的Canopy中。

3.迭代完一次之后，重新从集合S中随机选择一个点作为新的点P，然后重复执行以上步骤。

图示：

总结：与中心的距离大于T1时，这些点就不会被归入到中心所在的这个canopy类中。然当距离小于T1大于T2时，这些点会被归入到该中心所在的canopy中，但是它们并不会从D中被移除，也就是说，它们将会参与到下一轮的聚类过程中，成为新的canopy类的中心或者成员。亦即，两个Canopy类中有些成员是重叠的。而当距离小于T2的时候，这些点就会被归入到该中心的canopy类中，而且会从D中被移除，也就是不会参加下一次的聚类过程了。

层次聚类

层次聚类，是一种很直观的算法。顾名思义就是要一层一层地进行聚类，可以从下而上地把小的cluster合并聚集，也可以从上而下地将大的cluster进行分割。似乎一般用得比较多的是从下而上地聚集，因此这里我就只介绍这一种。   所谓从下而上地合并cluster，具体而言，就是每次找到距离最短的两个cluster，然后进行合并成一个大的cluster，直到全部合并为一个cluster。整个过程就是建立一个树结构，类似于下图。

一开始每个数据点独自作为一个类，它们的距离就是这两个点之间的距离。而对于包含不止一个数据点的cluster，就可以选择多种方法了。最常用的，就是average-linkage，即计算两个cluster各自数据点的两两距离的平均值。