馬如義

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

關(guān)鍵詞： 數(shù)據(jù)挖掘； Apriori算法； 詞性標(biāo)注； 規(guī)則

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

1 Apriori算法及問題描述

1.1 Apriori算法

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

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

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

1.2 問題描述

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

⑴ 詞性標(biāo)記集Tags={Tagi|i=1，2，…，m}，詞集Dwords={Wordi|i=1，2，…，n}，項(xiàng)集I=DwordsUTags，其中Wordi、Tagi分別為某個(gè)詞和詞性標(biāo)記。

⑵ 已標(biāo)記的文本T={（Wordi，Tagi）|Wordi∈Dwords，Tagi∈Tags}，Tagi是詞Wordi在該標(biāo)記文本中對應(yīng)的詞性標(biāo)記。

⑶ 模式集D={d|d∈I}，表示由詞與詞性標(biāo)記組合構(gòu)成的串。

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

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

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

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

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

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

2 Apriori算法的實(shí)現(xiàn)及應(yīng)用

2.1 Apriori算法的實(shí)現(xiàn)

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

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

Step1：選取模擬數(shù)據(jù)集，并設(shè)置項(xiàng)目集為I={“前一詞”，“前一詞詞性”，“當(dāng)前詞”，“當(dāng)前詞詞性”，“后一詞”，“后一詞詞性”}，用Apriori算法實(shí)現(xiàn)頻繁項(xiàng)集、關(guān)聯(lián)規(guī)則的獲取。

Step2：基于該模擬數(shù)據(jù)集，輸入最小的支持度閾值為10（經(jīng)多次實(shí)驗(yàn)選?。?，掃描項(xiàng)目集，對每個(gè)候選集進(jìn)行計(jì)數(shù)，丟棄小于最低支持度的候選集，進(jìn)而得到頻繁1-項(xiàng)集的集合L1。L1中的數(shù)據(jù)表示各個(gè)詞、詞性出現(xiàn)的次數(shù)。

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

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

2.2 模型程序設(shè)計(jì)

本設(shè)計(jì)項(xiàng)目集為6-itemset，即L6={“前一個(gè)詞”，“前一個(gè)詞的詞性”，“當(dāng)前詞”，“當(dāng)前詞詞性”，“后一個(gè)詞”，“后一個(gè)詞的詞性”}，并根據(jù)Apriori算法設(shè)計(jì)了相應(yīng)的模型程序，其模型程序架構(gòu)如圖1所示。

圖1 模型程序架構(gòu)

⑴ Main函數(shù)負(fù)責(zé)程序的整體運(yùn)行，如調(diào)用程序初始化、項(xiàng)目集計(jì)算、關(guān)聯(lián)規(guī)則算法、相關(guān)信息的輸出操作等。

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

⑶ print（）函數(shù)用于返回需要輸出的相關(guān)信息。

⑷ createTransRule（）函數(shù)用于創(chuàng)建關(guān)聯(lián)規(guī)則。

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

模式二：表示前一詞或前一詞性對當(dāng)前詞性的影響。

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

模式三：表示前兩詞或詞性的組合對當(dāng)前詞的詞性的影響。

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

模式六：表示{“前一個(gè)詞”，“前一個(gè)詞的詞性”，“當(dāng)前詞”，“當(dāng)前詞詞性”，“后一個(gè)詞”，“后一個(gè)詞的詞性”}出新的次數(shù)。

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)（References）：

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

[2] ZhaoHui Tang.數(shù)據(jù)挖掘原理與應(yīng)用[M].清華大學(xué)出版社，

2007.

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

現(xiàn)[D].新疆大學(xué)，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] 李曉黎，史忠植.用數(shù)據(jù)采掘方法獲取漢語詞性標(biāo)注規(guī)則[J].

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

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

2009.

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

[8] 鄧景毅.關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J].電腦學(xué)習(xí)報(bào)，2006.4：4-5