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

劉 磊，康瑞華

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

0 引言

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

1 相關(guān)研究

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

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

2 Apriori 算法

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

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

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

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

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

2.1 Apriori 算法改進思想

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

本文將從兩方面對現(xiàn)有Apriori 算法進行改進：

（1）針對事務(wù)數(shù)據(jù)庫掃描次數(shù)過多的問題，本文主要借鑒了文獻［4］的思想，采用與傳統(tǒng)Apriori 算法不同的數(shù)據(jù)結(jié)構(gòu)，將水平的事務(wù)數(shù)據(jù)庫（見表1）轉(zhuǎn)變?yōu)榇怪钡臄?shù)據(jù)結(jié)構(gòu)（見表2）。

Table 1 Transaction database表1 事務(wù)數(shù)據(jù)庫

Table 2 Project database表2 項目數(shù)據(jù)庫

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

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

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

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

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

2.2 改進后的Apriori 算法描述

相關(guān)定義如下：

3 數(shù)據(jù)分析

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

根據(jù)大學生當前的綜合素質(zhì)情況對2 812 份調(diào)查問卷進行分類，并設(shè)計特征因子與權(quán)值，運用本文改進的Apriori算法進行分析。

3.1 垂直數(shù)據(jù)庫建立

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

Table 3 Diversity capability database表3 多元化能力數(shù)據(jù)庫

3.2 改進Apriori 算法數(shù)據(jù)分析

設(shè)置最小支持度0.3 后，由掃描數(shù)據(jù)庫得到頻繁一項集，如表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

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

通過改進Apriori 算法，并設(shè)置min_sup為0.40，對收集到的數(shù)據(jù)進行關(guān)聯(lián)規(guī)則分析得出以下頻繁項集，如表7 所示。

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

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

4 實驗結(jié)果

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

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

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

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

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

5 結(jié)語

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