机器学习 - 聚类算法 - 学习笔记

[zengbin93]

聚类算法和分类算法的最主要区别是：聚类算法可以使用没有标签的数据；分类算法通常都需要数据带标签。

这里，主要介绍几类实践中常用的聚类算法及其使用方法。

几个基本概念

• 聚类（clustering）试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个簇（cluster）。

• 优质聚类结果的簇内相似度（intra-cluster similarity）高且簇间相似度（inter-cluster similarity）低。

• 原型聚类（prototype-based clustering）：假设聚类结构能够通过一组原型刻画，通常是先对原型进行初始化，然后对原型进行迭代更新求解。

• 密度聚类（density-based clustering）：假设类簇结构能够通过样本分布的紧密程度确定。 通常，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展类簇以获得最终的聚类结果。

参考资料

• http://scikit-learn.org/stable/modules/clustering.html

[zengbin93]

K-Means

• 优点：1）简单快速、2）对大数据集有比较好的伸缩性
• 缺点：1）需要提前指定类簇数量；2）对异常值和初始值敏感
• 训练目标：最小化平方误差

找到最小平方误差需要考察所有可能的簇划分，这是一个NP难问题；因此K-Means算法采用了贪心策略来近似求解。

算法过程基本描述：1）输入样本集和类簇数量K；2）随机选择k个样本初始化均值向量；3）计算每个样本与所有均值向量的距离，将样本归属到距离最近的类簇；4）重复2/3步骤，直到均值向量不更新、或者达到最大迭代次数

K-Means算法的目标函数是非凸函数，容易陷入局部最优；为了得到更好的结果，可以使用不同的初始均值向量多次运行。

参考资料

• http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
• http://scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html

[zengbin93]

DBSCAN

英文全称： Density-Based Spatial Clustering of Application with Noise

DBSCAN是典型的密度聚类算法。它基于“领域（neighborhood）”来刻画样本分布的紧密程度。

参考资料

• 《机器学习（周志华）》9.5密度聚类
• https://www.jianshu.com/p/2e3cbbaec7e6
• http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html