一種基于關(guān)聯(lián)規(guī)則的中文變體詞識別算法

趙俊杰

(安徽財經(jīng)大學(xué) 工商管理學(xué)院， 安徽 蚌埠　233030)

隨著手機及互聯(lián)網(wǎng)的高速發(fā)展和社交網(wǎng)絡(luò)的興起，經(jīng)常會遇到如何正確識別變體詞的問題[1]。例如，很多網(wǎng)民往往會采用不規(guī)范的漢字書寫辦法，使用字形相近的生僻字來代替原有的文字，或者針對某些敏感詞采用加特殊符號的辦法等[2]。這樣做的目的或者是為了避開一些政治敏感詞語[3]，或者為躲避常規(guī)的過濾方法來發(fā)布廣告以及反動、暴力或者色情等不良信息。這些變體詞主要出現(xiàn)在短信、微博/博客、論壇、電子小說、電子郵件、微信以及各種即時通訊中[4]。

大量的廣告與不良信息常常干擾到用戶對互聯(lián)網(wǎng)的正常使用，甚至?xí)o用戶帶來損失。目前針對廣告與不良信息主要采取關(guān)鍵詞匹配的方法來進行識別和過濾，常見的關(guān)鍵詞匹配方法是基于中文信息處理技術(shù)和多模式匹配技術(shù)，能夠有效發(fā)現(xiàn)各種廣告和不良信息，技術(shù)實現(xiàn)簡單[5]。但因這些文本中存在的關(guān)鍵詞中間夾雜字符、對關(guān)鍵詞中的關(guān)鍵字使用形近字或拼音進行替換等變體特征，在實際應(yīng)用中存在較高的誤判率或漏判率，使得人工干預(yù)成本增加[6]。同時，需要不斷增加新出現(xiàn)的各種特征進入關(guān)鍵詞庫，造成關(guān)鍵詞庫的極大冗余[7]。國內(nèi)外一些專家學(xué)者針對中文變體詞的識別技術(shù)和算法也進行了大量研究，例如：王寶勛等[8]提出一種適用于中文的基于無監(jiān)督的變體詞識別算法；汪霞等[9]針對特征詞變異的中文垃圾郵件問題，提出了一種基于變體特征詞匹配還原的新貝葉斯郵件過濾算法；溫園旭等[10]提出的基于層次特征的變體短文本過濾算法；Sood等[11]在對不良文本及其變體信息進行檢測的時候,采用機器學(xué)習(xí)的方法，通過采用bigram、詞干等作為特征值來對文本信息做分類分析,以檢測出變體詞；Wang等[12]將中文微博變體詞的發(fā)現(xiàn)與中文分詞結(jié)合起來，提出二層階乘條件隨機場模型，并將兩者結(jié)合起來，使得兩者的性能都有所提高。Zhang 等[13]提出了一個端到端的無監(jiān)督的方法，基于深度學(xué)習(xí)實現(xiàn)對變體詞及其目標(biāo)實體詞的映射關(guān)系的發(fā)現(xiàn)。另外，部分防水墻過濾系統(tǒng)中對于網(wǎng)絡(luò)灌水等惡意行為的監(jiān)測，是將所有漢字轉(zhuǎn)換成拼音形式，然后檢索和過濾拼音關(guān)鍵字，但效果不理想?？傮w來說，關(guān)于中文變體詞的識別技術(shù)研究還較少，目前對中文變體詞仍缺少有效的解決方法。

本文研究中文變體詞的識別技術(shù)和算法，對于垃圾郵件與短消息的過濾、不良信息的檢索等都有著非常重要的作用。本文針對中文變體詞的常見類型進行分析歸納，設(shè)計出一種基于關(guān)聯(lián)規(guī)則的中文變體詞識別算法，以提升識別效果。

1　中文變體詞的分類及相關(guān)工作

1.1　中文變體詞分類

通過對于中文變體詞的收集和分析，中文變體詞總體可以分為3種類型：

1) 漢字字形的變體，即使用繁體字、同音字或形近字替換部分或者全部目標(biāo)詞語，如“代開發(fā)票”替換為“代開發(fā)飄”等；

