董 輝

（亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800）

基于興趣度的高職課程關(guān)聯(lián)規(guī)則挖掘＊

董 輝

（亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800）

研究關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘，討論興趣度的概念，設(shè)計基于此概念的算法.以高職成績數(shù)據(jù)庫為處理對象，分析課程間的關(guān)聯(lián)規(guī)則，并以興趣度為約束條件，剔除具有欺騙性的無效關(guān)聯(lián)，挖掘一些合理可靠的課程間有趣的關(guān)聯(lián)規(guī)則，從而為高職課程設(shè)置和教學(xué)大綱的修訂提供參考，同時也驗證了算法的有效性.

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；興趣度；課程設(shè)置

高校各專業(yè)的課程設(shè)置，體現(xiàn)了相應(yīng)專業(yè)人才培養(yǎng)目標(biāo)、要求及人才培養(yǎng)規(guī)格等，因此在確保教學(xué)質(zhì)量的過程中，課程是直接影響人才培養(yǎng)質(zhì)量最關(guān)鍵、最活躍的因素，課程建設(shè)是核心內(nèi)容，是教學(xué)質(zhì)量的標(biāo)志［1］.同一專業(yè)的各課程之間存在相關(guān)聯(lián)性，如各課程的先后、內(nèi)容銜接以及課程的專業(yè)權(quán)重等，因此，構(gòu)建科學(xué)的課程體系和合理的課程設(shè)置是至關(guān)重要的.目前，每個高職院校都有自己的課程設(shè)置方案，但事實上很多高職院校在課程設(shè)置上存在不少問題，如相關(guān)課程的前后關(guān)系不清、專業(yè)課程劃分不合理等，導(dǎo)致課程設(shè)置盲目、課程之間不銜接、課程設(shè)置定位不當(dāng)，從而影響了專業(yè)建設(shè)及人才培養(yǎng)目標(biāo).在高職面臨越來越大的社會及校際間競爭壓力的今天，這必將對學(xué)院的發(fā)展和建設(shè)帶來不利影響.因此，對高職專業(yè)課程進行設(shè)置，必須充分利用現(xiàn)有的信息進行持續(xù)的探索，以構(gòu)建先進的課程體系、完善的課程設(shè)置［2］.筆者基于某學(xué)院現(xiàn)有的成績數(shù)據(jù)庫，在傳統(tǒng)關(guān)聯(lián)數(shù)據(jù)挖掘中引入興趣度概念并以此為約束條件，利用關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘和興趣度閥值挖掘課程間的相關(guān)性，深入分析課程設(shè)置，為學(xué)校的課程總體設(shè)置提供參考.

1 相關(guān)概念

1.1 關(guān)聯(lián)規(guī)則概念

關(guān)聯(lián)規(guī)則模型是由R.A Grawal等人提出的基于頻繁集理論的數(shù)據(jù)挖掘方法.此后人們對這一的數(shù)據(jù)挖掘方式進行了大量研究，提出許多不同的改進算法，使之成為數(shù)據(jù)挖掘研究中一個相當(dāng)活躍的領(lǐng)域［2］.其概念如下：

定義1（關(guān)聯(lián)規(guī)則）［3］設(shè)有項目集I＝｛i1，i2，i3，…，im｝（任意ix≠iy，x，y 為任意不相等的自然數(shù)），D為一個給定的事務(wù)數(shù)據(jù)庫，D中每個具有唯一的標(biāo)識符TID的事務(wù)T都是I中的一組項目的組合（即T?I），則關(guān)聯(lián)規(guī)則可以描述為蘊含式R：X?Y，其中X?I，Y?I，X∩Y＝?，表示X在某一事務(wù)出現(xiàn)，Y也必然會在同一事務(wù)中出現(xiàn).

此規(guī)則成立的條件是：

（2）式表示D中包含X的事務(wù)中有Confidence的也包含Y.

關(guān)聯(lián)規(guī)則挖掘要解決的問題就是在事務(wù)庫D中發(fā)現(xiàn)滿足不小于給定的最小支持度和最小置信度閥值的強關(guān)聯(lián)規(guī)則.

1.2 興趣度概念

1.2.1 興趣度研究的意義 傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法主要考慮支持度和置信度指標(biāo)，但沒有提供好的能夠評價規(guī)則是否有價值的方法，導(dǎo)致有時滿足大于最小支持度和置信度的強關(guān)聯(lián)規(guī)則卻沒有實際意義，甚至有的還具有一定的誘導(dǎo)欺騙性，而且基于這一框架的數(shù)據(jù)挖掘還有另外的缺陷，就是當(dāng)二者閥值設(shè)得過低時，可能會挖掘出一些矛盾的關(guān)聯(lián)規(guī)則，若設(shè)得過高，又可能疏漏掉有價值的規(guī)則.［4］為此，人們定義了“興趣度”度量值，彌補傳統(tǒng)支持度 －置信度模型的缺陷，充分利用用戶的專業(yè)知識和經(jīng)驗來對產(chǎn)生的規(guī)則進行篩選，避免生成 “干擾性”關(guān)聯(lián)規(guī)則影響數(shù)據(jù)挖掘的結(jié)果.

