數(shù)據(jù)挖掘?qū)W習(xí)報(bào)告

1、數(shù)據(jù)挖掘?qū)W習(xí)報(bào)告引言數(shù)據(jù)挖掘是通過(guò)分析每個(gè)數(shù)據(jù)，從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、規(guī)律尋找和規(guī)律表示 3 個(gè)步驟。數(shù)據(jù)挖掘的任務(wù)有關(guān)聯(lián)分析、聚類分析、分類分析、異 常分析、特異群組分析和演變分析等。二、基本概念數(shù)據(jù)挖掘，在人工智能領(lǐng)域，習(xí)慣上又稱為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)也有人把數(shù)據(jù)挖掘 視為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)過(guò)程的一個(gè)基本步驟。知識(shí)發(fā)現(xiàn)過(guò)程由以下三個(gè)階段組成： ( 1) 數(shù)據(jù)準(zhǔn)備，(2)數(shù)據(jù)挖掘，(3)結(jié)果表達(dá)和解釋。數(shù)據(jù)挖掘可以與用戶或知識(shí)庫(kù)交互。 數(shù)據(jù)挖掘是通過(guò)分析每個(gè)數(shù)據(jù)，從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、規(guī) 律尋找和規(guī)律表示 3 個(gè)步驟。數(shù)據(jù)準(zhǔn)備是從相關(guān)的數(shù)據(jù)源中選取

2、所需的數(shù)據(jù)并整合成用 于數(shù)據(jù)挖掘的數(shù)據(jù)集；規(guī)律尋找是用某種方法將數(shù)據(jù)集所含的規(guī)律找出來(lái)；規(guī)律表示是 盡可能以用戶可理解的方式(如可視化)將找出的規(guī)律表示出來(lái)。數(shù)據(jù)挖掘的任務(wù)有關(guān)聯(lián)分析、聚類分析、分類分析、異常分析、特異群組分析和演 變分析，等等。并非所有的信息發(fā)現(xiàn)任務(wù)都被視為數(shù)據(jù)挖掘。例如，使用數(shù)據(jù)庫(kù)管理系 統(tǒng)查找個(gè)別的記錄，或通過(guò)因特網(wǎng)的搜索引擎查找特定的 Web 頁(yè)面，則是信息檢索領(lǐng) 域的任務(wù)。雖然這些任務(wù)是重要的，可能涉及使用復(fù)雜的算法和數(shù)據(jù)結(jié)構(gòu)，但是它們主 要依賴傳統(tǒng)的計(jì)算機(jī)科學(xué)技術(shù)和數(shù)據(jù)的明顯特征來(lái)創(chuàng)建索引結(jié)構(gòu)， 從而有效地組織和檢 索信息。盡管如此，數(shù)據(jù)挖掘技術(shù)也已用來(lái)增強(qiáng)信息檢索

3、系統(tǒng)的能力。 1、數(shù)據(jù)挖掘的基本步驟數(shù)據(jù)挖掘的步驟會(huì)隨不同領(lǐng)域的應(yīng)用而有所變化，每一種數(shù)據(jù)挖掘技術(shù)也會(huì)有各自 的特性和使用步驟，針對(duì)不同問(wèn)題和需求所制定的數(shù)據(jù)挖掘過(guò)程也會(huì)存在差異。此外， 數(shù)據(jù)的完整程度、專業(yè)人員支持的程度等都會(huì)對(duì)建立數(shù)據(jù)挖掘過(guò)程有所影響。這些因素 造成了數(shù)據(jù)挖掘在各不同領(lǐng)域中的運(yùn)用、規(guī)劃，以及流程的差異性，即使同一產(chǎn)業(yè)，也 會(huì)因?yàn)榉治黾夹g(shù)和專業(yè)知識(shí)的涉入程度不同而不同，因此對(duì)于數(shù)據(jù)挖掘過(guò)程的系統(tǒng)化、 標(biāo)準(zhǔn)化就顯得格外重要。如此一來(lái)，不僅可以較容易地跨領(lǐng)域應(yīng)用，也可以結(jié)合不同的 專業(yè)知識(shí)，發(fā)揮數(shù)據(jù)挖掘的真正精神。數(shù)據(jù)挖掘完整的步驟如下： 理解數(shù)據(jù)和數(shù)據(jù)的來(lái)源( understa

4、nding)。 獲取相關(guān)知識(shí)與技術(shù)( acquisition )。 整合與檢查數(shù)據(jù)( integration and checking)。 去除錯(cuò)誤或不一致的數(shù)據(jù)( data cleaning)。 建立模型和假設(shè)( model and hypothesis developmen)t 。 實(shí)際數(shù)據(jù)挖掘工作( data mining)。 測(cè)試和驗(yàn)證挖掘結(jié)果( testing and verification)。 解釋和應(yīng)用( interpretation and use)。由上述步驟可看出，數(shù)據(jù)挖掘牽涉了大量的準(zhǔn)備工作與規(guī)劃工作，事實(shí)上許多專家 都認(rèn)為整套數(shù)據(jù)挖掘的過(guò)程中， 有 80%的時(shí)間和精力