2) 漢字變換為字母，即使用英文單詞、拼音或者拼音縮寫替換目標(biāo)詞語，如“發(fā)票”替換為“fa piao”等；

3) 漢字詞中包含特殊字符，即在中文詞語中插入特殊字符或者使用特殊字符進行部分漢字替換，這里特殊字符包括字母或漢字的偏旁部首等形式。如“招聘淘寶刷鉆”替換為“招*聘*淘*寶*刷*鉆”等。

中文變體詞的分類采用以上劃分方式的主要目的是方便中文變體詞識別算法的設(shè)計。另外，還有使用圖形或圖片替換中文目標(biāo)詞語的情況，需要圖形識別等技術(shù)，這里不做討論。

1.2　中文分詞方法的改進

目前，常見的中文分詞技術(shù)主要有基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法[14]。對于已經(jīng)收錄詞庫的詞語分詞結(jié)果誤差較小，但對于一些新詞或者變體詞的分詞效果不是很好。這里對于中文分詞方法的改進主要是針對中文變體詞的劃分。

大多數(shù)中文分詞系統(tǒng)對于不能識別的詞語或者字符都是單獨分離出來進行分別標(biāo)注，這樣做的結(jié)果可能使得大多數(shù)中文變體詞被分成多個單個的字符和漢字，例如原文：“本站誠征EMAIL廣告代理，收費為每群發(fā)一次EMAIL廣告100元?！北环纸獬伞氨菊?誠/征/EMAIL/廣/ #/告/ #/代/ #/理/，/收費/為/每/群/ #/發(fā)/ #/一次/ EMAIL/廣/ #/告/ #/100/元/。/”。

本文對中文分詞系統(tǒng)做部分改進，即對于不能識別的字符與前后的單個漢字合并，直至后面詞語或符號等能夠被單獨識別和標(biāo)注。這樣設(shè)計的主要目的是盡可能地分出多字詞和短語，方便中文變體詞的識別。對ICTCLAS中文分詞系統(tǒng)[7]進行改進，對于以上的例子，在改進后的ICTCLAS中文分詞系統(tǒng)中分詞的結(jié)果為“本站/誠/征/ EMAIL/廣#告#代#理/，/收費/為/每/群#發(fā)#/一次/ EMAIL/廣#告#/100/元/。/”。

1.3　中文變體詞庫及其關(guān)聯(lián)詞庫的建立

對于中文變體詞庫的建立本文主要針對以上分類中的第1種和第2種類型，主要原因是第3種變體類型變化較多，如采用多種特殊字符進行替換等，不方便歸納和存儲。中文變體詞庫包括3個表：中文變體原詞表、字形變體表、字母變體表。其中：字形變體表主要收錄變體原詞的繁體字、常見同音字和形近字；字母變體表主要收錄變體原詞的英文單詞、拼音或者拼音縮寫。另外，為改善識別效果，還增加了1個關(guān)聯(lián)詞庫。關(guān)聯(lián)詞庫的建立原則是：首先對樣本集的文本在分詞后去除停用詞，再篩選出與中文變體原詞同時使用概率較大的詞語集合，最后按照關(guān)聯(lián)規(guī)則對每個中文變體詞選定若干關(guān)聯(lián)詞語，形成關(guān)聯(lián)詞庫。

中文變體原詞表、字形變體表、字母變體表按編號建立關(guān)聯(lián)，一一對應(yīng)。關(guān)聯(lián)詞庫與中文變體原詞庫中各表也按編號建立關(guān)聯(lián)。這里共收集了477個變體原詞(政治敏感詞102個，廣告詞85個，反動和恐怖詞93個，色情詞71個，其他126個)和變體詞以及關(guān)聯(lián)詞，分別存放在中文變體原詞表、字形變體表、字母變體表以及關(guān)聯(lián)詞庫中。

2　基于關(guān)聯(lián)規(guī)則的中文變體詞識別算法

2.1　算法優(yōu)勢與總體思路

