Apriori算法在詞性標注規(guī)則獲取中的應用

馬如義

摘 要： 人工方法獲取的規(guī)則準確率有待驗證，所以從數據挖掘的角度運用Apriori算法對詞性標注規(guī)則的獲取進行研究。用戶根據需求自定義支持度與置信度，在滿足規(guī)定支持度的前提下，先從候選集模式中挑選出高于支持度的模式，再挖掘出高于置信度的產生式規(guī)則，獲取的規(guī)則是隱含在數據中不易被發(fā)現的，其表達上是明確的。實驗表明，自動獲取的標注規(guī)則具有很好的利用價值，可以提高詞性標注的正確率。

關鍵詞： 數據挖掘； Apriori算法； 詞性標注； 規(guī)則

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2016）10-32-04

Application of Apriori algorithm to obtain part-of-speech tagging rules

Ma Ruyi

（Computer Department Qinghai University for Nationalities， Xining， Qinghai 810007， China）

Abstract： The correct rate of the artificially obtained rules need to be verified， so from the point of view of data mining， using Apriori algorithm to obtain the rules of part-of-speech tagging is researched in this paper. User defines their support and confidence according to the requirements， in the premise of meeting the support provided， a mode that is higher than the support is selected from the candidate mode set， and the production rule that is higher than the confidence is dug out， the rule is hidden in the data and not easy to be found， but its expression is clear. Experiments show that the tagging rules automatically obtained have a good utility value， and can improve the correct rate of part-of-speech tagging.

Key words： data mining； Apriori algorithm； part-of-speech tagging； rule

0 引言

數據挖掘[1]是從大量的數據中提取或“挖掘”知識。具體來說，數據挖掘就是從大量的、隨機的、模糊的、不完全的、有噪聲的數據中，提取隱含在其中的、潛在有用的、事先不為人知道的知識和信息的過程[2]。詞性標注是自然語言處理的一個重要環(huán)節(jié)，其任務是為句子中的每一個詞標注一個正確的詞性，此環(huán)節(jié)出現的錯誤，將在后續(xù)的句法分析、機器翻譯等處理中被放大[3]。詞性標注迄今為止已經有很多方法，有基于規(guī)則、統(tǒng)計以及規(guī)則與統(tǒng)計相結合的方法[4]。

規(guī)則的獲取一般由人工整理集成，但這存在以下兩方面的問題[5]：①從規(guī)則的應用范圍上看，靠人工的方法只可能產生一些共性規(guī)則，不可能產生針對個別情況的個性規(guī)則，而個性規(guī)則盡管應用范圍小，但也是提高正確率的重要手段；②由于人工方法獲取的規(guī)則準確率有待驗證，因此在基于統(tǒng)計方法正確率不易再提高的前提下，能否自動高效地獲取規(guī)則是實現詞性標注中的關鍵問題。

本文對于詞性標注規(guī)則的獲取不需要進行維數與層次分析，也不需要采用分而治之的方法，而是采用了最基本的Apriori算法，從人工已標注好的語料中來研究詞性及詞的模式序列對詞性的影響。該方法與人們利用語料上下文中的詞、詞性等信息來對詞性進行判斷的方法是一致的。在統(tǒng)計語料規(guī)模較大的情況下，給定最小支持度及最小可信度后，首先挖掘大于最小支持度的常用模式集，然后生產關聯規(guī)則，若此規(guī)則的可信度大于最小可信度，則得到詞性規(guī)則。如果最小可信度定義的足夠高，則獲得的規(guī)則能夠作為概率方法的補充，從而較好地解決詞性標注問題。但由于該規(guī)則的挖掘是在文本數據中進行的，同時它又依賴于詞性與詞的各種組合，這使得其挖掘過程較數據庫中的數據挖掘復雜得多[5]。

1 Apriori算法及問題描述

1.1 Apriori算法

Agrawal等人[6]于1993年首先提出了挖掘顧客交易數據庫中項集間的關聯規(guī)則問題，設計了基于頻繁集理論的Apriori算法[7]。Apriori算法是一種最有影響力的挖掘布爾關聯規(guī)則頻繁項集的算法。其核心是基于兩個階段頻繁項集思想的遞推算法，該算法的設計分解為兩個子問題：①找到所有支持度大于最小支持度的項集（itemset），這些項集稱為頻繁集（frequent itemset）；②根據最小的置信度和找到的頻繁項集產生關聯規(guī)則。

關聯規(guī)則的一般形式為[8]：X=>Y，其含義為X的出現同時也導致Y的出現。對于關聯規(guī)則X=>Y，其支持度的表現形式為sup（X=>Y）=P（X∪Y）=sup（X∪Y），即交易集中同時包含X、Y的交易總數在所有交易總數中所占的比值；置信度的表現形式為conf（X=>Y）=P（Y|X）=sup（X∪Y）/sup（X），即同時包含X、Y的交易總數與只包含X的交易總數的比值。其中支持度是對關聯規(guī)則重要性的一種表示，而置信度又可稱為可信度，是對關聯規(guī)則準確度的一種表示，其取值范圍在0到1之間。它們都由用戶根據需求自己進行設置。

