面向學生成績分析的高效關聯規則挖掘算法研究

周日輝

摘要：數據挖掘技術是在大數據環境下，通過利用關聯規則挖掘等技術方法，進行知識發現，其核心過程是挖掘算法在起關鍵作用。文章分析了關聯規則挖掘技術原理，以學生成績作為數據樣本，對其算法進行分析，探討算法優化思路，提出高效的算法改進方案并驗證。為進一步利用關聯規則挖掘技術探索教育領域的數據挖掘應用研究打下堅實的基礎。

關鍵詞：數據挖掘；關聯規則；學生成績；算法；教育

中圖分類號：TP399? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）30-0048-03

開放科學（資源服務）標識碼（OSID）：

1? 關聯規則挖掘概述

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

支持度計數[3]? σ（P）=|{ tj| P ?tj，tj∈Trans}|；對于關聯規則挖掘結果的某一條蘊涵式“P->Q”，其中項集P和項集Q的關系為P∩Q= {φ}，關聯規則質量的評估標準可以用“s”（支持度）和“c”（置信度）來衡量。

支持度[3] s（P->Q） = σ（P∪Q） / N （N為事務集合中事務項的總數）；

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

關聯規則挖掘可以定義為，在給定的事務集合“Trans”上，搜索發掘支持度超過支持度閾值并且置信度也超過置信度閾值的所有形如“P->Q”的規則。

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

2? 關聯規則挖掘算法

2.1 Apriori算法描述

Apriori算法[5]是解決關聯規則挖掘工作的第一個算法，算法根據關聯規則挖掘的兩個任務而設計，頻繁項集的產生及規則的產生，在實踐過程中會發現前者的計算開銷遠大于后者。

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

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

2.2 Apriori算法的改進

本文針對高校學生成績開展關聯規則挖掘以探索高校育人規律，以廣東茂名幼兒師范專科學校歷年的學生數據作為原始數據。為保證數據挖掘質量與目標，選擇的原始成績數據的學生應為相同或相近專業，成績數據應包含學生相同學期區間的成績項，成績數據中的學生年級可以不同，但應為相同學年制。通過數據預處理，對原始數據存在的空值、非法記錄等異常情況作清洗處理，以及數據格式和數據類型的轉換。數據類型轉換主要是由于成績數據為連續型屬性，為適應關聯挖掘算法的應用，需要對成績數據進行“離散化”[6]處理，即分等級。

對Apriori算法進行改進的方法，就是在算法執行頻繁項集挖掘任務的過程中，通過縱、橫兩個維度對事務集的質量及數據量進行調整，其進行改進思想如下：

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

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

2.3 改進算法偽代碼

算法： New_Apriori

輸入：事務集T，項目集合I，支持度閾值minSup，成績等級比例閾值overSup，成績等級數量閾值minGrd。

輸出：T中的頻繁項集。

方法：

（1）? k = 1

（2）? for 每個項i∈I

（3）? { if（σ（i）>= N*overSup ∨ testGrade（i ， minGrd）==true）（測試該項所占比例是否過高，和該科目的成績等級分布是否過窄）

（4）? { I.deleteItem（i）? ? ? ? （刪除該項）

（5）? T.deleteColumns（i）? ? ?（事務數據集刪除該數據列）

（6）? }

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

（8）? Fk.add（i）? ?（發現所有頻繁1-項集）

（9）? ?}

（10）? repeat

（11）? k = k+1

（12）? Ck = apriori_gen（Fk - 1）? ? ?（產生候選項集）

（13）? for 每個事務t∈T

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

（15）? for 每個候選項集 c∈Ct

（16）? {σ（c）? = σ（c） + 1? ? （項集c增加支持度計數）

（17）? }}

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

（19）? CompressInstances（T，Fk）? ? （事務集的壓縮，在事務集T中刪除不包含任何頻繁項集的事務）

（20）? until Fk = ?

（21）? Return =∪Fk

算法： CompressInstances函數，通過排除不包含任何頻繁K-項集的事務進行事務集合的壓縮

輸入：事務集T，頻繁K-項集集合itemSets

輸出： 壓縮后的事務集合

方法：

（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? ?（判斷當前頻繁K-項集是否被第i個事務包含）