5、是花費(fèi)在數(shù)據(jù)預(yù)處理階段， 其中包 括數(shù)據(jù)的凈化、數(shù)據(jù)格式轉(zhuǎn)換、變量整合，以及數(shù)據(jù)表的鏈接。可見(jiàn)，在進(jìn)行數(shù)據(jù)挖掘 技術(shù)的分析之前，還有許多準(zhǔn)備工作要完成。2、數(shù)據(jù)挖掘十大經(jīng)典算法1. C4.5:是機(jī)器學(xué)習(xí)算法中的一種分類決策樹(shù)算法，其核心算法是ID3算法。2. K-mea ns算法：是一種聚類算法。3.SVM :種監(jiān)督式學(xué)習(xí)的方法，廣泛運(yùn)用于統(tǒng)計(jì)分類以及回歸分析中4. Apriori ：是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。5. EM ：最大期望值法。6. pagerank是google算法的重要內(nèi)容。7. Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器然

6、 后把弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器。8. KNN:是一個(gè)理論上比較成熟的的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)方法之一。9. Naive Bayes：在眾多分類方法中，應(yīng)用最廣泛的有決策樹(shù)模型和樸素貝葉斯 (Naive Bayes)10. Cart：分類與回歸樹(shù)，在分類樹(shù)下面有兩個(gè)關(guān)鍵的思想，第一個(gè)是關(guān)于遞歸地劃 分自變量空間的想法，第二個(gè)是用驗(yàn)證數(shù)據(jù)進(jìn)行減枝。下面我們著重研究一下動(dòng)態(tài)規(guī)劃法。三、動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。 20世紀(jì) 50年 代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程(multistep decision pro

7、cess的優(yōu) 化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理 (principle of optimality) ，把多階段過(guò)程轉(zhuǎn)化為一系 列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新 方法動(dòng)態(tài)規(guī)劃。一)基本思想動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許 多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與 分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后 從這些子問(wèn)題的解得到原問(wèn)題的解。 與分治法不同的是， 適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題， 經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類問(wèn)

8、題，則分解得到的子問(wèn) 題數(shù)目太多，有些子問(wèn)題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問(wèn)題的答 案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我 們可以用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要 它被計(jì)算過(guò)，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算 法多種多樣，但它們具有相同的填表格式。(二)基本結(jié)構(gòu) 多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于 當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故 有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化問(wèn)題的方法為動(dòng)態(tài)

9、規(guī)劃方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、 一種方法，而不是一種特殊算法 不象前面所述的那些搜索或數(shù)值計(jì)算那樣， 具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解 題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對(duì)一種最優(yōu)化問(wèn)題，由于各種問(wèn)題的性質(zhì)不同，確 定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問(wèn)題，有各具特色的解 題方法，而不存在一種萬(wàn)能的動(dòng)態(tài)規(guī)劃，可以解決各類最優(yōu)化問(wèn)題。因此在學(xué)習(xí)時(shí)，除 了要對(duì)基本概念和方法正確理解外，必須具體問(wèn)題具體分析處理，以豐富的想象力去建 立模型，用創(chuàng)造性的技巧去求解。(三)基本模型根據(jù)上例分析和動(dòng)態(tài)規(guī)劃的基本概念，可以得到動(dòng)態(tài)規(guī)劃的基本模型如下：(1) 確定

10、問(wèn)題的決策對(duì)象。(2) 對(duì)決策過(guò)程劃分階段。(3) 對(duì)各階段確定狀態(tài)變量。(4) 根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。(5) 建立各階段狀態(tài)變量的轉(zhuǎn)移過(guò)程，確定狀態(tài)轉(zhuǎn)移方程。四、應(yīng)用舉例用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)導(dǎo)彈攔截。某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，開(kāi)發(fā)出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng) 有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高 于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以 只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被

