數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)總結(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ì)該類型的對(duì)象依靠屬性進(jìn)行分類。每個(gè)決策樹(shù)可以依靠對(duì)源數(shù)據(jù)庫(kù)的分割進(jìn)行數(shù)據(jù)測(cè)試。這個(gè)過(guò)程可以遞歸式的對(duì)樹(shù)進(jìn)行修剪。當(dāng)不能再進(jìn)行分割或一個(gè)單獨(dú)的類可以被應(yīng)用于某一分支時(shí)，遞歸過(guò)程就完成了。另外，隨機(jī)森林分類器將許多決策樹(shù)結(jié)合起來(lái)以提升分類的正確率。 決策樹(shù)同時(shí)也可以依靠計(jì)算條件概率來(lái)構(gòu)造。決策樹(shù)如果依靠數(shù)學(xué)的計(jì)算方法可以取得更加理想的效果。

　　1.1 決策樹(shù)的工作原理

　　決策樹(shù)一般都是自上而下的來(lái)生成的。

　　選擇分割的方法有多種，但是目的都是一致的，即對(duì)目標(biāo)類嘗試進(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)的話，分類的路徑；

　　3) 對(duì)葉子節(jié)點(diǎn)正確分類的比例。

　　有些規(guī)則的效果可以比其他的一些規(guī)則要好。

　　1.2 ID3算法

　　1.2.1 概念提取算法CLS

　　1) 初始化參數(shù)C={E}，E包括所有的例子，為根；

　　2) 如果C中的任一元素e同屬于同一個(gè)決策類則創(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.2 ID3算法

　　1) 隨機(jī)選擇C的一個(gè)子集W (窗口)；

　　2) 調(diào)用CLS生成W的分類樹(shù)DT(強(qiáng)調(diào)的啟發(fā)式標(biāo)準(zhǔn)在后)；

　　3) 順序掃描C搜集DT的意外(即由DT無(wú)法確定的例子)；

　　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)/|S|；INFO(S)=-SUM(P*LOG(P))；SUM()函數(shù)是求j從1到n的和。Gain(X)=Info(X)-Infox(X)；Infox(X)=SUM( (|Ti|/|T|)*Info(X)；

　　為保證生成的決策樹(shù)最小，ID3算法在生成子樹(shù)時(shí)，選取使生成的子樹(shù)的熵(即Gain(S))最小的特征來(lái)生成子樹(shù)。

　　ID3算法對(duì)數(shù)據(jù)的要求：

　　1) 所有屬性必須為離散量；

　　2) 所有的訓(xùn)練例的所有屬性必須有一個(gè)明確的值；

　　3) 相同的因素必須得到相同的結(jié)論且訓(xùn)練例必須唯一。

　　1.3 C4.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)生的分類規(guī)則易于理解，準(zhǔn)確率較高。

　　C4.5算法有如下缺點(diǎn)：

　　在構(gòu)造樹(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)行。

　　分類決策樹(shù)算法：

　　C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹(shù)算法，其核心算法是ID3算法。

　　分類決策樹(shù)算法是從大量事例中進(jìn)行提取分類規(guī)則的自上而下的決策樹(shù)。

　　決策樹(shù)的各部分是：

　　根：學(xué)習(xí)的事例集；

　　枝：分類的判定條件；

　　葉：分好的各個(gè)類。

　　1.3.1 C4.5對(duì)ID3算法的改進(jìn)

　　1) 熵的改進(jìn)，加上了子樹(shù)的信息。

　　Split_Infox(X)= -SUM( (|T|/|Ti|)*LOG(|Ti|/|T|))；

　　Gain ratio(X)= Gain(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ī)模。

　　2 The k-means algorithm（k平均算法）

　　k-means algorithm是一個(gè)聚類算法，把n個(gè)對(duì)象根據(jù)它們的屬性分為k個(gè)分割，k < n。它與處理混合正態(tài)分布的最大期望算法很相似，因?yàn)樗麄兌荚噲D找到數(shù)據(jù)中自然聚類的中心。它假設(shè)對(duì)象屬性來(lái)自于空間向量，并且目標(biāo)是使各個(gè)群組內(nèi)部的均方誤差總和最小。

