【机器学习】22. 聚类cluster - K-means

1. 定义

将数据对象划分为组的过程，使同一组中的对象在集群中彼此相似，而与其他集群中的对象不同。
无监督学习

2. 测量数据点之间的相似性

• 距离测量
• 余弦相似度
• 其他

3. Centroid and medoid

Centroid - 在中心
Medoid - 一个在中心的点

4. Cluster之间距离的测量方式

• Centroid
• Medoids
• Single link(min)
• Complete link(max)
• Average link(max)
  

5. 聚类算法的类别

• partitional -k-means, k-medoids;通过划分数据集生成一个簇的集合, 每个簇都对应数据中的一个子集
• Model-based – GMM 假设数据式由不同的概率分布生成的, 使用该模型来估计这些分布并分配数据点
• Hierarchical – agglomerative and divisive 构建嵌套的簇结构, 可以通过层次图展示, 层次聚类逐步合并或分裂数据, 创建不同层次的簇
• Density based - DBSCAN 基于数据点的密度进行聚类, 能够识别出形状不规则的簇, 并能够检测出噪声点

6. K-mean

• 分区聚类算法
• 非常流行和广泛使用
• 需要指定集群的个数k

3个主要步骤：

• 选择k个示例作为簇的初始质心
• 通过将每个例子分配到最近的质心来形成k个簇
• 在每个时期结束时：
  • 重新计算集群的质心
  • 检查停止条件是否满足：质心不改变。如果是-停止：否则，重复步骤2和3使用新的质心

问题：

对初始中心很敏感

7. 如何解决中心初始化带来的影响

• 方法1：随机选取不同的初始质心进行多次K-means运算，并使用SEE对每个聚类进行评估
  SSE：对于每个点，误差是到最近质心的距离。
• 方法2: k - means + +
  重心选择:
  逐步选择质心，直到选中k个质心
  在每一步，每个点都有一个概率被选为一个质心，这个概率与它到最近质心的距离的平方成正比
  选择离当前质心最远的点-选择分离良好的点
  可以选择异常值，但异常值的定义是罕见的。
  计算:
  1)对于第一个质心，随机选择一个点。
  2)i=1到试验次数
  3)计算每个点到它最近的质心的距离d(x)。
  4)赋予每个点与每个点的d(x)2成比例的概率。
  5)利用加权概率从剩余点中选取新的质心。

8. K-means问题：处理空集群

K-means可以产生空的集群-在分配步骤中没有分配到集群的点区域-集群仅由初始质心组成

• 解决方案：
  • 选择不同的初始质心策略
  • 选择距离任何当前质心最远的点
  • 使用k-means++方法
  • 从SSE最高的集群中选择一个点 这通常会分裂集群，减少集群的整体SSE
• 如果有几个空集群，以上可以重复几次。

9. 离群值的问题

由于异常值导致的聚类中心代表性较差，SSE较高
解决方案：去除异常值
或者，作为聚类后的后处理步骤，去除异常值。

10. Bisecting K-means（二分K-means）

1. 开始时所有的点都放在一个簇中
2. 重复以下过程
   从当前的簇列表中, 选择一个簇用于拆分
   对于指定的迭代次数, 使用K-means对选中的簇进行二分
   将二分后的簇中SSE最低的两个簇添加到簇列表中
   终止条件: 当簇的数量达到k个时

有多种方式可以选择要拆分的簇:：

• 选择最大的簇
• 选择SSE最大的簇
• 基于大小和SSE的综合指标

11. K-MEAN 缺点 和 优点

优点： 简单，高效
缺点：

• 在以球形分类, 同等大小, 分裂明显的原始数据上的表现非常好. 但是在非球形分类的, 复杂的, 大小不一致, 密度不一致的原始数据上表现不佳.
• 对中心初始化敏感
• 对有噪声的数据表现不好（通过预处理清除

改进:

• 通过 bisecting K-means 和 K-means ++ 减少对中心点初始化的敏感度