基于相似性搜索的水利普查數(shù)據(jù)融合

王繼民 ，徐 波 ，朱躍龍 ，汪衛(wèi)軍 ，李士進(jìn) ，萬定生

（1. 河海大學(xué)計(jì)算機(jī)與信息學(xué)院，江蘇 南京 210098；2. 水利部發(fā)展研究中心，北京 100038；3. 南京市社會保險管理中心，江蘇 南京 210017）

0 引言

第一次全國水利普查主要查清了中華人民共和國境內(nèi)（未含香港、澳門特別行政區(qū)和臺灣地區(qū)）的河流湖泊、水利工程、經(jīng)濟(jì)社會用水、河流湖泊治理保護(hù)、水土保持、水利行業(yè)能力建設(shè)、灌區(qū)及地下水等 8 大項(xiàng)基礎(chǔ)信息，為加強(qiáng)水利基礎(chǔ)設(shè)施建設(shè)與管理、實(shí)行最嚴(yán)格的水資源管理制度提供了科學(xué)權(quán)威的數(shù)據(jù)支撐。

水利單位是結(jié)合水利工程設(shè)施特性與行業(yè)發(fā)展規(guī)模等各類管理信息，分析水利單位與水利工程設(shè)施、資產(chǎn)、從業(yè)人員等發(fā)展?fàn)顩r的關(guān)鍵節(jié)點(diǎn)。因此，厘清水利單位，通過建立水利工程對象的工程管理單位與行業(yè)能力的水利單位之間的匹配關(guān)系，實(shí)現(xiàn)普查水利工程數(shù)據(jù)與行業(yè)能力數(shù)據(jù)融合，對科學(xué)研判水利管理能力和水平具有重要的意義。由于不同專業(yè)普查的填報范圍規(guī)定不同、規(guī)范性要求存在差異，因此部分水利單位普查數(shù)據(jù)存在組織機(jī)構(gòu)代碼不完整、重復(fù)，不同專業(yè)填報的水利單位名稱不能完全一致等問題，同時由于水利普查數(shù)據(jù)量大，直接通過人工方式建立匹配關(guān)系費(fèi)時費(fèi)力。

根據(jù)水利普查中水利單位信息的特點(diǎn)，提出自適應(yīng)編輯距離相似度量，對傳統(tǒng)編輯距離的 3 種操作（插入、刪除和替換），設(shè)置不同權(quán)重，并采用啟發(fā)式學(xué)習(xí)算法確定操作的權(quán)重向量。采用基于自適應(yīng)編輯距離的 k-近鄰搜索進(jìn)行水利單位匹配，實(shí)現(xiàn)水利工程和行業(yè)能力數(shù)據(jù)融合。

1 自適應(yīng)編輯距離

1.1 相關(guān)工作

水利普查數(shù)據(jù)中，不同來源的水利單位的相似匹配技術(shù)，主要通過單位名稱進(jìn)行相似查詢，核心在于字符串的相似度量技術(shù)，目的是在字符串?dāng)?shù)據(jù)庫中查找與給定字符串相似的字符串，查詢對象是字符串。

設(shè) S 代表全體被查詢中文字符串?dāng)?shù)據(jù)庫，大小為|S| = n，中文字符串 Si∈S，i = 0，1，2，...，n -1；查詢字符串為 Q；ε 代表允許的最大誤差；D ( ) 表示距離度量函數(shù)。按照中文字符串相似性查詢結(jié)果劃分，相似性查詢包括以下 2 種：

1）ε 范圍查詢，給定 ε，在 S 中查詢所有滿足D（Q，Si）≤ ε 的相似字符串 Si（0 ≤ i ≤ n-1），或者子字符串（結(jié)果包括字符串序號 i 及子串的偏移位置）；

2）k -近鄰查詢，在 S 中查詢和 Q 最相似的前k 個字符串或子字符串（結(jié)果包括字符串序號 i 及子串的偏移位置）。

按照查詢方式，相似性查詢包括：

1）全字符串查詢，查詢字符串和被查詢字符串進(jìn)行整體匹配，判斷是否相似；

2）子字符串查詢，在較長的字符串中，找出與查詢字符串相似的子字符串。

字符串相似性查詢的核心是選擇距離度量函數(shù)及子字符串查詢中的的子字符串匹配方法，目前較具代表性的字符串相似度量有基于相同字詞[1]、編輯距離[2]、向量空間[3]、語義詞典[4]、統(tǒng)計(jì)關(guān)聯(lián)[5]和語義依存[6]等方法。子字符串的匹配方法包括：動態(tài)規(guī)劃、自動機(jī)、位并行和過濾等方法[7]。水利單位匹配關(guān)注的是全字符串的 k-近鄰查詢，即給定查詢字符串 Q，在被查詢字符串集中查詢與 Q 最相似的前k 個字符串，核心是距離度量函數(shù)。

