基于FP-Growth算法的高校學(xué)生公共課成績與專業(yè)課成績相關(guān)性研究

余弦，周誼芬

（南通大學(xué)a.杏林學(xué)院，b.醫(yī)學(xué)院，江蘇 南通 226000）

高校人才培養(yǎng)方案中所計(jì)劃開設(shè)的課程，一般可分為公共課（包含公共選修課和公共必修課）和專業(yè)課（包含專業(yè)基礎(chǔ)課和專業(yè)課）兩種[1]。一般而言，公共課和專業(yè)課之間有一定的相關(guān)性，公共課所學(xué)習(xí)的內(nèi)容在一定程度上是專業(yè)課內(nèi)容的基礎(chǔ)，熟悉公共課知識(shí)對掌握專業(yè)課內(nèi)容具有促進(jìn)作用[2]，但是否每一門公共課的成績都會(huì)對相關(guān)專業(yè)課的成績產(chǎn)生影響，以及會(huì)產(chǎn)生多大的影響，仍有待研究和驗(yàn)證。

隨著信息技術(shù)的快速發(fā)展，數(shù)據(jù)挖掘及相關(guān)技術(shù)在高校的教學(xué)、科研等領(lǐng)域得到不斷拓展應(yīng)用。數(shù)據(jù)挖掘技術(shù)在尋找海量數(shù)據(jù)的內(nèi)在關(guān)聯(lián)規(guī)則方面具有效率高、適用靈活等優(yōu)點(diǎn)。在教學(xué)過程中累積的學(xué)生成績已經(jīng)形成一個(gè)體量龐大的數(shù)據(jù)庫，通過數(shù)據(jù)挖掘的相關(guān)算法來尋找大量學(xué)生成績數(shù)據(jù)之間潛在的關(guān)聯(lián)規(guī)律，進(jìn)而提高高校課程設(shè)置合理性和學(xué)生學(xué)習(xí)效率，已經(jīng)成為高等教育管理領(lǐng)域的研究熱點(diǎn)之一[3]。應(yīng)用FPGrowth算法對某高校部分計(jì)算機(jī)專業(yè)學(xué)生的公共課成績和專業(yè)課成績進(jìn)行相關(guān)性分析，針對二者的關(guān)聯(lián)程度展開實(shí)證研究，為高校教學(xué)計(jì)劃的課程設(shè)置和教學(xué)改革提供有力的科學(xué)依據(jù)。

1 FP-Growth算法原理和實(shí)現(xiàn)

FP-Growth(Frequent Pattern Tree,頻繁模式樹)算法是一種在經(jīng)典Apriori算法基礎(chǔ)上演變而來的挖掘頻繁項(xiàng)集方法[4]。它針對Apriori算法運(yùn)行效率較低，實(shí)現(xiàn)過程中需要多次掃描整個(gè)事務(wù)集，進(jìn)而產(chǎn)生大量候選集的缺點(diǎn)做了明顯的改進(jìn)。FP-Growth算法比Apriori算法效率更高，它將數(shù)據(jù)集存儲(chǔ)于一個(gè)按特定順序構(gòu)成的樹結(jié)構(gòu)（FP樹），通過構(gòu)建FP樹來壓縮事務(wù)數(shù)據(jù)庫中的信息，從而更加有效地產(chǎn)生頻繁項(xiàng)集[5]。在整個(gè)算法執(zhí)行過程中，只需遍歷事務(wù)集兩次，通過遞歸調(diào)用FP樹結(jié)構(gòu)，刪除不符合最小支持度（關(guān)聯(lián)度低）的項(xiàng)目，直至最終形成單一的樹結(jié)構(gòu)，就能夠完成頻繁模式的發(fā)現(xiàn)。其發(fā)現(xiàn)頻繁項(xiàng)集的基本過程如下。

