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

1、 基于MATLAB轉(zhuǎn)置矩陣的學(xué)生學(xué)習(xí)成績預(yù)警快速算法 宋紹云陳一民Summary：通過對目前基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行分析，提出一種更加高效的學(xué)生學(xué)科成績的關(guān)聯(lián)規(guī)則挖掘算法，通過實(shí)際案例進(jìn)行對比，證明所提出的算法在學(xué)生成績預(yù)警的關(guān)聯(lián)規(guī)則挖掘中具有明顯的效果。Key：MATLAB；轉(zhuǎn)置矩陣；關(guān)聯(lián)規(guī)則；學(xué)生成績；快速算法：TP391.3 ：A ：1009-3044（2016）02-0200-04Abstract： Through the current mining association rules based on matrix analysis algorithms， associati

2、on 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；

3、fast algorithm1 引言學(xué)生成績預(yù)測是學(xué)校教學(xué)管理的關(guān)鍵因素，隨著招生規(guī)模的擴(kuò)大，高校教學(xué)管理中積累大量學(xué)生的各個學(xué)科的成績數(shù)據(jù)，這些數(shù)據(jù)中隱含了大量的學(xué)生學(xué)習(xí)情況的信息，充分利用數(shù)據(jù)挖掘，發(fā)現(xiàn)成績中隱含在學(xué)科之間成績的知識信息，對學(xué)生各個學(xué)科的未來學(xué)習(xí)成績進(jìn)行預(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é)生成績，并使用比特矩陣運(yùn)算，獲得學(xué)生成績預(yù)警規(guī)則，對高校的素質(zhì)教育和創(chuàng)新人才的培養(yǎng)等方面具有重要的作用和意義。

4、2 目前矩陣算法分析文獻(xiàn)1提出的基于矩陣的關(guān)聯(lián)規(guī)則算法挖掘算法，將Apriori算法的剪枝與矩陣聯(lián)系起來，這種方法只需掃描一次數(shù)據(jù)庫，并且無需候選集Ck，即可得到頻繁集Lk，從而大大提高了算法的效率，在生成關(guān)聯(lián)規(guī)則中，利用了概率論的基本性質(zhì)，也大大減少了計算量。但該算法在生成K-項(xiàng)頻繁集時仍然采用了Apriori算法，降低了執(zhí)行效率。文獻(xiàn)2提出的算法，由m個任務(wù)和n個項(xiàng)目來構(gòu)建mn的布爾矩陣，該算法需要先構(gòu)造一個2維行向量，其中元素均為“1，將該2維行向量與候選2項(xiàng)集中的每個項(xiàng)集所組成的向量進(jìn)行內(nèi)積運(yùn)算得到各項(xiàng)集的支持?jǐn)?shù)，通過與支持度比較從而得到頻繁2項(xiàng)集；在頻繁2項(xiàng)集連接生成候選3項(xiàng)集之前，

5、對頻繁2項(xiàng)集進(jìn)行一次裁剪，利用得出的推論刪除掉不可能成為頻繁3項(xiàng)集的項(xiàng)目元素，這將減少生成候選3項(xiàng)集的規(guī)模。依次類推，在求第k-項(xiàng)集的支持度時候，構(gòu)造k維向量與各個k項(xiàng)候選集組成的向量進(jìn)行內(nèi)積運(yùn)算，同時在連接生成k+I項(xiàng)候選集時，先對k項(xiàng)集進(jìn)行裁剪。該算法需要進(jìn)行大量的內(nèi)積運(yùn)算，且需要通過與支持度比較從而得到頻繁集，消耗了大量的CPU時間和內(nèi)存空間。文獻(xiàn)3 首先掃描數(shù)據(jù)庫生成對應(yīng)的初始矩陣；其次，利用分析得到的頻繁項(xiàng)集的大小對矩陣進(jìn)行修剪；然后，直接生成頻繁k項(xiàng)集，通過矩陣向量相乘后相加得到待生成k項(xiàng)集的支持度。在算法確實(shí)提高了獲得頻繁k項(xiàng)集的效率，但對矩陣進(jìn)行修剪還可以進(jìn)行更高效修剪。文獻(xiàn)4

6、算法引入了兩個矩陣，一個矩陣用于映射數(shù)據(jù)庫，另一個用來存儲2-項(xiàng)頻繁集相關(guān)信息。該算法在剪裁事務(wù)矩陣時，確實(shí)提高了算法的效率。但在求K-項(xiàng)頻繁集時，需要對K個項(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個不同項(xiàng)目的集合，事務(wù)數(shù)據(jù)庫D=T1，T2，Tm，其中Ti=Ii1，Ii2，Iik，并且IijI，關(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的支

7、持度。（3） 關(guān)聯(lián)規(guī)則的支持?jǐn)?shù)與支持度： 數(shù)據(jù)庫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個項(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ù)庫中有m條記錄和n個不同的項(xiàng)，為此構(gòu)建一個由m+1行和n+1列組成的事務(wù)矩陣M?m+1?n+1?，并將矩陣各個元素初始化為0。掃描事

