基于分級教學(xué)的Apriori算法改進(jìn)

李 志

(武警學(xué)院 基礎(chǔ)部，河北 廊坊 065000)

基于分級教學(xué)的Apriori算法改進(jìn)

李 志

(武警學(xué)院 基礎(chǔ)部，河北 廊坊 065000)

學(xué)員之間計算機(jī)基礎(chǔ)能力的巨大差異，使《大學(xué)計算機(jī)基礎(chǔ)》實踐課程分級教學(xué)的需求越來越強烈。如何擺脫單純依靠測試分?jǐn)?shù)進(jìn)行分級的簡單方法，得到更加客觀、高效的分級結(jié)果，是實施分級教學(xué)急需解決的首要問題。結(jié)合分級教學(xué)的應(yīng)用目的，將Apriori算法從減少事務(wù)數(shù)據(jù)庫中事務(wù)數(shù)量和減少候選項集項數(shù)兩方面改進(jìn)后，從新學(xué)員計算機(jī)基礎(chǔ)能力表中得到對分級結(jié)果起決定作用的強關(guān)聯(lián)規(guī)則，提高了分級結(jié)果的客觀性和高效性。

大學(xué)計算機(jī)基礎(chǔ)；分級教學(xué)；關(guān)聯(lián)規(guī)則；Apriori

一、研究背景

隨著大學(xué)生入伍的普及，戰(zhàn)士本科生源中計算機(jī)基礎(chǔ)能力差異越發(fā)明顯，為計算機(jī)基礎(chǔ)教學(xué)，尤其是《大學(xué)計算機(jī)基礎(chǔ)》實踐課程教學(xué)帶來很大挑戰(zhàn)。經(jīng)過廣泛查閱資料、調(diào)查分析、認(rèn)真思考，筆者認(rèn)為：為有效解決學(xué)員計算機(jī)基礎(chǔ)能力差異帶來的教學(xué)矛盾，目前最好的方法就是實施分級教學(xué)。[1]

分級教學(xué)，在承認(rèn)學(xué)員個別差異的前提下，確立以學(xué)員為主體的意識，在調(diào)查問卷、能力測試、交流座談等基礎(chǔ)上，結(jié)合學(xué)員個人意愿，依據(jù)教學(xué)大綱和教學(xué)內(nèi)容要求，對學(xué)員的教學(xué)進(jìn)行分級。

為保證分級教學(xué)的有效性，必須首先制定完備、適用、有效的學(xué)員分級、教學(xué)目標(biāo)分級和評價分級方案。其中，對學(xué)員科學(xué)合理的分級是成功實施分級教學(xué)的前提。在充分了解學(xué)員實際情況的前提下，結(jié)合學(xué)員的入學(xué)計算機(jī)測試成績、基礎(chǔ)能力調(diào)查，在尊重學(xué)員意愿的基礎(chǔ)上，按照學(xué)員基礎(chǔ)水平和學(xué)習(xí)意愿，將學(xué)員劃分為不同的等級層次。這是一種比較全面、比較理想的學(xué)員分級方法。目前，陸續(xù)有一些高等院校對計算機(jī)基礎(chǔ)課程實施了分級教學(xué)。但是，在實踐應(yīng)用中，大多數(shù)高等院校都采用了摸底成績決定制的方法對學(xué)員進(jìn)行簡單分級。雖然有些高等院校對學(xué)員事先進(jìn)行了問卷調(diào)查或座談等，但并沒有應(yīng)用到學(xué)員分級過程中，忽略了一些主、客觀因素可能對摸底成績的影響，使對學(xué)員的分級可能出現(xiàn)一些片面性，分級結(jié)果具有偶然性。數(shù)據(jù)挖掘技術(shù)在《大學(xué)計算機(jī)基礎(chǔ)》實踐課程中對學(xué)員分級的應(yīng)用，將有效提高分級結(jié)果的客觀性和有效性。

二、Apriori算法

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域重要的研究方向之一。關(guān)聯(lián)規(guī)則的任務(wù)是：給定一個事務(wù)數(shù)據(jù)庫D，在基于支持度、置信度框架中，發(fā)現(xiàn)數(shù)據(jù)與項目之間大量有趣的相關(guān)聯(lián)系，生成所有支持度和置信度分別高于用戶給定的最小支持度和最小置信度的關(guān)聯(lián)規(guī)則，以揭示數(shù)據(jù)與數(shù)據(jù)之間未知的相互依賴關(guān)系。[2]

