宋紹云　陳一民

摘要：通過(guò)對(duì)目前基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行分析，提出一種更加高效的學(xué)生學(xué)科成績(jī)的關(guān)聯(lián)規(guī)則挖掘算法，通過(guò)實(shí)際案例進(jìn)行對(duì)比，證明所提出的算法在學(xué)生成績(jī)預(yù)警的關(guān)聯(lián)規(guī)則挖掘中具有明顯的效果。

關(guān)鍵詞：MATLAB；轉(zhuǎn)置矩陣；關(guān)聯(lián)規(guī)則；學(xué)生成績(jī)；快速算法

中圖分類號(hào)：TP391.3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）02-0200-04

Abstract： Through the current mining association rules based on matrix analysis algorithms， association rules proposed a more efficient algorithm for mining student academic performance， comparing actual cases， proves that the proposed algorithm has obvious warning in association rule mining in student achievement Effect.

Key words： MATLAB； transposed matrix； association rules； student achievement； fast algorithm

1 引言

學(xué)生成績(jī)預(yù)測(cè)是學(xué)校教學(xué)管理的關(guān)鍵因素，隨著招生規(guī)模的擴(kuò)大，高校教學(xué)管理中積累大量學(xué)生的各個(gè)學(xué)科的成績(jī)數(shù)據(jù)，這些數(shù)據(jù)中隱含了大量的學(xué)生學(xué)習(xí)情況的信息，充分利用數(shù)據(jù)挖掘，發(fā)現(xiàn)成績(jī)中隱含在學(xué)科之間成績(jī)的知識(shí)信息，對(duì)學(xué)生各個(gè)學(xué)科的未來(lái)學(xué)習(xí)成績(jī)進(jìn)行預(yù)測(cè)預(yù)報(bào)，將是高等學(xué)校教學(xué)管理的重要研究和應(yīng)用。

提出一種基于MATLAB的學(xué)生成績(jī)預(yù)警關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵算法，使用該算法所挖掘的學(xué)生預(yù)警規(guī)則集，生成預(yù)警信息，在用戶設(shè)定的支持度下，通過(guò)在MATLAB下導(dǎo)入Excel學(xué)生成績(jī)，并使用比特矩陣運(yùn)算，獲得學(xué)生成績(jī)預(yù)警規(guī)則，對(duì)高校的素質(zhì)教育和創(chuàng)新人才的培養(yǎng)等方面具有重要的作用和意義。

2 目前矩陣算法分析

文獻(xiàn)[1]提出的基于矩陣的關(guān)聯(lián)規(guī)則算法挖掘算法，將Apriori算法的剪枝與矩陣聯(lián)系起來(lái)，這種方法只需掃描一次數(shù)據(jù)庫(kù)，并且無(wú)需候選集Ck，即可得到頻繁集Lk，從而大大提高了算法的效率，在生成關(guān)聯(lián)規(guī)則中，利用了概率論的基本性質(zhì)，也大大減少了計(jì)算量。但該算法在生成K-項(xiàng)頻繁集時(shí)仍然采用了Apriori算法，降低了執(zhí)行效率。

文獻(xiàn)[2]提出的算法，由m個(gè)任務(wù)和n個(gè)項(xiàng)目來(lái)構(gòu)建m×n的布爾矩陣，該算法需要先構(gòu)造一個(gè)2維行向量，其中元素均為“1"，將該2維行向量與候選2項(xiàng)集中的每個(gè)項(xiàng)集所組成的向量進(jìn)行內(nèi)積運(yùn)算得到各項(xiàng)集的支持?jǐn)?shù)，通過(guò)與支持度比較從而得到頻繁2項(xiàng)集；在頻繁2項(xiàng)集連接生成候選3項(xiàng)集之前，對(duì)頻繁2項(xiàng)集進(jìn)行一次裁剪，利用得出的推論刪除掉不可能成為頻繁3項(xiàng)集的項(xiàng)目元素，這將減少生成候選3項(xiàng)集的規(guī)模。依次類推，在求第k-項(xiàng)集的支持度時(shí)候，構(gòu)造k維向量與各個(gè)k項(xiàng)候選集組成的向量進(jìn)行內(nèi)積運(yùn)算，同時(shí)在連接生成k+I項(xiàng)候選集時(shí)，先對(duì)k項(xiàng)集進(jìn)行裁剪。該算法需要進(jìn)行大量的內(nèi)積運(yùn)算，且需要通過(guò)與支持度比較從而得到頻繁集，消耗了大量的CPU時(shí)間和內(nèi)存空間。

