關聯規則Apriori算法在個性化學習系統中的應用研究

繆廣寒

摘 要 關聯算法是實現學習系統的個性化、自主化的有效工具，利用Apriori算法我們可以在學習系統中尋找到學生的學習規律，進而實現個性化的學習推薦，是為個性化學習系統不可取少的功能模塊。

關鍵詞 Apriori算法；個性化學習系統；AprioriTid算法；數據挖掘

中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）05-0047-02

目前，眾多的學習系統大多類似，主要表現在：通用型較多，有專業特色的開發者少；理論類多，實踐類少；大眾類多，個性化少。而對于目前的個性化系統來說，由于缺乏一個可以量化的個性化的標準，所以在具體實現上很難真正的實現個性化學習，即在內容上、模塊上、結構上很難有較為系統、全面、高質量的系統出現。同時，人們的網絡學習已經不再滿足于傳統書本的電子化。交互性、自主性、個性、多元化等各種學習特征急需實現。因此，許多教育學者協同學習系統開發者們都不斷投入到個性化學習系統中的個性化的開發建設中去，希望能在技術層面解決個性化需求與海量學習資源之間的矛盾，實時給網絡學習者個性化的學習指導，實現真正的因材施教。

基于上述問題的解決，本文構建設計了一個課外體育的個性化學習系統，并利用數據挖掘技術中Apriori算法來改進當前的個性化學習系統的學習模式，對每一個網絡學習者提供個性化的學習進程。

1 個性化學習系統及其技術支持

個性化學習是指根據學習者的個性特征實施教育活動，充分發揮學習者的主動性，促進學生全面、自由、協調的發展，從而進一步發展學生的個性和潛能激發。個性化學習是一種創造性、實踐性和探索性的學習方式，它的根本目標是讓每個學生獲得個性發展，實現個性化學習的關鍵主要是看個性化系統能否適應學生的個性化差異，其中包括學生的學習能力的差異、學習興趣的差異、學習適應性差異和學習經驗差異。

為了滿足學習者個性化、自主式學習要求，網絡學習系統平臺也在不斷的發展改進，以各種技術支撐的學習系統應運而生，如自適應學習系統、課程點播系統系統、課程視頻會議等，還有以建設個性化學習環境為主的WEB2.0技術，RSS聚合技術、Ajax技術、Ontology本體檢索技術、數據挖掘技術、數據庫技術等應運而生。可以說從國家到學校，各種相關研究和投入已經多有嘗試，頗具規模。

要實現學習系統個性關鍵在于從信息資源的海洋中得到關于學習者對系統資源使用模式的相關知識，并進一步結合這些知識根據學習者的個人興趣特征實現對學習者的個性化推薦，提供相應資源。目前這些功能的實現主要采用數據挖掘技術來實現。其中，關聯規則就是數據挖掘技術中的一個重要分析模式。

1.1 關聯規則

數據關聯是指數據庫中存在的一類重要的可被發現的知識。如果兩個或多個變量的取值之間存在某種規律性，就可稱之為關聯。數據挖掘中的關聯規則實在滿足一定支持度和置信度算法的同時在事務數據庫數量龐大的關聯規則中找到強規則。Apriori算法是一個典型的關聯規則算法 ，也稱廣度優先算法。是R Agrawal和R Srikant 于1994年提出的。

1.2 Apriori算法

Apriori算法的基本思想是：1）找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣；2）從頻繁項集發現強關聯規則。從一開始找到的頻繁項集的規則中找出只包含集合的項的所有規則。掃描項集，使用遞歸的方法找出所有頻繁項集，為了生成所有頻集，使用了遞歸的方法。具體算法偽代碼如下：

Input：數據庫D；最小支持度MinSuport_count。

Output：數據庫D中的頻繁項集I。

Begin

a、獲得所有支持度不小于 MinSupport的1-項目集

Im=large1-Itemsets；

b、找出數據庫D 中所有的頻繁項集I

FOR（k=2；Ik-1≠Ф；k++）DO

Ck=apriori_gen（Ik-1）；

FOR 所有transactions l ∈D DO

Ct=subset（CK，t）；

FOR 所有候選 c∈Ct DO

c.count++

END

END

Ik={ c ∈Ck|c.count≥MinSuport_count}

END

I=∪Ik

End

其中，apriori_gen（Ik-1）算法按照上一次迭代發現新的候選項集，分為鏈接和修剪兩個部分。具體描述如下：