1.2.2 興趣度的定義 關(guān)于興趣度，許多學(xué)者給出不同的定義.文獻［5］提出基于模板概念的興趣度，文獻［6］給出概率相關(guān)性的興趣度模型，文獻［7］敘述了信息量的興趣度函數(shù)，文獻［8］用相關(guān)支持度作為衡量興趣度的方法，文獻［9］給出基于興趣度的正負(fù)關(guān)聯(lián)規(guī)則的修訂.筆者結(jié)合研究的需要，引入基于概率統(tǒng)計和Bernoulli實驗的興趣度的定義模式［10］.

定義2（興趣度） 設(shè)定事務(wù)數(shù)據(jù)庫D，D上關(guān)聯(lián)規(guī)則X?Y的興趣度可表示為

其中：P（Y）表示Y發(fā)生概率；P（X｜Y）為X發(fā)生的條件下Y發(fā)生的概率；Sqrt表示開平方運算；N 為針對事務(wù)進行的Bernoulli實驗的次數(shù)，興趣值越大，說明規(guī)則越有趣，實用價值越高，且對事務(wù)X和Y同時都不發(fā)生是不敏感的.

例如針對表1數(shù)據(jù)，P（X）＝208／534≈0.39，P（Y）＝293／534≈0.549，P（Y｜X）＝168／223＝0.753，帶入（3）式可得規(guī)則（X?Y）的興趣度值：

表1 事務(wù)X與事務(wù)Y的Bernoulli實驗

2 基于興趣度的關(guān)聯(lián)規(guī)則算法

2.1 關(guān)聯(lián)規(guī)則基本算法分析

APRIOR算法和FP＿Growth算法是關(guān)聯(lián)規(guī)則挖掘2大著名的傳統(tǒng)算法，前者是由R.Agrawal和R.Srikant設(shè)計的基于頻繁項集性質(zhì)的一種寬度優(yōu)先先驗知識算法，后者是由Jiawei Han等提出的基于頻繁模式樹的數(shù)據(jù)挖掘算法.文中重點研究FP＿Growth算法，并在此基礎(chǔ)上引入其改進算法.

FP＿growth算法采用分治策略，將頻繁項集的數(shù)據(jù)庫壓縮成一棵FP頻繁模式樹，并仍保留項目集關(guān)聯(lián)信息，隨后將其分成一組條件數(shù)據(jù)庫，每個關(guān)聯(lián)1個頻繁項，而后分別挖掘每一條件數(shù)據(jù)庫.該算法的過程分為2步：第1步構(gòu)造FP樹；第2步是基于FP樹挖掘頻繁項集.

FP ＿growth算法如下［8］：

輸入：事務(wù)數(shù)據(jù)庫D；最小支持?jǐn)?shù)閥值Min＿Sup.

輸出：頻繁模式集.

第1步：構(gòu)造FP樹.

（?。┦状螔呙钄?shù)據(jù)庫D，得到頻繁項集F及支持度計數(shù)值i，按i降序排列項集，生成頻繁項表L；

（ⅱ）創(chuàng)建以“NULL”為根節(jié)點標(biāo)記的FP樹.

針對D中的每個事務(wù)做如下操作：對事務(wù)中的頻繁項按L排序得頻繁列表［g｜G］，g為首元素，G為暫未排入的元素列表.當(dāng)G≠?，遞歸Insert（［g｜G］，T）.

第2步：挖掘FP樹的過程.

算法中Insert（［g｜G］，T）函數(shù)執(zhí)行操作是：若G 有子女項M，且M.itemname＝＝G.itemname，則M 的計數(shù)值加1；否則新建一節(jié)點M，其計數(shù)置初始為1，將M 鏈接到父結(jié)點T下，并通過節(jié)點鏈連接到具有相同itemname的節(jié)點.

2.2 基于興趣度的關(guān)聯(lián)規(guī)則算法分析與設(shè)計

IR＿Growth算法過程與FP＿Growth算法類似，也通過執(zhí)行以下2步完成：第1步構(gòu)造頻繁FP樹，這一步與FP＿Growth算法相同；第2步是利用改進算法對FP樹挖掘頻繁項集.

下面給出第2步算法過程：挖掘FP樹，生成高興趣度頻繁模式.