對于中文變體字的識別目前采取的方法主要是基于多模式匹配技術(shù)和中文信息處理技術(shù)。多模式匹配技術(shù)即采用統(tǒng)計和規(guī)則的識別方法，這種方法主要依賴于匹配規(guī)則和變形詞庫。在實際運用中，一是精準(zhǔn)的匹配規(guī)則較難確定，二是變形詞庫龐大，使得識別效果不理想。基于中文信息處理技術(shù)主要是對變體詞在語義相似度上進行比較，在比較時一般是結(jié)合上下文或時空分布的相似性。但這種方法嚴(yán)重依賴變體詞的若干個樣本聚合上下文和時空信息，因此實際識別效果不穩(wěn)定。

本文采取的算法是對以上兩種方法的結(jié)合和改進：一是對模式匹配方法進行了改進，分類型進行匹配，提高了效率；二是采用關(guān)聯(lián)詞庫輔助識別，相比結(jié)合上下文或時空信息進行語義相似度計算要簡單易行，實際識別效果也較穩(wěn)定。其主要思路是：先通過字符串匹配算法識別出初步目標(biāo)，然后通過關(guān)聯(lián)分析進一步識別判斷，最后通過人工判定輔助最終識別出結(jié)果。對于識別出的結(jié)果可以補充和更新相應(yīng)的變體詞庫和關(guān)聯(lián)詞庫，具體識別過程如圖1所示。

具體步驟為：

1) 將待查文本轉(zhuǎn)換成文本格式，通過改進的分詞系統(tǒng)進行分詞；

2) 判斷文本中每個詞語或短語，是全部漢字、漢字與字符組合還是全部字母，然后分別結(jié)合對應(yīng)變體詞庫，使用相應(yīng)的識別算法進行識別；

3) 將初步識別結(jié)果進一步結(jié)合關(guān)聯(lián)詞庫進行關(guān)聯(lián)分析；

4) 對于關(guān)聯(lián)分析的結(jié)果輔助于人工判定，最后給出最終識別結(jié)果；

5) 將識別結(jié)果補充和更新變體詞庫和關(guān)聯(lián)詞庫。

識別算法在執(zhí)行過程中首先判斷目標(biāo)類型，即掃描每個分詞結(jié)果，判斷是否全為漢字，若是則判斷為第1種類型；否則再判斷是否全為字母，若是，則為第2種類型；否則歸為第3種類型。目標(biāo)類型判斷過程如圖2所示。

圖1　基于關(guān)聯(lián)規(guī)則的中文變體詞識別算法

對于目標(biāo)類型判斷結(jié)果采取以下3種對應(yīng)處理方法：

1) 全部漢字情況

對于繁體字和同音字，首先檢索變體詞表中繁體字項和常見同音字項，如果有完全匹配項則標(biāo)出，直接給出識別結(jié)果；否則將目標(biāo)轉(zhuǎn)換成拼音形式，然后與字體變體庫中字母變體表的拼音項進行比較，如有相同則標(biāo)出，沒有匹配項則進入形近字識別。

對于形近字的識別，先檢索字形變體詞表，查看有無完全匹配項，如有則標(biāo)出；沒有則與變體詞原表比較。如果有超過一半與原表中漢字相同，且字符數(shù)相等，則標(biāo)出；否則，認為無匹配項。

2) 全部字母情況

由于變體詞庫中字母變體表中收錄了變體詞對應(yīng)的拼音、拼音縮寫和英文形式以及英文縮寫形式，因此直接將目標(biāo)與字母變體表中各項進行比較即可。如果有匹配項則標(biāo)出；否則，認為是無匹配項。

3) 漢字與字符組合情況

由于這種類型變化較多，因此沒有建立相應(yīng)數(shù)據(jù)庫表，在識別時，主要根據(jù)變體詞原詞表進行檢索目標(biāo)詞語或短語，只要其中的漢字部分與變體詞原表中的原詞相應(yīng)部分相同，則標(biāo)出；否則，認為無匹配項。

2.2　關(guān)聯(lián)規(guī)則設(shè)置與關(guān)聯(lián)詞庫建立

