一、聚类的基本概念

1、相似度或距离

image.png

聚类的核心概念是相似度或距离。有多种相似度或距离的定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。

（1）闵可夫斯基距离

闵可夫斯基距离越大相似度越小，距离越小相似度越大。

image.png

（2）马哈拉诺比斯距离（马氏距离）

另一种常用的相似度，考虑各个分量（特征）之间的相关性并与各个分量的尺度无关。
马哈拉诺比斯距离越大相似度越小，距离越小相似度越大。

image.png

（3）相关系数

样本之间的相似度也可以用相关系数来表示
相关系数的绝对值越接近于1，表示样本越相似。
越接近于0，表示样本越不相似。

image.png

（4）夹角余弦

样本直接的相似度也可用夹角余弦表示。
夹角余弦越接近于1，表示样本越相似。
越接近于0，表示样本越不相似。

image.png image.png

2、类或簇

通过聚类得到的类或簇，本质是样本的子集。
如果一个聚类方法假定一个样本只能属于一个类，或类的交集为空集，那么该方法称为硬聚类方法。
如果一个样本可以属于多个类，或类的交集不为空集，那么该方法称为软聚类方法。

image.png

类的特征可以通过不同角度来刻画，常用的特征有下面三种：

image.png

3、类与类之间的距离

image.png

二、层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。
层次聚类又有聚合或自下而上聚类，分裂或自上而下聚类两种方法
因为每个样本只属于一个类，所以层次聚类属于硬聚类。

聚合聚类开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件得到层次化的类别。

分裂聚类开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件得到层次化的类别。

聚合聚类的具体过程：

• 对于给定的样本集合，开始将每个样本分到一个类
• 然后按照一定规则，例如类间距距离最小，将最满足规则条件的两个类进行合并
• 如此反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类。

聚合聚类需要预先确定三个要素：

image.png

聚合聚类算法

image.png

三、k均值聚类

k均值聚类是基于样本集合划分的聚类算法。
k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。
每个样本只能属于一个类，所以k均值聚类是硬聚类。

1、模型

image.png

2、策略

k均值聚类归结为样本集合X的划分，或者从样本到类的函数的选择问题。
k均值聚类的策略是通过损失函数的最小化选取最优的划分或函数C*

image.png

k均值聚类即使求解最优化问题：

image.png

3、算法

k均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤。

• 选择k个类的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果
• 然后更新每个类的样本的均值，作为类的新的中心
  重复以上步骤，直到收敛为止。

具体过程：

image.png

k均值聚类算法

image.png

4、算法特征

（1）总体特点

image.png

（2）收敛性

k均值聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果。
注意：类中心在聚类的过程中会发生移动，但是往往不会移动太大，因为在每一步，样本被分到与其最近的中心的类中。

（3）初始类的选择

选择不同的初始中心，会到的不同的聚类结果。
初始中心的选择，比如可以用层次聚类对样本进行聚类，得到k个类时停止。然后从美国类中选取一个与中心距离最近的点。

（4）类别数k的选择

image.png