《机器学习实战》笔记（十）：Ch10 - 利用k-均值聚类算法对

第10章 K-均值聚类算法(代码)

• K-均值算法的优缺点

  K-均值是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成.

  簇个数 K 是用户指定的, 每一个簇通过其质心（centroid）, 即簇中所有点的中心来描述.

  聚类与分类算法的最大区别在于, 分类的目标类别已知, 而聚类的目标类别是未知的.

  • 优点:容易实现

  • 缺点:可能收敛到局部最小值，在大规模数据集上收敛较慢

  • 使用数据类型 : 数值型数据

• K-均值聚类算法

  • 伪代码

    • 创建 k 个点作为起始质心（通常是随机选择）

    • 当任意一个点的簇分配结果发生改变时（不改变时算法结束）

    • 对数据集中的每个数据点

    • 对每个质心

    • 计算质心与数据点之间的距离

    • 将数据点分配到距其最近的簇

    • 对每一个簇, 计算簇中所有点的均值并将均值作为质心

  • 开发流程

    • 收集数据：使用任意方法

    • 准备数据：需要数值型数据类计算距离, 也可以将标称型数据映射为二值型数据再用于距离计算

    • 分析数据：使用任意方法

    • 训练算法：不适用于无监督学习，即无监督学习不需要训练步骤

    • 测试算法：应用聚类算法、观察结果.可以使用量化的误差指标如误差平方和（后面会介绍）来评价算法的结果.

    • 使用算法：可以用于所希望的任何应用.通常情况下, 簇质心可以代表整个簇的数据来做出决策.

  • K-均值 的评价标准

    因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。k-means算法因为手动选取k值和初始化随机质心的缘故，每一次的结果不会完全一样，而且由于手动选取k值，我们需要知道我们选取的k值是否合理，聚类效果好不好，那么如何来评价某一次的聚类效果呢？也许将它们画在图上直接观察是最好的办法，但现实是，我们的数据不会仅仅只有两个特征，一般来说都有十几个特征，而观察十几维的空间对我们来说是一个无法完成的任务。因此，我们需要一个公式来帮助我们判断聚类的性能，这个公式就是SSE (Sum of Squared Error, 误差平方和 ），它其实就是每一个点到其簇内质心的距离的平方值的总和，这个数值对应kmeans函数中clusterAssment矩阵的第一列之和。 SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。

• 使用后处理来提高聚类性能

  • 二分 K-Means 聚类算法

  该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分时候可以最大程度降低 SSE（平方和误差）的值上述基于 SSE 的划分过程不断重复，直到得到用户指定的簇数目为止

  • 伪代码

  • 将所有点看成一个簇

  • 当簇数目小于 k 时

  • 对于每一个簇

  • 计算总误差

  • 在给定的簇上面进行 KMeans 聚类（k=2）

  • 计算将该簇一分为二之后的总误差

  • 选择使得误差最小的那个簇进行划分操作

• 小节

  聚类算法是一种无监督学习算法.所谓无监督学习是指事先并不知道寻找的内容,即没有目标变量,一种广泛使用的聚类算法是K-均值算法,其中k是用户制定的要创建的族的数目,二分K-均值的聚类算法效果要好于K-均值算法

代码托管见Github