數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則在詞語關(guān)聯(lián)度計算中的應(yīng)用

董晨輝，師文慧

(福建寧德核電有限公司，福建 寧德 355200)

0 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)挖掘引起了信息產(chǎn)業(yè)界的廣泛關(guān)注。關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘的一個研究方向，廣泛應(yīng)用于銷售行業(yè)，如：購物籃分析、分類設(shè)計、捆綁銷售和虧本銷售分析等。它是以大規(guī)模事物關(guān)系庫為基礎(chǔ)，發(fā)現(xiàn)其項(xiàng)集之間頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。

移動通信技術(shù)與社交媒體的發(fā)展，使得中文短文本形式的信息廣泛滲透于社會和生活的各個領(lǐng)域。由于這些短文本字?jǐn)?shù)較少，因而所描述的概念信號弱、特征信息模糊，單從字面上難以獲取有效的特征信息，需要對文本進(jìn)行更深層次的分析。

詞語的關(guān)聯(lián)度計算已應(yīng)用到信息檢索、人工智能等多個領(lǐng)域，為文本信息挖掘和自然語言處理奠定了基礎(chǔ)。但傳統(tǒng)的方法對關(guān)聯(lián)度計算所度量的關(guān)系不明確，多數(shù)以相似度為基礎(chǔ)，而相似度只是關(guān)聯(lián)度的一個特例，只包括詞語之間的上下位關(guān)系和同義關(guān)系，易造成關(guān)聯(lián)度計算的局限性和不準(zhǔn)確性。

由于詞語特征信息稀疏，因此計算詞語間關(guān)聯(lián)度是一項(xiàng)復(fù)雜而艱難的任務(wù)，需要大量的外部資源作為支撐，以便對詞語特征進(jìn)行擴(kuò)充。有些方法是以外部知識庫為基礎(chǔ)來計算詞語間關(guān)聯(lián)度[1]，有些方法是通過對大型語料庫進(jìn)行統(tǒng)計分析來實(shí)現(xiàn)[2]，有些方法則使用經(jīng)過手工處理得出的語匯結(jié)構(gòu)實(shí)現(xiàn)，如同義詞典[3]、HowNet[4]。這些方法均沒有涉及數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則。

因此，本文以新聞?wù)Z料為外部數(shù)據(jù)庫，提出了一種利用數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則來計算詞語之間的關(guān)聯(lián)度的計算方法，以挖掘各詞語之間頻繁出現(xiàn)的關(guān)聯(lián)性。

1 關(guān)聯(lián)規(guī)則介紹

關(guān)聯(lián)規(guī)則挖掘問題是Agrawal R等人于1993年首先提出來的[5]，是指從巨量的信息資源中尋找隱含在數(shù)據(jù)項(xiàng)集間的有趣聯(lián)系或關(guān)聯(lián)關(guān)系，描述在一個事務(wù)中的物品之間同時出現(xiàn)的規(guī)律的知識模式。其表達(dá)式為：設(shè)I={i1，i2，i3，…，im}是所有項(xiàng)的集合；設(shè)D是事務(wù)T的集合，其中每個事務(wù)T是項(xiàng)I的子集，使得T?I。其包含的相關(guān)概念如下。

①支持度：事務(wù)集D中包含XUY的百分比。

(1)

其中，|D|等于D中事務(wù)T的個數(shù)。

②置信度：在含有物品X的事務(wù)T中含有物品Y的概率。

(2)

③期望可信度：無任何條件影響下，物品X在事務(wù)集D中出現(xiàn)的概率。

(3)

④作用度：描述物品X對物品Y的影響力，反映了Y對于X的依賴程度。

(4)

⑤關(guān)聯(lián)規(guī)則挖掘：從事務(wù)集合中挖掘出滿足支持度和置信度最低閾值(minsup，minconf)要求的所有關(guān)聯(lián)規(guī)則，這樣的關(guān)聯(lián)規(guī)則也稱強(qiáng)關(guān)聯(lián)規(guī)則。

