EN中文

地理科学 >

2013 , Vol. 33 >Issue 2: 143 - 149

DOI: https://doi.org/10.13249/j.cnki.sgs.2013.02.143

基于复杂网络聚类的最优选址模型

  • 戴技才 , 1 ,
  • 宗会明 , 2
展开
  • 1.重庆师范大学地理与旅游学院 重庆 400047
  • 2.西南大学地理科学学院,重庆400715
宗会明,博士,副教授。 E-mail:

作者简介:戴技才(1974-),男,湖南益阳人,博士,讲师,主要从事地理信息系统模型,复杂系统研究。E-mail:

收稿日期: 2012-01-09

  要求修回日期: 2012-04-09

  网络出版日期: 2013-02-20

基金资助

教育部人文社会科学研究青年基金(批准号: 11YJCZH023)

国家自然科学基金项目（41271411,41001102）资助

收起

Model of Locating Optimal Sites Based on Complex Network Clustering

  • DAI Ji-cai , 1 ,
  • ZONG Hui-ming , 2
Expand
  • 1.College of Geographical Sciences, Chongqing Normal University, Chongqing 400047, China
  • 2.School of Geographical Sciences, Southwest University, Chongqing 400715, China

Received date: 2012-01-09

  Request revised date: 2012-04-09

  Online published: 2013-02-20

Copyright

本文是开放获取期刊文献，在以下情况下可以自由使用：学术研究、学术交流、科研教学等，但不允许用于商业目的.
Fold

摘要

最优选址在社会经济活动中非常重要。传统的网络聚类分析以空间两点之间的直线度量距离,而不是以空间最短网络路径作为聚类条件,无法找到复杂网络的最优选址中心。基于最短路径的复杂网络聚类模型,探索复杂道路网络中的最优选址。模型通过迭代法获取近似最优解,二分邻域分割法逼近最优解分布区,应用邻域下降法达到最优选址点。实验结果表明：本模型与穷举-Dijkstra算法相比,计算精度相当,计算速度提高了约23倍以上。模型以复杂网络聚类为基础推导,为复杂网络选址、聚类提供了一种新的理论与方法。

关键词： 选址; 网络聚类; 复杂网络; 最短路径; Dijkstra算法

本文引用格式

戴技才 , 宗会明 . 基于复杂网络聚类的最优选址模型[J]. 地理科学, 2013 , 33(2) : 143 -149 . DOI: 10.13249/j.cnki.sgs.2013.02.143

Abstract

The best location for site selection is very important for social and economical systems. Traditional clustering analysis cannot reach the optimal location allocation center based on the Euclidian, Manhattan, Chebyshev, Fu or Tanimoto distance,which does not depend on the shortest path distance as the clustering condition. Complex network clustering model based on the shortest path is proposed to explore site selection in this paper. The approximate optimal results are obtained using the iterative technology. The searching range of optimal site allocation is approached by half dividing the neighborhood. And the best location is captured applying the descend strategy. Experiments indicate that the proposed model can improve the calculating speed by at least 23 times with the same precision to approach the optimal resolution compared to the greedy Dijkstra algorithm. This model is inferred from the complex network clustering. It provides new theory and method to cluster complex network and locate sitting facilities.

Key words： location allocation; network clustering; complex network; shortest path; Dijkstra algorithm

前 言
选址模型属于网络聚类分析的范畴。网络聚类能分析网络拓扑结构、理解网络功能,是数据挖掘、探查性数据分析中的重要支撑技术[1,2]。网络聚类法的基本原则是：给定n个样本,按照一定的分类方法将数据划分为k类(或者称为簇,k≤n),每个类至少包含一个样本,且每个样本只属于某一类。网络聚类的类中心可以作为单点选址或多点选址的地点。网络聚类方法较多,各有特点,如层次聚类法采用系统树状图表示类的包含隶属关系对类进行合并与分裂[3,4]。K均值算法(k-means)随机选取k个点,采用非监督聚类算法形成k类[5~7]。ISODATA算法是更加完善的K均值算法,该算法不但可以调整样本的所属类别,而且可以自动进行类别的分裂与合并[8]。模糊聚类(fuzzy clustering)将每个数据点以一定的模糊度隶属于每个聚类集[9,10]。K近邻算法(kNN)基于近邻的优势类将准备进行聚类的对象划分到离训练数据集最近的对象类[11,12]。期望最大算法(EM)采用最大似然法对样本数据进行估计分类[13]。图论聚类应用最小生成树,根据两点之间的最大空间距离和最大完成子图进行聚类[14,15],已应用于大型网络聚类[16]。为了揭示大型自然与社会复杂网络的社团结构等性质[17,18],学者们提出了基于局部搜索的快速复杂网络聚类算法[19~21]。基于密度的聚类方法对孤立点不敏感,能发现任意形状的类[22]。
谱方法(spectral method)将网络聚类转化为二次型优化问题,通过计算特殊矩阵的特征向量优化预定义截函数进行聚类[23]。除此之外,还有基于统计学方法、神经网络方法、基于网格的多分辨率聚类法等。上述聚类算法几乎都是采用点与点之间欧氏距离或曼哈顿距离、切比雪夫 距离等(Euclidian, Manhattan, Chebyshev)进行聚类,不适合基于最短网络路径的复杂道路网络聚类。道路网络的聚类中心离本类各节点的平均距离近,离其它类各节点的平均距离远,最适合空间选址,但鲜有文献报道。本文提出复杂网络聚类模型,探索基于复杂道路网络的最优选址。

