DBSCAN

2. DBSCAN密度聚类

2.1 DBSCAN算法

是一种基于密度的聚类算法:

  • 聚类的时候不需要预先指定簇的个数
  • 最终的簇的个数不定

2.2 DBSCAN算法将数据点分为三类:

  • 核心点:在半径Eps内含有超过MinPts数目的点
  • 边界点:在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内
  • 噪音点:既不是核心点也不是边界点的点

2.3 DBSCAN算法流程:

  1. 将所有点标记为核心点、边界点或噪声点;
  2. 删除噪声点;
  3. 为距离在Eps之内的所有核心点之间赋予一条边;
  4. 每组连通的核心点形成一个簇;
  5. 将每个边界点指派到一个与之关联的核心点的簇中(哪一个核心点的半 径范围之内)。

举例:有如下13个样本点,使用DBSCAN进行聚类

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13
X 1 2 2 4 5 6 6 7 9 1 3 5 3
Y 2 1 4 3 8 7 9 9 5 12 12 12 3

取Eps=3,MinPts=3,依 据DBSACN对所有点进行聚类 (曼哈顿距离)。 对每个点计算其邻域Eps=3内 的点的集合。

  • 集合内点的个数超过 MinPts=3的点为核心点
  • 查看剩余点是否在核心点的邻 域内,若在,则为边界点,否 则为噪声点。对每个点计算其邻域Eps=3内 的点的集合。
  • 集合内点的个数超过 MinPts=3的点为核心点
  • 查看剩余点是否在核心点的邻 域内,若在,则为边界点,否 则为噪声点。 距离不超过Eps=3的点相互 连接,构成一个簇,核心点邻域 内的点也会被加入到这个簇中。 则右侧形成3个簇。

2.4 DBSCAN的应用实例

数据介绍:

现有大学校园网的日志数据,290条大学生的校园网使用情况数据,数据包 括用户ID,设备的MAC地址,IP地址,开始上网时间,停止上网时间,上 网时长,校园网套餐等。利用已有数据,分析学生上网的模式。

实验目的:

通过DBSCAN聚类,分析学生上网时间和上网时长的模式。 技术路线:sklearn.cluster.DBSCAN

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


mac2id=dict()
onlinetimes=[]
f=open('TestData.txt',encoding='utf-8')
for line in f:
    mac=line.split(',')[2]
    onlinetime=int(line.split(',')[6])
    starttime=int(line.split(',')[4].split(' ')[1].split(':')[0])
    if mac not in mac2id:
        mac2id[mac]=len(onlinetimes)
        onlinetimes.append((starttime,onlinetime))
    else:
        onlinetimes[mac2id[mac]]=[(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)
labels = db.labels_

print('Labels:')
print(labels)
raito=len(labels[labels[:] == -1]) / len(labels)
print('Noise raito:',format(raito, '.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,':')
    print(list(X[labels == i].flatten()))

plt.hist(X,24)

DBSCAN主要参数:

eps: 两个样本被看作邻居节点的最大距离

min_samples: 簇的样本数

metric:距离计算方式

例:sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean')

详细:http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN

参考资料

  • 北京理工大学 礼欣 www.python123.org
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学