Apriori 算法改進(jìn)及其在校園輿情焦點(diǎn)問題的應(yīng)用

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

（廣州大學(xué)計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣州 510006）

1 引言

大量的社交媒體的使用帶來大量的用戶數(shù)據(jù)信息，大學(xué)生作為社會(huì)的特殊群體，面對(duì)來自學(xué)習(xí)生活等各方面的壓力和困惑時(shí)，大部分選擇向虛擬的的社交網(wǎng)絡(luò)求助和分享自己的生活經(jīng)驗(yàn)。

如何利用數(shù)據(jù)挖掘中的方法對(duì)文本數(shù)據(jù)進(jìn)行有效的整合分析，幫助使用者從文本數(shù)據(jù)中發(fā)掘潛在信息，這是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域面臨的一大挑戰(zhàn)。關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘研究中的一個(gè)重要課題[2]，最開始是R.Agrawal 等人從顧客交易數(shù)據(jù)庫(kù)中發(fā)現(xiàn)用戶購(gòu)買的商品出現(xiàn)有趣的關(guān)聯(lián)提出了apriori 算法[6]，挖掘?qū)ο鬄槭聞?wù)型數(shù)據(jù)庫(kù)。隨著關(guān)聯(lián)規(guī)則研究的深入，已不僅僅限于在事務(wù)型數(shù)據(jù)庫(kù)中挖掘相關(guān)規(guī)則，同樣也可以基于不同媒體挖掘，如關(guān)系型數(shù)據(jù)庫(kù)、面向?qū)ο髷?shù)據(jù)庫(kù)、多維數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)等[2]。目前，胡珊將apriori 改進(jìn)算法找出大學(xué)生心理健康主要因素及其癥狀之間的聯(lián)系[3]。吉珊珊等人基于Apriori 算法對(duì)移動(dòng)課堂微信App中的熱點(diǎn)問題進(jìn)行關(guān)聯(lián)分析[4]，馬琳琳等結(jié)合關(guān)聯(lián)規(guī)則和文本分析模型（wordvec 和TFIDF）對(duì)黨的十九大報(bào)告關(guān)鍵詞進(jìn)行相關(guān)性分析[1]。

本文基于apriori 算法，對(duì)學(xué)生在學(xué)校百度貼吧中的發(fā)言和評(píng)論的焦點(diǎn)問題進(jìn)行全文關(guān)聯(lián)提取，深入了解學(xué)生的輿論，找出大學(xué)生談?wù)摰慕裹c(diǎn)問題中涉及的方方面面，從而為學(xué)校正確引導(dǎo)學(xué)生提供了數(shù)據(jù)參考。

2 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則最初運(yùn)用于“購(gòu)物籃”分析，顧客一次購(gòu)物同時(shí)購(gòu)買那些商品，這種關(guān)聯(lián)幫助銷售者設(shè)計(jì)不同的商品格局，如今信息的主要載體已，已經(jīng)由傳統(tǒng)的結(jié)構(gòu)化數(shù)字?jǐn)?shù)據(jù)轉(zhuǎn)變?yōu)榻Y(jié)構(gòu)特殊的文本數(shù)據(jù)。面對(duì)海量的文本數(shù)據(jù)，借鑒“購(gòu)物籃”問題所提出的關(guān)聯(lián)規(guī)則，用來對(duì)文本數(shù)據(jù)中進(jìn)行關(guān)聯(lián)分析。

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

若support（A）≥minsupport，則項(xiàng)集A 為頻繁k 項(xiàng)集，記為關(guān)聯(lián)規(guī)則是形如的蘊(yùn)含式，其中設(shè)規(guī)則支持度為s，置信度為c，其中s是D 中同時(shí)包含A 和B 的百分比，即s =P（A ∪B），c 為D 中包含A 的同時(shí)也包含B 的百分比，即c =P（B|A）。即，

一般而言，關(guān)聯(lián)規(guī)則的挖掘包含以下兩個(gè)步驟：找出所有頻繁項(xiàng)集：這些項(xiàng)集的支持度不小于最小支持度。由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：這些規(guī)則必須滿足同時(shí)滿足最小支持度和最小置信度。

3 Apriori 算法