將事務(wù)數(shù)據(jù)庫中的單個(gè)事務(wù)記為Tk，而T={T1,T2,...,Tk}是所有事務(wù)的集合。事務(wù)中所包含的各個(gè)項(xiàng)目記為Ik，所有項(xiàng)目的集合I={I1,I2,...,Ik}。FP-Growth算法首先掃描一遍事務(wù)集T，計(jì)算事務(wù)集T中各項(xiàng)目Ik出現(xiàn)的次數(shù)n，并設(shè)定最小支持度s（項(xiàng)目出現(xiàn)的最少次數(shù)），若項(xiàng)目集I中某個(gè)項(xiàng)目Ik的出現(xiàn)次數(shù)n小于最小支持度s，則刪除該項(xiàng)目，然后將原始事務(wù)集T中的各項(xiàng)事務(wù)Tk按項(xiàng)目集Ik中的項(xiàng)目頻次進(jìn)行降序排列。之后第二次掃描事務(wù)集T，創(chuàng)建項(xiàng)頭表以及FP樹。項(xiàng)頭表的第一列是按照降序排列的頻繁項(xiàng)，第二列是指向該頻繁項(xiàng)在FP樹中節(jié)點(diǎn)位置的指針[6]。FP樹其實(shí)是一棵用來存儲(chǔ)項(xiàng)目出現(xiàn)次數(shù)的前綴樹，每個(gè)項(xiàng)目均以路徑的方式存儲(chǔ)在樹結(jié)構(gòu)中，與其它樹形結(jié)構(gòu)不同，各項(xiàng)目在FP樹中并非只出現(xiàn)一次。只有當(dāng)項(xiàng)目和頻次均不一致時(shí)，樹結(jié)構(gòu)才會(huì)分枝。項(xiàng)目每出現(xiàn)一次，若在FP樹中有同路徑的節(jié)點(diǎn)，則記數(shù)增加一次，若無同路徑的節(jié)點(diǎn)，則相應(yīng)的新增該項(xiàng)目節(jié)點(diǎn)。最終各項(xiàng)目按支持度降序排列，支持度越高的頻繁項(xiàng)離根節(jié)點(diǎn)越近[7]，從而使得更多的頻繁項(xiàng)可以共享前綴。

FP樹構(gòu)建完成之后，依照樹結(jié)構(gòu)中從下往上的順序，對于每個(gè)項(xiàng)目找到其條件模式基（CPB，conditional patten base），遞歸調(diào)用樹結(jié)構(gòu)，刪除小于最小支持度的項(xiàng)。如果最終呈現(xiàn)單一路徑的樹結(jié)構(gòu)，則直接列舉所有組合；非單一路徑的則繼續(xù)調(diào)用樹結(jié)構(gòu)，直到形成單一路徑，即可挖掘出項(xiàng)目的頻繁項(xiàng)集。

2 FP-Growth算法在分析學(xué)生公共課成績與專業(yè)課成績相關(guān)性中的應(yīng)用

2.1 學(xué)生成績預(yù)處理及離散化

根據(jù)FP-Growth算法原理及其實(shí)現(xiàn)步驟，本文以某高校計(jì)算機(jī)專業(yè)2018級(jí)學(xué)生的成績?yōu)閿?shù)據(jù)來源，研究學(xué)生公共課成績和專業(yè)課成績之間的相關(guān)性。根據(jù)該專業(yè)教學(xué)計(jì)劃的具體內(nèi)容及培養(yǎng)重點(diǎn)，選擇高等數(shù)學(xué)A(一)、大學(xué)英語(一)、計(jì)算機(jī)導(dǎo)論三門課程成績作為公共課成績代表，另外選擇高級(jí)語言程序設(shè)計(jì)(C++)(一)、數(shù)據(jù)庫原理及應(yīng)用、數(shù)據(jù)結(jié)構(gòu)三門課程成績作為專業(yè)課成績代表，在不考慮學(xué)生補(bǔ)考或重修等異?？荚嚨那闆r下，共得到有效學(xué)生成績數(shù)據(jù)418條，作為全部的數(shù)據(jù)來源。限于本文篇幅，隨機(jī)選取其中的15名學(xué)生數(shù)據(jù)作為研究實(shí)例，其公共課和專業(yè)課原始成績?nèi)绫?所示。為保護(hù)學(xué)生個(gè)人信息，以學(xué)號(hào)后六位代表對應(yīng)學(xué)生。