Apriori算法的第二步比較容易，一般經過第一步篩選后的頻繁項集都不會很多，通過子集產生法就可以產生關聯規(guī)則。而第一步需要在大量的事務數據集中尋找出現頻率較高的項集Itemset，這可能要求多次掃描交易較大的數據庫，所以就需要一個比較高效的搜索方法。故可能產生大量的候選集，以及需要重復掃描數據庫，是Apriori算法的兩大缺點。

1.2 問題描述

為了使詞性標注的規(guī)則能夠更好的在語料中被挖掘出來，本文給出了以下描述。

⑴ 詞性標記集Tags={Tagi|i=1，2，…，m}，詞集Dwords={Wordi|i=1，2，…，n}，項集I=DwordsUTags，其中Wordi、Tagi分別為某個詞和詞性標記。

⑵ 已標記的文本T={（Wordi，Tagi）|Wordi∈Dwords，Tagi∈Tags}，Tagi是詞Wordi在該標記文本中對應的詞性標記。

⑶ 模式集D={d|d∈I}，表示由詞與詞性標記組合構成的串。

⑷ 若X∈D，且長度Lenth（X）=K，則模式X為K模式。

⑸ 若X∈D，F={Y|Y∈D，且Lenth（X）=Lenth（Y）}，則為模式X的支持度，它反映了該模式在同長度模式中所占的比例。其中freq（X）表示模式X出現的頻率，total（F）表示長度為Lenth（X）的模式出現的總頻率。

⑹ 令min_sup為用戶最小支持度，則集合C={X|X∈D，sup（X）≥min_sup}，稱X為頻繁項目集。

⑺ 若X，Y為大模式，且X，Y之間的關聯，記為規(guī)則X=>Y，該規(guī)則的可信度，其支持度為sup（X∪Y）。其中freq（XY）表示模式X，Y同現的頻率。

⑻ 令min_conf為用戶規(guī)定的最小可信度，若，則規(guī)則是值得該用戶信賴的產生式規(guī)則。

⑼ 取k模式，并且ak∈Tags，ak是詞k的詞性標記，則在文本中采取的規(guī)則形式為：，它表明若前k-1個詞、標記構成的模式等于a1，a2，…，ak-1，則第k個詞（詞k）的詞性標記用該為ak。

2 Apriori算法的實現及應用

2.1 Apriori算法的實現

基于Apriori算法的數據挖掘與數據庫中的數據挖掘不同，訓練集中僅長度為i（i模式）的子串，其詞與詞性的組合就有2i個，由此可見隨著模式長度的不斷增加，其對應長度的模式總數也急劇增加，所以最小支持度和可信度不應該是一成不變的，它們應隨模式長度的增加而減少，但對最小可信度的要求，不但不因模式長度的增加而減少，而且由于長模式應用范圍較小，必須保證其可信度比短模式的可信度高，否則將得不償失[5]。

由于該數據挖掘是在文本數據的基礎上進行操作的，所以，為了提高操作效率，本文對數據僅掃描一遍，其操作如下：首先，基于模擬數據集，用戶自己設置最小支持度，找出符合條件的頻繁項目集；然后，再定義一個衡量置信度的閾值，基于上一步產生的頻繁項目集，運用Apriori算法挖掘出支持度和置信度分別大于用戶給定的最小支持度（min_sup）和最小置信度（min_conf）的關聯規(guī)則。該算法的操作實現步驟如下。

Step1：選取模擬數據集，并設置項目集為I={“前一詞”，“前一詞詞性”，“當前詞”，“當前詞詞性”，“后一詞”，“后一詞詞性”}，用Apriori算法實現頻繁項集、關聯規(guī)則的獲取。

Step2：基于該模擬數據集，輸入最小的支持度閾值為10（經多次實驗選取），掃描項目集，對每個候選集進行計數，丟棄小于最低支持度的候選集，進而得到頻繁1-項集的集合L1。L1中的數據表示各個詞、詞性出現的次數。

Step3：由L1連接、剪枝產生候選C2，掃描項目集。對C2中每個候選集計數，小于最低支持度的候選數據集將會被丟棄，從而產生頻繁2-項集的集合L2。L2中的數據表示詞、詞性兩兩連接后出現的次數。以此類推求解候選C3、C4、C5、C6，進而得到頻繁項集集合L3、L4、L5、L6。

Step4：基于頻繁6-項集，輸入最小可信度值生成關聯規(guī)則。對于每一個頻繁項集L，找出其中所有的非空子集；然后，根基置信度計算公式confidence（A?B）=P（B|A）=support_count（AUB）/support_count（A），計算每一個子集a的置信度，如果support（L）與support（a）的比值大于最小可信度，則存在規(guī)則a==>（L-a），否則不存在關聯。

2.2 模型程序設計

本設計項目集為6-itemset，即L6={“前一個詞”，“前一個詞的詞性”，“當前詞”，“當前詞詞性”，“后一個詞”，“后一個詞的詞性”}，并根據Apriori算法設計了相應的模型程序，其模型程序架構如圖1所示。

圖1 模型程序架構