⑥頻繁項(xiàng)集(frequent itemsets)。如果項(xiàng)集的頻率大于“最小支持度×D中的事務(wù)總數(shù)”，則稱該項(xiàng)集為頻繁項(xiàng)集[6]。

2 詞匯社區(qū)結(jié)構(gòu)的構(gòu)建

關(guān)聯(lián)規(guī)則的挖掘過程主要包含兩個階段：第一階段，先從資料集合中找出所有頻繁項(xiàng)集；第二階段，由這些高頻項(xiàng)目組中產(chǎn)生關(guān)聯(lián)規(guī)則，即滿足最小支持度和最小置信度的規(guī)則。

利用關(guān)聯(lián)規(guī)則計算短文本的關(guān)聯(lián)度，這一類方法的理論基礎(chǔ)是Firth在文獻(xiàn)[7]提出的上下文假設(shè)：詞匯的上下文環(huán)境體現(xiàn)的是人們在實(shí)際語言交流中使用該詞匯的具體途徑，并且兩個詞匯的使用方式越接近，在語義上就越相關(guān)?；谶@一理論便可以通過統(tǒng)計大規(guī)模語料中詞匯出現(xiàn)的規(guī)律得到詞語間的關(guān)聯(lián)度，即通過在大規(guī)模語料中統(tǒng)計詞匯所處的上下文環(huán)境，得到每個詞匯的上下文分布，而兩個詞匯的語義相關(guān)度則通過比較二者對應(yīng)的上下文分布并綜合分析后得出最終結(jié)果。

關(guān)聯(lián)規(guī)則一般用來發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品(項(xiàng))之間的聯(lián)系。將大規(guī)模語料庫(人民日報2013-2014年語料庫)作為交易數(shù)據(jù)庫，每篇新聞中出現(xiàn)的實(shí)詞集合作為事務(wù)，出現(xiàn)的每個詞語認(rèn)為是商品，便可以找出兩詞語間的聯(lián)系。在中文語料中，將交易中的頻繁項(xiàng)集認(rèn)為是關(guān)聯(lián)度高的詞匯所構(gòu)造的一個詞匯社區(qū)，根據(jù)人民日報2013-2014年語料庫構(gòu)造的社區(qū)結(jié)構(gòu)就是新聞中共同出現(xiàn)頻率高的詞語集合，詞匯社區(qū)結(jié)構(gòu)如圖1所示，其中橢圓的大小代表社區(qū)的大小，橢圓的包含關(guān)系代表社區(qū)的包含關(guān)系。

圖1 詞匯社區(qū)結(jié)構(gòu)

構(gòu)造詞匯社區(qū)結(jié)構(gòu)作為關(guān)聯(lián)規(guī)則挖掘的第一階段，它的原理是根據(jù)k-頻繁項(xiàng)集生成(k+1)-頻繁項(xiàng)集。主要任務(wù)是從原始資料集合中找出頻繁項(xiàng)集。頻繁的意思是指某一項(xiàng)目組出現(xiàn)的頻率必須達(dá)到某一水平，即其支持度不小于最小支持度(minsup)。以一個包含A與B兩個項(xiàng)目的2-itemset為例，根據(jù)公式(1)可求得包含{A，B}項(xiàng)目組的支持度，若支持度大于等于所設(shè)定的最小支持度這一閾值時，則{A，B}稱為頻繁項(xiàng)集。一個滿足最小支持度的k-itemset，則稱為k-頻繁項(xiàng)集，一般表示為Large k或Frequent k。算法是從Large k的項(xiàng)目組中再產(chǎn)生Large(k+1)，直到無法再找到更長的頻繁項(xiàng)集為止，這樣一個詞匯社區(qū)結(jié)構(gòu)就形成了。

3 選用的算法

