Apriori 算法改進及其在校園輿情焦點問題的應用

梁 茵，張艷玲，鄭建靈，黃子豪，田俊雄

（廣州大學計算機科學與網絡工程學院，廣州 510006）

1 引言

大量的社交媒體的使用帶來大量的用戶數據信息，大學生作為社會的特殊群體，面對來自學習生活等各方面的壓力和困惑時，大部分選擇向虛擬的的社交網絡求助和分享自己的生活經驗。

如何利用數據挖掘中的方法對文本數據進行有效的整合分析，幫助使用者從文本數據中發掘潛在信息，這是當前數據挖掘領域面臨的一大挑戰。關聯規則作為數據挖掘研究中的一個重要課題[2]，最開始是R.Agrawal 等人從顧客交易數據庫中發現用戶購買的商品出現有趣的關聯提出了apriori 算法[6]，挖掘對象為事務型數據庫。隨著關聯規則研究的深入，已不僅僅限于在事務型數據庫中挖掘相關規則，同樣也可以基于不同媒體挖掘，如關系型數據庫、面向對象數據庫、多維數據庫、數據倉庫等[2]。目前，胡珊將apriori 改進算法找出大學生心理健康主要因素及其癥狀之間的聯系[3]。吉珊珊等人基于Apriori 算法對移動課堂微信App中的熱點問題進行關聯分析[4]，馬琳琳等結合關聯規則和文本分析模型（wordvec 和TFIDF）對黨的十九大報告關鍵詞進行相關性分析[1]。

本文基于apriori 算法，對學生在學校百度貼吧中的發言和評論的焦點問題進行全文關聯提取，深入了解學生的輿論，找出大學生談論的焦點問題中涉及的方方面面，從而為學校正確引導學生提供了數據參考。

2 關聯規則

關聯規則最初運用于“購物籃”分析，顧客一次購物同時購買那些商品，這種關聯幫助銷售者設計不同的商品格局，如今信息的主要載體已，已經由傳統的結構化數字數據轉變為結構特殊的文本數據。面對海量的文本數據，借鑒“購物籃”問題所提出的關聯規則，用來對文本數據中進行關聯分析。

關聯規則的支持度（support）和置信度（confidence）是規則興趣度的兩種度量，他們分別衡量規則的正確性和有效性。在一般情況下，關聯規則被認為是有趣的，如果滿足最小支持度閾值minsupport 和最小置信度閾值minconfidence。通常最小支持度的值和最小置信度的值是按照自己需求設定。簡言之，關聯規則挖掘是通過給定的數據庫，根據最小支持度和最小置信度來尋找合適關聯規則的過程[5]。設T={ I1，I2，I3，...，Im}是項的集合，D 為事務數據庫記錄集合，t 為D 中元素，使得設A 為一個項集，若A 中包含k 個項，則稱A 為k 項集，事務t 包含A，當且僅當其中A 的支持度如下：

若support（A）≥minsupport，則項集A 為頻繁k 項集，記為關聯規則是形如的蘊含式，其中設規則支持度為s，置信度為c，其中s是D 中同時包含A 和B 的百分比，即s =P（A ∪B），c 為D 中包含A 的同時也包含B 的百分比，即c =P（B|A）。即，

一般而言，關聯規則的挖掘包含以下兩個步驟：找出所有頻繁項集：這些項集的支持度不小于最小支持度。由頻繁項集產生強關聯規則：這些規則必須滿足同時滿足最小支持度和最小置信度。

3 Apriori 算法

Apriori 算法是經典的挖掘頻繁項集的辦法，使用逐層迭代搜索的方法，最終目標是迭代產生出所有頻繁項集。通過頻繁k 項集搜索k+1項集，即頻繁1項集用于搜索頻繁2項集，如此循環，直至找不到頻繁k 項集。Apriori 算法挖掘頻繁項集結束，根據最小置信度生成強關聯規則。采用此算法產生頻繁項集既不會遺漏也不會重復，但每一次生成頻繁k 項集都要掃描數據庫k 次，為了提高Apriori 的逐層產生頻繁項集效率，使用頻繁項集性質的先驗知識（即頻繁項集的所有子集都是頻繁的）來壓縮搜索空間。

Apriori 得到頻繁項集的具體步驟如下：

