基于數據挖掘的教學信息分析技術研究

賀嬌嬌,嚴武軍*,劉守業

(太原師范學院 計算機科學與技術學院,山西 晉中030619)

0 引言

近年來,高校教育與就業市場的職業需求不匹配日趨嚴峻,根據OBE教育理念(成果導向教育),高校開始分析學生的信息以找到適合學生的教育方法,隨著信息技術的不斷發展,教學信息分析技術越來越受到關注,它可以幫助教師更好地了解學生的學習情況和學習習慣,提高教學效率和質量.

由于大規模數據集的產生,加之傳統關聯規則算法Apriori算法的不足,為此提出了控制Apriori算法中前后項集的生成,解決了AR結構約束問題,極大地提高了挖掘興趣和高價值關聯規則的效率,再將優化的Apriori算法(FR-Apriori)和MapReduce結合對教學信息中的數據進行挖掘,可以加速數據處理,提高數據分析的效率.

1 研究現狀

1993年,Agrawal等首次提出了挖掘客戶交易數據庫中項集之間的關聯規則問題;2014年Zheng X,Wang S[1]在Apriori算法的基礎上提出了一種基于剪枝Eclat算法和MapReduce的道路運輸管理信息挖掘方法研究;2019年趙欣燦[2]、朱云、毛伊敏針對Apriori算法效率低下等問題,提出了一種WDU的動態加權增量挖掘算法,構建了CTP方法,解決了項集掃描次數多的問題;2020年Su F,Yuan Q[3]等將Apriori[4]算法用于道路交通事故,挖掘出事故結果的與事故客觀因素的關聯;2021年徐勝超[5]、宋娟、潘歡提出基于MapReduce并行關聯挖掘的網絡入侵檢測的Cloud-Apriori優化算法,證明了新Cloud-Apriori優化算法相比于已存在的網絡入侵算法而言,確實更具優勢;2022年,呂立新和楊帆[6]同樣針對Apriori算法效率低等問題,提出并設計了基于W-DPC策略的改進Apriori算法,為社會各領域信息分析提供了有效參考.

綜上所述,Apriori算法目前已應用于商業、道路等多個領域,并取得了良好的效果.然而,將Apriori和MapReduce結合的優化算法應用于高校教育的研究尚不多見.

2 基本算法及概念介紹

2.1 關聯規則及相關概念

關聯規則簡單來說就是從海量數據中挖掘出項集的關聯關系,最典型的就是啤酒和尿不濕事件,經調查發現67%的用戶購買啤酒的時候同時也會購買尿不濕,故而商超將兩者擺放在一起就可以提高銷售額.大型商城都會有專門的數據分析師,通過分析各種商品之間的關聯關系來了解用戶的心理,并據此設計商城的營銷策略.

關聯規則是一個形如X?Y的表達式,其中X和Y是不相交的項集(譬如{啤酒,尿不濕}被稱為2-項集),關聯規則的支持度是對X和Y的支持度.

Support(X?Y)=P(X∪Y),式中是表示X出現時Y也出現的可能性(即超市同時購買啤酒和尿不濕的顧客占購物總顧客的比例).

關聯規則的置信度是X出現的時候Y也出現的概率.

Confidence(X?Y)=P(Y|X),式中是表示發生X事件的基礎上發生Y事件的概率(即超市購買啤酒和尿不濕的顧客占購買啤酒的顧客的比例).

2.2 Apriori算法

2.2.1 Apriori算法及相關概念

Apriori算法是頻繁模式挖掘的一個簡單而有效的算法,也是最經典的關聯規則算法.該算法中最常用的幾個名詞就是支持度、置信度、頻繁項集、候選項集.支持度和置信度在2.1中已給出.

頻繁項集:假設給定的最小支持度閾值minSupport,如果有support(C)>minSupport,則稱該集合為頻繁項集.

候選項集:假設給定頻繁項集Ck(k∈1,2,…,n),其中Ck[i]和Ck[j]中有k-1個屬性值相同且唯一不同地分布在Ck[i]和Ck[j]中,則通過兩兩連接可得出候選集.

2.2.2 Apriori算法的基本思想

(1)頻繁項集的生成.傳統Apriori算法采用逐層搜索的模式,通過用戶給出的最小支持度求出所有頻繁項集,即所有支持度不小于最小支持度的項集.這些頻繁的項集可能具有包含關系.通常只關心那些不被其他頻繁項集包含的所謂頻繁大項集,而這些頻繁大項集是形成關聯規則的基礎.

(2)生成關聯規則.利用用戶給出的最小置信度,在每個最大頻繁項集中找到置信度不小于最小置信度的關聯規則.關聯規則挖掘的整體性能取決于頻繁項集的生成,生成關聯規則相對容易.

