点击上方卡片链接就可以进入专栏，专栏右上角有订阅选项，欢迎大家订阅～

前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第2.3节：聚类算法-DBSCAN。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

一、原理

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类算法）是一种常见的密度聚类算法，其主要思想是将高密度地区视为“簇”，并将其他区域视为噪声。DBSCAN可以处理任意形状的簇，并能够识别和剔除噪声点，因此在实际应用中被广泛使用。

1. 核心概念

在 DBSCAN 中，有一些核心概念作为算法的参数进行应用，下面简单进行介绍：

1）邻域半径 Eps

Eps 是用来定义一个样本点邻域范围的最大半径。一个点的邻域包括其本身及在其 Eps 距离内的所有样本点。邻域半径Eps越大，领域会包含更多的数据，聚簇也就越大。

2）最小点数 MmPtS

在一个邻域的半径内minPts数的邻域被认为是一个簇。

3）核心点

在半径 Eps 内含有超过 MinPts 数目的数据点。如果一个点 p 在距离 Eps 范围内有至少 MinPts 个点（包括自己），则这个点被称为核心点。核心点对应稠密区域内部的点。

4）边界点

如果一个数据点在其半径 Eps 内含有数据量小于 MinPts，但是该数据点落在核心点的邻域内，则该数据点为边界点。边界点对应稠密区域边缘的点。

5）离群点

既不是核心点也不是边界点的数据点，称为离群点。离群点对应稀疏区域中的点。

以下图为例，假定最小点数 MmPtS=5，则：

• 点 A 为核心点，其Eps邻域内超过了5个点；
• 点 B 为边界点，其Eps邻域内小于5个点，且落在了点A的Eps邻域内；
• 点 C 为离群点，其Eps邻域内小于5个点，且没有落在任何核心点的邻域内。

根据以上核心概念，DBSCAN 算法还延伸出了以下定义：

1）Eps 领域

与点的距离小于等于Eps的所有点的集合。

2）直接密度可达

如果点p在核心点q的Eps邻域内，则称数据对象p从数据对象q出发是直接密度可达的。

3）密度可达

如果存在数据链，数据链中是从关于EpS和MinPts直接密度可达的，则数据点是从数据点关于Eps和MinPts密度可达的。

4）密度相连

对于数据点p和q，如果存在核心点o，使数据点p和q均从o密度可达，则称数据点p和q关于Eps和MinPts密度相连。

5）密度聚类簇

由一个核心点和与其密度可达的所有数据点构成一个密度聚类簇。

以下图为例，点 a 为核心点，点 b 为边界点，并且因为 a 直接密度可达 b。但是 b 不直接密度可达 a（因为 b 不是一个核心点）。因为 c 直接密度可达 a，a 直接密度可达 b，所以 c 密度可达 b。但是因为 b 不直接密度可达 a，所以 b 不密度可达 c。但是 b 和 c 密度相连。

2. 算法流程

DBSCAN 算法的聚类本质上是将密度相连的样本点划分到同一个簇中。DBSCAN 聚类簇可以包含一个或多个核心点。当簇内只有一个核心点时，该核心点的 Eps 邻域内包含簇内所有其他非核心点样本。当簇内存在多个核心点时，簇内任意一个核心点的 Eps 邻域内必定包含另一个核心点，否则它们之间无法建立密度可达关系。这些核心点的 Eps 邻域内的所有样本集合则形成了一个DBSCAN 聚类簇。

具体算法流程：

1）初始化：输入参数包括数据集 D，邻域半径阈值 eps，样本点最小个数阈值 MinPts。

2）对数据集中所有对象进行标记：如果一个点的邻域中的点的个数不小于 MinPts，则该点被标记为核心点；如果一个点的邻域中的点的个数小于 MinPts，但其仍然在某个核心点的邻域内，则该点被标记为边界点；否则，该点被标记为噪声点。

3）从任意一个未访问的核心点开始，利用核心点的可达性，递归遍历该核心点的所有密度可达点，并将其加入到一个簇中，直到一个簇被完全遍历完成。

4）不断寻找核心点，不断寻找并扩展新的簇。

5）直到所有的核心点均被访问过后，聚类结束。

二、面试真题

1. DBSCAN聚类的优缺点？

1）优点：

• 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集；
• 可以在聚类的同时发现异常点