面向?qū)W生成績(jī)分析的高效關(guān)聯(lián)規(guī)則挖掘算法研究

周日輝

摘要：數(shù)據(jù)挖掘技術(shù)是在大數(shù)據(jù)環(huán)境下，通過(guò)利用關(guān)聯(lián)規(guī)則挖掘等技術(shù)方法，進(jìn)行知識(shí)發(fā)現(xiàn)，其核心過(guò)程是挖掘算法在起關(guān)鍵作用。文章分析了關(guān)聯(lián)規(guī)則挖掘技術(shù)原理，以學(xué)生成績(jī)作為數(shù)據(jù)樣本，對(duì)其算法進(jìn)行分析，探討算法優(yōu)化思路，提出高效的算法改進(jìn)方案并驗(yàn)證。為進(jìn)一步利用關(guān)聯(lián)規(guī)則挖掘技術(shù)探索教育領(lǐng)域的數(shù)據(jù)挖掘應(yīng)用研究打下堅(jiān)實(shí)的基礎(chǔ)。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；學(xué)生成績(jī)；算法；教育

中圖分類號(hào)：TP399? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）30-0048-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1? 關(guān)聯(lián)規(guī)則挖掘概述

關(guān)聯(lián)規(guī)則挖掘[1-2]是一個(gè)旨在發(fā)現(xiàn)一大組數(shù)據(jù)項(xiàng)之間隱含關(guān)系的數(shù)據(jù)挖掘技術(shù)。通過(guò)關(guān)聯(lián)規(guī)則挖掘過(guò)程，最后得到的分析結(jié)果是一系列形如“P -> Q”的蘊(yùn)涵式，這個(gè)蘊(yùn)涵式也稱之為關(guān)聯(lián)規(guī)則。式子中的“P”和“Q”分別稱為規(guī)則前件和規(guī)則后件。令 I ={i1，i2，i3，…，in}，是一組項(xiàng)目集合，另外 Trans = {t1，t2，t3，…，tn}是所有事務(wù)的集合，某個(gè)事務(wù)tj，其包含的項(xiàng)集都是I的一個(gè)子集。在關(guān)聯(lián)分析過(guò)程中，含有零個(gè)以上數(shù)目項(xiàng)目的集合叫作項(xiàng)集，則有“k-項(xiàng)集”的表示形式，k表示項(xiàng)集中項(xiàng)目的個(gè)數(shù)。如果項(xiàng)集P是事務(wù)tj的子集，則說(shuō)明項(xiàng)集P包含于事務(wù)tj中。項(xiàng)集一個(gè)重要稱為支持度計(jì)數(shù)σ（P），其含義是指在所有的事務(wù)項(xiàng)目中，項(xiàng)集P是多少個(gè)事務(wù)的子集。其定義可以表示為：

支持度計(jì)數(shù)[3]? σ（P）=|{ tj| P ?tj，tj∈Trans}|；對(duì)于關(guān)聯(lián)規(guī)則挖掘結(jié)果的某一條蘊(yùn)涵式“P->Q”，其中項(xiàng)集P和項(xiàng)集Q的關(guān)系為P∩Q= {φ}，關(guān)聯(lián)規(guī)則質(zhì)量的評(píng)估標(biāo)準(zhǔn)可以用“s”（支持度）和“c”（置信度）來(lái)衡量。

支持度[3] s（P->Q） = σ（P∪Q） / N （N為事務(wù)集合中事務(wù)項(xiàng)的總數(shù)）；

置信度[3] c（P->Q） = σ（P∪Q）? / σ（P）；

關(guān)聯(lián)規(guī)則挖掘可以定義為，在給定的事務(wù)集合“Trans”上，搜索發(fā)掘支持度超過(guò)支持度閾值并且置信度也超過(guò)置信度閾值的所有形如“P->Q”的規(guī)則。

