devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【聚类】一种自适应Eps和Minpts的DBSCAN方法（python实现）_自适应dbscan

作者：不正经 | 2024-05-01 17:39:18

赞

踩

自适应dbscan

一、算法来源

1、DBSCAN算法原型

       这个算法原型非常简单，有很多博主都有写，大家自己去看看就好了，也不用花太多时间，顶多十分钟就能了解个大概。

2、自适应Eps和Minpts参数

       由于该算法对Eps和Minpts参数十分敏感，所以如何确定这两个参数对于DBSCAN来说是很重要的一步，这篇博文是基于李文杰老师的论文《自适应确定DBSCAN算法参数的算法研究》，通过这篇论文，输入数据集即可大致确定这两个参数，从而可以直接在DBSCAN中应用。

二、大致思想

        参考论文中提出的，根据数据集提取出Eps候选项（按从小到大排列），然后再提取出Minpts候选项，随后用这些候选项尝试使用DBSCAN算法进行聚类，如果连续的候选项聚类的类别数目相同，那么选择Eps相对较大的那个最为最终参数输入到DBSCAN算法中去。

        论文中认为如果连续3个Eps候选项聚类的类别数目相同，那么可以认为数据集在这些参数下逐渐收敛，但是我觉得具体最好看图像是否收敛，所以我就简单的在程序里将聚类数目打印出来，读者可以自行选择聚利时使用的Eps和Minpts参数。

三、程序介绍

0、头文件import

  1. import math
  2. import copy
  3. import numpy as np
  4. from sklearn.cluster import DBSCAN

1、首先定义聚类的“距离”，这里将欧式距离作为聚类距离

  1. def dist(a,b):
  2.     """
  3.     :param a: 样本点
  4.     :param b: 样本点
  5.     :return: 两个样本点之间的欧式距离
  6.     """
  7.     return math.sqrt(math.pow(a[0]-b[0],2) + math.pow(a[1]-b[1],2))

2、根据论文求解Eps和Minpts候选项列表

  1. def returnDk(matrix,k):
  2.     """
  3.     :param matrix: 距离矩阵
  4.     :param k: 第k最近
  5.     :return: 第k最近距离集合
  6.     """
  7.     Dk = []
  8.     for i in range(len(matrix)):
  9.         Dk.append(matrix[i][k])
  10.     return Dk
  11.  
  12.  
  13. def returnDkAverage(Dk):
  14.     """
  15.     :param Dk: k-最近距离集合
  16.     :return: Dk的平均值
  17.     """
  18.     sum = 0
  19.     for i in range(len(Dk)):
  20.         sum = sum + Dk[i]
  21.     return sum/len(Dk)
  22.  
  23.  
  24. def CalculateDistMatrix(dataset):
  25.     """
  26.     :param dataset: 数据集
  27.     :return: 距离矩阵
  28.     """
  29.     DistMatrix = [[0 for j in range(len(dataset))] for i in range(len(dataset))]
  30.     for i in range(len(dataset)):
  31.         for j in range(len(dataset)):
  32.             DistMatrix[i][j] = dist(dataset[i], dataset[j])
  33.     return DistMatrix
  34.  
  35.  
  36. def returnEpsCandidate(dataSet):
  37.     """
  38.     :param dataSet: 数据集
  39.     :return: eps候选集合
  40.     """
  41.     DistMatrix = CalculateDistMatrix(dataSet)
  42.     tmp_matrix = copy.deepcopy(DistMatrix)
  43.     for i in range(len(tmp_matrix)):
  44.         tmp_matrix[i].sort()
  45.     EpsCandidate = []
  46.     for k in range(1,len(dataSet)):
  47.         Dk = returnDk(tmp_matrix,k)
  48.         DkAverage = returnDkAverage(Dk)
  49.         EpsCandidate.append(DkAverage)
  50.     return EpsCandidate
  51.  
  52.  
  53. def returnMinptsCandidate(DistMatrix,EpsCandidate):
  54.     """
  55.     :param DistMatrix: 距离矩阵
  56.     :param EpsCandidate: Eps候选列表
  57.     :return: Minpts候选列表
  58.     """
  59.     MinptsCandidate = []
  60.     for k in range(len(EpsCandidate)):
  61.         tmp_eps = EpsCandidate[k]
  62.         tmp_count = 0
  63.         for i in range(len(DistMatrix)):
  64.             for j in range(len(DistMatrix[i])):
  65.                 if DistMatrix[i][j] <= tmp_eps:
  66.                     tmp_count = tmp_count + 1
  67.         MinptsCandidate.append(tmp_count/len(dataSet))
  68.     return MinptsCandidate

