无监督学习
机器学习中面对无标签的数据的一类数据挖掘的学习算法。
聚类
是无监督学习的一种,将有相似特征的样本聚合为1类。
K-means
算法流程
数据输入:
- K:定下的分类的组数
- 训练集${x^{(1)},…,x^{(m)}}$,训练集中有$m$个样本,其中每个样本有n个特征,即$x^{(i)}\in \mathbb{R}^{n}$
算法流程:
1 | 随机生成K个聚类中心 |
优化目标
记:
- $c^{(i)}$为$x^{(i)}$分配到K个聚类中心的索引号
- $\mu_k$为第k个聚类中心的位置
- $\mu_{c^{(i)}}$为$x^{(i)}$被分配到聚类中心的位置
由K-means算法流程我们很容易得到目标函数为
$$
J(c^{(1)},…,c^{(m)},\mu_1,…,\mu_K)=\frac{1}{m}\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2
$$
优化目标为
$$
\min_{c^{(1)},…,c^{(m)}\ \mu_1,…,\mu_K}J(c^{(1)},…,c^{(m)},\mu_1,…,\mu_K)
$$
J(·)又称为畸变函数。
如何初始化
一般选择的聚类组数K要小于样本数m。但随机选择K个样本赋值作为K个初始聚类中心,有可能陷入局部最优解。如下图所示,左右两图均落入局部最优解。
此时,较好的办法是使用多次初始化,即可得到较好的效果。
具体计算过程如下:
1 | For i =1 to 100{ |
当聚类数目过小时,会有较好的结果。
如何选择K值
- 通常情况
肘部法则:将K=1,…的损失函数图像画出来,选择其中在肘部位置的K值最好。此时计算量不大,迭代速度快,且误差不会太大。
- 其他目的
例如需要衣服尺寸只有固定5类尺码,S,M,L,XL,XLL,只能选取固定的类别数。