本文提出的快递地址自动分类方法以基于概率统计的地址分类模型为核心，该地址分类模型的基本思想是根据快递地址中所有最小地址要素对应取送点的概率分布情况，综合评价出该快递地址对应各个取送点的可能性，最终对快递地址应分类到的取送点做出判别。在模型的训练阶段，以人工标记出取送点分类结果的快递地址作为训练数据，首先过滤训练数据中的停用字符，然后对快递地址进行分词得到其包含的最小地址要素，最后统计出最小地址要素对应取送点的频率分布及概率分布，并计算最小地址要素的区分度系数d。基于概率统计分类模型进行快递地址分类时，首先过滤待分类地址中的停用字符，然后对地址进行分词得到其包含的最小地址要素，最后由基于概率统计的地址分类模型判断出待分类地址所属的取送点，完成快递地址的自动分类。

快递网络中的中转点和取送点以不同大小的地域范围为服务对象，各级中转点以各级中心城市为基本单位，取送点以各中心城市辐射的周边市、县、中心城市内的社区为基本单位。中文地址采用地域范围由大到小的层级嵌套方式书写，地址中不同地域范围大小的地名在取送点分类时提供的信息量是不同的。以北京市地址和快递取送点的分布情况为例，北京中转点下辖几十个取送点，分布在北京市各个区、县、社区内。“北京市”、“海淀区”、“朝阳区”这类地域范围广阔的地名，其所指代地域范围内的取送点数量众多，对取送点的分类判断帮助不大。详细的楼(门)牌号地名，如“9号楼”、“A座”、“204室”，其所指代的地域范围远小于取送点的基本服务单位，在取送点的分类判别时也不需要关注这类地名。在快递地址的分类判别中，将这2类地域范围过大和过小的地名定义为停用字符，从地址中过滤清除出去。物流地址中的特殊字符，如括号、空格、破折号等，对取送点的分类判别也没有任何指导意义，也定义为停用字符，在地址中予以过滤清除。

中文地址采用连续字符串的形式书写，词与词之间没有明确的分隔符。在地理地址编码领域，中文地址的分词是近年来的研究热点之一。中文地址分词，是将一个中文地址文本拆分为多个最小地址要素[9]的过程。最小地址要素是不可继续拆分的地址要素，具有最小的地址意义。如对中文地址“北京市海淀区西土城路10号北京邮电大学”进行分词，可以拆分出“北京市”、“海淀区”、“西土城路”、“10号”、“北京邮电大学”5个最小地址要素。依据利用信息的不同，目前的中文地址分词方法主要有2种：基于地名词典的方法[1011]和基于地址特征字的方法[12]。基于地址词典的方法维护一个尽可能完备的地名词典，通过串匹配技术在地名词典中查找最小地址要素进行分词，主要采用最大正向匹配方式和最大逆向匹配方式。基于地名词典的方法准确率完全依赖地名词典的完备性，但实际操作中地名词典的更新维护存在很大难度，地名词典的完备性难以保障。各类最小地址要素包含一些相同的字符串作为后缀，这样的后缀字符段称为地址特征字或地址通名，如“北京市”中的“市”、“海淀区”中的“区”就都是地址特征字。基于地址特征字的方法为各类最小地址要素定义特征字并制定相应的拆分规则，通过对特征字和拆分规则的匹配完成对地址的分词。这类方法摆脱了对地名词典的依赖，但特征字和拆分规则的合理选择存在一定难度。本文采用地名词典和特征字相结合的方式对中文地址进行分词。采用某物流公司提供的北京市地名词典作为中文分词的地名词典，该词典共计包括10151个北京市地名。本文依据国家测绘局颁布的《数字城市地理空间信息公共平台地名/地址分类、描述及编码规定(CH/Z90022007)》[13]中对最小地址要素的分类方法，将最小地址要素划分为行政区划地名、小区名、街巷名、标志物名、兴趣点名、门(楼)址6个大类。中文地址表示为字符串T=t1t2…tn，n为字符串T的长度。地名词典表示为字符串集合Pd={p1,p2,…,pr}，特征字词典表示为字符串集合Pf={p1,p2,…,pm}。中文地址分词后得到的是一组最小地址要素，表示为字符串集合Pr，Pr初始状态为空集。本文采用的地名字典与特征字结合的中文地址分词方法步骤如下：步步步骤骤骤1如果字符串T为空，转到步骤3；否则，查找T的前缀能否匹配地名词典Pd中的元素，如果匹配成功，即存在(1,2,,)idp∈Pi=r，使t1,t2,…,tk=pi，其中，k为pi的长度，则将t1,t2,…,tk放入Pr，并将T置为tk+1,tk+2,…,tn，转到步骤1；如果匹配失败，转到步骤2。步步步骤骤骤2查找T的子串能否匹配特征字词典Pf中的元素，如果匹配成功，即存在(1,2,,)ifp∈Pi=m，使tj,tj+1,…,tj+k1=pi，其中k为pi的长度，则将t1,t2,…,tj+k+1放入Pr，并将T置为tj+k,tj+k+1,…,tn，转到步骤1；如果不存在，则将则将T放入Pr，转到步骤3。步步步骤骤骤3返回Pr，算法结束。