關(guān)聯(lián)規(guī)則挖掘工作主要分為兩個(gè)部分，第一個(gè)任務(wù)是從項(xiàng)目集合“I”中發(fā)掘滿足大于支持度閾值的所有項(xiàng)集，稱之為頻繁項(xiàng)集[4]（關(guān)聯(lián)分析中用到的關(guān)鍵概念），此外，根據(jù)項(xiàng)集的項(xiàng)數(shù)來(lái)命名頻繁項(xiàng)集，如包含K項(xiàng)的項(xiàng)集，如果滿足支持度閾值，則稱之為“頻繁K-項(xiàng)集”，得到所有的頻繁項(xiàng)集，是挖掘關(guān)聯(lián)規(guī)則的先決條件；第二個(gè)任務(wù)是在得到的頻繁項(xiàng)集中，通過(guò)組合不同的規(guī)則前后件演化成不同規(guī)則，所有滿足大于置信度閾值的規(guī)則稱之為強(qiáng)規(guī)則，這也是關(guān)聯(lián)挖掘的最終結(jié)果。

2? 關(guān)聯(lián)規(guī)則挖掘算法

2.1 Apriori算法描述

Apriori算法[5]是解決關(guān)聯(lián)規(guī)則挖掘工作的第一個(gè)算法，算法根據(jù)關(guān)聯(lián)規(guī)則挖掘的兩個(gè)任務(wù)而設(shè)計(jì)，頻繁項(xiàng)集的產(chǎn)生及規(guī)則的產(chǎn)生，在實(shí)踐過(guò)程中會(huì)發(fā)現(xiàn)前者的計(jì)算開銷遠(yuǎn)大于后者。

在頻繁項(xiàng)集產(chǎn)生的任務(wù)中，算法使用一種稱作逐層搜索的迭代方法，即“（K-1）-項(xiàng)集”是用于搜索“K項(xiàng)集”的前提條件。算法開始，找出包含所有“頻繁1-項(xiàng)集”的集合，該集合通過(guò)兩兩結(jié)合的方式生成稱之為“候選2-項(xiàng)集”的集合，這一步驟我們稱之為“連接步”。由于從“候選K-項(xiàng)集”集合生成“頻繁K-項(xiàng)集”集合的過(guò)程，需要把每個(gè)候選集和每條事務(wù)進(jìn)行對(duì)比，如此計(jì)算開銷呈指數(shù)級(jí)增長(zhǎng)，為減少計(jì)算開銷，一方面需要減少“候選K-項(xiàng)集”的數(shù)量，這一步驟稱之為“剪枝步”。應(yīng)用的是Apriori算法的核心思想，稱為“先驗(yàn)原理”[5]，即：如果一個(gè)項(xiàng)集是頻繁的，那它的所有子集也一定是頻繁的，反過(guò)來(lái)同樣成立。

算法得到包含所有頻繁項(xiàng)集的集合后，同樣使用逐層的方法產(chǎn)生規(guī)則，規(guī)則后件項(xiàng)的數(shù)目對(duì)應(yīng)當(dāng)前層數(shù)。針對(duì)某一個(gè)頻繁項(xiàng)集，后件只有一項(xiàng)的候選規(guī)則首先被提取，檢測(cè)其置信度產(chǎn)生高置信度規(guī)則，然后兩兩合并后件而生成新的候選規(guī)則，例如由頻繁項(xiàng)集{a，b，c}產(chǎn)生的兩個(gè)高置信度規(guī)則（a，b->c）及（a，c->b），合并成候選規(guī)則（a->b，c），對(duì)此候選規(guī)則再進(jìn)行置信度檢驗(yàn)，從而確定其是否成為強(qiáng)規(guī)則，以此類推直至不再產(chǎn)生新的候選規(guī)則。為減少候選規(guī)則數(shù)量，同樣利用類似“先驗(yàn)原則”的定理進(jìn)行剪枝，即如果規(guī)則“X->（Y-X）”不滿足置信度閾值，則規(guī)則“X'->（Y-X'）”一定也不滿足置信度閾值，其中X是X的子集。

2.2 Apriori算法的改進(jìn)

