EN中文

Journal of Geo-information Science >

2024 , Vol. 26 >Issue 9: 2038 - 2051

DOI: https://doi.org/10.12082/dqxxkx.2024.240053

A Fuzzy C-Means Clustering Algorithm Based on Reachable Distance

  • CUI Junchao ,
  • ZHANG Qiongbing , * ,
  • LI Xiaolong
Expand
  • School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411100, China
* ZHANG Qiongbing, E-mail:

Received date: 2024-01-23

  Revised date: 2024-07-29

  Online published: 2024-09-10

Supported by

National Natural Science Foundation of China Youth Project(62107013)

Hunan Provincial Education Department Scientific Research Project(22B0511)

Fold

Abstract

Facility location is of great significance for improving residents’ quality of life, and geographic accessibility indicators, such as the road network, are often used as the main decision-making factors. Clustering analysis based on geographic accessibility is an important tool for solving such problems. However, existing clustering algorithms often fail to guarantee the accuracy of clustering results, the accessibility of cluster centers, or the selectivity of cluster centers, making them less effective in solving the facility location problem in real scenarios. This paper proposes a Fuzzy C-Means clustering algorithm based on Reachable Distance (FCM-RD), which modifies the objective function, the membership function, and the cluster center function of the classical FCM. It employs reachable distance as a measure of geographic reachable similarity and iterates the cluster centers during the clustering process. Specifically, to capture the true relationships and connectivity between different elements, FCM-RD takes into account physical and spatial barriers, employs the shortest path distance along the road network as the reachable distance, and aligns geographic coordinates with the road network. It is possible for one position on the road network to correspond to multiple positions in geographic coordinates. Consequently, when multiple candidate positions for cluster centers are obtained, a cluster center correction mechanism is designed to iterate the accessible cluster center with reachable distance during the clustering process. Mathematical analysis and experiments in actual scenarios both show the validity of the cluster center iteration mechanism, showing the selected cluster centers in each iteration of FCM-RD are the unique and minimum value points of the intra-cluster objective function. The rationality of FCM-RD is further verified through experiments, and it is compared with baseline algorithms from three aspects: experimental results, convergence, and performance. The results indicate that, compared to the baseline algorithms, FCM- RD improves performance on both the mean and maximum indicators of the shortest reachable distance, with some indicators even improving by up to 38.9%. In a few experiments, there are slight improvements in the DB index and silhouette coefficient indicators, and 100% of the cluster centers selected by FCM- RD are located on the road network. FCM- RD overcomes the shortcomings of ignoring geographical obstacles and unreachable cluster centers. In conclusion, FCM-RD not only obtains accessible cluster centers without location restrictions but also achieves better clustering results. FCM-RD provides an effective and precise solution for geographical spatial clustering in practical scenarios.

Key words： geographical accessibility; spatial clustering; reachable distance; facility location; road network; fuzzy C-means clustering algorithm; cluster center iteration mechanism

Cite this article

CUI Junchao , ZHANG Qiongbing , LI Xiaolong . A Fuzzy C-Means Clustering Algorithm Based on Reachable Distance[J]. Journal of Geo-information Science, 2024 , 26(9) : 2038 -2051 . DOI: 10.12082/dqxxkx.2024.240053

1 引言

聚类算法[1-2]是数据挖掘、模式识别、机器学习等领域的基础算法，是识别数据集合内部结构与数值分异的主要方法，目前已广泛应用于设施选址研究中，其主要作用是对空间数据进行地理可达性分析。地理可达性是指地理区域内不同点之间的相互关联程度，包括路网距离、交通便捷性、出行成本等属性。利用地理可达相似性[3]聚类对空间元素进行分类是解决设施选址和服务范围覆盖等问题的重要方法。
目前已有很多研究将聚类算法应用于设施选址问题求解[4-5]。聚类算法在设施选址中的主要作用是进行地理可达相似性分析，将相似性高的元素聚为一簇，簇类中心则是在地理可达维度上为该簇内所有元素提供服务的最佳位置点。例如Rajan等[6]在求解印度某区域公共服务中心选址问题时，采用基于欧氏距离的FCM(Fuzzy C-Means，模糊C均值聚类)算法进行聚类，并以簇中心点为初始选址位置。实际应用中，大部分设施选址问题除了考虑地理可达性因素外，还需考虑交通成本、建设代价等其它业务因素。一种采用较多的方法是“二步法”：首先，采用聚类算法进行地理可达性聚类，得到簇划分和各簇中心点；然后，考虑其它业务因素，采用相关方法（智能计算方法居多）调整这些簇中心，从而确定最终位置点[7⇓⇓-10]。在某些只考虑地理可达性因素的选址应用中，簇类中心点即为最终选址位置，例如RAMKRISHNA等[11]在求解高速公路上交通事故的急救中心选址问题时，采用基于欧氏距离的均值漂移聚类算法对业务区域进行聚类，所得簇中心即为急救中心位置。因此，对于设施选址应用，无论是考虑多因素还是只考虑地理可达因素，涉及簇中心迭代的聚类算法都有重要作用。
然而，这些算法大多以欧氏距离进行聚类，可达性测度准确性较低，可能导致聚类元素被划分至实际距离更远的分簇中，聚类结果误差偏大；且并没有考虑山川湖泊等地理障碍，生成的簇中心很可能位于路网之外的不可达区域，只适合在宏观角度[12]下进行较低精准度的地理相似性分析。
实际场景中的山脉、河流等物理障碍会影响聚类元素之间的可达性，考虑这些物理障碍约束会使地理相似性评价更准确。一种可行的方案是以“障碍距离[13]”替代欧氏距离来进行聚类分析。Estivill-Castro等[14]、John等[15]、Zaiane等[16]多位学者也相继提出了类似考虑物理“障碍距离”的聚类算法。然而，这些算法采用的是“避开障碍的欧氏距离”，虽在一定程度上减小了以欧氏距离衡量地理相似性所带来的误差，但仍然无法克服聚类结果不准确、簇中心不可达等缺陷。此外，这类算法需要在预处理中构建障碍物可见图，而在真实广域场景[17-18]下对所有障碍物进行标记显然比较困难。
基于可达距离进行空间元素地理相似性聚类可有效的避免上述缺陷，众多研究人员采用可达距离评估空间元素的地理相似性[19⇓⇓-22]。当前基于可达距离的聚类先产生聚类元素间的可达距离矩阵，再采用适当的聚类算法离线聚类。这类方法在较大规模应用场景中面临挑战：一方面，可达距离矩阵为N*N，其中N是聚类元素数量，很显然当N规模较大时，生成和操作可达距离矩阵需要较大时间复杂度和空间复杂度；另一方面，目前基于可达距离的聚类算法不能保证簇类中心的可达性，所采用的聚类算法或不涉及簇中心迭代，或以聚类元素为簇中心。而簇类中心通常具有重要的物理意义，尤其在设施选址问题中，簇中心代表所选定的设施位置。综上所述，现有的面向地理可达性的聚类算法并不能有效解决真实场景下的设施选址问题，特别是对于聚类元素间可达距离和欧氏距离相差较远的场景。因此，探索基于可达距离聚类且能生成可达簇中心的聚类算法相当重要，本文拟设计一种基于可达距离且确保簇中心可达的聚类算法，为广域场景下的设施选址、服务范围划分等应用提供地理可达性分析。
作为应用最为广泛的模糊聚类算法，FCM算法简洁直观，误差小，收敛快，不易陷入局部最优解，且该算法聚类过程中需要进行簇类中心迭代，目前，FCM算法已广泛应用于设施选址研究中[23⇓-25]。基于此，本文改进基于欧氏距离的FCM算法，提出一种基于可达距离聚类且生成可达簇中心的模糊C均值聚类算法（Fuzzy C-Means based on Reachable Distance, FCM-RD），并可在聚类迭代过程中结合ArcGIS动态地呈现聚类过程。据作者所知，该算法是首个以实际可达距离作为地理相似性测度并且在聚类过程实现不受约束的可达簇中心迭代的聚类算法，对真实广域场景下的设施选址研究具有较大意义。同时，本文通过理论分析和基于真实场景的实验证明FCM-RD算法簇中心迭代机制的有效性。基于实际场景的对比实验结果表明，与基准算法相比，FCM-RD算法在可达距离均值、最大值指标上均有性能提升，部分性能提升甚至达到38.9%；少部分实验在DB指数和轮廓系数指标上也略有提升，且克服了现有聚类算法在真实场景中地理可达性测度不准确、聚类结果误差偏大、簇中心不可达等缺陷。

