机器学习之聚类算法(K-means)

    聚类(Clustering)是一种无监督的学习方法。主要是对大量未标注的数据集，按照内在相似性将数据集划分为多个类别，使得类别内的数据相似度较大而类别间的数据的相似度较小。

相似度度量

    样本之间的相似性可以通过样本在特征空间中的距离来度量，两个样本在特征空间中距离越小，则越相似，相似性越高，反之，相似性越低。接下来总结几种相似度度量方式。

闵可夫斯基距离

    闵可夫斯基距离不是一种距离，而是一组距离的定义，定义如下：

$$d(x,y)=\sqrt[p]{\sum_{i=1}^n|x_i-y_i|^p}$$

当$p=1$时，代表的是曼哈顿距离；当$p=2$时，代表的是欧式距离，当$p \to \infty$,代表的是切比雪夫距离。

欧式距离

    欧几里得度量（euclidean metric）（也称欧氏距离）指的是在$m$维空间中两个点之间的真实距离，定义在欧几里得空间中：

$$d(x,y)=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$$

曼哈顿距离

    曼哈顿距离的正式意义为L1-距离，也就是在欧几里得空间的固定直角坐标系上两点所想成的线段在轴上的投影距离综合：

$$d(x,y)=\sum_{i=1}^n|x_i-y_i|$$

杰卡德相似性度量

1. 杰卡德相似系数
       杰卡德相似系数是衡量两个集合相似度的一种指标，指的是两个集合$A$和$B$交集元素的个数在$A$和$B$并集中所占的比例，表示为： $$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$$
2. 杰卡德距离
       杰卡德距离正好和杰卡德相似系数相反，用来衡量两个集合的区分度。指的是两个集合中不同元素占所有元素的比例。 $$J_{\delta}(A,B)=1-J(A,B)$$

   余弦相似度

       乍一看，余弦好像和相似度并没有关系，夹角预先是衡量两个向量方向的差异，运用在机器学习中来衡量样本所在的特征空间之间的差异。 $$cos(\theta)=\frac{a·b}{|a||b|}$$ $cos(\theta)$越大，说明两个向量之间的夹角越小，反之亦然。

   Pearson相关系数

       在数据标准化($\mu=0,\sigma=1$)之后,Pearson相关系数等价于余弦相似度、欧氏距离，它是衡量特征向量之间相似度的一种方法。是对欧式距离的改进，它提供了对于变量取值范围不同的处理步骤。它将输出范围在-1到1之间，0代表无相关性，负值代表负相关，正值代表正相关。
   \begin{equation}\begin{split}\rho(x,y)&=\frac{E[(X-\mu_X)(Y-\mu_Y)]}{\sigma_X\sigma_Y}\\\\
   &=\frac{E[(X-\mu_X)(Y-\mu_Y)]}{\sqrt\sum_{i=1}^n(X_i-\mu_X)^2\sqrt\sum_{i=1}^n(Y_i-\mu_Y)^2}\end{split}\end{equation}

   相对熵

       相对熵，又称为KL散度、信息增益。在信息论中，是衡量基于$Q$分布的编码来编码来自$P$分布的样本平均所需的额外的bit个数。在机器学习领域则是是用来衡量两个分布之间的相似程度。对于离散随机变量，其概率分布$P$和$Q$的KL散度可以定义为： $$D_{KL}(P||Q)=-\sum_iP(i)ln\frac{Q(i)}{P(i)}$$ 注意：$D_{KL}(P||Q) \neq D_{KL}(Q||P)$
   若$P$是数据的真实概率分布，$Q$式由数据计算得到的概率分布。机器学习的目的是希望$Q$尽可能地逼近$P$，从而使相对熵为0。只有二者之间略有差异，其值就会大于0。

   K-means

       K-means算法属于聚类算法，属于无监督学习，它主要是把$n$个样本根据样本的特征分为$k$簇，同一簇之间的样本相似性很高，而不同簇中的样本相似性很小。

   算法描述

   大白话叙述如下：
       (1)为每个类确定一个初始聚类中心，作为$K$个簇的起始质心，一般这$K$个点事随机选择的。
       (2)对于每一个样本点，将其标记为距离簇中心最近（相似度最高）的类别。
       (3)根据聚类结果，重新计算$K$各簇各自的中心，计算方法一般是取簇中所有点各自维度的算术平均值。
       (4)重复步骤(2)，按照步骤(3)得出的簇中心，重新聚类。
       (5)重复步骤(4)，直到聚类结果不再发生变化，输出聚类结果。
   公式化解释：
       K-means是基于这样一个假设建模的：每一个簇里面的数据都是服从均值不同，方差相同的混合高斯分布。
       假设$K$个簇中心为$\mu_1,\mu_2,…,\mu_k$，每个簇的样本的数目为$N_1,N_2,…,N_k$，每个簇样本都服从方差为$\sigma$的高斯分布，则第$i$个簇的第$j$个样本的概率可以表示为： $$p_{ij}=\frac1{\sqrt{2\pi}\sigma}exp\frac{x_j^i-\mu_i}{2\sigma^2}$$ 第$i$个簇的似然函数可以表示为： $$\prod_{j=1}^{j=N_j}p_{ij}=\prod_{j=1}^{j=N_j}\frac1{\sqrt{2\pi}\sigma}exp\frac{x_j^i-\mu_i}{2\sigma^2}$$ 所有样本的似然函数可以表示为： $$\prod_{i=1}^K\prod_{j=1}^{j=N_j}p_{ij}=\prod_{i=1}^K\prod_{j=1}^{j=N_j}\frac1{\sqrt{2\pi}\sigma}exp\frac{x_j^i-\mu_i}{2\sigma^2}$$ 对似然函数取对数可以表示为： $$\ln\prod_{i=1}^K\prod_{j=1}^{j=N_j}p_{ij}=\sum_{i=1}^K\sum_{j=1}^{j=N_j}\frac1{\sqrt{2\pi}\sigma}exp\frac{x_j^i-\mu_i}{2\sigma^2}$$ 省去常数项,则得到最大似然估计的目标函数，让其目标函数取最大即可： $$J(\mu_1,\mu_2,…,\mu_k)=-\frac12\sum_{i=1}^K\sum_{j=1}^{j=N_j}(x_j^i-\mu_i)$$ 即添加一个负号，我们的目标函数就变成了均方误差： $$J(\mu_1,\mu_2,…,\mu_k)=\frac12\sum_{i=1}^K\sum_{j=1}^{j=N_j}(x_j^i-\mu_i)$$ 对目标函数求偏导，得： $$\frac{\partial J}{\partial \mu_i}=-\sum_{j=1}^{N_j}(x_j-\mu_i)=0$$ 解出来： $$\mu_i=$frac1N\sum_{j=1}^{N_j}x_j$$

   算法评价