11、攔截的導(dǎo)彈飛來(lái)時(shí)候的高度。SAMPLE INPUT:389 207 155 300 299 170 158 65SAMPLE OUTPUT:6389 300 299 170 158 65因?yàn)橹挥幸惶讓?dǎo)彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高度外，以 后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以，被攔截的導(dǎo)彈應(yīng)該按飛來(lái)的 高 度組成一個(gè)非遞增序列。題目要求我們計(jì)算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)，并依次輸出 被攔截導(dǎo)彈的高度，實(shí)際上就是要求我們?cè)趯?dǎo)彈依次飛來(lái)的高度序列中尋找 一個(gè)最長(zhǎng) 非遞增子序列。設(shè)X=x 1 ,x 2 ,x n為依次飛來(lái)的導(dǎo)彈序列，Y=y 1 ,y 2 , ,y k為問(wèn)

12、題的最優(yōu)解（即X的最長(zhǎng)非遞增子序列），s為問(wèn)題的狀態(tài)（表示導(dǎo)彈攔截系統(tǒng)當(dāng)前發(fā)送炮彈 能夠到達(dá)的最大高度，初值為s=x第一發(fā)炮彈能夠到達(dá)任意的高度）。如果y 1 =x1 ，即飛來(lái)的第一枚導(dǎo)彈被成功攔截。那么，根據(jù)題意 “每一發(fā)炮彈都不能高于前一發(fā) 的高度”問(wèn)題的狀態(tài)將由s=x變成sx 1 （ x 1為第一枚導(dǎo)彈的高度）；在當(dāng)前狀態(tài) 下，序列丫 1 =y 2 ,y k也應(yīng)該是序列X 1 =x 2 ,x n 的最長(zhǎng)非遞增子序列（大 家用反證法很容易證明）。也就是說(shuō)，在當(dāng)前狀態(tài) s1假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為dmax (即問(wèn)題的最優(yōu)值)，貝U dmax = max(D(i)所以，要計(jì)算問(wèn)題的最優(yōu)值d

13、max ,需要分別計(jì)算出D(1)、D(2)、D(n)的 值，然后將它們進(jìn)行比較，找出其中的最大值。根據(jù)上面分析出來(lái)的遞歸方程，我們完 全可以設(shè)計(jì)一個(gè)遞歸函數(shù)，采用自頂向下的方法計(jì)算 D(i) 的值。然后，對(duì) i 從 1 到 n 分別調(diào)用這個(gè)遞歸函數(shù)，就可以計(jì)算出 D(1)、D(2)、D(n)。但這樣將會(huì)有大量的子問(wèn)題被重復(fù)計(jì)算。比如在調(diào)用遞歸函數(shù)計(jì)算 D(1) 的時(shí)候，可能需要先計(jì)算 D(5) 的值;之后在分別調(diào)用遞歸函數(shù)計(jì)算 D(2) 、D(3) 、D(4) 的時(shí)候，都有可能需要先計(jì)算 D(5) 的值。如此一來(lái)，在整個(gè)問(wèn)題的求解過(guò)程中， D(5) 可能會(huì)被重復(fù)計(jì)算很多 次，從而造成了冗余，降

14、低了程序的效率。其實(shí)，通過(guò)以上分析，我們已經(jīng)知道：D(n)=1。如果將n作為階段對(duì)問(wèn)題進(jìn)行劃分， 根據(jù)問(wèn)題的動(dòng)態(tài)規(guī)劃遞歸方程，我們可以采用自底向上的方法依次計(jì)算出D(n-1) 、D(n-2)、D(1)的值。這樣，每個(gè) D(i)的值只計(jì)算一次，并在計(jì)算的同時(shí)把計(jì)算 結(jié)果保存下來(lái)，從而避免了有些子問(wèn)題被重復(fù)計(jì)算的情況發(fā)生，提高了程序的效率。算 法代碼如下：for(i=n-2;i=0;i-)/ 從后往前計(jì)算 di值for(j=i+1;jn;j+)if(arrayj=arrayi)&(didj+1)di=dj+1;dmax = 0;xh = 1;for(i=0;idmax)dmax = di;xh = i;coutdmaxendl;/輸出結(jié)果 coutarrayxh);int temp = xh;for(i=xh+1;in;i+)if(di=dtemp-1)temp = i;couta