該算法首先輸入事務數據庫、minSupport,k=1;掃描整個數據集,假設候選頻繁0-項集為空集,搜索候選頻繁1-項集及相應的支持度,通過剪枝去除低于支持度的1-項集,得到頻繁的1-項集.然后連接剩余的頻繁1-項集得到候選頻繁2-項集,過濾掉低于支持度的候選頻繁2-項集,得到頻繁2-項集,如此反復.直到找不到頻繁的k+1個項目集,也就是Lk為空對應的頻繁的k個項目集就是算法的輸出結果.Apriori算法流程圖如圖1所示.

圖1 Apriori算法流程圖

2.2.3 優化Apriori算法(FR-Apriori)

隨著數據量的增長,Apriori算法的執行也受到一定的限制.為了提高效率,進行了如下優化:

通過劃分數據塊和控制前后項集(F表示前項集,R表示后項集)生成,解決了AR結構約束問題,極大地提高了挖掘興趣和高價值關聯規則的效率.它確保每個規則以預期的形式呈現給用戶,同時避免無效的關聯規則.

1.FR-Apriori算法基本概念

1)項i是項I的主要組成部分.I由前項If和后項Ir組成.對于教學信息分析,If表示誘發因素,如學生自身學習能力和教師自身能力等分類觸發因素,Ir表示最終狀態事件,如優秀狀態和非優秀狀態.

2)項目I是一個項目集合,定義為:I=If∪Ir={I1,I2,…,In}式中If為前項集,If=If1,If2,…,Ifn.Ir是后項集,其中Ir={Ir1,Ir2,…,Irn}.If與Ir無交集,即If∩Ir=.

3)事務數據庫T由具有唯一事務標識TIDs的事務組成,其中T={t1,t2,…,tn}≠.每個事務t對應于T的一個子集,至少包含一個前項和一個后項.

5)先驗集Xf是If的所有非空真子集的和,其中Xf={X1,X2,…,Xn}.例如,如果If={A1,A2,A3,B1,B2},則其非空固有子集包括{A1,B1},{A2,B1},{A3,B1},{A1,B2},{A2,B2} 和 {A3,B2}.因此,

Xf={{A1,B1},{A2,B1},{A3,B1},{A1,B2},{A2,B2},{A3,B2}}

6)結果集Yr是所有事務中Ir的所有非空真子集Yr={Y1,Y2,…,Yn}的和.例如,對于Ir={C1,C2,C3},非空的固有子集是{C1},{C2}和{C3}.

7)潛在信息集V由Xf和Yr組成,是Xf和Yr的笛卡爾積

8)支持度是指同時包含X和Y的事務數與數據庫中事務總數的比值.定義如下:

式中Count(X∪Y)是同時包含X和Y的事務數.|T|是事務總數.

9)置信度表示假設X發生,Y發生的概率.定義如下:

式中Count(X)是包含X的事務數.

10)強關聯規則(SAR)是滿足用戶指定的評價指標的候選關聯規則,即最小支持閾值(即Min_Supp1和Min_Supp2)和最小置信閾值(Min_Conf).

2.MapReduce基本概念

MapReduce是一個由MRAppMaster、MapTask、ReduceTask構成的分布式程序的通用框架,解決分布式計算中的復雜性.最初是由Google提出,用來解決搜索引擎中大規模網頁數據的并行化處理問題.目前MapReduce主要用來解決海量數據的計算問題.

MR由兩個階段組成:Map(映射)和Reduce(規約),在運行上采用一種“分而治之,先分后合”的思想.目前使用廣泛一方面原因是它的計算簡單,用戶只需要根據業務邏輯編寫Map()和Reduce()兩個函數,其余的系統層面的細節,諸如數據存儲的劃分、分發等均由框架來完成.

MR的工作流程:Map階段、shuffle階段、Reduce階段.

①在Map(映射)階段讀取大規模數據集的內容并將要處理數據進行邏輯切片(split),將split后的數據子塊解析為key、value對.

②并行運行多個Map任務,MapTask(映射任務)由程序員根據相應的業務邏輯編寫,對輸入的鍵值對進行處理并寫入其內存緩沖區.

③寫入內存緩沖區的數據量達到其設置的閾值后會進行spill(溢出)并根據key進行sort(排序),再sort的基礎上進行combiner(聚合),以減少網絡帶寬的開銷,將相同key對應的value提取出來進行分組輸出給shuffle.

④經過shuffle(混洗)階段得到Map階段處理后的數據的中間結果,并將其分發到Reduce節點.

⑤Reduce階段按照key的value列表進行全局的匯總處理,最后,把Reduce的輸出結果保存到HDFS上.如圖2是MapReduce處理數據集的過程圖.

圖2 MapReduce處理數據集的過程圖

圖3 基于MapReduce的FR-Apriori算法流程圖

3.計算過程

基于MapReduce的FR-Apriori算法計算過程:

