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ī)則，用于對新集進(jìn)行預(yù)測。決策樹算法可設(shè)計(jì)成具有良好可伸縮性的算法，能夠很好地與超大型數(shù)據(jù)庫結(jié)合，處理相關(guān)的多種數(shù)據(jù)類型，并且,其運(yùn)算結(jié)果容易被人理解，其分類模式容易轉(zhuǎn)化成分類規(guī)則。(二)、算法思想：該算法的基本思想是：首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集

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

3、和一些老字型大小的零售店也在進(jìn)行數(shù)據(jù)挖掘，以便猜測這些年來顧客的消費(fèi)習(xí)慣。(2) Apriori算法應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域，比如時(shí)候入侵檢測技術(shù)中。早期中大型的電腦系統(tǒng)中都收集審計(jì)信息來建立跟蹤檔，這些審計(jì)跟蹤的目的多是為了性能測試或計(jì)費(fèi)，因此對攻擊檢測提供的有用信息比較少。它通過模式的學(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挖掘算法存在的不足進(jìn)行改進(jìn)，先將事務(wù)數(shù)據(jù)庫映射為一個(gè)布爾矩陣，用一種逐層遞增的思想來動(dòng)態(tài)的分配內(nèi)存進(jìn)行存儲，再利用向量求"與"運(yùn)算，尋找頻繁項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的Apriori算法在運(yùn)行效率上有了很大的提升，挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對性的開展貧困助學(xué)工作。(4) Apriori算法被廣泛應(yīng)用于移動(dòng)通信領(lǐng)域。移動(dòng)增值業(yè)務(wù)逐漸成為移動(dòng)通信市場上最有活力、最具潛力、最受矚目的業(yè)務(wù)。隨著產(chǎn)業(yè)的復(fù)蘇，越來越多的增值

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

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

7、接產(chǎn)生候選k項(xiàng)集的集合。候選集合記作Ck。設(shè)l1和l2是Lk-1中的成員。記lij表示li中的第j項(xiàng)。假設(shè)Apriori算法對事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序，即對于（k-1）項(xiàng)集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中每個(gè)候選的計(jì)數(shù)，判斷是否小于最小支持度計(jì)數(shù)，如果不是，則認(rèn)為該候選是頻繁的。為了壓縮Ck，可以利用Apriori性質(zhì)：任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的，反之，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。、Apriori算法實(shí)例:假設(shè)有一個(gè)數(shù)據(jù)庫D,其中有4個(gè)事務(wù)記實(shí)例一：下面以圖例的方式說明該算法的運(yùn)行過程:錄，分別表示為：這里預(yù)定最小支持度minSupport=2,下面用圖例說明算法運(yùn)行的過程:1、掃描D,對每個(gè)候選項(xiàng)進(jìn)行支持度計(jì)數(shù)得到表C1:項(xiàng)集支持度計(jì)敵032123133141里3L1:2、比較候選

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

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ì)剪枝:刪除其子集為非頻繁的選項(xiàng)：頻繁項(xiàng)集的所有子集必須是頻繁的，對候選項(xiàng)C3,我們可以A,B,C的除這個(gè)選項(xiàng)；2項(xiàng)子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪A,C,E的2除這個(gè)選項(xiàng)；B,C,E的2因此保留這個(gè)選項(xiàng)。DatabaseTDB項(xiàng)子集是項(xiàng)子集是A,C,A,E,C,EB,C,B,E,C,E,其中A,E,它的所有2一項(xiàng)子集都是L2的元素,3ldscan不是L2

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

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

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