⑴ Main函數負責程序的整體運行，如調用程序初始化、項目集計算、關聯規(guī)則算法、相關信息的輸出操作等。

⑵ Apriori（）構造函數用于創(chuàng)建圖形用戶界面。

⑶ print（）函數用于返回需要輸出的相關信息。

⑷ createTransRule（）函數用于創(chuàng)建關聯規(guī)則。

⑸ createL1（）、createL2（）、createL3（）、createL4（）、createL5（）、createL6（）六個函數用于創(chuàng)建頻繁集。

⑹ removeNotSupportKey（）函數用于刪除鍵值小于最小支持度的鍵。

⑺ findKey（Set keyset，String a， String b， String c，String d， String e， String f）函數用于在健集keyset里查找健值為a，b，c，d，e，f的健。

⑻ contain（Set keyset，String a，String b，String c，String d，String e，String f） 函數用于判斷在健集keyset里是否已經包含了健值為a，b，c，d，e，f的健。

⑼ getMinusCollect（String[] a， String[] L） 函數用于求a與L的差集。

⑽ getSubSet（String setN[]）函數用于獲取setN的子集。

3 實驗結果與分析

語料使用《新疆日報》維語版，題材涉及政治、經濟、體育、衛(wèi)生、文化、藝術、娛樂等。目前該語料已完成詞干切分、詞綴提取，以及部分詞性標注。

根據數據挖掘中的Apriori方法，從本文獲取的模擬數據集中，分別對各長度模式進行挖掘，并對最終的模式設置最小支持度和置信度，從中挖掘出詞性標注的規(guī)則。從挖掘出的規(guī)則可以看出，詞、詞性及詞與詞性的組合對當前詞詞性的影響。下面對部分長度模式進行說明。

模式一：表示單個詞或詞性的出現次數，其中出現次數前三位的為：n，v，adj。由于一模式中未利用上下文信息，因而不構成規(guī)則。

模式二：表示前一詞或前一詞性對當前詞性的影響。

獲取的標注規(guī)則為：if（wordi，adv） then（word2，n），這說明若前一詞詞性為副詞，則其后一詞的詞性為名詞。

模式三：表示前兩詞或詞性的組合對當前詞的詞性的影響。

獲取的規(guī)則為：if（詞性1，v）and（詞2，“”）then（詞3，n）。

模式六：表示{“前一個詞”，“前一個詞的詞性”，“當前詞”，“當前詞詞性”，“后一個詞”，“后一個詞的詞性”}出新的次數。

通過對不同長度模式的比較可以清楚的看出詞在模式中的限制作用。

從實驗數據可以看出：每種模式的組合隨著模式長度的不斷增加其組合的絕對數量也不斷增加。由于受到較多的上下文制約，模式的支持度降低、可信度增加，而且詞性能夠被惟一確定的可能性也增加了。

由于詞及其對應的詞性出現的次數遠遠沒有一個詞性單獨出現的次數要多，所以，用詞上下文信息中的詞性做制約對應的情況更多、更復雜，不利于對兼類詞詞性進行消歧，而詞作為上下文的因素之一對詞性的影響更大，即對詞性的限制更加精確。一般來說，模式中詞對詞性的影響更大一些，故含詞的模式的支持度要更小一些。

為了進行實驗比較，本文先用最大熵的方法對上述語料進行標注，準確為92.01%。根據獲取的標注規(guī)則，在最大熵模型標注的基礎上，對標注結果進行了優(yōu)化，準確為93.13%，優(yōu)于單純用基于統(tǒng)計的最大熵方法標注的結果。

4 結束語

本文采用數據挖掘方法，對詞性規(guī)則的自動獲取進行了有益嘗試，獲取的規(guī)則能夠對詞性的正確標注起到很好的輔助作用。該方法是一種從語料庫中以規(guī)則的形式獲取知識的新方式，較適用于大規(guī)模語料庫，為后續(xù)數據挖掘方法在自然語言處理中的應用提供了新思路。該方法的缺點是，一定程度上依賴于訓練語料的規(guī)模，而且對于多次掃描的效率較低，這些問題有待進一步研究。

參考文獻（References）：

[1] 蔣海昆.數據挖掘過程的研究[J].福建電腦，2007.3：67-74

[2] ZhaoHui Tang.數據挖掘原理與應用[M].清華大學出版社，

2007.

[3] 買合木提·買買提.基于統(tǒng)計的維吾爾語詞性標注研究與實

現[D].新疆大學，2009.

[4] Liu S，Chen L et al.Automatic part-of-speech tagging for

Chinese corpus.Computer progressing of Chinese and Oriental Languages，1955.9（1）：31-47

[5] 李曉黎，史忠植.用數據采掘方法獲取漢語詞性標注規(guī)則[J].

計算機研究與發(fā)展，2000.37（2）：1409-1414

[6] 許婭.關聯規(guī)則更新算法研究與應用[D].合肥工業(yè)大學，

2009.

[7] 楊光.關聯規(guī)則挖掘算法研究[D].大連交通大學，2005.

[8] 鄧景毅.關聯規(guī)則數據挖掘[J].電腦學習報，2006.4：4-5