文獻(xiàn)[3] 首先掃描數(shù)據(jù)庫(kù)生成對(duì)應(yīng)的初始矩陣；其次，利用分析得到的頻繁項(xiàng)集的大小對(duì)矩陣進(jìn)行修剪；然后，直接生成頻繁k項(xiàng)集，通過(guò)矩陣向量相乘后相加得到待生成k項(xiàng)集的支持度。在算法確實(shí)提高了獲得頻繁k項(xiàng)集的效率，但對(duì)矩陣進(jìn)行修剪還可以進(jìn)行更高效修剪。

文獻(xiàn)[4]算法引入了兩個(gè)矩陣，一個(gè)矩陣用于映射數(shù)據(jù)庫(kù)，另一個(gè)用來(lái)存儲(chǔ)2-項(xiàng)頻繁集相關(guān)信息。該算法在剪裁事務(wù)矩陣時(shí)，確實(shí)提高了算法的效率。但在求K-項(xiàng)頻繁集時(shí)，需要對(duì)K個(gè)項(xiàng)目的映射矩陣中的列向量做內(nèi)積運(yùn)算，降低了算法的效率。

3 基本概念

3.1 關(guān)聯(lián)規(guī)則

（1） 關(guān)聯(lián)規(guī)則：設(shè)[I={I1，I2，…，In}]是n個(gè)不同項(xiàng)目的集合，事務(wù)數(shù)據(jù)庫(kù)[D={T1，T2，…，Tm}]，其中[Ti={Ii1，Ii2，…，Iik}]，并且[Iij∈I]，關(guān)聯(lián)規(guī)則是形如[X?Y]的蘊(yùn)含式，其中[X，Y?I]，且[X?Y=Φ]。

（2） 項(xiàng)目集的支持度：[D]中支持項(xiàng)目集[X]的事務(wù)數(shù)稱為[X]的支持?jǐn)?shù)，記為[Count（X）]。設(shè)[D]中的總事務(wù)數(shù)位[D]，則[Sup（X）=Count（X）/D]稱為項(xiàng)目集[X]的支持度。

（3） 關(guān)聯(lián)規(guī)則的支持?jǐn)?shù)與支持度： 數(shù)據(jù)庫(kù)[D]中支持項(xiàng)目集[X?Y]的事務(wù)數(shù)稱為關(guān)聯(lián)規(guī)則[X?Y]的支持?jǐn)?shù)，記為[Count（X?Y）]，[Count（X?Y）/D]，稱為規(guī)則的支持度，記為[Sup（X?Y）]

（4）項(xiàng)集合：包含k個(gè)項(xiàng)的項(xiàng)集稱為k-項(xiàng)集。

（5） k-項(xiàng)頻繁集：滿足最小支持的k-項(xiàng)集。

（6） 強(qiáng)關(guān)聯(lián)規(guī)則：同事滿足最小支持度閥值和最小置信度閥值的規(guī)則。

關(guān)聯(lián)規(guī)則的挖掘就是要發(fā)現(xiàn)滿足用戶給定最小支持度和最小置信度的所有條件的蘊(yùn)含式，即強(qiáng)關(guān)聯(lián)規(guī)則。

3.2 比特矩陣

設(shè)事務(wù)數(shù)據(jù)庫(kù)中有m條記錄和n個(gè)不同的項(xiàng)，為此構(gòu)建一個(gè)由m+1行和n+1列組成的事務(wù)矩陣[M?m+1?×?n+1?]，并將矩陣各個(gè)元素初始化為0。