2 研究方法

2.1 问题场景与建模

面向地理可达性的聚类通常根据聚类元素间的可达距离将其划分为若干簇，使得相同簇内元素间的可达性优于非同簇元素。设施选址问题是其中的典型应用。图1展示了基于实际场景的设施选址示例，红色圆点代表设施，需对区域内所有聚类元素提供服务。目前，对空间元素进行地理相似性聚类是确定设施位置及覆盖范围的主要方法。
图1 标准FCM聚类算法在应用场景中的聚类结果

Fig. 1 Clustering results of standard FCM clustering algorithm in application scenarios

令C={c1, c2, ⋯, ci, ci+1, ⋯, cd}表示簇中心(即设施位置)集合，X={x1, x2, ⋯, xj, xj+1, ⋯, xn}表示聚类元素集合，其中ci、xj分别表示第i个簇中心和第j个聚类元素，n∈N*表示集合中聚类元素的个数，d∈N*且d≤n表示分簇的个数(即设施的个数)。FCM聚类算法的聚类目标函数如式(1)所示。
J = m i n ∑ i = 1 d ∑ j = 1 n u i j m x j - c i 2 ，                           s . t .   ∑ i = 1 d u i j = 1 ,       j = 1,2 , ⋯ , n  
式中： uij为第j个聚类元素隶属于第i个簇的隶属度，表示聚类元素xj被划分至第i个簇的可能性； x j   -   c i为xj与ci间的欧氏距离； m为隶属度轻缓因子，一般m > 1。该目标函数对聚类元素与簇中心之间的成对差异(即聚类元素与簇中心之间受隶属度影响的欧氏距离)求和，通过最小化该函数得到最紧密的聚类结果。在式(1)中引入拉格朗日乘子λj可得新的目标函数，如式(2)所示。
J = m i n ∑ i = 1 d ∑ j = 1 n u i j m x j - c i 2 + λ 1 ∑ i = 1 d u i 1 - 1 +                 λ 2 ∑ i = 1 d u i 2 - 1 + ⋯ + λ n ∑ i = 1 d u i n - 1
分别对uij、ci和λj求偏导，可得隶属度uij及各簇中心点位置ci，分别如式(3)、式(4)所示。
u i j = 1 ∑ k = 1 d x j - c i x j - c k 2 m - 1
c i = ∑ j = 1 n u i j m ∑ j = 1 n u i j m x j
显然uij和ci相互影响，多次迭代后簇类中心和各聚类元素隶属度达到平衡，得到聚类结果。但标准FCM聚类算法在求解面向地理可达性的设施选址等问题时效果并不理想。图1展示了标准FCM算法对示例场景的聚类结果。由图可见，红色圆圈处的聚类元素实际上距蓝色分簇簇中心更近，但由于标准FCM算法以欧氏距离作为相似性度量，因此导致该聚类元素被划分至实际距离更远的黄色分簇中；而黄色方框处的簇中心并未位于路网上，出现了明显的簇类中心不可达现象。事实上，这些缺陷也是在迭代过程中生成不受约束簇中心的聚类方法目前不能应用于地理可达性聚类的主要原因。因此，探索基于可达距离聚类且能生成可达簇中心的聚类算法有重要意义。

2.2 基于可达距离的模糊C均值聚类算法

FCM-RD算法将基于路网的可达距离作为地理相似性度量指标，改造了经典FCM算法的目标函数、隶属度函数和簇中心计算函数；并根据预先指定的簇划分数初始化可达簇中心集合，将聚类元素投影到路网上，设计了满足地理可达性的簇中心迭代机制，实现了基于可达距离的聚类，并在迭代过程中生成可达簇中心。本节将对FCM-RD聚类算法进行详细阐述，FCM-RD算法的整体框架图如图2所示。
图2 FCM-RD算法整体框架