本文針對(duì)高校學(xué)生成績(jī)開展關(guān)聯(lián)規(guī)則挖掘以探索高校育人規(guī)律，以廣東茂名幼兒師范?？茖W(xué)校歷年的學(xué)生數(shù)據(jù)作為原始數(shù)據(jù)。為保證數(shù)據(jù)挖掘質(zhì)量與目標(biāo)，選擇的原始成績(jī)數(shù)據(jù)的學(xué)生應(yīng)為相同或相近專業(yè)，成績(jī)數(shù)據(jù)應(yīng)包含學(xué)生相同學(xué)期區(qū)間的成績(jī)項(xiàng)，成績(jī)數(shù)據(jù)中的學(xué)生年級(jí)可以不同，但應(yīng)為相同學(xué)年制。通過(guò)數(shù)據(jù)預(yù)處理，對(duì)原始數(shù)據(jù)存在的空值、非法記錄等異常情況作清洗處理，以及數(shù)據(jù)格式和數(shù)據(jù)類型的轉(zhuǎn)換。數(shù)據(jù)類型轉(zhuǎn)換主要是由于成績(jī)數(shù)據(jù)為連續(xù)型屬性，為適應(yīng)關(guān)聯(lián)挖掘算法的應(yīng)用，需要對(duì)成績(jī)數(shù)據(jù)進(jìn)行“離散化”[6]處理，即分等級(jí)。

對(duì)Apriori算法進(jìn)行改進(jìn)的方法，就是在算法執(zhí)行頻繁項(xiàng)集挖掘任務(wù)的過(guò)程中，通過(guò)縱、橫兩個(gè)維度對(duì)事務(wù)集的質(zhì)量及數(shù)據(jù)量進(jìn)行調(diào)整，其進(jìn)行改進(jìn)思想如下：

（1）縱向。對(duì)于成績(jī)分?jǐn)?shù)在某個(gè)等級(jí)所占比例（根據(jù)實(shí)際情況設(shè)置閾值參數(shù)）過(guò)高，或者成績(jī)集中分布在較少等級(jí)數(shù)（根據(jù)實(shí)際情況設(shè)置閾值參數(shù)）的科目，在算法為發(fā)現(xiàn)“頻繁1-項(xiàng)集”時(shí)第一次掃描全局事務(wù)集后，從事務(wù)集中被排除或被標(biāo)記，在整列數(shù)據(jù)被剔除或被標(biāo)記的同時(shí)，該科目亦將不會(huì)產(chǎn)生的“頻繁1-項(xiàng)集”，如此一方面避免產(chǎn)生較多無(wú)分析價(jià)值的交叉支持模式[7]，另一方面也減少了需要掃描的事務(wù)集數(shù)據(jù)量，如此在提高挖掘的質(zhì)量及效率上做貢獻(xiàn)。

（2）橫向。根據(jù)Apriori算法的先驗(yàn)原理，一個(gè)頻繁項(xiàng)集的所有非空子集也一定是頻繁的，反之，一個(gè)非頻繁項(xiàng)集的超集也一定是非頻繁的。由此進(jìn)行如下推論，如果一個(gè)事務(wù)包含的所有 “K-項(xiàng)集”都是非頻繁的，即該事務(wù)不包含任何“頻繁K-項(xiàng)集”，那么它所有的“（K+1）-項(xiàng)集” 也一定是非頻繁的（“（K+1）-項(xiàng)集”是“K-項(xiàng)集”的超集），即其一定不會(huì)包含任何“頻繁（K+1）-項(xiàng)集”，如此迭代，該事務(wù)將不再包含任何“頻繁L-項(xiàng)集”（L>K）。根據(jù)此推論，當(dāng)算法完成“頻繁K-項(xiàng)集”的統(tǒng)計(jì)后，不包含任何“頻繁K-項(xiàng)集”的事務(wù)將不會(huì)為統(tǒng)計(jì)“頻繁L-項(xiàng)集”（L>K）的工作做任何貢獻(xiàn)，所以，可以將該事務(wù)從事務(wù)集中刪除（標(biāo)記），即為得到“頻繁L-項(xiàng)集”（L>K）掃描全局事務(wù)集時(shí)不再掃描該事務(wù)，從而減少需要掃描的事務(wù)集數(shù)據(jù)量。這是一種逐層減少事務(wù)數(shù)據(jù)量的方式，是對(duì)Apriori算法先驗(yàn)原理的靈活運(yùn)用。

