Message Board

Respected readers, authors and reviewers, you can add comments to this page on any questions about the contribution, review,        editing and publication of this journal. We will give you an answer as soon as possible. Thank you for your support!

Name
E-mail
Phone
Title
Content
Verification Code
Volume 44 Issue 2
Feb.  2019
Turn off MathJax
Article Contents

YING Shen, LI Weiyang, HE Biao, WANG Wei, WAN Yuan. Chinese Segmentation of City Address Set Based on the Statistical Decision Tree[J]. Geomatics and Information Science of Wuhan University, 2019, 44(2): 302-309. doi: 10.13203/j.whugis20170072
Citation: YING Shen, LI Weiyang, HE Biao, WANG Wei, WAN Yuan. Chinese Segmentation of City Address Set Based on the Statistical Decision Tree[J]. Geomatics and Information Science of Wuhan University, 2019, 44(2): 302-309. doi: 10.13203/j.whugis20170072

Chinese Segmentation of City Address Set Based on the Statistical Decision Tree

doi: 10.13203/j.whugis20170072
Funds:  The National Natural Science Foundation of China, Nos. 41671381, 41371369, 41531177;the National "13·5" Key R&D Program, Nos. 2016YFF0201301, 2017YFB0503500;the Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Land and Resources of China, No.KF-2018-03-010
More Information
  • Author Bio:

    First author: YING Shen, PhD, professor, specializes in the 3D cadastre and multi-scale map data representation.E-mail:shy@whu.edu.cn

  • Corresponding author: WAN Yuan, PhD. E-mail: wanyuan14@163.com
  • Received Date: 2017-03-28
  • Publish Date: 2019-02-05
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(9)  / Tables(7)

Article Metrics

Article views(1239) PDF downloads(326) Cited by()

Related
Proportional views

Chinese Segmentation of City Address Set Based on the Statistical Decision Tree

doi: 10.13203/j.whugis20170072
Funds:  The National Natural Science Foundation of China, Nos. 41671381, 41371369, 41531177;the National "13·5" Key R&D Program, Nos. 2016YFF0201301, 2017YFB0503500;the Open Fund of Key Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Land and Resources of China, No.KF-2018-03-010

Abstract: Different from the conventional address word segmentation model, which relies on the city address dictionary or the rule set, this paper proposes a word segmentation method which does not depend on the address dictionary but based on massive address data mining. This method combines the statistic rules to calculate the distribution of the address elements in the address dataset, excavates the suffix points and the drop points of the address elements in the address data. The method constructs the statistical decision tree based on their relative position relations to extract the address elements, uses the investigation data of building address in Shenzhen to verify and to make a useful supplement to the current gazetteers.