掃描事務(wù)數(shù)據(jù)庫(kù)并計(jì)算事務(wù)矩陣[M]，其中[Mij=0，Ij∈Ti1，Ij?Ti，i=1，2，…，m；j=1，2，…，n]。計(jì)算后的事務(wù)矩陣[M]稱為事務(wù)比特矩陣。矩陣的最后一列的[Mi（n+1）]是第[i]行的“1”的個(gè)數(shù)，表示事務(wù)[Tj]的長(zhǎng)度，即[Tj]包含的項(xiàng)目數(shù)。矩陣最后一行的[M（m+1）j]是第[j]列“1”的個(gè)數(shù)，表示項(xiàng)目[Ii]的支持?jǐn)?shù)。

4 轉(zhuǎn)置矩陣算法

4.1 算法設(shè)計(jì)

設(shè)事務(wù)數(shù)據(jù)庫(kù)為：[D={T1，T2，…，Tn}]， 項(xiàng)目集為：[I={I1，I2，…，Im}]，最小支持度為minsup，最小置信度為minconf。

算法步驟如下：

（1）構(gòu)建事務(wù)比特矩陣，并獲得1-項(xiàng)頻繁集

根據(jù)[D={T1，T2，…，Tn}]和[I={I1，I2，…，Im}]創(chuàng)建n+1行m+1列事務(wù)比特矩陣[M]，方法如上所述。[M]的最后一行的數(shù)值是所在列項(xiàng)目的支持?jǐn)?shù)，大于minsup所有列所在的項(xiàng)目就組成了1-項(xiàng)頻繁集。最后一列的數(shù)值時(shí)事務(wù)的長(zhǎng)度，即包含項(xiàng)的數(shù)目。

（2）剪裁事務(wù)矩陣[M]

把[M]最后一行數(shù)值小于minsup所在的列刪除，且刪除最后一列數(shù)值小于k（k>=2）的行，重新計(jì)算[M]的最后一行和最后一列的數(shù)值。

（3）利用轉(zhuǎn)置矩陣計(jì)算2-項(xiàng)頻繁集

[Lm×m=MTm×n×Mn×m]，該矩陣中上三角中的數(shù)值是組成2-項(xiàng)頻繁集的支持?jǐn)?shù)，主對(duì)角線上的數(shù)值是1-項(xiàng)頻繁集的支持?jǐn)?shù)。根據(jù)上三角矩陣中數(shù)值大于minsup所在的行列項(xiàng)目組合可獲得2-項(xiàng)頻繁集。

（4）剪裁2-項(xiàng)頻繁集，生成k-項(xiàng)頻繁集（k>2）

定義1：若[k]-項(xiàng)集[X={i1，i2，…，ik}]中存在一個(gè)項(xiàng)[j∈X]，[j]表示為[Lk]中包含[j]的頻繁項(xiàng)集的個(gè)數(shù)，如果[j

證明：假設(shè)[X]是[?k+1）]-項(xiàng)頻繁集，則它的[k+1]個(gè)[k]-子集均在[Lk]中。則在生成的[k+1]個(gè)[k]-子集中，每一個(gè)項(xiàng)目[j∈X]共出現(xiàn)[k]次，任給[j∈X]均有[j>k].因此假若出現(xiàn)[j

根據(jù)以上性質(zhì)對(duì)k-項(xiàng)頻繁集進(jìn)行剪裁：首先對(duì)[Lm×m]的矩陣進(jìn)行處理，把矩陣的對(duì)角線和下三角元素設(shè)置為0，可以用MatLab的函數(shù)triu（triu（L）-tril（L））實(shí)現(xiàn)，把上三角矩陣中若數(shù)值大于minsup的元素設(shè)置為1，否則設(shè)置為0，可以用MatLab的函數(shù)L（L=minsup）=1實(shí)現(xiàn)。.其次，計(jì)算矩陣中每列和行的1的個(gè)數(shù)，可以用MatLab的函數(shù)A=sum（L，1）+（sum（L，2））T實(shí)現(xiàn)。

把A中數(shù)值小于k的所對(duì)應(yīng)的列刪除，可以使用Matlab函數(shù)L（：，n）實(shí)現(xiàn)，其中n為要?jiǎng)h除的列號(hào)。根據(jù)矩陣L中的1所在行的組合就可以得到k-頻繁集。它們的支持?jǐn)?shù)可以根據(jù)事務(wù)比特矩陣所在的列的內(nèi)積得到。