2.3 改進(jìn)算法偽代碼

算法： New_Apriori

輸入：事務(wù)集T，項(xiàng)目集合I，支持度閾值minSup，成績(jī)等級(jí)比例閾值overSup，成績(jī)等級(jí)數(shù)量閾值minGrd。

輸出：T中的頻繁項(xiàng)集。

方法：

（1）? k = 1

（2）? for 每個(gè)項(xiàng)i∈I

（3）? { if（σ（i）>= N*overSup ∨ testGrade（i ， minGrd）==true）（測(cè)試該項(xiàng)所占比例是否過(guò)高，和該科目的成績(jī)等級(jí)分布是否過(guò)窄）

（4）? { I.deleteItem（i）? ? ? ? （刪除該項(xiàng)）

（5）? T.deleteColumns（i）? ? ?（事務(wù)數(shù)據(jù)集刪除該數(shù)據(jù)列）

（6）? }

（7）? else if（σ（i） >= N*minsup）

（8）? Fk.add（i）? ?（發(fā)現(xiàn)所有頻繁1-項(xiàng)集）

（9）? ?}

（10）? repeat

（11）? k = k+1

（12）? Ck = apriori_gen（Fk - 1）? ? ?（產(chǎn)生候選項(xiàng)集）

（13）? for 每個(gè)事務(wù)t∈T

（14）? { Ct = subset（Ck，t）? ? ? （識(shí)別包含在t的所有候選集）

（15）? for 每個(gè)候選項(xiàng)集 c∈Ct

（16）? {σ（c）? = σ（c） + 1? ? （項(xiàng)集c增加支持度計(jì)數(shù)）

（17）? }}

（18）? Fk? = {c|c ∈Ck ∧σ（c） >= N*minSup}

（19）? CompressInstances（T，F(xiàn)k）? ? （事務(wù)集的壓縮，在事務(wù)集T中刪除不包含任何頻繁項(xiàng)集的事務(wù)）

（20）? until Fk = ?

（21）? Return =∪Fk

算法： CompressInstances函數(shù)，通過(guò)排除不包含任何頻繁K-項(xiàng)集的事務(wù)進(jìn)行事務(wù)集合的壓縮

輸入：事務(wù)集T，頻繁K-項(xiàng)集集合itemSets

輸出： 壓縮后的事務(wù)集合

方法：

（1）? function CompressInstances（T，itemSets）

（2）? for i = 0--> T.numInstances（）? do

（3） enu <-- itemSets

（4） containItemSet <--false

（5） while enu.hasMoreElements（）= true? do

（6）? if enu.nextElement（）.containedBy（T.instance（i））? do? ?（判斷當(dāng)前頻繁K-項(xiàng)集是否被第i個(gè)事務(wù)包含）

（7）? ?containItemSet <-- true

（8）? break

（9）? ? end if

（10） end while

（11）? if containItemSet = false? do

（12）? T.delete（i）? ?（事務(wù)集刪除第i個(gè)事務(wù)）

（13）? end if

（14） end for

（15）? end function

New_Apriori算法有兩個(gè)主要過(guò)程，第一個(gè)過(guò)程是算法的第1-9步，在檢測(cè)所有的頻繁1-項(xiàng)集時(shí)，刪除成績(jī)等級(jí)分布異常的數(shù)據(jù)列（科目）。第二個(gè)過(guò)程是算法第10～21步，在每一次迭代的過(guò)程中，通過(guò)支持度計(jì)數(shù)的方式發(fā)現(xiàn)頻繁k-項(xiàng)集，并對(duì)事務(wù)集進(jìn)行檢測(cè)，在事務(wù)數(shù)據(jù)集中排除（標(biāo)記）不包含任何頻繁k-項(xiàng)集的事務(wù)，這通過(guò)CompressInstances函數(shù)實(shí)現(xiàn)。通過(guò)這兩步，避免了在挖掘結(jié)果中產(chǎn)生冗余或交叉支持規(guī)則，也有效地降低了Apriori算法需要掃描的事務(wù)數(shù)據(jù)量，從而大大提高算法的性能。

