DBSCAN聚类算法

wu小胖

16339人浏览 · 2020-07-25 16:05:46

wu小胖 · 2020-07-25 16:05:46 发布

一、DBSCAN算法是一种基于密度的聚类算法，聚类的时候不需要预先指定簇的个数，最终簇的个数不确定。
DBSCAN算法将数据点分为三类：
1、核心点：在半径Eps内含有超过MinPts数目的点。
2、边界点：在半径Eps内点的数量小于MinPts，但是落在核心点的邻域内的点。
3、噪音点：既不是核心点也不是边界点的点。
在这里插入图片描述
DBSCAN算法流程：
1、将所有点标记为核心点、边界点或噪声点；
2、删除噪声点；
3、为距离在Eps之内的所有核心点之间赋予一条边；
4、每组连通的核心点形成一个簇；
5、将每个边界点指派到一个与之关联的核心点的簇中（哪一个核心点的半径范围之内）。
二、以中国MOOC大学《Python机器学习基础》课程练习材料实现，通过DBSCAN聚类，分析学生上网时间和上网时长的模式。原始数据集是校园网的日志数据，单条记录格式如下：
在这里插入图片描述
原始数据处理相关代码如下：

import numpy as np
import sklearn.cluster as skc
from sklearn import metrics
import matplotlib.pyplot as plt

onlinetimes = []    #存储开始上网时间和上网时长
f = open('Dbscan_Data.txt', encoding='utf-8')  #读取数据
for line in f:
    line = line.split(',')
    onlinetime = int(line[6])   #读取每条数据中的上网时长
    starttime = int(line[4].split(' ')[1].split(':')[0])    #读取每条数据中的开始上网时间
    onlinetimes.append((starttime, onlinetime)) 
real_X = np.array(onlinetimes).reshape((-1, 2)) #将列表转化为两列的矩阵

开始上网时间聚类实现相关代码如下：

X = real_X[:, 0:1]  #截取第一列,即开始上网时间
db = skc.DBSCAN(eps=0.01, min_samples=20).fit(X)    #调用DBSCAN方法进行训练，eps是两个样本被看作邻居节点的最大距离，min_sample是簇的样本数
labels = db.labels_ #获得每个数据的簇标签
ratio = len(labels[labels[:] == -1]) / len(labels)  #计算噪声数据（label为-1）所占的比例
print('Noise ratio:', format(ratio, '.2%'))
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0) #计算簇的个数
print('Estimated number of clusters: %d' % n_clusters_)
print('Silhouette Coefficient: %0.3f' % metrics.silhouette_score(X, labels))    #聚类效果评价,轮廓系数取值为[-1,1],越趋近于1代表内聚度和分离度都相对较优
for i in range(n_clusters_):    #打印各簇标号以及各簇内数据
    print('Cluster ', i, ':')
    print(list(X[labels == i].flatten()))

其聚类结果如下：
在这里插入图片描述
可以看到学生上网时间主要集中在早上7：00-8：00、晚上20：00-23：00，其中晚上22：00和23：00数量尤其显著。
上网时长聚类实现相关代码如下：

x=real_X[:,1:]   #截取第二列,即上网时长
#plt.hist(x)
#plt.show()
X=np.log(1+x)   #进行对数变换，改进数据分布
#plt.hist(X)
#plt.show()
db=skc.DBSCAN(eps=0.14,min_samples=10).fit(X)   #调用DBSCAN方法进行训练
labels=db.labels_   #获得每个数据的簇标签
ratio=len(labels[labels[:]==-1])/len(labels)    #计算噪声数据（label为-1）所占的比例
print('Noise ratio:',format(ratio,'.2%'))
n_clusters_=len(set(labels))-(1 if -1 in labels else 0) #计算簇的个数
print('Estimated number of clusters: %d'%n_clusters_)
print('Silhouette Coefficient: %0.3f' % metrics.silhouette_score(X, labels)) #聚类效果评价
for i in range(n_clusters_):	#统计每个簇内的样本个数、均值、标准差
    print('Cluster ', i, ':')
    count = len(X[labels == i])
    mean = np.mean(x[labels == i])
    std = np.std(x[labels == i])
    print('\t number of sample: ', count)
    print('\t mean of sample: ', format(mean, '.1f'))
    print('\t std of sample: ', format(std, '.1f'))