1.2.1 鏈接

Begin

FOR 所有項目集 p∈Lk-1 DO

FOR 所有項目集 q∈Lk-1 DO

IF p.item1=q.item1，p.item2=q.item2…p.itemk-2=

q.itemk-2， p.itemk-1=q.itemk-1， THEN {

C=p∪q； //鏈接，產生候選集

IF has_infrequent_subset（c，Ik-1） THEN

Delete c； // 修剪。去掉無用候選項

ELSE add c to Ck}

Return Ck

End

1.2.2 修剪

在上述算法中，語句“IF has_infrequent_subset（c，Lk-1） THEN刪除”是判斷c 是否需要加入到 k-候選集中，不需要就修剪掉。endprint

Begin

FOR each （k-1）-subsets of c DO

IF S ? Ik-1 THEN

Return true；

Return False；

END

End

2 使用Apriori 算法獲得學習者的學習規則

關聯規則挖掘算法可以應用在學生的成績分析上，如知識點與測試成績之間函數關系。通過對籃球課程的活動記錄與相應的測試成績的數據分析，我們可以找到一些對今后指導學生課外學習的有用規律。其具體流程如下。

2.1 整理數據

學生的學習記錄庫中記錄了學生的個人信息與基本學習過程信息。如學生姓名、學號、學習風格、學習時間、學習路徑、測試成績等內容。整理數據的目的是為了使學生的數據記錄等符合Apriori算法所需的項目集開展數據挖掘，首先需要將關系表轉換成相應的事務數據庫。

2.2 生成事物數據庫選擇自主學習內容，以代碼代替

2.3 生成頻繁項集

通過以上的對應抽象，我們可知事務集，假設最小支持度為25%，使用Apriori算法尋找D的所有頻繁項集。

2.4 關聯規則生成

在Apriori算法中，對于每一個頻繁k-項集都要找出其中所有可能的真子集，計算出相應規則的置信度。當我們發現某一規則的置信度大于設定的最小置信度就導出該規則。其中，每驗證一個項子集都要重新掃描一遍Ik-1。在對某學生的籃球學習記錄中分析，最小置信度閾值設置為75%則可以發現強規則I01∧I08→I03。此規則告訴我們發現如果某生的運球技能與防守戰術同時成績優秀，則發現的該生在實踐活動中的投籃技能成績也一般為優秀。通過該例，我們可以發現數據關聯算法可以發現學生學習中的一些隱藏的學習規律，而這些規律正好可供學習系統給學習者提供下一步個性化學習方案。

3 多項目集的Apriori算法改進

我們發現，由于Apriori算法對數據庫的掃描次數過多，所以在有限的內存容量下存放大量的事務數據時，系統I/O負載會變大，每次掃描數據庫的時間就會越長。此外，如果學習系統中某一課程的知識節點太多而導致分析的頻繁項集個數太多會產生大量的侯選項集。這會導致運算時間顯著增加。所以根據不同的課程，我們可以改進Apriori算法，采用減低候選項目數量的方法，我們稱之為AprioriTid。此算法無需此次掃描數據庫，當第一次掃描數據庫之后，第二次只需要掃描前一次產生的項目集而不再需要完全的掃描數據庫，這樣就可以有效的減少了I/O負載和數據運算時間。

具體改進為在事務集TID中。當k=1時，C1掃描數據庫D，C1=數據庫D，但當k>1時，有算法產生Ck，Ck=apriori-gen（Lk-1）。

此外，我們還可以在AprioriTid的基礎上通過把項目集中一些無關的屬性先去掉以及通過把兩個元素結合在一起組成一個新屬性的辦法來減少工作量，又或者在產生頻繁k-項集以后去掉一些非頻繁項集來簡化掃描時間。以上兩種方法的結合使用類似于矩陣中逐漸去掉行與列。

4 現存的問題與思考

利用Apriori算法與AprioriTid算法，我們可以有效的挖掘出個性化學習中學習者的學習關聯，掌握學生的學習動態，進而更深入了了解學生的學習規律與特點。但是在分布式計算與學習增量的情況下，我們不得不需要進一步地改進算法，以適合當前及未來的個性化學習系統發展的趨勢。

參考文獻

[1]劉美玲.基于數據挖掘技術的個性化學習系統研究[D].揚州：揚州大學，2009.

[2]盛立，高明，劉希玉.一種高效的關聯規則的算法研究[J].濱州學院學報，2005（12）.

