资源描述：
《基于遗传算法的面状地理实体聚类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第20卷第3期地理与地理信息科学Vol.20No.32004年5月GeographyandGeo-InformationScienceMay2004基于遗传算法的面状地理实体聚类12111杨春成,张清浦,田向春,何列松,苏永宪(1.西安测绘研究所,陕西西安710054;2.中国测绘科学研究院,北京100039)摘要:该文提出一种利用遗传算法解决面状地理实体聚类问题的新方法。设计的遗传算法采用整数编码和RARw交叉算子。针对整数编码提出了新的初始种群生成方法和基因多样性度量
2、方法。试验结果表明,该方法能部分改善面状地理实体的聚类质量。关键词:空间聚类;RARw交叉算子;遗传算法中图分类号:P208文献标识码:A文章编号:1672-0504(2004)03-0012-05最大邻居数,Numlocal是可获得的最大局部最优解数。0引言算法从一随机选择的节点(当前局部最优解)开始,检空间数据挖掘是从空间数据库中识别或提取隐测节点的一个随机邻居,寻找更优解。如果找到,则[1]含特征和未知关系,是数据挖掘研究的子领域之将找到节点作为当前局部最优解继续该过程,直至[2]一。其目的是:
3、1)抽取有意义的空间模式和特征;maxneighbor次数满足。否则,认为当前解是一局部最2)获取空间数据和非空间数据之间的内在联系;3)优解,继续新的寻优过程,直到Numlocal个局部最优在更高概念层次上以简洁方式展示数据规律性;4)解得到算法终止。这种随机搜索算法不能保证得到利用所获知识调整空间数据库结构,使之更适合全局最优解,因为寻优次数受Numlocal参数限制,算表达数据语义,提高数据库整体性能。法也不一定能得到真正的局部最优解,因为寻找局部空间聚类是空间数据挖掘的重要组成部分,是最优解的次数受m
4、axneighbor参数限制。另外,如果按照某种相似性度量准则,将空间数据集分组成为算法初值选择不当,最终得到的结果会受影响。由类似对象组成的多个类或簇的过程。类中对象彼有鉴于此,本文基于遗传算法求解面状地理实体的此间具有较高相似性,类间对象具有较大差异性。聚类问题。遗传算法是一种全局优化搜索算法,它能同空间聚类可以从空间数据集中发现对象的凝聚趋时在解空间的多个区域进行搜索,并且能以较大概率跳[7]势、分布规律和发展方向;它通常还是空间数据挖掘出局部最优,所以遗传搜索的结果是全局最优的。[3]的首要步骤,聚类的
5、结果可作为其它空间数据挖1划分聚类算法与适应度函数的设计掘方法的输入数据,做进一步的挖掘分析。为此,提[1,4,5]出了许多针对空间数据集的聚类算法,这些算依据表示聚类对象特征的数据类型、聚类的目的法的预设前提是聚类对象是点状地理实体。而在实和应用领域的不同,聚类算法主要可分为划分算法、际应用中,空间聚类的对象既可能是点状地理实体,层次算法、基于密度算法、基于网格算法和基于模型也可能是线状、面状和体状地理实体。如何针对面算法[8]。其中划分算法又分为基于质心或中心点的状地理实体设计聚类算法是本文探讨的重点。划
6、分算法、基于图划分的聚类算法、模型搜索聚类算文献[6]提出一种基于随机搜索的针对点状对象法和最近邻居聚类算法[9]等。基于中心点划分算法和面状对象聚类算法。算法将已知n个对象、发现k将n个对象划分k类(k<=n),其中每个划分代表一个中心点的过程抽象为图的搜索过程。在这个图中,个簇,并用接近聚类中心的一个对象表示该簇。基于一个节点是k个对象的集合{Om1,!,Omk},Om1,!,中心点划分算法不易受噪声和孤立点数据的影响,Om是选择的中心点。图中所有节点的集合为:聚类的形状对聚类质量的影响较基于质心划分算法
7、小。k{{Om,!,Om}
8、Om,!,Om是数据集中的对象}基于中心点聚类问题是一类组合优化问题。已1k1ks如果两个节点仅有一个对象不同,则称此两节点是邻知s维实空间R上n个对象S={x1,x2,!,xn}和一固居。算法指定两个参数,其中maxneighbor是节点的定整数k(聚类数),欲从n个对象中发现k个对象{o1,收稿日期:2004-02-08;修订日期:2004-04-06作者简介:杨春成(1966-),男,博士研究生,高级工程师,主要研究方向为空间数据库与数据仓库。第3期
9、杨春成等:基于遗传算法的面状地理实体聚类第13页!,ok}=k(聚类中心对象),使目标函数最小,即:为了确定式(2)与式(3)定义的两类适应度函数nminmin∀xi-ol∀(1)哪个更优,从457个对象中生成12个簇,设计遗传o,!,oi=1l=1,!,k1k算法。种群规模为12,得到两种适应度函数的适应式中:xi=,xij(1#j#s,1