目前，關(guān)聯(lián)規(guī)則技術(shù)在數(shù)據(jù)挖掘領(lǐng)域研究中，主要應(yīng)用于挖掘大規(guī)模數(shù)據(jù)集數(shù)據(jù)間潛在的、有價值的聯(lián)系，它既可以檢驗業(yè)內(nèi)長期形成的知識模式，也能發(fā)現(xiàn)其中隱藏的新規(guī)律[3]，其應(yīng)用已經(jīng)從開始的商業(yè)指導(dǎo)廣泛發(fā)展到社會的各個領(lǐng)域，如醫(yī)療、金融、保險、教育等。

Apriori算法根據(jù)有關(guān)頻繁項集特性的先驗知識而命名，它使用一種逐層搜索的迭代方法來完成頻繁項集的挖掘工作。它是最成熟、最具有影響力的關(guān)聯(lián)規(guī)則挖掘算法之一。

為保證關(guān)聯(lián)規(guī)則的質(zhì)量，需要對規(guī)則進(jìn)行支持度、置信度和提升度的計算。

關(guān)聯(lián)規(guī)則是如同A?B的蘊含式[4]，項目集A，B均屬于I，且A∩B=?。關(guān)聯(lián)規(guī)則的支持度用Support表示，規(guī)則A?B在事務(wù)數(shù)據(jù)庫D中的支持度，是指包含項目集A和B的事務(wù)在事務(wù)數(shù)據(jù)庫D所有事務(wù)之中所占的百分比。其表達(dá)式如下所示：

Support(A?B)=P(A∪B)

關(guān)聯(lián)規(guī)則的置信度用Confidence表示，規(guī)則A?B的置信度，是指同時包含項目集A和B的事務(wù)在所有包含項目集A的事務(wù)中所占的百分比。其表達(dá)式如下所示：

Confidence(A?B)=(Support(A?B))/

(Support(A))= P(B|A)

關(guān)聯(lián)規(guī)則的提升度用Lift表示，規(guī)則A?B的提升度，是目標(biāo)的密度(置信度)對總目標(biāo)的密度(規(guī)則中右端的結(jié)果)的比率。其表達(dá)式如下所示：

Lift(A,B) =P(A∩B)/P(A)P(B)

=P(B|A)/(P(B))

支持度是對關(guān)聯(lián)規(guī)則重要性的衡量，表示規(guī)則的頻度。支持度越大，說明關(guān)聯(lián)規(guī)則越重要，同時說明這條規(guī)則應(yīng)用越廣泛。置信度是對關(guān)聯(lián)規(guī)則準(zhǔn)確度和可信度的衡量，表示規(guī)則的強度。提升度是判斷強關(guān)聯(lián)規(guī)則對后件屬性的正相關(guān)性的運算，Lift(A,B)>1，說明A與B正相關(guān)，否則，說明A與B負(fù)相關(guān)。

三、算法的改進(jìn)

(一)傳統(tǒng)Apriori算法存在問題

由于Apriori算法采用多次迭代的算法，嚴(yán)格按標(biāo)準(zhǔn)尋找不小于最小支持度的頻繁項，此過程中需要多次掃描事務(wù)數(shù)據(jù)庫。在事務(wù)數(shù)據(jù)庫較少的情況下，該算法的性能很好，但隨著事務(wù)數(shù)據(jù)庫的增大，其較為嚴(yán)重的性能瓶頸就顯現(xiàn)了[5]：

1.多次掃描事務(wù)數(shù)據(jù)庫，需要的I/O負(fù)載很大。在每次迭代過程中，候選項集的每一項都需要重新掃描事務(wù)數(shù)據(jù)庫來確定其是否為頻繁項集，候選項集中項數(shù)越多，需要掃描事務(wù)數(shù)據(jù)庫的遍數(shù)就越多，增大了I/O負(fù)載。

2.可能產(chǎn)生龐大的候選項集，造成時間和空間威脅。候選項集都是由前一項頻繁集連接生成的，其數(shù)量成指數(shù)增長。隨著頻繁項集的計算，候選項集的數(shù)量可能會變得極為龐大。這時，將對頻繁項集的計算時間和當(dāng)前存儲空間造成很大的威脅。