Apriori 算法是經(jīng)典的挖掘頻繁項(xiàng)集的辦法，使用逐層迭代搜索的方法，最終目標(biāo)是迭代產(chǎn)生出所有頻繁項(xiàng)集。通過頻繁k 項(xiàng)集搜索k+1項(xiàng)集，即頻繁1項(xiàng)集用于搜索頻繁2項(xiàng)集，如此循環(huán)，直至找不到頻繁k 項(xiàng)集。Apriori 算法挖掘頻繁項(xiàng)集結(jié)束，根據(jù)最小置信度生成強(qiáng)關(guān)聯(lián)規(guī)則。采用此算法產(chǎn)生頻繁項(xiàng)集既不會(huì)遺漏也不會(huì)重復(fù)，但每一次生成頻繁k 項(xiàng)集都要掃描數(shù)據(jù)庫(kù)k 次，為了提高Apriori 的逐層產(chǎn)生頻繁項(xiàng)集效率，使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)（即頻繁項(xiàng)集的所有子集都是頻繁的）來壓縮搜索空間。

Apriori 得到頻繁項(xiàng)集的具體步驟如下：

①掃描事務(wù)數(shù)據(jù)庫(kù)，統(tǒng)計(jì)每一個(gè)項(xiàng)出現(xiàn)的個(gè)數(shù)，與最小支持度比較，刪除小于最小支持度的項(xiàng)，得到頻繁1項(xiàng)集L1

②若Lk-1為空，則算法結(jié)束

③用Lk-1進(jìn)行自連接生成候選k 項(xiàng)集集合Ck

④Ck是Lk超集，根據(jù)頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)：頻繁項(xiàng)集的子集也是頻繁的，即非頻繁項(xiàng)集的超集也是非頻繁的。若某候選k 項(xiàng)集的一個(gè)（k-1）子集不在Lk-1中，則直接從Ck中刪除。

⑤掃描事務(wù)數(shù)據(jù)庫(kù)，統(tǒng)計(jì)Ck中每個(gè)候選k 項(xiàng)集在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)，刪除小于最小支持度的項(xiàng)集，得到頻繁k 項(xiàng)集Lk

⑥k=k+1，重復(fù)執(zhí)行2、3、4，5。

由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則

強(qiáng)關(guān)聯(lián)規(guī)則是同時(shí)滿足最小支持度和最小置信度的規(guī)則，前面已經(jīng)求出了每個(gè)頻繁項(xiàng)集的支持度，故此處只需要算出最小置信度。關(guān)聯(lián)規(guī)則產(chǎn)生如下：

①對(duì)于每一個(gè)頻繁項(xiàng)集l，產(chǎn)生l 的所有非空子集

4 Apriori 改進(jìn)算法

通過以上的Apriori 得到頻繁項(xiàng)集的具體步驟，可以看出在數(shù)據(jù)挖掘中存在兩個(gè)缺陷：

①找出每個(gè)頻繁項(xiàng)集時(shí)都需要完整掃描數(shù)據(jù)庫(kù)一次，面對(duì)海量數(shù)據(jù)時(shí)，算法開銷很大，嚴(yán)重影響apriori 的執(zhí)行效率。

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

針對(duì)上述缺陷，改進(jìn)主要從以下三個(gè)方面：

①掃描數(shù)據(jù)庫(kù)統(tǒng)計(jì)每一個(gè)項(xiàng)出現(xiàn)次數(shù)時(shí)，計(jì)數(shù)同時(shí)記錄下每一項(xiàng)出現(xiàn)的行號(hào)。

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

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

如果lift（A，B）的值小于1，則A 和B 的出現(xiàn)是負(fù)相關(guān)，意味A 的出現(xiàn)導(dǎo)致B 的不出現(xiàn)。如果lift（A，B）值大于1，則A 和B 的出現(xiàn)是正相關(guān)，意味A 的出現(xiàn)蘊(yùn)含B 出現(xiàn)。如果lift（A，B）值等于1，則A 和B 是獨(dú)立的，它們之間沒有相關(guān)性。

5 改進(jìn)算法應(yīng)用于文本

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

5.1 數(shù)據(jù)來源

利用python 爬蟲工具從全國(guó)各大高校百度貼吧上爬取了用戶的評(píng)論數(shù)據(jù)，分為兩類，一類為廣州大學(xué)貼吧數(shù)據(jù)，一類為全國(guó)高校數(shù)據(jù)。

5.2 文本預(yù)處理

前人的研究成果得到10類焦點(diǎn)問題，每一類含有10個(gè)關(guān)鍵詞。在前人研究基礎(chǔ)上，合并焦點(diǎn)問題中的所有關(guān)鍵詞，得到57個(gè)關(guān)鍵詞。對(duì)用jieba 分詞和清洗后的文本集按照是否含有某關(guān)鍵詞進(jìn)行分類，可到57個(gè)文本，接下來就是分別對(duì)57個(gè)文本進(jìn)行關(guān)聯(lián)分析。