（7）? ?containItemSet <-- true

（8）? break

（9）? ? end if

（10） end while

（11）? if containItemSet = false? do

（12）? T.delete（i）? ?（事務集刪除第i個事務）

（13）? end if

（14） end for

（15）? end function

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

3? 改進算法的驗證

對于使用數據挖掘算法得到的關聯規則，建立一種廣泛接受并合乎客觀實際的評估標準尤為重要，客觀興趣度度量是利用數據驅動評估規則質量，客觀興趣度分析是在支持度與置信度之外，考究規則前后件的“相關性”，使用“提升度值（lift）”[8]進行度量，亦被稱作“興趣因子”，它計算關聯規則的置信度與規則后件的支持度之間的比率，即：

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

提升度值（lift）參數的意義在于，在置信度已經考慮了規則前件支持度參數的基礎上，再考慮規則后件支持度進行概率計算，當其值等于1，說明P與Q是獨立事件，當其值大于1，P與Q存在正相關性[9]，值小于1則存在負相關性，存在正相關性且其值越大則代表規則前后件有積極的依賴關系或因果關系，而負相關性則代表這兩個事件有消極的影響關系，在實際應用中，前后件呈正相關性或負相關性的，尤其是正相關而且其提升度值越大的關聯規則是更值得關注的。

對改進算法的驗證，首先選取學校200名學生80項科目的成績作為數據樣本，運行改進算法及原算法，對比兩者的工作情況進行驗證。對兩算法所獲得的高支持度高置信度的規則進行“客觀興趣度”的質量評估，通過在設定相同支持度閾值及置信度閾值的情況下，對比兩算法挖掘出“相關性”高的規則占總規則數量比例的高低。

在挖掘過程中，為保證規則質量，不斷調整算法參數以達到最合理，設置支持度閾值上下限分別為0.6及0.3，當置信度閾值設置為0.8時，隨著設置挖掘的最優規則總數量的變化，兩個算法的挖掘結果中，“客觀興趣度”高的規則比例對比情況如表1所示，當置信度閾值為0.9時的情況類似。

接下來，對比兩算法的運行效率，設置相同的支持度閾值情況，設置挖掘的最優規則數量為100，不斷改變置信度閾值，每設定一個置信度閾值，運行算法10次取平均值，兩算法運行時間的對比情況見圖1。

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

以上實驗結果顯示，在10個隨機數據樣本的實驗中，改進算法產生的高客觀興趣度規則的平均比例為39%，高于原算法29%，改進算法運行的平均時間為3859（ms），效率高于原算法27356（ms）。實驗結果與以真實成績作為數據樣本的實驗結果基本吻合。

4? 結束語

綜上所述，通過對關聯規則挖掘算法的改進，在效率和挖掘質量上都有一定提升，在效率上的提升較為明顯。原算法在設計上是為迎合不同挖掘需求，在使用上具有普適性。本文的算法改進方案是針對學生成績數據挖掘或與此應用情況類似的場景而設計，挖掘過程比原算法更高效，為通過對學生成績等教育資源數據進行數據挖掘，進一步構建完整的系統應用提供有力的技術支持。

參考文獻：

[1] 康君.教育數據挖掘服務平臺的設計與實現[D].濟南：山東師范大學，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] 李忠，安建琴，劉海軍，等.關聯挖掘算法及發展趨勢[J].智能計算機與應用，2017，7（5）：22-25.

[4] 李強.數據挖掘中關聯分析算法研究[D].哈爾濱：哈爾濱工程大學，2010.

[5] 趙峰，劉博妍.基于改進Apriori算法的大學生成績關聯分析[J].齊齊哈爾大學學報（自然科學版），2018，34（1）：11-15.

[6] 譚誠.基于數據挖掘的義務教育績效考核分析系統的設計與實現[D].長沙：湖南大學，2016.

[7] 琚安康，郭淵博，朱泰銘，等.網絡安全事件關聯分析技術與工具研究[J].計算機科學，2017，44（2）：38-45.

[8] 陳建堯.云計算下的一種關聯挖掘算法的研究[J].科技通報，2018，34（7）：188-192.

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

【通聯編輯：唐一東】