裘慧奇

（上海理工大學(xué) 信息化辦公室，上海 200093）

人們的行為習(xí)慣對(duì)經(jīng)濟(jì)、社會(huì)、工作及生活等各方面的影響是學(xué)者們努力研究和探索的一個(gè)熱點(diǎn)。與此同時(shí)，大數(shù)據(jù)伴隨著物聯(lián)網(wǎng)、云計(jì)算和人工智能技術(shù)的不斷發(fā)展，在很多領(lǐng)域得到了應(yīng)用和發(fā)展，為研究各行各業(yè)的用戶畫像提供了基礎(chǔ)數(shù)據(jù)來源。如何利用大數(shù)據(jù)對(duì)用戶行為進(jìn)行分析，是數(shù)據(jù)挖掘技術(shù)在用戶行為分析應(yīng)用上的一個(gè)研究難點(diǎn)。關(guān)聯(lián)分析是數(shù)據(jù)挖掘領(lǐng)域較為基礎(chǔ)的數(shù)據(jù)處理方法，利用關(guān)聯(lián)規(guī)則，從目標(biāo)數(shù)據(jù)對(duì)象中挖掘出不同元素之間有意義、有價(jià)值的規(guī)則，從而發(fā)現(xiàn)目標(biāo)數(shù)據(jù)集中的潛在數(shù)據(jù)模式和內(nèi)在聯(lián)系[1]。

近年來，信息技術(shù)在高校學(xué)生管理中的應(yīng)用越來越廣泛，學(xué)生的校園活動(dòng)軌跡也被各類物聯(lián)網(wǎng)設(shè)備和信息系統(tǒng)記錄，如食堂消費(fèi)、門禁進(jìn)出、上課考勤、圖書借閱及上網(wǎng)記錄等，通過這些系統(tǒng)的數(shù)據(jù)記錄，為基于數(shù)據(jù)挖掘技術(shù)的學(xué)生在校行為分析創(chuàng)造了條件。尋找關(guān)聯(lián)規(guī)則是關(guān)聯(lián)分析的核心，通過找出頻繁項(xiàng)目集，并在頻繁項(xiàng)目中找出隱含規(guī)則，是一種在大量數(shù)據(jù)中發(fā)掘某種潛在規(guī)律的數(shù)據(jù)分析方法，可以挖掘出數(shù)據(jù)之間有價(jià)值的關(guān)聯(lián)關(guān)系。應(yīng)用關(guān)聯(lián)規(guī)則最經(jīng)典的例子是啤酒尿布購物習(xí)慣挖掘[2]。利用高校學(xué)生的行為軌跡數(shù)據(jù)集，挖掘?qū)W生行為與學(xué)業(yè)水平之間的關(guān)系是高校在學(xué)生培養(yǎng)上利用大數(shù)據(jù)的一個(gè)經(jīng)典應(yīng)用場景。通過整合學(xué)生在校行為數(shù)據(jù)，運(yùn)用關(guān)聯(lián)規(guī)則方法進(jìn)行數(shù)據(jù)挖掘，構(gòu)建學(xué)生在校行為模型，從而實(shí)現(xiàn)對(duì)在校學(xué)生的行為預(yù)測，對(duì)學(xué)業(yè)水平進(jìn)行預(yù)警，關(guān)注學(xué)生心理健康問題。本文結(jié)合在高校學(xué)生管理過程中的實(shí)際經(jīng)驗(yàn)，在利用學(xué)生行為大數(shù)據(jù)分析時(shí)，對(duì)經(jīng)典Apriori 算法進(jìn)行了改進(jìn)，在保持原有算法的有效性的基礎(chǔ)上，改進(jìn)算法大幅提升了關(guān)聯(lián)規(guī)則挖掘的效率。

1 Apriori 算法及性質(zhì)

Apriori 算法[3]是挖掘海量數(shù)據(jù)中的關(guān)聯(lián)規(guī)則的一個(gè)經(jīng)典算法，通過Apriori 算法，在事務(wù)集D中尋找滿足所有最小支持度閾值的頻繁項(xiàng)集；利用頻繁項(xiàng)集生成所有滿足最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則，從而發(fā)現(xiàn)項(xiàng)目間的關(guān)聯(lián)關(guān)系。