1 模 型

基于复杂网络聚类的选址模型分为两步。第一步：获取近似最优解,模型采用迭代法求取近似最优解。第二步：逼近最优解,模型利用二分邻域下降法逐步逼近最优解。模型流程图如图1所示。
Fig. 1 Flow chart of location allocation based on complex network clustering

图1 复杂网络聚类选址模型流程

1.1 获取近似最优解

获取近似最优解的方法如下,以图2所示的复杂道路网络聚类为例说明。假设在该网络中欲选取一个点,作为救灾物质储备库。救灾物质储备库的选址点必须位于某一网络节点上,与网络各节点的加权最短路径之和最小。该选址的实际意义是：该道路网络的各节点同时发生某种灾害,救灾物质从储备库运送到各受灾点(各节点)的总时间最少。定义如下变量与公式：
Pi是已知的网络节点(xi,yi) (i= 0,1,2,…n)。
P为待求的最优救灾物质储备库的选址点 (x,y),即本案例的最优解。
ci是网络节点Pi处的人数。
b是某救灾物质的人均需求量。
假设该网络中各节点同时发生了某种灾害,救灾物质储备库向网络中其它各点输送救灾物质。定义救灾物质输送量di是最优位置点P至Pi处应输送的救灾物质的量。di是一种加权距离,用方程式(1)表示：
d i = b ⋅ c i ⋅ ( x - x i ) 2 + ( y - y i ) 2 (1)
di也可认为是最优位置点P至Pi处的网络流量。
假设网络有n个节点,所有节点至最优位置点P的救灾物质输送量之和为D,用方程式(2)表示：
D = ∑ i = 1 n d i = ∑ i = 1 n b ⋅ c i ⋅ ( x - x i ) 2 + ( y - y i ) 2 (2)
D其实就是整个网络流量,定义为目标函数。当目标函数D取最小值时对应的(x,y),即为本案例的最佳选址点。目标函数D是一个二元函数。根据二元函数连续的定义可知,D是连续函数。函数D的定义域为 x ∈ ∈ ( - ∞ , + ∞ ) , y ∈ ∈ ( - ∞ , + ∞ ) 。对应实际问题,定义域为有界闭区域。在有界闭区域上,连续函数D有界,且能取得它的最小值。D的最小值的几何意义是：网络中存在某个点,该点至网络上其它各点的加权距离之和最小,如图2所示。求函数D的最小值和最佳选址点(x,y)的方法有如下两种。
方法一：牛顿迭代法。求函数D的所有驻点,对式(2)分别求偏导数 ∂ D ∂ x , ∂ D ∂ y ,并使偏导数为0,得方程组(3)。
∂ D ∂ x = ∑ i = 1 n b ⋅ c i ⋅ ( x - x i ) ( x - x i ) 2 + ( y - y i ) 2 = 0 ∂ D ∂ y = ∑ i = 1 n b ⋅ c i ⋅ ( y - y i ) ( x - x i ) 2 + ( y - y i ) 2 = 0 (3)
用牛顿迭代法求解线性方程组(3)的解。若用向量记号记 T = ( x , y ) Τ , F = ( ∂ D / ∂ x , ∂ D / ∂ y ) Τ 。方程组(3)就可写成
F(x,y) = 0 (4)
求F(x,y)的雅可比(Jacobi)矩阵及其逆矩阵。
F ' ( x , y ) = ∂ 2 D ∂ x 2 ∂ 2 D ∂ x ∂ y ∂ 2 D ∂ y 2 ∂ 2 D ∂ x ∂ y (5)
记解为 ( x , y ) k + 1 ,则得.
( x , y ) k + 1 = ( x , y ) k - F ' ( ( x , y ) k ) - 1 F ( ( x , y ) k ) (6)
式(5)中的各项如下。
∂ 2 D ∂ x 2 = ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 - b ⋅ c i ⋅ ( x - x i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3
= b ⋅ c i ⋅ ( y - y i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3 (7)
∂ 2 D ∂ y 2 = ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 - b ⋅ c i ⋅ ( y - y i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3
= b ⋅ c i ⋅ ( x - x i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3 (8)
∂ 2 D ∂ x ∂ y = - ∑ i = 1 n b ⋅ c i ⋅ ( x - x i ) ( y - y i ) ( x - x i ) 2 + ( y - y i ) 2 3 (9)
在 ( x i , y i ) i = 1,2 ⋯ n 已知的前提下,牛顿迭代法求解是一种快捷方法。对于本类问题,初值选定义域内的任一点都不敏感,且牛顿法的根以平方收敛。但是牛顿迭代法的公式相对较复杂,需要求二阶偏导数,还要求矩阵的逆。
方法二：重心法。对方程组(3)稍作变化,变成方程组(10)所示的迭代表达式。
x = ∑ i = 1 n b ⋅ c i ⋅ x i ( x - x i ) 2 + ( y - y i ) 2 ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 y = ∑ i = 1 n b ⋅ c i ⋅ y i ( x - x i ) 2 + ( y - y i ) 2 ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 (10)
方法二的几何意义是基于反距离权重迭代求重心。将定义域内的任一点的坐标分别代入方程组(10)右边的(x,y),然后计算方程组(10)左边的(x,y),再以方程组(10)左边计算所得的(x,y)代入方程组右边(分母为0时,该点舍弃)。迭代5~10次,方程组的解可能趋于稳定。方法二较方法一简单,不必再求二阶导数与矩阵的逆,且收敛性容易证明。方法二的不足是计算量依然很大,不妨直接采用权重重心法,将方程组(10)改为方程组(11)式样。
x = ∑ i = 1 n b ⋅ c i ⋅ x i ∑ i = 1 n b ⋅ c i y = ∑ i = 1 n b ⋅ c i ⋅ y i ∑ i = 1 n b ⋅ c i (11)
方程组(11)的优点是：求解不再采用多次迭代,计算量较小;系数n、b、ci、xi、yi均已知,方程组(11)的解x和y都是唯一确定的数,绝对收敛。
应用上述两种方法得到的最小D值都是近似最优解,求解的网络聚类中心(x,y)是近似最优聚类中心,如图2所示。因为上述两种方法应用欧氏几何原理计算网络聚类中心至网络各节点的直线距离,而在实际道路网络中,空间两点的最短距离是最短网络路径,不是空间直线距离。因此,欲获得网络聚类的最优解,必须基于最短网络路径距离逐步逼近。
Fig. 2 Approach the approximate optimal location using iterative algorithm

图2 迭代法获取近似最优解

1.2 逼近最优解

逼近最优解共分两步。第一步：采用二分邻域分割法缩小最优解的候选区域。第二步：应用邻域下降法逐步逼近最优解。
复杂网络聚类模型应用迭代法获得的近似最优解一般不是网络节点,将离近似最优聚类中心最近的网络节点作为近似最优解(后续计算都以该网络节点为近似最优解),如图3a所示。应用穷举-Dijkstra算法分析网络可知：设网络节点至网络上其它各节点的最短路径之和为Z轴坐标值,所有网络节点的空间图形如图3b所示,呈朝口向上的抛物面形状。近似最优解常位于 “抛物面”的底部,但不是“抛物面”的最低处(最优解)。逼近最优解,模型采用二分邻域分割法。
Fig. 3 (a) the approximate optimal result fitting to the vertex of network, (b) space shape of the results

图3 (a)近似最优解拟合至网络节点,(b)解的空间形状

二分邻域分割法按如下步骤循环。第一次二分邻域以近似最优解为中心,二分之一网络图形的边长画矩形,如图4a所示。找出矩形框外满足如下条件的网络节点：连接这些节点的网络边与该矩形框相交。应用Dijkstra算法,计算这些网络节点至网络中其它节点的最短加权路径距离之和。比较近似最优解与这些网络节点的优劣。若近似最优解比上述节点更优,模型进行第二次二分邻域,如图4b所示。若上述某一节点比近似最优解更优,模型停止二分邻域,以上一步求得的矩形框内的区域作为最优解候选区。如图4c所示,矩形框外的某一网络节点比近似最优解更优,模型以图4b所示的矩形框内的区域作为最优解候选区。再应用邻域下降法,求最优解。
Fig. 4 Method of half dividing the neighborhood. (a) the length and width of the blue rectangle is half of the length and width of the original rectangle of the network, (b) the second half-dividing the neighborhood, (c) the third half-dividing the neighborhood

图4 二分邻域分割法。(a)蓝色矩形的长和宽分别为原网络图形长和宽的二分之一,(b)第二次二分邻域分割,(c)第三次二分邻域分割

邻域下降法的原理类似于最速下降法,遵循邻域下降的原则搜索解。如图5所示,基于复杂网络聚类的解的图形呈不规则开口朝上的椭圆抛物面。为了能搜索到这种形状的抛物面上的最小值点,邻域下降法模型在最优解候选区内,随机抽取9个以上网络节点为起点,进行邻域下降法搜索(如图5的搜索起点A、B、C、D、E),直到不再出现新的邻域下降路径为止。比较各邻域下降路径中的最小值,获得最优解。
Fig. 5 Principle of searching for the results based on the descend approach in the neighborhood

图5 邻域下降法搜索解的原理

邻域下降法的算法如下。第一步,求选定节点Pm至网络上其它节点的最短路径之和Dm。第二步,根据相邻节点之间的汇流关系、或者比较Dm与Dn(Dn为相邻节点Pn至网络上其它节点的最短路径之和,Pn为相邻节点的代称),确定从Pm出发的下降路径的节点。第三步,重复第二步,递归查找下降路径的节点,直到不能下降为止。以图6为例,说明邻域下降算法。设某一级别的二分邻域矩形框如图6所示,任意选取该框内的一个网络节点,不妨设为P1,应用Dijkstra算法,计算P1至所有网络节点的最短路径之和D1,用P1相邻节点的汇流进行计算。
D 1 = | | p 3 - p 1 | | × D 1 3 + | | p 4 - p 1 | | × D 1 4 + | | p 5 - p 1 | × D 1 5 + | | p 6 - p 1 | | × D 1 6 (12)
| p 3 - p 1 | 是网络节点P1至网络节点P3的网络路径距离, D 1 3 表示经P3点进入P1点的网络汇流量。不妨设 D 1 6 ≥ D 1 5 ≥ D 1 3 ≥ D 1 4 。若不等式(13)成立,则P6点是比P1点更优的解,下降路径为 P 1 → P 6 。若P1的四个相邻节点都不满足相应的形如(13)方程,则应用Dijkstra算法逐个求取D3 、D4 、D5 、D6,再与D1比较,得出下降路径,或停止该路径的搜索。
| p 6 - p 1 | | × ( D 1 - D 1 6 ) + D 1 6 ≤ D 1 (13)
Fig. 6 (a)Principle of the descend approach in the neighborhood, (b)path of searching the results

图6 (a)邻域下降法的算法原理,(b)邻域下降法搜索解的路径

2 模型分析与案例

模型采用牛顿迭代法或重心法获取近似最优解,利用二分邻域分割法和邻域下降法逼近最优解。求取近似最优解的目的是使二分邻域分割法有执行的标准。二分邻域下降法没有沿最速下降的方向搜索解,但能逐步趋优。模型随机选择节点为始点,从不同方向,不同路径趋近最优解,避免陷入局部最优。模型未在全局范围内采用邻域下降法搜索最优解,原因是在全局范围内,邻域下降的路径太多,邻域下降的速度太慢。全局邻域下降法的效率与穷举-Dijkstra算法的效率接近。
为了验证模型的有效性,分别应用网络聚类法与穷举-Dijkstra算法求解9个复杂道路网路的救灾物质储备库聚类选址中心。由于网络节点处的人数、救灾物质的人均需求量都为常数,为了简化本模型与其它模型对比时的复杂程度,不妨将上述两个参数都设为1,对比实验的目标函数化简为求解网络中的某一个节点,从该节点出发至网络中其它各点的最短路径距离之和的值最小。
对比实验分别选取中国大陆、英国、德国、法国、意大利、印度、日本、俄罗斯、美国本土的公路网(分别对应图7中的a~i)。图7中绿色点表示网络聚类模型第一步求得的近似最优解;红色框表示不同级别的二分邻域分割法逼近最优解所在的区域,红色点表示应用本模型找到的最优解。表1记录了网络节点数、弧段数,以及本模型与穷举-Dijkstra算法计算速度的对比,本模型是否找到了最优解。实验表明：复杂网络聚类法的计算精度高,速度快。
Fig. 7 To capture the optimal location site based on complex network clustering

图7 网络聚类法求解最优选址点

Table 1 Comparing with the results based on complex network clustering and greedy Dijkstra algorithm

表1 网络聚类法与穷举-Dijkstra算法的实验对比结果

国家或地区 节点数
（个）		 弧段数
（个）		 穷举-Dijkstra法用时(h) 网络聚类法用时
(h)		 网络聚类法是否找到了
最优解
中国大陆 21986 27256 49.47 1.83 是
英国 3774 5295 0.23 0.01 是
德国 3799 5343 0.24 0.01 是
法国 5314 7056 0.63 0.01 是
意大利 2563 3469 0.07 0.003 是
印度 15941 21674 17.09 0.31 是
日本 6706 8983 1.27 0.05 是
俄罗斯 37705 43908 258.49 9.32 是
美国本土 28602 46358 112.26 3.74 是

3 结 论

本文提出了基于复杂网络的聚类模型探索选址。模型采用牛顿迭代法或重心法求取近似最优解,应用二分邻域分割法缩小最优解的备选区。在最优解的备选区,模型利用邻域下降法,从不同路径和方向逼近最优解。在大型、巨型道路网络中,本模型适合寻找基于最短路径的最优选址点,为复杂网络选址与聚类提供了一种新的理论与方法。实验结果表明：本模型的算法与穷举-Dijkstra算法相比,计算精度相当,计算速度提高了约23倍以上。求解均匀道路网络中的空间选址,本模型的计算速度可以提高63倍。本模型尚存些许不足,有待进一步完善。对于形状特殊的网络,如网络重心不在网络边的包络中,模型的求解速度与穷举-Dijkstra算法相当;求解无标度网络的网络聚类中心,本模型可能会陷入局部最优。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Jain A K, Murty M N,Flynn P J.Data clustering: A review[J]. Acm Comput Surv, 1999, 31:264-323.

[2]
Wu X, Kumar V, Quinlan J R, et al.Top 10 algorithms in data mining[J]. Knowl Inf Syst, 2008, 14:1-37.

[3]
King B.Step-wise clustering procedures[J]. J Am Stat Assoc, 1967, 69:86-101.

[4]
Murtagh F.A survey of recent advances in hierarchical clustering algorithms which use cluster centers[J]. Comput J,1984, 26:354-359.

[5]
Lloyd S P.Least squares quantization in pcm[J]. IEEE T Inform Theory, 1982, 28(2):129-137.

[6]
Lloyd S P.Least squares quantization in pcm[C]. Bell Telephone Laboratories Paper, 1957.

[7]
Gray R M, Neuhoff D L.Quantization[J]. IEEE T Inform Theory, 1998, 44(6):2325-2384.

[8]
Ball G H, Hall D J.Isodata, a novel method of data analysis and classification[M]. Technical report republished by Stanford University, Stanford, CA, 1965.

[9]
Ruspini E H.A new approach to clustering[J]. Inf Control, 1969, 15:22-32.

[10]
Zadeh L A.Fuzzy sets[J]. Inf Control, 1965, 8:338-353.

[11]
Hart P.The condensed nearest neighbor rule[J]. IEEE T Inform Theory, 1968, 14:515-516.

[12]
Bezdek J C, Chuah S, Leep D.Generalized k-nearest neighbor rules[J]. Fuzzy Set Syst, 1986, 18(3):237-256.

[13]
Dempster A P, Laird N M, Rubin D B.Maximum likelihood from incomplete data via the EM algorithm[J]. J R Stat Soc B, 1977, 39:1-38.

[14]
Zahn C T.Graph-theoretical methods for detecting and describing gestalt clusters[J]. IEEE T Comput C, 1971, 20:68-86.

[15]
Guimera R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks[J]. Phys Rev E, 2004, 70:025101.

[16]
Pujol J M, Bejar J, Delgado J.Clustering algorithm for determining community structure in large networks[J]. Phys Rev E, 2006, 74:016107.

[17]
Palla G, Derenyi I, Farkas I, et al.Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435:814-818.

[18]
Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433:895-900.

[19]
Newman M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E, 2004, 69(6):066133.

[20]
Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Phys Rev E, 2004, 69:026113.

[21]
Duch J, Arenas A.Community detection in complex networks using extremal optimization[J]. Phys Rev E, 2005, 72:027104.

[22]
Jain A K.Algorithms for clustering data[M]. Prentice-Hall advanced reference series Prentice-Hall, Inc, Upper Saddle River, NJ, 1988.

[23]
Hagen L, Kahng A B.New spectral methods for ratio cut partitioning and clustering[J]. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 1992,1992, 11:1074-1085.

Options
文章导航

/

〈 〉