[工學(xué)]數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)

《[工學(xué)]數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

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

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

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

4、確定的例子)；4)組合W與已發(fā)現(xiàn)的意外，形成新的W；5)重復(fù)2)到4)，直到無(wú)例外為止。啟發(fā)式標(biāo)準(zhǔn)：只跟本身與其子樹(shù)有關(guān)，采取信息理論用熵來(lái)量度。熵是選擇事件時(shí)選擇自由度的量度，其計(jì)算方法為：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)；為保證生成的決策樹(shù)最小，ID3算法在生成子樹(shù)時(shí)，選取使生成的子樹(shù)的熵(即Gain(S))最小的特征來(lái)生成子樹(shù)。ID3算法對(duì)數(shù)據(jù)的要求：1)所有屬性必須為離散

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

12、造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。分類(lèi)決策樹(shù)算法：C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類(lèi)決策樹(shù)算法，其核心算法是ID3算法。分類(lèi)決策樹(shù)算法是從大量事例中進(jìn)行提取分類(lèi)規(guī)則的自上而下的決策樹(shù)。決策樹(shù)的各部分是：根：學(xué)習(xí)的事例集；枝：分類(lèi)的判定條件；葉：分好的各個(gè)類(lèi)。1.3.1C4.5對(duì)ID3算法的改進(jìn)1)熵的改進(jìn)，加上了子樹(shù)的信息。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ù)上的改進(jìn)①因素屬性的值可以是連續(xù)量，C4.5對(duì)其排序并分成不同的集合后按照ID3算法當(dāng)作離散量進(jìn)行處理，但結(jié)論屬性的值必須是離散值。②訓(xùn)練例的因素屬性值可以是不確定的，以?表示，但結(jié)論必須是確定的。3)對(duì)已生成的決策樹(shù)進(jìn)行裁剪，減小生成樹(shù)的規(guī)模。2Thek-meansalgorithm（k平均算法）k-meansalgorithm是一個(gè)聚類(lèi)算法，把n個(gè)對(duì)象根據(jù)它們的屬性分為k個(gè)分割，k