8、務(wù)數(shù)據(jù)庫并計算事務(wù)矩陣M，其中Mij=0，IjTi1，Ij?Ti，i=1，2，m；j=1，2，n。計算后的事務(wù)矩陣M稱為事務(wù)比特矩陣。矩陣的最后一列的Mi（n+1）是第i行的“1”的個數(shù)，表示事務(wù)Tj的長度，即Tj包含的項(xiàng)目數(shù)。矩陣最后一行的M（m+1）j是第j列“1”的個數(shù)，表示項(xiàng)目Ii的支持?jǐn)?shù)。 4 轉(zhuǎn)置矩陣算法4.1 算法設(shè)計設(shè)事務(wù)數(shù)據(jù)庫為：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，方

9、法如上所述。M的最后一行的數(shù)值是所在列項(xiàng)目的支持?jǐn)?shù)，大于minsup所有列所在的項(xiàng)目就組成了1-項(xiàng)頻繁集。最后一列的數(shù)值時事務(wù)的長度，即包含項(xiàng)的數(shù)目。（2）剪裁事務(wù)矩陣M把M最后一行數(shù)值小于minsup所在的列刪除，且刪除最后一列數(shù)值小于k（k=2）的行，重新計算M的最后一行和最后一列的數(shù)值。（3）利用轉(zhuǎn)置矩陣計算2-項(xiàng)頻繁集Lmm=MTmnMnm，該矩陣中上三角中的數(shù)值是組成2-項(xiàng)頻繁集的支持?jǐn)?shù)，主對角線上的數(shù)值是1-項(xiàng)頻繁集的支持?jǐn)?shù)。根據(jù)上三角矩陣中數(shù)值大于minsup所在的行列項(xiàng)目組合可獲得2-項(xiàng)頻繁集。（4）剪裁2-項(xiàng)頻繁集，生成k-項(xiàng)頻繁集（k2）定義1：若k-項(xiàng)集X=i1，i2，i

10、k中存在一個項(xiàng)jX，j表示為Lk中包含j的頻繁項(xiàng)集的個數(shù)，如果j證明：假設(shè)X是?k+1）-項(xiàng)頻繁集，則它的k+1個k-子集均在Lk中。則在生成的k+1個k-子集中，每一個項(xiàng)目jX共出現(xiàn)k次，任給jX均有jk.因此假若出現(xiàn)j根據(jù)以上性質(zhì)對k-項(xiàng)頻繁集進(jìn)行剪裁：首先對Lmm的矩陣進(jìn)行處理，把矩陣的對角線和下三角元素設(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)。.其次，計算矩陣中每列和行的1的個數(shù)，可以用MatLab的函數(shù)A=sum（L，1）+（

11、sum（L，2）T實(shí)現(xiàn)。把A中數(shù)值小于k的所對應(yīng)的列刪除，可以使用Matlab函數(shù)L（：，n）實(shí)現(xiàn)，其中n為要刪除的列號。根據(jù)矩陣L中的1所在行的組合就可以得到k-頻繁集。它們的支持?jǐn)?shù)可以根據(jù)事務(wù)比特矩陣所在的列的內(nèi)積得到。以上算法不需要產(chǎn)生大量的候選集合，挖掘頻繁集的時間效率和空間效率較高，下面給出實(shí)例，并進(jìn)行了分析。數(shù)據(jù)來自多年的本校教務(wù)處的學(xué)科成績數(shù)據(jù)，經(jīng)過處理獲取部分?jǐn)?shù)據(jù)進(jìn)行計算。把成績大于等于60分的在比特矩陣中設(shè)置為1，成績小于60分的設(shè)置為0。各學(xué)科的表示：高數(shù)A，高數(shù)B，計算機(jī)網(wǎng)絡(luò)C，數(shù)據(jù)結(jié)構(gòu)D，C語言E，路由與交換F。如表1所示。把圖4的矩陣進(jìn)行k-1行的內(nèi)積運(yùn)算，把計算結(jié)果