以上算法不需要產(chǎn)生大量的候選集合，挖掘頻繁集的時(shí)間效率和空間效率較高，下面給出實(shí)例，并進(jìn)行了分析。數(shù)據(jù)來(lái)自多年的本校教務(wù)處的學(xué)科成績(jī)數(shù)據(jù)，經(jīng)過(guò)處理獲取部分?jǐn)?shù)據(jù)進(jìn)行計(jì)算。把成績(jī)大于等于60分的在比特矩陣中設(shè)置為1，成績(jī)小于60分的設(shè)置為0。各學(xué)科的表示：高數(shù)Ⅰ—A，高數(shù)Ⅱ—B，計(jì)算機(jī)網(wǎng)絡(luò)—C，數(shù)據(jù)結(jié)構(gòu)—D，C語(yǔ)言—E，路由與交換—F。如表1所示。

把圖4的矩陣進(jìn)行k-1行的內(nèi)積運(yùn)算，把計(jì)算結(jié)果等于k-1的行項(xiàng)目和列項(xiàng)目組合就可與得到k項(xiàng)頻繁集。

本列的3-項(xiàng)頻繁集為：[L3={BEF，CEF}]，由于沒(méi)有k行內(nèi)積后等于k的行，所以運(yùn)算到此為止。

5 性能比較和實(shí)驗(yàn)結(jié)果

5.1 性能比較

所提出的轉(zhuǎn)置矩陣算法只需要掃描數(shù)據(jù)庫(kù)一次就可得到1-項(xiàng)頻繁集，通過(guò)矩陣轉(zhuǎn)置相乘可以得到2-項(xiàng)頻繁集，而不需要通過(guò)候選集的計(jì)算，減少了讀取數(shù)據(jù)庫(kù)的時(shí)間。通過(guò)對(duì)2-項(xiàng)頻繁集的剪裁和內(nèi)積運(yùn)算可以得到k-項(xiàng)頻繁集。ABM算法是一種高效的關(guān)聯(lián)規(guī)則挖掘算法，與之相比較，ABTM采用矩陣映射事物數(shù)據(jù)庫(kù)，而不是建立單個(gè)項(xiàng)目的位向量，盡管兩種算法將數(shù)據(jù)庫(kù)映射到內(nèi)存中占用的空間相同，但矩陣存儲(chǔ)能夠?qū)崿F(xiàn)對(duì)規(guī)模的有效剪裁，隨著項(xiàng)目集維數(shù)的增長(zhǎng)，ABTM算法將矩陣中無(wú)用的行和列刪除，使得內(nèi)存空間逐步得到釋放，同時(shí)參與運(yùn)算的向量的長(zhǎng)度越短，計(jì)算量也越小。ABTM算法能節(jié)省存儲(chǔ)空降。

5.2 實(shí)驗(yàn)結(jié)果與分析

算法采用Matlab進(jìn)行仿真實(shí)驗(yàn)， 數(shù)據(jù)采用Mashroom數(shù)據(jù)集，為了比較在不同支持度下的所用時(shí)間，實(shí)驗(yàn)機(jī)器的CPU為Inter Pentium3.0GHz，內(nèi)存為2GB。針對(duì)Apriori算法、矩陣算法和ABTM算法比較，對(duì)不同支持度下的運(yùn)行時(shí)間的測(cè)試。結(jié)果圖5所示。

