机器学习 DBSCAN聚类算法

admin 管理员组

文章数量: 887017

机器学习 DBSCAN聚类算法

DBSCAN算法

基本概念

工作流程

优势

劣势

代码

DBSCAN算法

基本概念

Density-Based Spatial Clustering of Applications with Noise

• 核心对象：若某个点的密度可达到算法设定的阈值则其为核心点。（即r邻域内点的数量不小于minPts）
• 邻域的距离：设定的半径r，
• minPts：半径内点的数量不小于minPts
• 直接密度可达：若某点p在点q的r邻域内，且q是核心点，则p-q直接密度可达。
• 密度可达：若有一个点的序列q0，q1、....qk，对任意qi-q(i-1)是直接密度可达的，则称从q0到qk密度可达，这实际上是直接密度可达的传播。
• 密度相连：若从某核心点p出发，点q和点k都是密度可达的，则称点q和点k是密度相连的。
• 边界点：属于某一个类的非核心点，不能发展下线了。
• 直接密度可达：若某点p在点q的r邻域内，且q是核心点则p-q直接密度可达。
• 噪声点：不属于任何一个类簇的点，从任何一个核心点出发都是密度不可达的。

1. A：核心对象
2. B，C：边界点
3. N：离群点

工作流程

• 参数D：输入数据集
• 参数e：指定半径
• minPts：密度阈值

优势

1. 不需要指定簇个数
2. 可以发现任意形状的簇
3. 擅长找到离群点（检测任务）
4. 两个参数就够了
5. 可以在聚类的同时发现异常点，对数据集中的异常点不敏感
6. 聚类结果没有偏倚

劣势

1. 高维数据有些困难（可以做降维）
2. 参数难以选择（参数对结果的影响非常大）
3. Sklearn中效率很慢（数据削减策略）
4. 如果样本集的密度不均匀、聚类间距相差很大时，聚类质量较差
5. 如果样本集较大时，聚类收敛时间较长

代码