1.1 Apriori 算法的定理

定理1若一個(gè)項(xiàng)集不是頻繁項(xiàng)集，則該項(xiàng)集的所有超集也不是頻繁項(xiàng)集[4]。

定理2頻繁項(xiàng)集的所有非空子集仍是頻繁項(xiàng)集。

Apriori 算法利用定理1，通過連接產(chǎn)生候選項(xiàng)集。對(duì)候選項(xiàng)集進(jìn)行剪枝產(chǎn)生頻繁項(xiàng)集，采用逐層搜索的方法，由頻繁k項(xiàng)集來構(gòu)造候選k+1 項(xiàng)集，當(dāng)沒有新的候選項(xiàng)集產(chǎn)生時(shí)，生成最終頻繁項(xiàng)集。算法雖然簡潔，但需要進(jìn)行大量的計(jì)算。主要存在如下2 方面問題：

a.生成的候選項(xiàng)集數(shù)過多，尤其是候選2-項(xiàng)集。如頻繁1-項(xiàng)集的數(shù)目為n，則會(huì)產(chǎn)生個(gè)候選2-項(xiàng)集使內(nèi)存占用很大；

b.掃描數(shù)據(jù)庫的次數(shù)過多，每次更新支持度的時(shí)候都需要重新掃描數(shù)據(jù)庫，需要很大的I/O 負(fù)載，在時(shí)間、空間上都需要付出很大的代價(jià)。

1.2 算法相關(guān)符號(hào)說明

I表示關(guān)聯(lián)分析事務(wù)數(shù)據(jù)庫的事務(wù)項(xiàng)，由事務(wù)數(shù)據(jù)庫中的項(xiàng)組成。

T表示事務(wù)項(xiàng)I的事實(shí)組合。

Lk-1（i-1）集合表示由Ii組成的k-1-i項(xiàng)目集，i∈（1，k-1）。

sup(Cj) :sup(Ci)=Nj/ |D|表示為項(xiàng)目Cj的支持度，j∈[1,i]。其中，Ci為事務(wù)項(xiàng)的向量矩陣，Nj為Ij在T({Ij})中出現(xiàn)的次數(shù)，|D|為事務(wù)項(xiàng)集數(shù)。

1.3 Apriori 算法的性質(zhì)

性質(zhì)1對(duì)于頻繁k-1 項(xiàng)集的集合Lk-1，如果頻繁項(xiàng)集中的集合個(gè)數(shù)|Lk-1| ＜k，則算法結(jié)束。

性質(zhì)2Lk-1中任意2 個(gè)頻繁k-1 項(xiàng)集自連接后組成的頻繁k項(xiàng)子集為頻繁項(xiàng)集的必要條件：Lk-1中任一頻繁集必須滿足前i個(gè)項(xiàng)的數(shù)目至少為k-i個(gè)。

證明由Lk-1（i-1）集合生成Lk-項(xiàng)集的集合Ck時(shí)，包 含k-項(xiàng) 集X={Ii},i∈[1,k]，且 當(dāng)|Lk-1（i-1）|＜k-i時(shí)，k-項(xiàng)目X不是頻繁k-項(xiàng)目集。其中，|Lk-1（i-1）|表示k-1 頻繁項(xiàng)集的集合Lk-1同時(shí)包含項(xiàng)I(i)的個(gè)數(shù)，i=1,2,···。

假設(shè)上述Ck中，X為頻繁k-項(xiàng)集。根據(jù)排列組合可得，也就是可以合并構(gòu)成一個(gè)k-1 頻繁項(xiàng)集。由X生成的k-1 頻繁項(xiàng)集個(gè)數(shù)為k-i，即|Lk-1（i-1）|=k-i，與假設(shè)矛盾，由此得出：Lk-1中任一頻繁集必須滿足前i個(gè)項(xiàng)的數(shù)目至少為k-i個(gè)。

利用以上性質(zhì)，在自連接之前對(duì)Lk-1進(jìn)行一次枝剪，減少自連接的頻繁項(xiàng)集數(shù)，從而實(shí)現(xiàn)降低候選頻繁集頻度計(jì)算的時(shí)間復(fù)雜度，提高運(yùn)行效率。