Fig. 2 Overall framework diagram of the FCM-RD

2.2.1 FCM-RD算法

以图3为例，该图是一个基于可达距离聚类的抽象场景图。其中，黑色线段表示路网分布，蓝色圆点表示聚类元素，黄色五边形为路线相交的路网分叉点。
图3 FCM-RD应用场景

Fig. 3 FCM-RD application scenarios

算法首先将聚类元素的地理坐标投影到路网，每个聚类元素得到路网坐标。具体而言，在算法开始时，随机选择路网上一点(为方便计算，一般选取路况简单的路网点，如非交叉点)作为原点O，并选择原点O的任意一侧为正方向。对于不在路网上的元素，使用ArcGIS工具计算距该元素直线距离最近的路网上的点。这个点被视为元素在道路网络上的投影，其路网坐标被用来表示该元素的路网坐标。至此，仅需考虑如何计算路网上各点的路网坐标即可。对于被投影到路网上的聚类元素xj，以其投影点与原点O之间沿路网的最短距离和方向表示其路网坐标。令P(xj, O)表示聚类元素xj的投影点和原点O之间沿路网的最短路径，则路网坐标L(xj)为：
L ( x j ) = | P ( x j ,   O ) | ,               P ( x j ,   O ) 位 于 正 向 - | P ( x j ,   O ) | ,         其 他
图4展示了将图3所示场景中的聚类元素投影到路网，并生成相应的路网坐标。红色五角星为随机选择的原点O，红色圆点表示此时刻的其中一个簇中心ci，蓝色圆点表示各聚类元素在路网上的投影点，括号中的数值分别为该聚类元素的路网坐标和隶属于该簇的隶属度。路网被原点O分割为左右两侧，选择原点O的右侧为正方向。显然，簇中心ci、聚类元素x3、x4、x5、x6、x7和路网分叉点f3、f4、f5位于原点O的正方向，聚类元素x1、x2和路网分叉点f1、f2位于原点O的负方向。以聚类元素x7为例，其路网坐标L(x7)=P(x7, O)=150。值得注意的是，如果场景存在环形路，原点位置不一样，会导致各元素到原点的最短距离改变幅度不一致，导致聚类结果可能不同。因此FCM-RD算法对原点位置敏感，不同的原点所得到的聚类结果可能不同，实际应用应取多次运行结果的最佳值。为方便描述，表1对本文中使用的符号、函数进行汇总说明。
图4 FCM-RD应用示例

Fig. 4 Example of FCM-RD application

表1 符号说明

Tab. 1 Symbol description

符号 说明
X = { x1, x2, ⋯, xj, xj+1, ⋯, xn }，n∈N* 聚类元素集合，n表示聚类元素个数
C = {c1, c2, ⋯, ci, ci+1, ⋯, cd}，d∈N*且d≤n 簇中心集合，d表示簇中心个数
F = {f1, f2, ⋯, fk, fk+1, ⋯, fv }，v ∈ N* 路网分叉点集合，v表示路网分叉点个数
R(fk) = { r1, r2, ⋯, rq, rq+1, ⋯, rs }，s∈N* 分叉点搜索方向上的分支集合，s表示分支条数
Y = {y | y ∈ X∪C∪F} 聚类场景元素集合
L(y) 元素 y（包括聚类元素、分叉点、簇中心等）的路网坐标，以其与原点O之间的沿路网的最短距离和方向表示其路网坐标
Point(L(y)) 路网坐标为 L(y) 的点集
FPoint(fk) 位于分叉点 fk 搜索方向各分支上的聚类元素集合
RPoint(fk, rq) = {xj | rq∈R(fk), xj∈FPoint(fk)} 位于分叉点 fk 搜索方向 rq 分支上的聚类元素集合
TopFork(y1, y2) 元素 y1 到 y2 路径上的第一个分叉点
f ( c i , x j ) 簇中心 ci 所在分支与聚类元素 xj 所在分支的公共分叉点
uij 聚类元素 xj 隶属于簇中心 ci 的隶属度
d(xj, ci) 以聚类元素 xj 与簇中心点 ci 之间的路网坐标差值计算的有向可达距离
P(y1, y2) 元素y1与y2之间沿路网的最短路径
cit 第 t 代第 i 个簇中心
cit' 第 t 代第 i 个簇中心迭代修正过程中的簇中心
相对于式(1)， FCM-RD聚类算法的目标函数将由式(1)转换为式(6)：
J = m i n ∑ i = 1 d ∑ j = 1 n u i j m d x j , c i 2 ,                   s . t .   ∑ i = 1 d u i j = 1 ,       j = 1,2 , … , n
式中：d(xj, ci)为聚类元素xj与簇中心ci之间的有向可达距离，同理隶属度uij计算公式如式(7)所示。
u i j = 1 ∑ k = 1 d d x j , c i d x j , c k ( 2 m - 1 )
对应的簇中心ci位置为：
c i = ∑ j = 1 n u i j m ∑ j = 1 n u i j m d x j , O
由图3可见，聚类元素xj与路网原点O间的有向可达距离即为两者路网坐标的差值，即：
d x j , O = L x j - L O = L x j
簇类中心的计算由式(8)变为式(10)。
L c i = ∑ j = 1 n u i j m ∑ j = 1 n u i j m × L x j ,   i ≤ d ,     j ≤ n
对于簇中心的具体位置，有以下推论。
推论1. 基于可达距离聚类的簇中心点一定在路线上。
证明见附录A。
因此，对于簇中心ci，其具体位置为式（10）计算所得的路网坐标为L(ci)的位置点，若该点到原点O的最短路径上没有分叉点，则该路网坐标点唯一，否则可能存在多个点有相同路网坐标的情况。如图3所示，原点负方向的第一个分叉点f2坐标为-40，路网坐标在[-40, 0]区间的位置点具有唯一性。而聚类元素x2 (-60, 0.6)表示该点位于原点负方向可达距离60 m处，路网坐标-60表示的点并不唯一，可能在其它分叉路线上存在。因此当式（10）所得L(ci)可能存在多个位置点时，需要对簇中心位置修正。

