上一篇我們講了K-Means的聚類算法：，K-Means算法需要事先定好聚合多少族群(即K的數(shù)量)，同時(shí)會(huì)受離群點(diǎn)影響較大，如果事先不知道有多少個(gè)族群怎么辦呢？這里就到了DBSCAN算法出場(chǎng)的時(shí)候了
DBSCAN
DBSCAN是一種基于密度的聚類算法，可以根據(jù)樣本分布的緊密程度決定，同一類別的樣本之間是緊密相連的，不同類別樣本聯(lián)系是比較少的。
DBSCAN算法需要用到參數(shù)：
- eps (ε)：一種距離度量，用于定位任何點(diǎn)的鄰域內(nèi)的點(diǎn)。
- minPts：聚類在一起的點(diǎn)的最小數(shù)目，超過(guò)這一閾值才算是一個(gè)族群
DBSCAN聚類完成后會(huì)產(chǎn)生三種類型的點(diǎn)：
- 核心點(diǎn)（Core）——該點(diǎn)表示至少有m個(gè)點(diǎn)在距離n的范圍內(nèi)。
- 邊界點(diǎn)（Border） ——該點(diǎn)表示在距離n處至少有一個(gè)核心。
- 噪聲點(diǎn)（Noise） ——它既不是核心點(diǎn)也不是邊界點(diǎn)。并且它在距離自身n的范圍內(nèi)有不到m個(gè)點(diǎn)。
DBSCAN算法步驟
- 算法通過(guò)任意選取數(shù)據(jù)集中的一個(gè)點(diǎn)（直到所有的點(diǎn)都訪問(wèn)到）來(lái)運(yùn)行。
- 如果在該點(diǎn)的“ε”半徑范圍內(nèi)至少存在“minPoint”點(diǎn)，那么認(rèn)為所有這些點(diǎn)都屬于同一個(gè)聚類。
- 通過(guò)遞歸地重復(fù)步驟1、步驟2 對(duì)每個(gè)相鄰點(diǎn)的鄰域計(jì)算來(lái)擴(kuò)展聚類
DBSCAN的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
- 不需要事先指定聚類的數(shù)量，通過(guò)密度來(lái)聚合在一起
- 對(duì)于復(fù)雜的分布及離群點(diǎn)產(chǎn)生的結(jié)果比K-Means更加合理，如圖：
** 缺點(diǎn)：**
- 如果樣本集的密度不均勻、聚類間距差相差很大時(shí)，聚類質(zhì)量較差
- 算法較復(fù)雜，需要針對(duì)距離閾值和領(lǐng)域樣本閾值進(jìn)行調(diào)參才能產(chǎn)生較好的效果
代碼實(shí)現(xiàn)
# -*- 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 最少樣本數(shù)量
"""
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)
運(yùn)行結(jié)果：
參考
[1] https://baijiahao.baidu.com/s?id=1666471511374947763
[2] https://www.cnblogs.com/hugechuanqi/p/10509307.html
[3].http://www.itdecent.cn/p/e594c2ce0ac0