Apriori算法和FP-tree算法是關(guān)聯(lián)規(guī)則挖掘中最經(jīng)典的兩個算法，前者采用逐層搜索的迭代策略，先產(chǎn)生候選集，再對候選集進(jìn)行篩選，然后產(chǎn)生該層的頻繁集；后者采取模式增長的遞歸策略，不用產(chǎn)生侯選集，而是把事務(wù)數(shù)據(jù)庫壓縮到一個只存儲頻繁項(xiàng)的樹結(jié)構(gòu)中。FP-growth算法是韓家煒等人在2000年提出的關(guān)聯(lián)分析算法[8]，算法基于Apriori算法構(gòu)建，但采用了高級的數(shù)據(jù)結(jié)構(gòu)以減少掃描次數(shù)，在不生成候選項(xiàng)的情況下，完成Apriori算法的功能，大大加快了算法速度。因此，本文選擇FP-growth算法進(jìn)行詞語關(guān)聯(lián)度的計算。FP-growth算法發(fā)現(xiàn)頻繁項(xiàng)集的基本過程如下。

3.1 構(gòu)建FP樹

構(gòu)建FP樹，即是把事務(wù)數(shù)據(jù)表中的各個事務(wù)數(shù)據(jù)項(xiàng)按照支持度降序排序后，依次插入到一棵以NULL為根結(jié)點(diǎn)的樹中，同時在每個結(jié)點(diǎn)處記錄該結(jié)點(diǎn)出現(xiàn)的支持度。圖2為構(gòu)建FP樹的過程示意圖。

圖2 構(gòu)建FP樹的過程示意圖

①輸入：數(shù)據(jù)集、最小值尺度。輸出：FP樹、頭指針表(inTree，headerTable)。遍歷數(shù)據(jù)集，統(tǒng)計各元素項(xiàng)的出現(xiàn)次數(shù)，創(chuàng)建頭指針表。②移除頭指針表中不滿足最小值尺度的元素項(xiàng)。③第二次遍歷數(shù)據(jù)集，創(chuàng)建FP樹。對每個數(shù)據(jù)集中的項(xiàng)集：第一，初始化空FP樹；第二，對每個項(xiàng)集進(jìn)行過濾和重排序；第三，使用這個項(xiàng)集更新FP樹，從FP樹的根節(jié)點(diǎn)開始，如果當(dāng)前項(xiàng)集的第一個元素項(xiàng)存在于FP樹當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)中，則更新這個子節(jié)點(diǎn)的計數(shù)值；否則，創(chuàng)建新的子節(jié)點(diǎn)，更新頭指針表。對當(dāng)前項(xiàng)集的其余元素項(xiàng)和當(dāng)前元素項(xiàng)的對應(yīng)子節(jié)點(diǎn)遞歸第三的過程。

3.2 從FP樹中挖掘頻繁項(xiàng)集

3.2.1 算法1：通過構(gòu)造條件樹查找頻繁項(xiàng)集

①從FP樹中獲得條件模式基；②利用條件模式基，構(gòu)建一個條件FP樹；③迭代重復(fù)步驟①和步驟②，直到樹包含一個元素項(xiàng)為止。

其中的條件模式基是指包含F(xiàn)P-Tree中與后綴模式一起出現(xiàn)的前綴路徑的集合，也就是同一個頻繁項(xiàng)在PF樹中的所有節(jié)點(diǎn)的祖先路徑的集合。比如在圖2中糖果在FP樹中一共出現(xiàn)了3次，其祖先路徑分別是{中國，春節(jié)，鞭炮：20(頻度為20)}，{中國，鞭炮：5}和{春節(jié)：15}。這3個祖先路徑的集合就是頻繁項(xiàng)“糖果”的條件模式基。然后，將所獲得的條件模式基按照FP-Tree的構(gòu)造原則形成一個新的FP-Tree，稱為條件樹，如圖3所示。

圖3 條件樹示意圖

3.2.2 算法2：遞歸查找頻繁項(xiàng)集

輸入：有當(dāng)前數(shù)據(jù)集的FP樹(inTree，headerTable)。

