基于加权的无线弱覆盖栅格聚类研究

【摘要】

本文研究了一种无线弱覆盖栅格的聚类方法。通过获取栅格的中心经纬度，弱覆盖采样点占比以及弱覆盖出现频次，根据加权的dbscan算法对各栅格中心经纬度聚类得到对应的弱覆盖栅格簇。在聚类过程中对核心点的判断引入频次加权和弱覆盖采样点占比加权筛选，减少了虚假核心点的误导，提高了计算速度，减少了计算量。

【正文】

一、传统密度聚类的思路与局限

传统DBSCAN是基于密度的聚类算法，只要任意两个样本点是密度直达或密度可达的关系，那么该两个样本点归为同一簇类。传统DBSCAN算法划分数据集D为核心点，边界点和噪声点，并按照一定的连接规则组成簇类。定义下面这几个概念：

1、密度直达（directly density-reachable）：若q处于p的ε邻域内，且p为核心点，则称q由p密度直达；

2、密度可达（density-reachable）：若q处于p的ε邻域内，且p，q均为核心点，则称q的邻域点由p密度可达；

3、密度相连（density-connected）：若p，q均为非核心点，且p，q处于同一个簇类中，则称q与p密度相连。

下图给出了上述概念的直观显示（MinPts）：

因此，DBSCAN算法从数据集D中随机选择一个核心点作为“种子”，由该种子出发确定相应的聚类簇，当遍历完所有核心点时，算法结束。针对弱覆盖栅格的聚类方法，除了地理的密度聚类外，还需要考虑栅格的弱覆盖采样点占比，以及弱覆盖出现的时间频率。传统技术方案需要在聚类完成后再进行频次筛选，计算量大。

二、引入维度加权的密度聚类

本文方案与传统方案的不同之处在于，现有方案需要在聚类完成后再进行频次筛选，而本文方案是在聚类过程中对核心点的判断引入频次加权筛选，减少了虚假核心点的误导。

2.1、设置参数：

对于每个栅格，计算其中心经纬度。首先是确定聚类的数据集时间范围。数据集的时间粒度可划分为为天，周，月等。可按工作日\节假日，天气，季节等日期属性分割数据集单独聚类。以弱覆盖采样点占比大于弱覆盖阈值的栅格作为DBSCAN算法的一个输入数据点。其次是确定聚类簇的大小。根据聚类簇大小可设置邻域大小ε和确定聚类簇的最小数据点数量。根据聚类簇大小，和时间范围设定聚类簇的最小数据点数量。最后是确定聚类簇中弱覆盖栅格出现的最小频次。根据数据集时间范围设定，设定聚类簇数据点出现的最小频次。

2.2、加权DBSCAN聚类

传统的DBSCAN算法是基于密度的聚类方法，它通过检查数据点ε-邻域内的点数是否达到某个阈值（MinPts）来决定是否形成簇。在加权DBSCAN中，不仅要考虑邻域内的点数，还要考虑这些点的权重，即弱覆盖采样点占比和出现频次。因此，需要修改DBSCAN算法中的密度计算方式，以纳入权重因素。DBSCAN算法处理后的聚类样本点分为：核心点（core points），边界点（border points）和噪声点（noise），这三类样本点的定义如下：核心点：对本案例数据集D，若栅格p的ε邻域内至少包含MinPts个样本（包括栅格p），且这些样本点的弱覆盖采样点占比大于MinCover，且出现频次大于MinFres，那么样本p称核心点。即：

称p为核心点，其中ε领域的表达式为：

其中:

1、如果邻域形状为矩形，为曼哈顿距离，如果邻域形状为圆形，为欧拉距离。

2、）为数据点q的弱覆盖采样点占比。

3、为栅格p的ε邻域内，在时间粒度上数据点q出现的频次。例如时间粒度为天粒度，聚类周期为30天，栅格p的ε邻域内一共有20天出现数据点，则=20。

边界点：对于非核心点的样本b，若b在任意核心点p的ε领域内，那么样本b称为边界点。即：

称b为非核心点。
噪声点：对于非核心点的样本n，若n不在任意核心点p的ε领域内，那么样本n称为噪声点。即：

称n为噪声点。

2.3、简化距离计算

因为栅格中心的距离是固定的。预先计算并存储栅格中心之间的距离，以便在聚类过程中快速查找，而不需要实时或重复计算。利用字典结构来加速ε邻域的搜索过程。每个栅格标识为字典的一个键，距离满足ε的栅格作为值。在搜索过程中利用字典，直接调用满足ε的栅格，提升的计算速度。

2.4、构建聚类簇

从一个未访问过的核心点开始，找出所有密度可达的点（即通过一个或多个核心点的加权邻域可以到达的点），形成一个聚类簇。重复此过程，直到所有核心点都被访问过。未被归入任何聚类簇的点被视为噪声点。输出聚类簇的栅格作为弱覆盖栅格聚集区域。

四、结论

本文提出基于弱覆盖采样点占比和弱覆盖频次加权的dbscan计算方法，通过在核心点计算中引入弱覆盖采样点占比和弱覆盖频次判断，聚类过程中对核心点的选择同时满足弱覆盖采样点占比和弱覆盖频次的要求，弱覆盖栅格聚类簇更加准确。本文还基于弱覆盖栅格的特点，通过预先计算并存储栅格中心之间的距离，减少了栅格距离的重复计算，提高dbscan聚类的计算速度。

五、参考文献：

[1]马晓明，樊野，孙小娟，刘亮，陈晓锋，基于位置精准性识别的网格应用及5G网络覆盖指导提升的研究，江苏通信，2023年12月15日

[2]王照宇，王森，索小新，无线网精准规建方法论研究，邮电设计技术，2023年10月20日