3? 改進(jìn)算法的驗(yàn)證

對(duì)于使用數(shù)據(jù)挖掘算法得到的關(guān)聯(lián)規(guī)則，建立一種廣泛接受并合乎客觀實(shí)際的評(píng)估標(biāo)準(zhǔn)尤為重要，客觀興趣度度量是利用數(shù)據(jù)驅(qū)動(dòng)評(píng)估規(guī)則質(zhì)量，客觀興趣度分析是在支持度與置信度之外，考究規(guī)則前后件的“相關(guān)性”，使用“提升度值（lift）”[8]進(jìn)行度量，亦被稱作“興趣因子”，它計(jì)算關(guān)聯(lián)規(guī)則的置信度與規(guī)則后件的支持度之間的比率，即：

lift（P->Q）= c（P->Q） / s（Q）

提升度值（lift）參數(shù)的意義在于，在置信度已經(jīng)考慮了規(guī)則前件支持度參數(shù)的基礎(chǔ)上，再考慮規(guī)則后件支持度進(jìn)行概率計(jì)算，當(dāng)其值等于1，說(shuō)明P與Q是獨(dú)立事件，當(dāng)其值大于1，P與Q存在正相關(guān)性[9]，值小于1則存在負(fù)相關(guān)性，存在正相關(guān)性且其值越大則代表規(guī)則前后件有積極的依賴關(guān)系或因果關(guān)系，而負(fù)相關(guān)性則代表這兩個(gè)事件有消極的影響關(guān)系，在實(shí)際應(yīng)用中，前后件呈正相關(guān)性或負(fù)相關(guān)性的，尤其是正相關(guān)而且其提升度值越大的關(guān)聯(lián)規(guī)則是更值得關(guān)注的。

對(duì)改進(jìn)算法的驗(yàn)證，首先選取學(xué)校200名學(xué)生80項(xiàng)科目的成績(jī)作為數(shù)據(jù)樣本，運(yùn)行改進(jìn)算法及原算法，對(duì)比兩者的工作情況進(jìn)行驗(yàn)證。對(duì)兩算法所獲得的高支持度高置信度的規(guī)則進(jìn)行“客觀興趣度”的質(zhì)量評(píng)估，通過(guò)在設(shè)定相同支持度閾值及置信度閾值的情況下，對(duì)比兩算法挖掘出“相關(guān)性”高的規(guī)則占總規(guī)則數(shù)量比例的高低。

在挖掘過(guò)程中，為保證規(guī)則質(zhì)量，不斷調(diào)整算法參數(shù)以達(dá)到最合理，設(shè)置支持度閾值上下限分別為0.6及0.3，當(dāng)置信度閾值設(shè)置為0.8時(shí)，隨著設(shè)置挖掘的最優(yōu)規(guī)則總數(shù)量的變化，兩個(gè)算法的挖掘結(jié)果中，“客觀興趣度”高的規(guī)則比例對(duì)比情況如表1所示，當(dāng)置信度閾值為0.9時(shí)的情況類似。

接下來(lái)，對(duì)比兩算法的運(yùn)行效率，設(shè)置相同的支持度閾值情況，設(shè)置挖掘的最優(yōu)規(guī)則數(shù)量為100，不斷改變置信度閾值，每設(shè)定一個(gè)置信度閾值，運(yùn)行算法10次取平均值，兩算法運(yùn)行時(shí)間的對(duì)比情況見圖1。