設(shè)I={X,i1,i2,…,im}是項的集合，包括某一變體詞及其所在語句中的去除停用詞之外的詞語集合。事物數(shù)據(jù)庫D為變體詞及所在的每條語句中去除停用詞之外的詞語集合，D={t1,t2,…,tn}，ti(i=1,2,…,n)對應(yīng)I上的一個子集，存放單條語句中的詞語集。X?I，Y?I,X∩Y=?，其中:X為變體詞;Y為高頻詞集。這里高頻詞的選擇設(shè)定為變體詞所在語句范圍內(nèi)，是考慮到如果設(shè)定為全文范圍，選擇的高頻詞可能大多數(shù)與全文主題相關(guān)，但變體詞不一定與全文主題相關(guān)，以此作為關(guān)聯(lián)詞的選擇可能造成變體詞的識別效果誤差較大。對于其他變體詞及其所在語句中的高頻詞可設(shè)定同樣集合。關(guān)聯(lián)規(guī)則X=>Y的支持度與置信度公式如下[15]：

Support(X=>Y)=P(X∪Y)；

Confidence(X=>Y)=P(Y|X)=P(X∪Y)/P(X)

主要思路為：

1) 對樣本中文本分詞，去除停用詞，人工抽取樣本中包含有變體詞的語句；

2) 對于每個變體詞找出其所在語句中的前m個高頻詞；

3) 分別計算變體詞與相應(yīng)的這m個高頻詞在事物數(shù)據(jù)庫D中同時出現(xiàn)的支持度與置信度；

4) 對于其他集合中每個變體詞及其相應(yīng)的高頻詞做同樣計算；

5) 設(shè)置最小支持度和最小置信度值，以此對變體詞的關(guān)聯(lián)詞語進行選擇。

作為初步實驗數(shù)據(jù)，抽取電子郵件2 500條，論壇發(fā)帖1 500條，電子小說600篇作為訓(xùn)練樣本。通過統(tǒng)計分析發(fā)現(xiàn)：與變體詞所在語句中同時使用概率較大的高頻詞基本集中在前7個高頻詞中，因此這里m值設(shè)為7。由于實驗數(shù)據(jù)較少，這里只選取了在實驗數(shù)據(jù)集出現(xiàn)的其中50個變體詞。表1和表2是部分變體詞的7個關(guān)聯(lián)詞語的支持度和置信度計算結(jié)果。

表1　部分變體詞的主要關(guān)聯(lián)詞語的支持度計算結(jié)果　%

表2　部分變體詞的主要關(guān)聯(lián)詞語的置信度計算結(jié)果　%

通過對計算結(jié)果進行統(tǒng)計發(fā)現(xiàn)：對于某一個變體詞的每個關(guān)聯(lián)詞最小支持度和置信度，數(shù)值都較??；對于不同變體詞的關(guān)聯(lián)詞，其支持度和置信度出現(xiàn)較大差別，最小支持度和置信度值較難設(shè)置，且依此選擇的關(guān)聯(lián)詞比較分散，出現(xiàn)稀疏項目問題[16]。即：如果最小支持度太高，有些項目集中就不會生成包含稀疏項目的規(guī)則；如果最小支持度設(shè)置太低，就會生成太多的規(guī)則，而且其中很多規(guī)則都是不重要的[17]。解決稀疏項目的可行方法是將稀疏項目組合，并對這些組合重新生成關(guān)聯(lián)規(guī)則，并按此關(guān)聯(lián)規(guī)則重新選擇關(guān)聯(lián)詞語集合，建立關(guān)聯(lián)詞庫。

定義1支持度公式。設(shè)I={X,i1,i2,…,im}是項的集合，包括某一變體詞及其所在語句中的去除停用詞之外的詞語集合。事物數(shù)據(jù)庫D為變體詞及所在的每條語句中去除停用詞之外的詞語集合，D={t1,t2,…,tn}，ti(i=1,2,…,n)對應(yīng)I上的一個子集，存放單條語句中的詞語集。X?I，Y?I,X∩Y=?。X為變體詞，Y={i1,i2,…,ik}，k=1,2,…,m，且規(guī)定當(dāng)X出現(xiàn)時Y中的任意一項同時出現(xiàn)，則 Support(X=>Y)=P(X∪Y)就成立。

定義2置信度公式。X?I，Y?I，X∩Y=?，X為變體詞，Y={i1,i2,…,ik}，k=1,2,…,m。當(dāng)X出現(xiàn)時，Y中的任意一項同時出現(xiàn)，則Confidence(X=>Y)=P(Y|X)=P(X∪Y)/P(X) 成立。

