概率統(tǒng)計(jì)的地址分類辦法探索

前言：本站為你精心整理了概率統(tǒng)計(jì)的地址分類辦法探索范文，希望能為你的創(chuàng)作提供參考價(jià)值，我們的客服老師可以幫助你提供個(gè)性化的參考范文，歡迎咨詢。

本文提出的快遞地址自動(dòng)分類方法以基于概率統(tǒng)計(jì)的地址分類模型為核心，該地址分類模型的基本思想是根據(jù)快遞地址中所有最小地址要素對(duì)應(yīng)取送點(diǎn)的概率分布情況，綜合評(píng)價(jià)出該快遞地址對(duì)應(yīng)各個(gè)取送點(diǎn)的可能性，最終對(duì)快遞地址應(yīng)分類到的取送點(diǎn)做出判別。在模型的訓(xùn)練階段，以人工標(biāo)記出取送點(diǎn)分類結(jié)果的快遞地址作為訓(xùn)練數(shù)據(jù)，首先過(guò)濾訓(xùn)練數(shù)據(jù)中的停用字符，然后對(duì)快遞地址進(jìn)行分詞得到其包含的最小地址要素，最后統(tǒng)計(jì)出最小地址要素對(duì)應(yīng)取送點(diǎn)的頻率分布及概率分布，并計(jì)算最小地址要素的區(qū)分度系數(shù)d?；诟怕式y(tǒng)計(jì)分類模型進(jìn)行快遞地址分類時(shí)，首先過(guò)濾待分類地址中的停用字符，然后對(duì)地址進(jìn)行分詞得到其包含的最小地址要素，最后由基于概率統(tǒng)計(jì)的地址分類模型判斷出待分類地址所屬的取送點(diǎn)，完成快遞地址的自動(dòng)分類。

快遞網(wǎng)絡(luò)中的中轉(zhuǎn)點(diǎn)和取送點(diǎn)以不同大小的地域范圍為服務(wù)對(duì)象，各級(jí)中轉(zhuǎn)點(diǎn)以各級(jí)中心城市為基本單位，取送點(diǎn)以各中心城市輻射的周邊市、縣、中心城市內(nèi)的社區(qū)為基本單位。中文地址采用地域范圍由大到小的層級(jí)嵌套方式書寫，地址中不同地域范圍大小的地名在取送點(diǎn)分類時(shí)提供的信息量是不同的。以北京市地址和快遞取送點(diǎn)的分布情況為例，北京中轉(zhuǎn)點(diǎn)下轄?zhēng)资畟€(gè)取送點(diǎn)，分布在北京市各個(gè)區(qū)、縣、社區(qū)內(nèi)?！氨本┦小?、“海淀區(qū)”、“朝陽(yáng)區(qū)”這類地域范圍廣闊的地名，其所指代地域范圍內(nèi)的取送點(diǎn)數(shù)量眾多，對(duì)取送點(diǎn)的分類判斷幫助不大。詳細(xì)的樓(門)牌號(hào)地名，如“9號(hào)樓”、“A座”、“204室”，其所指代的地域范圍遠(yuǎn)小于取送點(diǎn)的基本服務(wù)單位，在取送點(diǎn)的分類判別時(shí)也不需要關(guān)注這類地名。在快遞地址的分類判別中，將這2類地域范圍過(guò)大和過(guò)小的地名定義為停用字符，從地址中過(guò)濾清除出去。物流地址中的特殊字符，如括號(hào)、空格、破折號(hào)等，對(duì)取送點(diǎn)的分類判別也沒(méi)有任何指導(dǎo)意義，也定義為停用字符，在地址中予以過(guò)濾清除。