(二)以分級教學(xué)為應(yīng)用目的的算法改進(jìn)

針對Apriori算法面臨的兩大缺陷，對于該算法的改進(jìn)主要從減少事務(wù)數(shù)據(jù)庫中事務(wù)數(shù)量和減少候選項集項數(shù)兩方面著手:

1.越過1項頻繁集，直接計算2項頻繁集。根據(jù)Apriori算法在此的應(yīng)用目的是尋找對分級結(jié)果起決定作用的強關(guān)聯(lián)規(guī)則，確定其應(yīng)用目的為生成關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則至少涉及兩個不同的項，因此1項頻繁集在這里計算沒有任何意義，可以直接越過，生成2項候選集，進(jìn)入2項頻繁集的運算。

2.對候選項集進(jìn)行過濾，只保留分級結(jié)果為后件的項。根本目的是尋找分級結(jié)果為后件的強關(guān)聯(lián)規(guī)則，因此，可以對候選項集進(jìn)行過濾，只保留分級結(jié)果字段為后件的項作為候選項集即可，這樣，在很大程度上減少了候選項集的數(shù)量。同時，在強關(guān)聯(lián)規(guī)則的判斷過程中，也只需要對分級結(jié)果為后件的規(guī)則計算其支持度。

3.強關(guān)聯(lián)規(guī)則分次計算，及時刪除確定為強關(guān)聯(lián)規(guī)則的對應(yīng)事務(wù)。因為可以預(yù)想到某些特定項(如：入伍前為計算機(jī)相關(guān)專業(yè))對分級結(jié)果有著很強的決定作用，如果某個事務(wù)已經(jīng)存在此前提，就沒必要再進(jìn)行下一項頻繁集的計算，所以第1步可以先把這種起決定作用的強關(guān)聯(lián)規(guī)則進(jìn)行計算并存儲、輸出。同時，該事務(wù)其他項也失去了強代表性，可以從事務(wù)數(shù)據(jù)庫中刪除。

4.及時刪除數(shù)據(jù)項小于當(dāng)前頻繁項集個數(shù)的事務(wù)。一個非頻繁項集，它的所有超集也一定是非頻繁項集。因此，在計算候選項集支持度前，可以先對事務(wù)數(shù)據(jù)庫進(jìn)行預(yù)掃描，將不包含任何候選項集的事務(wù)刪除，再進(jìn)行候選項集支持度的掃描和計算。

四、改進(jìn)算法在分級教學(xué)中的應(yīng)用實現(xiàn)

在分級教學(xué)過程中，根據(jù)教學(xué)內(nèi)容，綜合考慮學(xué)習(xí)者生理、心理特點，結(jié)合學(xué)習(xí)者學(xué)習(xí)能力水平，制定客觀、科學(xué)、合理的層次劃分標(biāo)準(zhǔn)是有效實施分級教學(xué)的首要問題和關(guān)鍵問題。因此，在我院《大學(xué)計算機(jī)基礎(chǔ)》實踐課程的分級教學(xué)中采用入學(xué)摸底測試、調(diào)查問卷和學(xué)生意愿三者結(jié)合的方法。

為充分了解我院入學(xué)新學(xué)員計算機(jī)基礎(chǔ)能力，在學(xué)員開設(shè)計算機(jī)基礎(chǔ)課程前，統(tǒng)一填寫“武警學(xué)院入學(xué)新生計算機(jī)水平調(diào)查問卷”，其內(nèi)容包括籍貫、家庭情況、計算機(jī)學(xué)習(xí)情況、計算機(jī)技能掌握情況、計算機(jī)技能拓展情況、上網(wǎng)情況、興趣判斷等。由于生源的特殊性，對于戰(zhàn)士生源的學(xué)員還應(yīng)該包括入學(xué)前服役地、入學(xué)前工作性質(zhì)、入伍前最高學(xué)歷、是否大學(xué)生入伍、是否計算機(jī)相關(guān)專業(yè)等信息。其結(jié)構(gòu)如表1所示。

表1 新生計算機(jī)水平調(diào)查表

為保證調(diào)查結(jié)果的客觀性，調(diào)查問卷設(shè)計力求全面。然而，在實際應(yīng)用中，這些字段并不一定與分級結(jié)果密切相關(guān)，不適宜用于分級依據(jù)。關(guān)聯(lián)規(guī)則Apriori算法在《大學(xué)計算機(jī)基礎(chǔ)》實踐課程分級教學(xué)的應(yīng)用目的，就是為了通過對調(diào)查信息進(jìn)行分析，從眾多字段中尋找與分級結(jié)果密切相關(guān)的字段，以輔助以后的分級過程。

