郭 暉董 源周 鋼

（1.海軍工程大學(xué)電子工程學(xué)院計算機工程系 武漢 430033）（2.海軍水文氣象中心 北京 100000）

1 引言

大數(shù)據(jù)應(yīng)用中由于數(shù)據(jù)來源各異、結(jié)構(gòu)不一，為了提高數(shù)據(jù)分析性能，需要對不一致、不準(zhǔn)確的等臟數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，或?qū)Σ煌瑪?shù)據(jù)源的同一數(shù)據(jù)進(jìn)行數(shù)據(jù)集成［1～2］。字符匹配是指尋找表示實體世界中同一實體的字符串，相互匹配的字符串應(yīng)對具有同義性，可互換［3］。

在中文語言環(huán)境中，對于中文固定名詞，如組織機構(gòu)名等常用簡稱，如“華中科技大學(xué)”簡稱為“華科大”或“華科”，研究同一名詞的“簡稱”和“全稱”兩個字符串的匹配算法，其核心在于字符串相似度的度量方法。

本文針對大數(shù)據(jù)應(yīng)用特點，以中文固定名詞所在數(shù)據(jù)源為基礎(chǔ)，采用基于統(tǒng)計方法，運用數(shù)據(jù)挖掘技術(shù)，提出了基于屬性相關(guān)度的中文簡稱匹配算法，該算法通過對匹配名詞所處屬性的強相關(guān)屬性的數(shù)據(jù)范圍對比相似度，按照中文簡稱和全稱比量設(shè)置置信度，兩者乘積得到匹配度。該算法對大數(shù)據(jù)中保障數(shù)據(jù)質(zhì)量，提高數(shù)據(jù)分析性能具有重要意義。

2 問題背景

中文語言環(huán)境中，對于很多固定名詞，通常會約定俗成的簡短稱謂，即為簡稱。在大數(shù)據(jù)具體應(yīng)用中，由于數(shù)據(jù)采集規(guī)范要求不同，數(shù)據(jù)來源不一，容易出現(xiàn)同一對象有簡稱和全稱兩種不同表述，在對數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗或?qū)Σ煌瑪?shù)據(jù)源進(jìn)行數(shù)據(jù)集成時，需要對中文固定名詞的“簡稱”和“全稱”字符串進(jìn)行有效匹配，是提高數(shù)據(jù)質(zhì)量的重要途徑。

對中文固定名詞簡稱，通過對中國部分高校簡稱與全稱對比表分析，中文簡稱具有以下特點規(guī)律：一是其長度相對全稱要簡短很多；二是簡稱字符串中所有字符在全稱中均有出現(xiàn)；三是簡稱中基本單個字符，有意義詞極少出現(xiàn)。

對中文固定名詞的“簡稱”和“全稱”進(jìn)行匹配，本質(zhì)就是字符串的相似度計算。目前，較具代表性的算法有基于相同字詞［4］、基于編輯距離［5］、基于向量空間［6］、基于語義詞典［7］、基于統(tǒng)計關(guān)聯(lián)［8］和基于語義依存［9］等方法。前三種方法是基于字符串本身分析，且在英文字符串匹配中有較好應(yīng)用，但在中文匹配中由于涉及到分詞問題，將大幅降低算法準(zhǔn)確性，增加執(zhí)行時間；基于語義詞典、基于統(tǒng)計關(guān)聯(lián)依托詞典實現(xiàn)，對于中文專屬名詞中生澀詞匯多，簡稱字符串簡短且無意義，基于語義依存對于短中文應(yīng)用效果較差，所以針對中文固定名詞的簡稱和全稱字符匹配問題，由于其分詞不明，語義不清，文幅較短特點，已有算法在其上應(yīng)用存在局限性。

因此，在大數(shù)據(jù)應(yīng)用背景下，已擁有大量相關(guān)數(shù)據(jù)基礎(chǔ)上，可以考慮使用以統(tǒng)計學(xué)為基礎(chǔ)，使用數(shù)據(jù)挖掘技術(shù)，提出一種基于屬性關(guān)聯(lián)度的中文“簡稱”和“全稱”的匹配算法。

3 基于屬性關(guān)聯(lián)度的匹配算法

