基于划分的聚类算法（K-Means）与基于密度的聚类算法（DBSCAN）的代码实现与分析

2023-12-11 08:10:21

基于划分的聚类算法（K-Means）与基于密度的聚类算法（DBSCAN）对比分析

在开始阅读前可以看一下有关这两个算法的描述和可视化效果展示
Visualizing K-Means Clustering
Visualizing DBSCAN Clustering

使用Python实现了两个算法，算法设计场景是对平面二维样本点的计算

K-Means算法步骤

随机生成k个点作为样本数据的中心点
计算所有点分别到k个中心点的距离
对于二维的每个样本点，比较到哪一个中心点的距离近（欧式距离最小），就被划分到哪一类，并更新样本点的类别表
对于归类后的数据重新计算中心点的坐标
判断中心点是否有明显变化，如果有，跳转到2，如果没有，跳转到6
程序结束，划分完成

DBSCAN算法步骤

设置与样本集等长的访问标记列表(最初所有的点被标记为noise或unvisted)
设置邻域epsilon,点邻域形成团的最少点数量 min_points
遍历样本点集D, 检查点p的表示是否visited，如果unvisited，执行4，否则继续进行遍历直到结束
检查距p在epsilon范围内的点数量是否达到min_points,如果是，则跳转到5
将邻域内所有点加入到该群集clusters中
检查这些点在其邻域内是否有不少于min_points的点，如果是，递归扩充该群集
完全有可能选择的点在其epsilon球中少于minPoints，并且也不属于任何其他群集。如果是这种情况，则将其视为不属于任何群集的“噪声点”。

算法实现

K-Means算法实现

# 计算两点之间的距离，传入narray作为[[],[],[]]做多个点距离计算，axis=1
def dist(a, b, axis=1):
    return np.linalg.norm(a - b, axis=axis)


def kmeans_alg(k, D):
    """
    params:
    k 设定划分的区域数目
    D 样本点数据集
    """
    # 随机初始化中心点 方法一
    center_x = np.random.randint(D.min(0)[0], D.max(0)[0], size=k)
    center_y = np.random.randint(D.min(0)[1], D.max(0)[1], size=k)
    centers = np.array(list(zip(center_x, center_y)), dtype=D[:,0].dtype)
    # 随机初始化中心点 方法二
    centers = D[np.random.randint(0, len(D), size=k)]
    
    # c_new用来保存迭代产生的新中心点坐标
    centers_new = np.zeros(centers.shape)
    # 用于保存数据所属划分
    labels = np.zeros(len(D))
    # 设置容忍度,该变量为迭代前后中心点的变化明显性，低于这个明显性的时候，不再进行迭代
    tol_move = 10.0
    tol = True
    
    while tol:
        for i in range(len(D)):
            #记录每个样本点的所属划分，计算距哪个中心点的距离最小
            cluster = np.argmin(dist(D[i], centers))
            labels[i] = cluster
        for i in range(k):
            # c_p_sets = [D[j] for j in range(len(D)) if labels[j] == i]
            c_p_sets = D[labels == i]        
            if len(c_p_sets)!=0:
                centers_new[i] = np.mean(c_p_sets, axis=0) 
        # 当k个中心点的位置都不再发生变化的时候，结束循环,也可使用tol_move自定义容忍度   
        tol = dist(centers_new, centers).any()
        centers = deepcopy(centers_new)
    return labels, centers

DBSCAN算法实现



# DBSCAN算法中，计算两点之间的距离 [] 
def dist1(a, b,axis=0):
    return np.linalg.norm(a - b,axis=axis)

def find_ngb_eps(p, D,epsilon):
    # 在样本点中寻找p点邻域epsilon内的点,不包含p
    neighbors = [i for i in range(len(D)) if 0<dist1(D[p], D[i]) < epsilon]
    return neighbors

def expand_cluster_rec(labels, p, cid, D, min_points, epsilon):
	# 求群集方法一
    # 递归求群集
    if labels[p] == -1:    
        labels[p]=cid
    if labels[p] == 0:
        labels[p]=cid
        neighbors = find_ngb_eps(p, D, epsilon)
        if(len(neighbors) >= min_points):
            for ngb in neighbors:
                expand_cluster_rec(ngb, cid, D, min_points, epsilon)

def expand_cluster_bfs(labels,p, cid, D, min_points, epsilon):
	# 求群集方法二
    # 广度优先搜索求群集
    expand_queue = Queue()
    expand_queue.put(p)
    while not expand_queue.empty():
        seed = expand_queue.get()
        neighbors = find_ngb_eps(seed, D,epsilon)
        if (len(neighbors) >= min_points):
            for ngb in neighbors:
                if(labels[ngb] == -1):
                    labels[ngb] = cid
                if(labels[ngb] == 0):
                    labels[ngb] = cid
                    expand_queue.put(ngb)

