上一篇我们讲了K-Means的聚类算法：，K-Means算法需要事先定好聚合多少族群(即K的数量)，同时会受离群点影响较大，如果事先不知道有多少个族群怎么办呢？这里就到了DBSCAN算法出场的时候了
DBSCAN
DBSCAN是一种基于密度的聚类算法，可以根据样本分布的紧密程度决定，同一类别的样本之间是紧密相连的，不同类别样本联系是比较少的。
DBSCAN算法需要用到参数：
- eps (ε)：一种距离度量，用于定位任何点的邻域内的点。
- minPts：聚类在一起的点的最小数目，超过这一阈值才算是一个族群
DBSCAN聚类完成后会产生三种类型的点：
- 核心点（Core）——该点表示至少有m个点在距离n的范围内。
- 边界点（Border） ——该点表示在距离n处至少有一个核心。
- 噪声点（Noise） ——它既不是核心点也不是边界点。并且它在距离自身n的范围内有不到m个点。
DBSCAN算法步骤
- 算法通过任意选取数据集中的一个点（直到所有的点都访问到）来运行。
- 如果在该点的“ε”半径范围内至少存在“minPoint”点，那么认为所有这些点都属于同一个聚类。
- 通过递归地重复步骤1、步骤2 对每个相邻点的邻域计算来扩展聚类
DBSCAN的优缺点
优点：
- 不需要事先指定聚类的数量，通过密度来聚合在一起
- 对于复杂的分布及离群点产生的结果比K-Means更加合理，如图：
** 缺点：**
- 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差
- 算法较复杂，需要针对距离阈值和领域样本阈值进行调参才能产生较好的效果
代码实现
# -*- coding: utf-8 -*-
import math
import random
import matplotlib.pyplot as plt
class DBSCAN(object):
STATUS_UNVISITED = 'unvisited'
STATUS_VISITED = 'visited'
STATUS_GROUP = 1
STATUS_NOGROUP = 0
data = dict()
def __init__(self, e, minPts):
"""
e 最小距离
minPts 最少样本数量
"""
self.e = e
self.minPts = minPts
def nearby(self, id):
nearby_points = list()
for link_id in self.scores[id]:
if self.scores[id][link_id] <= self.e:
nearby_points.append(link_id)
return nearby_points
def visit_nearby_points(self, points, group):
for id in points:
if self.data[id]['is_visited'] == self.STATUS_VISITED \
and self.data[id]['is_group'] == self.STATUS_GROUP:
continue
self.data[id]['is_visited'] = self.STATUS_VISITED
if self.data[id]['is_group'] == self.STATUS_NOGROUP:
group.append(id)
self.data[id]['is_group'] = self.STATUS_GROUP
nearby_points = self.nearby(id)
if len(nearby_points) >= self.minPts:
self.visit_nearby_points(nearby_points, group)
def fit(self, data_set, scores):
self.scores = scores
groups = list()
for index, item in enumerate(data_set):
self.data[index] = {'id': index,
'is_visited': self.STATUS_UNVISITED,
'is_group': self.STATUS_NOGROUP
}
for id in self.data:
if self.data[id]['is_visited'] == self.STATUS_VISITED:
continue
self.data[id]['is_visited'] = self.STATUS_VISITED
nearby_points = self.nearby(id)
if len(nearby_points) >= self.minPts:
group = list()
group.append(id)
self.data[id]['is_group'] = self.STATUS_GROUP
self.visit_nearby_points(nearby_points, group)
groups.append(group)
for id in self.data:
if self.data[id]['is_group'] == self.STATUS_NOGROUP:
groups.append([id])
return groups
def init_data(num, min, max):
data = []
for i in range(num):
data.append([random.randint(min, max), random.randint(min, max)])
return data
def mat_score(data_set):
score = dict()
for i in range(len(data_set)):
score[i] = dict()
for i in range(len(data_set) - 1):
j = i + 1
while j < len(data_set):
score[i][j] = math.sqrt(abs(data_set[i][0] - data_set[j][0]) ** 2 + abs(data_set[i][1] - data_set[j][1]) ** 2)
score[j][i] = score[i][j]
j += 1
return score
def show_cluster(data_set, groups):
plt.title(u'DBSCAN')
mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
for index, group in enumerate(groups):
for i in group:
plt.plot(data_set[i][0], data_set[i][1], mark[index])
plt.xlim(0.0, 100)
plt.ylim(0.0, 100)
plt.show()
if __name__ == '__main__':
data_set1 = init_data(20, 0, 30)
data_set2 = init_data(20, 40, 60)
data_set3 = init_data(20, 70, 100)
data_set = data_set1 + data_set2 + data_set3
score_mat = mat_score(data_set)
groups = DBSCAN(20, 3).fit(data_set, score_mat)
show_cluster(data_set, groups)
运行结果：
参考
[1] https://baijiahao.baidu.com/s?id=1666471511374947763
[2] https://www.cnblogs.com/hugechuanqi/p/10509307.html
[3].https://www.jianshu.com/p/e594c2ce0ac0
网友评论