# -*- coding: utf-8 -*-import numpy as np
import matplotlib.pyplot as plt
import math
import os
from collections import Counter# 未访问
UNVISITED = -2
# 噪声
NOISE = -1def dist(a, b):"""输入：向量A, 向量B输出：两个向量的欧式距离公式略"""return math.sqrt(np.power(a - b, 2).sum())def whether_neighbor(a, b, radius):"""输入：向量A, 向量B输出：是否在领域内"""return dist(a, b) < radiusdef whether_kernel_object(dataSet, selectId, radius):"""输入：数据集, 查询是否是核心对象的点id, 半径大小ϵ输出：[ 在领域范围内的点的id ]"""# 计算在领域范围内有多少点return [i for i in range(dataSet.shape[0]) if whether_neighbor(a=dataSet[selectId], b=dataSet[i], radius=radius)]def visualization(dataSet, resultSet, clusterNumber):"""实现可视化输入：数据集, 结果集, 簇个数"""# 转一下#print(resultSet)res=Counter(resultSet)print('res',res)#key=sorted(res.items())[0]#print('key',key)key=max(res,key=res.get)print('key',key)matResult = np.mat(resultSet).transpose()#print(matResult)dataSet = dataSet.transpose()print(dataSet)# 图figure = plt.figure()# 取红橙黄绿蓝几种颜色colors = ['green', 'blue', 'orange', 'yellow', 'red']# 一行一列第一个ax = figure.add_subplot(111)# 遍历每一个簇for i in range(clusterNumber + 1):# 选一种颜色，若是簇的数目超过颜色数的话从头选color = colors[i % len(colors)]sub = dataSet[:, np.nonzero(matResult[:, 0].A == i)]# 画点 前两个参数为坐标ax.scatter(sub[0, :].flatten().A[0], sub[1, :].flatten().A[0], c=color, s=40)plt.show()def visualization_new(dataSet, resultSet, clusterNumber):"""实现可视化输入：数据集, 结果集, 簇个数将噪点图和去噪后的图作比较"""# 转一下#print(resultSet)res=Counter(resultSet)print('res',res)#key=sorted(res.items())[0]#print('key',key)key=max(res,key=res.get)print('key',key)matResult = np.mat(resultSet).transpose()#print(matResult)dataSet = dataSet.transpose()print(dataSet)# 图#figure = plt.figure()# 取红橙黄绿蓝几种颜色colors = ['green', 'blue', 'orange', 'yellow', 'red']# 一行一列第一个#ax = figure.add_subplot(111)plt.figure(figsize=(10,20))# 遍历每一个簇for i in range(clusterNumber + 1):color = colors[i % len(colors)]sub = dataSet[:, np.nonzero(matResult[:, 0].A == i)]# 画点 前两个参数为坐标plt.subplot(1,2,1)plt.scatter(sub[0, :].flatten().A[0], sub[1, :].flatten().A[0], c=color, s=40)print(i)# 选一种颜色，若是簇的数目超过颜色数的话从头选if i==key:sub = dataSet[:, np.nonzero(matResult[:, 0].A == i)]# 画点 前两个参数为坐标plt.subplot(1,2,2)plt.scatter(sub[0, :].flatten().A[0], sub[1, :].flatten().A[0], c='red', s=40)plt.show()def dbscan(path,radius,minPts):with open(path) as file:# 分行, 逗号分隔,转成listdataSet = [list(map(float, line.strip().split())) for line in file.readlines()]dataSet = np.mat(dataSet)# 点的数目pointNumber = dataSet.shape[0]# 和伪代码一致先将所有的点标为未访问，flagClusterList最终是存放每个点的判定结果，例如簇几、噪声flagClusterList = [UNVISITED] * pointNumber# 簇的数目，也算作下标，从簇1开始# (当前的簇)clusterNumber = 1# 开始遍历for selectPoint in range(pointNumber):# 如果点没有被分类if flagClusterList[selectPoint] == UNVISITED:# 找出邻域里的点neighbors = whether_kernel_object(dataSet=dataSet, selectId=selectPoint, radius=radius)# 不满足最小点if len(neighbors) < minPts:flagClusterList[selectPoint] = NOISEelse:# 划分到当前簇flagClusterList[selectPoint] = clusterNumber# 先将邻域里的其他点装到簇里（和伪代码一致）for neighborsId in neighbors:# 未访问过或是噪声(若是其他簇的话按照先来后到的顺序)if flagClusterList[neighborsId] == UNVISITED or flagClusterList[neighborsId] == NOISE:flagClusterList[neighborsId] = clusterNumber# 扩张while len(neighbors) > 0:# 掏出第一个点currentPoint = neighbors[0]# 查询当前点邻域中的点queryNeighbors = whether_kernel_object(dataSet=dataSet, selectId=currentPoint , radius=radius)# 如果大于等于最小点if len(queryNeighbors) >= minPts:for i in range(len(queryNeighbors)):# 将新的邻域点取出存到N中resultPoint = queryNeighbors[i]if flagClusterList[resultPoint] == UNVISITED:# 如果未访问的话继续往下找，继续扩展neighbors.append(resultPoint)flagClusterList[resultPoint] = clusterNumber# 和上面思想一致elif flagClusterList[resultPoint] == NOISE:flagClusterList[resultPoint] = clusterNumber# 因为N中第一个拿过了，需要刷新neighbors = neighbors[1:]# 该簇结束，创建一个新簇clusterNumber += 1print("簇的个数：" + str(clusterNumber - 1))# 遍历结束# 绘图实现可视化visualization_new(dataSet, flagClusterList, clusterNumber - 1)if __name__ == '__main__':# 初始化参数(懒得写在文件开头了)# 半径radius = 200# 最小点数minPts = 2path='./data'for file in os.listdir(path):filepath=os.path.join(path,file)dbscan(filepath,radius,minPts)

./data/test.txt

 1575  685  1577  705  1577  712  1577  726  1577  734  1578  742  1577  790  1577  794  1577  799  1578  803  1579  807  1578  811  1578  817  1578  822  1579  825  1577  829  1577  835  1573  847  1570  849  1549  867  1546  869  1544  874  1542  875  1541  878  1538  881  1535  884  1532  887  1525  897  1522  900  1483  970  

本文标签： 机器学习 DBSCAN聚类算法