李 志

(武警學院 基礎部，河北 廊坊 065000)

基于分級教學的Apriori算法改進

李 志

(武警學院 基礎部，河北 廊坊 065000)

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

大學計算機基礎；分級教學；關聯(lián)規(guī)則；Apriori

一、研究背景

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

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

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

二、Apriori算法

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

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

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

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

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

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

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

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

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

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

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

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

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

三、算法的改進

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

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

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

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

(二)以分級教學為應用目的的算法改進

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

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

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

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

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

四、改進算法在分級教學中的應用實現(xiàn)

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

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

表1 新生計算機水平調查表

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

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

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

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

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

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

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

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

表2 離散化后屬性值域

表3 離散化后部分數(shù)據(jù)

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

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

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

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

表6 約簡后部分數(shù)據(jù)

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

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

經過分析，計算機相關且大學生入伍與分級結果為A的提升度為4.6，與分級結果密切相關，可以作為下一步進行分級的判斷屬性。

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

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

五、結束語

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

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

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

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

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

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

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

(責任編輯 李獻惠)

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)役院校《大學計算機基礎》分級教學模式研究”(Z2012114)

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

TP311.13

A

1008-2077(2015)05-0066-05