文章目录
前言
题目要求：
- 任选语言（本文选择Python）自实现DBSCAN聚类算法
- 对两个参数ξ和Minpt的选取选取进行说明
- 支持多维数组
- 采用欧氏距离
先上效果图，（项目链接在文章最后）：
提示：以下是本篇文章正文内容
一、关于算法的相关介绍
算法原理DBSCAN详解
感谢CSDN博主「皮卡丘的情绪」的原创文章
以下截取部分
输入：数据集，邻域半径 Eps，邻域中数据对象数目阈值 MinPts;
输出：密度联通簇。
处理流程如下。
- 从数据集中任意选取一个数据对象点 p；
- 如果对于参数 Eps 和 MinPts，所选取的数据对象点 p 为核心点，则找出所有从 p 密度可达的数据对象点，形成一个簇；
- 如果选取的数据对象点 p 是边缘点，选取另一个数据对象点；
- 重复（2）、（3）步，直到所有点被处理。
DBSCAN 算法的计算复杂的度为 O(n²)，n 为数据对象的数目。
这种算法对于输入参数 Eps 和 MinPts 是敏感的。
接下来完成代码复现
二、核心内容
1、数据集介绍
提供一个测试数据集
链接：https://pan.baidu.com/s/1qoq2RFTvPwrJuexevGq3iA
提取码：ygtl
文件命名为：cluster_x-y_z.csv
其中各参数表示一共有x个y维的数据需要聚为z个类
比如： 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)
运行结果截图：
3、参数介绍
此处参数依据聚类的准确率与运行时长来选择最优组合
以下提供部分可以选择的参数，时间单位：微秒
如果有什么更好的选择方式麻烦评论区说一下，感激不尽。
4、完整项目
对核心代码做“亿点点”的改造和包装之后就做成了文章开头的样子，截图如下：
项目完整代码下载链接：
点击跳转
结语
创作不易，如果您觉得写得还行，还请点赞、评论、收藏走一波。