5.3 關(guān)聯(lián)分析

5.3.1 改進(jìn)算法具體步驟

①掃描事務(wù)數(shù)據(jù)庫(kù)，記錄每一項(xiàng)出現(xiàn)的行號(hào)和并計(jì)數(shù)，與最小支持度比較，刪除小于最小支持度的項(xiàng)，得到頻繁1項(xiàng)集L1。

②若Lk-1為空，則算法結(jié)束。

③用Lk-1進(jìn)行自連接生成候選k 項(xiàng)集集合Ck。

④Ck 是Lk 超集，根據(jù)頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)：頻繁項(xiàng)集的子集也是頻繁的，即非頻繁項(xiàng)集的超集也是非頻繁的。若某候選k 項(xiàng)集的一個(gè)（k-1）子集不在Lk-1中，則直接從Ck中刪除。

⑤遍歷Ck每一項(xiàng)，求Ck中每個(gè)候選k 項(xiàng)集包含所有項(xiàng)對(duì)應(yīng)行號(hào)的交集，計(jì)算交集的個(gè)數(shù)，即最小支持度計(jì)數(shù)，刪除小于最小支持度的項(xiàng)集，得到頻繁k 項(xiàng)集Lk。

⑥k=k+1，重復(fù)執(zhí)行②③④⑤。

5.3.2 改進(jìn)算法樣例解析

在進(jìn)行大文本集分析之前，先抽取“專業(yè)”關(guān)鍵詞中少量文本使用改進(jìn)后算法進(jìn)行關(guān)聯(lián)分析

表1 樣例數(shù)據(jù)

設(shè)定最小支持度計(jì)數(shù)為2

①掃描文本，統(tǒng)計(jì)每一個(gè)項(xiàng)的計(jì)數(shù)，得到結(jié)果{考研：{1，3}，專業(yè)：{1，2，3，4，5}，學(xué)校：{1，3，5}，分?jǐn)?shù)線：{1，2，5}，大學(xué)：{2}，錄取：{2，4，5}，排名：{2，4}，計(jì)算機(jī)：{3，5}，文科：{4}，研究生：{4}，除去支持度計(jì)數(shù)小于2的項(xiàng)，得到頻繁1-項(xiàng)集為{{考研}，{專業(yè)}，{學(xué)校}，{分?jǐn)?shù)線}，{錄取}，{排名}，{計(jì)算機(jī)}}共7項(xiàng)。

②對(duì)頻繁1-項(xiàng)集進(jìn)行自連接，得到候選2-項(xiàng)集{{考研，專業(yè)}，{考研，學(xué)校}，{考研，分?jǐn)?shù)線}，{考研，錄取}，{考研，排名}，{考研，計(jì)算機(jī)}，{專業(yè)，學(xué)校}，{專業(yè)，分?jǐn)?shù)線}，{專業(yè)，錄取}，{專業(yè)，排名}，{專業(yè)，計(jì)算機(jī)}……

③對(duì)候選2-項(xiàng)集進(jìn)行計(jì)數(shù)，{考研，專業(yè)}={1，3}&{1，2，3，4，5}={1，3}，{考研，學(xué)校}={1，3}&{1，3，5}={1，3}...，如果計(jì)算后交集結(jié)合含有兩個(gè)以上元素，則為頻繁2-項(xiàng)集，得到頻繁2-項(xiàng)集為{考研，專業(yè)}，{考研，學(xué)校}，{專業(yè)，學(xué)校}，{專業(yè)，分?jǐn)?shù)線}，{專業(yè)，錄取}，{專業(yè)，排名}，{專業(yè)，計(jì)算機(jī)}，{學(xué)校，分?jǐn)?shù)線}，{學(xué)校，計(jì)算機(jī)}，{分?jǐn)?shù)線，錄取}，{錄取，排名}共11項(xiàng)。

④對(duì)頻繁2-項(xiàng)集進(jìn)行自連接，刪除非頻繁項(xiàng)得到候選3-項(xiàng)集為{考研，專業(yè)，學(xué)校}，{專業(yè)，學(xué)校，分?jǐn)?shù)線}，{專業(yè)，學(xué)校，計(jì)算機(jī)}，{專業(yè)，分?jǐn)?shù)線，錄取}，{專業(yè)，錄取，排名}。

