---

基于密度的聚类方法 DBSCAN

将 簇 看作是数据空间中被低密度区域（代表噪声/噪点）分割开的 稠密对象区域 （簇的定义：密度相连的点的最大集合）。

将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。

一、基础概念：

• 邻域：

  半径为 $r$ 的圆，其包含的范围称为 $r$ 邻域。

• 密度：

  给定 $r$ 邻域内最小的对象点数目 $m$ （又可称为最小邻居数）。

• 高密度区域：

  在某一个 $r$ 邻域内至少需要包含 $m$ 个对象点（$\ge m$），就可定义为高密度区域。

• 核心点：

  若某邻域以某一个对象点为圆心，且其满足高密度要求（包含该点），则称该对象点为核心对象。

• 边界点：

  若某邻域以某一个对象点为圆心，但其不满足高密度要求（包含该点），不过处于某个核心对象的邻域内，则称该对象点为边界对象。

• 邻域点（补充的概念）：

  某个点的邻域内的其他点。

• 离群点（噪声）：

  既不是核心对象，也不是边界对象。

• 直接密度可达：

  如果某个对象点 $B$ 处于某个核心对象点 $A$ 的邻域内，则认为对象点 $B$ 是 从核心对象点 $A$ 出发，关于 $r$ 和 $m$ 直接密度可达的 。

  （ $B$ 和 $A$ 都可以是核心对象点）。

  简单理解为：若某个点处于核心对象点的邻域内，则说该点是 从核心对象点出发，关于 $r$ 和 $m$ 直接密度可达的（邻域半径规定为 $r$ ）。

  ​ 或者说某个点的邻域内有核心对象点，则说该点是 从核心对象点出发，关于 $r$ 和 $m$ 直接密度可达的（邻域半径规定为 $r$ ）。

• 密度可达：

  如果存在一个对象链 $P_1,P_2,...,P_n$ ，其中 $P_{i+1}$ 是从核心对象点 $P_i$ 出发，关于 $r$ 和 $m$ 直接密度可达的，则对象点 $P_n$ 是从 $P_1$ 出发，关于 $r$ 和 $m$ 密度可达的。其中 $P_n$ 既可以是核心对象点，也可以是边界对象点。（这里有一个隐藏事实：前 $n-1$ 个点均是核心对象点）

  简单理解为：若有由 $n-1$ 个核心对象点 + 一个非离群点组成的对象链，那么此非离群点和前 $n-2$ 个核心对象点都可叫做 密度可达的。

• 密度相连：

  如果存在核心对象点 $O$ ，使对象点 $P$ 和对象点 $Q$ 都是从核心对象点 $O$ 出发，关于 $r$ 和 $m$ 密度可达 的，那么对象点 $P$ 和 $Q$ 相互关于 $r$ 和 $m$ 密度相连。

二、图解

1）邻域、密度、高密度区域、低密度区域、核心对象点、边界对象点、离 群点：

2）直接密度可达、密度可达、密度相连：

三、算法核心及示例

$DBSCAN$ 通过检查数据库中每点的邻域来搜索簇。

如果点 $P$ 的邻域包含的点多于 $m$ 个，则创建一个以 $P$ 为核心对象的新簇。然后 $DBSCAN$ 迭代地聚集从这个核心对象密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以添加到任何簇时，该过程结束。

1）算法步骤（四步）：

1. 找到所有核心点以及它的邻域点：

   • 详细步骤：计算每个点到其他所有点之间的距离，找出小于等于 $r$ 的距离个数以及对应点，满足要求的就是核心点（记住：自己也算一个点数）；

2. 围绕第一个核心点创建簇，将其邻域边界点分配与核心点相同的簇，并进行辐射扩展簇：

   • 详细步骤：
   • 先围绕第一个找到的核心点创建簇，同时将其标记为“已经访问”；
   • 将其邻域点依次拉进此簇中，同时标记为“已经访问”，并判断该邻域点是不是核心点，若是则将该点的邻域点也拉进来；
   • 以此类推…

3. 对每个核心点，如果它没有被分配给现有簇，则创建一个新簇；

4. 重复上述步骤，直到访问完所有核心点，不属于任何簇的点被认为是噪声点。

2）代码展示 (MATLAB)

D = pdist2(X, X); 函数介绍：

在 MATLAB 中，D = pdist2(X, X); 的作用是计算矩阵 X 中各对行向量之间的欧几里得距离，并将这些距离存储在矩阵 D 中。

• pdist2(X, X)的两个输入矩阵都是 X，这意味着我们要计算 X 中每一对行向量之间的距离。

• X：输入矩阵，尺寸为n×m，n表示样本数，m表示特征数（即坐标维度）。例如：

  % 特征数为3，第一列表示x轴坐标，第二列表示y轴坐标，第三列表示z轴坐标
  [[1, 3, 4]
   [2, 5, 2]
   [6, 1, 3]]
  

• D：D 是一个方阵，其中 D(i, j) 表示 X 中第 i 行和第 j 行之间的欧几里得距离。

• 欧几里得距离是指两个点在 n 维空间中彼此之间的直线距离。

算法代码：

代码里的 epsilon 就是理论中的 r ， MinPts 就是理论中的 m 。

function IDX = DBSCAN(X, epsilon, MinPts)
% 输入：
%   X:          输入数据矩阵 [n×m]，n为样本数, m为特征数 (例如3D坐标就是 m=3)
%   epsilon:    邻域半径
%   MinPts:     最小邻居数
% 输出：
%   IDX: 聚类标签 [n×1]，噪声点=-1，簇编号从1开始

    n = size(X,1);                  % 样本数量
    IDX = -1 * ones(n,1);           % 默认全是噪声
    visited = false(n,1);           % 是否访问过
    C = 0;                          % 当前簇编号

    for i = 1:n
        if ~visited(i)
            visited(i) = true;
            Neighbors = RegionQuery(X,i,epsilon);
            if numel(Neighbors) >= MinPts
                C = C + 1;  % 新建簇
                ExpandCluster(i, Neighbors, C);
            end
        end
    end

    % ===== 内部函数 =====
    % 扩展簇
    function ExpandCluster(i, Neighbors, C)
        IDX(i) = C;
        k = 1;
        while k <= numel(Neighbors)
            j = Neighbors(k);
            if ~visited(j)
                visited(j) = true;
                Neighbors2 = RegionQuery(X,j,epsilon);
                if numel(Neighbors2) >= MinPts
                    % 合并去重
                    Neighbors = union(Neighbors, Neighbors2);
                end
            end
            if IDX(j) == -1  % 还未分配簇
                IDX(j) = C;
            end
            k = k + 1;
        end
    end

    % 查找某点的邻域
    function Neighbors = RegionQuery(X,i,epsilon)
        d = pdist2(X(i,:), X);            % 计算到所有点的距离
        Neighbors = find(d <= epsilon);   % 找到在半径内的点
    end


end

3）实例

可参考B站视频《基于密度的聚类 DBSCAN 解释与实例计算_哔哩哔哩_bilibili》，小姐姐讲得非常好哦。

---

上一篇	下一篇
毫米波雷达技术（九）	待发布