2 Apriori 改進(jìn)算法設(shè)計(jì)

由于Apriori 算法需要大量計(jì)算，尤其是對(duì)海量數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析時(shí)效率不高，研究者通過改變數(shù)據(jù)的原始存儲(chǔ)方式和數(shù)據(jù)表達(dá)結(jié)構(gòu)這兩方面進(jìn)行算法優(yōu)化和改進(jìn)。文獻(xiàn)[5]提出的I_Apriori 算法通過映射數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)事務(wù)數(shù)據(jù)庫的方法達(dá)到減少掃描數(shù)據(jù)庫、降低計(jì)算復(fù)雜度的目的。文獻(xiàn)[6]提出的Bloom_Apriori 算法利用布隆函數(shù)過濾壓縮k-項(xiàng)集，精簡事務(wù)集和候選集以提升挖掘效率，節(jié)省計(jì)算資源。文獻(xiàn)[7]提出的FP-growth 算法利用FP-tree 精簡事務(wù)數(shù)據(jù)庫及候選集來減少枝剪次數(shù)。上述文獻(xiàn)的算法都存在不足之處：計(jì)算過程中存儲(chǔ)了大量與頻繁項(xiàng)集無關(guān)的元素，同時(shí)存在重復(fù)掃描矩陣列或事務(wù)項(xiàng)集的情況。

根據(jù)Aprior 算法的性質(zhì)，本文提出了一種利用〈key，valuses〉鍵值轉(zhuǎn)換事務(wù)項(xiàng)集的方法對(duì)Apriori 算法進(jìn)行改進(jìn)。利用〈key，valuses〉鍵值表示將事務(wù)數(shù)據(jù)庫映射為一個(gè)向量矩陣，用行向量來表示每一個(gè)項(xiàng)在事實(shí)事務(wù)組合Ti中的出現(xiàn)情況，‘1’表示存在，‘0’表示不存在。通過動(dòng)態(tài)地分配內(nèi)存進(jìn)行I/O 存儲(chǔ)，根據(jù)向量操作規(guī)則，只需要進(jìn)行向量“與”運(yùn)算就可以快速產(chǎn)生頻繁項(xiàng)集。Apriori 改進(jìn)算法在連接生成新的候選集后，直接進(jìn)行交集運(yùn)算即可得到支持度，省去剪枝過程中的反復(fù)比較，從而優(yōu)化計(jì)算復(fù)雜度。

Apriori 改進(jìn)算法利用向量矩陣數(shù)據(jù)庫，減少掃描數(shù)據(jù)庫次數(shù)和存儲(chǔ)空間，利用向量“與”操作實(shí)現(xiàn)對(duì)連接和枝剪步驟的優(yōu)化，從而降低了候選頻繁集頻度計(jì)算的時(shí)間復(fù)雜度，提高了運(yùn)行效率。Apriori 改進(jìn)算法優(yōu)化關(guān)聯(lián)規(guī)則挖掘的步驟如下：

步驟1重構(gòu)事務(wù)數(shù)據(jù)庫為向量矩陣，并計(jì)算1-頻繁項(xiàng)集集合L1以及1-頻繁項(xiàng)集集合L1對(duì)應(yīng)的〈key，valuses〉值。

掃描數(shù)據(jù)庫一次，將事務(wù)項(xiàng)目數(shù)據(jù)庫轉(zhuǎn)化為項(xiàng)目事務(wù)數(shù)據(jù)庫。記錄每個(gè)1 項(xiàng)集出現(xiàn)的記錄，統(tǒng)計(jì)項(xiàng)目數(shù)，根據(jù)最小支持度刪除不滿足的項(xiàng)集，轉(zhuǎn)換為基于〈key,valuses〉的頻繁項(xiàng)集GetMrItem，從而轉(zhuǎn)換生成新的事務(wù)項(xiàng)集合；

掃描數(shù)據(jù)轉(zhuǎn)換為向量矩陣項(xiàng)目集合C={C1,C2,···,C(i)}，并計(jì)算各項(xiàng)目成員在所有事務(wù)中出現(xiàn)的次數(shù)，分別為N1,N2,···,N(i)。