大多數(shù)數(shù)據(jù)挖掘算法都要求處理離散型數(shù)據(jù)，即便是可以處理連續(xù)型數(shù)據(jù)的算法，相對來說，離散型數(shù)據(jù)處理也更簡單、更直觀。因此，在對采集的原始問卷調(diào)查數(shù)據(jù)進(jìn)行數(shù)據(jù)清理后，還需要對其中籍貫和入學(xué)前工作性質(zhì)兩個字段進(jìn)行離散化。

對入學(xué)前工作性質(zhì)進(jìn)行匯總整理，其取值可以概括為：戰(zhàn)斗員、通訊員、衛(wèi)生員、話務(wù)員、駕駛員和文書。根據(jù)工作性質(zhì)與計算機(jī)接觸幾率分析，將入學(xué)前工作性質(zhì)分成“計算機(jī)相關(guān)”和“計算機(jī)無關(guān)”，其中“計算機(jī)相關(guān)”包括“通訊員”和“文書”，“計算機(jī)無關(guān)”包括“戰(zhàn)斗員”，“衛(wèi)生員”，“話務(wù)員”和“駕駛員”，完成該字段的泛化離散化。為順利應(yīng)用到關(guān)聯(lián)規(guī)則Apriori算法中，進(jìn)一步將其抽象為邏輯變量“計算機(jī)相關(guān)工作”，其值分別取Y或N。

籍貫屬性因涉及值較多，其數(shù)據(jù)離散化無法用一般方法完成。可結(jié)合分級結(jié)果，借用Apriori算法進(jìn)行數(shù)據(jù)離散化。對于后件為“A”的強關(guān)聯(lián)規(guī)則，其對應(yīng)籍貫屬性值可以約簡為“先”。同理，對于后件為“B”的強關(guān)聯(lián)規(guī)則，其對應(yīng)籍貫屬性值可以約簡為“中”。其他籍貫屬性值均約簡為“后”。

為簡化數(shù)據(jù)調(diào)用過程，將離散化后的能力調(diào)查表與分級結(jié)果進(jìn)行合并，離散化后的各字段屬性域如表2所示，其部分?jǐn)?shù)據(jù)如表3所示。

對于離散化后的事務(wù)數(shù)據(jù)庫進(jìn)行掃描，根據(jù)Apriori算法生成2項頻繁集，設(shè)定其最小支持度為5，篩選后件為分級的頻繁項，分別計算其置信度，設(shè)定其最小置信度為60%，其強關(guān)聯(lián)規(guī)則如表4所示。

為確保強關(guān)聯(lián)規(guī)則對后件屬性的正相關(guān)性，分別計算各強關(guān)聯(lián)規(guī)則提升度，其結(jié)果如表5所示。

其中，計算機(jī)相關(guān)專業(yè)?A、通過計算機(jī)等級考試?A、自我興趣判斷A?A提升度高，可以基本決定分級屬性。其他關(guān)聯(lián)規(guī)則提升度均在1左右，雖然也是正相關(guān)關(guān)系，但還不能直接提取該屬性，需要進(jìn)一步判斷。由此得出，計算機(jī)相關(guān)專業(yè)、通過計算機(jī)等級考試、自我興趣判斷三個屬性與分級結(jié)果密切相關(guān)，可以作為分級用判斷屬性。

表2 離散化后屬性值域

表3 離散化后部分?jǐn)?shù)據(jù)

表4 計算強關(guān)聯(lián)規(guī)則

表5 強關(guān)聯(lián)規(guī)則提升度

當(dāng)對其他屬性計算其基于3項頻繁集的強關(guān)聯(lián)規(guī)則時，為減少掃描事務(wù)數(shù)量，將計算機(jī)相關(guān)專業(yè)=Y、通過計算機(jī)等級考試=Y和自我興趣判斷=A的事務(wù)從事務(wù)數(shù)據(jù)庫中刪除，并刪除計算機(jī)相關(guān)專業(yè)和計算機(jī)等級考試兩個屬性。同時，由于計算機(jī)相關(guān)競賽屬性支持度<5，該屬性也被刪除。

