76a2838322f60d43e23362752d06ec6c
聚类算法(上)

1、前言

聚类算法很多,所以和讲回归算法一样,分成了上下,上中主要讲了传统的K-Means算法以及其相应的优化算法入K-Means++,K-Means||和Canopy等。下中主要讲了另外两种的思路的聚类算法,即层次聚类和密度聚类。

2、什么是聚类

聚类算就是怼大量未知标注的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据比较相似,类别之间的数据相似度比较小,属于无监督学习

从定义就可以看出,聚类算法的关键在于计算样本之间的相似度,也称为样本间的距离

3、相似度/距离计算公式

说到聚类算法,那肯定核心就是计算距离的公式了,目前常用的有以下几种。
闵可夫斯基距离(Minkowski):公式2.1

  • 当p为1的时候是曼哈顿距离(Manhattan):公式2.2
  • 当p为2的时候是欧式距离(Euclidean):公式2.3
    • 标准化欧式距离:
      这个距离的计算方式如同其字面意思,标准化欧式距离就是对欧式距离的标准化。标准化的正常定义为,$X^* = \frac{X - \overline X}{s}$,这个$s$指的就是方差,而方差的计算公式为$s = \sqrt{\frac{\sum_{i=1}^n(x_i - \overline X)^2}{n}}$,所以其标准化公式如下公式2.5。
  • 当p为无穷大的以后是切比雪夫距离(Chebyshev):公式2.4
    $$
    dist(X,Y)= \sqrt[p]{\sum_{i=1}^{n} |x_i - y_i|^p}\ \ \ 公式2.1
    $$
    $$
    M\_dist=\sum_{i=1}^n|x_i-y_i| \ \ \ 公式2.2
    $$
    $$
    E\_dist = \sqrt{\sum_{i=1}^n|x_i-y_i|^2} \ \ \ 公式2.3
    $$
    $$
    C\_dist = max_i(|x_i-y_i|)\ \ \ 公式2.4
    $$
    $$
    S\_E\_D = \sqrt{\sum_{i=1}^n(\frac{x_i-y_i}{s_i})^2}\ \ \ 公式2.5
    $$

夹角余弦相似度(Cosine)
使用这个公式的时候,需要注意的是,这里的相似之的是同一个方向上的,而同一个方向上的两个点可能距离是非常远的。比如一个吻张灏总分别出现单词A 10次,单词B 20次,另一个文章中出现单词A 100次,单词B 200次,这时候如果使用欧几里得距离的话,这两个文章是不相似的,然而显然这两个单词的比例相似很能说明这两个文章其实是有关系的,所以在文章的相似度的判别中使用夹角余弦相似度比较合适,如下公式2.6。
注:夹角余弦相似度是从距离以外的衡量相似度的另一个维度的指标
$$
\cos(\theta) = \frac{\sum_{k=1}^n x_{1k}x_{2k}}{\sqrt{\sum_{k=1}^n x_{1k}^2} * \sqrt{\sum_{k=1}^n x_{2k}^2}} = \frac{a^T · b}{|a||b|}\ \ \ 公式2.6
$$

KL距离(相对熵)
思考下条件熵的定义,简单的来说就是在放生一件事情的时候,发生另一件事的概率。公式如下公式2.7.
注:这里书的概率不是实指概率,而是熵表达的含义。这个公式其实就是条件熵的公式。
$$
D(P|Q)=\sum_x P(x)\log(\frac{P(x)}{Q(x)})\ \ \ 公式2.7
$$

杰卡德相似系数(Jaccard)
这个很好理解,它的核心就是使用两个集合的交集和并集的比率来代表两者的相似度,也就是说重合的越多越相似。公式如下,公式2.8.
$$
J(A,B) = \frac{|A\bigcap B|}{|A \bigcup B|}
$$
$$
dist(A,B) = 1-J(A,B) \ \ \ 公式2.8
$$

