9 聚类

9.1 聚类任务

• 聚类：无监督学习

• 类簇：簇内相似度高，簇间相似度低。

9.2 性能度量

闵可夫斯基距离：P=2时，闵氏距离等于欧氏距离；P=1时，闵氏距离等于曼哈顿距离。

9.3 聚类算法

9.3.1 k均值算法

算法步骤：

1. 初始化K值和聚类中心
2. 计算样本到各个聚类中心的距离
3. 比较距离，将样本划入相应簇中
4. 计算新的均值向量
5. 判断聚类中心是否变化，变换则重复2-4步，否则输出聚类结果

9.3.2 密度聚类

基本概念：

• 核心对象：样本邻域至少包含MinPts个样本。
• 密度直达：样本在核心对象的邻域中。
• 密度可达：传递性密度直达。
• 密度相连：存在一个样本使得另外两个样本与该样本密度可达。称这两个样本密度相连。

注

试析均值算法能否找到最小化(9.24)的最优解?

不能，因为k均值算法只是局部最有的近似算法，只能找到初始化均值附近的局部最优解，无法找到全局最优解。

注

基于 DBSCAN 的概念定义，若 x 为核心对象，有 x 密度可达的所有样本构成的集合 X ，试证明： X 满足连接性和最大性。

• 显然最大性是满足的。
• 连接性：假设 $x_i$ 为核心对象，由于 $x_j$ 可以由xi密度可达。则存在核心对象 $x_k$，使得 $x_i$ 与 $x_k$ 密度直达，$x_k$ 与 $x_j$ 密度直达。
• 由于 $x_k$ 是核心对象，则 $x_k$ 与 $x_i$ 密度直达。且密度直达是密度可达的子集，所以 $x_k$ 与 $x_j$ 密度可达，$x_k$ 与 $x_i$ 密度可达，所以 $x_i$ 与 $x_j$ 密度相连。