表1 學(xué)生公共課和專業(yè)課原始成績

學(xué)生的成績數(shù)據(jù)部分為百分制，部分為五級(jí)計(jì)分制，為方便FP-Growth算法處理，將學(xué)生成績數(shù)據(jù)做進(jìn)一步的離散化處理。若某門課程成績?yōu)槲寮?jí)計(jì)分制的優(yōu)秀或良好，或者其成績?yōu)榘俜种魄曳謹(jǐn)?shù)大于等于80，則認(rèn)為其成績優(yōu)良，將其標(biāo)注為Ik，反之則不標(biāo)注。依此規(guī)則，將高等數(shù)學(xué)A(一)、大學(xué)英語(一)、計(jì)算機(jī)導(dǎo)論三門公共課成績?yōu)閮?yōu)良分別記作I1、I2、I3，高級(jí)語言程序設(shè)計(jì)(C++)(一)、數(shù)據(jù)庫原理及應(yīng)用、數(shù)據(jù)結(jié)構(gòu)三門專業(yè)課成績?yōu)閮?yōu)良分別記作I4、I5、I6。本文主要討論公共課成績優(yōu)良與專業(yè)課成績優(yōu)良之間的關(guān)系，故非優(yōu)良的成績忽略不計(jì)。原始成績離散規(guī)則如表2所示。離散化后的學(xué)生公共課成績和專業(yè)課成績?nèi)绫?所示。

表2 原始成績離散規(guī)則

表3 離散化后的學(xué)生公共課成績和專業(yè)課成績

2.2 學(xué)生公共課成績與專業(yè)課成績相關(guān)性分析

根據(jù)FP-Growth算法思想，通過以下步驟來完成學(xué)生公共課成績與專業(yè)課成績相關(guān)性分析。

1)將表3中離散化后的學(xué)生公共課成績和專業(yè)課成績作為事務(wù)集T，各項(xiàng)事務(wù)中所包含的項(xiàng)目的集合I={I1，I2，I3，I4，I5，I6}。首先完整地掃描一遍事務(wù)集T，計(jì)算所有學(xué)生成績數(shù)據(jù)中各成績項(xiàng)目Ik出現(xiàn)的次數(shù)n，得到的結(jié)果如表4所示。

表4 各成績項(xiàng)目Ik出現(xiàn)的次數(shù)

2)設(shè)定最小支持度s=5。項(xiàng)目集I中成績項(xiàng)目I2的出現(xiàn)次數(shù)n為4，小于最小支持度s，故刪除此項(xiàng)目。按出現(xiàn)頻次將項(xiàng)目集I重新排序?yàn)閧I1，I6，I5，I4，I3}，依照此項(xiàng)目順序?qū)⒊煽兪聞?wù)集T中的各項(xiàng)事務(wù)Tk進(jìn)行降序排列。刪除不符合最小支持度項(xiàng)目并進(jìn)行降序排列前后的事務(wù)集T如表5所示。

表5 刪除不符合最小支持度項(xiàng)目并進(jìn)行降序排列前后的事務(wù)集

3)掃描表5中經(jīng)過刪除不符合最小支持度項(xiàng)目并進(jìn)行降序排列之后的事務(wù)集T，創(chuàng)建項(xiàng)頭表以及FP樹。FP樹的根節(jié)點(diǎn)記為null，不表示任何項(xiàng)。先根據(jù)第一條事務(wù)T1={I1,I6,I5}創(chuàng)建FP樹的第一條分支，之后將事務(wù)T2到T13中的項(xiàng)目逐條插入FP樹中。若新加入的項(xiàng)目路徑若與現(xiàn)有FP樹節(jié)點(diǎn)相同，則原有節(jié)點(diǎn)數(shù)量增加一次；若新加入的項(xiàng)目路徑與FP樹節(jié)點(diǎn)不同，則FP樹分枝，增加新的項(xiàng)目節(jié)點(diǎn)。以此構(gòu)建的項(xiàng)頭表和FP樹如圖1所示。

