数据和算法的相爱相杀（二）：常见的聚类算法

关注

来源： 300701 2018-08-08

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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