2.2.2 簇中心迭代机制

路网坐标L(ci)存在多个对应位置点时，采取簇中心迭代机制来确定合理的簇中心位置。对于t代第i个簇中心cit，其路网坐标L(cit)由式（10）可得，若L(cit)表示的点不唯一，则使用cit'表示迭代修正过程中的簇中心，Point(L(cit'))表示路网坐标L(cit')对应的所有位置点的集合，同时也是候选簇中心。
如图4中所示场景，计算得到的簇中心路网坐标L(cit)为72.76，方向为正向，由于存在路网分叉点，有Point (72.76) = {cit'1, cit'2, cit'3}，如图4中橙色圆点所示，需沿着正向对各簇中心进行修正。
令ftop = TopFork (O, cit')，以该点为基点，依次对每一条分支r (r∈R(ftop))上的候选簇中心位置进行修正。修正过程中始终以当前搜索分支rq为新的搜索正向，其余分支rp (rp∈R(ftop)且p ≠ q)为负方向，但由于该分支上的临时候选簇中心位置是在所有分支上的聚类元素均处于正向时计算所得，因此需将其它分支上的聚类元素到分叉点的距离所造成的影响修正为负影响。对于分叉点ftop处分支rq上的临时候选簇中心，其修正后的路网坐标L(cit'q)为：
L c i t ' q = L c i t ' q -         2 × ∑ r p ∈ R ( f t o p ) , p ≠ q ∑     x j ∈ R P o i n t ( f t o p , r p ) u i j m × ( L ( x j ) - L ( f t o p ) ) ∑ j = 1 n u i j m
如图4中有TopFork (O, cit') = f3，R(f3) = {r1, r2, r3}。依次对各分支上的簇中心进行修正，由式(11)计算可得：L(cit'1) = -45.66、L(cit'2) = 47.37、L(cit'3) = -68.16。
若簇中心被修正到ftop搜索方向的反方向，则表明该分支上的候选簇中心不合理，此时应继续搜索下一分支，如图4中cit'1、cit'3的修正簇中心；若所有分支上的候选簇中心均不合理，则选择ftop作为下一代簇中心cit+1；若修正后的簇中心仍位于ftop的搜索方向上且有|L(cit'q)| ≥ |L(ftop)|，则判断该路网坐标表示的点是否唯一，若唯一则该点即为下一代簇中心cit+1，如图4中cit'2的修正簇中心即为该簇的下一代簇中心；若不唯一，则更新ftop=TopFork(ftop, cit'q)，重复上述步骤直到得到唯一的点作为下一代簇中心cit+1。

2.2.3 簇中心有效性分析

上述总体算法表明FCM-RD聚类算法的关键是设计了适配地理可达性的簇中心迭代机制，实现在聚类过程中迭代不受约束的可达簇中心。合理的聚类算法簇中心应该满足“各簇簇中心有且唯一”，本节将证明FCM-RD算法所选取的各簇簇中心有且唯一。
证明见附录B。

3 场景实验

本节将通过实验对比FCM-RD算法与各基准算法在面向地理可达性聚类应用中的算法性能。首先，对实验场景数据、评价指标及实验设置进行简要说明。其次，从簇中心迭代机制有效性、聚类结果合理性、簇中心位置统计结果、算法收敛性和算法性能等方面说明FCM-RD算法的有效性，验证加入可达距离约束后FCM-RD算法的性能改进。

3.1 实验设计

3.1.1 场景数据

实验场景为湖南省某县一实际业务场景，其中遥感影像来源于开源下载；路网数据来源于商业购买，包括农村公路及普通国、省道数据；预处理阶段已删除重复以及无意义的线段，补齐缺失不连通的线段；聚类元素原始数据为文本地址信息，预处理过程中通过地址匹配加地理编码技术转换为空间坐标。最后，利用ArcGIS工具将路网数据、聚类元素位置数据与研究区边界等相关地理数据的坐标系统一投影为WGS_1984_UTM_Zone_48N投影坐标。

3.1.2 评价指标

实验选用5种度量指标来评估聚类性能：所有聚类元素距其所属簇中心最短可达距离的均值、最大值、最小值(以下分别简称为均值、最大值、最小值)[26]、Davies-Bouldin Index(DB指数)[27]、Silhouette Coefficient(轮廓系数)[28]。其中DB指数越小，意味着簇内距离越小而簇间距离越大，即同簇之间更紧密，异簇之间更分散，聚类效果更好。轮廓系数旨在对比某聚类元素与其所属簇的相似程度和与其他簇的相似程度，其取值范围是[-1,1]，轮廓系数值越大，即同簇聚类元素距离越相近、异簇聚类元素距离越远，聚类效果越好。实际地理环境中地理相似性是以可达距离为准，因此指标计算中的距离皆采用可达距离。

3.1.3 实验设置

据作者所知， FCM-RD算法是首个基于可达距离聚类并实现不受约束的可达簇中心迭代的聚类算法。对于那些同样可选取任意位置作为簇中心，并已广泛应用于设施选址研究的聚类算法，例如FCM和均值漂移（Mean Shift）算法，目前尚未有以可达距离作为相似性度量的版本。FCM算法能较准确反应实际场景中地理位置及划分的不确定性，均值漂移算法适用在复杂地理数据分析。因此本研究首先选择基于欧氏距离的FCM[23⇓-25]、均值漂移算法[11,29,30]作为基准算法，以对比加入可达距离约束后，FCM-RD算法在生成可达簇中心上的改进。目前以可达距离进行地理相似性分析的聚类算法中，层次聚类算法[31]应用广泛，因此也将其作为本文的基准算法之一，以对比其与生成可达簇中心的FCM-RD算法的性能差异。实验将小规模和中等规模下的实验场景分为八组，分别为G1：n=16，d=4；G2：n=50，d=4；G3：n=100，d=4；G4：n=100，d=2；G5：n=100，d=3；G6：n=100，d=5；G7：n=100，d=6；G8：n=200，d=4；其中n表示聚类元素个数，d表示簇中心数。欧氏FCM和FCM-RD算法中的参数m设置为2，为经典经验系数[32]；均值漂移算法中的参数bandwidth根据各组实验场景中的聚类元素数和簇划分数设置不同的值，同样为经验值。所有实验均在Dell 3690电脑上运行，环境为Windows 10 X64位操作系统，CPU CORE i5-11400 CPU，内存为16 GB。所有算法均使用Python 2.7实现并调用ArcGIS 10.2的API接口进行空间几何分析。

3.2 实验结果分析

3.2.1 簇中心迭代机制有效性验证

目前基于可达距离的聚类算法或不产生簇中心，或以聚类元素为簇中心，FCM-RD的核心创新是实现基于可达距离的不受约束簇中心迭代机制。本节主要从3个方面验证FCM-RD算法分簇的合理性及簇中心迭代机制的有效性。首先验证FCM-RD算法在每次迭代中所选簇中心为当前簇类目标函数最小值点；其次，给出FCM-RD聚类算法结果图，直观地从簇中心位置、分簇方案等方面判断FCM-RD算法以可达距离聚类的分簇合理性；最后，统计并对比FCM-RD聚类算法与涉及簇中心选取的欧氏FCM、均值漂移聚类算法所获得的簇中心的可达性。
为验证FCM-RD算法在每次迭代中所选簇中心为当前簇类目标函数最小值点，随机在某轮迭代后簇中心左右两边均匀采点并计算采样点的簇类目标值。图5展示了本文八组聚类场景中随机选取的某一轮迭代过程的采点取值结果。图5(a)展示了在G1—G3实验场景下的验证结果；图5(b)展示了在G4—G8实验场景下的验证结果；图中横坐标表示簇中心，C表示FCM-RD算法的簇中心，L1~L3和R1~R3表示簇中心左右的描点；纵坐标表示簇内目标函数值。图示结果表明，相比簇类其他点， FCM-RD算法所选簇中心的目标函数为最小值。
图5 FCM-RD簇中心有效性验证结果

Fig. 5 Cluster center effectiveness verification results of FCM-RD

图6给出了FCM-RD算法在各组实验中的可视化聚类结果。其中，红色圆点表示簇中心，相同颜色的正方形点表示同一簇中的样本点。由图可知，FCM-RD算法将聚类元素按照路网距离将其划分到最近簇中心，且算法所选到的簇中心始终位于路网上，克服了现有聚类算法在实际场景中聚类结果不准确、忽略地理障碍、簇中心不可达或不涉及簇中心选取等缺陷，在面向地理可达性的聚类问题中取得了较好的聚类结果。
图6 FCM-RD部分聚类结果

Fig. 6 Partial clustering results of FCM-RD

本文还分别对八组实验中的簇中心位置进行了统计，如表2所示，FCM-RD所选到的簇中心100%位于路网上，而欧氏FCM、均值漂移算法所选到的簇中心均位于路网之外的空地上或不可达区域，且各组实验中仅有至多50%簇中心位于路网周围。由此可见，相比对比算法，FCM-RD算法能确保簇中心的可达性。
表2 簇中心位置结果

Tab. 2 Cluster center location results

实验 簇中心
总数/个		 位于路网上的簇中心数/个 位于路网上的簇中心数占比/% 路网周围簇中心数/个 路网周围簇中心数占比/%
FCM-RD 欧氏FCM Mean Shift FCM-RD 欧氏FCM Mean Shift FCM-RD 欧氏FCM Mean Shift FCM-RD 欧氏FCM Mean Shift
G1 120 120 0 0 100 0 0 0 0 0 0 0 0.0
G2 120 120 0 0 100 0 0 0 0 30 0 0 25.0
G3 120 120 0 0 100 0 0 0 30 30 0 25 25.0
G4 60 60 0 0 100 0 0 0 24 0 0 40 0.0
G5 90 90 0 0 100 0 0 0 11 0 0 12 0.0
G6 150 150 0 0 100 0 0 0 12 60 0 8 40.0
G7 180 180 0 0 100 0 0 0 31 30 0 17 16.7
G8 120 120 0 0 100 0 0 0 30 60 0 25 50.0

注：位于路网周围是指在1：60 000 m的比例尺下，簇中心与路网接近重合的场景；加粗数据表示对比项中的较优结果。

3.2.2 FCM-RD与FCM的收敛性对比

本节将展示FCM-RD聚类算法和欧氏FCM聚类算法的收敛曲线，说明改进的FCM-RD算法并不影响FCM本身的收敛性。图7展示了两种算法在实验中的平均每代目标函数值，横轴表示迭代次数，纵轴表示目标函数值。由图可见，FCM-RD聚类算法的收敛速度与欧氏FCM聚类算法相当。值得注意的是，各组实验中FCM-RD算法的目标函数值均远远大于欧氏FCM算法的目标函数值，这是由于FCM-RD算法的目标函数值采用基于可达性的路网距离进行计算，而欧氏FCM算法的目标函数值采用欧氏距离计算，因此导致二者目标函数值相差较大，并不代表FCM-RD算法相较于欧氏FCM算法聚类效果较差。
图7 算法收敛速度对比

Fig. 7 Algorithm convergence speed comparison

3.3 算法性能分析

表3分析了4种算法的聚类结果。由该表可知，对于指标“最小值”，欧氏FCM算法在G1、G2、G6、G7和G8场景取得最好值，均值漂移算法在G3、G4和G5场景取得最好值，而FCM-RD算法在所有场景中均取得最差值；对于指标“DB指数”，FCM-RD算法在G1、G2和G7上取得最好值，欧氏FCM算法在G3、G4、G5、G6和G8场景取得最好值，而均值漂移算法在所有场景中均取得最差值；对于指标“轮廓系数”，FCM-RD算法在G3、G4和G6场景取得最好值，均值漂移算法在G1、G2、G3、G5、G6、G7和G8场景取得最好值，层次聚类算法在G5和G8场景取得最好值，而欧氏FCM算法在所有场景中均取得最差值。需注意的是，层次聚类算法不涉及簇中心选取，而欧氏FCM、均值漂移聚类算法的簇中心不受路网限制，可以坐落在区域内的任意位置，甚至是不可达区域，这就使得欧氏聚类算法簇内连接更紧密，而簇间连接相对分散，从而导致DB指数、轮廓系数在大部分场景中表现更优。此外，欧氏聚类算法的簇中心落在样本点附近的非路网区域上，通过映射即可导致该簇中心距样本点的最小距离远小于FCM-RD算法的簇中心距样本点的最小距离。但这并不意味着欧氏聚类算法的性能更优，因为欧氏聚类算法选出的簇中心极有可能是不可达的。如图1所示，该图为G6实验场景下采用欧氏FCM聚类算法得到的聚类结果图，图中黄色方框框出的簇中心均位于山地等不可达区域，而本章第2节已从多角度验证FCM-RD算法所选簇中心均可达，对求解地理场景下的设施选址问题有重要意义。
表3 实验结果性能指标分析

Tab. 3 Performance analysis of experimental results

实验 算法 均值/m 最大值/m 最小值/m DB指数 轮廓系数
G1 FCM-RD 974.67 2 230.55 473.48 0.44 0.76
欧氏FCM 1 107.67 3 363.04 116.71 0.47 0.76
Mean Shift 1 159.41 3 317.53 355.77 0.70 0.82
层次聚类 未生成簇中心 0.76
G2 FCM-RD 1 805.31 3 849.25 289.43 0.66 0.70
欧氏FCM 2 123.84 6 295.07 45.94 0.87 0.66
Mean Shift 2 128.23 5 563.67 57.74 1.11 0.73
层次聚类 未生成簇中心 0.70
G3 FCM-RD 3 220.10 7 273.50 131.72 1.60 0.59
欧氏FCM 3 327.96 8 955.90 152.05 0.70 0.58
Mean Shift 3 490.11 9 794.47 50.97 1.42 0.59
层次聚类 未生成簇中心 0.58
G4 FCM-RD 4 892.31 9 808.73 534.47 2.32 0.39
欧氏FCM 5 070.98 11 102.91 93.41 1.24 0.37
Mean Shift 7 605.33 15 304.62 64.80 3.29 0.23
层次聚类 未生成簇中心 0.37
G5 FCM-RD 3 984.76 9 808.73 92.30 1.12 0.52
欧氏FCM 4 112.86 10 169.18 175.67 0.86 0.49
Mean Shift 4 174.03 9 821.42 83.40 0.93 0.53
层次聚类 未生成簇中心 0.53
G6 FCM-RD 2 744.64 6 319.25 269.05 1.31 0.64
欧氏FCM 2 883.95 9 798.69 35.25 0.83 0.62
Mean Shift 2 904.36 6 987.29 355.14 1.49 0.64
层次聚类 未生成簇中心 0.63
G7 FCM-RD 974.67 2 230.55 473.48 0.44 0.76
欧氏FCM 1 107.67 3 363.04 116.71 0.47 0.76
Mean Shift 1 159.41 3 317.53 355.77 0.70 0.82
层次聚类 未生成簇中心 0.76
G8 FCM-RD 2 472.79 5 453.20 365.17 1.47 0.67
欧氏FCM 2 539.43 7 161.58 24.80 0.93 0.67
Mean Shift 2 536.71 6 353.28 95.46 1.55 0.68
层次聚类 未生成簇中心 0.68

注：加粗数据表示对比项中的较优结果。

此外，在“均值”、“最大值”这2项指标上，FCM-RD聚类算法在各组实验中均优于欧氏FCM、均值漂移聚类算法：相比于欧氏FCM聚类算法，FCM-RD聚类算法在G1—G8实验场景下分别取得12%、15%、3.2%、3.5%、3.1%、4.8%、2.6%、7.7%的均值减小和33.7%、38.9%、18.8%、11.7%、3.5%、35.5%、23.9%、30%的最大值减小；相比于均值漂移聚类算法，FCM-RD聚类算法在G1—G8实验场景下分别取得16%、15.2%、7.7%、35.7%、4.5%、5.5%、2.5%、10.5%的均值减小和32.8%、30.8%、25.7%、35.9%、0.13%、9.6%、14.2%、31.4%的最大值减小。综上所述，基于可达距离的FCM-RD聚类算法性能优于对比算法。

4 结论与讨论

4.1 结论

鉴于现有的面向地理可达性的聚类算法存在忽略地理障碍、簇中心受限等缺陷，本文提出了一种基于可达距离的模糊C均值聚类算法(Fuzzy C-Means based on Reachable Distance, FCM-RD)。算法的创新包括： ① 改造基于欧氏距离的FCM算法的目标函数、隶属度函数和簇中心函数，将聚类元素间沿路网的最短路径距离作为可达距离，以可达距离衡量数据元素间的地理可达相似性，克服传统聚类算法在处理地理空间数据时的局限性，提升聚类结果精度； ② 将聚类元素的二维地理坐标映射为平面路网坐标，以实际可达距离衡量元素地理相似性，以路网坐标计算簇中心位置，便利簇中心计算且确保簇中心可达； ③ 设计基于可达距离的簇中心迭代机制，确保簇中心唯一且为簇类目标函数最小值点，并对所选取的簇中心的有效性进行了数学分析和实验验证，结果表明，FCM-RD算法所选到的各簇簇中心有且唯一，且为当前簇类目标函数最小值点。与基准算法的对比实验也表明，FCM-RD算法在可达距离均值、最大值指标上均有性能提升，部分性能提升甚至达到38.9%；少部分实验在DB指数和轮廓系数指标上也略有提升，且克服了现有聚类算法在真实场景中地理可达性测度不准确、聚类结果误差偏大、簇中心不可达等缺陷，为实际场景下的地理空间聚类方案提供有效且精准的解决方案。

4.2 讨论

据作者所知，FCM-RD算法是首个以可达距离聚类并在聚类过程实现不受约束的可达簇中心的聚类算法，为设施选址、服务范围划分等问题提供了有效求解工具。相比于现有的应用“二步法”求解考虑多业务因素的设施选址问题的相关研究，FCM-RD算法可以确保初始设施位置可达且为真实地理可达性下的最优选择；而相比于只考虑地理可达性因素的选址研究，如消防站、急救服务中心等应急设施选址，FCM-RD算法可实现精确的地理可达性分析，准确计算设施的服务覆盖范围和响应距离，尤其是保证选址点的可达性，克服目前聚类算法需调整选址位置的不足。
但当路网数据庞大且复杂时，FCM-RD算法的聚类精度较低，后续研究需验证FCM-RD算法在不同数据规模下的一致性和稳定性，以确保其在各种应用场景中的适用性。此外，FCM-RD算法在迭代过程中需频繁读取GIS系统中的数据，导致I/O时间过长，这类问题可从软件工程角度进行优化，如通过多线程、将所需地理数据常驻内存等方式提高效率。后续研究将关注上述优化方向，分析并较为准确的刻画算法对原点位置敏感的关联关系，在实际应用中验证优化后的算法性能。最后，还拟将其它涉及簇中心迭代的经典聚类算法适配面向地理可达性的聚类研究，如 K-Means算法和均值漂移算法。探究所提簇中心迭代机制在这些算法中的适配操作，以及改进后的算法在不同应用场景中的性能表现，进一步提升涉及簇中心迭代的聚类算法在地理可达性分析应用的普适性和应用价值。

附录A

推论1及其证明
推论1. 基于可达距离聚类的簇中心点一定在路线上。
证明： 假设该簇中心与最近的道路的直线路径为lc，那么，对于簇中心c覆盖的任一聚类元素x来说，令其与路径lc间的路网段为ei (ei∈E，E为路网集合)。
在簇中心c的覆盖范围内，令其覆盖的聚类元素的个数为n，各聚类元素与簇中心间的路网段为{e1, e2,⋯, en}⊂ E。若簇中心位于路网上，则各聚类元素到簇中心的可达距离之和D为：
D = ∑ i = 1 n e i
若簇中心不位于路网上，则计算各聚类元素与簇中心间的可达距离时都要重复一段lc路径，即各聚类元素到簇中心的可达距离之和D'为：
D ' = ∑ i = 1 n e i + n × l c
显然，D' > D，即若簇中心不位于路网上，则会存在冗余路径，此中心点不是最佳簇中心点。
因此，簇类中心点一定在路线上。
证毕。

附录B

FCM-RD所选取的各簇簇中心有且唯一
证明： 由第2章算法整体描述可知，迭代簇中心的最终位置由2种情形产生： ① 直接计算产生，② 簇中心迭代产生。
对于情形 ① ，簇中心位置由式(10)直接计算并映射为路网上唯一点，很显然该簇中心唯一。
对于情形② ，当多个分支存在候选中心点时，簇中心位置至多仅位于其中一个路网分支，证明如下：
以图4为例，假设修正后簇中心位置可位于r1、r2、r3分支中的多个分支上，某分支rq上的聚类元素到其分叉点fk的可达距离与隶属度乘积之和 s r q为：
s r q = ∑ x j ∈ R P o i n t ( f k , r q ) u i j m × L x j - L f k ∑ j = 1 n u i j m ,     i ≤ d
若假设成立，则有：
s r 1 > 2 × ( s r 2 + s r 3 )
s r 2 > 2 × ( s r 1 + s r 3 )
显然式（15）和式（16）相互矛盾，故多个分支存在候选中心点时，簇中心位置至多仅位于其中一个路网分支。
因此FCM-RD聚类算法各簇所选取的各簇中心有且唯一得证。
证毕。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
王鹏洲, 赵志远, 姚伟, 等. 基于地理流空间的巡游车与网约车人群出行模式研究[J]. 地球信息科学学报, 2023, 25(4):726-740.

DOI

[Wang P Z, Zhao Z Y, Yao W, et al. Human travel patterns by E-hailing cars and traditional taxis based on geographic flow space[J]. Journal of Geo-information Science, 2023, 25(4):726-740.] DOI:10.12082/dqxxkx.2023.210769

[2]
王浩成, 向隆刚, 关雪峰, 等. 基于出租车上下客数据流与分布式多阶段网格聚类的城市热点区域实时探测方法[J]. 地球信息科学学报, 2023, 25(7):1514-1530..

DOI

[Wang H C, Xiang L G, Guan X F, et al. Urban hotspot detection from the data stream of Taxi pick-up and drop-off based on distributed multistage grid clustering[J]. Journal of Geo-information Science, 2023, 25(7):1514-1530.] DOI:10.12082/dqxxkx.2023.220753

[3]
张亚, 刘纪平, 周亮, 等. 基于DBSCAN算法的北京市顺丰快递服务设施集群识别与空间特征分析[J]. 地球信息科学学报, 2020, 22(8):1630-1641.

DOI

[Zhang Y, Liu J P, Zhou L, et al. Cluster identification and spatial characteristics analysis of Shunfeng express service facilities based on the DBSCAN algorithm in Beijing[J]. Journal of Geo-information Science, 2020, 22(8):1630-1641.] DOI:10.12082/dqxxkx.2020.190380

[4]
Soufyane M, Chakir L, Jaouad B. New approach to solve uncapacitated facility location problem using continuous hopfield network and modified K-means clustering[C]. 2023 9th International Conference on Optimization and Applications (ICOA). IEEE, 2023:1-9. DOI:10.1109/ICOA58279.2023.10308818

[5]
Pooja, Kumar R, Viriyasitavat W, et al. Analysis of clustering algorithms for facility location allocation problems[M]//Lecture Notes in Networks and Systems. Singapore: Springer Nature Singapore, 2023:597-605. DOI:10.1007/978-981-19-9228-5_51

[6]
Gupta R, Muttoo S K, Pal S K. Fuzzy c-means clustering and particle swarm optimization based scheme for common service center location allocation[J]. Applied Intelligence, 2017, 47(3):624-643. DOI:10.1007/s10489-017-0917-0

[7]
Bunwit P, Tharmmaphornphilas W. Strategic cross-dock allocation for traffic safety products across thailand[C]. 2023 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2023:480-484. DOI:10.1109/IEEM58616.2023.10406517

[8]
Cai C L, Luo Y, Cui Y H, et al. Solving multiple distribution center location allocation problem using K-means algorithm and center of gravity method take Jinjiang district of Chengdu as an example[J]. IOP Conference Series: Earth and Environmental Science, 2020, 587(1):012120. DOI:10.1088/1755-1315/587/1/012120

[9]
Wu J, Liu X, Li Y Y, et al. A two-stage model with an improved clustering algorithm for a distribution center location problem under uncertainty[J]. Mathematics, 2022, 10(14):2519. DOI:10.3390/math10142519

[10]
da Costa Borba B F, de Gusmão A P H, Clemente T R N, et al. Optimizing police facility locations based on cluster analysis and the maximal covering location problem[J]. Applied System Innovation, 2022, 5(4):74. DOI:10.3390/asi5040074

[11]
Bharsakade R, Kulkarni O, Afle A, et al. Analysis of and modeling for emergency medical services facility location for road accidents on highway[J]. International Journal of Mechanical and Production Engineering Research and Development, 2018, 8(1):595-604. DOI:10.24247/ijmperdfeb201866

[12]
Csiszár C, Csonka B, Földes D, et al. Urban public charging station locating method for electric vehicles based on land use approach[J]. Journal of Transport Geography, 2019, 74:173-180. DOI:10.1016/j.jtrangeo.2018.11.016

[13]
Tung A K H, Hou J, Han J W. Spatial clustering in the presence of obstacles[C]. Proceedings 17th International Conference on Data Engineering. IEEE, 2001:359-367. DOI:10.1109/ICDE.2001.914848

[14]
Estivill-Castro V, Lee I. Autoclust+: Automatic clustering of point-data sets in the presence of obstacles[M]// Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001:133-146. DOI:10.1007/3-540-45244-3_11

[15]
John A, Mathiyalagan P, Blessy A. Continuous moving object clustering in dynamic road network[C]. 2020 International Conference on Inventive Computation Technologies (ICICT). IEEE, 2020:710-715. DOI:10.1109/ICICT48043.2020.9112410

[16]
Zaiane O R, Lee C H. Clustering spatial data when facing physical constraints[C]. 2002 IEEE International Conference on Data Mining, 2002. Proceedings. IEEE, 2002:737-740. DOI:10.1109/ICDM.2002.1184042

[17]
Wang X, Wang J. Using clustering methods in geospatial information systems[J]. Geomatica, 2010, 64(3):347-361. DOI: 10.5623/geomat-2010-0035

[18]
Li X P, Zhao Z X, Zhu X Y, et al. Covering models and optimization techniques for emergency response facility location and planning: A review[J]. Mathematical Methods of Operations Research, 2011, 74(3):281-310. DOI:10.1007/s00186-011-0363-4

[19]
Xiao Y, Wang Z, Li Z G, et al. An assessment of urban park access in Shanghai-Implications for the social equity in urban China[J]. Landscape and Urban Planning, 2017, 157:383-393. DOI:10.1016/j.landurbplan.2016.08.007

[20]
Mohammed A F, Baiee W R. The GIS based criminal hotspot analysis using DBSCAN technique[J]. IOP Conference Series: Materials Science and Engineering, 2020, 928(3):032081. DOI:10.1088/1757-899X/928/3/032081

[21]
Peng Y H, Zhuang Y, Yang Y H. A driving cycle construction methodology combining k-means clustering and Markov model for urban mixed roads[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 2020, 234(2/3):714-724. DOI:10.1177/0954407019848873

[22]
Gao Y, Zhang Y, Alsulaiman H. Spatial structure system of land use along urban rail transit based on GIS spatial clustering[J]. European Journal of Remote Sensing, 2021, 54(sup2):438-445. DOI:10.1080/22797254.2020.1801356

[23]
Hu W J, Dong J J, Hwang B G, et al. Network planning of urban underground logistics system with hub-and-spoke layout: Two phase cluster-based approach[J]. Engineering, Construction and Architectural Management, 2020, 27(8):2079-2105. DOI:10.1108/ecam-06-2019-0296

[24]
Pattanaik L N, Gupta A K, Surin S, et al. Application of clustering algorithms for locating distribution centers of logistics system[M]//Mahapatra R P, Panigrahi B K, Kaushik B K, et al, eds. Lecture Notes in Networks and Systems. Singapore: Springer Singapore, 2021:503-510. DOI:10.1007/978-981-33-4501-0_46

[25]
Bayturk E, Esnaf S, Kucukdeniz T. A revised weighted fuzzy c-means and Nelder-Mead algorithm for probabilistic demand and customer positions[J]. Journal of Intelligent & Fuzzy Systems, 2021, 42(1):465-475. DOI:10.3233/JIFS-219204

[26]
Rezaee B. A cluster validity index for fuzzy clustering[J]. Fuzzy Sets and Systems, 2010, 161(23):3014-3025. DOI: 10.1016/j.fss.2010.07.005

[27]
Davies D L, Bouldin D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, PAMI-1(2):224-227. DOI:10.1109/TPAMI.1979.4766909

[28]
Rousseeuw P J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[J]. Journal of Computational and Applied Mathematics, 1987, 20:53-65. DOI:10.1016/0377-0427(87)90125-7

[29]
Chen J, Shi Y K, Sun J Q, et al. Base station planning based on region division and mean shift clustering[J]. Mathematics, 2023, 11(8):1971. DOI:10.3390/math11081971

[30]
Wang N, Wang C F, Niu Y F, et al. A two-stage charging facilities planning method for electric vehicle sharing systems[C]// 2020 IEEE/IAS 56th Industrial and Commercial Power Systems Technical Conference (I&CPS). IEEE, 2020:1-7. DOI:10.1109/ICPS48389.2020.9176750

[31]
Liang H J, Yuan G H, Han J T, et al. A multi-objective location and channel model for ULS network[J]. Neural Computing and Applications, 2019, 31(1):35-46. DOI:10.1007/s00521-018-3636-5

[32]
Pal N R, Bezdek J C. On cluster validity for the fuzzy c-means model[J]. IEEE Transactions on Fuzzy Systems, 1995, 3(3):370-379. DOI:10.1109/91.413225

Options
Outlines

/

〈 〉