机器学习实战 - 读书笔记(10) - 利用Ｋ-均值聚类算法对未标注数据分组

前言

最近在看Peter Harrington写的“机器学习实战”，这是我的学习心得，这次是第10章 - 利用Ｋ-均值聚类算法对未标注数据分组。

基本概念

• 非监督学习 Unsupervised learning is the machine learning task of inferring a function to describe hidden structure from unlabeled data.
• 聚类（Clustering） Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).
• SSE（Sum of Squared Error，误差平方和） 一种用于度量聚类效果的指标。簇中所有点离簇心的距离平方的总和。
• 后处理 在算法产生之后，对算法结果进行修正。 比如：对k均值聚类算法的修正方法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。

k均值聚类算法

创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生改变时
    对数据集中的每个数据点
        对每个质心
            计算质心与数据点之间的距离
        将数据点分配到距其最近的簇
    对每一个簇，计算簇中所有点的均值并将均值作为质心

• 输入
  • DataSet
  • k
  • 距离计算方法
• 输出
  • 簇心点
  • 数据的分配结果（每个点在哪个簇里；离簇心的距离平方）
• 优点
  • 有效
• 缺点
  • 容易受到初始簇心的影响。
  • 收敛于局部最小值而不是全局最小值。

二分k均值算法

将所有点看成一个簇
当簇数目小于k时
    对于每一个簇
        计算总误差
        在给定的簇上面进行K均值聚类（K=2）
        计算将该簇一分为二之后的总误差
    选择使得误差最小的那个簇进行划分操作

• 输入
  • DataSet
  • k
  • 距离计算方法
• 输出
  • 簇心点
  • 数据的分配结果（每个点在哪个簇里；离簇心的距离平方）
• 优点
  • 可以解决k均值聚类算法的收敛于局部最小值的问题。

核心算法

• 距离计算方法 - 几何距离 \sqrt{\textstyle \sum_{i=1}^n (x1[i] - x2[i])^2}

参考

• Machine Learning in Action by Peter Harrington
• Unsupervised learning
• Cluster analysis