上一篇我们讲了K-Means的聚类算法：，K-Means算法需要事先定好聚合多少族群(即K的数量)，同时会受离群点影响较大，如果事先不知道有多少个族群怎么办呢？这里就到了DBSCAN算法出场的时候了

DBSCAN

DBSCAN是一种基于密度的聚类算法，可以根据样本分布的紧密程度决定，同一类别的样本之间是紧密相连的，不同类别样本联系是比较少的。

DBSCAN算法需要用到参数：

• eps (ε)：一种距离度量，用于定位任何点的邻域内的点。
• minPts：聚类在一起的点的最小数目，超过这一阈值才算是一个族群

DBSCAN聚类完成后会产生三种类型的点：

• 核心点（Core）——该点表示至少有m个点在距离n的范围内。
• 边界点（Border） ——该点表示在距离n处至少有一个核心。
• 噪声点（Noise） ——它既不是核心点也不是边界点。并且它在距离自身n的范围内有不到m个点。

DBSCAN算法步骤

1. 算法通过任意选取数据集中的一个点（直到所有的点都访问到）来运行。
2. 如果在该点的“ε”半径范围内至少存在“minPoint”点，那么认为所有这些点都属于同一个聚类。
3. 通过递归地重复步骤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