改進Apriori 算法在學生能力影響因子分析中的應用

劉 磊，康瑞華

（湖北工業大學計算機學院，湖北武漢 430072）

0 引言

隨著信息技術的發展與智能時代的到來，社會教育系統的變革逐漸頻繁，學生綜合素質能力培養顯得尤為重要。本文通過對2 000 多名來自不同地域、不同學校與不同專業的大一、大二學生的問卷調查，應用Apriori 算法分析其學習生涯中曾進行的能力培養對當前大學時期綜合素質的影響，從而給予當前學生成長過程中多元化教育選擇以方向性指導［1］。

1 相關研究

大數據是繼云計算、物聯網之后，計算機行業又一次顛覆性的技術革命。大數據挖掘與應用可創造出很高的經濟價值，將是未來計算機領域最大的市場機遇之一［2］。大數據的應用在生活中也屢見不鮮，例如大數據在電視臺數據處理中的應用［3］、大數據在金融投資中的應用［4］、關聯分析在教育領域的應用等［5-17］。

在大數據應用過程中，其常常引發人們對算法本身的思考。我國近年來在大數據分析領域的研究進展很快，在研究起始階段，劉君強等［18］收集整理近年來關于關聯規則的詳細研究，針對大數據分析領域的新進展進行綜述與分析，并根據基礎大數據分析算法Apriori 的特點，提出Apriori 算法優化的初步方向與思想。之后，王偉勤等［19］提出改進Apriori 算法的具體內容，即采用基于數組，且避免Apriori 的匹配模式，通過只掃描一次，同時減少算法內存占用空間的方式提高算法效率，并對該方法進行驗證，但其仍存在兩個關鍵問題：掃描次數與剪枝效率。本文在此基礎上對掃描方式和數據結構存儲兩個關鍵問題進行優化與改進，通過分析學生能力影響因子，探究Apriori 算法的改進思路與方法。

2 Apriori 算法

Apriori 算法常用的頻繁項集評估標準有3 個：支持度、置信度和提升度。其中，支持度是關聯數據在數據集中出現的概率，支持度高的數據不一定構成頻繁項集，但是構成頻繁項集的數據支持度肯定不低。置信度則體現一個數據出現后，另一個數據出現的概率，即數據的條件概率。如大學生幼年培訓奧數對應鋼琴的置信度為60%，支持度為5%，說明總共有5%的學生在幼年培訓了奧數和鋼琴，培訓了奧數的學生中有60%的人培訓了鋼琴。提升度則表示兩個數據之間的管理關系，也即在培訓奧數的情況下同時培訓鋼琴的概率與培訓鋼琴總體發生概率之比。若提升度大于1，則鋼琴?奧數是有效的強關聯規則；若提升度小于等于1，則鋼琴?奧數是無效的強關聯規則［8，14-16］。

Apriori 算法采用逐層搜素策略，同時依據其性質壓縮搜索空間。其基本思想在于，首先掃描一次事務數據集，找出頻繁一項集集合L1，然后基于L1產生所有可能的頻繁二項集即候選集C2，篩選出候選項集C2中所有滿足最小置信度的項集，組成頻繁項集L2。用上述步驟重復處理新得到的頻繁項集Lx，直至再也找不出頻繁項集時退出［17-19］。

在Apriori 算法中，候選項集的生成可分成連接和剪枝兩部分。為提高剪枝效率，運用了以下兩個重要定律：

定律1 如果k維數據項Xk是頻繁項集，則其k-1 維子集都是頻繁項集。

定律2 如果k-1 維數據項Xk-1不是頻繁項集，則其k維超集都不是頻繁項集。

2.1 Apriori 算法改進思想

Apriori 算法得到了廣泛運用，主要由于其算法結構簡單易懂、便于理解，沒有復雜的公式推導［2］。通過運用兩個重要定律，使得算法候選集的規模大幅減小，相應算法運算速度大幅提高，但其仍存在兩個影響內存及效率的問題：①事務數據庫掃描次數過多。每次尋找頻繁項集都需要掃描一次事務數據庫，最終尋找到長度為k的頻繁項集共需掃描k次，所以當數據庫或k很大時，算法耗時將呈幾何式增長；②在執行候選集的剪枝操作時，對數據庫的掃描次數過多。而且當候選集與自身連接時也要對數據庫進行多次掃描，導致算法在廣度優先方面的適應性很差［10-13］。

本文將從兩方面對現有Apriori 算法進行改進：

（1）針對事務數據庫掃描次數過多的問題，本文主要借鑒了文獻［4］的思想，采用與傳統Apriori 算法不同的數據結構，將水平的事務數據庫（見表1）轉變為垂直的數據結構（見表2）。

Table 1 Transaction database表1 事務數據庫

Table 2 Project database表2 項目數據庫

通過這種轉換將事務數據庫垂直化，只需掃描一次數據庫即可完成數據分析，并且更容易得到支持k維數據項的事務數。

（2）針對冗余數據項過多、剪枝次數過多以及連接產生數據項空間較大的問題，本文利用算法的兩個定律推斷出第3 個定律：

定律3 對于k維數據項x={i1,i2,i3…,ik}，如果存在一個元素j?x，使表示在k-1維頻繁項集中包含j的數量)，則x不是頻繁項集。

