20090307113曹晨數(shù)據(jù)挖掘期末大作業(yè)

1、數(shù)據(jù)挖掘原理、算法及應(yīng)用學(xué)號：20120311145學(xué)生所在學(xué)院：信息工程學(xué)院學(xué)生姓名：顏偉泰任課教師：湯亮教師所在學(xué)院：信息工程學(xué)院2015年12月12年級決策樹分類算法顏偉泰12軟件(1)班一'、摘要(一)、決策樹算法簡介：決策樹算法是一種歸納分類算法，它通過對訓(xùn)練集的學(xué)習(xí)，挖掘出有用的規(guī)則，用于對新集進行預(yù)測。決策樹算法可設(shè)計成具有良好可伸縮性的算法，能夠很好地與超大型數(shù)據(jù)庫結(jié)合，處理相關(guān)的多種數(shù)據(jù)類型，并且,其運算結(jié)果容易被人理解，其分類模式容易轉(zhuǎn)化成分類規(guī)則。(二)、算法思想：該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集

2、產(chǎn)生強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞歸的方法。(三)、算法運用領(lǐng)域：(1) Apriori算法廣泛應(yīng)用于商業(yè)中，應(yīng)用于消費市場價格分析中，它能夠很快的求出各種產(chǎn)品之間的價格關(guān)系和它們之間的影響。通過數(shù)據(jù)挖掘，市場商人可以瞄準(zhǔn)目標(biāo)客戶，采用個人股票行市、最新信息、特殊的市場推廣活動或其他一些特殊的信息手段，從而極大地減少廣告預(yù)算和增加收入。百貨商場、超市

3、和一些老字型大小的零售店也在進行數(shù)據(jù)挖掘，以便猜測這些年來顧客的消費習(xí)慣。(2) Apriori算法應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域，比如時候入侵檢測技術(shù)中。早期中大型的電腦系統(tǒng)中都收集審計信息來建立跟蹤檔，這些審計跟蹤的目的多是為了性能測試或計費，因此對攻擊檢測提供的有用信息比較少。它通過模式的學(xué)習(xí)和訓(xùn)練可以發(fā)現(xiàn)網(wǎng)絡(luò)用戶的異常行為模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘結(jié)果規(guī)則，是網(wǎng)絡(luò)入侵檢測系統(tǒng)可以快速的發(fā)現(xiàn)用戶的行為模式，能夠快速的鎖定攻擊者，提高了基于關(guān)聯(lián)規(guī)則的入侵檢測系統(tǒng)的檢測性。(3) Apriori算法應(yīng)用于高校管理中。隨著高校貧困生人數(shù)的不斷增加，學(xué)校管理部門資助工

4、作難度也越加增大。針對這一現(xiàn)象，提出一種基于數(shù)據(jù)挖掘算法的解決方法。將關(guān)聯(lián)規(guī)則的Apriori算法應(yīng)用到貧困助學(xué)體系中，并且針對經(jīng)典Apriori挖掘算法存在的不足進行改進，先將事務(wù)數(shù)據(jù)庫映射為一個布爾矩陣，用一種逐層遞增的思想來動態(tài)的分配內(nèi)存進行存儲，再利用向量求"與"運算，尋找頻繁項集。實驗結(jié)果表明，改進后的Apriori算法在運行效率上有了很大的提升，挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對性的開展貧困助學(xué)工作。(4) Apriori算法被廣泛應(yīng)用于移動通信領(lǐng)域。移動增值業(yè)務(wù)逐漸成為移動通信市場上最有活力、最具潛力、最受矚目的業(yè)務(wù)。隨著產(chǎn)業(yè)的復(fù)蘇，越來越多的增值

5、業(yè)務(wù)表現(xiàn)出強勁的發(fā)展勢頭，呈現(xiàn)出應(yīng)用多元化、營銷品牌化、管理集中化、合作縱深化的特點。針對這種趨勢，在關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘中廣泛應(yīng)用的Apriori算法被很多公司應(yīng)用。依托某電信運營商正在建設(shè)的增值業(yè)務(wù)We跋據(jù)倉庫平臺，對來自移動增值業(yè)務(wù)方面的調(diào)查數(shù)據(jù)進行了相關(guān)的挖掘處理，從而獲得了關(guān)于用戶行為特征和需求的間接反映市場動態(tài)的有用信息，這些信息在指導(dǎo)運營商的業(yè)務(wù)運營和輔助業(yè)務(wù)提供商的決策制定等方面具有十分重要的參考價值。二、算法步驟Apriori算法過程分為兩個步驟：第一步通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設(shè)定的閾值的項集；第二步利用頻繁項集構(gòu)造出滿足用戶最小信任度的規(guī)則

6、。具體做法就是：首先找出頻繁1-項集，記為L1;然后利用L1來產(chǎn)生候選項集C2,對C2中的項進行判定挖掘出L2,即頻繁2-項集；不斷如此循環(huán)下去直到無法發(fā)現(xiàn)更多的頻繁k-項集為止。每挖掘一層Lk就需要掃描整個數(shù)據(jù)庫一遍。算法利用了一個性質(zhì)：Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的。意思就是說，生成一個k-itemset的候選項時，如果這個候選項有子集不在（k-1）-itemset（已經(jīng)確定是frequent的）中時，那么這個候選項就不用拿去和支持度判斷了，直接刪除。具體而言：1）連接步為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連

7、接產(chǎn)生候選k項集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記lij表示li中的第j項。假設(shè)Apriori算法對事務(wù)或項集中的項按字典次序排序，即對于（k-1）項集li,li1<li2<.<lik-1。將Lk-1與自身連接，如果（l11=l21）&&（l12=l22）&&.&&（l1k-2=l2k-2）&&（l1k-1<l2k-1）,那認(rèn)為l1和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是l11,l12,l1k-1,l2k-1。2）剪枝步CK是LK的超集，也就是說，CK的成員可能是也可能不是頻繁的