def dbscan_alg(D,epsilon,min_points):
    """
    params:
    两个密度参数epsilon ,min_points
    epsilon  聚类半径
    min_points 聚类点数
    """
    # 样本点所属cluster的id,从1开始
    cid = 0 
    # 样本点的标记 unvisited(0),visited（用该点的cid表示）, noise(用-1表示)
    # 所有样本初始标记为unvisited
    labels = np.zeros(len(D))
    
    
    for i in range(len(D)):
        if labels[i] == 0:
            if(len(find_ngb_eps(i, D,epsilon)) >= min_points):
                cid+=1
                expand_cluster_bfs(labels, i, cid, D, min_points, epsilon)
            else:
                labels[i] = -1
                # 后续的遍历可能会把该点连接为其他cluster,最终的标记为-1，才会被认定为noise
    return labels, cid

聚类效果分析与思考

效果展示采用的方法：

为了展示实现的效果，使用sklearn.cluster的对应KMeans和DBSCAN模型对相同数据集进行聚类，对比分类效果

K-Means聚类效果展示

输入：要事先给出k值，即要生成簇的数目，数据集D
输出：分类结果，各类中心点

效果展示采用的数据集：

使用sklearn.datasets中的聚类数据生成器make_blobs来产生数据集：

X, y = make_blobs(n_samples=150, random_state=170)

数据分布：

效果展示及对比如下：

中心点输出结果：
[[-4.73502019 0.10448638]，[-9.13517967 -5.39468265]，[1.97517735 0.64725381]]

[[ 1.97517735 0.64725381] ，[-9.13517967 -5.39468265] ， [-4.73502019 0.10448638]]

结论：经对比发现自己编程实现的kmeans算法和KMeans模型在数据分类和簇中心点的位置是完全一致的。

DBSCAN聚类效果展示

输入：设定两个关于密度计算的参数，聚类半径（ epsilon ）和聚类点数（ min_points ）
输出：分类结果，DBSCAN不需要事先知道要形成的簇类的数量，通过参数自动得到簇数；

效果展示采用的数据集：

使用sklearn.datasets中的聚类数据生成器make_blobs来产生数据集：

X,y = datasets.make_moons(500,noise = 0.1,random_state=1)

数据分布：

效果展示及对比如下：

本例使用的参数
eps = 0.2
min_points=20

结论：经对比发现自己编程实现的dbscan_alg算法和DBSCAN模型在数据分类结果是完全一致的。

对于DBSCAN算法来说，参数的选择对于聚类质量的影响很大。

令min_points的值不变，增长eps的值，修改为0.25
对比效果如下：（右边是参数修改后分类效果）

可以发现在min_points的值不变，稍微增加eps的值后，可视化图中可以明显发现一部分噪音点因为邻域半径的增加被归为相邻的群集中。
令eps的值不变，增长min_points的值，修改为25
对比效果如下：（左边的是修改后的分类效果）

经过实验，可以发现在eps的值不变，缓慢增加min_points的值，可以发现类别会增多

这两个修改参数的实验效果是和基于密度聚类的算法思想是吻合的。

聚类效果对比分析

案例1:鸢尾花数据集

使用sklearn.datasets中的iris数据集，对数据集进行降维处理，得到本次实验所需的二维数据集，用已知结果对两种算法进行聚类效果的对比分析。

数据分布：

原始标签下的数据分布：

使用原始标签下的数据分布，来对编写的kmeans算法和dbscan算法的聚类效果进行对比分析

聚类效果对比：
左图1是kmeans算法的聚类效果，k设置为3
右图上是DBSCAN算法的一个出现二分类聚类效果的参数设置
右图下是DBSCAN算法的一个出现三分类聚类效果的参数设置
（红星标志为噪音点）

通过上述可视化展示的直观对比分析，可以发现DBSCAN能够降低噪声的干扰，但是聚类的结果与参数的设置有很大的关系，受人为因素的影响很大。受参数的影响，在实验过程中，参数调整后会发现，密度较大且聚集相近的簇会被并到一个簇中，如上图右上的两类就被合并成一类。

案例2:双月数据集

数据分布：

聚类效果对比：
左图是kmeans算法的聚类效果，k设置为2
右图是dbscan算法的聚类效果，参数调试（eps=0.1,min_points=3)使得分类类别数为2