①掃描事務數據庫，統計每一個項出現的個數，與最小支持度比較，刪除小于最小支持度的項，得到頻繁1項集L1

②若Lk-1為空，則算法結束

③用Lk-1進行自連接生成候選k 項集集合Ck

④Ck是Lk超集，根據頻繁項集性質的先驗知識：頻繁項集的子集也是頻繁的，即非頻繁項集的超集也是非頻繁的。若某候選k 項集的一個（k-1）子集不在Lk-1中，則直接從Ck中刪除。

⑤掃描事務數據庫，統計Ck中每個候選k 項集在數據庫中出現的次數，刪除小于最小支持度的項集，得到頻繁k 項集Lk

⑥k=k+1，重復執行2、3、4，5。

由頻繁項集產生強關聯規則

強關聯規則是同時滿足最小支持度和最小置信度的規則，前面已經求出了每個頻繁項集的支持度，故此處只需要算出最小置信度。關聯規則產生如下：

①對于每一個頻繁項集l，產生l 的所有非空子集

4 Apriori 改進算法

通過以上的Apriori 得到頻繁項集的具體步驟，可以看出在數據挖掘中存在兩個缺陷：

①找出每個頻繁項集時都需要完整掃描數據庫一次，面對海量數據時，算法開銷很大，嚴重影響apriori 的執行效率。

②由于Apriori 算法并沒有考慮挖掘出的規則的價值，所以可能挖掘出大量無意義的規則。

針對上述缺陷，改進主要從以下三個方面：

①掃描數據庫統計每一個項出現次數時，計數同時記錄下每一項出現的行號。

②用Lk-1進行自連接生成候選k 項集集合Ck 并刪除非頻繁的候選后，原始apriori 算法需要掃面數據庫統計候選k 選集的個數，改進的算法中求k 個項目中包含行號的交集，統計集合中元素個數，將其除以數據庫記錄條數，即得到該候選項集的支持度，和最小支持度比較，就可以得到頻繁k 項集。

lift（A，B）=（P（AUB））/（P（A）P（B））（4）

如果lift（A，B）的值小于1，則A 和B 的出現是負相關，意味A 的出現導致B 的不出現。如果lift（A，B）值大于1，則A 和B 的出現是正相關，意味A 的出現蘊含B 出現。如果lift（A，B）值等于1，則A 和B 是獨立的，它們之間沒有相關性。

5 改進算法應用于文本

文本挖掘中的關聯分析是從文本集合中找出不同關鍵詞之間的關聯關系。其基本思想是將數據挖掘中的apriori 算法運用于中文文本挖掘中，將文本集D 看成事務型數據庫，T={I1，I2，I3，...，Im}是m 個特征詞的集合，文本集中的每一條文本看成事務型數據庫中的一條記錄，每個文本包含T 中若干特征詞。

5.1 數據來源

利用python 爬蟲工具從全國各大高校百度貼吧上爬取了用戶的評論數據，分為兩類，一類為廣州大學貼吧數據，一類為全國高校數據。

5.2 文本預處理

前人的研究成果得到10類焦點問題，每一類含有10個關鍵詞。在前人研究基礎上，合并焦點問題中的所有關鍵詞，得到57個關鍵詞。對用jieba 分詞和清洗后的文本集按照是否含有某關鍵詞進行分類，可到57個文本，接下來就是分別對57個文本進行關聯分析。

5.3 關聯分析

5.3.1 改進算法具體步驟

①掃描事務數據庫，記錄每一項出現的行號和并計數，與最小支持度比較，刪除小于最小支持度的項，得到頻繁1項集L1。

②若Lk-1為空，則算法結束。

③用Lk-1進行自連接生成候選k 項集集合Ck。

④Ck 是Lk 超集，根據頻繁項集性質的先驗知識：頻繁項集的子集也是頻繁的，即非頻繁項集的超集也是非頻繁的。若某候選k 項集的一個（k-1）子集不在Lk-1中，則直接從Ck中刪除。

⑤遍歷Ck每一項，求Ck中每個候選k 項集包含所有項對應行號的交集，計算交集的個數，即最小支持度計數，刪除小于最小支持度的項集，得到頻繁k 項集Lk。

⑥k=k+1，重復執行②③④⑤。

5.3.2 改進算法樣例解析