根據(jù)對我國高校部分簡稱［10］分析中文簡稱特點，先采用單個字符進(jìn)行初步匹配，逐步抽取“簡稱”字符串中的單個字符與“全稱”字符串中的所有字符進(jìn)行逐一比較，并將匹配成功的字符個數(shù)與“簡稱”字符串長度相同，從而判斷兩者基本匹配。若中文“全稱”字符串長度n一般不大，算法的時間復(fù)雜度O（nlogn）是非常有限。

但由于存在中文簡稱指代不明情況，需要做進(jìn)一步更加準(zhǔn)確的匹配，如“南京大學(xué)”“南昌大學(xué)”均可簡稱為“南大”。

3.1 算法基本思想

基于屬性關(guān)聯(lián)度的匹配算法主要基于某一個屬性數(shù)據(jù)的區(qū)分可以由與該屬性密切相關(guān)屬性的區(qū)分來發(fā)現(xiàn)，即可以通過密切相關(guān)屬性來辨別某一屬性的數(shù)據(jù)。假設(shè)中文“簡稱”和“全稱”匹配的屬性為A，算法包括四個步驟：選取A的強關(guān)聯(lián)屬性；分別分析“簡稱”和“全稱”在強關(guān)聯(lián)屬性的分布相似情況；“簡稱”和“全稱”屬相的元組數(shù)量確定置信度；以關(guān)聯(lián)相似度同置信度的乘積為匹配度。算法整體框架示意如圖1所示。

圖1 算法整體框架示意圖

3.2 屬性關(guān)聯(lián)相似度計算

3.2.1 屬性關(guān)聯(lián)度

屬性關(guān)聯(lián)度就是數(shù)據(jù)源中S中屬性集合A中任意兩個屬性間的關(guān)聯(lián)程度，這里主要研究屬性集合中各屬性同 D 的關(guān)聯(lián)程度。屬性關(guān)聯(lián)度計算有基于線性相關(guān)性計算或基于貝葉斯分類器進(jìn)行實現(xiàn)等方法，由于數(shù)據(jù)源中各屬性數(shù)據(jù)數(shù)值型數(shù)據(jù)較少使用線性相關(guān)性不能計算完全，對于貝葉斯分類器方法通過針對決策屬性的條件屬性調(diào)整判斷關(guān)聯(lián)度，只能得到條件數(shù)據(jù)的關(guān)聯(lián)強度定性數(shù)據(jù)。因此，這里使用基于信息熵理論的互信息度來評價屬性關(guān)聯(lián)度。

在數(shù)據(jù)源中，兩個屬性間如果相互關(guān)聯(lián)，那么其中一個屬性數(shù)據(jù)變化時，另一個關(guān)聯(lián)屬性也會發(fā)生相應(yīng)變化，兩屬性關(guān)聯(lián)程度越強，那么聯(lián)動變化越緊密。從信息熵的角度來看，屬性間的關(guān)聯(lián)度轉(zhuǎn)化為一個屬性的變化引起另一屬性變化的互信息度。

苗奪謙在文獻(xiàn)［11］中的基本方法，給出了一種計算互信息度的基本方法。該方法以屬性D為目標(biāo)屬性，以A’屬性集為條件屬性，研究A’中各屬性和屬性D的互信息度。由于D∩A’=?，D∪A’=A，那么U在D和A’上的概率分布為

其中，p（Ai）=|Ai|/|U|，根據(jù)信息熵的定義，屬性集 A’的信息熵可以定義為

那么目標(biāo)屬性D相對于條件屬性集A’的條件信息熵為

根據(jù)粗糙集理論［12～13］，計算A’中所有支持D的屬性集合，即為A’的D核CoreD（A’），記A0=CoreD（A’）。

按照互信息計算方法，依次計算I（D|A0），由于討論不含D核的互信息沒有衡量意義。因此，對于不含D核的集合A’-A0的任意屬性Ak的相對D的關(guān)聯(lián)度為

對于D核集合A0中的屬性則不作單獨討論，認(rèn)為RD（A0）=I（D|A0）。因此得到了A’相對于D的所有屬性關(guān)聯(lián)度。

3.2.2 屬性相似度

屬性相似度主要研究的是屬性D上d1，d2對應(yīng)的關(guān)聯(lián)屬性集合A’D中各屬性上數(shù)據(jù)分布的相似程度。在大數(shù)據(jù)應(yīng)用中，代表中文固定名詞的“簡稱”和“全稱”的數(shù)據(jù)如果指代相同，由于參與統(tǒng)計數(shù)據(jù)量大，那么其相關(guān)屬性上的數(shù)據(jù)分布應(yīng)當(dāng)近似。