这个实验，意图是想要得到dbscan算法的分类结果，但是由于kmeans算法的是各个点距离中心点的距离，因为算法本身的原因造成了实验结果的不理想，对于这类凹形状的数据分布，Kmeans算法是不适合的，而dbscan的表现是很好的。

附加实验：Kmeans聚类结果探究

问题点一：初始中心点选取对实验结果的影响

初始中心点选取办法一:

1，找到样本点两个维度上的最大值和最小值
2，选取中心点的坐标时，是随机选取样本点各维度的 [ 最小值, 最大值 ] 范围内的整数值；

# D为数据集
center_x = np.random.randint(D.min(0)[0], D.max(0)[0], size=k)
center_y = np.random.randint(D.min(0)[1], D.max(0)[1], size=k)
centers = np.array(list(zip(center_x, center_y)), dtype=D[:,0].dtype)

这样做是考虑让初始中心点的位置在样本点整体范围内分散开；但是缺点是会受到离群点的较大干扰

初始中心点选取办法二：

centers = D[np.random.randint(0, len(D), size=k)]

这样就是在数据集中随机选取k个点，随机性较高，不考虑初始中心点分布位置

问题点二：测试数据集的选用对实验结果的影响

实验展示：

数据集一：
实验中选用的测试集的分布如下：总样本点为1502

实验对比：左图是我的K-Means算法聚类的效果，右图是sklearn库中的KMeans模型的聚类效果。

输入： k=2

左图的各类样本点数量及中心点坐标：

右图的各类样本点数量及中心点坐标：

这是二分类多次实验结果对比发现，结果是完全一致的，并且经过多次的运行，绝大部分两个模型跑出来的都是一致的结果

输入： k=4

k=4实验结果一：中心点位置和各类样本点的分布与模型跑出来的结果出现了明显差异
左图的各类样本点数量及中心点坐标：

[218, 395, 397, 492]

[[ 1.39172245 0.03217653]
[-0.76217937 0.54538487]
[ 0.48779272 -0.26739042]
[ 0.30262734 0.81337307]]

右图的各类样本点数量及中心点坐标：
[218, 385, 428, 471]

[[ 0.74221635 -0.01429847]
[ 0.23034468 0.82802393]
[ 1.72011121 -0.08372242]
[-0.77602224 0.53373488]]

k=4实验结果二：这次选择的结果是和模型跑出结果相似的情况，可以看到样本的分类结果以及中心点的位置都是非常接近的。
左图的各类样本点数量及中心点坐标：

[219, 385, 427, 471]

[[ 0.74115753 -0.01307078]
[-0.77602224 0.53373488]
[ 0.23034468 0.82802393]
[ 1.7177104 -0.08579915]]

右图的各类样本点数量及中心点坐标：
[216, 385, 429, 472]

[[ 0.74399 -0.01948443]
[ 0.23284281 0.8270763 ]
[-0.77602224 0.53373488]
[ 1.72492047 -0.07981352]]

数据集二

实验中选用的测试集的分布如下：总样本点为178

实验对比：左图是我的K-Means算法聚类的效果，右图是sklearn库中的KMeans模型的聚类效果。

k=3

k=3实验结果一：

k=3实验结果二：

k=4

k=4实验结果：样本点分布的区域出现了差异
左图的各类样本点数量及中心点坐标：
[23, 32, 57, 66]
[[-294.43555355 -2.01756568]
[ 270.62843354 1.89743236]
[ 591.6978191 -4.30663452]
[ -49.76163471 3.00866831]]
右图的各类样本点数量及中心点坐标：
[23, 39, 57, 59]
[[ -87.66016499 1.67523347]
[ 591.6978191 -4.30663452]
[ 238.80453682 3.61824549]
[-311.41187791 -2.47189043]]

综上实验得到结论：

K值相同时，Kmeans算法模型在每次运行得到的分类结果一般是不同的，这是受到算法中初始中心点选择的影响
如果选取的数据集的分布是很明显的几个簇，并且选取的k与簇的个数一致时，初始中心点的选取对最后的实验结果的影响就很小了。

码农公寓

基于划分的聚类算法（K-Means）与基于密度的聚类算法（DBSCAN）对比分析

K-Means算法步骤

DBSCAN算法步骤

算法实现

K-Means算法实现

DBSCAN算法实现

聚类效果分析与思考

效果展示采用的方法：

K-Means聚类效果展示

效果展示采用的数据集：

效果展示及对比如下：

DBSCAN聚类效果展示

效果展示采用的数据集：

效果展示及对比如下：

聚类效果对比分析

案例1:鸢尾花数据集

案例2:双月数据集

附加实验：Kmeans聚类结果探究

相关文章