聚类
文章目录
- 聚类
* - 一.什么是聚类
– - 二.K-means算法
– - 三.Canopy算法
- 四.聚类算法的评价指标
– - 五.层次聚类
– - 六.密度聚类方法
– - 七.谱聚类
– - 八.标签传递算法
一.什么是聚类
1.聚类定义
聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小。由这个定义，我们便可以知道，数据集并没有目标值。因此聚类算法属于无监督算法。
2. 相似度的衡量
之前在k-means算法的简介当中，提及过一个欧式距离。但实际上，相似度的衡量方式有很多种。比如说：
- 欧式距离（这里列出的是欧式距离的拓展，闵可夫斯基距离）：
- 杰卡德相似系数(Jaccard)
- 余弦相似度：
cos ( θ ) = x T y ∣ x ∣ ⋅ ∣ y ∣ \cos(\theta) = \frac{x^Ty}{|x|\cdot |y|}cos (θ)=∣x ∣⋅∣y ∣x T y
这个是x向量与y向量之间的夹角为theta。如果x，y都是多维呢？如下：
- Pearson相似系数：
- 相对熵(K-L距离)：
- Hellinger距离：
在Hellinger距离当中，特殊的，我们取a=0的时候：
对于这几种距离到底适用于哪种场景，优缺点是什么，其实很难说，查了一些资料，一句话引起了我的注意：
其实你会发现，选择不同的相似性度量方法，对结果的影响是微乎其微的。 ——《集体智慧编程》
; 3. 聚类与降维的关系
我们看下面这个示例，我们假设有x1,x2, ……, xn堆样本，每堆样本有m个数据，那么这m个堆样本就组成了n*m的矩阵。
( x 1 x 2 x 3 . . . . x n ) ⇒ ( x 1 ( 1 ) x 1 ( 2 ) … … x 1 ( m ) x 2 ( 1 ) x 2 ( 2 ) … … x 2 ( m ) x 3 ( 1 ) x 3 ( 2 ) … … x 3 ( m ) … … … … … … … … … … … … … … … … … … … … … … … … x n ( 1 ) x n ( 2 ) … … x n ( m ) ) \begin{pmatrix} x_{1}\ x_{2}\ x_{3}\ .\ .\ .\ .\ x_{n} \end{pmatrix} \Rightarrow \begin{pmatrix} x_{1}^{(1)} && x_{1}^{(2)} && …… && x_{1}^{(m)} \ x_{2}^{(1)} && x_{2}^{(2)} && …… && x_{2}^{(m)} \ x_{3}^{(1)} && x_{3}^{(2)} && …… && x_{3}^{(m)} \ ……&&……&&……&&……\ ……&&……&&……&&……\ ……&&……&&……&&……\ x_{n}^{(1)} && x_{n}^{(2)} && …… && x_{n}^{(m)} \ \end{pmatrix}⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛x 1 x 2 x 3 ….x n ⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞⇒⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛x 1 (1 )x 2 (1 )x 3 (1 )………………x n (1 )x 1 (2 )x 2 (2 )x 3 (2 )………………x n (2 )……………………………………x 1 (m )x 2 (m )x 3 (m )………………x n (m )⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞
聚类，就是要把这些样本进行分类，是一种无监督的分类。那么，经过分类之后，发现整体有k=6个簇。依据不同的簇，又可以组成一个m*6的one-hot矩阵如下：
( x 1 ( 1 ) x 1 ( 2 ) … … x 1 ( m ) x 2 ( 1 ) x 2 ( 2 ) … … x 2 ( m ) x 3 ( 1 ) x 3 ( 2 ) … … x 3 ( m ) … … … … … … … … … … … … … … … … … … … … … … … … x n ( 1 ) x n ( 2 ) … … x n ( m ) ) ⇒ ( o n e _ h o t 矩 阵 ) ⇒ n ∗ 6 矩 阵 \begin{pmatrix}x_{1}^{(1)} && x_{1}^{(2)} && …… && x_{1}^{(m)} \x_{2}^{(1)} && x_{2}^{(2)} && …… && x_{2}^{(m)} \x_{3}^{(1)} && x_{3}^{(2)} && …… && x_{3}^{(m)} \……&&……&&……&&……\……&&……&&……&&……\……&&……&&……&&……\x_{n}^{(1)} && x_{n}^{(2)} && …… && x_{n}^{(m)}\end{pmatrix} \Rightarrow (one_hot矩阵) \Rightarrow n*6矩阵⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛x 1 (1 )x 2 (1 )x 3 (1 )………………x n (1 )x 1 (2 )x 2 (2 )x 3 (2 )………………x n (2 )……………………………………x 1 (m )x 2 (m )x 3 (m )………………x n (m )⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞⇒(o n e _h o t 矩阵)⇒n ∗6 矩阵
这就是一种降维。所以在某些情景里面，降维和聚类具有一定的相通的地方。
4.聚类的思想
基本思想:对于给定的类别数目k,首先给出初始划分,通过迭代改变样本和簇的隶属关系,使得每一次改进之后的划分方案都较前一次好
二.K-means算法
这个，先看一看简介：k-means算法简介
这个之前有介绍过基本原理，但是需要做一些补充
1. 算法步骤
假定输入样本为S=x 1 ,x 2 ,…,x m ,则 算法步骤为:
- 选择初始的k个类别中心μ1, μ2 … μk
- 对于每个样本xi ,将其标记为距离类别中心最近的类别,即:
l a b e l i = a r g m i n 1 < = j < = k ∣ ∣ x i − u j ∣ ∣ label_{i} = argmin_{1 - 将每个类别中心更新为隶属该类别的所有样本的均值
μ j = 1 ∣ c j ∣ ∑ i ∈ c j x i \mu_{j} = \frac{1}{|c_{j}|}\sum_{i\in c_j}x_{i}μj =∣c j ∣1 i ∈c j ∑x i - 重复最后两步,直到类别中心的变化小于某阈值。
中止条件：迭代次数/簇中心变化率/最小平方误差MSE(Minimum Squared Error)，这个需要你自己指定
2. k-means公式化解读
其实，对于k-means算法，和之前的机器学习算法一样，也有一个目标函数，我们假设有K个簇中心为 u1 , u2 , …… , uk ,每个簇的样本数目为 N1 , N2 , …… , Nk，我们使用平方误差做目标函数，就会得到如下公式：
如何理解这个损失函数呢？
我们假定有三个类别，分别服从三个不同的正态分布N(u1, a1^2), N(u2, a2^2), N(u3, a3^2)。分别求这三个类别里面，所有样本的最大似然估计。以第一个类别为例：
x ( i ) ∼ N ( u 1 , σ 1 2 ) ∼ 1 2 π σ 1 e − ( x ( i ) − u 1 ) 2 2 σ 1 2 x^{(i)}\thicksim N(u1,\sigma_{1}^2)\thicksim \frac{1}{\sqrt{2\pi}\sigma_{1}} e^{-\frac{(x^{(i)}-u1)^2}{2\sigma1^2}}x (i )∼N (u 1 ,σ1 2 )∼2 πσ1 1 e −2 σ1 2 (x (i )−u 1 )2
第一个类别里面的所有样本都是服从这样一个分布，我们按照求最大似然估计的套路，先累乘，就是：
∏ i = 1 n 1 2 π σ 1 e − ( x ( i ) − u 1 ) 2 2 σ 1 2 \prod_{i=1}^{n}\frac{1}{\sqrt{2\pi}\sigma_{1}} e^{-\frac{(x^{(i)}-u1)^2}{2\sigma1^2}}i =1 ∏n 2 πσ1 1 e −2 σ1 2 (x (i )−u 1 )2
那么，三个类别我们都进行累乘，然后取对数。前面带有pi的系数是常量，可以不管，最后剩下的就是xi-uj。
通过上述这个推导，有没有想过这样一个事情，为什么正态分布的情况竟然能够和损失函数完美对接呢？由此，也可以大体猜出一件事情：k-means对样本分布是有一定的要求的，即：整体符合正态分布。即使单个样本不一定是服从于正态分布，但如果样本足够大，那么通过大数定律，使得整体大概符合正态分布也是可以的。
如果针对这个损失函数，我们对不同的中心点，即：u1, u2, u3, ……, uk求偏导，然后求驻点，会如何呢？
由此可见：有好多个极值点，从这个角度来说，k-means可以当作是那个所示函数在梯度下降上的一个应用。而依据上面这个数学推导，我们大致就可以画出目标函数的一个大致的图像：
那么很显然，你到底初值选哪里，才更容易迭代到更好的结果，还真是不太容易搞，就像上图当中的，你选3点，肯定比1点能迭代到更小的损失值。说白了：初值选的好不好，直接影响到你能否迭代到一个好的结果。这就引申出了一个很重要的问题： k-means是初值敏感的。就像下面这个图：
如果我像左图那样选定初始点，那么久可能分成右侧那个图的样子。但是实际上，那个最大的圈，还可以至少分成两部分。
那么如何解决这个事情？
; 3. k-means ++
解决上述问题的一种思路是：初始选择的样本点，距离要尽可能的大。k-means算法一开始都会选初值。假定我选定了一个点，那么我把各个样本到这个点的距离全部计算一次，这样就得到了一组距离：d1, d2, d3 ……, dn。我们令D = d1 + d2 + …… + dn。然后得到若干个概率p1= d1/D, p2= d2/D, ……pn = dn/D。我们按照概率来选择哪个点是优先选择的点。
什么叫依概率选择呢？其实就是说，以上这若干的概率，哪个值最大，就越有可能会被选中，是不是一定选中呢？不一定！！不过，这个可能意味着运算量会很大。 有一段代码很好的说明了这个思路：
cluster_center = np.zeros((k,n))
j= np.random.randint(m)
cluster_center[0] = data[j][:]
dis = np.zeros(m) - 1
i=0
while i<k-1:
for j in ramge(m):
d = (cluster_center[i]-data[j]) ** 2
d = np.sum(d)
if (dis[j]<0) or (dis[j] > d):
dis[j] = d
j = random_select(dis)
i += 1
cluster_center[i] = data[j][:]
如此一来，我们就得到了另一个算法：k-means++，相比纯粹的k-means，他就是多了一个这样的初始选择方式。这个方式颇有点这种味道：跳远比赛，不能每个人只跳一次，而是每个人跳好多次，综合考虑。
4.Mini-Batch K-Means
如果我们在k-means的基础上考虑SGD, BGD。如果我们所有点都考虑，那么就是SGD，但是如果我们从各个样本之间随机选若干个样本，然后做这些事情呢，那不就是BGD的思想。实际上，还真就有这种方式的k-means。这个方式有另外一个名字：Mini-Batch K-Means
5. k-means总结：
首先，我们看看它的优点:
- k-means是解决聚类问题的一种经典算法,简单、快速
- 对处理大数据集,该算法保持可伸缩性和高效率
- 当簇近似为高斯分布时,它的效果较好
但是，k-means的缺点也很明显，上面已经分析过了：
- 在簇的平均值可被定义的情况下才能使用,可能不适用于所有的应用场景
- 必须事先给出k(要生成的簇的数目，这个是个超参数，自己调整不是很好拿捏)，而且对初值敏感，对于不同的初始值可能会导致不同结果。
- 不适合于发现非凸形状的簇或者大小差别很大的簇
- 对躁声和孤立点数据敏感
与此同时，k-means可作为其他聚类方法的基础算法,如谱聚类
三.Canopy算法
这个算法，最开始其实是用来做空间索引的，但是它也可以应用于聚类问题。
这个算法的大体思路如下：
我们假定，有给定样本 x1 , x2 …… xm ，首先，我们给定先验值 r1 , r2 , 假设r1
Original: https://blog.csdn.net/johnny_love_1968/article/details/116708871
Author: 南方惆怅客
Title: 聚类算法简介
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/560341/
转载文章受原作者版权保护。转载请注明原作者出处！