《數(shù)據(jù)挖掘及其應用講義》應用關聯(lián)規(guī)則課件

,單擊此處編輯母版標題樣式,*,單擊此處編輯母版文本樣式,第二級,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,*,關聯(lián)規(guī)則應用,1,關聯(lián)規(guī)則,設,I=I,1,I,2,I,m,是一組數(shù)據(jù)項集合,D,是與任務相關的數(shù)據(jù)集合，也稱為交易數(shù)據(jù)庫。其中每個,交易,T,是一個數(shù)據(jù)項子集，,TI,。關聯(lián)規(guī)則是如下形式的一種蘊含,:,A B,表示,If conditions then result,其中,AI,BI,且,AB=,。一般用,支持度、可信度、期望可信度、作用度,4,個參數(shù)來描述一個關聯(lián)規(guī)則的屬性。,可信度,:,在屬性集,A,出現(xiàn)的前提下,B,出現(xiàn)的,概率,P(B|A),支持度,:,屬性集,A,B,同時出現(xiàn)的概率,P(AB),期望可信度,:,屬性集,B,出現(xiàn)的概率,P(B),作用度,:,可信度對期望可信度的比值,P(B|A)/P(B),可信度,是對關聯(lián)規(guī)則準確度的衡量,支持度,是對關聯(lián)規(guī)則重要性的衡量。顯然,支持度越大,關聯(lián)規(guī)則越重要。有些關聯(lián)規(guī)則可信度雖然很高,但支持度卻很低,說明該關聯(lián)規(guī)則實用的機會很小,因此也不重要。,作用度,描述屬性集,A,的出現(xiàn)對屬性集,B,的出現(xiàn)有多大影響。作用度越大,說明屬性集,B,受屬性集,A,的影響越大。一般情況,有用的關聯(lián)規(guī)則的作用度都應大于,1,只有關聯(lián)規(guī)則的可信度大于期望可信度,才說明,A,的出現(xiàn)對,B,的出現(xiàn)有促進作用,也說明了它們之間某種程度的相關性,如果作用度不大于,1,則此關聯(lián)規(guī)則就沒有意義。,2,關聯(lián)規(guī)則算法（,Apriori,算法）,2.1,概念介紹,項集,：一個數(shù)據(jù)項的集合；,K,項集,：一個包含,k,個數(shù)據(jù)項的項集；,項集頻度,：整個交易數(shù)據(jù)庫,D,中，包含該項集的交易記錄數(shù),也稱為該項集的支持度。,頻繁項集,：滿足最小支持度的項集。,若一個項集的出現(xiàn)頻度大于最小支持度閾值乘以交易記錄集,D,中的記錄數(shù)，就稱該項集滿足最小支持度閾值；滿足最小支持度閾值所對應的交易記錄數(shù)稱為最小支持頻度。,返回,2.2 Apriori算法,Apriori,算法是一個基于兩階段頻繁項集的數(shù)據(jù)挖掘方法,將關聯(lián)規(guī)則挖掘算法分為兩部分,:,一是找到所有支持度大于最小支持度的項集,稱為頻繁項集,二是使用第一步找到的頻繁項集產(chǎn)生期望規(guī)則,.,Apriori,算法的性質(zhì)：如果一個項集是頻繁的，則它的所有子集也是頻繁的。,首先，給定最小支持度及最小可信度。,返回,第一步,:,找頻繁項集,由數(shù)據(jù)庫讀入所有的交易，得出候選單項集的支持度，再找出頻繁單項集，并利用這些頻繁單項集的結(jié)合，產(chǎn)生候選,2,項集，若候選,2,項集的支持度大于或等于最小支持度，則該候選項集為頻繁項集，即為頻繁,2,項集，并利用頻繁,2,項集的結(jié)合，產(chǎn)生候選,3,項集，若候選,3,項集的支持度大于或等于最小支持度，則該候選項集為頻繁,3,項集，并利用高頻,3,項集的結(jié)合，產(chǎn)生候選,4,項，,，最后產(chǎn)生頻繁多項集，再結(jié)合產(chǎn)生下一級候選項集，,直到新產(chǎn)生的候選項集的支持度小于給定的最小支持度,，則不再結(jié)合產(chǎn)生新的候選項集，算法結(jié)束。,第二步,:,由頻繁項集產(chǎn)生期望規(guī)則,(1),對于每個,頻繁項集,L,產(chǎn)生,L,的所有非空子集,;,(2),對于,L,的每個,非空子集,S,如果其可信度大,于最小可信度,則輸出規(guī)則,”,s,L-s,”,(,一,)Apriori,算法在學生成績分析中的應用研究,學生的各科考試成績一直以來作為國內(nèi)各高等院校評價學生學業(yè)以及綜合素質(zhì)的重要指標，各高校經(jīng)過長期的積累都儲存了大量的學生成績信息，但對成績的分析處理一般還停留在簡單的查詢和統(tǒng)計階段，例如統(tǒng)計優(yōu)、良、及格、不及格等級別的人數(shù)以及計算平均成績、標準差等指標，而對于學生取得這些,成績與課程之間的關系,有無關聯(lián)往往沒有深入了解。如果能夠合理開發(fā)利用這些數(shù)據(jù)，找到,課程之間的相關關系對學生成績的影響，,必將對課程的設置與安排具有重大的指導意義。,1 研究對象,以沈陽農(nóng)業(yè)大學,01,屆計算機專業(yè)學生在校四年的學習成績作為數(shù)據(jù)源，選取成績數(shù)據(jù)庫中,計算機網(wǎng)絡,、,外語,、,工科高數(shù),、,計算機基礎,、,操作系統(tǒng),等,8,門課程作為研究對象，挖掘出某門課程對于其他課程的影響程度，為教務人員以后安排課程提供參考，為學生選課提供指導。,2,數(shù)據(jù)預處理,2.1,數(shù)據(jù)清理,原始數(shù)據(jù)庫中包含全校各個專業(yè)、各個年級、各門課程的所有成績,某些記錄難免會有一些差錯或者從經(jīng)驗上看沒有關聯(lián),為了便于進行數(shù)據(jù)挖掘，只選取,01,屆計算機專業(yè)學生的,計算機網(wǎng)絡,等,8,門課程成績作為挖掘?qū)ο?，去掉所有其他不必要的字段，刪除空白以及數(shù)據(jù)有缺失的記錄。清理后的數(shù)據(jù)表部分數(shù)據(jù)如圖,1,所示。,圖,1,原始數(shù)據(jù)表,2.2 數(shù)據(jù)轉(zhuǎn)換,學生成績是以數(shù)值形式表示的，不便于進行數(shù)據(jù)挖掘，因此對各科成績進行離散化處理，即轉(zhuǎn)換為優(yōu)、良、中、及格、不及格,5,個等級。大于,90,分的為,“,優(yōu),”,，,80,90,分之間的為,“,良,”,，,70,80,分之間的為,“,中,”,，,60,70,分之間的為,“,及格,”,，小于,60,分的為,“,不及格,”,。,“,優(yōu)、良、中、及格、不及格,”,5,個等級分別用數(shù)字,“,1,、,2,、,3,、,4,、,5,”,表示，,用,“,A,”,表示計算機網(wǎng)絡，,“,B,”,表示數(shù)據(jù)結(jié)構(gòu)，,“,C,”,表示計算機基礎，,“,D,”,表示外語，以此類推。將各科目字段設置為字符型，轉(zhuǎn)換后的數(shù)據(jù)表部分數(shù)據(jù)如圖,2,所示。,圖,2,轉(zhuǎn)換后數(shù)據(jù)表,3,研究方法,3,2 Apriori,算法應用,用寬度優(yōu)先的迭代搜索方法，首先找出頻繁,1-,項集,L1,，用,L1,查找頻繁,2-,項集,L2,，以此類推，直到求出所有的頻繁項目集。若發(fā)現(xiàn)某頻繁項集的數(shù)目為零，則停止計算。最后，輸出所有項目的頻繁集。在該程序中依然運用了,Apriori,算法的性質(zhì)：如果一個項集是頻繁的，則它的所有子集也是頻繁的。設最小支持度為,0.3,，產(chǎn)生頻繁項目集,56,個，從產(chǎn)生的頻繁項集中確定它們的子集，然后根據(jù)關聯(lián)規(guī)則挖掘算法原理，設最小可信度為,0.6,，由程序得出關聯(lián)規(guī)則,18,個，部分規(guī)則如表,1,所示。,4,結(jié)果與分析,規(guī)則,1,說明，,數(shù)據(jù)結(jié)構(gòu),成績在,80,90,分之間，,高級語言程序設計,成績也在,80,90,分之間的支持度為,66.8%,置信度為,89.2%,說明學好,數(shù)據(jù)結(jié)構(gòu),課程對學好,高級語言課程,起到關鍵作用，以后安排課程時可以將,數(shù)據(jù)結(jié)構(gòu),安排在前，教師授課中要督促學生學好這門課程，打好基礎。,規(guī)則,3,說明,外語,成績在,70,80,分之間，,高級語言程序設計,成績在,80,90,分之間的支持度為,61.6%,置信度為,79.8%,，,規(guī)則,4,說明,計算機基礎,成績在,70,80,分之間，,高級語言程序設計,在,80,90,分之間的支持度為,72.6%,，置信度為,85.7%,；這兩個規(guī)則表示公共基礎課程,外語,和,計算機基礎,對學好計算機專業(yè)課也很重要，同時可以看出,計算機基礎,成績和,外語,成績相對偏低，需要引起重視。,規(guī)則,5,說明,數(shù)據(jù)庫原理,成績在,80,90,分之間，,計算機網(wǎng)絡,也在,80,90,分之間的支持度為,58.4%,置信度為,76.5%,規(guī)則,6,說明,高級語言程序設計,在,80,90,分之間，,計算機網(wǎng)絡,也在,80,90,分之間的支持度為,56.9%,置信度為,83.4%,這兩個規(guī)則雖然可信度和置信度都較高，但實際究竟有無關聯(lián)需要深入探討。,規(guī)則,2,說明,計算機基礎,成績在,70,80,分之間，,工科高數(shù),在,80,90,分之間的支持度為,55.8%,置信度為,87.2%,雖然可信度和置信度都達到了要求，但根據(jù)實際經(jīng)驗，兩者并無直接關聯(lián)，實際工作中可以不予考慮。其他規(guī)則同樣如此，需要決策者根據(jù)實際情況具體研究，有分析地借鑒參考。,5,結(jié)語,高等學校學生信息量巨大，運用關聯(lián)規(guī)則挖掘算法進行數(shù)據(jù)挖掘，能夠得到很多有價值的信息，挖掘出的規(guī)則對教務人員以及教師具有重大意義。舉一反三，如果從其他信息中能夠挖掘出更多的規(guī)則，例如個人成績與班級、專業(yè)之間的關系；個人成績與家庭、地域之間的關系等，必然對教學工作起到積極的指導作用。,Apriori算法的應用,例,:,假設數(shù)據(jù)項集合,I=I,1,I,2,I,3,I,4,I,5,共有,5,個數(shù)據(jù)項,表,1,給出含有這,5,個數(shù)據(jù)項的,9,條交易數(shù)據(jù)庫,第一列是交易數(shù)據(jù)的標識號,第二列是交易數(shù)據(jù)所包含的項目,假定,最小支持度是,2,最小可信度為,50%,求最大頻繁項目集及其期望規(guī)則,.,表,1,交易數(shù)據(jù)集,注,:,支持度,=,項集頻度,選擇有且只有一個相同元素的兩個,2_,項頻繁集進,行連接,生成,3_,項候選集是,I1,I2,I3,I1,I2,I5,I1,I3,I5,I2,I3,I4,I2,I3,I5,I2,I4,I5,I1,I2,I4,如果一個項集是頻繁的，則它的所有子集也是頻,繁的。所以只考慮,I1,I2,I3,I1,I2,I5.,生成,4_,項候選集是,I1,I2,I3,I5,而,I2,I3,I5,不是頻繁集,所以不存在,4_,項頻繁集,.,從兩個最大頻繁集,I1,I2,I3,和,I1,I2,I5,可推出侯選關聯(lián)規(guī)則,再從侯選關聯(lián)規(guī)則中選出大于最小可信度的關聯(lián)規(guī)則即為期望的規(guī)則,.,從最大頻繁項集中可得候選關聯(lián)規(guī)則,大于最小可信度的為關聯(lián)規(guī)則,(*),同理，從六個,2_,項頻繁集可推出侯選關聯(lián)規(guī)則,再從侯選關聯(lián)規(guī)則中選出大于最小可信度的關聯(lián)規(guī)則即為期望的規(guī)則,.,SQL Server 2005:,最低支持,:,此參數(shù)是關聯(lián)規(guī)則的最小支持,低于此值的對象組將會被過濾,;,最小項集大小,:,項集的對象數(shù)低于此值將會被過濾,;,最小概率,:,此參數(shù)是關聯(lián)規(guī)則的最小可信度,低于此值的規(guī)則將會被過濾,;,最低重要性,:,此參數(shù)是關聯(lián)規(guī)則的作用度,通過對數(shù)的方式來取得,大于零,指標越大,規(guī)則越顯著,小于零,指標越小,.,