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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、低了程序的效率。其實，通過以上分析，我們已經(jīng)知道：D(n)=1。如果將n作為階段對問題進行劃分， 根據(jù)問題的動態(tài)規(guī)劃遞歸方程，我們可以采用自底向上的方法依次計算出D(n-1) 、D(n-2)、D(1)的值。這樣，每個 D(i)的值只計算一次，并在計算的同時把計算 結(jié)果保存下來，從而避免了有些子問題被重復(fù)計算的情況發(fā)生，提高了程序的效率。算 法代碼如下：for(i=n-2;i=0;i-)/ 從后往前計算 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