中文地址采用連續(xù)字符串的形式書寫，詞與詞之間沒(méi)有明確的分隔符。在地理地址編碼領(lǐng)域，中文地址的分詞是近年來(lái)的研究熱點(diǎn)之一。中文地址分詞，是將一個(gè)中文地址文本拆分為多個(gè)最小地址要素[9]的過(guò)程。最小地址要素是不可繼續(xù)拆分的地址要素，具有最小的地址意義。如對(duì)中文地址“北京市海淀區(qū)西土城路10號(hào)北京郵電大學(xué)”進(jìn)行分詞，可以拆分出“北京市”、“海淀區(qū)”、“西土城路”、“10號(hào)”、“北京郵電大學(xué)”5個(gè)最小地址要素。依據(jù)利用信息的不同，目前的中文地址分詞方法主要有2種：基于地名詞典的方法[1011]和基于地址特征字的方法[12]?；诘刂吩~典的方法維護(hù)一個(gè)盡可能完備的地名詞典，通過(guò)串匹配技術(shù)在地名詞典中查找最小地址要素進(jìn)行分詞，主要采用最大正向匹配方式和最大逆向匹配方式?；诘孛~典的方法準(zhǔn)確率完全依賴地名詞典的完備性，但實(shí)際操作中地名詞典的更新維護(hù)存在很大難度，地名詞典的完備性難以保障。各類最小地址要素包含一些相同的字符串作為后綴，這樣的后綴字符段稱為地址特征字或地址通名，如“北京市”中的“市”、“海淀區(qū)”中的“區(qū)”就都是地址特征字?；诘刂诽卣髯值姆椒楦黝愖钚〉刂芬囟x特征字并制定相應(yīng)的拆分規(guī)則，通過(guò)對(duì)特征字和拆分規(guī)則的匹配完成對(duì)地址的分詞。這類方法擺脫了對(duì)地名詞典的依賴，但特征字和拆分規(guī)則的合理選擇存在一定難度。本文采用地名詞典和特征字相結(jié)合的方式對(duì)中文地址進(jìn)行分詞。采用某物流公司提供的北京市地名詞典作為中文分詞的地名詞典，該詞典共計(jì)包括10151個(gè)北京市地名。本文依據(jù)國(guó)家測(cè)繪局頒布的《數(shù)字城市地理空間信息公共平臺(tái)地名/地址分類、描述及編碼規(guī)定(CH/Z90022007)》[13]中對(duì)最小地址要素的分類方法，將最小地址要素劃分為行政區(qū)劃地名、小區(qū)名、街巷名、標(biāo)志物名、興趣點(diǎn)名、門(樓)址6個(gè)大類。中文地址表示為字符串T=t1t2…tn，n為字符串T的長(zhǎng)度。地名詞典表示為字符串集合Pd={p1,p2,…,pr}，特征字詞典表示為字符串集合Pf={p1,p2,…,pm}。中文地址分詞后得到的是一組最小地址要素，表示為字符串集合Pr，Pr初始狀態(tài)為空集。本文采用的地名字典與特征字結(jié)合的中文地址分詞方法步驟如下：步步步驟驟驟1如果字符串T為空，轉(zhuǎn)到步驟3；否則，查找T的前綴能否匹配地名詞典Pd中的元素，如果匹配成功，即存在(1,2,,)idp∈Pi=r，使t1,t2,…,tk=pi，其中，k為pi的長(zhǎng)度，則將t1,t2,…,tk放入Pr，并將T置為tk+1,tk+2,…,tn，轉(zhuǎn)到步驟1；如果匹配失敗，轉(zhuǎn)到步驟2。步步步驟驟驟2查找T的子串能否匹配特征字詞典Pf中的元素，如果匹配成功，即存在(1,2,,)ifp∈Pi=m，使tj,tj+1,…,tj+k1=pi，其中k為pi的長(zhǎng)度，則將t1,t2,…,tj+k+1放入Pr，并將T置為tj+k,tj+k+1,…,tn，轉(zhuǎn)到步驟1；如果不存在，則將則將T放入Pr，轉(zhuǎn)到步驟3。步步步驟驟驟3返回Pr，算法結(jié)束。

