董晨輝，師文慧

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

0 引言

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

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

2 詞匯社區(qū)結構的構建

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

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

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

圖1 詞匯社區(qū)結構

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

3 選用的算法

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

3.1 構建FP樹

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

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

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

3.2 從FP樹中挖掘頻繁項集

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

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

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

圖3 條件樹示意圖

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

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

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

4 詞語間相關度的計算

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

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

(5)

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

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

(6)

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

(7)

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

(8)

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

(9)

5 實驗驗證

5.1 數(shù)據(jù)準備

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

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

5.2 實驗過程

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

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

圖4 社區(qū)結構規(guī)模與支持度閾值的關系圖

5.3 實驗結果與分析

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

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

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

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

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

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

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

圖5 準確率對比

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

6 結語

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

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

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

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

參考文獻：

[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.