⑤對(duì)候選3-項(xiàng)集進(jìn)行計(jì)數(shù)，{考研，專業(yè)，學(xué)校}={考研，專業(yè)}&{學(xué)校}={1，3}&{1，3，5}={1，3}…如果計(jì)算后交集結(jié)合含有兩個(gè)以上元素，則為頻繁3-項(xiàng)集，得到頻繁3-項(xiàng)集為{考研，專業(yè)，學(xué)校}，{專業(yè)，學(xué)校，分?jǐn)?shù)}，{專業(yè)，學(xué)校，計(jì)算機(jī)}，{專業(yè)，分?jǐn)?shù)線，錄取}，{專業(yè)，錄取，排名}共4項(xiàng)。

⑥對(duì)頻繁3-項(xiàng)集進(jìn)行自連接，刪除非頻繁項(xiàng)得到候選4-項(xiàng)集為{}，則頻繁4-項(xiàng)集為空，算法結(jié)束。

⑦由頻繁項(xiàng)集找出關(guān)聯(lián)規(guī)則。

設(shè)最小置信度為0.7，lift=1.0，得到關(guān)聯(lián)規(guī)則為

表2 樣例結(jié)果

由上述表格可以得出，由于專業(yè)關(guān)鍵詞在每一行記錄中都出現(xiàn)，所以P（專業(yè)）=1，對(duì)于頻繁2-項(xiàng)集而言，三個(gè)指標(biāo)只有support 起作用，表明專業(yè)和其他關(guān)鍵詞同時(shí)出現(xiàn)的概率有多大。對(duì)于項(xiàng)集大小大于2時(shí)，當(dāng)專業(yè)位于箭頭右邊時(shí)，也只有support起作用，表明專業(yè)和其他k-1項(xiàng)集同時(shí)出現(xiàn)的概率，當(dāng)專業(yè)關(guān)鍵詞在箭頭左邊時(shí)，規(guī)則才有意義。由表格可以看出，當(dāng)人們?cè)谡務(wù)搶I(yè)和考研時(shí)，會(huì)提到學(xué)校，即確定自己要考研和報(bào)考專業(yè)后，就要選好學(xué)校進(jìn)行針對(duì)性復(fù)習(xí)。當(dāng)大家在討論計(jì)算機(jī)專業(yè)時(shí)，就非常想知道該計(jì)算機(jī)專業(yè)是哪個(gè)學(xué)校開設(shè)的。當(dāng)大家在討論排名和專業(yè)時(shí)，會(huì)提到錄取，即當(dāng)初試知道成績(jī)排名后，人們更加想知道自己能否進(jìn)入復(fù)試，也就增加了被錄取的可能性。

5.3.3 改進(jìn)算法運(yùn)用于文本集結(jié)果展示

將改進(jìn)算法運(yùn)用于大文本集后，提取10個(gè)有代表性的關(guān)鍵詞關(guān)聯(lián)分析后的前5個(gè)結(jié)果得到結(jié)果如下：

表3 大文本運(yùn)行結(jié)果

從表格中看出，就專業(yè)這個(gè)關(guān)鍵詞，某高校學(xué)生關(guān)注的東西和全國(guó)各大高校的學(xué)生關(guān)注的東西略有不同，因?yàn)槟掣咝Ｇ靶┠暧锌梢赞D(zhuǎn)專業(yè)的慣例，所以大部分的同學(xué)關(guān)注的內(nèi)容是轉(zhuǎn)專業(yè)。全國(guó)各大高校的學(xué)生關(guān)注最多的是在哪所大學(xué)學(xué)習(xí)該專業(yè)和如何學(xué)習(xí)專業(yè)。倒數(shù)四行，可以看出所有高校都是關(guān)注考研和畢業(yè)內(nèi)容。

6 結(jié)束語

大數(shù)據(jù)時(shí)代，從社交網(wǎng)絡(luò)上了解學(xué)生對(duì)學(xué)習(xí)和生活的困惑和評(píng)價(jià)的作用是不可忽視的，本文研究的Apriori 改進(jìn)算法，通過數(shù)據(jù)挖掘發(fā)現(xiàn)了某高校和全國(guó)其他高校在專業(yè)問題上關(guān)注的東西的不同，給學(xué)生提供一個(gè)知道自己和其他高校學(xué)生差距的平臺(tái)，同時(shí)也為教育工作者在如何正確引導(dǎo)學(xué)生方面提供數(shù)據(jù)參考。Apriori 改進(jìn)算法優(yōu)化了生成頻繁項(xiàng)集過程，不用重復(fù)掃描數(shù)據(jù)庫(kù)，提高了Apriori 算法的運(yùn)行效率。