Pearson相关系数
这个就是考研数学中的相关系数,表达就是两者之间的想关系,所以直接拿来用就好了,公式如下公式2.9。
$$
\rho_{XY} = \frac{Cov(X,Y)}{\sqrt{D(X)} \sqrt{D(Y)}} = \frac{E[(X-E(X))(Y-E(Y))]}{\sqrt{D(X)}\sqrt{D(Y)}} = \frac{\sum_{i=1}^n(X_i - \mu_x)(Y_i - \mu_Y)}{\sqrt{\sum_{i=1}^n(X_i - \mu_X)^2}*\sqrt{\sum_{i=1}^n(Y_i - \mu_Y)^2}}
$$
$$
dist(X,Y) = 1 - \rho_{XY}\ \ \ 公式2.9
$$

4、聚类的思想

给定一个有 M 个对象的数据集,构建一个具有 k 个簇的模型,其中 k \<= M。满足 以下条件:

  • 每个簇至少包含一个对象
  • 每个对象属于且仅属于一个簇
  • 将满足上述条件的k个簇成为一个合理的聚类划分

基本思想:
对于给定的类别数目k,首先给定初始划分,通过迭代改变样本和簇的隶属关系,使的每次处理后得到的划分方式比上一次的好,即总的数据集之间的距离和变小了

5、 K-Means 系列

K-Means 算法

K-means的核心算法如下:

# 假设输入样本T为x1,x2,x3,...,xm

初始化k个类别的中心点a1,a2,a3,...,ak
while not EndCondition :
    1.根据每个样本和中心点的欧几里得距离,选择最近的中心点作为自己的类别
    2.更新每个类别的中心点aj,为隶属该类别的所有的样本的均值

# EndCondition有迭代次数,最小平方误差MSE,簇中心点变化率。

在循环中的第二步,我们移动了中心点的位置,把中心点移到了隶属于该中心点类别的所有样本的中间,并使用样本的均值作为位置。这样子看似是拍脑袋想的移动策略,其实是可以推导出来的。正如聚类算法思想所指出的,我们要让所有的点到自己的分类的中心点的欧几里得距离最小,所以我们设置目标放称为公式4.1,公式中的1/2是为了之后求导运算方便。我们为了让目标函数尽可能的小,所以使用了之前一直在使用的思考方式,对其使用梯度下降算法,求导后得到公式4.2,之后令其等于0,就得到了公式4.3。
$$
J(a_1,a_2,a_3,...,a_k) = \frac{1}{2}\sum_{j=1}^K \sum_{i=1}^n (x_i - a_j)^2 \ \ \ 公式4.1
$$
$$
\frac{\partial J}{\partial a_j} = \sum_{i=1}^{N_j}(x_i-a_j)\ \ \ 公式4.2
$$

$$
a_j = \frac{1}{N}\sum_{i=1}^{N_j} x_i \ \ \ 公式4.3
$$
最后,这个看似不错的算法,其实有着不小的缺点,那就是初值敏感。我们来仔细想一想,如果两个不小心随机生成的初值落到了一个类别中,两者的距离还特别近,这中情况下就很难正确分类了。除此之外,由于移动策略中使用的是均值,也就是说如果集合中含有非常大的误差点的话,这样子会是中心点的设置偏离正确点很远,所以很多时候我们改用中值来更新中心点,这就是我们说的K-Mediods聚类,即K中值聚类。

K-means算法总结:

优点:

  • 理解容易,聚类效果不错
    • 处理大数据集的时候,该算法可以保证较好的伸缩性和高效率
    • 当簇近似高斯分布的时候,效果非常不错
      缺点:
  • K值是用户给定的,在进行数据处理前,K值是未知的,不同的K值得到的结果也不一样
  • 对初始簇中心点是敏感的
  • 不适合发现非凸形状的簇或者大小差别较大的簇
  • 特殊值(离群值)对模型的影响比较大

二分 K-Means 算法

和之前线性回归算法的进化一样,针对K-Means对初始中心点非常敏感这一缺点,就引入了二分 K-Means算法,其尝试通过二分法弱化初始中心点。这种算法的具体步骤如下:

# 把所有样本数据作为一个簇放到队列中
while not EndCondition:
    1.从队列中选择一个簇,使用K-means划分为两个簇
    2.将划分好的两个簇放回队列
# EndCondition 为簇的数量,最小平方误差,迭代次数等
# 选择簇的手段有两种1.使用SSE 2.选择数据量最多的簇
top Created with Sketch.