3. 该算法是基于样本是服从高斯分布的这个假设，当簇样本近似为高斯分布时，效果较好，但对于环状分布的数据聚类效果不好
4. K-means需要人为确定初始聚类中心，不同的初始聚类中心导致完全不同的聚类结果，还需要事先给出簇的数目，即对初始值敏感。
5. 对噪声和孤立点比较敏感
6. 容易实现，简单快速

   K-means++

        K-means++算法是K-means的高配版，它主要是为解决初始聚类中心随机选可能会出现比较近导致后期聚类效果不理想的问题。k-means++选择初始聚类中心的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。

   算法描述

   大白话描述为：
        (1)从给定的样本点集合中随机选择一个点作为第一个聚类中心
       (2)计算其他样本点到最近聚类中心的距离(相似度)，在距离聚类中心比较远，相似度比较小的点，随机选择一个聚类中心，作为新的聚类中心。
       (3)重复(2)，直到$k$个初始聚类中心被选出来，再执行标准k-means。

   KNN

        KNN(K Nearest Neighbor)属于lazy-leaning，是一种分类算法。在一个样本空间里，样本分成几个类型，然后给定一个待分类的数据，通过计算距离自己最近的K个样本来判断这个待分类数据属于哪个类别。
   如图所示，图中有两类，一类是蓝色的正方形，另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。如果k=3，则距离测试样本最近的有两个红色三角形和1个蓝色正方形的样本，基于少数服从多数的原则，该样本属于红色三角形。若K=5，则样本属于蓝色正方形。

   KNN和K-means区别

   

参考资料

邹博，小象学院
李航，统计学习方法，清华大学出版社，2012
Pearson相关系数
机器学习中的相似性度量
K-means聚类算法
KNN算法