從圖6可以看出，ABTM算法運(yùn)行所需時(shí)間明顯小于Apriori算法和ABM算法。圖5中，隨著所設(shè)定的支持度越來(lái)越小，Apriori算法和ABM算法總運(yùn)算量與支持度呈費(fèi)線性增長(zhǎng)，所需時(shí)間也大大增加，而由于ABTM算法僅需掃描數(shù)據(jù)庫(kù)一次，減少了讀取數(shù)據(jù)庫(kù)的時(shí)間，而且k-項(xiàng)頻繁集的產(chǎn)生式通過(guò)擴(kuò)展項(xiàng)集和向量?jī)?nèi)積運(yùn)算求解，不需要連接等操作，隨著支持度減少，算法所需要的時(shí)間并未顯著增加。圖2中，隨著屬性數(shù)量的增加，Apriori算法和ABM算法運(yùn)行時(shí)間迅速上升，而ABTM得擴(kuò)展項(xiàng)集合向量?jī)?nèi)積運(yùn)算并不會(huì)因?yàn)閷傩缘葦?shù)量增加而受到較大的影響。

在支持度越小的情況下，轉(zhuǎn)置矩陣法算法的優(yōu)勢(shì)越加明顯，與Apriori算法相比較，運(yùn)行時(shí)間得到較大程度的減少，在頻繁項(xiàng)集數(shù)量增大的同時(shí)，只需要掃描數(shù)據(jù)庫(kù)一次，節(jié)省了很多開(kāi)銷。實(shí)驗(yàn)結(jié)果表明，隨著事物記錄的增加，Apriori算法將花費(fèi)大的開(kāi)銷來(lái)掃描多次數(shù)據(jù)庫(kù)，而引入轉(zhuǎn)置矩陣算法只需要掃描數(shù)據(jù)庫(kù)一次，通過(guò)對(duì)比，可以看出轉(zhuǎn)置矩陣算法的優(yōu)勢(shì)。

6 結(jié)論

所提出的算法引入了兩個(gè)矩陣，分別從時(shí)間和空間上進(jìn)行優(yōu)化，使得算法效率得到顯著的提高，是一種容易且可行的較好算法。算法還可以在以下兩個(gè)方面做進(jìn)一步的優(yōu)化：

（1）由于在構(gòu)造事物矩陣后直接獲得了1-項(xiàng)頻繁集，所以可以在構(gòu)造2-項(xiàng)支持矩陣前進(jìn)行一次映射矩陣的剪裁。

（2）由于可能存在一些項(xiàng)并非是1-項(xiàng)頻繁集，則這些項(xiàng)不可能再出現(xiàn)在更高階的頻繁項(xiàng)集中。因此在構(gòu)造2-項(xiàng)支持矩陣時(shí)也沒(méi)有必要考慮這些項(xiàng)。

針對(duì)典型的頻繁項(xiàng)集挖掘Apriori算法及相關(guān)矩陣算法進(jìn)行分析，提出了一種新的基于轉(zhuǎn)置矩陣的頻繁集挖掘算法，并對(duì)新算法做了詳細(xì)分析和描述。理論和實(shí)驗(yàn)證明，該算法在性能上臂Apriori算法及矩陣算法更優(yōu)越。特別是在學(xué)生成績(jī)預(yù)警預(yù)報(bào)方面更加出色。

參考文獻(xiàn)：

[1] 宋紹云. 基于SQL Server數(shù)據(jù)挖掘的學(xué)生成績(jī)預(yù)警預(yù)報(bào)研究. 電腦知識(shí)與技術(shù)[J]. 2015，11（17）.

[2] 曹風(fēng)華. 改進(jìn)的基于兩個(gè)矩陣的關(guān)聯(lián)規(guī)則挖掘算法.電子科技[J] .2012-05-15.

[3] 呂桃霞，劉培玉. 一種基于矩陣的強(qiáng)關(guān)聯(lián)規(guī)則生成算法. 計(jì)算機(jī)應(yīng)用研究[J]. 2011-4-20.

[4] Park J S， Chen M S， Yu P S. An effective hash-based algorithm for mining association rules [C]. Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data， San Jose， California： ACM Press， 1995： 175-186.