3、求解出聚类类别数列表

  1. def returnClusterNumberList(dataset,EpsCandidate,MinptsCandidate):
  2.     """
  3.     :param dataset: 数据集
  4.     :param EpsCandidate: Eps候选列表
  5.     :param MinptsCandidate: Minpts候选列表
  6.     :return: 聚类数量列表
  7.     """
  8.     np_dataset = np.array(dataset)  #将dataset转换成numpy_array的形式
  9.     ClusterNumberList = []
  10.     for i in range(len(EpsCandidate)):
  11.         clustering = DBSCAN(eps= EpsCandidate[i],min_samples= MinptsCandidate[i]).fit(np_dataset)
  12.         num_clustering = max(clustering.labels_)
  13.         ClusterNumberList.append(num_clustering)
  14.     return ClusterNumberList

 四、程序（完全版）

  1. import math
  2. import copy
  3. import numpy as np
  4. from sklearn.cluster import DBSCAN
  5.  
  6.  
  7. def loadDataSet(fileName, splitChar='\t'):
  8.     """
  9.     输入：文件名
  10.     输出：数据集
  11.     描述：从文件读入数据集
  12.     """
  13.     dataSet = []
  14.     with open(fileName) as fr:
  15.         for line in fr.readlines():
  16.             curline = line.strip().split(splitChar)
  17.             fltline = list(map(float, curline))
  18.             dataSet.append(fltline)
  19.     return dataSet
  20.  
  21.  
  22. def dist(a,b):
  23.     """
  24.     :param a: 样本点
  25.     :param b: 样本点
  26.     :return: 两个样本点之间的欧式距离
  27.     """
  28.     return math.sqrt(math.pow(a[0]-b[0],2) + math.pow(a[1]-b[1],2))
  29.  
  30.  
  31. def returnDk(matrix,k):
  32.     """
  33.     :param matrix: 距离矩阵
  34.     :param k: 第k最近
  35.     :return: 第k最近距离集合
  36.     """
  37.     Dk = []
  38.     for i in range(len(matrix)):
  39.         Dk.append(matrix[i][k])
  40.     return Dk
  41.  
  42.  
  43. def returnDkAverage(Dk):
  44.     """
  45.     :param Dk: k-最近距离集合
  46.     :return: Dk的平均值
  47.     """
  48.     sum = 0
  49.     for i in range(len(Dk)):
  50.         sum = sum + Dk[i]
  51.     return sum/len(Dk)
  52.  
  53.  
  54. def CalculateDistMatrix(dataset):
  55.     """
  56.     :param dataset: 数据集
  57.     :return: 距离矩阵
  58.     """
  59.     DistMatrix = [[0 for j in range(len(dataset))] for i in range(len(dataset))]
  60.     for i in range(len(dataset)):
  61.         for j in range(len(dataset)):
  62.             DistMatrix[i][j] = dist(dataset[i], dataset[j])
  63.     return DistMatrix
  64.  
  65.  
  66. def returnEpsCandidate(dataSet):
  67.     """
  68.     :param dataSet: 数据集
  69.     :return: eps候选集合
  70.     """
  71.     DistMatrix = CalculateDistMatrix(dataSet)
  72.     tmp_matrix = copy.deepcopy(DistMatrix)
  73.     for i in range(len(tmp_matrix)):
  74.         tmp_matrix[i].sort()
  75.     EpsCandidate = []
  76.     for k in range(1,len(dataSet)):
  77.         Dk = returnDk(tmp_matrix,k)
  78.         DkAverage = returnDkAverage(Dk)
  79.         EpsCandidate.append(DkAverage)
  80.     return EpsCandidate
  81.  
  82.  
  83. def returnMinptsCandidate(DistMatrix,EpsCandidate):
  84.     """
  85.     :param DistMatrix: 距离矩阵
  86.     :param EpsCandidate: Eps候选列表
  87.     :return: Minpts候选列表
  88.     """
  89.     MinptsCandidate = []
  90.     for k in range(len(EpsCandidate)):
  91.         tmp_eps = EpsCandidate[k]
  92.         tmp_count = 0
  93.         for i in range(len(DistMatrix)):
  94.             for j in range(len(DistMatrix[i])):
  95.                 if DistMatrix[i][j] <= tmp_eps:
  96.                     tmp_count = tmp_count + 1
  97.         MinptsCandidate.append(tmp_count/len(dataSet))
  98.     return MinptsCandidate
  99.  
  100.  
  101. def returnClusterNumberList(dataset,EpsCandidate,MinptsCandidate):
  102.     """
  103.     :param dataset: 数据集
  104.     :param EpsCandidate: Eps候选列表
  105.     :param MinptsCandidate: Minpts候选列表
  106.     :return: 聚类数量列表
  107.     """
  108.     np_dataset = np.array(dataset)  #将dataset转换成numpy_array的形式
  109.     ClusterNumberList = []
  110.     for i in range(len(EpsCandidate)):
  111.         clustering = DBSCAN(eps= EpsCandidate[i],min_samples= MinptsCandidate[i]).fit(np_dataset)
  112.         num_clustering = max(clustering.labels_)
  113.         ClusterNumberList.append(num_clustering)
  114.     return ClusterNumberList
  115.  
  116. if __name__ == '__main__':
  117.     dataSet = loadDataSet('788points.txt', splitChar=',')
  118.     EpsCandidate = returnEpsCandidate(dataSet)
  119.     DistMatrix = CalculateDistMatrix(dataSet)
  120.     MinptsCandidate = returnMinptsCandidate(DistMatrix,EpsCandidate)
  121.     ClusterNumberList = returnClusterNumberList(dataSet,EpsCandidate,MinptsCandidate)
  122.     print(EpsCandidate)
  123.     print(MinptsCandidate)
  124.     print('cluster number list is')
  125.     print(ClusterNumberList)

五、相关文件

我会将txt文件和程序放在以下位置：

https://download.csdn.net/download/liyihao17/11125093

https://download.csdn.net/download/liyihao17/11125098

另外我也在github上放了

https://github.com/liyihao17/KANN-DBSCAN

需要的读者可以自行下载，相关论文读者可以自行去知网搜索下载

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/519963
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号