在進行大文本集分析之前，先抽取“專業”關鍵詞中少量文本使用改進后算法進行關聯分析

表1 樣例數據

設定最小支持度計數為2

①掃描文本，統計每一個項的計數，得到結果{考研：{1，3}，專業：{1，2，3，4，5}，學校：{1，3，5}，分數線：{1，2，5}，大學：{2}，錄?。簕2，4，5}，排名：{2，4}，計算機：{3，5}，文科：{4}，研究生：{4}，除去支持度計數小于2的項，得到頻繁1-項集為{{考研}，{專業}，{學校}，{分數線}，{錄取}，{排名}，{計算機}}共7項。

②對頻繁1-項集進行自連接，得到候選2-項集{{考研，專業}，{考研，學校}，{考研，分數線}，{考研，錄取}，{考研，排名}，{考研，計算機}，{專業，學校}，{專業，分數線}，{專業，錄取}，{專業，排名}，{專業，計算機}……

③對候選2-項集進行計數，{考研，專業}={1，3}&{1，2，3，4，5}={1，3}，{考研，學校}={1，3}&{1，3，5}={1，3}...，如果計算后交集結合含有兩個以上元素，則為頻繁2-項集，得到頻繁2-項集為{考研，專業}，{考研，學校}，{專業，學校}，{專業，分數線}，{專業，錄取}，{專業，排名}，{專業，計算機}，{學校，分數線}，{學校，計算機}，{分數線，錄取}，{錄取，排名}共11項。

④對頻繁2-項集進行自連接，刪除非頻繁項得到候選3-項集為{考研，專業，學校}，{專業，學校，分數線}，{專業，學校，計算機}，{專業，分數線，錄取}，{專業，錄取，排名}。

⑤對候選3-項集進行計數，{考研，專業，學校}={考研，專業}&{學校}={1，3}&{1，3，5}={1，3}…如果計算后交集結合含有兩個以上元素，則為頻繁3-項集，得到頻繁3-項集為{考研，專業，學校}，{專業，學校，分數}，{專業，學校，計算機}，{專業，分數線，錄取}，{專業，錄取，排名}共4項。

⑥對頻繁3-項集進行自連接，刪除非頻繁項得到候選4-項集為{}，則頻繁4-項集為空，算法結束。

⑦由頻繁項集找出關聯規則。

設最小置信度為0.7，lift=1.0，得到關聯規則為

表2 樣例結果

由上述表格可以得出，由于專業關鍵詞在每一行記錄中都出現，所以P（專業）=1，對于頻繁2-項集而言，三個指標只有support 起作用，表明專業和其他關鍵詞同時出現的概率有多大。對于項集大小大于2時，當專業位于箭頭右邊時，也只有support起作用，表明專業和其他k-1項集同時出現的概率，當專業關鍵詞在箭頭左邊時，規則才有意義。由表格可以看出，當人們在談論專業和考研時，會提到學校，即確定自己要考研和報考專業后，就要選好學校進行針對性復習。當大家在討論計算機專業時，就非常想知道該計算機專業是哪個學校開設的。當大家在討論排名和專業時，會提到錄取，即當初試知道成績排名后，人們更加想知道自己能否進入復試，也就增加了被錄取的可能性。

5.3.3 改進算法運用于文本集結果展示

將改進算法運用于大文本集后，提取10個有代表性的關鍵詞關聯分析后的前5個結果得到結果如下：

表3 大文本運行結果

從表格中看出，就專業這個關鍵詞，某高校學生關注的東西和全國各大高校的學生關注的東西略有不同，因為某高校前些年有可以轉專業的慣例，所以大部分的同學關注的內容是轉專業。全國各大高校的學生關注最多的是在哪所大學學習該專業和如何學習專業。倒數四行，可以看出所有高校都是關注考研和畢業內容。

6 結束語

大數據時代，從社交網絡上了解學生對學習和生活的困惑和評價的作用是不可忽視的，本文研究的Apriori 改進算法，通過數據挖掘發現了某高校和全國其他高校在專業問題上關注的東西的不同，給學生提供一個知道自己和其他高校學生差距的平臺，同時也為教育工作者在如何正確引導學生方面提供數據參考。Apriori 改進算法優化了生成頻繁項集過程，不用重復掃描數據庫，提高了Apriori 算法的運行效率。