1.2 帶權(quán)重的編輯距離

編輯距離首先由 Levenshtein 提出，假設(shè)有 A 和B 2 個字符串，編輯距離定義為把 A 轉(zhuǎn)換成 B 需要的最少刪除（刪除 A 中 1 個字符）、插入（在 A 中插入1 個字符）或替換（把 A 中某個字符替換成另一個字符）的次數(shù)。2 個字符串互相轉(zhuǎn)換需要經(jīng)過的步驟越多，編輯距離就越遠(yuǎn)，編輯距離的計(jì)算通常采用二維矩陣動態(tài)規(guī)劃的方法。文獻(xiàn) [8]針對中西文混合字符串，采用了將漢字作為西文字符的等價單位計(jì)算編輯距離的方法，并從輸入法的角度提出采用拼音和五筆編碼計(jì)算編輯距離的方法，最后給出融合3 種編輯距離計(jì)算字符串相似度的算法。文獻(xiàn) [9]采用不同的帶權(quán)重編輯距離實(shí)現(xiàn)中文組織機(jī)構(gòu)簡稱和全名的匹配。

在原始編輯距離計(jì)算中，刪除、插入和替換3 種操作的權(quán)重完全相同，然而，由于中文表述的特殊性，在組織機(jī)構(gòu)名稱中插入或者刪除字詞，有時候不會對名稱的含義產(chǎn)生影響，而替換字詞則可能會完全改變原字符串的含義。因此，可以對不同操作設(shè)定不同權(quán)重，以更加準(zhǔn)確地度量字符串間的距離。實(shí)驗(yàn)表明，重新設(shè)定操作的權(quán)重可以在很大程度上提高編輯距離對水利單位匹配處理的適應(yīng)性。表1 和 2 顯示了在權(quán)重向量 ，分別取 <1.0, 1.0, 1.0> 和 <0.1, 0.1, 1.0> 下計(jì)算“竹鎮(zhèn)水利管理站”與“竹鎮(zhèn)鎮(zhèn)水利管理工作站”和“龍楊鎮(zhèn)水利管理站”2 個水利單位名稱的編輯距離。權(quán)重向量 <1.0, 1.0, 1.0> 下，“竹鎮(zhèn)水利管理站”與“竹鎮(zhèn)鎮(zhèn)水利管理工作站”之間的編輯距離 3 大于其與“龍楊鎮(zhèn)水利管理站”之間的編輯距離 2；權(quán)重向量 <0.1, 0.1, 1.0> 下，“竹鎮(zhèn)水利管理站”與“竹鎮(zhèn)鎮(zhèn)水利管理工作站”之間的編輯距離 0.3 遠(yuǎn)遠(yuǎn)小于其與“龍楊鎮(zhèn)水利管理站”之間的編輯距離 1.1，判斷出“竹鎮(zhèn)水利管理站”與“竹鎮(zhèn)鎮(zhèn)水利管理工作站”更為相近，因此可以看出，對編輯操作的權(quán)重進(jìn)行有方向的調(diào)整可以提高相似性判斷的正確率。

1.3 啟發(fā)式權(quán)重學(xué)習(xí)

不同數(shù)據(jù)集可能對編輯距離的 3 種操作具有不同的敏感性，因此，需要針對不同的數(shù)據(jù)集，動態(tài)調(diào)整編輯操作的權(quán)重以滿足不同特征數(shù)據(jù)集的實(shí)際應(yīng)用。

本文給出一種基于 k-近鄰算法[10]的啟發(fā)式權(quán)重學(xué)習(xí)算法。訓(xùn)練集包含訓(xùn)練查詢集 T1和訓(xùn)練數(shù)據(jù)集T22 個字符串集。T1中每個字符串都和 T2中的唯一字符串匹配，并且已進(jìn)行標(biāo)記，若將 T2中的每個字符串視為一類標(biāo)記，則基于數(shù)據(jù)挖掘中分類思想，可以認(rèn)為 T1中的每個中文字符串所屬類知。本文采用“留一法”[11]基于帶權(quán)重的編輯距離和 k-近鄰算法在 T2中搜索 T1字符串的最相似串，并以該最相似串作為匹配的串，計(jì)算整體的匹配錯誤率。不同的編輯操作權(quán)重向量計(jì)算得到的匹配錯誤率可能是不同的，對應(yīng)錯誤率最低的權(quán)重向量將作為當(dāng)前數(shù)據(jù)集的最優(yōu)權(quán)重向量。

