Page 73 - 高中 信息技术 选择性必修4 人工智能初步
P. 73
3.3 聚类
3. 基于密度的方法
大部分聚类算法都通过衡量对象之间的距离来划分簇。因此这样划分出来的簇都会呈
球状分布，导致在发现任意形状的簇时，会遇到困难。而基于密度的方法（Density-Based
Methods）的主要思想是：只要“领域”中的密度（对象或数据点的数量）超过阈值，就
继续增长给定的簇。也就是说，对给定簇中的每个数据点，在给定半径的领域中必须至少
包含最少数目的点。这样的方法可以用来过滤噪声或离群点，发现任意形状的簇。基于这
一思想的典型方法有DBSCAN，如图3-6所示。
广东教育出版社
图3-6 DBSCAN聚类结果图
4. 基于网格的方法
基于网格的方法（Grid-Based Methods）把对象空间量化为有限数目的单元，形成网格
结构，所有的聚类操作都在这个网格结构（即量化空间）中进行。该算法的优点是处理速
度快，其处理时间常常独立于数据对象的数量，只与量化空间中每一维的单元数量有关。
3 . 3 . 2 K-Means聚类算法
K-Means聚类是发现给定数据集的k个簇的算法。簇个数k是用户给定的，每个簇通过
其质心（Centroid），即簇中所有点的中心来描述。
K-Means聚类算法工作时，首先随机确定k个初始点作为质心；接着将数据集中的每个
点分配到一个簇中，即为每个点找距其最近的质心，并将其分配给该质心所对应的簇；然
后把每个簇的质心更新为该簇所有点的平均值。上述流程可用如下伪代码表示：
输入：簇个数k，数据点集合X , …, X
n
1
为k个簇随机初始化它们的质心C , …, C k
1
重复以下步骤直到收敛：
对于每个点X :
i
找到距其最近的质心C：argminD( X , C )
j
i
j
将点X 分配到簇 j 中
i
65 65
21Y3228.indd 65 2019/10/10 14:23:55