對于大數(shù)據(jù)應(yīng)用中的具體業(yè)務(wù)數(shù)據(jù)源，除基本的數(shù)值類型數(shù)據(jù)外，其余文本型、非結(jié)構(gòu)化數(shù)據(jù)等可以通過聚集、分類等技術(shù)轉(zhuǎn)化為離散型數(shù)值，重點對離散型數(shù)據(jù)進(jìn)行分析研究，對于連續(xù)型數(shù)據(jù)可以按照隸屬函數(shù)的方法轉(zhuǎn)化為離散型數(shù)值。

分析關(guān)聯(lián)屬性中離散型數(shù)據(jù)進(jìn)而分析其分布近似情況。對于關(guān)聯(lián)屬性Ak中離散型數(shù)據(jù)在U上的集合｛a1，a2，…an｝，主要統(tǒng)計各數(shù)據(jù)點分布數(shù)據(jù)個數(shù)集合Ck=｛c1，c2，…cn｝，分別計算 d1，d2對應(yīng)的統(tǒng)計分布集合為 C1k=｛c11，c12，…c1n｝，C2k=｛c21，c22，…c2n｝，那么屬性D中d1，d2相對關(guān)聯(lián)屬性A的差異體現(xiàn)在Ak同一數(shù)據(jù)ai的統(tǒng)計數(shù)占總比值的差值，則兩者在離散數(shù)據(jù)類型屬性Ak相似度表示是100%減去差異度，即為

當(dāng)屬性D取d1，d2對應(yīng)在關(guān)聯(lián)屬性Ak上的數(shù)據(jù)集在各離散點分布情況完全相同，即認(rèn)為d1，d2本質(zhì)上完全相同的，那么式（6）的后半部分為0，此時相似度為1，即100%。

3.2.3 屬性關(guān)聯(lián)相似度

屬性關(guān)聯(lián)相似度作為判斷中文固定名詞所在屬性D中兩個數(shù)值“簡稱”和“全稱”的d1，d2的相似程度，對與屬性D相關(guān)聯(lián)屬性A’進(jìn)行相似分析得到無當(dāng)量相似度SEAi（d1，d2）。在判斷d1，d2的匹配程度時，考慮所有關(guān)聯(lián)屬性A’，那么以關(guān)聯(lián)屬性集合A’中各屬性權(quán)重可以用與屬性D的關(guān)聯(lián)度表示。

因此，首先對 A’中的所有屬性 A0+｛A1，A2，…Am｝，其中A0為屬性D的核其中包括n-m個屬性，并對A’-A0的非核屬性進(jìn)行重新編號，通過歸一化方法得到各屬性或?qū)傩约臋?quán)重矩陣為

那么，可以得到屬性D上d1，d2的關(guān)聯(lián)相似度RS（d1，d2）為W和 A’中各屬性相似度的對應(yīng)乘積和，是一個小于100%的無量綱數(shù)值，即

3.3 置信度的引入及匹配度計算

由于關(guān)聯(lián)相似度的計算主要基于統(tǒng)計學(xué)的，需要大量基礎(chǔ)數(shù)據(jù)作為支撐。但同時要注意，作為數(shù)據(jù)源S上屬性D=d1，D=d2所對應(yīng)的數(shù)據(jù)集元組數(shù)量足夠多且相當(dāng)，否則，當(dāng)D=d1，D=d2數(shù)據(jù)量有限且不相當(dāng)時，即便關(guān)聯(lián)相似度較高，可以認(rèn)為是偶然因素導(dǎo)致，不具備普遍意義。樣本量數(shù)據(jù)與結(jié)果置信度密切相關(guān)［14］，因此，需要在關(guān)聯(lián)相似度基礎(chǔ)上引入置信度。

根據(jù)置信度與樣本量的密切關(guān)系，使用頻繁共現(xiàn)熵方法［15］分析置信度，假設(shè)D=d1，D=d2對應(yīng)數(shù)據(jù)量為C1，C2，當(dāng) C1，C2不是足夠大時，那么 d1在屬性D對應(yīng)的全樣本空間分布概率為p（d1）=C1/（C1+C2），同理可得 p(d2)的值。