步驟2計(jì)算滿足最小支持度的k-項(xiàng)集，通過“與”運(yùn)算，生成k項(xiàng)頻繁項(xiàng)集。

采用Apriori 算法的連接，利用“與”運(yùn)算求連接項(xiàng)目的記錄交集，生成新的記錄數(shù)據(jù)庫。

計(jì)算各項(xiàng)目支持度并與預(yù)設(shè)最小支持度min_support 進(jìn)行比較，所有支持度sup(Cj) 大于預(yù)設(shè)最小支持度的項(xiàng)集合便為頻繁k-項(xiàng)集集合Lk-中各元素對(duì)應(yīng)的事務(wù)集合T({Cj})，可構(gòu)建得到頻繁k-項(xiàng)集集合Lk-對(duì)應(yīng)的項(xiàng)集。

步驟3重復(fù)步驟2，直到不再產(chǎn)生滿足最小支持度的項(xiàng)集為止，生成滿足條件的頻繁項(xiàng)集。

整個(gè)計(jì)算過程避免重新掃描原始數(shù)據(jù)庫，而且生成的頻繁項(xiàng)目集越多，掃描的數(shù)據(jù)庫就會(huì)越小，從而提高了運(yùn)行效率。若T中含有n個(gè)項(xiàng)集，則會(huì)生成2n-1 個(gè)候選項(xiàng)集，通過Item-Tidlist列表方式可以生成1-頻繁項(xiàng)集，刪除所有事務(wù)T中不含1-頻繁項(xiàng)集生成新的事務(wù)T′，T′中 含有n′個(gè)項(xiàng)集，且n′≤n，可得 2n′-1 明顯小于 2n-1。從而減少了候選項(xiàng)集數(shù)量。

Apriori 改進(jìn)算法流程偽代碼：

3 Apriori 改進(jìn)算法實(shí)例分析

已知事務(wù)數(shù)據(jù)庫D，如表1 所示，包含5 個(gè)項(xiàng)數(shù)的6 個(gè)事務(wù)，需要計(jì)算最小支持度為3 的頻繁項(xiàng)集。

表1 事務(wù)數(shù)據(jù)庫DTab.1 Transaction database D

步驟1對(duì)Ti求每個(gè)事務(wù)項(xiàng)對(duì)應(yīng)鍵值，合并所有T鍵值，得到下述事務(wù)項(xiàng)對(duì)應(yīng)的鍵值：

〈A，2〉，〈B，2〉，〈C，5〉，〈D，4〉，〈E，5〉，根據(jù)最小支持?jǐn)?shù)閾值，生成頻繁1-項(xiàng)集的集合L1：{〈C，5〉，〈D，4〉，〈E，5〉}。同步轉(zhuǎn)換事務(wù)數(shù)據(jù)庫D為向量矩陣D′，如表2 所示。

表2 向量矩陣D′Tab.2 Vector matrix D′

步驟2轉(zhuǎn)換后的向量矩陣由行向量A=(1,0,0,0,1,0)，B=(1,1,0,0,0,0)，C=(0,1,1,1,1,1)，D=(1,0,1,0,1,1)，E=(1,1,1,1,1,0)組成；對(duì)L1中所有候選項(xiàng)集中的行向量進(jìn)行組合“與”操作。即=(0,0,1,0,1,1)，D∧E=(1,0,1,0,1,0)，C∧D∧E=(0,0,1,0,0,1)，并計(jì)算支持度，結(jié)果如表3 所示。

表3 候選項(xiàng)集“與”操作Tab.3 Results of “and” operation between candidate item set

根據(jù)Apriori 算法的性質(zhì)2，得到頻繁項(xiàng)集L2為{{C，D}，{D，E}}。根據(jù)Apriori 算法的性質(zhì)1，L2中項(xiàng)集個(gè)數(shù)等于2，小于3，因此，不再求頻繁3-項(xiàng)集，最大頻繁項(xiàng)集為頻繁2-項(xiàng)集，即頻繁項(xiàng)集。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)處理