①初始化一個空列表preFix表示前綴。②初始化一個空列表freqItemList，接收生成的頻繁項(xiàng)集(作為輸出)。③對headerTable中的每個元素basePat(按計數(shù)值由小到大排列)進(jìn)行遞歸：記basePat+preFix為當(dāng)前頻繁項(xiàng)集newFreqSet；將newFreqSet添加到freqItemList中；計算t的條件FP樹(myCondTree，myHead)；當(dāng)條件FP樹不為空時，繼續(xù)下一步，否則退出遞歸；以myCondTree，myHead為新的輸入，以newFreqSet為新的preFix，外加freqItemList，遞歸這個過程。

4 詞語間相關(guān)度的計算

本文基于數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘提出計算詞語間關(guān)聯(lián)度的方法。記|D(X)|為含有詞語X的新聞報道的篇數(shù)，可得出：

(1)詞語A，B的支持度反映詞語A與B的共現(xiàn)程度。如果A與B同時出現(xiàn)的概率小，說明A與B的關(guān)系不大；如果A與B共現(xiàn)頻率較高，則說明A與B是相關(guān)的。

(5)

其中，|D|等于數(shù)據(jù)庫D中新聞報道的總篇數(shù)；|D(A∪B)|為數(shù)據(jù)庫中共同含有詞語A和B的新聞報道的篇數(shù)。

(2)一部分詞對在重要程度上是不對稱的，例如，“中國”和“北京”相互之間的依賴程度是對稱的，因?yàn)椤氨本笔恰爸袊钡氖锥?；相反，位于四川省邛崍市的“白楊村”和“中國”相互之間依賴程度是不對稱的，“白楊村”對“中國”的依賴程度大于“中國”對“白楊村”的依賴程度。A出現(xiàn)時B出現(xiàn)的概率可用詞語A，B的置信度來表示。置信度“A?B”并不等于置信度“B?A”。

(6)

(3)期望可信度描述了在所有報道中詞語A出現(xiàn)的概率。

(7)

(4)詞語A對B的作用度描述了A對B的影響力的大小。作用度越大關(guān)聯(lián)性也就越強(qiáng)。一般情況，只有關(guān)聯(lián)規(guī)則的置信度大于期望可信度，才說明A對B有促進(jìn)作用，也說明它們之間存在某種程度的關(guān)聯(lián)性。如果作用度值等于1，說明兩個條件沒有任何關(guān)聯(lián)；如果小于1，說明在詞語A出現(xiàn)的前提下，詞語B出現(xiàn)的概率降低，即詞語A對詞語B并沒有促進(jìn)作用，詞語A與詞語B是相斥的。一般在數(shù)據(jù)挖掘中當(dāng)作用度大于3時，才承認(rèn)挖掘出的關(guān)聯(lián)規(guī)則是有價值的。

(8)

結(jié)合詞語A，B之間的支持度以及置信度，可以給出計算兩詞語關(guān)聯(lián)度的計算公式：當(dāng)Lift(A?B)和Lift(B?A)其中有一個為零，詞語A與詞語B的關(guān)聯(lián)度記為0；當(dāng)Lift(A?B)>1并且Lift(B?A)>1時，詞語A與B之間的關(guān)聯(lián)度計算公式為：

(9)

5 實(shí)驗(yàn)驗(yàn)證

5.1 數(shù)據(jù)準(zhǔn)備

在數(shù)據(jù)挖掘這一過程中，數(shù)據(jù)準(zhǔn)備作為第一步，也是這一過程中的核心。數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù)，數(shù)據(jù)準(zhǔn)備是否做好直接影響到數(shù)據(jù)挖掘的效率和準(zhǔn)確度，以及最終結(jié)果的有效性。