那么頻繁共現(xiàn)熵 f(D)值為

由式（9）得到置信度c(D)為

由式（8）和（10）得到 d1，d2的匹配度為

4 實驗分析及效果評價

根據(jù)數(shù)據(jù)堂提供的我國15萬在售小區(qū)信息數(shù)據(jù)集，數(shù)據(jù)集包含數(shù)據(jù)項：小區(qū)id、城市、小區(qū)名稱、均價、小區(qū)地址、所在區(qū)域、周邊學(xué)校、郵編、竣工時間、總戶數(shù)、停車位、綠化率、容積率、物業(yè)費，以及停車位信息包含停車場方式、價格車位數(shù)等方面信息。由于數(shù)據(jù)源來自網(wǎng)絡(luò)，數(shù)據(jù)規(guī)范性較差，在周邊學(xué)校數(shù)據(jù)項中出現(xiàn)比較多的高校名稱簡稱，主要研究該屬性中高校簡稱匹配問題。

大數(shù)據(jù)應(yīng)用中，對數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理，主要先完成“周邊學(xué)?！逼渌麑傩裕鐚⒕鶅r按千元，物業(yè)費按1元劃分區(qū)間等級，“周邊學(xué)校”屬性按標(biāo)點劃分開來。按照基于屬性關(guān)聯(lián)度方法對高校名稱進(jìn)行匹配，以數(shù)據(jù)項“周邊學(xué)校”為目標(biāo)屬性D，得到屬性D的核CoreD為A0=｛均價，所在區(qū)域，郵編｝，按照式（5）得到其余屬性的關(guān)聯(lián)度（忽略值＜0.01的屬性），那么通過式（7）歸一化處理得到屬性集合｛均價，所在區(qū)域，郵編，物業(yè)費，城市｝的相對“周邊學(xué)?！睂傩訢關(guān)聯(lián)度權(quán)重為

這里對屬性D中的d1=“華中科技大學(xué)”進(jìn)行分析，通過單字匹配方法進(jìn)行初步匹配得到d2=“華科大”，d3=“華科”，d4=“科大”，d5=“中科大”，以 d1為基準(zhǔn)，計算關(guān)聯(lián)屬性集｛均價，所在區(qū)域，郵編，物業(yè)費，城市｝的相似度為

表1 關(guān)聯(lián)屬性集的相似度

根據(jù)式（8）得到 d2，d3，d4，d5相對屬性D的值 d1的匹配關(guān)聯(lián)度為

認(rèn)為d2，d3同全稱d1的匹配度高，且匹配度均超過75%，判斷與d1為同一指向，d4，d5與d1的匹配度均沒有達(dá)到35%，不認(rèn)為匹配。根據(jù)現(xiàn)實簡稱情況，該匹配算法結(jié)果符合實際情況。

5 結(jié)語

該匹配算法主要運用于大數(shù)據(jù)具體分析及應(yīng)用之前，對于匹配算法結(jié)果匹配度不高時候，采用關(guān)聯(lián)屬性方法會導(dǎo)致后續(xù)的關(guān)聯(lián)分析存在效能增強的情況，因此對于涉及各屬性關(guān)聯(lián)情況的主因分析等大數(shù)據(jù)應(yīng)用時，應(yīng)謹(jǐn)慎使用本算法。

在大數(shù)據(jù)應(yīng)用中，為解決數(shù)據(jù)清洗或數(shù)據(jù)集成中中文固定名詞的簡稱和全稱匹配問題，提出一種基于屬性關(guān)聯(lián)度的匹配算法。該算法在單詞匹配基礎(chǔ)上，通過其他屬性同匹配目標(biāo)屬性間的關(guān)聯(lián)度，及“簡稱”和“全稱”對應(yīng)關(guān)聯(lián)屬性上的數(shù)據(jù)分布相似度得到各屬性的關(guān)聯(lián)相似度，并結(jié)合“簡稱”和“全稱”的數(shù)據(jù)量得到置信度，并結(jié)合關(guān)聯(lián)相似度得到匹配度。該算法應(yīng)用于小區(qū)數(shù)據(jù)集，發(fā)現(xiàn)該算法匹配度高，結(jié)果符合實際情況，算法匹配效果好。