基于概率统计的地址分类模型以人工标记出所属取送点的快递地址作为训练数据。随机选取5条训练数作为示例，说明该模型的训练方法，随机选取的示例训练数据如表2所示。首先以2.1节和2.2节介绍的方法过滤掉快递地址中的停用字符并对地址进行分词，每条标记数据得出一组最小地址要素及其对应的取送点，结果如表3所示。例如“朝阳区建国路乙118号京汇大厦三层人事部”这个快递地址，过滤停用字符并地址分词后，得到最小地址要素集合{建国路,京汇大厦}，这组最小地址要素对应的取送点为990060。然后，统计出最小地址要素对应各取送点的总次数，得出每个最小地址要素对应到各取送点的频率分布情况，结果如表4所示。在示例标记数据中，“建国路”这个最小地址要素对应取送点990060的总次数为3，对应取送点990030的总次数为2。训练数据中所有快递地址提取出的最小地址要素总数为m，取送点的总数为n，那么最小地址要素对应到各取送点的频率分布情况可以用一个m×n的矩阵F表示，F中第i行第j列元素fij为最小地址要素i对应取送点j的总次数。同时，统计出每个最小地址要素对应到的取送点的总数，本文将其称为最小地址要素的区分度系数d。根据示例训练数据求得的最小地址要素对应取送点的概率分布和区分度系数分别如表5、表6所示。“建国路”对应取送点990060的概率=3/(3+2)=0.6，对应取送点990030的概率=2/(3+2)=0.4。由于“建国路”既对应取送点990060，也对应取送点990030，因此它的区分度系数d=2。至此，基于概率统计的地址分类模型训练完成。2.4地地地址址址的的的分分分类类类方方方法法法应用基于概率统计的地址分类模型对快递地址进行分类时，先过滤掉待分类快递地址中的停用字符并对其进行地址分词，得到一组最小地址要素，表示为字符串集合Pr={p1,p2,…,pk}，k为最小地址要素的总数。

本节通过实验对本文提出的基于概率统计分类模型的快递地址自动分类方法进行性能评估，选取训练用时、分类用时、准确率和拒绝率作为评价指标。其中，本文对地址自动分类的准确率和拒绝率的定义如下：拒绝率=无法分类的地址总数/待分类地址总数准确率=正确分类的地址总数/(待分类地址总数无法分类的地址总数)

本文选取某快递公司提供的已人工标记取送点分类结果的北京地区快递地址作为实验数据，从中随机选取63535条作为训练数据，2000条作为测试数据。通过本文提出的基于概率统计分类模型的快递地址自动分类方法对2000条测试数据完成自动分类后，将自动分类结果与原始的人工标记结果进行对比，对本文提出的快递地址自动分类方法的性能做出评价。实验的软硬件环境如下：CPU：IntelCorei52400，3.10GHz，双核；内存：4.0GB；Cache：一级数据缓存128KB，一级指令缓存128KB，二级缓存1MB；操作系统：Windows7专业版，32位；编译平台：VisualStudio2010；编程语言：C++。3.2实实实验验验结结结果果果与与与分分分析析析本文测试了应用基于概率统计的地址分类模型进行快递地址自动分类的效果，测试结果如表7和图2所示，由测试结果可以看出：(1)基于概率统计的地址分类模型的训练速度快，对快递地址进行自动分类的分类用时短。采用63535条数据对模型进行训练的平均训练用时约为5.19s，对2000条待分类地址的分类用时平均约为0.85s，分类速度达到每条0.43ms。(2)置信阈值S(定义详见2.4节)决定了地址自动分类的准确率和拒绝率。S值越大，地址自动分类的准确率越高，拒绝率也越高；反之，S值越小，地址自动分类的准确率越低，拒绝率也会相应越低。应用本文提出的快递地址自动分类方法时，应根据实际的应用需求选择合适的S值，在自动分类的准确率和效率间合理权衡。(3)置信阈值S为0.75时地址自动分类的准确率为99%，拒绝率为9.3%，可以满足大多数应用场合的需求。

随着互联网技术特别是移动互联网技术的进一步普及，我国的电子商务产业规模将进一步扩大。作为电子商务的支撑行业，快递行业必然迎来新的机遇和挑战。本文介绍的基于概率统计分类模型的快递地址自动分类方法可以快速、准确地对快递地址所属的取送点做出分类判别，提高包裹分拣中的自动化程度，加快分拣速度，降低人力和包裹存储的成本。本文的快递地址自动分类方法以基于概率统计的地址分类模型为核心，通过统计出的最小地址要素与取送点的概率分布关系对快递地址进行分类。该方法适应性强，对人工标记的训练数据规模要求低，几万条训练数据就可以满足模型训练的要求。因此，即使运营时间较短、人工分拣的快递地址历史数据较少的快递公司也能应用本文的方法。本文的研究工作针对北京地区的快递分拣配送数据，在下一步的工作中将继续扩充训练数据集，扩大概率统计分类模型的适用范围。

作者：邵妍单位：北京邮电大学计算机学院