為了利用高校學(xué)生行為數(shù)據(jù)集對(duì)本文算法進(jìn)行算法的有效性和高效性驗(yàn)證，需對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行預(yù)處理。為了挖掘?qū)W生在校行為習(xí)慣與其學(xué)業(yè)成長之間的隱含關(guān)聯(lián)關(guān)系，僅僅對(duì)散落在各個(gè)業(yè)務(wù)系統(tǒng)的數(shù)據(jù)進(jìn)行歸集還無法直接利用關(guān)聯(lián)分析算法進(jìn)行挖掘分析[8]，需要進(jìn)一步清洗、轉(zhuǎn)換和整合生成數(shù)據(jù)挖掘分析的樣本數(shù)據(jù)。為了達(dá)到Apriori算法對(duì)數(shù)據(jù)樣本的要求，需要對(duì)歸集上來的樣本數(shù)據(jù)進(jìn)行離散化處理。本文采用了一種自動(dòng)調(diào)整寬度的數(shù)據(jù)離散化方法[9]。經(jīng)實(shí)踐證明，該方法比較符合高校對(duì)學(xué)生管理的大數(shù)據(jù)處理要求。

將數(shù)據(jù)項(xiàng)屬性值域劃分N個(gè)類別，每個(gè)類別分別對(duì)應(yīng)一個(gè)連續(xù)數(shù)據(jù)區(qū)間，區(qū)間的寬度由該類別的數(shù)據(jù)占整個(gè)數(shù)據(jù)區(qū)間的比例確定。數(shù)據(jù)項(xiàng)屬性值域的類別數(shù)量及占比采用經(jīng)驗(yàn)值法[10]確定，根據(jù)實(shí)際工作經(jīng)驗(yàn)確定不同數(shù)據(jù)項(xiàng)的屬性值域劃分，充分考慮數(shù)據(jù)項(xiàng)的內(nèi)在特點(diǎn)和差異，具有較強(qiáng)的靈活性。

本文選取筆者所在高校一個(gè)年級(jí)學(xué)生（4 400人）一周年系內(nèi)系統(tǒng)產(chǎn)生的統(tǒng)計(jì)數(shù)據(jù)共計(jì)6 054 622條記錄為樣本。包含4 個(gè)維度（圖書館進(jìn)館記錄、無線上網(wǎng)記錄、早餐就餐記錄、學(xué)習(xí)成績），以刷卡進(jìn)圖書館的信息作為學(xué)生去圖書館的依據(jù)，以早上8:00 以前的一卡通消費(fèi)流水作為學(xué)生早起的依據(jù)，以Wifi 上網(wǎng)日志作為學(xué)生上網(wǎng)行為的依據(jù)，以該年級(jí)學(xué)生一學(xué)年內(nèi)選修的52 萬門課程考試成績作為評(píng)價(jià)學(xué)生學(xué)習(xí)成效的依據(jù)。對(duì)學(xué)生訪問圖書館次數(shù)、上網(wǎng)次數(shù)、早餐次數(shù)參照數(shù)據(jù)離散化方法中的第一種方法分別離散為6，5，5 個(gè)區(qū)間；學(xué)習(xí)成績以不及格課程數(shù)量作為離散區(qū)間進(jìn)行預(yù)處理[11]，最終離散為10 個(gè)區(qū)間。同時(shí)去除學(xué)生基本信息以保護(hù)學(xué)生隱私，形成以年級(jí)學(xué)生數(shù)為樣本事務(wù)數(shù)的數(shù)據(jù)庫BehavioTtrajectory DateSet。如表4 所示。

表4 樣本事務(wù)數(shù)據(jù)庫DTab.4 Database of sample transactions D

4.2 實(shí)驗(yàn)環(huán)境

以英特爾酷睿i5 2.9GHz 6 核CPU，DDR4 16G 內(nèi)存，500GB SSD 硬盤配置的PC 為實(shí)驗(yàn)用硬件平臺(tái)，部署Win10 操作系統(tǒng)，在Weka 開源平臺(tái)設(shè)計(jì)實(shí)現(xiàn)。采用上述預(yù)處理數(shù)據(jù)集（學(xué)生在校行為數(shù)據(jù)集BehavioTtrajectory DateSet），共計(jì)6 054 622條記錄來驗(yàn)證Apriori 改進(jìn)算法的有效性[12]和高效性[13]。

