bic准则（测绘通报 ）

本文内容来源于《测绘通报》2021年第5期，审图号：GS（2021）2567号

基于共享单车时空大数据的细粒度聚类

张强, 白征东, 辛浩浩, 程宇航, 郭锦萍

清华大学土木工程系, 北京 100084

基金项目：国家重点研发计划(2017YFB0504202)

摘要：针对传统上单独采用K-means或DBSCAN等方法对共享单车位置数据聚类时造成的聚类结果与真实的聚类结构不符的问题, 本文提出了一种基于共享单车时空大数据的细粒度聚类方法(FGCM)。该方法通过DBSCAN进行初始聚类, 并在此基础上采用GMM-EM算法进行细部聚类, 以提取细粒度层级的热点区域。试验表明, 该方法可根据密度阈值排除噪声和离群值, 无需指定细部聚类簇数, 簇的形状和大小比较灵活。在对共享单车大数据位置特征进行聚类时, 与传统的单独采用K-means或DBSCAN的方法相比, FGCM具备更高的精细程度, 能够充分展现共享单车的实际聚集特征, 可用于规划共享单车电子围栏等设施, 在不降低通勤效率的基础上规范共享单车的停放问题。

关键词： 共享单车 时空大数据 细粒度聚类 DBSCAN K-means

引文格式：张强, 白征东, 辛浩浩, 等. 基于共享单车时空大数据的细粒度聚类[J]. 测绘通报，2021(5)：15-19, 29. DOI: 10.13474/j.cnki.11-2246.2021.0134.

阅读全文：http://tb.sinomaps.com/article/2021/0494-0911/20210504.htm

全文概述

共享单车是一种新型的基于互联网的自行车租赁业务，其在日常运营中产生了大量含有时间和空间信息的时空大数据[1]。通过数据挖掘方法可以从中提取出共享单车区域热点[2]，用于规划电子围栏、规划停车区域、优化车辆调度等，改善共享单车的车辆堆积、乱停乱放等交通设施管理问题，对优化城市交通设施利用、解决拥堵问题具有重要意义。

聚类分析是一类常用的数据挖掘方法，该方法依据数据间的相似程度对数据集进行划分和标记，可有效应用于时空大数据分析。当前基于时空大数据提取区域热点所采用的聚类分析方法主要包括两类：K-means[3]和DBSCAN[4]。

国内外学者采用上述方法，在基于各类时空大数据提取区域热点上取得了一定进展。文献[5-6] 均采用K-means算法对出租车订单起点位置进行聚类分析，可为出租车提供热点位置推荐。文献[7-8]采用K-means和DBSCAN方法进行聚类，确定了共享单车的聚集热点，提出电子围栏或虚拟站点的规划建议。

文献[5-6]针对出租车数据的聚类分析均是在较大范围内(半径数十到数百米)进行的，其结果精细程度不高。而相比于出租车数据的低密度分布、高定位精度和高采样率[9]，共享单车分布密度更高且定位结果相对较差、位置特征复杂。由于这些特性，单独采用一种聚类分析方法会造成聚类结果与真实的聚类结构不符的问题，具体体现为聚类簇精细度不足、形状不正确、随机性强。文献[7-8]及其他文献对共享单车的聚类分析结果也证实了上述问题的存在，其聚类结果的用途仅限于作需求量分析或规划数百平方米的虚拟站点。

通过合理融合多种聚类算法可以有效降低聚类簇的失真程度[10]。借鉴该思想，以叠合的方式融合聚类算法也可起到类似效果。

本文提出一种细粒度聚类方法(fine-grained clustering method, FGCM)。该方法利用共享单车时空大数据的位置特征，通过DBSCAN进行初始聚类，并在其聚类结果的基础上采用高斯混合模型期望最大化(GMM-EM)算法再度聚类，以达到混合聚类计算的目的，提取细粒度层级的热点区域。

本文介绍FGCM的原理，通过试验测试其性能，并与K-means、DBSCAN方法进行比较，以验证该算法的有效性。

1 FGCM原理

FGCM主要利用DBSCAN和GMM-EM进行聚类融合运算，提高聚类结果的精细程度和真实性，从而提升对于共享单车时空大数据的聚类效果。

1.1 初始聚类

初始聚类采用文献[4]提出的DBSCAN算法。DBSCAN在分析含有噪声的数据集方面十分有效[11]，聚类簇形状灵活，适用于共享单车时空大数据等噪声多、形态复杂的数据集。

对于各样本点xi∈X，记其ε邻域内的点集合为Xi={xi1,xi2, …, xim}，若点个数m≤Minpts，则将xi标记为噪声；否则，对各样本点xij∈Xi，若其无所属簇，则加入xi的所属簇。若样本点xij未被访问过，则进一步搜索样本点xij的ε邻域，记其ε邻域内的点集合为Xij={xij1,xij2, …, xijm′}，若点个数m′≥Minpts，则将Xi更新为Xi∪Xij，并继续搜索；直至所有点都被标记了所属簇或噪声，记聚类结果为C={C1,C2, …, Cp}。

