概率統計的地址分類辦法探索

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

本文提出的快遞地址自動分類方法以基于概率統計的地址分類模型為核心，該地址分類模型的基本思想是根據快遞地址中所有最小地址要素對應取送點的概率分布情況，綜合評價出該快遞地址對應各個取送點的可能性，最終對快遞地址應分類到的取送點做出判別。在模型的訓練階段，以人工標記出取送點分類結果的快遞地址作為訓練數據，首先過濾訓練數據中的停用字符，然后對快遞地址進行分詞得到其包含的最小地址要素，最后統計出最小地址要素對應取送點的頻率分布及概率分布，并計算最小地址要素的區分度系數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%，可以滿足大多數應用場合的需求。

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

作者：邵妍單位：北京郵電大學計算機學院