以上實(shí)驗(yàn)是選取學(xué)校真實(shí)成績(jī)作為準(zhǔn)備數(shù)據(jù)樣本，為進(jìn)一步驗(yàn)證改進(jìn)Apriori算法設(shè)計(jì)的效果，現(xiàn)保持與上述數(shù)據(jù)樣本的學(xué)生范圍、科目范圍不變，編寫隨機(jī)函數(shù)以生成成績(jī)值的方式，生成準(zhǔn)備數(shù)據(jù)樣本。運(yùn)行隨機(jī)函數(shù)10次，生成10個(gè)隨機(jī)準(zhǔn)備數(shù)據(jù)樣本，針對(duì)每個(gè)樣本運(yùn)行改進(jìn)算法及原算法，參數(shù)設(shè)定支持度閾值上限為0.3，支持度閾值下限為0.1，由于數(shù)據(jù)樣本為隨機(jī)數(shù)值，故降低支持度閾值要求，以保證挖掘數(shù)量，置信度閾值為0.8，挖掘最優(yōu)規(guī)則數(shù)量為100，運(yùn)行時(shí)間是運(yùn)行算法10次取平均值，兩算法運(yùn)行情況對(duì)比如表2所示。

以上實(shí)驗(yàn)結(jié)果顯示，在10個(gè)隨機(jī)數(shù)據(jù)樣本的實(shí)驗(yàn)中，改進(jìn)算法產(chǎn)生的高客觀興趣度規(guī)則的平均比例為39%，高于原算法29%，改進(jìn)算法運(yùn)行的平均時(shí)間為3859（ms），效率高于原算法27356（ms）。實(shí)驗(yàn)結(jié)果與以真實(shí)成績(jī)作為數(shù)據(jù)樣本的實(shí)驗(yàn)結(jié)果基本吻合。

4? 結(jié)束語(yǔ)

綜上所述，通過(guò)對(duì)關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)，在效率和挖掘質(zhì)量上都有一定提升，在效率上的提升較為明顯。原算法在設(shè)計(jì)上是為迎合不同挖掘需求，在使用上具有普適性。本文的算法改進(jìn)方案是針對(duì)學(xué)生成績(jī)數(shù)據(jù)挖掘或與此應(yīng)用情況類似的場(chǎng)景而設(shè)計(jì)，挖掘過(guò)程比原算法更高效，為通過(guò)對(duì)學(xué)生成績(jī)等教育資源數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，進(jìn)一步構(gòu)建完整的系統(tǒng)應(yīng)用提供有力的技術(shù)支持。

參考文獻(xiàn)：

[1] 康君.教育數(shù)據(jù)挖掘服務(wù)平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)[D].濟(jì)南：山東師范大學(xué)，2016.

[2] Sin K，Malaysia O U，Muthu L，et al.“application of big data in education data mining and learning analytics - a literature review”[J].ICTACT Journal on Soft Computing，2015，5（4）：1035-1049.

[3] 李忠，安建琴，劉海軍，等.關(guān)聯(lián)挖掘算法及發(fā)展趨勢(shì)[J].智能計(jì)算機(jī)與應(yīng)用，2017，7（5）：22-25.

[4] 李強(qiáng).數(shù)據(jù)挖掘中關(guān)聯(lián)分析算法研究[D].哈爾濱：哈爾濱工程大學(xué)，2010.

[5] 趙峰，劉博妍.基于改進(jìn)Apriori算法的大學(xué)生成績(jī)關(guān)聯(lián)分析[J].齊齊哈爾大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，34（1）：11-15.

[6] 譚誠(chéng).基于數(shù)據(jù)挖掘的義務(wù)教育績(jī)效考核分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].長(zhǎng)沙：湖南大學(xué)，2016.

[7] 琚安康，郭淵博，朱泰銘，等.網(wǎng)絡(luò)安全事件關(guān)聯(lián)分析技術(shù)與工具研究[J].計(jì)算機(jī)科學(xué)，2017，44（2）：38-45.

[8] 陳建堯.云計(jì)算下的一種關(guān)聯(lián)挖掘算法的研究[J].科技通報(bào)，2018，34（7）：188-192.

[9] Pang-Ning Tan，Micheal SteinBach，Vipin Kumar. Introduction to Data Mining[M]. 北京：人民郵電出版社，2011：201-303.

【通聯(lián)編輯：唐一東】