基于概率統(tǒng)計(jì)的地址分類模型以人工標(biāo)記出所屬取送點(diǎn)的快遞地址作為訓(xùn)練數(shù)據(jù)。隨機(jī)選取5條訓(xùn)練數(shù)作為示例，說(shuō)明該模型的訓(xùn)練方法，隨機(jī)選取的示例訓(xùn)練數(shù)據(jù)如表2所示。首先以2.1節(jié)和2.2節(jié)介紹的方法過(guò)濾掉快遞地址中的停用字符并對(duì)地址進(jìn)行分詞，每條標(biāo)記數(shù)據(jù)得出一組最小地址要素及其對(duì)應(yīng)的取送點(diǎn)，結(jié)果如表3所示。例如“朝陽(yáng)區(qū)建國(guó)路乙118號(hào)京匯大廈三層人事部”這個(gè)快遞地址，過(guò)濾停用字符并地址分詞后，得到最小地址要素集合{建國(guó)路,京匯大廈}，這組最小地址要素對(duì)應(yīng)的取送點(diǎn)為990060。然后，統(tǒng)計(jì)出最小地址要素對(duì)應(yīng)各取送點(diǎn)的總次數(shù)，得出每個(gè)最小地址要素對(duì)應(yīng)到各取送點(diǎn)的頻率分布情況，結(jié)果如表4所示。在示例標(biāo)記數(shù)據(jù)中，“建國(guó)路”這個(gè)最小地址要素對(duì)應(yīng)取送點(diǎn)990060的總次數(shù)為3，對(duì)應(yīng)取送點(diǎn)990030的總次數(shù)為2。訓(xùn)練數(shù)據(jù)中所有快遞地址提取出的最小地址要素總數(shù)為m，取送點(diǎn)的總數(shù)為n，那么最小地址要素對(duì)應(yīng)到各取送點(diǎn)的頻率分布情況可以用一個(gè)m×n的矩陣F表示，F(xiàn)中第i行第j列元素fij為最小地址要素i對(duì)應(yīng)取送點(diǎn)j的總次數(shù)。同時(shí)，統(tǒng)計(jì)出每個(gè)最小地址要素對(duì)應(yīng)到的取送點(diǎn)的總數(shù)，本文將其稱為最小地址要素的區(qū)分度系數(shù)d。根據(jù)示例訓(xùn)練數(shù)據(jù)求得的最小地址要素對(duì)應(yīng)取送點(diǎn)的概率分布和區(qū)分度系數(shù)分別如表5、表6所示?！敖▏?guó)路”對(duì)應(yīng)取送點(diǎn)990060的概率=3/(3+2)=0.6，對(duì)應(yīng)取送點(diǎn)990030的概率=2/(3+2)=0.4。由于“建國(guó)路”既對(duì)應(yīng)取送點(diǎn)990060，也對(duì)應(yīng)取送點(diǎn)990030，因此它的區(qū)分度系數(shù)d=2。至此，基于概率統(tǒng)計(jì)的地址分類模型訓(xùn)練完成。2.4地地地址址址的的的分分分類類類方方方法法法應(yīng)用基于概率統(tǒng)計(jì)的地址分類模型對(duì)快遞地址進(jìn)行分類時(shí)，先過(guò)濾掉待分類快遞地址中的停用字符并對(duì)其進(jìn)行地址分詞，得到一組最小地址要素，表示為字符串集合Pr={p1,p2,…,pk}，k為最小地址要素的總數(shù)。

本節(jié)通過(guò)實(shí)驗(yàn)對(duì)本文提出的基于概率統(tǒng)計(jì)分類模型的快遞地址自動(dòng)分類方法進(jìn)行性能評(píng)估，選取訓(xùn)練用時(shí)、分類用時(shí)、準(zhǔn)確率和拒絕率作為評(píng)價(jià)指標(biāo)。其中，本文對(duì)地址自動(dòng)分類的準(zhǔn)確率和拒絕率的定義如下：拒絕率=無(wú)法分類的地址總數(shù)/待分類地址總數(shù)準(zhǔn)確率=正確分類的地址總數(shù)/(待分類地址總數(shù)無(wú)法分類的地址總數(shù))