4.3 結(jié)果與分析

為了驗(yàn)證Apriori 改進(jìn)算法的有效性，對(duì)數(shù)據(jù)集BehavioTtrajectory DateSet 在相同最小支持度和置信度下分別用Apriori 改進(jìn)算法和Apriori 算法進(jìn)行關(guān)聯(lián)規(guī)則分析，結(jié)果如表5 所示。

表5 相同最小支持度和置信度下頻繁k-項(xiàng)集數(shù)Tab.5 Number of frequent k-item sets with the same minimum support and confidence

結(jié)果顯示，在相同的支持度和置信度下，2 個(gè)算法計(jì)算獲得的k-頻繁項(xiàng)集數(shù)一致。因此，Apriori改進(jìn)算法是有效可靠的，能夠挖掘出準(zhǔn)確的頻繁項(xiàng)集。

對(duì)數(shù)據(jù)集BehavioTtrajectory DateSet 分別采用Apriori 改進(jìn)算法、Apriori 算法、I_Apriori 算法、FP-growth 算法在不同最小支持度情況下的算法執(zhí)行時(shí)間進(jìn)行對(duì)比，結(jié)果如圖1 所示。

圖1 BehavioTtrajectory DateSet 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對(duì)比Fig.1 Comparison of experimental results of Behavio-Ttrajectory DateSet

從圖1 中可以看到，當(dāng)最小支持度超過0.1 以后，Apriori 改進(jìn)算法的效率基本與Apriori 算法一致。但是，當(dāng)降低最小支持度時(shí)，會(huì)發(fā)現(xiàn)Apriori改進(jìn)算法的效率明顯高于Apriori 算法。這是因?yàn)锳priori 算法在產(chǎn)生頻繁項(xiàng)集較多的情況下需要多次掃描數(shù)據(jù)庫，導(dǎo)致I/O 負(fù)擔(dān)過重，且存在大量無效的事務(wù)掃描，而Apriori 改進(jìn)算法則通過掃描一次數(shù)據(jù)庫即可獲得頻繁項(xiàng)集，在頻繁項(xiàng)集較多時(shí)具有明顯的性能優(yōu)勢，與本文改進(jìn)算法的預(yù)期目標(biāo)符合。

為了進(jìn)一步驗(yàn)證Apriori 算法對(duì)潛在k-頻繁項(xiàng)集數(shù)量的敏感性，將上述數(shù)據(jù)集進(jìn)行分解，從中選擇若干工科專業(yè)學(xué)生的行為數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析，將數(shù)據(jù)集降為490 人，行為數(shù)據(jù)714 267 條為樣本數(shù)據(jù)，項(xiàng)目數(shù)保持不變。對(duì)數(shù)據(jù)集Behavio-Ttrajectory-DateSet 分別采用Apriori 改進(jìn)算法、Apriori 算法、I_Apriori 算法、FP-growth 算法在不同最小支持度情況下的算法執(zhí)行時(shí)間進(jìn)行對(duì)比，結(jié)果如圖2 所示。

圖2 BehavioTtrajectory-DateSet 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對(duì)比Fig.2 Comparison of experimental results of Behavio-Ttrajectory-DateSet

從圖2 中可以看到，當(dāng)數(shù)據(jù)集較小時(shí)，4 個(gè)算法對(duì)應(yīng)最小支持度的敏感區(qū)間也相應(yīng)地發(fā)生了變化，這是因?yàn)楫a(chǎn)生頻繁k-項(xiàng)集的數(shù)量發(fā)生了變化。再次驗(yàn)證了影響算法性能主要是在計(jì)算大量頻繁項(xiàng)集的階段。

為了進(jìn)一步驗(yàn)證改進(jìn)算法的正確性，對(duì)同一數(shù)據(jù)集BehavioTtrajectory DateSet 在同一最小支持度和置信度的前提下，分別對(duì)Apriori 改進(jìn)算法、Apriori 算法、I_Apriori 算法、FP-growth 算法比較生成頻繁1-項(xiàng)集和頻繁k-項(xiàng)集（k!=1）時(shí)的速度。在設(shè)定最小支持度為0.05、置信度為0.4 時(shí)，得到的頻繁1-項(xiàng)目數(shù)為14 個(gè)，214-1 ?226-1，實(shí)驗(yàn)證明，在樣本數(shù)據(jù)中存在大量非頻繁項(xiàng)時(shí)，本文算法性能體現(xiàn)出較大的優(yōu)勢。

