一種基于關聯規則的中文變體詞識別算法

趙俊杰

(安徽財經大學 工商管理學院， 安徽 蚌埠　233030)

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

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

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

1　中文變體詞的分類及相關工作

1.1　中文變體詞分類

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

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

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

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

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

1.2　中文分詞方法的改進

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

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

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

1.3　中文變體詞庫及其關聯詞庫的建立

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

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

2　基于關聯規則的中文變體詞識別算法

2.1　算法優勢與總體思路

對于中文變體字的識別目前采取的方法主要是基于多模式匹配技術和中文信息處理技術。多模式匹配技術即采用統計和規則的識別方法，這種方法主要依賴于匹配規則和變形詞庫。在實際運用中，一是精準的匹配規則較難確定，二是變形詞庫龐大，使得識別效果不理想?；谥形男畔⑻幚砑夹g主要是對變體詞在語義相似度上進行比較，在比較時一般是結合上下文或時空分布的相似性。但這種方法嚴重依賴變體詞的若干個樣本聚合上下文和時空信息，因此實際識別效果不穩定。

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

具體步驟為：

1) 將待查文本轉換成文本格式，通過改進的分詞系統進行分詞；

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

3) 將初步識別結果進一步結合關聯詞庫進行關聯分析；

4) 對于關聯分析的結果輔助于人工判定，最后給出最終識別結果；

5) 將識別結果補充和更新變體詞庫和關聯詞庫。

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

圖1　基于關聯規則的中文變體詞識別算法

對于目標類型判斷結果采取以下3種對應處理方法：

1) 全部漢字情況

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

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

2) 全部字母情況

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

3) 漢字與字符組合情況

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

2.2　關聯規則設置與關聯詞庫建立

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

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

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

主要思路為：

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

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

3) 分別計算變體詞與相應的這m個高頻詞在事物數據庫D中同時出現的支持度與置信度；

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

5) 設置最小支持度和最小置信度值，以此對變體詞的關聯詞語進行選擇。

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

表1　部分變體詞的主要關聯詞語的支持度計算結果　%

表2　部分變體詞的主要關聯詞語的置信度計算結果　%

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

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

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

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

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

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

3　實驗及結果分析

3.1　實驗語料的選取及準備工作

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

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

3.2　實驗過程

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

進而對測試樣本做基于關聯規則的變體詞識別整體測試，對比初步識別結果和基于關聯規則的識別結果，如表7所示。

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

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

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

3.3　實驗結果分析

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

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

4　結束語

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

參考文獻：

[1]羅剛,張子憲.自然語言處理原理與技術實現[M].北京:電子工業出版社,2016.

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

[3]謝邦昌,朱建平,李毅.文本挖掘技術及其應用[M].廈門:廈門大學出版社,2016.

[4]朱儉.文本情感分析關鍵技術研究[M],北京:中國社會科學出版社，2015.

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

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

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

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

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

[10] 溫園旭.變體短文本過濾算法研究[D].北京:北京郵電大學,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].中文信息學報,2007,1(3):8-19.

[15] 李愛國.數據挖掘原理、算法及應用[M].西安:西安電子科技大學出版社,2012.

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

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