數(shù)據(jù)集選擇的是人民日報2013-2014年語料庫，語料庫為已標(biāo)注好的新聞報道，但并不適合直接在這些數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘，仍需要對語料進(jìn)行清洗加工。詞語關(guān)聯(lián)度主要針對于有實(shí)際意義的特征詞，因此第一步凈化包含的步驟主要有去停用詞、過濾虛詞等；第二步為縮減，主要目的為消除新聞報道中重復(fù)的詞語，消除冗余數(shù)據(jù)；第三步為轉(zhuǎn)換，主要是將經(jīng)過加工處理的語料轉(zhuǎn)換成數(shù)據(jù)庫文件，然后在此基礎(chǔ)上進(jìn)行數(shù)據(jù)挖掘。關(guān)于詞語關(guān)聯(lián)度計算的測試集選用了人工翻譯WordSimilarity-353測試集[9]以及北京理工大學(xué)所統(tǒng)計的Words-240[10]。

5.2 實(shí)驗(yàn)過程

本實(shí)驗(yàn)硬件環(huán)境為雙核T6 Intel處理器、主頻2.80 GHz、內(nèi)存為4 GB，編程環(huán)境為MyEclipse，數(shù)據(jù)庫使用的是MySQL。通過挖掘強(qiáng)關(guān)聯(lián)規(guī)則，可以拓展詞語的長度，增加特征數(shù)，從而減輕特征稀疏性對關(guān)聯(lián)度計算結(jié)果產(chǎn)生的影響。

社區(qū)規(guī)?？梢酝ㄟ^設(shè)置不同的最小支持度以及最小置信度來改變。規(guī)模較小的社區(qū)包含了緊密的語義相關(guān)的互聯(lián)節(jié)點(diǎn)，它們通常隸屬于同一主題。社區(qū)結(jié)構(gòu)規(guī)模與支持度閾值的關(guān)系如圖4所示。利用“試錯”法選取合適的閾值，支持度越大，社區(qū)規(guī)模越小，語義節(jié)點(diǎn)間也更為緊密。

圖4 社區(qū)結(jié)構(gòu)規(guī)模與支持度閾值的關(guān)系圖

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

根據(jù)上述計算方法，實(shí)現(xiàn)了關(guān)聯(lián)規(guī)則在詞語關(guān)聯(lián)度計算中的應(yīng)用。部分詞對關(guān)聯(lián)度的計算結(jié)果如表1所示。

表1 部分詞對關(guān)聯(lián)度計算結(jié)果

通過分析表1，可以看出實(shí)驗(yàn)結(jié)果有一定的合理性，符合人們主觀上的判斷。

(1)該計算方法解決了依賴程度不對稱詞語間關(guān)聯(lián)度的計算問題，例如“中國”與“春節(jié)”，“春節(jié)”對于“中國”的依賴程度高于“中國”對于“春節(jié)”的依賴程度。

(2)從計算結(jié)果可以看出詞語的支持度都比較小，這是由于新聞?wù)Z料中出現(xiàn)的詞語過于龐大造成的，但支持度的大小并不影響關(guān)聯(lián)度計算的結(jié)果。

(3)該計算方法是通過對大規(guī)模語料庫進(jìn)行統(tǒng)計分析從而得到詞語間關(guān)聯(lián)度，因此沒有考慮詞語語義這一層面，例如“蘋果”與“橘子”、“蘋果”與“手機(jī)”這兩個詞對中“蘋果”的語義并不相同，但在計算時并不考慮深層的語義信息。

圖5為該計算方法與WikiRelate[11]，ESA[12]和WLM[13]計算準(zhǔn)確率的對比結(jié)果，表2為該計算方法與WikiRelate[11]，GooRel[14]方法所計算出的Spearman相關(guān)系數(shù)的對比。從圖5可以看出本文計算方法的準(zhǔn)確率為84%，比其他方法都高。從表2可看出該方法的Spearman相關(guān)系數(shù)比另兩種方法高。準(zhǔn)確率以及Spearman相關(guān)系數(shù)的提高說明數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則對詞語關(guān)聯(lián)度計算是有一定幫助的，證明了該方法的可行性。

圖5 準(zhǔn)確率對比

