聚类算法

聚类:通过物品来计算距离,并自动分类到不同的群集或组中。有两种聚类算法比较常用:

(1)K-means聚类算法

需要提前告诉算法要将数据分成几个组。
K-means算法过程可概括为:

  1. 随机选取k个元素作为中心点
  2. 根据距离将各个点分配给中心点
  3. 计算新的中心点
  4. 重复2,3,直至满足条件

K-means是一种最大期望算法,这类算法会在“期望”和“最大化”两个阶段不断迭代,比如k-means的期望阶段是将各个点分配到他们所期望的分类中,然后在最大化阶段重新计算中心点的位置。

补充:登山式算法
假设我们想要登上一座山的顶峰,可以通过以下步骤实现:

  1. 在山上随机选取一个点作为开始
  2. 向高处爬一点
  3. 重复第2步,直到没有更高的点
    对于如下的山峰看起来很合理:


    登山式算法

K-means也是这样的一种算法,它并不能保证最终结果是最优的,因为我们一开始选择的中心点是随机的,很有可能就会选到A点,最终获得局部最优解B点。因此,最终的聚类结果和起始点的选择有很大的关系。但尽管如此,k-means通常还是能够获得良好的结果的。

误差平凡和SSE
可以用误差平凡和(或称为离散程度)来评判聚类结果的好坏,他的计算方法是计算每个点到中心点的距离平凡和

误差平凡和

注意:虽然指定了K的值,但不代表最终结果就会有k个分类,这通常是好事,比如,指定k=10,但结果有2个为空,那很可能这个数据集本来就该分成8个类别,因此可以尝试用k=8来重新计算。

K-means++

k-means算法有一个明显的缺点,在算法一开始需要随机选取k个起始点,这个随机会有问题。有时选取的点能产生最佳结果,而有时会让结果变得很差。K-means++则改进了起始点的选取过程,其余和k-means一致。

k-means++选取起始点的过程:

  1. 随机选取一个点
  2. 重复以下步骤,直到选完k个点
    I. 计算没个数据点(dp)到各个中心点的距离(D),选取最小的值,记为D(dp)
    II. 根据D(dp)的概率来随机选取一个点作为中心点

K-means++选取起始点的方法总结下来就是:第一个点还是随机的,但后续的点就会尽量选择离现有中心点更远的点

(2)层次聚类算法

不需要预先指定分类的数量,这个方法会将每条数据都当做是一个分类,每次迭代的时候合并距离最近的两个分类,直到剩下一个分类为止。


层次聚类法原理图

在合并的时候会计算两个分类之间的距离,可以采用不同的方法:


层次聚类法

内容来源:《dataminmingguide》---聚类

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容