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

董 輝

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

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

董 輝

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

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

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

高校各專業(yè)的課程設(shè)置，體現(xiàn)了相應(yīng)專業(yè)人才培養(yǎng)目標(biāo)、要求及人才培養(yǎng)規(guī)格等，因此在確保教學(xué)質(zhì)量的過(guò)程中，課程是直接影響人才培養(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)重要的.目前，每個(gè)高職院校都有自己的課程設(shè)置方案，但事實(shí)上很多高職院校在課程設(shè)置上存在不少問(wèn)題，如相關(guān)課程的前后關(guān)系不清、專業(yè)課程劃分不合理等，導(dǎo)致課程設(shè)置盲目、課程之間不銜接、課程設(shè)置定位不當(dāng)，從而影響了專業(yè)建設(shè)及人才培養(yǎng)目標(biāo).在高職面臨越來(lái)越大的社會(huì)及校際間競(jìng)爭(zhēng)壓力的今天，這必將對(duì)學(xué)院的發(fā)展和建設(shè)帶來(lái)不利影響.因此，對(duì)高職專業(yè)課程進(jìn)行設(shè)置，必須充分利用現(xiàn)有的信息進(jìn)行持續(xù)的探索，以構(gòu)建先進(jìn)的課程體系、完善的課程設(shè)置［2］.筆者基于某學(xué)院現(xiàn)有的成績(jī)數(shù)據(jù)庫(kù)，在傳統(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ù)挖掘方法.此后人們對(duì)這一的數(shù)據(jù)挖掘方式進(jìn)行了大量研究，提出許多不同的改進(jìn)算法，使之成為數(shù)據(jù)挖掘研究中一個(gè)相當(dāng)活躍的領(lǐng)域［2］.其概念如下：

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

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

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

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

1.2 興趣度概念

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

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

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

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

例如針對(duì)表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實(shí)驗(yàn)

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è)計(jì)的基于頻繁項(xiàng)集性質(zhì)的一種寬度優(yōu)先先驗(yàn)知識(shí)算法，后者是由Jiawei Han等提出的基于頻繁模式樹(shù)的數(shù)據(jù)挖掘算法.文中重點(diǎn)研究FP＿Growth算法，并在此基礎(chǔ)上引入其改進(jìn)算法.

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

FP ＿growth算法如下［8］：

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

輸出：頻繁模式集.

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

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

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

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

第2步：挖掘FP樹(shù)的過(guò)程.

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

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

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

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

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

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

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

通過(guò)上面的分析可知，IR＿Growth算法中在置信度的基礎(chǔ)上引入對(duì)關(guān)聯(lián)規(guī)則度量一個(gè)的新的閥值——興趣度，根據(jù)這個(gè)閾值可以將FP＿Growth算法產(chǎn)生的一些不被感興趣的關(guān)聯(lián)規(guī)則刪除，從而產(chǎn)生真有趣的關(guān)聯(lián)規(guī)則集合，避免一些具有無(wú)意義的 “干擾性”關(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è)課成績(jī)數(shù)據(jù)庫(kù)D為例，部分?jǐn)?shù)據(jù)如表2所示.該成績(jī)數(shù)據(jù)庫(kù)的能較大程度反映學(xué)生的專業(yè)學(xué)習(xí)情況.如果每個(gè)學(xué)生學(xué)號(hào)屬性可作為事務(wù)標(biāo)識(shí)符TID，那么成績(jī)記錄可視為事務(wù)，而該數(shù)據(jù)庫(kù)就是一個(gè)事務(wù)數(shù)據(jù)庫(kù).由于具體分?jǐn)?shù)表示學(xué)生成績(jī)過(guò)于細(xì)微，不利于挖掘處理，因此采用以下方法對(duì)數(shù)據(jù)進(jìn)行概化處理：課程名以字母表示；100分制下，75分（含75分）以上者成績(jī)?cè)u(píng)定等級(jí)為“優(yōu)”，以“1”表示；成績(jī)?yōu)?5分以下以“0”表示.轉(zhuǎn)化后的成績(jī)數(shù)據(jù)庫(kù)如表3所示.

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

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

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

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

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

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

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

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

首先從頻繁項(xiàng)表底部項(xiàng)K9→1的節(jié)點(diǎn)鏈的開(kāi)始，在FP樹(shù)中，K9的分支路徑如表3所示.

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

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

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

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

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

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

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

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

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

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

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

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

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

［4］丁 一，付 弦.基于興趣度的關(guān)聯(lián)規(guī)則挖掘研究 ［J］.情報(bào)科學(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］徐 勇，周森鑫.一種改進(jìn)的關(guān)聯(lián)規(guī)則挖掘方法研究 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（3）：77－79.

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

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

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

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é)院自然科研基金資助項(xiàng)目（BYK1105）

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