算法Spearman相關(guān)系數(shù)Sim0.795WikiRelate0.776GooRel0.731

6 結(jié)語

本文采用數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則中運(yùn)行速度較快的FP-growth算法，目的是從大規(guī)模語料庫中得到詞匯社區(qū)網(wǎng)絡(luò)。目前數(shù)據(jù)挖掘大部分應(yīng)用在銀行、金融、大型商業(yè)數(shù)據(jù)庫等盈利性領(lǐng)域中，在詞語關(guān)聯(lián)度這一研究領(lǐng)域中應(yīng)用很少，本文對數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則在詞語關(guān)聯(lián)度計算的應(yīng)用進(jìn)行了探索，提高了詞語關(guān)聯(lián)度計算的準(zhǔn)確性，在后續(xù)工作中，我們將進(jìn)一步研究如下問題：

(1)人民日報新聞?wù)Z料過于正規(guī)、范圍局限，因此可以考慮擴(kuò)大語料范圍，例如網(wǎng)絡(luò)上的微博語料庫等。

(2)本文研究的詞語關(guān)聯(lián)度計算是基于語料庫的，該算法是通過對大量文本進(jìn)行統(tǒng)計分析來得出詞語關(guān)聯(lián)度。下一步工作可以與基于外部知識庫的方法結(jié)合起來，例如維基百科、知網(wǎng)等。通過對知識庫結(jié)構(gòu)化的、明確的語義知識進(jìn)行分析，提高詞語關(guān)聯(lián)度計算的覆蓋度和準(zhǔn)確性。

(3)在本文的研究基礎(chǔ)上，希望將數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則應(yīng)用在自然語言處理其他研究任務(wù)中。

參考文獻(xiàn)：

[1] LENAT D B， GUHA R V. Building large knowledge based systems[M]. New York：Addison Wesley，1990：78.

[2] DEERWESTER S， DUMAIS S， FURNAS U， et al. Indexing by latent semantic analysis[J]. Journal of the American society for information science，1990，41(6)：391-407.

[3] ALEXANDER B， GRAEME H. Evaluating word net-based measures of lexical semantic relatedness[J]. Computational linguistics，2006，32(1)：13-47.

[4] 李赟.基于中文維基百科的語義知識挖掘相關(guān)研究[D].北京：北京郵電大學(xué)，2009.

[5] DAVIS R， LENAT D B. Knowledge-based systems in artificial intelligence[M]. New York： McGraw-Hill，1982：39-51.

[6] AGRAWAL R， IMIELINSKI T， SWAMI A N. Mining association rules between sets of items in large databases[C]// Proceedings of the 1993 ACM Sigmod Intenrational Conference on Management of Data， Acm sigmod record，1993，22(2)：207-216.

[7] FIRTH J R. A synopsis of linguistic theory 1930-55[M]. Oxford： The Philological Society，1957：1-32.

[8] HAN J， PEI J， YIN Y. Minning frequent patterns without candidate generation[J]. Acm sigmod international conference on management of data，2000，29(2)：1-12.

[9] FINKELSTEIN R L. Placing search in context： the concept revisited[J]. Acm transactions on information systems，2002，20(1)：116-131.

[10] 夏天.中文信息處理中的相似度計算研究與應(yīng)用[D].北京：北京理工大學(xué)，2005.

[11] STRUBE M， PONZETTO S P. WikiRelate! computing semantic relatedness using wikipedia[J]. Proc. Nat. Conf. artificial intelligence(AAAI)，2006，2(6)：1419-1424.

[12] GABRILOVICH E， MARKOVITCH S. Computing semantic relatedness using Wikipedia-based explicit semantic analysis[J]. Proc international joint conference on artificial intelligence，2007(6)：1606-1611.

[13] MILNE D. Computing semantic relatedness using Wikipedia link structure[C]. Proceedings of the New Zealand Computer Science Research Student conference，2007.

[14] SPEARMAN C. The proof and measurement of association between two things[J].The American journal of psychology，1904，15(1)：72-101.