由于不同變體詞的關(guān)聯(lián)詞語的支持度數(shù)值差別較大，因此對于每個變體詞的關(guān)聯(lián)詞分別單獨計算其支持度。由于篇幅有限，表3和表4只給出k取1～7時部分變體詞的支持度和置信度計算結(jié)果。

表3　k取不同值時支持度計算結(jié)果　%

表3、4中：當(dāng)k=1時，值為第一個高頻詞支持度值；當(dāng)k=2時，值為前兩個高頻詞組合，以此類推。由表3和表4中數(shù)據(jù)可以看出：隨著k值增大，其支持度和置信度值也隨之增大，但在實際識別中誤差也會增大。這里對于k的取值，如果統(tǒng)一設(shè)定一個固定值，由于有的變體詞的關(guān)聯(lián)詞比較集中，有的變體詞的關(guān)聯(lián)詞比較分散，導(dǎo)致誤判率較高。因此，這里根據(jù)最小關(guān)聯(lián)度值和最小置信度值作為k取值的依據(jù)，即確定關(guān)聯(lián)詞集合中詞語的個數(shù)。通過對初步實驗數(shù)據(jù)的綜合分析，將最小支持度的值設(shè)定為15%，最小置信度值設(shè)定為40%，此時k的取值比較合理。每個變體詞在此最小支持度和最小置信度下分別取對應(yīng)的k值，當(dāng)兩個k取值不統(tǒng)一時，以最小的k值為最終值。統(tǒng)計表明，大多數(shù)k的取值主要集中在2～5之間，少數(shù)k值為1和6?？紤]到計算誤差和樣本較少，在實際執(zhí)行過程中對k值進行微調(diào)，即：當(dāng)k<2時，k=2；當(dāng)k>5時，k=5。這樣設(shè)計的目的在于：如只取一個關(guān)鍵詞和超過5個關(guān)鍵詞，可能造成關(guān)鍵詞過于集中和過于分散。

3　實驗及結(jié)果分析

3.1　實驗語料的選取及準(zhǔn)備工作

本文收集了477個變體詞樣本作為實驗數(shù)據(jù)，其語料來源為網(wǎng)上收集的包含變體詞的電子郵件、論壇和電子小說。其中，電子郵件5 000條，論壇發(fā)帖3 500條，電子小說1 300篇。這些實驗語料中的變型詞主要涉及廣告、不良信息和政治敏感詞語等。在實驗前期，抽取電子郵件2 500條、論壇發(fā)帖1 500條、電子小說600篇作為訓(xùn)練樣本，剩下的作為測試樣本。由于收集的變體詞樣本只涉及到部分變體類型，因此在測試樣本中人工增加了一些變體詞實例，盡可能覆蓋各種變體類型，以便檢驗整體的識別效果。

對訓(xùn)練樣本進行分詞，去除停用詞。針對訓(xùn)練樣本中的變體詞進行統(tǒng)計和歸納，分別建立中文變體詞庫。其中，中文變體詞庫包括中文變體原詞表、字形變體表、字母變體表。對于每個變體詞先找出其所在語句中的前7個高頻詞，然后根據(jù)最小支持度值和最小置信度值為每個變體詞建立關(guān)聯(lián)詞集，從而形成關(guān)聯(lián)詞庫。

3.2　實驗過程

首先對于測試樣本進行初步識別，未使用關(guān)聯(lián)規(guī)則，3種變體詞類型的識別效果如表5、6所示。

進而對測試樣本做基于關(guān)聯(lián)規(guī)則的變體詞識別整體測試，對比初步識別結(jié)果和基于關(guān)聯(lián)規(guī)則的識別結(jié)果，如表7所示。

表5　測試樣本各類型識別效果　%

表6　測試樣本平均識別效果　%

表7　測試樣本識別效果對比　%

3.3　實驗結(jié)果分析

