机器学习 18、聚类算法-Kmeans

你挡我一时,挡不了我一世

发布日期: 2019-05-29 15:55:53 浏览量: 394
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

前文链接:https://write-bug.com/article/2530.html

上节 我们暂时实现了一下单机版推荐系统,并且串了下知识,这节介绍下聚类,说起聚类就得先提下监督和非监督式学习:

  • 监督式学习:我们之前学习的分类、回归问题中的排序模型LR、Softmax,包括后面的dnn,dt等等都是需要数据事先有一个标签label作为新特征的分类

  • 非监督式学习:而这个有些类似之前的推荐算法,并没有特定的类别作为比对

而今天学习的算法聚类算法也是非监督式学习。

聚类是什么?

之前对于文本分类来说,需要事先设定好类别标签对新文本进行概率分类、对label对比,而这里的聚类则可以既不需要设定类别,也不需要事先设定文本中心,其可自动将数据划分到不同的类中,使相似的数据划分到相同的类中,这种方法可应用到几乎所有分类中,用户聚类、商品聚类、生物特征、基因、图像聚类等等分类。

比如说,随机系统中有10000篇文章,我只告诉系统分为多少个类,其他什么都不告诉,这个系统就可以自动操作完成。

事实上,就是对特征的向量化及空间划分。

向量化

如果想对一个文章、物品等作聚类,那聚类之前,如何表示文章呢?

向量

比如之前的tfidf,用一个向量来表示物品之后作cos、内积、计算质心等等

质心:各个向量的点构成的空间的中心,即每个点到这个点的最短平均距离

  1. A:(a1, a2, a3)
  2. B:(b1, b2, b3)
  3. C:(c1, c2, c3)
  4. 质心=( (a1+b1+c1)/3, (a2+b2+c2/3, (a3+b3+c3)/3)

距离矩阵、相似度矩阵

此矩阵就像之前的推荐算法中的矩阵,各个pair相似度的矩阵

评估

如何评估聚类效果?

内部方法

同类尽可能相似,不同类尽可能不相似

分子为对象到质心距离和,越小越好

分母为质心距离,越大越好

外部方法(准确P、召回R)

之前利用pr曲线找到最好的分类面,但是需要有监督的情况下才能用,这里如果想用,在特定情况下,比如说文章有固定标签,用这种方法训练后再告诉label评估效果,但是工作中几乎遇到的都是无标签的,所以这种方法是很鸡肋的方法,工作中基本用内部方法解决。

  1. F=PR /(P+R

聚类类别

层次聚类

  • 自底向上凝聚聚类,从不同的对象凝聚结果形成聚合节点,成树状

  • 自顶向下分裂聚类,从一个对象分裂结果形成分裂节点,成树状

优点:

  • 可通过阈值灵活控制类个数

  • 层次用于概念聚类,分类后人工对其打标签,抽象概念。

凝聚实现:

  • 将每个对象样本分为一类,得到N个类

  • 找到最接近的两个类合并为一个类:两层for循环遍历所有样本,计算cos相似度

  • 重新计算新类与旧类之间距离:类别之间距离和类别与对象之间距离的计算方式一般使用组合链的方式进行计算:即类中质心距离(平均距离),而与之相对的有单链(最近距离)和全链(最远距离)两种方式,一般工作中就直接使用组合链方式

  • 重复直到最后合并为一个类

  • 复杂度O(n^3)

非层次聚类:Kmeans

层次聚类是一种需要将向量两两比较聚类的方法,但这种方法的计算时间过长,影响效率,而Kmeans是随机选择对象作为类别中心,然后优化这些中心点的位置,使尽可能收敛到和真实中心一致的算法。

步骤:

  • 任意选择K个点作为初始聚类中心 (初始化类个数)

  • 根据每个聚类的中心,计算每个对象与这些中心的距离(cos、欧式距离),并根据 最小距离重新对相应对象进行划分

  1. 欧式距离:A:(a1, a2, a3) B:(b1, b2, b3)
  2. 距离=sqrt((a1-b1)^2 + (a2-b2)^2 + (a3-b3)^2 )
  • 重新计算每个聚类的中心 (更新质心计算)

  • 当满足一定条件,如类别划分不再发生变化时,算法终止,否则 继续步骤2和3

  • 复杂度:O(Ktn^2)K个点,n个对象,t次循环,n次计算质心

之前介绍时为什么说是向量化并分割空间,下面这个图每个点都是空间中的向量点,把两个中心点相连,中心分割的垂线就是分割面,再迭代更新质心位置,从而分割空间

一定条件

  • 轮数

  • WCSS损失函数:最小化簇内对象到质心的距离平方和

wcss变小,即空间变化不剧烈

缺点:过于依赖初始点选择,可能导致的结果大不一样

解决方法:只能多训练几轮,求质心平均值或者选择最小的wcss的模型。

模型:最终计算结果的K个中心点向量

K选择,业务场景:

举例:半个性化推荐,即热榜推荐列表只有一部分是个性化对用户的推荐(如视频网站首页上半部),但是当用户上亿,但热榜或首页展示目录只有10个,候选集合只有100个的时候怎么办?如何给大量的用户也做一个模糊的推荐?如何在100个候选集合中选择10个作为推荐列表?

对上亿用户作聚类,可以随意聚几千个类,再用这几千个类的向量和每个物品向量作cos,选出分数前10的物品向量作为此用户类的候选集合。

用户向量化:利用历史行为作用户画像:token作向量

层次 vs Kmeans

从上面两张图,我们可以看到右面Kmeans算法的暴力分割和缺点,在生活中的数据大部分都是球面原始数据,也是Kmeans的强项,左面的那种长条数据只能用层次聚类分辨出来,而与此同时左面五颜六色的单点都是噪音数据,前面说过层次聚类非常耗时,并且我们事先并不知道数据的分布,所以部分解决办法就是增加K类个数。

Kmeans粒度比较粗,层次粒度比较细。

聚类这种发现规律的分类效果永远无法赶上分类回归那种有监督式的效果,即有老师无老师的区别。如果效果不好,可以适当增加K个数增加准确率。

上传的附件
最近文章
eject