圖1 項(xiàng)頭表和FP樹

4)FP樹構(gòu)建完成之后，查找每個(gè)項(xiàng)目對應(yīng)的條件模式基。以項(xiàng)目I5和I6為例，I5的條件模式基為{I1}、{I1:7，I6:7}，I6的條件模式基為{I1:9}。將I5和I6的條件模式基作為新的事務(wù)數(shù)據(jù)庫，以條件模式基的項(xiàng)目為節(jié)點(diǎn)，構(gòu)建I5和I6的條件FP樹如圖2所示。

由圖2可知，I5和I6的條件FP樹均為單路徑，且每一節(jié)點(diǎn)均滿足最小支持度，所以直接列舉條件FP樹中的所有節(jié)點(diǎn)組合，與對應(yīng)項(xiàng)目取并集，即可得對應(yīng)項(xiàng)目的頻繁項(xiàng)集。I5的條件FP樹節(jié)點(diǎn)組合為{I1:8}、{I6:7}、{I1:8，I6:7}，與I5取并集得到滿足最小支持度的頻繁項(xiàng)集為{（I1:8，I5:8），（I6:7，I5:7），（I1:7，I6:7，I5:7）}；同理，I6的條件FP樹節(jié)點(diǎn)組合為{I1:9}，與I6取并集得到滿足最小支持度的頻繁項(xiàng)集為{（I1:9，I6:9）}。

圖2 I5和I6的條件FP樹

據(jù)此分析，I1和I5以及I1和I6之間存在較強(qiáng)的關(guān)聯(lián)性。由此可以得出，如果學(xué)生的公共課高等數(shù)學(xué)A(一)的成績?yōu)閮?yōu)良，則其數(shù)據(jù)庫原理及應(yīng)用、數(shù)據(jù)結(jié)構(gòu)兩門專業(yè)課成績?yōu)閮?yōu)良的概率較大。而大學(xué)英語(一)和計(jì)算機(jī)導(dǎo)論兩門公共課成績未發(fā)現(xiàn)與數(shù)據(jù)庫原理及應(yīng)用、數(shù)據(jù)結(jié)構(gòu)兩門專業(yè)課成績存在明顯的關(guān)聯(lián)性。

3 結(jié)語

本文指出了高校學(xué)生公共課成績與專業(yè)課成績之間關(guān)聯(lián)的不確定性，通過分析數(shù)據(jù)挖掘的FP-Growth算法，以某高校計(jì)算機(jī)專業(yè)學(xué)生為例，選擇高等數(shù)學(xué)A(一)、大學(xué)英語(一)、計(jì)算機(jī)導(dǎo)論三門公共課成績和高級(jí)語言程序設(shè)計(jì)(C++)(一)、數(shù)據(jù)庫原理及應(yīng)用、數(shù)據(jù)結(jié)構(gòu)三門專業(yè)課成績?yōu)閿?shù)據(jù)挖掘?qū)ο?，將六門課程成績概化之后引入FP-Growth算法進(jìn)行分析處理，通過構(gòu)建FP樹等步驟，高效挖掘?qū)W生公共課成績與專業(yè)課成績之間的潛在關(guān)系，得出了兩者之間的關(guān)聯(lián)規(guī)則。這些關(guān)聯(lián)規(guī)則可以為高校教學(xué)單位課程設(shè)置提供有力的理論依據(jù)，進(jìn)而制定更加科學(xué)合理的培養(yǎng)計(jì)劃，促進(jìn)高校教學(xué)模式及人才培養(yǎng)過程的改革。學(xué)生也能以此為參考，結(jié)合自身成績特點(diǎn)，靈活調(diào)整學(xué)習(xí)重點(diǎn)，更有針對性地吸收知識(shí)，有效提高學(xué)習(xí)效率。