2019年數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)總結(jié)

1、2019 年數(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)不能再

2、進(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

3、.2ID3算法1.2.1概念提取算法 CLS1) 初始化參數(shù) C=E，E 包括所有的例子， 根；2) 如果 C中的任一元素 e 同屬于同一個(gè)決策 建一個(gè)葉子 點(diǎn) YES 止；否 依啟 式 準(zhǔn)， 特征 Fi=V1,V2,V3, ,Vn并 建判定 點(diǎn)， 劃分 C 互不相交的 N 個(gè)集合 C1，C2，C3，Cn；3) 任一個(gè) Ci 。1.2.2ID3算法1) 隨機(jī) C的一個(gè)子集 W(窗口 ) ；2) 用 CLS生成 W的分 DT( 的啟 式 準(zhǔn)在后 ) ；3) 序 描 C搜集 DT的意外 ( 即由 DT無(wú)法確定的例子 ) ；4) 合 W與已 的意外，形成新的 W；5) 重復(fù) 2) 到 4) ，直到無(wú)

4、例外 止。啟發(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) 相同的因素必須得到相同的

5、結(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)生的分類規(guī)則易于理解，準(zhǔn)確率較高。C4.5算法有如下缺點(diǎn)：在構(gòu)造樹(shù)的過(guò)程中， 需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法

6、的低效。此外， 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.1C4.5對(duì) ID3 算法的改進(jìn)1) 熵的改進(jìn)，加上了子樹(shù)的信息。Split_Infox(X)=-SUM(|T|/|Ti|)*LOG(|Ti|/|T|)；Gainratio(X)=Gain(X)/Split_Infox(X);2) 在輸入數(shù)據(jù)上的改進(jìn)因素屬性

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

8、 的重心，或叫中心點(diǎn)。i是群組Si內(nèi)所有元素k 平均聚類發(fā)明于 1956 年，該算法最常見(jiàn)的形式是采用被稱為勞埃德算法 (Lloydalgorithm) 的迭代式改進(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é)果。 （上

9、面函數(shù)中存在的不同的最優(yōu)解）雖然存在變異，但是勞埃德算法仍舊保持流行，因?yàn)樗趯?shí)際中收斂非常快。實(shí)際上，觀察發(fā)現(xiàn)迭代次數(shù)遠(yuǎn)遠(yuǎn)少于點(diǎn)的數(shù)量。然而最近， DavidArthur 和 SergeiVassilvitskii 提出存在特定的點(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é)果。 另

10、外，算法還假設(shè)均方誤差是計(jì)算群組分散度的最佳參數(shù)。3SVM （支持向量機(jī)）支持向量機(jī)，英文為 SupportVectorMachine ，簡(jiǎn)稱 SV機(jī)（論文中一般簡(jiǎn)稱 SVM）。它是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。支持向量機(jī)屬于一般化線性分類器。它們也可以被認(rèn)為是提克洛夫規(guī)范化（ TikhonovRegularization ）方法的一個(gè)特例。這種分類器的特點(diǎn)是他們能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)。 因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。在統(tǒng)計(jì)計(jì)算中，最大期望（EM）算法是在概率（probabilistic ）模型中尋找參數(shù)最大似然估計(jì)的算法， 其中概率模

11、型依賴于無(wú)法觀測(cè)的隱藏變量（ LatentVariable ）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)的數(shù)據(jù)集聚（ DataClustering ）領(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ò)展到線性不可分的情況。 甚

12、至擴(kuò)展到使用非線性函數(shù)中去， 這種分類器被稱為支持向量機(jī) (SupportVectorMachine ，簡(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)化， 并且在

13、整個(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.CBurges 的模式識(shí)別支持向量機(jī)指南。 vanderWalt 和 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) ) 中或者 (