　　假設(shè)有k個(gè)群組Si, i=1,2,...,k。μi是群組Si內(nèi)所有元素xj的重心，或叫中心點(diǎn)。

　　k平均聚類發(fā)明于1956年，該算法最常見(jiàn)的形式是采用被稱為勞埃德算法(Lloyd algorithm)的迭代式改進(jìn)探索法。勞埃德算法首先把輸入點(diǎn)分成k個(gè)初始化分組，可以是隨機(jī)的或者使用一些啟發(fā)式數(shù)據(jù)。然后計(jì)算每組的中心點(diǎn)，根據(jù)中心點(diǎn)的位臵把對(duì)象分到離它最近的中心，重新確定分組。繼續(xù)重復(fù)不斷地計(jì)算中心并重新分組，直到收斂，即對(duì)象不再改變分組（中心點(diǎn)位臵不再改變）。

　　勞埃德算法和k平均通常是緊密聯(lián)系的，但是在實(shí)際應(yīng)用中，勞埃德算法是解決k平均問(wèn)題的啟發(fā)式法則，對(duì)于某些起始點(diǎn)和重心的組合，勞埃德算法可能實(shí)際上收斂于錯(cuò)誤的結(jié)果。（上面函數(shù)中存在的不同的最優(yōu)解）

　　雖然存在變異，但是勞埃德算法仍舊保持流行，因?yàn)樗�在�?shí)際中收斂非常快。實(shí)際上，觀察發(fā)現(xiàn)迭代次數(shù)遠(yuǎn)遠(yuǎn)少于點(diǎn)的數(shù)量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的點(diǎn)集使得k平均算法花費(fèi)超多項(xiàng)式時(shí)間達(dá)到收斂。

　　近似的k平均算法已經(jīng)被設(shè)計(jì)用于原始數(shù)據(jù)子集的計(jì)算。

　　從算法的表現(xiàn)上來(lái)說(shuō)，它并不保證一定得到全局最優(yōu)解，最終解的質(zhì)量很大程度上取決于初始化的分組。由于該算法的速度很快，因此常用的一種方法是多次運(yùn)行k平均算法，選擇最優(yōu)解。

　　k平均算法的一個(gè)缺點(diǎn)是，分組的數(shù)目k是一個(gè)輸入?yún)��?shù)，不合適的k可能返回較差的結(jié)果。另外，算法還假設(shè)均方誤差是計(jì)算群組分散度的最佳參數(shù)。

　　3 SVM（支持向量機(jī)）

　　支持向量機(jī)，英文為Support Vector Machine，簡(jiǎn)稱SV機(jī)（論文中一般簡(jiǎn)稱SVM）。它是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。

　　支持向量機(jī)屬于一般化線性分類器。它們也可以被認(rèn)為是提克洛夫規(guī)范化（Tikhonov Regularization）方法的一個(gè)特例。這種分類器的特點(diǎn)是他們能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)。因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。

　　在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計(jì)的算法，其中概率模型依賴于無(wú)法觀測(cè)的隱藏變量（Latent Variable）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)的數(shù)據(jù)集聚（Data Clustering）領(lǐng)域。最大期望算法經(jīng)過(guò)兩個(gè)步驟交替進(jìn)行計(jì)算，第一步是計(jì)算期望（E），也就是將隱藏變量像能夠觀測(cè)到的一樣包含在內(nèi)從而計(jì)算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值從而計(jì)算參數(shù)的最大似然估計(jì)。M 步上找到的參數(shù)然后用于另外一個(gè) E 步計(jì)算，這個(gè)過(guò)程不斷交替進(jìn)行。