本文選取某快遞公司提供的已人工標(biāo)記取送點(diǎn)分類結(jié)果的北京地區(qū)快遞地址作為實(shí)驗(yàn)數(shù)據(jù)，從中隨機(jī)選取63535條作為訓(xùn)練數(shù)據(jù)，2000條作為測(cè)試數(shù)據(jù)。通過(guò)本文提出的基于概率統(tǒng)計(jì)分類模型的快遞地址自動(dòng)分類方法對(duì)2000條測(cè)試數(shù)據(jù)完成自動(dòng)分類后，將自動(dòng)分類結(jié)果與原始的人工標(biāo)記結(jié)果進(jìn)行對(duì)比，對(duì)本文提出的快遞地址自動(dòng)分類方法的性能做出評(píng)價(jià)。實(shí)驗(yàn)的軟硬件環(huán)境如下：CPU：IntelCorei52400，3.10GHz，雙核；內(nèi)存：4.0GB；Cache：一級(jí)數(shù)據(jù)緩存128KB，一級(jí)指令緩存128KB，二級(jí)緩存1MB；操作系統(tǒng)：Windows7專業(yè)版，32位；編譯平臺(tái)：VisualStudio2010；編程語(yǔ)言：C++。3.2實(shí)實(shí)實(shí)驗(yàn)驗(yàn)驗(yàn)結(jié)結(jié)結(jié)果果果與與與分分分析析析本文測(cè)試了應(yīng)用基于概率統(tǒng)計(jì)的地址分類模型進(jìn)行快遞地址自動(dòng)分類的效果，測(cè)試結(jié)果如表7和圖2所示，由測(cè)試結(jié)果可以看出：(1)基于概率統(tǒng)計(jì)的地址分類模型的訓(xùn)練速度快，對(duì)快遞地址進(jìn)行自動(dòng)分類的分類用時(shí)短。采用63535條數(shù)據(jù)對(duì)模型進(jìn)行訓(xùn)練的平均訓(xùn)練用時(shí)約為5.19s，對(duì)2000條待分類地址的分類用時(shí)平均約為0.85s，分類速度達(dá)到每條0.43ms。(2)置信閾值S(定義詳見(jiàn)2.4節(jié))決定了地址自動(dòng)分類的準(zhǔn)確率和拒絕率。S值越大，地址自動(dòng)分類的準(zhǔn)確率越高，拒絕率也越高；反之，S值越小，地址自動(dòng)分類的準(zhǔn)確率越低，拒絕率也會(huì)相應(yīng)越低。應(yīng)用本文提出的快遞地址自動(dòng)分類方法時(shí)，應(yīng)根據(jù)實(shí)際的應(yīng)用需求選擇合適的S值，在自動(dòng)分類的準(zhǔn)確率和效率間合理權(quán)衡。(3)置信閾值S為0.75時(shí)地址自動(dòng)分類的準(zhǔn)確率為99%，拒絕率為9.3%，可以滿足大多數(shù)應(yīng)用場(chǎng)合的需求。

隨著互聯(lián)網(wǎng)技術(shù)特別是移動(dòng)互聯(lián)網(wǎng)技術(shù)的進(jìn)一步普及，我國(guó)的電子商務(wù)產(chǎn)業(yè)規(guī)模將進(jìn)一步擴(kuò)大。作為電子商務(wù)的支撐行業(yè)，快遞行業(yè)必然迎來(lái)新的機(jī)遇和挑戰(zhàn)。本文介紹的基于概率統(tǒng)計(jì)分類模型的快遞地址自動(dòng)分類方法可以快速、準(zhǔn)確地對(duì)快遞地址所屬的取送點(diǎn)做出分類判別，提高包裹分揀中的自動(dòng)化程度，加快分揀速度，降低人力和包裹存儲(chǔ)的成本。本文的快遞地址自動(dòng)分類方法以基于概率統(tǒng)計(jì)的地址分類模型為核心，通過(guò)統(tǒng)計(jì)出的最小地址要素與取送點(diǎn)的概率分布關(guān)系對(duì)快遞地址進(jìn)行分類。該方法適應(yīng)性強(qiáng)，對(duì)人工標(biāo)記的訓(xùn)練數(shù)據(jù)規(guī)模要求低，幾萬(wàn)條訓(xùn)練數(shù)據(jù)就可以滿足模型訓(xùn)練的要求。因此，即使運(yùn)營(yíng)時(shí)間較短、人工分揀的快遞地址歷史數(shù)據(jù)較少的快遞公司也能應(yīng)用本文的方法。本文的研究工作針對(duì)北京地區(qū)的快遞分揀配送數(shù)據(jù)，在下一步的工作中將繼續(xù)擴(kuò)充訓(xùn)練數(shù)據(jù)集，擴(kuò)大概率統(tǒng)計(jì)分類模型的適用范圍。

作者：邵妍單位：北京郵電大學(xué)計(jì)算機(jī)學(xué)院