基于ＦＰ－ＴＲＥＥ算法的學生主干課程學習和所選模塊的關聯發現

摘要：FP-TREE算法是關聯規則算法的一種，可以用其發現事物之間的潛在關聯關系。用FP-TREE算法發掘出高職院校的學生選擇的學習方向和其主干課程成績之間的關系。

關鍵詞：數據挖掘；FP-TREE算法；關聯規則

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)22-610-02

The Students Learning in Main Course Association to the Selected Module through FP-TREE Algorithm

LIU Bing

(Department of Information， Anhui Industrial Vocational and Technical College， Tongling 244000， China)

Abstract: FP-TREE algorithm is one of association rules algorithm that can find the potential association between things. I explore the relationship between the students choose the direction of the study and its results backbone of courses through FP-TREE algorithm.

Key words: FP-TREE algorithms; data mining; association rules

1 研究背景

當前，職業教育在我國已經成為一個比較熱門的話題，它在社會經濟發展中的重要性與特殊功能。它以培養技術應用性人才為主要目標的高等教育，堅持以服務為宗旨，以就業為導向，走產學研結合之路。這是高職教學的獨特性。我校，安徽工業職業技術學院，信息系積極探索在計算機教學領域的改革，走適合高職教育特點的計算機教學改革，在2002年提出進行模塊化的教學。具體作法是在高職的專科三年中，前1.5年，不進行分專業的教學，主要進行基礎主干課程的教學，在第四學期，根據學生的興趣，重新分班級，進行分模塊的教學，一共分為六個模塊：平面設計，網頁設計，計算機軟件，網絡管理，網絡工程師，企業文員。

在分模塊前的三個學期中，學生主要學習了：數學、英語、網頁設計、程序設計語言、網絡概論、數據庫原理等課程，然后在第四學期根據學生通過前面課程的學習和產生的興趣，自己選擇模塊，轉入模塊的學習。本文試圖通過韓家煒教授在2000年提出的FP-TREE算法，分析他們在前三個學期學習課程成績和選擇模塊之間的關聯關系。

2 數據挖掘技術

數據挖掘（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。

2.1 數據挖掘技術分類

常用的數據挖掘技術可以分為統計分析類、知識發現類和其它類型的數據挖掘技術三大類。

統計分析類技術可以檢查那些異常形式的數據，利用各種統計模型和數學模型解釋這些數據，解釋隱藏這些數據背后的市場規律和商業機會。

知識發現類數據挖掘技術可以從數據倉庫的大量數據中篩選信息，尋找市場可能出現運營模式，發掘人們所不知的事實。知識發現類數據挖掘技術包括人工神經網絡、決策樹、遺傳算法、粗糙集和關聯規則等。

其它類的數據挖掘技術包括文本數據挖掘、Web數據挖掘、分類系統、可視化系統、空間數據挖掘和分布式數據挖掘等。

2.2 數據挖掘的一般過程

數據挖掘和具體的問題應用密切相關，每一種數據挖掘方法在算法和技術要求上都有自己的特點和實現步驟。人們從系統化和方法學的角度，提出了數據挖掘過程的參考模型或標準。

1) 問題的理解和提出；

2) 數據準備和建立數據挖掘數據庫；

3) 數據預處理。由于數據可能是不完全的、有噪聲的、隨機的，有復雜的數據結構，就要對數據進行初步的處理，清洗不完全的數據，做初步的描述分析；

4) 建立模型；

5) 評估模型；

6) 數據挖掘；

7) 評價和解釋。

3 關聯規則算法

關聯規則數據挖掘是數據挖掘中最活躍的研究方法之一，最早由Agrawal等人在1993年提出。最出提出的動機是針對購物籃分析問題提出的，目的是為了發現交易數據庫中不同商品之間的聯系規則。Agrawal等人提出了基于頻繁集的Apriori算法，該算法的主要優點是算法思路比較簡單，以遞歸統計為基礎，剪切生成頻繁集。其主要缺點是，在產生頻繁模式的過程中，需要產生大量的侯選項和多次遍歷數據庫。

韓家煒教授在2000年提出了用頻繁模式樹產生頻繁集的方法，其主要思想是將產生頻繁集的數據壓縮到一棵頻繁模式樹FP-Tree中，用FP-Tree存儲項目的有關信息，然后對模式樹產生頻繁集。FP-Tree算法的主要優點是：1) 不需要產生侯選項，僅需要構建FP-Tree的條件FP-Tree；2) 對事務數據庫只需進行兩次遍歷，第一次遍歷產生頻繁1-項集，第二次遍歷用于創建FP-Tree，從而極大的降低了訪問數據庫的次數。

本文在FP-Tree算法的基礎上，實現學生所學習的主干課程成績和他們選擇模塊之間的關聯規則的發現。

