基于复杂网络聚类的最优选址模型_戴技才

《基于复杂网络聚类的最优选址模型_戴技才》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第33卷第2期地理科学Vol.33No.22013年02月SCIENTIAGEOGRAPHICASINICAFeb.,2013基于复杂网络聚类的最优选址模型12戴技才，宗会明（1.重庆师范大学地理与旅游学院重庆400047；2.西南大学地理科学学院，重庆400715）摘要：最优选址在社会经济活动中非常重要。传统的网络聚类分析以空间两点之间的直线度量距离，而不是以空间最短网络路径作为聚类条件，无法找到复杂网络的最优选址中心。基于最短路径的复杂网络聚类模型，探索复杂道路网络中的最优选址。模型通过迭代法获取近似最优解，二分邻域分割法逼近最优解分布区，应用邻域下降

2、法达到最优选址点。实验结果表明：本模型与穷举-Dijkstra算法相比，计算精度相当，计算速度提高了约23倍以上。模型以复杂网络聚类为基础推导，为复杂网络选址、聚类提供了一种新的理论与方法。关键词：选址；网络聚类；复杂网络；最短路径；Dijkstra算法中图分类号:K903文献标识码:A文章编号:1000-0690(2013)02-0143-07为了揭示大型自然与社会复杂网络的社团结构等前言[17,18]性质，学者们提出了基于局部搜索的快速复杂[19~21]选址模型属于网络聚类分析的范畴。网络聚网络聚类算法。基于密度的聚类方法对孤立[22]类能分析网络拓扑

3、结构、理解网络功能，是数据挖点不敏感，能发现任意形状的类。[1,2]掘、探查性数据分析中的重要支撑技术。网络谱方法(spectralmethod)将网络聚类转化为二聚类法的基本原则是：给定n个样本，按照一定的次型优化问题，通过计算特殊矩阵的特征向量优[23]分类方法将数据划分为k类(或者称为簇，k≤n)，每化预定义截函数进行聚类。除此之外，还有基于个类至少包含一个样本，且每个样本只属于某一统计学方法、神经网络方法、基于网格的多分辨率类。网络聚类的类中心可以作为单点选址或多点聚类法等。上述聚类算法几乎都是采用点与点之选址的地点。网络聚类方法较多，各有特点，如

4、层间欧氏距离或曼哈顿距离、切比雪夫距离等(Eu-次聚类法采用系统树状图表示类的包含隶属关系clidian,Manhattan,Chebyshev)进行聚类，不适合基[3,4]对类进行合并与分裂。K均值算法(k-means)随于最短网络路径的复杂道路网络聚类。道路网络[5~7]机选取k个点，采用非监督聚类算法形成k类。的聚类中心离本类各节点的平均距离近，离其它ISODATA算法是更加完善的K均值算法，该算法类各节点的平均距离远，最适合空间选址，但鲜有不但可以调整样本的所属类别，而且可以自动进文献报道。本文提出复杂网络聚类模型，探索基[8]行类别的分裂与合并。

5、模糊聚类(fuzzycluster-于复杂道路网络的最优选址。ing)将每个数据点以一定的模糊度隶属于每个聚1模型[9,10]类集。K近邻算法(kNN)基于近邻的优势类将准备进行聚类的对象划分到离训练数据集最近的基于复杂网络聚类的选址模型分为两步。[11,12]对象类。期望最大算法(EM)采用最大似然法第一步：获取近似最优解，模型采用迭代法求取[13]对样本数据进行估计分类。图论聚类应用最小近似最优解。第二步：逼近最优解，模型利用二生成树，根据两点之间的最大空间距离和最大完分邻域下降法逐步逼近最优解。模型流程图如图[14,15][16]成子图进行聚类，已应

6、用于大型网络聚类。1所示。收稿日期：2012-01-09；修订日期：2012-04-09基金项目：教育部人文社会科学研究青年基金(批准号:11YJCZH023)；国家自然科学基金项目（41271411，41001102）资助。作者简介:戴技才(1974-)，男，湖南益阳人，博士，讲师，主要从事地理信息系统模型，复杂系统研究。E-mail:daijicai@cqnu.edu.cn通讯作者：宗会明，博士，副教授。E-mail:zonghuim@swu.edu.cn144地理科学33卷图1复杂网络聚类选址模型流程Fig.1Flowchartoflocationa

7、llocationbasedoncomplexnetworkclustering1.1获取近似最优解方程式(1)表示：获取近似最优解的方法如下，以图2所示的复d=b⋅c⋅(x-x)2+(y-y)2(1)iiii杂道路网络聚类为例说明。假设在该网络中欲选di也可认为是最优位置点P至Pi处的网络流量。取一个点，作为救灾物质储备库。救灾物质储备假设网络有n个节点，所有节点至最优位置点库的选址点必须位于某一网络节点上，与网络各P的救灾物质输送量之和为D，用方程式(2)表示：节点的加权最短路径之和最小。该选址的实际意nn22义是：该道路网络的各节点同时发生某种灾害，

8、救D=∑di=∑b⋅ci⋅(x-xi)+(y-yi)(2)i=1i