Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。

文章目录


前言

题目要求:

  • 任选语言(本文选择Python)自实现DBSCAN聚类算法
  • 对两个参数ξ和Minpt的选取选取进行说明
  • 支持多维数组
  • 采用欧氏距离

先上效果图,(项目链接在文章最后):

Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。


提示:以下是本篇文章正文内容

一、关于算法的相关介绍

算法原理DBSCAN详解
感谢CSDN博主「皮卡丘的情绪」的原创文章

以下截取部分

输入:数据集,邻域半径 Eps,邻域中数据对象数目阈值 MinPts;
输出:密度联通簇。
处理流程如下。

  1. 从数据集中任意选取一个数据对象点 p;
  2. 如果对于参数 Eps 和 MinPts,所选取的数据对象点 p 为核心点,则找出所有从 p 密度可达的数据对象点,形成一个簇;
  3. 如果选取的数据对象点 p 是边缘点,选取另一个数据对象点;
  4. 重复(2)、(3)步,直到所有点被处理。

DBSCAN 算法的计算复杂的度为 O(n²),n 为数据对象的数目。
这种算法对于输入参数 Eps 和 MinPts 是敏感的。

接下来完成代码复现

二、核心内容

1、数据集介绍

提供一个测试数据集

链接:https://pan.baidu.com/s/1qoq2RFTvPwrJuexevGq3iA
提取码:ygtl

文件命名为:cluster_x-y_z.csv
其中各参数表示一共有x个y维的数据需要聚为z个类
Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。

比如: cluster_500-10_7.csv 表示 500个初始点,特征量有10维,需要聚为7个类。数据集中,target为聚类目标量,可用来后期校验结果正确性

2、核心代码


import numpy as np
import pandas as pd
import time


start = time.time()

# 读取数据
read_df = pd.read_csv('../../datas/cluster_500-10_7.csv')

target = read_df.iloc[:, -1]
data = read_df.iloc[:, 1:-1]

k = 7
n = data.shape[0]

# 初始化dis矩阵
dis = np.zeros([n, n])
# 求两两簇(点)之间的距离
for i in range(n - 1):
    for j in range(i + 1, n):
        dis[j][i] = ((data.iloc[j] - data.iloc[i]) ** 2).sum()
    print("初始化dis矩阵进度:{}/{}".format(i + 1, n))
# 下三角复制到上三角
i_lower = np.triu_indices(n, 0)
dis[i_lower] = dis.T[i_lower]
print("初始化dis矩阵进度:{}/{}".format(n, n))

def Exactitude(pre_target, c_num):
    """
    Exactitude的相关定义放在了完整的项目代码中(文末查看)此处不影响使用
    完全预测正确返回0
    """
    pass

######### 以下是重中之重 #########

def regionQuery(p, dis, Eps):
    """
    返回点p的密度直达点
    """
    neighbors = np.where(dis[:, p] <= Eps ** 2)[0]
    return neighbors

def growCluster(dis, pre_target, labels, p, Eps, MinPts):
    """
    寻找p点的所有密度可达点,形成最终一个簇
    输入:距离矩阵、预测标签、初始点p、是否被遍历过的标签、邻域半径、邻域中数据对象数目阈值
    """
    
    # 如果该点已经经过遍历,结束对该点的操作
    if labels[p] == -1:
        return labels, pre_target
    
    # p的密度直达点
    NeighborPts = regionQuery(p, dis, Eps)
    
    # 遍历p的密度直达点
    i = 0
    while i < len(NeighborPts):
        Pn = NeighborPts[i]
        # 找出Pn的密度直达点
        PnNeighborPts = regionQuery(Pn, dis, Eps)
        # 如果此时的点是核心点
        if len(PnNeighborPts) >= MinPts:
            # 将点Pn的新的密度直达点加入点簇
            Setdiff1d = np.setdiff1d(PnNeighborPts, NeighborPts)  # 在PnNeighborPts不在NeighborPts中
            NeighborPts = np.hstack((NeighborPts, Setdiff1d))
        # 否则,说明为边界点,什么也不需要做
        # NeighborPts = NeighborPts
        i += 1

    # 将点p密度可达各点归入p所在簇
    pre_target[NeighborPts] = pre_target[p]
    labels[NeighborPts] = -1
    return labels, pre_target

def DBSCAN(n, k ,dis, Eps, MinPts, mode=2):
    """
    输入:距离矩阵、邻域半径、邻域中数据对象数目阈值
    输出:mode==1:预测值准确性(平均标准差),运行时间;mode==2:预测值
    """
    temp_start = int(round(time.time() * 1000000))

    p = 0
    labels = np.zeros(n)  # 有两个可能的值:-1:完成遍历的;0:这个点还没经历过遍历,初始均为0
    pre_target = np.arange(n)
    
    if mode == 2:
        print("开始循环迭代")

    # 从第一个点开始遍历
    while p < n:
        # 寻找当前点的密度可达点,形成一个簇
        labels, pre_target = growCluster(dis, pre_target, labels, p, Eps, MinPts)
        # 此时的簇数
        c_num = len(np.unique(pre_target))
        if mode == 2:
            print("循环迭代次数:{},此时有{}个簇".format(p + 1, c_num))
        # 分成小于k簇直接跳出循环(说明分得有问题)
        # 分成正好k簇也跳出循环,直接去检查有没有分对
        if c_num <= k:
            break
        p += 1

    if mode == 2:
        print("结束循环迭代")

    temp_stop = int(round(time.time() * 1000000))

    if mode == 1:
        return Exactitude(pre_target, c_num), temp_stop - temp_start
    elif mode == 2:
        return pre_target

######### 以上是重中之重 #########

# 经过观察,Eps=4.0,MinPts=29可作为参数传入,
# 准确率100%
# 再次提示,测试、参数调整过程及可视化所用相关在文末完整项目中提供
# pre_target = DBSCAN(n=n, k=k, dis=dis, Eps=4.0, MinPts=29, mode=1)

pre_target = DBSCAN(n=n, k=k, dis=dis, Eps=4.0, MinPts=29)

#pca降维
from sklearn.decomposition import PCA

pca = PCA(n_components=2)
newData = pca.fit_transform(data)
newData = pd.DataFrame(newData)

# 可视化
import matplotlib.pyplot as plt

x = np.array(newData.iloc[:, 0])
y = np.array(newData.iloc[:, 1])

# 原数据
plt.subplot(2, 1, 1)
plt.scatter(x, y, c=np.array(target))
# 预测数据
plt.subplot(2, 1, 2)
plt.scatter(x, y, c=pre_target)
plt.show()

end = time.time()
print(end - start)

运行结果截图:
Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。

3、参数介绍

此处参数依据聚类的准确率与运行时长来选择最优组合
以下提供部分可以选择的参数,时间单位:微秒
Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。
如果有什么更好的选择方式麻烦评论区说一下,感激不尽。

4、完整项目

对核心代码做“亿点点”的改造和包装之后就做成了文章开头的样子,截图如下:
Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。
项目完整代码下载链接:

点击跳转


结语

创作不易,如果您觉得写得还行,还请点赞、评论、收藏走一波。
Python自实现DBSCAN聚类算法,支持多维数组,距离用欧式距离。

上一篇:PHP-Audit-Labs-day5


下一篇:ASP.NET获取在线接口数据HttpGet