8、。通過掃描所有的事務(wù)（交易），確定CK中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認(rèn)為該候選是頻繁的。為了壓縮Ck，可以利用Apriori性質(zhì)：任一頻繁項集的所有非空子集也必須是頻繁的，反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。、Apriori算法實例:假設(shè)有一個數(shù)據(jù)庫D,其中有4個事務(wù)記實例一：下面以圖例的方式說明該算法的運行過程:錄，分別表示為：這里預(yù)定最小支持度minSupport=2,下面用圖例說明算法運行的過程:1、掃描D,對每個候選項進行支持度計數(shù)得到表C1:項集支持度計敵032123133141里3L1:2、比較候選

9、項支持度計數(shù)與最小支持度minSupport,產(chǎn)生1維最大項目集3、由L1產(chǎn)生候選項集C2：項集0111國1213(12.15)(13.15)4、掃描D,對每個候選項集進行支持度計數(shù)哽集支持度計數(shù)H121H13211母112,1321215)3131525、比較候選項支持度計數(shù)與最小支持度minSupport,產(chǎn)生2維最大項目集L2：項集支持度計敷HJ32(12132I2J53131526、由L2產(chǎn)生候選項集C3:項集卜2.13.15minSupport,產(chǎn)生3維最大項目集L3:7、比較候選項支持度計數(shù)與最小支持度項集支持度計數(shù)1213,152算法終止。(AB.C)實例二：下圖從整體同樣的能說

10、明此過程:此例的分析如下:A,B,C,A,C,E,B,C,E3.這樣，剪枝后得到C3=B,C,Escan1.連接：C3=L2L2=A,C,B,C,B,EC,EA,C,B,C,B,EC,E=2.使用Apriori性質(zhì)剪枝:刪除其子集為非頻繁的選項：頻繁項集的所有子集必須是頻繁的，對候選項C3,我們可以A,B,C的除這個選項；2項子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪A,C,E的2除這個選項；B,C,E的2因此保留這個選項。DatabaseTDB項子集是項子集是A,C,A,E,C,EB,C,B,E,C,E,其中A,E,它的所有2一項子集都是L2的元素,3ldscan不是L2

11、的元素，所以刪PTscan四、綜合分析（一）、從算法的運行過程，我們可以看出該Apriori算法的優(yōu)點：簡單、易理解、數(shù)據(jù)要求低（二）、我們也可以看到Apriori算法的缺點：（1）在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；（2）每次計算項集的支持度時，都對數(shù)據(jù)庫D中的全部記錄進行了一遍掃描比較，如果是一個大型的數(shù)據(jù)庫的話，這種掃描比較會大大增加計算機系統(tǒng)的I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄的增加呈現(xiàn)出幾何級數(shù)的增加。因此人們開始尋求更好性能的算法。改進Apriori算法的方法方法1:基于hash表的項集計數(shù)將每個項集通過相應(yīng)的hash函數(shù)映射到hash表

12、中的不同的桶中，這樣可以通過將桶中的項集技術(shù)跟最小支持計數(shù)相比較先淘汰一部分項集。方法2：事務(wù)壓縮（壓縮進一步迭代的事務(wù)數(shù)）不包含任何k-項集的事務(wù)不可能包含任何（k+1）-項集，這種事務(wù)在下一步的計算中可以加上標(biāo)記或刪除方法3:劃分挖掘頻繁項集只需要兩次數(shù)據(jù)掃描D中的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。第一次掃描：將數(shù)據(jù)劃分為多個部分并找到局部頻繁項集第二次掃描：評估每個候選項集的實際支持度，以確定全局頻繁項集。方法4:選樣（在給定數(shù)據(jù)的一個子集挖掘）基本思想：選擇原始數(shù)據(jù)的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式通過犧牲精確度來減少算法開銷，為了提高效率，樣

13、本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來減少遺漏的頻繁模式可以通過一次全局掃描來驗證從樣本中發(fā)現(xiàn)的模式可以通過第二此全局掃描來找到遺漏的模式方法5:動態(tài)項集計數(shù)在掃描的不同點添加候選項集，這樣，如果一個候選項集已經(jīng)滿足最少支持度，則在可以直接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續(xù)計算。Apriori算法的優(yōu)化思路1、在逐層搜索循環(huán)過程的第k步中，根據(jù)k-1步生成的k-1維頻繁項目集來產(chǎn)生k維候選項目集,由于在產(chǎn)生k-1維頻繁項目集時，我們可以實現(xiàn)對該集中出現(xiàn)元素的個數(shù)進行計數(shù)處理，因此對某元素而言，若它的計數(shù)個數(shù)不到k-1的話，可以事先刪除該元素，從而排除由該元素將引起的大規(guī)格所有組合。這是因為對某一個元素要成為K維項目集的一元素的話，該元素在k-1階頻繁項目集中的計數(shù)次數(shù)必須達(dá)到K-1個，否則不可能生成K維項目集（性質(zhì)3）。2、根據(jù)以上思路得到了這個候選項目集后，可以對數(shù)據(jù)庫D的每一個事務(wù)進行掃描，若該事務(wù)中至少含有候選項目集Ck中的一員則保留該項事務(wù)，否則把該事物記錄與數(shù)據(jù)庫末端沒有作刪除標(biāo)記的事務(wù)記錄對換，并對移到數(shù)據(jù)庫末端的事務(wù)記錄作刪除標(biāo)一記，整個數(shù)據(jù)庫掃描完畢后為新的事務(wù)數(shù)據(jù)庫D'中。因此隨著K的增大，D'