基于AC自動(dòng)機(jī)的特征詞匹配識(shí)別方法分析案例概述目錄TOC\o"1-3"\h\u30693基于AC自動(dòng)機(jī)的特征詞匹配識(shí)別方法分析案例概述 139061.1中文垃圾廣告評(píng)論的變體詞生成 134521.1.1變體詞規(guī)則總結(jié) 1275971.1.2基于規(guī)則的變體詞生成 251371.2基于AC自動(dòng)機(jī)的中文垃圾廣告評(píng)論過濾 4100001.2.1AC自動(dòng)機(jī)的原理 426541.2.2AC自動(dòng)機(jī)的實(shí)驗(yàn)結(jié)果 7新媒體平臺(tái)的垃圾廣告評(píng)論為了逃避關(guān)鍵詞檢查，會(huì)采取一些變體形式。本章將對(duì)垃圾廣告所使用的變體詞規(guī)則進(jìn)行研究和總結(jié)，使用變體詞規(guī)則擴(kuò)大關(guān)鍵詞庫，通過AC自動(dòng)機(jī)算法對(duì)垃圾廣告評(píng)論進(jìn)行檢測(cè)和識(shí)別，并對(duì)檢測(cè)結(jié)果進(jìn)行總結(jié)和分析。1.1中文垃圾廣告評(píng)論的變體詞生成變體詞[11][12][13]是互聯(lián)網(wǎng)時(shí)代下誕生的網(wǎng)絡(luò)語言作為一種不規(guī)范語言的顯著特點(diǎn)，用戶出于逃避檢查、表達(dá)特定情感、諷刺、娛樂等目的，將原本相對(duì)嚴(yán)肅、規(guī)范、正式、敏感的詞用相對(duì)不規(guī)范、不敏感的詞代替，這些用來代替原本詞的新詞就是變體詞。本節(jié)將對(duì)垃圾廣告評(píng)論的變體詞規(guī)則進(jìn)行總結(jié)，并以此規(guī)則為基礎(chǔ)生成變體詞，擴(kuò)大關(guān)鍵詞庫。1.1.1變體詞規(guī)則總結(jié)垃圾廣告評(píng)論的變體詞轉(zhuǎn)換規(guī)則，大致可以分為基于字形相似度變換、基于語音相似度變換以及基于其他相似度變換三類，具體如下：1）基于字形相似度將關(guān)鍵詞替換成字形相同的詞，例如將“微信”替換成“徽信”，如圖3-1所示：圖3-1基于字形相似度變換2）基于語音相似度將關(guān)鍵詞替換成擁有相同發(fā)音的詞，例如將“微信”替換成“威信”，如圖3-2所示：圖3-2基于語音相似度變換3）基于其他相似度（1）漢字拆分組合將具有左右結(jié)構(gòu)的關(guān)鍵詞拆分，例如將“聯(lián)系”替換成“耳關(guān)系”，如圖3-3所示：圖3-3基于漢字拆分組合變換（2）拼音替換將關(guān)鍵詞替換為拼音，例如將“微信”替換為“weixin”，如圖3-4所示：圖3-4基于拼音替換變換（3）簡繁轉(zhuǎn)化將關(guān)鍵詞替換為繁體詞，例如將“貸款”替換為“貸款”，如圖3-5所示：圖3-5基于簡繁轉(zhuǎn)化變換1.1.2基于規(guī)則的變體詞生成 本小節(jié)將基于垃圾廣告評(píng)論的變體詞生成規(guī)則，對(duì)于變體詞的音、形、拆分、簡繁轉(zhuǎn)換、拼音替換進(jìn)行實(shí)驗(yàn)，生成變體詞庫。1）語音相似度（1）下載漢字的數(shù)據(jù)庫，利用此數(shù)據(jù)編程進(jìn)行基于語音的變體詞生成。（2）設(shè)置特征詞為“微信”，生成變體詞，對(duì)特征詞的每個(gè)字查找讀音，生成五組具有相同讀音的字，再對(duì)生成的字進(jìn)行隨機(jī)組合，生成五組數(shù)據(jù)，如圖3-6所示：圖3-6語音相似度變換結(jié)果由圖3-6可知，單純采用語音相似度生成的變體詞有部分中性詞匯，也有可能生成具有相同讀音但是字形十分復(fù)雜的字，變體詞的生成效果較差。因此，可以采取字形相似度與語音相似度結(jié)合的方式生成變體詞。2）字形相似度（1）下載漢字的四角編碼、結(jié)構(gòu)數(shù)據(jù)庫、筆畫數(shù)據(jù)庫，結(jié)合語音相似度綜合進(jìn)行計(jì)算。（2）規(guī)定各部分占比權(quán)重為：0.4*語音相似度+0.2*四角編碼相似度+0.2*結(jié)構(gòu)相似度+0.2*筆畫相似度，計(jì)算結(jié)果大于0.7即認(rèn)為是變體詞。由于變體詞大多是具有相同讀音的詞，因此語音相似度的占比選擇較高，其他相似度平分權(quán)重占比。在實(shí)際實(shí)驗(yàn)中，可以根據(jù)需要修改各部分的占比權(quán)重。（3）對(duì)于關(guān)鍵詞“微信”，重復(fù)生成變體詞的工作，直到生成五組數(shù)據(jù)，如圖3-7所示：圖3-7字形相似度變換結(jié)果由圖3-7可知，與單純采用語音相似度生成變體詞的方式對(duì)比，新生成的變體詞與原本的關(guān)鍵詞相比有了更高的相似度。因此，可以使用這種方式對(duì)提取出的特征詞進(jìn)行變體詞生成，擴(kuò)大特征詞庫。3）漢字拆分部分垃圾廣告評(píng)論采用了將關(guān)鍵詞拆分的方式生成變體詞，可以采用獲取的結(jié)構(gòu)數(shù)據(jù)庫對(duì)關(guān)鍵詞進(jìn)行拆分生成變體詞。由于變體詞大多都是對(duì)具有左右結(jié)構(gòu)的漢字進(jìn)行拆分，因此，在實(shí)驗(yàn)中，對(duì)于每個(gè)字僅計(jì)算它的左右結(jié)構(gòu)，若漢字的左右結(jié)構(gòu)都可以組成新的字，則對(duì)其進(jìn)行拆分，生成新的變體詞，如圖3-8所示：圖3-8漢字拆分變換結(jié)果4）簡繁轉(zhuǎn)換部分垃圾廣告評(píng)論會(huì)使用繁體字替換掉關(guān)鍵詞部分來進(jìn)行變體，故可以下載簡體字與繁體字的轉(zhuǎn)換字典，對(duì)于關(guān)鍵詞的各個(gè)字進(jìn)行簡繁轉(zhuǎn)換，隨即組合生成關(guān)鍵詞，如圖3-9所示：圖3-9簡繁轉(zhuǎn)換變換結(jié)果5）拼音替換部分垃圾廣告評(píng)論會(huì)使用拼音的形勢(shì)來代替關(guān)鍵詞，故可以采用漢字字典對(duì)關(guān)鍵詞生成讀音變換，如圖3-10所示：圖3-10拼音替換轉(zhuǎn)換結(jié)果綜上所述，在實(shí)驗(yàn)中，將結(jié)合以上五種變體詞生成規(guī)則，對(duì)提取出的關(guān)鍵詞進(jìn)行變體詞生成，添加變體詞數(shù)據(jù)庫，用于AC自動(dòng)機(jī)的關(guān)鍵詞過濾。1.2基于AC自動(dòng)機(jī)的中文垃圾廣告評(píng)論過濾垃圾廣告評(píng)論為了能夠用簡短的文本表達(dá)信息，一般都會(huì)使用諸如“購買”、“股票”、“出售”等具有鮮明特點(diǎn)的詞。AC自動(dòng)機(jī)[14]作為一種著名且高效的多模匹配算法，可以快速匹配到用戶評(píng)論中出現(xiàn)的所有關(guān)鍵詞，進(jìn)而判斷該評(píng)論是否為垃圾廣告評(píng)論。本節(jié)將對(duì)AC自動(dòng)機(jī)算法進(jìn)行簡單介紹，并以上一節(jié)生成的變體詞庫為字典，使用該算法對(duì)垃圾廣告評(píng)論和正常評(píng)論進(jìn)行識(shí)別。1.2.1AC自動(dòng)機(jī)的原理AC自動(dòng)機(jī)（Aho-Corasick算法），是由AlfredV.Aho和MargaretJ.Corasick[15]這兩位貝爾實(shí)驗(yàn)室的研究人員在1975年發(fā)明的。這是一種字符串匹配算法，常用于在輸入的字符串中查找匹配有限組“字典”中的子串。但其與普通字符串匹配算法的最大不同點(diǎn)在于該算法會(huì)與所有“字典”中的子串進(jìn)行匹配，即多模匹配。AC自動(dòng)機(jī)算法是由一個(gè)Trie樹構(gòu)成，通過給Trie樹的每個(gè)節(jié)點(diǎn)添加一個(gè)指向該節(jié)點(diǎn)的失敗節(jié)點(diǎn)的指針來實(shí)現(xiàn)的有限狀態(tài)機(jī)。Trie樹，即我們常說的字典樹、前綴樹，很適合用來對(duì)大量的字符串進(jìn)行統(tǒng)計(jì)、排序和存儲(chǔ)，在搜索引擎對(duì)文本中詞頻的統(tǒng)計(jì)有重要應(yīng)用。Trie樹與二叉查找樹比較類似，但它的信息并沒有直接保存在每個(gè)節(jié)點(diǎn)中，而是由節(jié)點(diǎn)在Trie樹中的位置排列來決定的。Trie樹中的任意一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都具有相同的前綴，這個(gè)前綴為該節(jié)點(diǎn)中存儲(chǔ)的字符串，根節(jié)點(diǎn)中的值為空字符串。Trie樹的結(jié)構(gòu)如圖3-11所示：圖3-11Trie樹的結(jié)構(gòu)上圖是一個(gè)由“兼職”、“游戲機(jī)”、“游戲廳”、“游玩”、“的”組成的Trie樹。圖中每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)中的值就是該節(jié)點(diǎn)對(duì)應(yīng)的字符在字符串中的前一個(gè)字符。由此，我們可以總結(jié)出Trie樹的特點(diǎn)：1）根節(jié)點(diǎn)對(duì)應(yīng)的值為空，其余節(jié)點(diǎn)中對(duì)應(yīng)的值都為一個(gè)字符。2）某一個(gè)節(jié)點(diǎn)代表的字符串為從根節(jié)點(diǎn)到該節(jié)點(diǎn)經(jīng)過的所有節(jié)點(diǎn)的字符連接。3）每個(gè)節(jié)點(diǎn)如果有子節(jié)點(diǎn)，則其所有的子節(jié)點(diǎn)都具有不同的字符。為了提高匹配的效率，AC自動(dòng)機(jī)在Trie樹的基礎(chǔ)上引入了失敗指針的概念。例如，對(duì)于上圖中的Trie樹，匹配字符串“上公眾號(hào)兼職”，首先從根節(jié)點(diǎn)開始匹配，經(jīng)過1、2、3、4號(hào)節(jié)點(diǎn)后，成功匹配到了字符串“上公眾號(hào)”，由于4號(hào)節(jié)點(diǎn)已不具有子節(jié)點(diǎn)，匹配完成。此時(shí)若返回根節(jié)點(diǎn)重新匹配，效率較差，若可以從Trie樹上的某個(gè)節(jié)點(diǎn)繼續(xù)匹配，明顯優(yōu)于返回根節(jié)點(diǎn)重新匹配。在這顆樹上，顯然可以從7號(hào)節(jié)點(diǎn)繼續(xù)匹配，然后經(jīng)過8、9節(jié)點(diǎn)，匹配出字符串“公眾號(hào)兼職”。此時(shí)，在4號(hào)節(jié)點(diǎn)處匹配失敗后從7號(hào)節(jié)點(diǎn)處可以繼續(xù)進(jìn)行匹配，則稱7號(hào)節(jié)點(diǎn)是4號(hào)節(jié)點(diǎn)的失敗指針指向的節(jié)點(diǎn)，即失敗節(jié)點(diǎn)。同時(shí)可以看出，從根節(jié)點(diǎn)到7號(hào)節(jié)點(diǎn)組成的字符串為“公眾號(hào)”，是從根節(jié)點(diǎn)到4號(hào)結(jié)果組成的字符串“上公眾號(hào)”的后綴。由于失敗指針指的是當(dāng)前字符串最長的可以在Trie樹上查找到的后綴的末尾字符在Trie樹上對(duì)應(yīng)的節(jié)點(diǎn)，所以可以確定，某一個(gè)節(jié)點(diǎn)的失敗指針指向的節(jié)點(diǎn)對(duì)應(yīng)的深度一定比當(dāng)前節(jié)點(diǎn)的深度小，即位于當(dāng)前節(jié)點(diǎn)的上層。由于根節(jié)點(diǎn)不會(huì)存儲(chǔ)數(shù)據(jù)，并且根節(jié)點(diǎn)不存在父節(jié)點(diǎn)，因此根節(jié)點(diǎn)的失敗指針為空，且不存在失敗節(jié)點(diǎn)。為了保證從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)的失敗指針指向的節(jié)點(diǎn)構(gòu)成的字符串即為需要匹配的字符串的后綴，需要到該節(jié)點(diǎn)的父節(jié)點(diǎn)的失敗節(jié)點(diǎn)中尋找與子節(jié)點(diǎn)匹配的節(jié)點(diǎn)，如果找不到，則繼續(xù)向失敗節(jié)點(diǎn)的失敗指針的方向?qū)ふ铱梢耘c該節(jié)點(diǎn)匹配的節(jié)點(diǎn)，如果一直到了根節(jié)點(diǎn)處還沒有找到，則認(rèn)為根節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)的失敗指針。綜上所述，對(duì)于AC自動(dòng)機(jī)，可以總結(jié)出以下規(guī)則：1）根節(jié)點(diǎn)的失敗指針為空。2）一個(gè)節(jié)點(diǎn)的失敗指針只可能存在于該節(jié)點(diǎn)的上層中。3）需要在父節(jié)點(diǎn)的失敗節(jié)點(diǎn)中尋找與子節(jié)點(diǎn)匹配的節(jié)點(diǎn)。如果匹配的節(jié)點(diǎn)不存在，則沿著失敗節(jié)點(diǎn)繼續(xù)向上，找該節(jié)點(diǎn)的失敗節(jié)點(diǎn)是否存在匹配節(jié)點(diǎn)。如果存在，則該節(jié)點(diǎn)就是子節(jié)點(diǎn)的失敗節(jié)點(diǎn)。4）如果一直到根節(jié)點(diǎn)都沒有找到任何可以匹配的節(jié)點(diǎn)，則失敗指針指向根節(jié)點(diǎn)。因此，對(duì)于上圖中的Trie樹，根據(jù)AC自動(dòng)機(jī)的規(guī)則，可以構(gòu)建出一顆滿足要求的樹，如圖3-12所示：圖3-12AC自動(dòng)機(jī)的構(gòu)建圖中未標(biāo)出的節(jié)點(diǎn)的失敗指向都指向根節(jié)點(diǎn)。1.2.2AC自動(dòng)機(jī)的實(shí)驗(yàn)結(jié)果將關(guān)鍵詞和變體詞構(gòu)成的“字典”導(dǎo)入AC自動(dòng)機(jī)，隨機(jī)抽取4萬條垃圾廣告評(píng)論進(jìn)行測(cè)試，結(jié)果如圖3-13所示：圖3-13對(duì)垃圾廣告評(píng)論測(cè)試結(jié)果隨機(jī)抽取4萬條正常評(píng)論進(jìn)行測(cè)試，結(jié)果如圖3-14所示：圖3-14對(duì)正常評(píng)論測(cè)試結(jié)果對(duì)以上數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，以垃圾廣告評(píng)論為正項(xiàng)，以正常評(píng)論為負(fù)項(xiàng)，采用準(zhǔn)確率、精確率和召回率三種評(píng)價(jià)指標(biāo)，對(duì)AC自動(dòng)機(jī)的性能和效果進(jìn)行分析，對(duì)比結(jié)果如表3-1所示：表3-1不同評(píng)論測(cè)試結(jié)果對(duì)比評(píng)論類型準(zhǔn)確率精確率召回率垃圾廣告評(píng)論82.89%//正常評(píng)論70.37%//任意評(píng)論76.63%71.67%82.89%由上表可知，對(duì)于4萬條垃圾廣告評(píng)論和4萬條正常評(píng)論構(gòu)成的集合，AC自動(dòng)機(jī)可以將63241條評(píng)論正確分類，準(zhǔn)確率為76.63%；對(duì)垃圾廣告評(píng)論的召回率達(dá)到了82.89%，具有一定的垃圾廣告評(píng)論識(shí)別能力；但是卻錯(cuò)誤的將11851條正常評(píng)論認(rèn)定為了垃圾廣告評(píng)論，對(duì)垃圾廣告評(píng)論識(shí)別的精確率僅為71.67%，檢測(cè)結(jié)果并不理想。這是由于垃圾廣告評(píng)論形式多變，可能會(huì)生成更多新的關(guān)鍵詞或者變體詞，由于這些新出的關(guān)鍵詞不在詞庫中，所以無法形成檢測(cè)。同時(shí)，由于正常評(píng)論中也有可能出現(xiàn)關(guān)鍵詞，AC自動(dòng)機(jī)應(yīng)用的特征詞匹配識(shí)別方法會(huì)對(duì)這些正常評(píng)論中的關(guān)鍵詞也進(jìn)行匹配，錯(cuò)誤的將正常評(píng)論認(rèn)定為了垃圾廣告評(píng)論?？紤]到AC自動(dòng)機(jī)的特點(diǎn)，一次匹配中可能會(huì)匹配到多個(gè)關(guān)鍵詞，因此將匹配成功的評(píng)論分為含有一個(gè)關(guān)鍵詞、含有兩個(gè)關(guān)鍵詞、含有三個(gè)及三個(gè)以上關(guān)鍵詞三類，并進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖3-15和3-16所示：圖3-15垃圾廣告評(píng)論關(guān)鍵詞包含結(jié)果圖3-16正常評(píng)論關(guān)鍵詞包含結(jié)果對(duì)圖中數(shù)據(jù)進(jìn)行整理統(tǒng)計(jì)，結(jié)果如表3-2：表3-2關(guān)鍵詞包含數(shù)量占比結(jié)果對(duì)比評(píng)論類型一個(gè)關(guān)鍵詞兩個(gè)關(guān)鍵詞兩個(gè)以上垃圾廣告評(píng)論27.28%26.29%46.43%正常評(píng)論71.67%19.72%6.61%由表中數(shù)據(jù)可知，垃圾廣告評(píng)論大多包含了至少三個(gè)關(guān)鍵詞，少部分垃圾廣告評(píng)論包含了一個(gè)或兩個(gè)關(guān)鍵詞，但是正常評(píng)論只有極少數(shù)包含了兩個(gè)或更多的關(guān)鍵詞，大多數(shù)都因?yàn)橹话艘粋€(gè)關(guān)鍵詞就被篩選出來，極大地干擾了對(duì)垃圾廣告評(píng)論識(shí)別的精確率。但是如果僅規(guī)定包含兩個(gè)關(guān)鍵詞及以上的評(píng)論為垃圾評(píng)論的話，盡管可以極大降低對(duì)正常評(píng)論識(shí)別的出錯(cuò)率，但是卻會(huì)對(duì)垃圾廣告評(píng)論識(shí)別的準(zhǔn)確率造成影響，因此需要對(duì)正常評(píng)論繼續(xù)進(jìn)行分析。對(duì)因?yàn)橐粋€(gè)關(guān)鍵詞被識(shí)別出的正常評(píng)論進(jìn)行分析，發(fā)現(xiàn)其大多是因?yàn)椤百I”、“賣”、“干”這幾個(gè)單字而受到了檢測(cè)，對(duì)正常評(píng)論中被檢測(cè)的評(píng)論使用這幾個(gè)關(guān)鍵詞檢查，結(jié)果如圖3-17所示：圖3-17正常評(píng)論部分單字包含結(jié)果從字典中移除這幾個(gè)關(guān)鍵詞字，使用相同數(shù)據(jù)集再次測(cè)試，結(jié)果如圖：圖3-18垃圾廣告評(píng)論測(cè)試結(jié)果圖3-19正常評(píng)論測(cè)試結(jié)果與移除這幾個(gè)關(guān)鍵詞前的測(cè)試結(jié)果進(jìn)行對(duì)比，結(jié)果如表3-3：表3-3關(guān)鍵詞移除前后測(cè)試結(jié)果對(duì)比類型垃圾廣告數(shù)量誤識(shí)別為垃圾廣告的數(shù)量準(zhǔn)確率精確率召回率移除前331581185176.63%71.67%82.89%移除后32304971278.24%76.88%80.76%對(duì)這幾個(gè)關(guān)鍵詞移除后，正確識(shí)別出的垃圾廣告數(shù)量下降了854條，錯(cuò)誤的將正常評(píng)論誤認(rèn)為是垃圾廣告的數(shù)量下降了2139條，下降幅度遠(yuǎn)高于前者。對(duì)垃圾廣告評(píng)論識(shí)別的準(zhǔn)確率上升了1.61%，精確率上升了1.21%，但召回率下降了2.13%。之所以有這樣的變化，是因?yàn)檎Ｔu(píng)論大多因?yàn)橹话艘粋€(gè)關(guān)鍵詞而被識(shí)別出來，對(duì)這些容易導(dǎo)致誤識(shí)別的關(guān)鍵詞的移除可以極大的降低出錯(cuò)率，而垃圾廣告評(píng)論又都含有兩個(gè)及以上的關(guān)鍵詞，缺少了某個(gè)關(guān)鍵詞也可能會(huì)被其他關(guān)鍵詞匹配出來，因此對(duì)其的影響比正常評(píng)論少。刪除了部分容易導(dǎo)致錯(cuò)誤識(shí)別的關(guān)鍵詞，提高了審查標(biāo)準(zhǔn)，對(duì)于識(shí)別的精確率有了較為明顯的提高，但高的審查標(biāo)準(zhǔn)也使得部分垃圾廣告評(píng)論無法被檢測(cè)，因此導(dǎo)致了召回率的降低。結(jié)合以上結(jié)果進(jìn)行分析，想要提高AC自動(dòng)機(jī)對(duì)于垃圾廣告評(píng)論識(shí)別的精確率和召回率，可以從兩方面入手：1）制定更多具有垃圾廣告評(píng)論特色的關(guān)鍵詞，增加需要匹配的關(guān)鍵詞的數(shù)量來提高召回率。2）移除正常評(píng)論中高頻出現(xiàn)的關(guān)鍵詞，提高精確率。結(jié)合以上兩點(diǎn)，本文提出以下改進(jìn)方法：1）對(duì)正常評(píng)論進(jìn)行特征詞提取，將其中具有較高占比的關(guān)鍵詞從字典中移除。2）以正常評(píng)論提取出的特征詞構(gòu)建AC自動(dòng)機(jī)。3）分別使用垃圾廣告評(píng)論特征詞和正常評(píng)論特征詞構(gòu)建的兩個(gè)AC自動(dòng)機(jī)對(duì)評(píng)論進(jìn)行識(shí)別，并對(duì)垃圾廣告評(píng)論識(shí)別的判定標(biāo)準(zhǔn)做出修改，進(jìn)行如下規(guī)定：（1）若評(píng)論中具有兩個(gè)或兩個(gè)以上的垃圾廣告評(píng)論特征詞，則判定該評(píng)論為垃圾廣告評(píng)論。（2）若評(píng)論中只有一個(gè)垃圾廣告評(píng)論特征詞，當(dāng)該評(píng)論中包含兩個(gè)或兩個(gè)以