從圖3 中可以看到，4 個(gè)算法在生成1-頻繁項(xiàng)集時(shí)所需時(shí)間基本相同，Apriori 改進(jìn)算法所需時(shí)間略長，這是因?yàn)锳priori 改進(jìn)算法在生成1-頻繁項(xiàng)時(shí)，需要轉(zhuǎn)秩事務(wù)項(xiàng)集數(shù)據(jù)庫；但是，在后續(xù)k-頻繁項(xiàng)集生成過程中，I_Apriori 算法、FP-growth算法較經(jīng)典Apriori 算法性能有明顯提升，其中，Apriori 改進(jìn)算法性能優(yōu)勢更加明顯。

圖3 生成頻繁k-項(xiàng)集效率對(duì)比Fig.3 Efficiency comparison about generating frequent kitem set

4.4 算法應(yīng)用分析

利用本文算法關(guān)聯(lián)分析學(xué)生在校活動(dòng)與學(xué)生成長的關(guān)系，為學(xué)校制定培養(yǎng)人才方案提供依據(jù)。以是否有早餐消費(fèi)頻次為判斷學(xué)生是否有晚起習(xí)慣，以前往圖書館頻次作為判斷學(xué)生是否有自我約束能力[14]，以上網(wǎng)頻次來判斷學(xué)生是否有網(wǎng)癮，并根據(jù)以上維度來關(guān)聯(lián)分析對(duì)學(xué)生成績的影響。挖掘關(guān)聯(lián)規(guī)則結(jié)果如表6 所示。

表6 在?；顒?dòng)與學(xué)生成長的關(guān)聯(lián)規(guī)則Tab.6 Association rules between school activities with students' growth

通過調(diào)整最小支持度和最小可信度，在最小支持度為0.2、可信度大于60%的規(guī)則下產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則5 條，分析可得，有良好生活習(xí)慣、具有自我約束能力（定期去圖書館）的學(xué)生，學(xué)習(xí)成績基本不掛科。

另外，分析有掛科情況的學(xué)生的行為習(xí)慣，將樣本數(shù)據(jù)中無掛科學(xué)生的記錄清除后進(jìn)行關(guān)聯(lián)分析，發(fā)現(xiàn)同樣在最小支持度為0.2、可信度大于60%的規(guī)則下，習(xí)慣早起（有早餐消費(fèi)習(xí)慣）的同學(xué)掛科數(shù)較少，且這類學(xué)生也會(huì)不定期去圖書館，對(duì)無線網(wǎng)絡(luò)也不特別依賴。

5 結(jié)束語

Apriori 算法是經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，但是，由于每次更新支持度時(shí)都需要重新掃描數(shù)據(jù)庫，需要很大的I/O 負(fù)載，在時(shí)間、空間上都需要付出很大的代價(jià)。Apriori 改進(jìn)算法通過轉(zhuǎn)換事務(wù)項(xiàng)集的方法對(duì)Apriori 算法進(jìn)行改進(jìn)，在頻繁項(xiàng)集求解過程中減少數(shù)據(jù)庫的掃描次數(shù)，降低了I/O 消耗，利用向量“與”運(yùn)算提高了運(yùn)算效率。Apriori改進(jìn)算法在連接生成新的候選集后，無需再進(jìn)行枝剪即可直接取交集運(yùn)算獲取支持度，省去剪枝過程中反復(fù)比較，從而達(dá)到了性能優(yōu)化的目的。同時(shí)，在驗(yàn)證Apriori 改進(jìn)算法時(shí)，利用現(xiàn)實(shí)生活中的行為軌跡數(shù)據(jù)，通過數(shù)據(jù)預(yù)處理形成一個(gè)樣本數(shù)據(jù)集，驗(yàn)證了Apriori 改進(jìn)算法的有效性，又通過對(duì)比經(jīng)典Apriori 算法及若干Apriori 優(yōu)化算法驗(yàn)證了本算法的高效性。