　　Vapnik等人在多年研究統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上對(duì)線性分類器提出了另一種設(shè)計(jì)最佳準(zhǔn)則。其原理也從線性可分說(shuō)起，然后擴(kuò)展到線性不可分的情況。甚至擴(kuò)展到使用非線性函數(shù)中去，這種分類器被稱為支持向量機(jī)(Support Vector Machine，簡(jiǎn)稱SVM)。支持向量機(jī)的提出有很深的理論背景。支持向量機(jī)方法是在近年來(lái)提出的一種新方法，但是進(jìn)展很快，已經(jīng)被廣泛應(yīng)用在各個(gè)領(lǐng)域之中。

　　SVM的主要思想可以概括為兩點(diǎn)：(1) 它是針對(duì)線性可分情況進(jìn)行分析，對(duì)于線性不可分的情況，通過(guò)使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對(duì)樣本的非線性特征進(jìn)行線性分析成為可能；(2) 它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個(gè)樣本空間的期望風(fēng)險(xiǎn)以某個(gè)概率滿足一定上界。

　　在學(xué)習(xí)這種方法時(shí)，首先要弄清楚這種方法考慮問(wèn)題的特點(diǎn)，這就要從線性可分的最簡(jiǎn)單情況討論起，在沒(méi)有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分等較復(fù)雜的情況，支持向量機(jī)在設(shè)計(jì)時(shí)，需要用到條件極值問(wèn)題的求解，因此需用拉格朗日乘子理論，但對(duì)多數(shù)人來(lái)說(shuō)，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時(shí)只要了解拉格朗日理論的有關(guān)結(jié)論就行。

　　支持向量機(jī)將向量映射到一個(gè)更高維的空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開(kāi)數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面。分隔超平面使兩個(gè)平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。一個(gè)極好的指南是C.J.C Burges的《模式識(shí)別支持向量機(jī)指南》。van der Walt 和 Barnard 將支持向量機(jī)和其他分類器進(jìn)行了比較。

　　有很多個(gè)分類器(超平面）可以把數(shù)據(jù)分開(kāi)，但是只有一個(gè)能夠達(dá)到最大分割。

　　我們通常希望分類的過(guò)程是一個(gè)機(jī)器學(xué)習(xí)的過(guò)程。這些數(shù)據(jù)點(diǎn)并不需要是中的點(diǎn)，而可以是任意(統(tǒng)計(jì)學(xué)符號(hào))中或者 (計(jì)算機(jī)科學(xué)符號(hào)) 的點(diǎn)。我們希望能夠把這些點(diǎn)通過(guò)一個(gè)n-1維的超平面分開(kāi)，通常這個(gè)被稱為線性分類器。有很多分類器都符合這個(gè)要求，但是我們還希望找到分類最佳的平面，即使得屬于兩個(gè)不同類的數(shù)據(jù)點(diǎn)間隔最大的那個(gè)面，該面亦稱為最大間隔超平面。如果我們能夠找到這個(gè)面，那么這個(gè)分類器就稱為最大間隔分類器。

　　設(shè)樣本屬于兩個(gè)類，用該樣本訓(xùn)練SVM得到的最大間隔超平面。在超平面上的樣本點(diǎn)也稱為支持向量。

【數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)總結(jié)】相關(guān)文章：

挖掘買賣合同01-15

教師外出學(xué)習(xí)總結(jié)-學(xué)習(xí)總結(jié)12-23

有關(guān)寫大學(xué)學(xué)習(xí)總結(jié)-學(xué)習(xí)總結(jié)12-21

外出參觀學(xué)習(xí)總結(jié)3篇-學(xué)習(xí)總結(jié)12-21

大學(xué)三年學(xué)習(xí)總結(jié)-學(xué)習(xí)總結(jié)12-21

挖掘機(jī)租賃合同(15篇)01-28

學(xué)習(xí)部部門學(xué)習(xí)總結(jié)08-23

學(xué)年學(xué)習(xí)總結(jié)12-21

盾構(gòu)學(xué)習(xí)總結(jié)11-26

學(xué)習(xí)的總結(jié)08-18