權(quán)重調(diào)整的策略為，將間隔 [0, 1]分割成 k 個等間距的子間隔，使用 <0, 0, 0> 作為權(quán)重向量起點(diǎn)進(jìn)行匹配，逐步使用相鄰的更大的權(quán)重替代，使用訓(xùn)練數(shù)據(jù)集的匹配錯誤率作為權(quán)重評估函數(shù)。在一些情況下，該方法可能產(chǎn)生冗余的權(quán)重向量。例如，假設(shè) k =10，權(quán)重向量 <0.1, 0.1, 0.1> 和 <0.5, 0.5,0.5> 將產(chǎn)生相同的匹配錯誤率。因此，約定權(quán)重向量中各分量的和必須為 1，算法針對權(quán)重向量中的每個分量逐步從 0 按照 1/k 的步長遞增到 1，并且只有各分量和為 1 的權(quán)重向量才用于評估匹配錯誤率。搜索最優(yōu)編輯操作權(quán)重向量的過程如算法 1 所示。

算法 1. 尋找能夠使字符串匹配性能最優(yōu)的編輯操作權(quán)重向量

Algorithm 1. Searches for the weights that maximize the matching performance

參數(shù)：S 為訓(xùn)練字符串集，包括 T1和 T22 部分；

表1 傳統(tǒng)編輯距離計(jì)算示例

表2 調(diào)整的編輯權(quán)重向量下編輯距離計(jì)算示例

d 為權(quán)重向量變化的步長（1/k）。

返回值：P 為最優(yōu)的權(quán)重向量。

se ← sd ← ∞ {se 為最小的錯誤率，sd 為最優(yōu)權(quán)重向量下查詢字符串距離匹配字符串的平均編輯距離。}

while (i >= 0) ∧ (w[i]+ d > 1) {判斷是否還有分量可以增加}

在算法 1 中，假設(shè) d = 0.5，即 k = 2，算法將產(chǎn)生如表3 所示的權(quán)重向量，并使用 evaluate_error函數(shù)評估每個權(quán)重向量對應(yīng)的匹配錯誤率；evaluate_distance 函數(shù)計(jì)算查詢字符串到最近鄰的平均編輯距離 dist，在匹配錯誤率相同時，算法優(yōu)先選擇最小平均距離對應(yīng)的權(quán)重向量。

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)及方法

為了驗(yàn)證自適應(yīng)編輯距離算法，進(jìn)行了相關(guān)實(shí)驗(yàn)。數(shù)據(jù)來自第一次全國水利普查，選擇 2 個省的部分市級水利普查數(shù)據(jù)中水利工程的管理單位信息，去掉未填記錄，通過利用組織機(jī)構(gòu)代碼、原始編輯距離進(jìn)行相似及人工匹配的方式，建立水利工程管理單位信息項(xiàng)和行業(yè)能力單位的匹配，并從匹配后的記錄中各隨機(jī)選擇 2000 條記錄用于實(shí)驗(yàn)。由于各省獨(dú)立開展普查工作，因此數(shù)據(jù)具有獨(dú)立性。實(shí)驗(yàn)中，針對每個省，以 500 條為步長，隨機(jī)選擇記錄作為每步的實(shí)驗(yàn)數(shù)據(jù)，選擇測試數(shù)據(jù)的 30% 作為訓(xùn)練數(shù)據(jù)，計(jì)算最優(yōu)權(quán)重向量，剩余 70% 作為測試數(shù)據(jù)，計(jì)算匹配準(zhǔn)確率。

表3 算法 1 產(chǎn)生的有效權(quán)重向量（k = 2）

2.2 實(shí)驗(yàn)結(jié)果

圖1 顯示隨著選擇的樣本數(shù)據(jù)的變化，基于原始和自適應(yīng)編輯距離的匹配準(zhǔn)確率的變化情況?；谠季庉嬀嚯x直接匹配算法，在數(shù)據(jù)量較小時，匹配準(zhǔn)確率較高，但是隨著數(shù)據(jù)量的增加，準(zhǔn)確率降低；基于自適應(yīng)編輯距離算法的匹配方法，匹配準(zhǔn)確率可以達(dá)到 80%～85% 之間，由于水利普查數(shù)據(jù)的數(shù)據(jù)量巨大，采用此算法進(jìn)行水利工程和行業(yè)能力數(shù)據(jù)融合可以大大提高工作效率。

3 水利普查數(shù)據(jù)融合

3.1 水利普查數(shù)據(jù)融合框架

