K-means聚类与DBSCAN的比较

Dear 丶 2022-06-07 02:25 154阅读 0赞

K-means与DBSCAN都是常见的聚类算法，在比较它们之前，我们先看一下两个算法的处理过程。

#### 1 K-means聚类的过程： ####

1）从n个数据对象中任意选出k个对象作为初始的聚类中心；  
2）计算剩余的各个对象到聚类中心的距离，将它划分给最近的簇；  
3）重新计算每一簇的平均值（中心对象）；  
4）循环2-3直到每个聚类不再发生变化为止。

#### 2 DBSCAN算法涉及到几个定义 ####

2.1 定义  
**核心点**：这些点在基于密度的簇内部。点的邻域由距离函数和用户指定的距离参数Eps决定。核心点的定义是，如果该点的给定邻域的点的个数超过给定的阈值MinPts，其中MinPts也是一个用户指定的参数。  
**边界点**：边界点不是核心点，但它落在某个核心点的邻域内。  
**噪声点**：噪声点是既非核心点也非边界点的任何点。

2.2 DBSCAN的过程：  
DBScan需要二个参数： 扫描半径 (eps)和最小包含点数(minPts)。

1） 任选一个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点；  
2） 如果 附近点的数量 ≥ minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的方法处理该簇内所有未被标记为已访问(visited)的点，从而对簇进行扩展；  
3） 如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点；  
4） 如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点。

#### 3 K-means与DBSCAN的区别 ####

*  K-means使用簇的基于原型的概念，而DBSCAN使用基于密度的概念。
 *  K-means只能用于具有明确定义的质心（如均值）的数据。DBSCAN要求密度定义（基于传统的欧几里得密度概念）对于数据是有意义的。
 *  K-means需要指定簇的个数作为参数，DBSCAN不需要事先知道要形成的簇类的数量，DBSCAN自动确定簇个数。
 *  与K-means方法相比，DBSCAN可以发现任意形状的簇类。DBSCAN可以处理不同大小和不同形状的簇，K-means很难处理非球形的簇和不同形状的簇。
 *  K-means可以用于稀疏的高纬数据，如文档数据。DBSCAN则不能很好反映高维数据。
 *  K-means可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。