約簡后的部分?jǐn)?shù)據(jù)如表6所示。

表6 約簡后部分?jǐn)?shù)據(jù)

再次掃描事務(wù)數(shù)據(jù)庫，根據(jù)Apriori算法生成3項頻繁集，篩選其后件為分級的頻繁項，分別計算其置信度。設(shè)定其最小置信度為60%，其部分強關(guān)聯(lián)規(guī)則如表7所示。

分別計算各強關(guān)聯(lián)規(guī)則提升度，其結(jié)果如表8所示。

經(jīng)過分析，計算機(jī)相關(guān)且大學(xué)生入伍與分級結(jié)果為A的提升度為4.6，與分級結(jié)果密切相關(guān)，可以作為下一步進(jìn)行分級的判斷屬性。

至此，經(jīng)過分別尋找基于2項頻繁集的強關(guān)聯(lián)規(guī)則和基于3項頻繁集的強關(guān)聯(lián)規(guī)則，共得到與分級結(jié)果密切相關(guān)屬性有4個，分別為：計算機(jī)相關(guān)專業(yè)、通過計算機(jī)等級考試、自我興趣判斷以及計算機(jī)相關(guān)工作且大學(xué)生入伍。

表7 基于3項頻繁集的強關(guān)聯(lián)規(guī)則

五、結(jié)束語

學(xué)員計算機(jī)基礎(chǔ)能力差異對教學(xué)帶來的困難越來越大，《大學(xué)計算機(jī)基礎(chǔ)》實踐課程分級教學(xué)的開展，對教學(xué)效果必將有顯著提高。但如何從繁雜的海量數(shù)據(jù)中快速、高效地尋找到有用信息，是客觀、有效地開展分級教學(xué)的第一步。關(guān)聯(lián)規(guī)則Apriori算法的應(yīng)用，通過對新生計算機(jī)水平調(diào)查表中大量數(shù)據(jù)的分析、計算，從14個已有字段中抽取出與分級結(jié)果密切相關(guān)的4個屬性，為提高分級結(jié)果的效率和準(zhǔn)確性提供了保障。

表8 基于3項頻繁集的強關(guān)聯(lián)規(guī)則提升度

[1] 李志，張晶．公安現(xiàn)役院校計算機(jī)基礎(chǔ)課程分級教學(xué)探析[J]．武警學(xué)院學(xué)報，2013，29(9).

[2] 紀(jì)希禹．?dāng)?shù)據(jù)挖掘技術(shù)應(yīng)用實例[M]．北京：機(jī)械工業(yè)出版社，2009.

[3] 劉平．關(guān)聯(lián)規(guī)則算法在高校教務(wù)管理系統(tǒng)中的應(yīng)用與實現(xiàn)[D]．石家莊：河北科技大學(xué)，2010.

[4] 曹揚波．?dāng)?shù)據(jù)挖掘技術(shù)在壽險市場分析中的應(yīng)用[D]．重慶：重慶大學(xué)，2010.

[5] 楊秋葉．改進(jìn)的Apriori算法在Excel智能考試系統(tǒng)中的應(yīng)用[D]．桂林：廣西師范大學(xué)，2012.

(責(zé)任編輯 李獻(xiàn)惠)

The Improved Apriori Algorithm Based on Gread-teaching

LI Zhi

(DepartmentofBasicCoursesTeaching，TheArmedPoliceAcademy，Langfang，HebeiProvince065000，China)

The bigger difference between a computer basic ability of students produces a strong demand on the grade-teaching inUniversityComputerFoundation’spractical course. How to get rid of the simple way which relys solely on tests in grading for obtaining more objective and efficient classification results. It is the most important to be implemented in grade-teaching. It makes the improvement to the Apriori algorithm based on grade-teaching application， such as reducing the number of scanning and candidate set. The strong association rules which play a decisive role is obtained from new students’ basic computer capability table. The purpose is to improve the classification results of objectivity and efficiency.

UniversityComputerFoundation； grade-teaching； association rules； Apriori

2014-11-13

河北省教育廳項目“公安現(xiàn)役院?！洞髮W(xué)計算機(jī)基礎(chǔ)》分級教學(xué)模式研究”(Z2012114)

李志(1977— )，女，河北衡水人，副教授，碩士。

TP311.13

A

1008-2077(2015)05-0066-05