YING Shen, LI Weiyang, HE Biao, WANG Wei, WAN Yuan. Chinese Segmentation of City Address Set Based on the Statistical Decision Tree[J]. Geomatics and Information Science of Wuhan University, 2019, 44(2): 302-309. doi: 10.13203/j.whugis20170072
Citation: YING Shen, LI Weiyang, HE Biao, WANG Wei, WAN Yuan. Chinese Segmentation of City Address Set Based on the Statistical Decision Tree[J]. Geomatics and Information Science of Wuhan University, 2019, 44(2): 302-309. doi: 10.13203/j.whugis20170072
  • 现今城市各部门机构都存有海量与地址有关的信息,基本上是非结构化、非空间化的地址数据[1],以字符串的形式进行存储;地址数据表达了城市的行政区划、各级街道以及门牌号的信息,城市地址集是指城市范围内地址数据空间均衡分布的数据集合,如城市建筑物地址、居民家庭住址、快递地址等,城市地址集在本文中简称为地址集。地址分词是将地址集中地址数据分解成多个地址要素词组的过程[2],是地理编码[3]和地址匹配的基础。如地址数据“深圳市福田区福中一路2001号”,通过地址分词分解得到“深圳市”、“福田区”、“福中一路”、“2001号”等若干地址要素词组。

    不同于国外地址的规则化表达,中文地址数据没有明确的分隔符,且经常出现冗余或缺省,是由不同的地址单元信息组成的[4],增加了地址分词的难度。地址分词方法主要概括为机械分词法、知识分词法和统计分词法[5]。机械分词法是地址数据按照一定的扫描规则与城市地址词典进行匹配,包括正向最大匹配法[6]和逆向最大匹配法[7]等。正向最大匹配法是让地址数据按照正向递减的遍历规则依次与词典中词条进行匹配,尽可能保留最大长度,属于精确的匹配方法,但是需要建立一个尽量包含城市所有地址要素的词典来达到较高的正确度;知识分词法是通过人工智能建立基于语义知识和规则的地址分词模型,让模型尽量接近人理解地址数据的水平,这种方法需要大量正确的地址分词样本进行训练,加上地址数据和研究方法的复杂性,难以应用在实际环境中;统计分词法不依赖地址词典,是根据相邻字词的频繁度来进行地址分词[8],字词在语句中频繁的相邻出现能反映组合成地址要素的可信度,如隐Markov模型[9]N元模型[10]和最大熵模型[11]等,地址数据是按照一定的规则进行排列组织,不具备自然语言表达的多样性和随机性,单一的概率条件不能作为地址分词的依据。

    中文分词研究中常用的地址分词模型需要依赖城市地址词典[2, 12-13]或规则库[14]等繁琐的先验知识,本文设计不依赖地址词典的中文地址分词方法,根据城市内海量的地址要素在地址集的统计特征,辨别地址数据的后缀点和落差点,根据其相对位置关系构成决策树模型的分支条件,依据地址要素的特征形成不同条件的地址分词解决方案,达到对城市地名词典进行丰富和补充的目的。

  • 《地名地址数据规范》中规定地址要素按照一定的命名规范和习惯进行组织[15],实际上在中文地址中隐含着分隔符,如“街道”、“小区”、“街”、“路”、“大道”、“村”等地址要素中常见的后缀词。后缀词表示在地址要素中普遍出现的、能够在地址集中表示地址分隔的词。

    在实验过程中,认为连续的数字、符号、单个的中文字符为单元字符,因此可以将地址数据看成是离散化字符单元的顺序排列,每个单元字符在地址数据中存在相对应的位置点,紧随字符单元之后,称之为位置点,如图 1中单元字符“区”的位置点为f1,地址分词的过程则是确定地址数据中的多个位置点,分离出地址要素。根据地址数据的特征和城市基础建设命名的规范化,后缀词在地址集中的频繁出现,可以作为一种辅助的特征进行地址分词研究,在地址数据中出现后缀词的位置称为后缀点,后缀点是位置点中的一种。如深圳市大运中心体育馆地址“深圳市龙岗区龙翔大道3001号”的离散序列如图 1所示。

    Figure 1.  Discretization Order of the Address Data

    实验过程中,后缀词的集合包括中文地址集中常见的后缀词如“区”、“路”、“号”等,相应的在该地址数据中的后缀点分别为f1f2f3。地址数据的规范命名与表达,使得中文地址中实际上隐含着分隔符,后缀点能够在一定程度上表示地址数据的分隔符,从而为提取相应的地址要素提供了基础条件。

  • 《地名地址数据规范》中规定地址要素应包括行政区划、地址、子地址[15],地址要素代表了地址信息在地图内的一个空间位置点或者一个空间范围[16]。地址要素按照地址的排列组织在地图上表示的空间范围的大小是逐渐缩小的,对位置的描述是逐渐精细的过程。按照地址排列的顺序,地址要素在语义范围以及居民使用的频次是逐渐衰减的,这是本文地址分词研究的重要依据。

    本文以深圳市建筑物普查的地址数据集为实验数据,以地址“宝安区石岩街道应人石片区松白路2022号”为例。在地址分词中,单个字符单元不具备实际涵义,因此在地址切分时,词组的长度大于1;地址数据按照切分规则进行连续的不同位置的切分实验,每次正向顺序只切分一个位置将地址分为前部和后部,统计前部的地址字符串在地址集中出现的次数,并计算当前词组数量与前一词组数量的比值。获得统计表 1,比值变化如图 2所示。

    实例 前部 词组数量(Ni) 比值(Ni/Ni-1)
    1 宝安 274 462
    2 宝安区 273 215 0.995
    3 宝安区石 16 890 0.062
    4 宝安区石岩 16 753 0.992
    5 宝安区石岩街 16 639 0.993
    6 宝安区石岩街道 16 637 1.000

    Table 1.  Statistical Information of "Baoan" Based Phrase Segmentation

    Figure 2.  Statistical Changes of the Number About Phrases in "Baoanqu"

    表 1图 2中,“宝安区”到“宝安区石”的词组数量出现了明显了下滑,以该位置点为分界点,前部词组的数量出现了两个不同的数量量级,在该位置点切分之后,原地址数据中后部的地址字符串为“石岩街道应人石片区松白路2022号”,以此地址信息再次统计词组数量和比值变化,见表 2图 3

    实例 前部 词组数量(Ni) 比值(Ni/Ni-1)
    1 石岩 17 809
    2 石岩街 16 922 0.950
    3 石岩街道 16 920 1.000
    4 石岩街道应 340 0.020
    5 石岩街道应人 313 0.921
    6 石岩街道应人石 313 1.000
    7 石岩街道应人石片 44 0.141
    8 石岩街道应人石片区 44 1.000

    Table 2.  Statistical Information of "Shiyan" Based Phrase Segmentation

    Figure 3.  Statistical Changes of the Number About Phrases in "Shiyanjiedao"

    表 2中从“石岩街道”到“石岩街道应”前部词组的数量同样出现了明显的下滑落差。在地址集中,地址要素的数目会随着地址词组排列顺序进行衰减,结合中文单元字符的单一性和独立性,前部词组的数量会在某个位置点出现明显下滑,这个位置点称为地址数据的落差点。落差点在地址集中可以反映地址要素之间数量的下滑。

    表 2图 3的描述中,从“石岩街道应人石”词组到“石岩街道应人石片”词组的数量出现了下滑的落差,正确的分词结果“应人石片区”为完整的地址要素,根据落差点进行地址分词时在此位置点出现误判。通过查找“应人石”词组在地址集中后部主要接词种类,进行统计和汇总,如表 3所示。

    实例 词组 词组数量
    1 应人石社(区) 121
    2 应人石片(区) 109
    3 应人石村 92
    4 应人石路 90
    5 应人石新(村) 30
    6 应人石老(村) 23

    Table 3.  Category Statistics of Phrases Based on "Yingrenshi"

    其中“应人石”词组在地址集的数量为474,从表 3中可以看出,“应人石”在地址集中构成的地址要素种类主要有“应人石社区”、“应人石片区”、“应人石村”等。通过对“应人石”词组数量到其构成的地址要素的数量进行对比,所有地址要素均出现了下滑,其中“应人石新村”和“应人石老村”数量变化是明显大幅度的下滑,但是这些词组在地址分词过程中属于正确的联结。在中文地址集中,某一词组后部会存在多种可能的接词,且是属于正确的联结,因此依靠单一的落差点进行地址分词时会造成误判。

    为解决落差点产生的误判问题,在单次的地址分词时引入了双落差点,如词组“应人石片区松白路”在地址集的前部数量统计如表 4所示。

    实例 前部 词组数量(Ni) 比值(Ni/Ni-1)
    1 应人 477
    2 应人石 474 0.994
    3 应人石片 109 0.230
    4 应人石片区 109 1.000
    5 应人石片区松 5 0.046
    6 应人石片区松白 5 1.000
    7 应人石片区松白路 4 0.800

    Table 4.  The Statistical Information of "Yingrenshi" Based Phrase Segmentation

    表 4图 4中可以看出,在从“应人石”到“应人石片”和从“应人石片区”到“应人石片区松”的词组数量变化出现了明显落差,为落差点,此时在这两个位置点切分地址数据会得到两个地址要素,为“应人石”和“片区”。在地址集中“片区”词组在地址集的数量(38 574)远高于“应人石”词组的数量(474)。按照地址要素的数量会随着地址排列的顺序进行衰减这一特征,“片区”这一词组不满足此特征,因此不能在第一个落差点进行地址切分。

    Figure 4.  Double Drop Points of the "Yingrenshi" Based Phrase

    这一现象的产生可以从地址要素的组成进行解释,邬伦等[17]通过地名的“专名+通名”的结构上总结归纳各词素类型的特征,同样地址要素是特征词和方向(类型)词组成,或者是由单独的特征词组成;特征词是地址要素中表示专有地名信息的词汇,如“天安门”、“颐和园”等;方向(类型)词是表示特征词的方向或者地址要素的类型,如“西路”、“一巷”等。地址要素“下沙”、“田贝”和“西丽”是由单独的特征词组成,而地址要素“桃源村”是特征词“桃源”和类型词“村”组成。根据中文地名的命名习惯,特征词后面经常会出现多种方向(类型)词,表示不同的地址要素,如特征词“应人石”后续出现了“社区”、“片区”、“路”、“村”等类型词。方向(类型)词在地址集中出现的次数很频繁,可以反向验证地址分词的正确性。

    在研究过程中发现,单一地依赖后缀点进行地址分词会使得完整的地址要素产生断裂,如“龙岗街道办事处”地址要素中出现后缀词“街道”,另外地址集的后缀词不可穷举性使得其正确率有限;单一地依靠落差点则会产生遗漏和误判。借助落差点能够依靠地址集自身特征识别出地址要素,与后缀点的隐式分隔符形成互补关系,落差点作为辅助判断决策信息进行地址分词。本文在研究过程中组合后缀点和落差点及相关的地址要素特征,并且引入统计决策树的模式实现递归地址分词过程。

  • 决策树是以实例为基础的归纳学习算法,着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则,通常用来形成分类器和预测模型,可以对未知数据进行分类或预测、数据挖掘等[18]。本文中使用地址数据中的后缀点和落差点构建决策树的分枝和节点;根据上文中的实验分析和地址要素的特征,对决策树的节点进行判断处理,形成地址分词过程,并利用决策树对地址集中的地址数据进行递归分词。

    统计决策树模型中涉及到的符号和方法及其含义如下:s为待分词的地址数据;fis中正向第一次出现后缀词时点的位置;OS中正向出现的至多两个落差点的位置集合为O:[ai, bi],其中aibi;sepis单次地址分词时的确定位置;Null(object)方法判断对象object是否为空或不存在,其中为空或不存在时返回true,否则返回false;Num(str)方法是统计字符串str在地址集中的数量,为统计特征值;Segment(array)方法是对集合array进行集合判断(下文中有详细描述)。

    统计决策树模型如图 5所示,分为条件判断、节点分类、节点处理和集合判断模块。条件判断是初始判断过程,根据基本条件进行粗分类;节点分类是根据粗分类中位置点可能出现的情况进行归纳总结;节点处理是对归纳的节点进行精简处理;集合判断是对精简后的位置点集合进行分析处理,确立分词位置点。

    Figure 5.  The Flow Chart of Decision Tree Model

    图 5中所示,决策树模型运行到节点处理模块时,可以归纳为两种情况:

    1) 结果位置集R中只有一个位置点mi,此时分词位置即为该位置点,Sepi=mi

    2) 结果位置集R中有两个不相等的位置点:R:[mini](mini)。

    前后位置点的相对位置会影响地址要素的切分,下面以实例进行阐明。

    实例1   mi+1=ni时,表示两个位置点之间只有一个单元字符,单个单元字符不能构成地址要素,因此需要将其进行合并处理。如图 6所示,“宝安区”和“石岩街道”词组已经进行正确的地址分词,在待处理前部词组中“应人石路263号”,出现了落差点mi和后缀点ni,且mi+1=ni,“路”不足以构成地址要素,因此确立切分位置为ni,即Sepi=ni

    Figure 6.  Relative Distance is 1 Point in Two Positions

    实例2  当mi+1<ni时,表示两个位置点之间有多个单元字符,按照地址要素在地址数据中的特征进行决策。如图 7所示,待处理前部词组为“应人石片区松白路2022号”,根据决策树模型的处理逻辑,结果位置集中存在位置点minimi是第一个落差点,ni是后缀点,也是第二个落差点,其中mi+2=ni。此时统计地址数据在mini位置点之间的词组在地址集的数量Nmulti和前部词组在mi位置的词组在地址集的数量Nbefore

    如果NmultiNbefore, 说明中间字符串“片区”的数量高于第一个位置点的前部字符串“应人石”的数量。若是选择在mi进行地址切分, 则产生地址要素“应人石”和后续递归产生的地址要素“片区”,按照地址要素数量衰减的分词逻辑,则会产生矛盾, 因此分词位置为ni,即Sepi=ni

    Figure 7.  Two Positions with Relative Distance over 1

    如果NmultiNbefore,此时前部的地址要素和后续可能的地址要素的数量满足衰减的逻辑,因此分词位置为mi,即Sepi=mi

    统计决策树地址分词模型构建完成,对于单条地址数据获得确定的切分位置Sepi之后,在位置点Sepi之后的地址尾部信息可能包含其他的地址要素,需要进一步的地址分词。按照递归的方法对尾部地址要素进行提取和决策,直到尾部地址信息不足以构成地址要素,地址要素的最小单元字符长度K值为2。基于决策树模型的地址分词流程算法如图 8所示。

    Figure 8.  Flow Chart of Address Segmentation

  • 本文中使用的实验数据是由深圳市政府单位提供的深圳市建筑物地址普查数据,共有518 948条地名地址数据。在不依赖于城市地址词典的条件下,通过统计和规则建立的决策树模型对深圳市建筑物地址集进行地址分词,分词的结果能够建立和完善城市的地名地址词典,在系统配置为Inter(R)Core(TM)i7-4790 CPU@ 3.60 GHz、内存8 GB的计算机上单条地址数据的分词过程耗时4.5 ms(见表 5)。由于地址分词结果在领域上没有统一的标准模型进行评价,且实验数据的数据量较大,采取简单随机抽样的方法检测200条分词结果的正确率α和错误率β,计算公式为:

    地址分词方法 正确率 依赖地址词典 学习方式 通用性 单条地址分词时间/s
    统计分词法 较高(< 80%) 无监督 0.183 0
    机械分词法 受地址词典影响大 不支持 > 1
    本文方法 高(> 90%) 无监督 0.004 5

    Table 5.  Comparision Between Methods of This Paper and Others

    分词结果中存在错误的类型包括遗漏和误判,单条地址数据中地址要素未能全部提取正确均算错误。

    机械分词法需要依赖地址词典,而地址分词则是建立或完善城市地名地址库,与机械分词分词法在出发点上存在不同,本文在实验过程中无现存的地址词典提供帮助,难以与机械分词法进行正确率的评价分析; 统计分词法以相邻字词的频繁度为依据,忽略了地址集中地址数据的表达不似自然语言的随机性,地址数据是以行政区划、街道、门牌号等地址要素按顺序排列。相较而言,本文考虑地址要素在城市地址集中的统计特征,利用决策树模型建立地址分词体系,能有效克服地址数据中地址要素的缺失和冗余,并能达到较高的正确率,同时不依赖地址词典,无监督的学习方式能适用于我国大多数城市的地址分词过程。

    本文综合后缀点和落差点的优势,组合后缀点和落差点及相关的地址要素特征,构建决策树判断模型进行地址分词,正确率有较大的提升,样本中部分的正确分词结果如表 6所示,表 7是抽样中错误分词结果数据的典型集合。

    实例 地址数据分词结果
    1 宝安区|西乡街道|富源工业城|C6栋
    2 宝安区|石岩街道|浪心社区|石岩新村|86栋
    3 宝安区|公明街道|塘尾|宝塘工业区|080栋
    4 罗湖区|桂木园片区|桂木园|17号|东
    5 龙岗区|圳埔|新一村|九巷|10号
    6 宝安区|大浪街道|鹊山|云峰路|22号|04
    7 宝安区|沙井街道|共和|福和路|西七巷|73号
    8 宝安区|观澜街道|大水田|居民小组|F21栋
    9 福田区|石厦|北八街|2号

    Table 6.  Examples of Correct Segmentation Results

    实例 地址数据分词结果 错误原因
    1 南山区|工业|七路|利万家实业有限公司东南边商业楼 “工业七路”是正确的地址要素
    2 大工业区|深圳市|出口|加工区|荔景路|11号 应该为“出口加工区”
    3 坪山新区|坪山|办事处|老围老屋|鱼塘|南边 应该为“坪山办事处”
    4 宝安区|沙井街道|新桥村|国道|上南|段景顺加油站 应该为“上南段|景顺加油站”

    Table 7.  Examples of Error Segmentation Results

    根据表 7中错误地址分词结果的统计,主要原因是在集合判断中存在特征词的数量比方向(类型)词的数量要高,如特征词“坪山”、“工业”等,这是由于城市的地址集数据的专有特征导致的,也是在地址分词研究中不可回避的现象,这将是在分词研究中需要解决的问题。

    按照决策树模型对实验数据进行地址分词之后得到城市行政区、主干街道(道路)、居民小区(自然村)和门牌号等地址要素的集合,按照树形的数据结构组织形成城市地址信息树,地址树的节点表示地址要素,按照树的深度遍历对表达的空间位置点或空间范围逐渐精细和准确,地址树在总体上由上至下表示城市的行政区、街道、社区、房屋和门牌号信息,能够运用于地址编码和地址匹配的过程中。

    地址分词在对地址集中每条地址数据进行切分的同时,也为地址要素的统计提供了支撑。深圳市建筑物地址普查数据中以“村”为后缀的地址要素共计186 383个,居民区的“小区、社区、公园、花园和广场”等地址要素,共计57 346个。由于这些地址要素在空间上的表达实际多为面状区域,区域内仍包含着众多其他地址要素,在地址集中还表现为有很多其他地址要素的描述来接续“村”、“小区、社区、公园、花园和广场”的地址数据,用这些为后缀词的地址要素去重后的数目分别为1 946个和842个,如图 9所示。前者为标准地址中可以解析的反映官方地名和地址的分布;后者为当前居民日常使用的名字,它们通常不在官方地名词典中,通过本方法将深圳市建筑物地址进行分词,有效地补充了官方地名词典中的名称和地址。

    Figure 9.  Distribution Map of Shenzhen City Address Elements

  • 本文不依赖城市地址词典和正确的分词结果样本进行地址分词,从实验数据本身出发,分析地址要素在地址集的特征,确定地址数据中的后缀点和落差点,根据两者之间的优缺点形成互补关系,组合判断构建地址决策树模型实现递归的地址分词过程;以深圳市建筑物地址数据进行实验和验证,地址分词结果的正确度达到预期值,有效用于构建城市地址信息树。另外不依赖地址词典和知识库,无监督的学习方式能够支持多数城市的地址分词,具备较强的普适性,基于决策树的地址分词模型较好地针对大规模地名地址数据集提取地址要素,将地址大数据服务于地址匹配和空间语义关联当中,有效地补充了政府的地名词典。

Reference (18)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return