1)根據最終所要達到的目標,首先將事務數據庫橫向劃分為n個大小近似相等的數據子塊,然后將劃分的數據字塊發送給m個節點.m遠小于n,這里采用隨機分區策略[7].在m個節點上分別推斷其所獲得的關聯規則的前后項.最后,將獲得的所有前項和后項分別存儲在前項集If和后項集Ir中.

2)掃描數據集,統計If和Ir中所有項目的出現次數.用Map集合進行存儲并排序.

3)根據上一節中描述的第一個最小支持閾值Min_Supp1,過濾掉If和Ir中的部分項.然后在上一步的Map集合中,找到有效前項集If和有效后項集Ir并按不同維度和層次存儲符合條件的項目.

4)通過If和Ir中存儲的項目不同維數之間的笛卡爾積的迭代計算,得到潛在的前、后最大頻繁項目,分別存儲在前集Xf和后集Yr中.其中,充分考慮了不同因素之間的排列關系對Xf的笛卡爾積結果的影響.

5)通過T的第二次掃描,計算出Xf和Yr中所有最大頻繁項的出現次數.

6)根據Min_Supp1,對Xf和Yr中的所有最大頻繁項進行過濾.符合條件的項目存儲在有效前項集Xf和有效后項集Yr中.

7)計算Xf與Yr之間的笛卡爾積,將所有組合的項目集放入潛在交易集V中.通過對T的第三次掃描,計算出V中所有非空固有子集的出現次數.

8)根據第二最小支持閾值Min_Supp2和最小置信閾值Min_Conf對V中的非空固有子集進行濾波,直至計算結果均為非頻繁項集,匯總前面所有的頻繁項集.

從上面的過程可以看出,改進后基于MapReduce的FR-Apriori優化算法有三個優點:第一,通過對前后項集的過濾可以有效減少數據集的規模;第二,它只需要讀取數據庫D三次就可以挖掘所有的頻繁項集,這減少了算法在運行中的資源開銷,它可以不受干擾地在每個節點上進行局部頻繁項集的發現.該設計既能滿足并行計算的要求,又能減少節點間數據傳輸帶來的網絡通信開銷;第三:引入MapReduce并行化處理進一步提高了算法的性能.

3 實驗結果與分析

為了驗證所提方法的有效性和性能,總共使用6臺計算機,其中1臺計算機作為master節點,剩余5臺作為slaver節點,處理器均為英特爾酷睿i7處理器,時鐘速率2.10 GHz,內存8.00 GB,使用IntelliJ IDEA 2020.3.2進行編程.實驗數據集來源于信息不對稱情況下太原師范學院2021屆計算機科學與技術學院的學生信息.該方法旨在使管理者了解到OBE理念下學生信息之間的關聯規則,從而制定合適的教學目標.因此,本文只描述和比較了該方法的性能,不重復關聯規則的挖掘結果.

為檢驗經過優化后的算法的有效性和實用性,首先設置一個最小支持度為5%,圖4和圖5分別顯示了改進后的FR-Apriori算法和改進前的Apriori算法在5種不同約束下的規則數,以及FR-Apriori算法和Apriori算法進行實施的持續時間.

圖4 FR-Apriori和Apriori在5種不同約束下獲取的規則數

圖5 FR-Apriori和Apriori在5種不同約束下算法的執行時間

從上圖中可得出,FR-Apriori算法與Apriori算法相比,獲取的規則很少,說明FR-Apriori剪枝程度遠遠大于Apriori算法,在執行時間上也遠遠大于經典Apriori算法,具有較高的挖掘效率,論證了FR-Apriori算法的有效性.

在基于上一個試驗的基礎上,接著驗證基于MapReduce的FR-Apriori算法的性能,即在集群環境下FR-Apriori算法的性能.選取太原師范學院2021屆計算機科學與技術學院的學生信息的20%、40%、60%,設置最小支持度為5%,10%.試驗結果如圖6、圖7所示.說明了算法執行時間隨著計算節點的增多而減少,且同樣的數據在不同的支持度下也呈現不同的趨勢,支持度越大,執行時間也越短,算法的優勢也就越明顯.

圖6 支持度為5%的執行時間對比

圖7 支持度為10%的執行時間對比

4 結論

關聯規則在高校教育的最新應用研究集中在時空數據挖掘上.這些結果應用于數據本身具有明顯的時間序列屬性,而教學信息的無序多為非結構化數據,利用其規律性規則更加困難.由于教學信息受到高校老師和管理者的影響,具有多個相關數據,因此探索新的關聯規則挖掘方法也有用于教學管理信息數據.本文針對Apriori算法的不足,提出并論證了以課程為前綴或后綴的候選集可以對這兩種屬性進行剪枝計算;結合MapReduce函數設計的Map和Reduce函數的特點,提出了一種綜合優化方法.最后,通過試驗結果證明了該算法的性能優勢.