数据和算法的相爱相杀(二):常见的聚类算法

6 评论 5595 浏览 41 收藏 7 分钟

以下是数据与算法相爱相杀的第二篇,常见的聚类算法。如果按正常的数据和算法知识体系,这时候应该讲一下常用的数据查询或算法的数学基础,但是观众老爷多是PM,恐不感兴趣或没有基础。所以我就从应用和实战的角度给大家直接上干货,在过程中介绍其用到的数学或计算机知识。

聚类算法应该是大数据分析中最常见一类算法,在一般互联网公司中,哪怕不借助算法,我们也经常需要对用户、客户进行分类,进行人群画像,以支持差异化服务或营销。所以说聚类这件事情我们一直在做,而借助数据规模和算法优势则可以让我们分类更加精准、多元、客观。

常见的聚类算法包括:层次化聚类算法、划分式聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法等,以及现在比较火的基于粒度的聚类等。

我没有打算做聚类算法的科普,也不做其发展来龙去脉的论文,就从一般互联网公司能用到,各位看官可以拿来就用的角度分享一下常见的算法。

1、基于空间测距的k-means算法系列

k-means算法是一种经典的分类算法,它的基本原理是,视所有的数据为多维空间的点,如一名普通用户(拥有:月消费频次、消费金额、最近一次消费时间等众多的消费数据),他每一个我们用于分析的数据都看作是一个维度。

这样我们就得出了该用户的位置,通过定义数个(即k个)中心点(中心点由机器随机寻找),测算用户与各中心点的距离并进行比较,将该用户加入距离最近的中心点,这样就形成了不同的圈层。

明眼的观众可能已经看到,如果某点对所有中心点距离的最小值存在相同的,那这个点应该加入哪个圈层呢?

这时候就原来的中心点变成圈层的几何中心,从新测算距离,直到所有的点全包包含在某一个圈层中。

k-means算法的优点是简单高效、时间复杂度、空间复杂度都比较低,而且对于数据规模也不感冒,这对追求效率和消费者体验的互联网公司至关重要。

但是其需要预设k值,k值的选择会很大程度上影响聚类,用户数据缺失的情况对结果也有很大影响,同时对脏数据和离群值也很敏感。所以人们又改良了k-means算法,具体如下,大家选择学习。

为了解决预设k值不准确问题,延伸出了k-means++等众多算法。其基本原理是:在选择初始中心之前,对所有数据进行一次计算,使得选择的初始聚类中心之间的距离尽可能的远,同时也减少了计算量。

2、基于空间测距的CURE算法

层次聚类的核心原理是:先将每个对象作为一个组(簇),然后根据两两之间的距离合并这些原子组为越来越大的组,直到所有对象都在一个组中,或者条件满足(达到了你想要的组个数)。

它的计算流程是:每个对象作为一类,计算两者这件最小距离>将两个 合并成一个新类,形成新的中心>计算所有类之间的距离,然后两两合并>直到合并完成或达到要求。

常见的层次聚类算法有:CURE算法、ROCK算法等,其基本原理都一样,不过是各有所长。

3、基于密度划分的DBSCAN算法

上文中我们讲到了基于空间距离的聚类算法,这类算法最终形成的多是“圆形”的元素类,而基于度划分的DBSCAN算法核心是:预先定义两个变量,一个表示球形的半径,一个表示球形内的点。

只要一个区域中的点的密度(即:球内的点/球的体积)大过某个阈值,就把球形相近的点加到与之相近的聚类中去。

  • 在DBSCAN中的点分为核心点:在球形范围核心(稠密)的点;
  • 边界点:处于球形边界之内,但离核心较远的点,处于球形范围之外的点。

DBSCAN也存在一定的缺陷,一方面是对于高维数据不能很好的反映,另一方面是在聚类密度不断变化的数据集中,不能很好地反映整体聚类情况。

以上几种算法,基本够PM们在日常使用,启迪思维,方便交流。

除了以上几种常用的聚类分析算法之外,还有一些聚类算法(均值漂移算法、网格算法、模型算法),如果大家有时间可以查找资继续学习。

相关阅读

数据和算法的相爱相杀(一):获取数据要注意什么?

 

本文由 @没空儿 原创发布于人人都是产品经理。未经许可,禁止转载

题图来自 Unsplash ,基于 CC0 协议

更多精彩内容,请关注人人都是产品经理微信公众号或下载App
评论
评论请登录
  1. 还有应该是先采集数据再用算法计算,是不是在采集前就已经明确了自己要用哪种算法计算哪种业务?可以减轻采集到的数据元的粒度

    回复
  2. 文章经常用到测距离这个词,没听懂,为什么能测距离?又不是位置,是不是专业术语啊

    回复
  3. 同问蜂窝煤的那句话,我也没搞懂

    回复
  4. “明眼的观众可能已经看到,如果某点对所有中心点距离的最小值存在相同的,那这个点应该加入哪个圈层呢?

    这时候就原来的中心点变成圈层的几何中心,从新测算距离,直到所有的点全包包含在某一个圈层中。”
    您好,这句话“这时候就原来的中心点变成圈层的几何中心”我没有搞懂

    来自北京 回复
    1. 额,明白了

      来自北京 回复