證明：若x是k維頻繁項集，則由定律1 可得，其共有=k個k-1 維子集為頻繁項集，其中包含j的共有=k-1 個。由于上述子集均為頻繁項集，故得到≥k-1，與假設矛盾，所以x不是k維頻繁項集。

從這一定律可以得出：如果在Lk-1中有一元素j，且有＜k-1，則所有包含元素j的k-1 維頻繁項集不參與連接。

2.2 改進后的Apriori 算法描述

相關定義如下：

3 數據分析

本文通過分析當前中小學教育政策、大學生培養計劃、企業需求以及大學新生心理，設計了關于大學生能力培養方式與當前時期適應力、自信心的調查問卷，并通過問卷星發放到包括985、211、普通高校在內的10 所高校，回收問卷共計2 812 份。之后使用Apriori 算法進行數據分析，Apriori 算法是一種挖掘布爾關聯規則頻繁項集（Bourg association rules frequent itemsets）的經典算法，用來尋找數據值中頻繁出現的數據集合。本文通過尋找當前大學生曾經參與過的多元化培訓對其綜合素質與自信心影響最大的特征數據結果集，根據該結果集為當前教育過程中的多元化能力個性培訓提供指導性方案。

根據大學生當前的綜合素質情況對2 812 份調查問卷進行分類，并設計特征因子與權值，運用本文改進的Apriori算法進行分析。

3.1 垂直數據庫建立

將收集的數據按照表2 的數據結構錄入項目數據庫，調查結果中的每一項包含多個選項，如果每個選項都由一個數據進行記錄，則需要龐大的數據空間進行記錄（若有4個選項則需4 位，但采用下述方法只需2 位）。在實際數據分析過程中，為每個選項進行編碼，如針對“結業成果是否有用”這一項，可進行如下二進制編碼：00：有很大作用；01：有作用但不大；10：基本沒什么作用。該方法相比位存儲有效減少了數據存儲空間。為更直觀地理解算法過程，下述分析示例不按以上方法進行編碼處理，而是直接用數據名稱表示，如表3 所示。

Table 3 Diversity capability database表3 多元化能力數據庫

3.2 改進Apriori 算法數據分析

設置最小支持度0.3 后，由掃描數據庫得到頻繁一項集，如表4 所示。

Table 4 Frequent itemsets L1表4 頻繁一項集L1

由于當L1不存在需要剪枝的元素即可進行連接，通過連接篩選得到L2，如表5 所示。

此時進行剪枝，其元素列表為｛書法，書法班，樂器類，是，有很大作用｝，所有元素均符合約束，所以無剪枝項，連接并篩選得到L3，如表6 所示。

Table 5 Frequent binomial sets L2表5 頻繁二項集L2

Table 6 Frequent trinomial sets L3表6 頻繁三項集L3

再次進行剪枝操作，由于｛書法｝的數量少于3 即可進行剪枝，此時元素列表為｛書法班，樂器類，是，有很大作用｝，連接篩選得到L4：｛書法班，樂器類，是，有很大作用｝。

通過改進Apriori 算法，并設置min_sup為0.40，對收集到的數據進行關聯規則分析得出以下頻繁項集，如表7 所示。

Table 7 All frequent itemsets表7 所有頻繁項集

由表7 可知，｛主動參加，成果有很大作用｝與｛樂器類，主動參加｝屬于頻繁項集，表示學生主動參加并覺得成果有很大作用的概率相對較大，其具有高置信度，說明學生在主動參加特長班之后，有很大概率認為成果有很大作用。對于第二個頻繁項集，亦可用相同思想進行分析。

4 實驗結果

根據本文的改進Apriori 算法思想，將上述數據整理分析過程與傳統的Apriori 算法分析過程從數據量與運行時間兩方面進行對比。具體說明如下：

（1）測試環境：本次測試采用Python 語言編程，操作系統為Windows 10，處理器為Intel 酷睿i7-6500 雙核處理器，內存大小為8GB。

（2）測試結果：通過對2 800 多份問卷進行分析，提取特征數據，并針對不同數據量進行測試與對比，得到結果如圖1 所示。

通過圖1 可以看出，本文提出的改進Apriori 算法相比傳統Apriori 算法可以有效縮短運行時間，加快數據處理速度。而且隨著數據量的增加，算法效果有一定程度提升。

Fig.1 Comparison of running time of each data volume test圖1 各數據量測試運行時間對比

5 結語

本文提出的改進Apriori 算法主要思想來自于兩個方面：①改變數據庫結構為項目數據庫結構，傳統的事務數據庫結構會造成多次掃描數據庫，帶來很大的時空開銷［time and memory-consuming］，而采用項目數據庫結構只需掃描一次即可完成整個算法的運行；②根據算法特性設計剪枝操作，相比傳統算法的剪枝操作，在一定程度上能夠提升算法性能。改進Apriori 算法在不同數據量情況下對傳統算法的提升效果不同，當數據量為8 000 時，改進Apriori 算法的運行時間相比傳統算法縮短了7.15%，算法效果得到了相當大程度的提升。但不足之處在于當數據量很大時，依舊需要大量時空開銷，其開銷主要存在于剪枝操作中。若能找到更好的剪枝操作方法，則能對算法作進一步改進。