[工學]數(shù)據(jù)挖掘機器學習

《[工學]數(shù)據(jù)挖掘機器學習》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在應用文檔-天天文庫。

1、機器學習、數(shù)據(jù)挖掘的經(jīng)典算法總結1決策樹算法機器學習中，決策樹是一個預測模型；它代表的是對象屬性值與對象值之間的一種映射關系。樹中每個節(jié)點表示某個對象，每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應具有上述屬性值的子對象。決策樹僅有單一輸出；若需要多個輸出，可以建立獨立的決策樹以處理不同輸出。從數(shù)據(jù)產(chǎn)生決策樹的機器學習技術叫做決策樹學習,通俗說就是決策樹。決策樹學習也是數(shù)據(jù)挖掘中一個普通的方法。在這里，每個決策樹都表述了一種樹型結構，它由它的分支來對該類型的對象依靠屬性進行分類。每個決策樹可以依靠對源數(shù)據(jù)庫的分割進行數(shù)據(jù)測試。這個過程可以遞歸式的對樹進行修剪。

2、當不能再進行分割或一個單獨的類可以被應用于某一分支時，遞歸過程就完成了。另外，隨機森林分類器將許多決策樹結合起來以提升分類的正確率。決策樹同時也可以依靠計算條件概率來構造。決策樹如果依靠數(shù)學的計算方法可以取得更加理想的效果。1.1決策樹的工作原理決策樹一般都是自上而下的來生成的。選擇分割的方法有多種，但是目的都是一致的，即對目標類嘗試進行最佳的分割。從根節(jié)點到葉子節(jié)點都有一條路徑，這條路徑就是一條“規(guī)則”。決策樹可以是二叉的，也可以是多叉的。對每個節(jié)點的衡量：1)通過該節(jié)點的記錄數(shù)；2)如果是葉子節(jié)點的話，分類的路徑；3)對葉子節(jié)點正確分類的比例。有些規(guī)則的效果可以比其

3、他的一些規(guī)則要好。YYYYNNNNw1Tx≥0w4Tx≥0w3Tx≥0w2Tx≥0二叉決策樹框圖1.2ID3算法1.2.1概念提取算法CLS1)初始化參數(shù)C={E}，E包括所有的例子，為根；2)如果C中的任一元素e同屬于同一個決策類則創(chuàng)建一個葉子節(jié)點YES終止；否則依啟發(fā)式標準，選擇特征Fi={V1,V2,V3,……,Vn}并創(chuàng)建判定節(jié)點，劃分C為互不相交的N個集合C1，C2，C3，……，Cn；3)對任一個Ci遞歸。1.2.2ID3算法1)隨機選擇C的一個子集W(窗口)；2)調(diào)用CLS生成W的分類樹DT(強調(diào)的啟發(fā)式標準在后)；3)順序掃描C搜集DT的意外(即由DT無法

4、確定的例子)；4)組合W與已發(fā)現(xiàn)的意外，形成新的W；5)重復2)到4)，直到無例外為止。啟發(fā)式標準：只跟本身與其子樹有關，采取信息理論用熵來量度。熵是選擇事件時選擇自由度的量度，其計算方法為：P=freq(Cj,S)/

5、S

6、；INFO(S)=-SUM(P*LOG(P))；SUM()函數(shù)是求j從1到n的和。Gain(X)=Info(X)-Infox(X)；Infox(X)=SUM((

7、Ti

8、/

9、T

10、)*Info(X)；為保證生成的決策樹最小，ID3算法在生成子樹時，選取使生成的子樹的熵(即Gain(S))最小的特征來生成子樹。ID3算法對數(shù)據(jù)的要求：1)所有屬性必須為離散

11、量；2)所有的訓練例的所有屬性必須有一個明確的值；3)相同的因素必須得到相同的結論且訓練例必須唯一。1.3C4.5算法由于ID3算法在實際應用中存在一些問題，于是Quilan提出了C4.5算法，嚴格上說C4.5只能是ID3的一個改進算法。C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進：1)用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；2)在樹構造過程中進行剪枝；3)能夠完成對連續(xù)屬性的離散化處理；4)能夠對不完整數(shù)據(jù)進行處理。C4.5算法有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。C4.5算法有如下缺點：在構

12、造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當訓練集大得無法在內(nèi)存容納時程序無法運行。分類決策樹算法：C4.5算法是機器學習算法中的一種分類決策樹算法，其核心算法是ID3算法。分類決策樹算法是從大量事例中進行提取分類規(guī)則的自上而下的決策樹。決策樹的各部分是：根：學習的事例集；枝：分類的判定條件；葉：分好的各個類。1.3.1C4.5對ID3算法的改進1)熵的改進，加上了子樹的信息。Split_Infox(X)=-SUM((

13、T

14、/

15、Ti

16、)*LOG(

17、Ti

18、/

19、T

20、))；Gainratio(X)=G

21、ain(X)/Split_Infox(X);2)在輸入數(shù)據(jù)上的改進①因素屬性的值可以是連續(xù)量，C4.5對其排序并分成不同的集合后按照ID3算法當作離散量進行處理，但結論屬性的值必須是離散值。②訓練例的因素屬性值可以是不確定的，以?表示，但結論必須是確定的。3)對已生成的決策樹進行裁剪，減小生成樹的規(guī)模。2Thek-meansalgorithm（k平均算法）k-meansalgorithm是一個聚類算法，把n個對象根據(jù)它們的屬性分為k個分割，k