通過對改進后的分詞結(jié)果進行初步字符匹配識別，可以初步識別出絕大多數(shù)疑似變體詞的目標(biāo)。對于不同類型采取不同的字符匹配的方法，使得平均查全率超過93%，其中對于繁體字、拼音替代、英文替代以及插入字符等類型識別效果較好，誤判率較低，對于同音字、形近字和字符替代類型誤判率稍高。分析其原因為：每個變體詞的不同同音字和形近字較多，不能全部收錄；字符替換的形式也是各種各樣，尤其是變體詞中大部分漢字被替換成符號的情況，容易造成誤判。

對于初步識別的結(jié)果通過進一步借助關(guān)聯(lián)詞庫分析識別，對于誤判率有顯著改變，尤其是同音詞和字符替換類型，使得變體詞識別的平均誤判率下降到2%以內(nèi)。

4　結(jié)束語

在現(xiàn)實生活中，大量的廣告和不良信息為了規(guī)避常規(guī)方法的檢測和過濾，常常以不規(guī)整、不正常的形式出現(xiàn)，即采用變體的形式使傳統(tǒng)方法無法正確檢測和過濾。但是這部分包含變體詞的文本卻仍能夠達到發(fā)布廣告、不良信息的目的。本文通過對改進后的分詞結(jié)果進行初步字符匹配識別，可以初步識別出絕大多數(shù)疑似變體詞的目標(biāo)。對于不同類型采取不同的字符匹配方法，使得平均查全率超過90%，接著對于初步識別的結(jié)果進一步借助關(guān)聯(lián)詞庫分析識別，可顯著減少誤判率，尤其是對同音詞和字符替換類型，使得變體詞識別的平均誤判率下降到2%以內(nèi)。但對于文本行列變換，圖形替代等變體形式如何識別未在算法中考慮，這部分內(nèi)容將在后續(xù)研究中進行。

參考文獻：

[1]羅剛,張子憲.自然語言處理原理與技術(shù)實現(xiàn)[M].北京:電子工業(yè)出版社,2016.

[2]陳鄞.自然語言處理基本理論和方法[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2013.

[3]謝邦昌,朱建平,李毅.文本挖掘技術(shù)及其應(yīng)用[M].廈門:廈門大學(xué)出版社,2016.

[4]朱儉.文本情感分析關(guān)鍵技術(shù)研究[M],北京:中國社會科學(xué)出版社，2015.

[5]范黎林,王曉東.一種用于垃圾郵件過濾的中文關(guān)鍵詞匹配算法[J].河南科技大學(xué)學(xué)報,2006,27(5):35-37.

[6]叢健.不良信息過濾技術(shù)研究[D].北京:北京郵電大學(xué),2012.

[7]周天綺.網(wǎng)絡(luò)安全中的信息過濾綜述[J].微處理機,2011.32(5):30-34.

[8]王寶勛,王曉龍,劉秉權(quán),等.一種基于無監(jiān)督學(xué)習(xí)的詞變體識別方法[J].中文信息學(xué)報,2008，22(3):32-36.

[9]汪霞,鄭寧.基于中文變形詞匹配的貝葉斯郵件過濾模型[J].計算機應(yīng)用與軟件,2010.27(1):105-107,130.

[10] 溫園旭.變體短文本過濾算法研究[D].北京:北京郵電大學(xué),2012.

[11] SOOD S O,ANTIN J,CHURCHILL E.Using Crowdsourcing to Improve Profanity Detection[J].Aaai Spring Symposium,2012，33：69-74.

[12] WANG A,KAN M Y.Mining Informal Language from Chinese Microtext:Joint Word Recognition and Segmentation[C]//Meeting of the Association for Computational Linguistics.2013:731-741.

[13] ZHANG B,HUANG H,PAN X,et al.Context-aware Entity Morph Decoding[C]//Meeting of the Association for Computational Linguistics and the,International Joint Conference on Natural Language Processing.2015:586-595.

[14] 黃昌寧,趙海.中文分詞十年回顧[J].中文信息學(xué)報,2007,1(3):8-19.

[15] 李愛國.數(shù)據(jù)挖掘原理、算法及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2012.

[16] XINDONG W,VIPIN K.數(shù)據(jù)挖掘十大算法[M].北京:清華大學(xué)出版社，2013.

[17] MARGARETH D,鄧納姆,郭崇慧,等.數(shù)據(jù)挖掘教程[M].北京:清華大學(xué)出版社,2005.