3.1 數據預處理

在學生成績數據庫中，令最小支持度為10%，已知有成績數據信息如表1。

表1

■

在成績中，選取數據結構（以1表示）、程序設計（以2表示）和網頁設計（以3表示）三門主干課程，對成績分為有三個檔次，4：80～100，5：70～80，6：60～70，7：60以下。六個方向模塊為：8：平面設計，9：軟件設計，10：網頁設計，11：網絡工程，12：網絡管理，13：企業文員。設數據庫中事務項目以來編號，其中TID表示相應事務標識符，ITEM則表示項目名稱。

通過對上表數據進行處理，可以得到基于事務數據庫FP-Tree算法可以處理的表2。

表2

■

3.2 Fp-Tree算法的應用

在給定了的成績數據庫中，可以使用FP-Tree算法生成降序的1-頻繁子集和FP-Tree，為使用FP-Growth算法生成有用規則做準備。

我們首先掃描一遍這個數據庫，計算每個項的計數值并保存在頻繁項的集合F中，F={(14:5)，(15:37)，(16:36)，(17:2)，(24:12)，(25:24)，(26:38)，(27:6)，(34:58)，(35:20)，(36:2)，(8:16)，(9:21)，(10:12)，(11:12)，(12:13)，(13:6)}。

我們假定最小支持度為3。選出F中支持度大于3的項，并按支持度遞降排列，將結果放入列表L中，此時，L={(34:58)，(26:38)，(15:37)，(16:36)，(25:24)，(9:21)，(35:20)，(8:16)，(12:13)，(24:12)，(10:12)，(11:12)，(27:6)，(13:6)，(14:5)}。

執行算法的第二步，創建一個標記為“1”的根節點。開始對數據庫的第二遍掃描。對第一個交易的掃描將建立這棵樹的第一個分支：<(15:1)，(35:1)，(8:1)，(24:1)>，在這個交易中的頻繁項已經被按照L中的順序進行排序了。對于第二個交易來說，它已經的頻繁項列表如果同已經存在的路徑有共同的前綴，則把這個前綴中的所有節點的count增加1，剩下的結點被創建作為子結點，如果沒有共同的前綴，則在根結點下創建新的結點。對第三個交易，如果它的頻繁項列表同已經存在的樹有共同的前綴，把這個節點的count增加1，剩下的子樹創建新節點。以此類推，掃描完整個數據庫。建立FP-Tree。

FP-Growth算法建立在FP-Tree的基礎上，遞歸調用自己，反復調用算法產生新的FP_Tree，得到頻繁項集。

3.3 規則總結

(1)34∧26∧168 confidence=5/16=31.25%

(2)34∧26∧169 confidences=4/21=19%

(3)349 confidences=10/58=17.2%

(4)249 confidences=17/21=80.9%

(5)34∧15∧2411 confidences=8/11=72.7%

(6)26∧1510 confidences=10/12=83.3%

根據設置的最小支持度為40%，可以得出弱強關聯規則為：

249 confidences= 17/21=80.9%

34∧15∧2411 confidences=8/11=72.7%

26∧1510 confidences=10/12=83.3%

如上規則可以總結為：

《程序設計》成績為80分以上的人，選擇軟件模塊學習的可信度80.9%；

《網頁設計》、《程序設計》成績在80分以上，《數據結構》成績在70分以上的人，選擇網絡工程模塊的可信度為72.7%；

《程序設計》成績在60～70，《數據結構》成績在70～80，選擇網頁設計模塊的可信度為83.3%。（下轉第614頁）

（上接第611頁）

4 結束語

關聯規則是一種很好的數據挖掘技術，可以應用在許多實際問題中。通過關聯規則的挖掘，我們可以發現很多隱藏的關聯。下一步的工作，就是我們在以后的程序設計中，要把數據挖掘技術應用到其中。

參考資料：

[1] Agrawal R，Imielinski T，Swami A.Mining A ssociation Rules Between Sets of Items in Large Databases[C].In: PeterB， SushilJ，eds. Proceedings of the 1993 ACM SIGMOD International Conference om M anagem ent of Data. Washington:ACM Press，1993：207-216.

[2] Han Jiawei，Pei Jian，Yin Yiwen. Miniing Frequent Patterns Without Candidate Generation[C]. In: Chen Weidong， Jeffrey F M，Philip A B. Proceedings of theACMSIGMOD Internal Conference on Management of Data.Dallas，Texas:ACMPress，2000:1-12.

[3] 蘇超， 左萬利. 基于關聯規則的分類[J]. 吉林大學自然科學學報，2001，(1):31-35.

[4] 秦亮羲，李謙，史忠植. 基于排序FP-樹的頻繁模式高效挖掘算法[J]. 計算機科學，2005，32(4):31-33.