[3]盛立，劉希玉，高明.數據關聯規則中AprioriTid[J].山東師范大學學報（自然科學版），2005（10）.

[4]李曼.Web日志挖掘技術在心靈家園網中的應用研究[D].河南：河南大學，2013.

[5]何月順.關聯規則挖掘技術的研究及應用[D].江蘇：南京航空航天大學，2010.

[6]王志強.基于遠程教育網站的信息采集與數據挖掘技術研究[D].上海：華東師范大學，2007.endprint

Begin

FOR each （k-1）-subsets of c DO

IF S ? Ik-1 THEN

Return true；

Return False；

END

End

2 使用Apriori 算法獲得學習者的學習規則

關聯規則挖掘算法可以應用在學生的成績分析上，如知識點與測試成績之間函數關系。通過對籃球課程的活動記錄與相應的測試成績的數據分析，我們可以找到一些對今后指導學生課外學習的有用規律。其具體流程如下。

2.1 整理數據

學生的學習記錄庫中記錄了學生的個人信息與基本學習過程信息。如學生姓名、學號、學習風格、學習時間、學習路徑、測試成績等內容。整理數據的目的是為了使學生的數據記錄等符合Apriori算法所需的項目集開展數據挖掘，首先需要將關系表轉換成相應的事務數據庫。

2.2 生成事物數據庫選擇自主學習內容，以代碼代替

2.3 生成頻繁項集

通過以上的對應抽象，我們可知事務集，假設最小支持度為25%，使用Apriori算法尋找D的所有頻繁項集。

2.4 關聯規則生成

在Apriori算法中，對于每一個頻繁k-項集都要找出其中所有可能的真子集，計算出相應規則的置信度。當我們發現某一規則的置信度大于設定的最小置信度就導出該規則。其中，每驗證一個項子集都要重新掃描一遍Ik-1。在對某學生的籃球學習記錄中分析，最小置信度閾值設置為75%則可以發現強規則I01∧I08→I03。此規則告訴我們發現如果某生的運球技能與防守戰術同時成績優秀，則發現的該生在實踐活動中的投籃技能成績也一般為優秀。通過該例，我們可以發現數據關聯算法可以發現學生學習中的一些隱藏的學習規律，而這些規律正好可供學習系統給學習者提供下一步個性化學習方案。

3 多項目集的Apriori算法改進

我們發現，由于Apriori算法對數據庫的掃描次數過多，所以在有限的內存容量下存放大量的事務數據時，系統I/O負載會變大，每次掃描數據庫的時間就會越長。此外，如果學習系統中某一課程的知識節點太多而導致分析的頻繁項集個數太多會產生大量的侯選項集。這會導致運算時間顯著增加。所以根據不同的課程，我們可以改進Apriori算法，采用減低候選項目數量的方法，我們稱之為AprioriTid。此算法無需此次掃描數據庫，當第一次掃描數據庫之后，第二次只需要掃描前一次產生的項目集而不再需要完全的掃描數據庫，這樣就可以有效的減少了I/O負載和數據運算時間。

具體改進為在事務集TID中。當k=1時，C1掃描數據庫D，C1=數據庫D，但當k>1時，有算法產生Ck，Ck=apriori-gen（Lk-1）。

此外，我們還可以在AprioriTid的基礎上通過把項目集中一些無關的屬性先去掉以及通過把兩個元素結合在一起組成一個新屬性的辦法來減少工作量，又或者在產生頻繁k-項集以后去掉一些非頻繁項集來簡化掃描時間。以上兩種方法的結合使用類似于矩陣中逐漸去掉行與列。

4 現存的問題與思考

利用Apriori算法與AprioriTid算法，我們可以有效的挖掘出個性化學習中學習者的學習關聯，掌握學生的學習動態，進而更深入了了解學生的學習規律與特點。但是在分布式計算與學習增量的情況下，我們不得不需要進一步地改進算法，以適合當前及未來的個性化學習系統發展的趨勢。

參考文獻

[1]劉美玲.基于數據挖掘技術的個性化學習系統研究[D].揚州：揚州大學，2009.

[2]盛立，高明，劉希玉.一種高效的關聯規則的算法研究[J].濱州學院學報，2005（12）.

[3]盛立，劉希玉，高明.數據關聯規則中AprioriTid[J].山東師范大學學報（自然科學版），2005（10）.

[4]李曼.Web日志挖掘技術在心靈家園網中的應用研究[D].河南：河南大學，2013.