12、等于k-1的行項(xiàng)目和列項(xiàng)目組合就可與得到k項(xiàng)頻繁集。本列的3-項(xiàng)頻繁集為：L3=BEF，CEF，由于沒有k行內(nèi)積后等于k的行，所以運(yùn)算到此為止。5 性能比較和實(shí)驗(yàn)結(jié)果5.1 性能比較所提出的轉(zhuǎn)置矩陣算法只需要掃描數(shù)據(jù)庫一次就可得到1-項(xiàng)頻繁集，通過矩陣轉(zhuǎn)置相乘可以得到2-項(xiàng)頻繁集，而不需要通過候選集的計算，減少了讀取數(shù)據(jù)庫的時間。通過對2-項(xiàng)頻繁集的剪裁和內(nèi)積運(yùn)算可以得到k-項(xiàng)頻繁集。ABM算法是一種高效的關(guān)聯(lián)規(guī)則挖掘算法，與之相比較，ABTM采用矩陣映射事物數(shù)據(jù)庫，而不是建立單個項(xiàng)目的位向量，盡管兩種算法將數(shù)據(jù)庫映射到內(nèi)存中占用的空間相同，但矩陣存儲能夠?qū)崿F(xiàn)對規(guī)模的有效剪裁，隨著項(xiàng)目集維數(shù)的

13、增長，ABTM算法將矩陣中無用的行和列刪除，使得內(nèi)存空間逐步得到釋放，同時參與運(yùn)算的向量的長度越短，計算量也越小。ABTM算法能節(jié)省存儲空降。5.2 實(shí)驗(yàn)結(jié)果與分析算法采用Matlab進(jìn)行仿真實(shí)驗(yàn)， 數(shù)據(jù)采用Mashroom數(shù)據(jù)集，為了比較在不同支持度下的所用時間，實(shí)驗(yàn)機(jī)器的CPU為Inter Pentium3.0GHz，內(nèi)存為2GB。針對Apriori算法、矩陣算法和ABTM算法比較，對不同支持度下的運(yùn)行時間的測試。結(jié)果圖5所示。從圖6可以看出，ABTM算法運(yùn)行所需時間明顯小于Apriori算法和ABM算法。圖5中，隨著所設(shè)定的支持度越來越小，Apriori算法和ABM算法總運(yùn)算量與支持度呈

14、費(fèi)線性增長，所需時間也大大增加，而由于ABTM算法僅需掃描數(shù)據(jù)庫一次，減少了讀取數(shù)據(jù)庫的時間，而且k-項(xiàng)頻繁集的產(chǎn)生式通過擴(kuò)展項(xiàng)集和向量內(nèi)積運(yùn)算求解，不需要連接等操作，隨著支持度減少，算法所需要的時間并未顯著增加。圖2中，隨著屬性數(shù)量的增加，Apriori算法和ABM算法運(yùn)行時間迅速上升，而ABTM得擴(kuò)展項(xiàng)集合向量內(nèi)積運(yùn)算并不會因?yàn)閷傩缘葦?shù)量增加而受到較大的影響。在支持度越小的情況下，轉(zhuǎn)置矩陣法算法的優(yōu)勢越加明顯，與Apriori算法相比較，運(yùn)行時間得到較大程度的減少，在頻繁項(xiàng)集數(shù)量增大的同時，只需要掃描數(shù)據(jù)庫一次，節(jié)省了很多開銷。實(shí)驗(yàn)結(jié)果表明，隨著事物記錄的增加，Apriori算法將花費(fèi)大的

15、開銷來掃描多次數(shù)據(jù)庫，而引入轉(zhuǎn)置矩陣算法只需要掃描數(shù)據(jù)庫一次，通過對比，可以看出轉(zhuǎn)置矩陣算法的優(yōu)勢。6 結(jié)論所提出的算法引入了兩個矩陣，分別從時間和空間上進(jìn)行優(yōu)化，使得算法效率得到顯著的提高，是一種容易且可行的較好算法。算法還可以在以下兩個方面做進(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)支持矩陣時也沒有必要考慮這些項(xiàng)。針對典型的頻繁項(xiàng)集挖掘Apriori算法及相關(guān)矩陣算法進(jìn)行分析，提出了一種新的基于轉(zhuǎn)置矩陣的頻繁集挖掘算法，并對新算法做了詳細(xì)分析和描述。理論和實(shí)驗(yàn)證明，該算法在性能上臂Apriori算法及矩陣算法更優(yōu)越。特別是在學(xué)生成績預(yù)警預(yù)報方面更加出色。Reference：1 宋紹云. 基于SQL Server數(shù)據(jù)挖掘的學(xué)生成績預(yù)警預(yù)報研究. 電腦知識與技術(shù)J. 2015，11（17）.2 曹風(fēng)華. 改進(jìn)的基于兩個矩陣的關(guān)聯(lián)規(guī)則挖掘算法.電子科技J .2012-05-15.3 呂桃霞，劉培玉. 一種基于矩陣的強(qiáng)關(guān)聯(lián)規(guī)則生成算法. 計算機(jī)應(yīng)