輸入：事務(wù)數(shù)據(jù)庫D；最小支持?jǐn)?shù)閥值Min＿Sup；最小置信度閥值Min＿Con；最小興趣度閥值Min＿Int.

輸出：高興趣頻繁模式集.

函數(shù)IR＿Rule（ζ）的功能是求出模式ζ所對應(yīng)的高興趣度關(guān)聯(lián)規(guī)則集，其過程如下：

通過上面的分析可知，IR＿Growth算法中在置信度的基礎(chǔ)上引入對關(guān)聯(lián)規(guī)則度量一個的新的閥值——興趣度，根據(jù)這個閾值可以將FP＿Growth算法產(chǎn)生的一些不被感興趣的關(guān)聯(lián)規(guī)則刪除，從而產(chǎn)生真有趣的關(guān)聯(lián)規(guī)則集合，避免一些具有無意義的 “干擾性”關(guān)聯(lián)規(guī)則的產(chǎn)生.

3 IR＿Growth算法在高職課程相關(guān)性中的應(yīng)用

3.1 數(shù)據(jù)準(zhǔn)備與預(yù)處理

以某高職235名軟件技術(shù)專業(yè)學(xué)生主要專業(yè)課成績數(shù)據(jù)庫D為例，部分?jǐn)?shù)據(jù)如表2所示.該成績數(shù)據(jù)庫的能較大程度反映學(xué)生的專業(yè)學(xué)習(xí)情況.如果每個學(xué)生學(xué)號屬性可作為事務(wù)標(biāo)識符TID，那么成績記錄可視為事務(wù)，而該數(shù)據(jù)庫就是一個事務(wù)數(shù)據(jù)庫.由于具體分?jǐn)?shù)表示學(xué)生成績過于細(xì)微，不利于挖掘處理，因此采用以下方法對數(shù)據(jù)進行概化處理：課程名以字母表示；100分制下，75分（含75分）以上者成績評定等級為“優(yōu)”，以“1”表示；成績?yōu)?5分以下以“0”表示.轉(zhuǎn)化后的成績數(shù)據(jù)庫如表3所示.

表2 學(xué)生成績事務(wù)數(shù)據(jù)庫

表3 處理后的學(xué)生成績事務(wù)數(shù)據(jù)庫

3.2 課程相關(guān)性挖掘?qū)崿F(xiàn)過程

現(xiàn)在所要解決的問題是針對上述類型事務(wù)數(shù)據(jù)庫生成支持度、置信度和興趣度都大于等于最小支持度計數(shù)、置信度和興趣度閥值的關(guān)聯(lián)規(guī)則集合，分析某門課程成績?yōu)椤皟?yōu)”時對其他課程成績的影響，以發(fā)現(xiàn)課程間的相關(guān)性，同時驗證IR＿Growth算法的有效性和可用性.

設(shè) Min＿Sup＝10，Min＿con＝60%，Min＿Int＝8，挖掘步驟如下：

（1）生成事務(wù)的FP樹.

首次掃描成績事務(wù)數(shù)據(jù)庫D，生成頻繁項1－項集及相應(yīng)的支持度，并按支持度降序排列成頻繁項表L，L的結(jié)構(gòu)如圖1左邊所示，項的支持?jǐn)?shù)即為表2中該項列值的累加值.調(diào)用Insert（［g｜G］，T）函數(shù)過程，創(chuàng)建以“NULL”為根節(jié)點標(biāo)記的FP樹，其結(jié)構(gòu)如圖1右邊所示.

（2）執(zhí)行IR＿Growth算法過程，挖掘高興趣度的頻繁模式項集.

首先從頻繁項表底部項K9→1的節(jié)點鏈的開始，在FP樹中，K9的分支路徑如表3所示.

圖1 所有成績事務(wù)構(gòu)成的FP樹

表3 含K9的FP樹分支及其支持度計數(shù)

支持度計數(shù)大等于20的只有 ＜K1，K2，K3，K4，K5，K6，K7＞，＜K1，K2，K3，K4，K5，K7＞ 和＜K1，K2，K3，K4，K6，K7＞，此處利用 （2）和（3）式在這2條分支路徑中分別計算K6?K7和K5?K7的置信度和興趣度：

顯然，規(guī)則K6?K7滿足大于Min＿Sup＝10，Min＿con＝60%，Min＿Int＝10的要求，將它們加入到含有K7的強關(guān)聯(lián)規(guī)則集合.

接著分析含有K6的FP樹分支（不再考慮K7），得出K5?K6和K4?K6滿足條件的規(guī)則，并加入到強關(guān)聯(lián)規(guī)則集合.

依次類推，即可挖掘出所有高興趣度關(guān)聯(lián)規(guī)則組成的集合.

3.3 課程關(guān)聯(lián)挖掘結(jié)果分析