通过DBSCAN，可以将偏离簇过远的点排除在所属簇之外，以达到去噪目的，使热点簇突出，减轻计算量和后续运算中的随机性。

1.2 细部聚类

对于Ci∈C，采用GMM-EM进行细部聚类。其中，高斯混合模型(Gaussian mixture model, GMM)是指多个正态分布的加权线性组合模型，可用于拟合复杂不定类型的分布[12]。期望最大化(expectation maximization, EM)算法是一种极大似然估计算法，用于解决当概率模型含有隐变量时的情形，适用于拟合包括GMM在内的多种概率分布模型[13]。

对于维数为的随机变量X∈RD，有正态分布

(1)

式中，D为随机变量X的维度；μ∈RD为均值(期望)；Σ∈RD×D为协方差；π为圆周率。

对于K个正态分布加权线性组合成的GMM，有

(2)

式中，θ为参数。每个子模型都包含3个参数，记第k组参数为θk=(πk,μk,Σk)，πk为混合系数，且有

(3)

假设现有N个观测到的独立同分布样本x1,x2, …,xN，则理论上可通过最大似然估计的方式得到参数

。该GMM的对数似然函数为

(4)

进一步，采用期望最大化EM算法迭代求解，其迭代过程主要包含两个步骤：

(1) 估计观测数据xi属于子模型k的期望γik

(5)

(2) 产生新的参数θk=(πk,μk,Σk)

(6)

(7)

(8)

迭代收敛后，对每个样本点xi，获取其在GMM中权重最大(即使得γik最大)的子模型k，作为xi的所属簇。

GMM-EM算法为一种软聚类，即采用概率(期望γik)的方式表述观测点隶属于某一子正态分布的程度，这一特性可以帮助判断观测点的离群程度。且GMM-EM算法获取的簇的形状较为灵活，相互之间可以交叉，因此可以处理密集且复杂的聚类。

GMM-EM算法的缺陷为对初始值的变化较敏感，可能收敛到局部最优解。为解决这一问题，本文主要采用以下初始化策略，以尽可能减少初始值的影响：①采用K-means++初始化策略初始化K-means，使初始化聚类中心间的距离尽可能远，以降低初始值敏感性[14]；②采用①中K-means聚类所得结果作为GMM-EM的初始化。

1.3 聚类优化

进行细部聚类时，需采用合理的聚类簇数K，对此本文采用贝叶斯信息量准则(Bayesian information criterion, BIC)[15]作为评估GMM-EM算法聚类结果收敛性的判断标准，以及选择合适的聚类簇数K的依据。

(9)

式中，N为样本量；

为最大似然函数，式(4)为其对数似然形式；k为模型估计中的参数数量。K包括以下3部分。

(1) 协方差：每个子模型均有各自独立的协方差Σ，其参数与观测量x的维度D有关，因此单个子模型的协方差参数数量为D(D+1)/2。

(2) 均值：每个子模型的均值μ的维度为D，因此单个子模型的均值参数数量为D。

(3) GMM子模型数量：聚类簇数K。

因此，在拟合GMM时，参数数量k为

(10)

BIC的优势在于：①考虑了EM算法迭代结束后的最大似然估计值：当增大时BIC减小，拟合效果较好；②引入ln Nk作为惩罚项：在观测量x的维度D给定时，当K增大时，k增大，使得BIC增大，拟合效果较差，且当K趋近于N时，在低维度情形下BIC会趋向全局极大值。

由于BIC随聚类簇数K的增大呈现单调递增或先减再增的趋势，因此其全局最小值对应的聚类簇数Km可作为最优簇数。

为进一步减小随机因素的影响，可对同一子聚类Ci在同一簇数K的条件下进行多次GMM-EM运算，计算BIC的平均值BICm。在构建BICm-K关系后，即可得到使BICm最小的Km。

1.4 算法流程

FGCM算法伪代码见表 1，主要包括以下步骤：

表 1 FGCM算法

Algorithm: FGCM

Input:

X={x1,x2, …, xn}//共n个样本

ε, MinPts //初始聚类参数

KM//细部聚类簇数上限

Output:

L={l1,l2, …, ln}//各样本点对应的簇标签

1

L=DBSCAN (X,ε, MinPts)//步骤1

2

d L=set (L)//簇标签序列

3

for each iin dLdo

4

if i≠－1 then //步骤2

5

Ci={xjwhere lj=i}

6

for k=1:KMdo

7

Calculate BIC of GMM_EM (Ci,k) for times

8

BICk=Mean(BIC)

9

end for

10

Km=argmink(BICk)//步骤3

11