基于屬性關(guān)聯(lián)相似度的中文簡稱匹配算法研究?

郭 暉董 源周 鋼

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

1 引言

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

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

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

2 問題背景

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

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

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

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

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

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

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

3.1 算法基本思想

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

圖1 算法整體框架示意圖

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

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

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

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

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

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

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

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

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

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

3.2.2 屬性相似度

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

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

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

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

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

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

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

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

3.3 置信度的引入及匹配度計(jì)算

由于關(guān)聯(lián)相似度的計(jì)算主要基于統(tǒng)計(jì)學(xué)的，需要大量基礎(chǔ)數(shù)據(jù)作為支撐。但同時(shí)要注意，作為數(shù)據(jù)源S上屬性D=d1，D=d2所對(duì)應(yīng)的數(shù)據(jù)集元組數(shù)量足夠多且相當(dāng)，否則，當(dāng)D=d1，D=d2數(shù)據(jù)量有限且不相當(dāng)時(shí)，即便關(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對(duì)應(yīng)數(shù)據(jù)量為C1，C2，當(dāng) C1，C2不是足夠大時(shí)，那么 d1在屬性D對(duì)應(yīng)的全樣本空間分布概率為p（d1）=C1/（C1+C2），同理可得 p(d2)的值。

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

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

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

4 實(shí)驗(yàn)分析及效果評(píng)價(jià)

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

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

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

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

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

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

5 結(jié)語

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

在大數(shù)據(jù)應(yīng)用中，為解決數(shù)據(jù)清洗或數(shù)據(jù)集成中中文固定名詞的簡稱和全稱匹配問題，提出一種基于屬性關(guān)聯(lián)度的匹配算法。該算法在單詞匹配基礎(chǔ)上，通過其他屬性同匹配目標(biāo)屬性間的關(guān)聯(lián)度，及“簡稱”和“全稱”對(duì)應(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é)果符合實(shí)際情況，算法匹配效果好。