用于分析實驗的計算機環(huán)境為Core i3CPU，2GB內(nèi)存硬件平臺，WindowsXP和SQL Server2005軟件平臺，以C＃編程環(huán)境實現(xiàn)算法.將學(xué)生成績事務(wù)數(shù)據(jù)庫挖掘結(jié)果集合中的課程代碼還原課程名稱后，結(jié)果如表4所示.

表4 強關(guān)聯(lián)規(guī)則集合

從表4可以看出，“C程序設(shè)計”應(yīng)在其他專業(yè)課之前開設(shè)，為后續(xù)課程打下基礎(chǔ)；“數(shù)據(jù)結(jié)構(gòu)”的成績優(yōu)秀與否對“數(shù)據(jù)庫及應(yīng)用”和“JAVA程序設(shè)計”成績有很大的影響，因此要加強“數(shù)據(jù)結(jié)構(gòu)”的教學(xué)，這不僅可以提高后續(xù)課程的教學(xué)效果，還應(yīng)在除“C程序設(shè)計”外其他的專業(yè)課程之前開設(shè).綜合對表4的分析，不難得出某學(xué)院軟件技術(shù)主要專業(yè)課合理的開課順序應(yīng)為：C程序設(shè)計→〈數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫及應(yīng)用〉→〈面向?qū)ο蟪绦蛟O(shè)計（JAVA）、網(wǎng)頁制作基礎(chǔ)〉→動態(tài)網(wǎng)頁設(shè)計→軟件工程.這樣的課程設(shè)置順序，既可以保證學(xué)生課程學(xué)習(xí)的連貫性，同時也驗證了IR＿Growth算法有一定的實用性.

［1］劉 寧.對高職院校課程建設(shè)的反思與重構(gòu) ［J］.教育與職業(yè)，2011（11）：122－124.

［2］崔學(xué)文.關(guān)聯(lián)規(guī)則挖掘算法 Apriori在學(xué)生成績分析中的應(yīng)用 ［J］.河北北方學(xué)院學(xué)報：自科版，2011，27（1）：44－47.

［3］朱 明.數(shù)據(jù)挖掘 ［M］.第2版.合肥：中國科學(xué)技術(shù)大學(xué)出版社，2008：156－192.

［4］丁 一，付 弦.基于興趣度的關(guān)聯(lián)規(guī)則挖掘研究 ［J］.情報科學(xué)，2011，29（6）：939－942.

［5］KLEMETTINEN M，MANNILA H，RONKAINEN P P，et al.Finding Interesting Rules from Large Sets of Discovered Association Rules［C］／／Proc.of the Third Int’l Conference on Information and Knowledge Management.New York：ACM，1994：401－407.

［6］TANSEL A U，AYAN N F.Discovery of Association Rules in Temporal Databases［C］／／Proceedings of the International Conference on Information Technology.［S.l.］：Institute of Electrical and Electronics Engineers Computer Society，2007：371－376.

［7］SYMTH P，GOODMAN R M.An Information Theoretic Approach to Rule Induction from Database［J］.IEEE Transaction on Knowledge Data Engineering，1992，4（4）：301－316.

［8］徐 勇，周森鑫.一種改進的關(guān)聯(lián)規(guī)則挖掘方法研究 ［J］.計算機技術(shù)與發(fā)展，2006，16（3）：77－79.

［9］高永惠.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則集的優(yōu)化 ［J］.吉首大學(xué)學(xué)報：自然科學(xué)版，2010，31（2）：38－42.

［10］李永立，吳 沖，王鼠聲.一種新的關(guān)聯(lián)規(guī)則興趣度度量方法 ［J］.情報學(xué)報，2011，30（5）：503－507.

（責(zé)任編輯 向陽潔）

Association Rule Mining Based on the Interestingness About Vocational College Courses

DONG Hui
（Bozhou Vocational and Technical College，Bozhou 236800，Anhui China）

Absract：This paper studies the association rules data mining，the concept of interestingness and algorithm design based on the concept.Taking vocational college’s achievement database for processing object，this paper analyzes the association rules of courses；and with interestingness as constraint conditions，deceptive invalid association rules are eliminated，and some reliable interesting association rules of courses are discovered.This paper provides reference for vocational college curriculum design and syllabus revision，and it also verifies the validity of the algorithm.

data mining；association rules；interestingness；course－setting

TP311

A

10.3969／j.issn.1007－2985.2012.03.011

1007－2985（2012）03－0041－06

2012－04－17

亳州職業(yè)技術(shù)學(xué)院自然科研基金資助項目（BYK1105）

董 輝（1975－），男，安徽亳州人，亳州職業(yè)技術(shù)學(xué)院信息工程系講師，碩士，主要從事數(shù)據(jù)庫、數(shù)據(jù)挖掘研究.