數據挖掘關聯規則在詞語關聯度計算中的應用

董晨輝，師文慧

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

0 引言

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

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

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

由于詞語特征信息稀疏，因此計算詞語間關聯度是一項復雜而艱難的任務，需要大量的外部資源作為支撐，以便對詞語特征進行擴充。有些方法是以外部知識庫為基礎來計算詞語間關聯度[1]，有些方法是通過對大型語料庫進行統計分析來實現[2]，有些方法則使用經過手工處理得出的語匯結構實現，如同義詞典[3]、HowNet[4]。這些方法均沒有涉及數據挖掘的關聯規則。

因此，本文以新聞語料為外部數據庫，提出了一種利用數據挖掘中關聯規則來計算詞語之間的關聯度的計算方法，以挖掘各詞語之間頻繁出現的關聯性。

1 關聯規則介紹

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

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

(1)

其中，|D|等于D中事務T的個數。

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

(2)

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

(3)

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

(4)

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

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

2 詞匯社區結構的構建

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

利用關聯規則計算短文本的關聯度，這一類方法的理論基礎是Firth在文獻[7]提出的上下文假設：詞匯的上下文環境體現的是人們在實際語言交流中使用該詞匯的具體途徑，并且兩個詞匯的使用方式越接近，在語義上就越相關。基于這一理論便可以通過統計大規模語料中詞匯出現的規律得到詞語間的關聯度，即通過在大規模語料中統計詞匯所處的上下文環境，得到每個詞匯的上下文分布，而兩個詞匯的語義相關度則通過比較二者對應的上下文分布并綜合分析后得出最終結果。

關聯規則一般用來發現交易數據庫中不同商品(項)之間的聯系。將大規模語料庫(人民日報2013-2014年語料庫)作為交易數據庫，每篇新聞中出現的實詞集合作為事務，出現的每個詞語認為是商品，便可以找出兩詞語間的聯系。在中文語料中，將交易中的頻繁項集認為是關聯度高的詞匯所構造的一個詞匯社區，根據人民日報2013-2014年語料庫構造的社區結構就是新聞中共同出現頻率高的詞語集合，詞匯社區結構如圖1所示，其中橢圓的大小代表社區的大小，橢圓的包含關系代表社區的包含關系。

圖1 詞匯社區結構

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

3 選用的算法

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

3.1 構建FP樹

構建FP樹，即是把事務數據表中的各個事務數據項按照支持度降序排序后，依次插入到一棵以NULL為根結點的樹中，同時在每個結點處記錄該結點出現的支持度。圖2為構建FP樹的過程示意圖。

圖2 構建FP樹的過程示意圖

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

3.2 從FP樹中挖掘頻繁項集

3.2.1 算法1：通過構造條件樹查找頻繁項集

①從FP樹中獲得條件模式基；②利用條件模式基，構建一個條件FP樹；③迭代重復步驟①和步驟②，直到樹包含一個元素項為止。

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

圖3 條件樹示意圖

3.2.2 算法2：遞歸查找頻繁項集

輸入：有當前數據集的FP樹(inTree，headerTable)。

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

4 詞語間相關度的計算

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

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

(5)

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

(2)一部分詞對在重要程度上是不對稱的，例如，“中國”和“北京”相互之間的依賴程度是對稱的，因為“北京”是“中國”的首都；相反，位于四川省邛崍市的“白楊村”和“中國”相互之間依賴程度是不對稱的，“白楊村”對“中國”的依賴程度大于“中國”對“白楊村”的依賴程度。A出現時B出現的概率可用詞語A，B的置信度來表示。置信度“A?B”并不等于置信度“B?A”。

(6)

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

(7)

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

(8)

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

(9)

5 實驗驗證

5.1 數據準備

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

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

5.2 實驗過程

本實驗硬件環境為雙核T6 Intel處理器、主頻2.80 GHz、內存為4 GB，編程環境為MyEclipse，數據庫使用的是MySQL。通過挖掘強關聯規則，可以拓展詞語的長度，增加特征數，從而減輕特征稀疏性對關聯度計算結果產生的影響。

社區規模可以通過設置不同的最小支持度以及最小置信度來改變。規模較小的社區包含了緊密的語義相關的互聯節點，它們通常隸屬于同一主題。社區結構規模與支持度閾值的關系如圖4所示。利用“試錯”法選取合適的閾值，支持度越大，社區規模越小，語義節點間也更為緊密。

圖4 社區結構規模與支持度閾值的關系圖

5.3 實驗結果與分析

根據上述計算方法，實現了關聯規則在詞語關聯度計算中的應用。部分詞對關聯度的計算結果如表1所示。

表1 部分詞對關聯度計算結果

通過分析表1，可以看出實驗結果有一定的合理性，符合人們主觀上的判斷。

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

(2)從計算結果可以看出詞語的支持度都比較小，這是由于新聞語料中出現的詞語過于龐大造成的，但支持度的大小并不影響關聯度計算的結果。

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

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

圖5 準確率對比

算法Spearman相關系數Sim0.795WikiRelate0.776GooRel0.731

6 結語

本文采用數據挖掘的關聯規則中運行速度較快的FP-growth算法，目的是從大規模語料庫中得到詞匯社區網絡。目前數據挖掘大部分應用在銀行、金融、大型商業數據庫等盈利性領域中，在詞語關聯度這一研究領域中應用很少，本文對數據挖掘的關聯規則在詞語關聯度計算的應用進行了探索，提高了詞語關聯度計算的準確性，在后續工作中，我們將進一步研究如下問題：

(1)人民日報新聞語料過于正規、范圍局限，因此可以考慮擴大語料范圍，例如網絡上的微博語料庫等。

(2)本文研究的詞語關聯度計算是基于語料庫的，該算法是通過對大量文本進行統計分析來得出詞語關聯度。下一步工作可以與基于外部知識庫的方法結合起來，例如維基百科、知網等。通過對知識庫結構化的、明確的語義知識進行分析，提高詞語關聯度計算的覆蓋度和準確性。

(3)在本文的研究基礎上，希望將數據挖掘的關聯規則應用在自然語言處理其他研究任務中。

參考文獻：

[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] 李赟.基于中文維基百科的語義知識挖掘相關研究[D].北京：北京郵電大學，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] 夏天.中文信息處理中的相似度計算研究與應用[D].北京：北京理工大學，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.