[5]何月順.關聯規則挖掘技術的研究及應用[D].江蘇：南京航空航天大學，2010.

[6]王志強.基于遠程教育網站的信息采集與數據挖掘技術研究[D].上海：華東師范大學，2007.endprint

Begin

FOR each （k-1）-subsets of c DO

IF S ? Ik-1 THEN

Return true；

Return False；

END

End

2 使用Apriori 算法獲得學習者的學習規則

關聯規則挖掘算法可以應用在學生的成績分析上，如知識點與測試成績之間函數關系。通過對籃球課程的活動記錄與相應的測試成績的數據分析，我們可以找到一些對今后指導學生課外學習的有用規律。其具體流程如下。

2.1 整理數據

學生的學習記錄庫中記錄了學生的個人信息與基本學習過程信息。如學生姓名、學號、學習風格、學習時間、學習路徑、測試成績等內容。整理數據的目的是為了使學生的數據記錄等符合Apriori算法所需的項目集開展數據挖掘，首先需要將關系表轉換成相應的事務數據庫。

2.2 生成事物數據庫選擇自主學習內容，以代碼代替

2.3 生成頻繁項集

通過以上的對應抽象，我們可知事務集，假設最小支持度為25%，使用Apriori算法尋找D的所有頻繁項集。

2.4 關聯規則生成

在Apriori算法中，對于每一個頻繁k-項集都要找出其中所有可能的真子集，計算出相應規則的置信度。當我們發現某一規則的置信度大于設定的最小置信度就導出該規則。其中，每驗證一個項子集都要重新掃描一遍Ik-1。在對某學生的籃球學習記錄中分析，最小置信度閾值設置為75%則可以發現強規則I01∧I08→I03。此規則告訴我們發現如果某生的運球技能與防守戰術同時成績優秀，則發現的該生在實踐活動中的投籃技能成績也一般為優秀。通過該例，我們可以發現數據關聯算法可以發現學生學習中的一些隱藏的學習規律，而這些規律正好可供學習系統給學習者提供下一步個性化學習方案。

3 多項目集的Apriori算法改進

我們發現，由于Apriori算法對數據庫的掃描次數過多，所以在有限的內存容量下存放大量的事務數據時，系統I/O負載會變大，每次掃描數據庫的時間就會越長。此外，如果學習系統中某一課程的知識節點太多而導致分析的頻繁項集個數太多會產生大量的侯選項集。這會導致運算時間顯著增加。所以根據不同的課程，我們可以改進Apriori算法，采用減低候選項目數量的方法，我們稱之為AprioriTid。此算法無需此次掃描數據庫，當第一次掃描數據庫之后，第二次只需要掃描前一次產生的項目集而不再需要完全的掃描數據庫，這樣就可以有效的減少了I/O負載和數據運算時間。

具體改進為在事務集TID中。當k=1時，C1掃描數據庫D，C1=數據庫D，但當k>1時，有算法產生Ck，Ck=apriori-gen（Lk-1）。

此外，我們還可以在AprioriTid的基礎上通過把項目集中一些無關的屬性先去掉以及通過把兩個元素結合在一起組成一個新屬性的辦法來減少工作量，又或者在產生頻繁k-項集以后去掉一些非頻繁項集來簡化掃描時間。以上兩種方法的結合使用類似于矩陣中逐漸去掉行與列。

4 現存的問題與思考

利用Apriori算法與AprioriTid算法，我們可以有效的挖掘出個性化學習中學習者的學習關聯，掌握學生的學習動態，進而更深入了了解學生的學習規律與特點。但是在分布式計算與學習增量的情況下，我們不得不需要進一步地改進算法，以適合當前及未來的個性化學習系統發展的趨勢。

參考文獻

[1]劉美玲.基于數據挖掘技術的個性化學習系統研究[D].揚州：揚州大學，2009.

[2]盛立，高明，劉希玉.一種高效的關聯規則的算法研究[J].濱州學院學報，2005（12）.

[3]盛立，劉希玉，高明.數據關聯規則中AprioriTid[J].山東師范大學學報（自然科學版），2005（10）.

[4]李曼.Web日志挖掘技術在心靈家園網中的應用研究[D].河南：河南大學，2013.

[5]何月順.關聯規則挖掘技術的研究及應用[D].江蘇：南京航空航天大學，2010.

[6]王志強.基于遠程教育網站的信息采集與數據挖掘技術研究[D].上海：華東師范大學，2007.endprint