圖1 匹配準(zhǔn)確率分析

數(shù)據(jù)融合就是利用計(jì)算機(jī)技術(shù)將來自多個傳感器或多源的觀測信息進(jìn)行分析、綜合處理，從而得出決策和估計(jì)任務(wù)所需的信息的處理過程。水利工程與行業(yè)能力普查數(shù)據(jù)融合就是通過相似性搜索建立行業(yè)能力普查單位與水利工程管理單位的一致匹配，實(shí)現(xiàn)水利工程和行業(yè)能力普查數(shù)據(jù)的有效銜接，為分析水利發(fā)展現(xiàn)狀，制定水利及經(jīng)濟(jì)社會發(fā)展規(guī)劃等提供支撐。水利工程與行業(yè)能力普查數(shù)據(jù)融合的框架如圖 2 所示。首先對行業(yè)能力普查和水利工程管理單位名稱進(jìn)行分級處理，提取單位名稱中的行政區(qū)劃信息，建立精簡的單位名稱；然后利用啟發(fā)式權(quán)重學(xué)習(xí)得到最優(yōu)的權(quán)重向量；最后利用組織機(jī)構(gòu)代碼和單位名稱進(jìn)行名稱相似搜索，并結(jié)合人工識別，實(shí)現(xiàn)水利單位匹配。

圖2 水利工程與行業(yè)能力數(shù)據(jù)融合框架

3.2 單位名稱分級

單位名稱分級處理是將填報的原始單位名稱分解成圖 3 所示格式。

圖3 單位名稱分解

部分單位名稱包含行政地名信息，如“宿州市埇橋區(qū)解集鄉(xiāng)水利工作站”，包含所在市和區(qū)的信息，由于普查對象是按照“在地原則”填報的，填報的水利單位名稱可能忽略了所在行政地名信息，如寫成“解集水利站”，若直接對兩者進(jìn)行相似性匹配，編輯距離較大，容易造成匹配失敗。提取單位名稱中的行政地名信息，構(gòu)建分級單位名稱，縮小匹配范圍將有助于提高匹配的正確率。如，將“宿州市埇橋區(qū)解集鄉(xiāng)水利工作站”分解成“江蘇省”+“宿州市”+“埇橋區(qū)”+“解集鄉(xiāng)水利工作站”，在相同省市縣區(qū)域內(nèi)利用“解集水利站”和“解集鄉(xiāng)水利工作站”進(jìn)行字符串相似性查詢，得到的編輯距離變小，容易得到正確的結(jié)果。

提取行政區(qū)劃信息時，按照從左到右的順序逐一加字成詞的方法，如針對“江蘇省南京市”，先取“江”字在行政區(qū)劃數(shù)據(jù)庫中比較核對，若是未登錄行政區(qū)劃，則依次加 1 個字并進(jìn)行比對，即核查“江蘇”是否為已登錄行政區(qū)劃，若為，則判定其為 1 個地名，否則，繼續(xù)逐一加字進(jìn)行匹配核查，直到超出最大長度。若碰見“省”、“自治區(qū)”、“市”、“州”、“區(qū)”、“縣”、“旗”等地名“后綴詞”，則將此后綴詞歸為緊挨著前面的地名，將核查出的行政區(qū)劃名從單位名稱中去除，在剩余部分中繼續(xù)提取下級行政區(qū)劃名，最低只提取到縣級。

部分單位名稱不包含行政區(qū)劃信息，如“黃河水利委員會”，還有些單位名稱由于進(jìn)行了簡寫，無法解析出分級行政區(qū)劃，這些單位名稱可直接保留其原始填報名稱，稱為非精簡單位名稱。

3.3 啟發(fā)式編輯距離權(quán)重學(xué)習(xí)

選擇部分水利普查數(shù)據(jù)（如 1 個?。┳鳛闄?quán)重學(xué)習(xí)數(shù)據(jù)，對水利單位名稱進(jìn)行分級處理，編輯操作權(quán)重向量設(shè)定為<1.0, 1.0, 1.0>，按照圖 2 中“單位名稱匹配”的流程完成水利單位匹配，最后，將成功匹配的水利單位名稱作為權(quán)重學(xué)習(xí)樣本，基于算法 1 進(jìn)行權(quán)重學(xué)習(xí)。

3.4 單位名稱相似搜索及匹配

