基于MATLAB轉(zhuǎn)置矩陣的學(xué)生學(xué)習(xí)成績預(yù)警快速算法

宋紹云　陳一民

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

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

中圖分類號：TP391.3 文獻標識碼：A 文章編號：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é)生成績預(yù)測是學(xué)校教學(xué)管理的關(guān)鍵因素，隨著招生規(guī)模的擴大，高校教學(xué)管理中積累大量學(xué)生的各個學(xué)科的成績數(shù)據(jù)，這些數(shù)據(jù)中隱含了大量的學(xué)生學(xué)習(xí)情況的信息，充分利用數(shù)據(jù)挖掘，發(fā)現(xiàn)成績中隱含在學(xué)科之間成績的知識信息，對學(xué)生各個學(xué)科的未來學(xué)習(xí)成績進行預(yù)測預(yù)報，將是高等學(xué)校教學(xué)管理的重要研究和應(yīng)用。

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

2 目前矩陣算法分析

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

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

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

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

3 基本概念

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

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

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

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

（4）項集合：包含k個項的項集稱為k-項集。

（5） k-項頻繁集：滿足最小支持的k-項集。

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

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

3.2 比特矩陣

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

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

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

4.1 算法設(shè)計

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

算法步驟如下：

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

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

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

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

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

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

（4）剪裁2-項頻繁集，生成k-項頻繁集（k>2）

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

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

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

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

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

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

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

5 性能比較和實驗結(jié)果

5.1 性能比較

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

5.2 實驗結(jié)果與分析

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

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

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

6 結(jié)論

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

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

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

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

參考文獻：

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

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

[3] 呂桃霞，劉培玉. 一種基于矩陣的強關(guān)聯(lián)規(guī)則生成算法. 計算機應(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.