經(jīng)過分級處理的單位名稱包括精簡和非精簡單位名稱 2 種，根據(jù)普查的“在地原則”，名稱包含行政區(qū)劃信息的單位一般在其名稱所包含的行政區(qū)劃內(nèi)填報，而名稱不包含行政區(qū)劃信息的單位則無法根據(jù)名稱確定其填報的行政區(qū)劃，因此針對 2 種不同的單位名稱可以采用不同的處理流程。在單位名稱 k-近鄰查詢中，水利工程管理單位名稱組成查詢字符串集 Q，行業(yè)能力普查單位名稱組成查詢字符串集 S。進(jìn)行單位名稱匹配時，優(yōu)先利用組織機(jī)構(gòu)代碼進(jìn)行匹配，然后采用單位名稱匹配。

首先利用組織機(jī)構(gòu)代碼進(jìn)行精確匹配，將匹配失敗，或組織機(jī)構(gòu)代碼未填的單位，利用單位名稱，采用相似性搜索進(jìn)行匹配；針對精簡管理單位名稱，到 S 中提取與管理單位在同一行政區(qū)劃內(nèi)的普查單位名稱作為被查詢子集，在子集中進(jìn)行字符串的 k-近鄰查詢，結(jié)合人工識別匹配的單位；針對非精簡的管理單位名稱，無法判斷填報的行政區(qū)劃，直接將 S 作為被查詢集進(jìn)行 k-近鄰查詢，結(jié)合人工識別匹配的單位名稱。為了提高匹配的準(zhǔn)確性，可以先以水利工程所在的省或市行政區(qū)劃內(nèi)的行業(yè)能力普查單位名作為被查詢子集進(jìn)行單位名匹配，若匹配失敗，則使用全國的行業(yè)能力普查單位名進(jìn)行匹配。

4 結(jié)語

實(shí)驗(yàn)證明，對編輯距離的各操作設(shè)置不同的權(quán)重，可以更加準(zhǔn)確地實(shí)現(xiàn)字符串的相似性匹配。提出的自適應(yīng)編輯距離，采用啟發(fā)式權(quán)重學(xué)習(xí)方法，獲得面向具體數(shù)據(jù)集的最優(yōu)操作權(quán)重向量，并給出基于自適應(yīng)編輯距離相似性查詢的第一次全國水利普查數(shù)據(jù)融合的處理流程，啟發(fā)式權(quán)重學(xué)習(xí)和評價采用有監(jiān)督學(xué)習(xí)策略，進(jìn)一步的工作將研究基于半監(jiān)督和無監(jiān)督的權(quán)重學(xué)習(xí)和評價方法，提高自適應(yīng)編輯距離適用性。

[1]Nirenburg S, Domashnev C, Grannes D J. Two approaches of matching in example-based machine translation[C]//Proceedings of the 5th International Conference on Theoretical and Methodological Issues in Machine Translation (TMI-93),.1993: 47-57.

[2]Ristad E S, Yianilos P N. Learing string-edit distance[J].IEEE PAMI, 1998, 20 (5): 522-532.

[3]Salton G, Wong A, Yang Chungshu. A vector space model for automatic indexing[J]. Communications of the ACM,1995,18 (11): 613-620.

[4]LI Sujian, ZHANG Jian, HUANG Xiong, et al. Semantic computation in Chinese question-answering system [J]. J.Comput. Sci. & Technol, 2002, 17 (6): 933-939.

[5]Chatterjee N. A statistical approach for similarity measurement between sentences for EBMT[C]//Proceedings of Symposium on Translation Support System. Washington:IEEE Computer Society, 1999: 15-17.

[6]李彬，劉挺，秦兵，等. 基于語義依存的漢語句子相似度計(jì)算[J]. 計(jì)算機(jī)應(yīng)用研究，2003, 20 (12): 15-17.

[7]范立新. 改進(jìn)的中文近似字符串匹配算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2006, 42 (34): 172-174.

[8]黃林晟，鄧志鴻，唐世渭，等. 基于編輯距離的中文組織機(jī)構(gòu)名簡稱－全稱匹配算法[J]. 山東大學(xué)學(xué)報：理學(xué)版，2012, 47 (5): 43-48.

[9]刁興春，譚明超，曹建軍. 一種融合多種編輯距離的字符串相似度計(jì)算方法[J]. 計(jì)算機(jī)應(yīng)用研究，2010, 27 (12):4523-4527.

[10]F.Fábris, I.Drago, F.M.Varej?o. A multi-measure nearest neighbor algorithm for time series classification[C]//Proceedings of the 11th Ibero-American Conference on AI(IBERAMIA '08). Berlin:Springer-Verlag, 2008: 153-162.

[11]Evgeniou T, Pontil M, Elisseeff A. Leave one out error,stability, and generalization of voting combinations of classifiers[J]. Machine Learning, 2004, 55(1): 71-97.