第一篇：斯坦福大學(xué)機(jī)器學(xué)習(xí)梯度算法總結(jié)

斯坦福大學(xué)機(jī)器學(xué)習(xí)梯度下降算法學(xué)習(xí)心得和相關(guān)概念介紹。

1基礎(chǔ)概念和記號(hào)

線性代數(shù)對(duì)于線性方程組可以提供一種簡(jiǎn)便的表達(dá)和操作方式，例如對(duì)于如下的方程組：

4x1-5x2=13

-2x1+3x2=-9

可以簡(jiǎn)單的表示成下面的方式：

X也是一個(gè)矩陣，為(x1,x2)T，當(dāng)然你可以看成一個(gè)列向量。

1.1基本記號(hào)

用A ∈表示一個(gè)矩陣A，有m行，n列，并且每一個(gè)矩陣元素都是實(shí)數(shù)。用x ∈ , 表示一個(gè)n維向量.通常是一個(gè)列向量.如果要表示一個(gè)行向量的話，通常是以列向量的轉(zhuǎn)置（后面加T）來(lái)表示。

1.2向量的內(nèi)積和外積

根據(jù)課內(nèi)的定義，如果形式如xT y，或者yT x，則表示為內(nèi)積，結(jié)果為一個(gè)實(shí)數(shù)，表示的是：，如果形式為xyT，則表示的為外積:。

1.3矩陣-向量的乘法

給定一個(gè)矩陣A ∈ Rm×n，以及一個(gè)向量x ∈ Rn，他們乘積為一個(gè)向量y = Ax ∈ Rm。也即如下的表示：

如果A為行表示的矩陣（即表示為），則y的表示為：

相對(duì)的，如果A為列表示的矩陣，則y的表示為：

即：y看成A的列的線性組合，每一列都乘以一個(gè)系數(shù)并相加，系數(shù)由x得到。

同理，yT=xT*A表示為：

yT是A的行的線性組合，每一行都乘以一個(gè)系數(shù)并相加，系數(shù)由x得到。

1.4矩陣-矩陣的乘法

同樣有兩種表示方式:

第一種：A表示為行，B表示為列

第二種，A表示為列，B表示為行：

本質(zhì)上是一樣的，只是表示方式不同罷了。

1.5矩陣的梯度運(yùn)算（這是老師自定義的）

定義函數(shù)f，是從m x n矩陣到實(shí)數(shù)的一個(gè)映射，那么對(duì)于f在A上的梯度的定義如下：

這里我的理解是，f（A）=關(guān)于A中的元素的表達(dá)式，是一個(gè)實(shí)數(shù)，然后所謂的對(duì)于A的梯度即是和A同樣規(guī)模的矩陣，矩陣中的每一個(gè)元素就是f(A)針對(duì)原來(lái)的元素的求導(dǎo)。

1.6其他概念

因?yàn)槠颍圆辉谶@里繼續(xù)贅述，其他需要的概念還有單位矩陣、對(duì)角線矩陣、矩陣轉(zhuǎn)置、對(duì)稱矩陣（AT=A）、反對(duì)稱矩陣（A=-AT）、矩陣的跡、向量的模、線性無(wú)關(guān)、矩陣的秩、滿秩矩陣、矩陣的逆（當(dāng)且僅當(dāng)矩陣滿秩時(shí)可逆）、正交矩陣、矩陣的列空間(值域)、行列式、特征向量與特征值……

2用到的公式

在課程中用到了許多公式，羅列一下。嗯，部分公式的證明很簡(jiǎn)單，部分難的證明我也不會(huì)，也懶得去細(xì)想了，畢竟感覺(jué)上數(shù)學(xué)對(duì)于我來(lái)說(shuō)更像是工具吧。

轉(zhuǎn)置相關(guān)：

?(AT)T = A

?(AB)T = BT AT

?(A + B)T = AT + BT 跡相關(guān)： ? For A ∈ Rn×n, trA = trAT.? For A, B ∈ Rn×n, tr(A + B)=trA + trB.? For A ∈ Rn×n, t ∈ R, tr(tA)= t trA.? For A, B such that AB issquare, trAB = trBA.? For A, B, C such that ABC issquare, trABC = trBCA = trCAB。當(dāng)乘法變多時(shí)也一樣，就是每次從末尾取一個(gè)矩陣放到前面去，這樣的矩陣乘法所得矩陣的跡是一致的。秩相關(guān)

? For A ∈ Rm×n,rank(A)≤ min(m, n).If rank(A)= min(m, n), 則A稱為滿秩

? For A ∈ Rm×n,rank(A)= rank(AT).? For A ∈ Rm×n, B ∈ Rn×p,rank(AB)≤ min(rank(A), rank(B)).? For A, B ∈ Rm×n,rank(A + B)≤ rank(A)+rank(B).逆相關(guān)：

?(A?1)?1 = A

? If Ax = b, 左右都乘以A?1 得到 x = A?1b.?(AB)?1 = B?1A?1

?(A?1)T =(AT)?1.F通常表示為A?T.行列式相關(guān)：

? For A ∈ Rn×n, |A| = |AT |.? For A, B ∈ Rn×n, |AB| = |A||B|.? For A ∈ Rn×n, |A| = 0，表示矩陣A是奇異矩陣，不可逆矩陣

? For A ∈ Rn×n and A 可逆, |A|?1 = 1/|A|.梯度相關(guān)： ? ?x(f(x)+ g(x))= ?xf(x)+ ?xg(x).? For t ∈ R, ?x(t f(x))= t?xf(x).? ?xbT x = b

? ?xxT Ax = 2Ax(if A 對(duì)稱)

? ?2xxT Ax = 2A(if A 對(duì)稱)

? ?A|A| =(adj(A))T = |A|A?T.adj=adjoint

3梯度下降算法和正規(guī)方程組實(shí)例應(yīng)用

例子用的是上節(jié)課的房?jī)r(jià)的例子，有一組數(shù)據(jù)，有房子面積和房子價(jià)格，輸入格式舉例：

老師定義的變量如下：

m:訓(xùn)練樣本的數(shù)目

x：輸入的變量（輸入的特征，在這個(gè)例子中為房子面積，后來(lái)又加了一個(gè)房子的臥室數(shù)目）

y :輸出變量（目標(biāo)變量，這個(gè)例子中就是房?jī)r(jià)）

(x,y)：表示的是一個(gè)樣本

：表示的第i個(gè)樣本，表示為。

3.1監(jiān)督學(xué)習(xí)概念

所謂的監(jiān)督學(xué)習(xí)即為告訴算法每個(gè)樣本的正確答案，學(xué)習(xí)后的算法對(duì)新的輸入也能輸入正確的答案。監(jiān)督指的是在訓(xùn)練樣本答案的監(jiān)督下，h即為監(jiān)督學(xué)習(xí)函數(shù)。

此例中我們假設(shè)輸出目標(biāo)變量是輸入變量的線性組合，也就是說(shuō)，我們的假設(shè)是存下如下的h（x）：

Theta表示是特征前面的參數(shù)（也稱作特征權(quán)重）。也就是經(jīng)過(guò)h(x)之后得到的就是預(yù)測(cè)的結(jié)果了。

如果假設(shè)x0=1，那么原來(lái)的h(x)就可以簡(jiǎn)單的表示為如下形式：，其中n為特征數(shù)目，我們?yōu)榱吮磉_(dá)簡(jiǎn)便，把theta和x都寫(xiě)成向量的形式。下面就是如何求出θ（向量）使得h(x)盡可能接近實(shí)際結(jié)果的,至少在訓(xùn)練集內(nèi)接近訓(xùn)練集中的正確答案。

我們定義一個(gè)花費(fèi)函數(shù)(costfunction)，針對(duì)每一組θ，計(jì)算出h(x)與實(shí)際值的差值。定義如下：

這也是用的最小二乘法的思想，但是之所以乘以1/2是為了簡(jiǎn)化后面的計(jì)算。針對(duì)訓(xùn)練集中的每一組數(shù)據(jù)。剩下的問(wèn)題就是求得minJ（θ）時(shí)的θ取值，因?yàn)镴(θ)是隨著θ變化而變化，所以我們要求得minJ（θ）時(shí)的θ就是我們想要的θ（這個(gè)min也叫做最小花費(fèi)函數(shù))，怎么樣求出這組theta呢？采用的方法就是梯度下降算法和正規(guī)方程組。我們首先來(lái)看梯度下降算法。

3.2梯度下降算法

梯度下降算法是一種搜索算法，基本思想可以這樣理解：我們從山上的某一點(diǎn)出發(fā)，找一個(gè)最陡的坡走一步（也就是找梯度方向），到達(dá)一個(gè)點(diǎn)之后，再找最陡的坡，再走一步，直到我們不斷的這么走，走到最“低”點(diǎn)（最小花費(fèi)函數(shù)收斂點(diǎn)）。

如上圖所示，x,y表示的是theta0和theta1，z方向表示的是花費(fèi)函數(shù)，很明顯出發(fā)點(diǎn)不同，最后到達(dá)的收斂點(diǎn)可能不一樣。當(dāng)然如果是碗狀的，那么收斂點(diǎn)就應(yīng)該是一樣的。

算法的theta更新表示如下：

對(duì)每一個(gè)theta(j),都先求J(θ)對(duì)theta(j)的偏導(dǎo)(梯度方向)，然后減少α，然后將現(xiàn)在的theta(j)帶入，求得新的theta(j)進(jìn)行更新。其中α為步長(zhǎng)，你可以理解為我們下山時(shí)走的步子的大小。步子太小了，收斂速度慢，步子太大了，可能會(huì)在收斂點(diǎn)附近來(lái)回?cái)[動(dòng)導(dǎo)致無(wú)法到達(dá)最低點(diǎn)。P.S.這個(gè)符號(hào)根據(jù)老師所說(shuō)理解為程序中的賦值符號(hào)(=號(hào))，如果是=號(hào)，則理解為值是相等的(編程里面的==號(hào))。下面我們先理解下，假設(shè)現(xiàn)在訓(xùn)練集只有一組數(shù)據(jù)求關(guān)于theta(j)的偏導(dǎo)：

帶入

可以得到關(guān)于一組數(shù)據(jù)的theta(j)的表達(dá)式，不妨，這組數(shù)據(jù)就是第i組，則表示為：

然后我們將這個(gè)更新theta(j)的方法擴(kuò)充到m個(gè)訓(xùn)練樣本中，就可以得到下面的式子：

P.S.最外面的那個(gè)xj(i)的理解為：第i組數(shù)據(jù)中的第j個(gè)特征(feature)值。

3.2.1批量梯度下降算法（batch gxxxxdxxxx algorithm）

重復(fù)執(zhí)行上面的這個(gè)更新步驟，直到收斂，就可以得到這組θ的值了。就是這個(gè)過(guò)程：。

這個(gè)算法就是批量梯度下降算法，為什么叫批量梯度下降？因?yàn)樽⒁獾缴鲜街忻扛乱粋€(gè)θj都需要計(jì)算所有的樣本取值，所以當(dāng)樣本數(shù)目非常大的時(shí)候(例如上萬(wàn)條甚至數(shù)十萬(wàn)條的時(shí)候)，這樣的更新非常慢，找θ也非常慢，所以就有了另外一種改進(jìn)的梯度下降算法。

3.2.2隨機(jī)梯度下降算法/增量梯度下降算法

做一個(gè)小小的改進(jìn)，用一個(gè)樣本做一個(gè)theta的更新，比如用樣本1做theta(1)的更新，用樣本2做theta(2)的更新，以此類推。這種方法的好處是速度上肯定比批量梯度下降算法快，而且樣本數(shù)據(jù)越多，體現(xiàn)應(yīng)該就越明顯。劣勢(shì)是得到的收斂點(diǎn)的值和批量梯度算法比起來(lái)也許不是最優(yōu)的值。

3.2.3梯度下降算法總結(jié)

不管是批量梯度算法還是隨機(jī)梯度下降算法，他們的共同點(diǎn)有以下：

1.時(shí)間復(fù)雜度都是O(mn)(m為樣本數(shù)目，n為特征值/影響因子數(shù)目)

2.都有梯度下降性質(zhì)：接近收斂時(shí)，每次“步子”（指實(shí)際減去的數(shù)，而不是前面定義的α，α是手動(dòng)設(shè)置參數(shù)，人為改變才會(huì)變）會(huì)越來(lái)越小。其原因是每次減去α乘以梯度，但是隨著收斂的進(jìn)行，梯度會(huì)越來(lái)越小，所以減去的值會(huì)。

3.判定收斂的方法都是如下兩種:

1)兩次迭代值改變量極小極小

2)J(θ)的值改變量極小極小

3.3正規(guī)方程組

寫(xiě)在前面：這種方法是另一種方法了，和梯度下降算法就沒(méi)啥聯(lián)系了！！！

首先回顧下前面定義的矩陣梯度運(yùn)算：

例如:

則：

定義一個(gè)矩陣，稱作設(shè)計(jì)矩陣，表示的是所有的樣本的輸入：

因?yàn)榍懊娴玫降慕Y(jié)論：

（θT*x(i)和x(i)的轉(zhuǎn)置*θ結(jié)果是一樣），可以得到

可以寫(xiě)成如下的形式：

又因?yàn)閷?duì)于任意向量，所以可以得到：

運(yùn)用下面介紹的一系列性質(zhì)：

（5）是由(2)和(3)得到的，進(jìn)行下面的推導(dǎo)

中間加tr不變的原因是因?yàn)槭且粋€(gè)實(shí)數(shù)(看成1x1矩陣)加跡等于他本身。

將上式設(shè)為0，得到正規(guī)方程組

求解得到

第二篇：面試備用：18大機(jī)器學(xué)習(xí)經(jīng)典算法總結(jié)

學(xué)習(xí)18大經(jīng)典數(shù)據(jù)挖掘算法

大概花了將近2個(gè)月的時(shí)間，自己把18大數(shù)據(jù)挖掘的經(jīng)典算法進(jìn)行了學(xué)習(xí)并且進(jìn)行了代碼實(shí)現(xiàn)，涉及到了決策分類，聚類，鏈接挖掘，關(guān)聯(lián)挖掘，模式挖掘等等方面。也算是對(duì)數(shù)據(jù)挖掘領(lǐng)域的小小入門了吧。下面就做個(gè)小小的總結(jié)，后面都是我自己相應(yīng)算法的博文鏈接，希望能夠幫助大家學(xué)習(xí)。

1.C4.5算法。C4.5算法與ID3算法一樣，都是數(shù)學(xué)分類算法，C4.5算法是ID3算法的一個(gè)改進(jìn)。ID3算法采用信息增益進(jìn)行決策判斷，而C4.5采用的是增益率。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42395865

2.CART算法。CART算法的全稱是分類回歸樹(shù)算法，他是一個(gè)二元分類，采用的是類似于熵的基尼指數(shù)作為分類決策，形成決策樹(shù)后之后還要進(jìn)行剪枝，我自己在實(shí)現(xiàn)整個(gè)算法的時(shí)候采用的是代價(jià)復(fù)雜度算法，詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42558235

3.KNN(K最近鄰)算法。給定一些已經(jīng)訓(xùn)練好的數(shù)據(jù)，輸入一個(gè)新的測(cè)試數(shù)據(jù)點(diǎn)，計(jì)算包含于此測(cè)試數(shù)據(jù)點(diǎn)的最近的點(diǎn)的分類情況，哪個(gè)分類的類型占多數(shù)，則此測(cè)試點(diǎn)的分類與此相同，所以在這里,有的時(shí)候可以復(fù)制不同的分類點(diǎn)不同的權(quán)重。近的點(diǎn)的權(quán)重大點(diǎn)，遠(yuǎn)的點(diǎn)自然就小點(diǎn)。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42613011

4.Naive Bayes(樸素貝葉斯)算法。樸素貝葉斯算法是貝葉斯算法里面一種比較簡(jiǎn)單的分類算法，用到了一個(gè)比較重要的貝葉斯定理，用一句簡(jiǎn)單的話概括就是條件概率的相互轉(zhuǎn)換推導(dǎo)。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42680161

5.SVM(支持向量機(jī))算法。支持向量機(jī)算法是一種對(duì)線性和非線性數(shù)據(jù)進(jìn)行分類的方法，非線性數(shù)據(jù)進(jìn)行分類的時(shí)候可以通過(guò)核函數(shù)轉(zhuǎn)為線性的情況再處理。其中的一個(gè)關(guān)鍵的步驟是搜索最大邊緣超平面。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42780439

6.EM(期望最大化)算法。期望最大化算法，可以拆分為2個(gè)算法，1個(gè)E-Step期望化步驟,和1個(gè)M-Step最大化步驟。他是一種算法框架，在每次計(jì)算結(jié)果之后，逼近統(tǒng)計(jì)模型參數(shù)的最大似然或最大后驗(yàn)估計(jì)。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/42921789

7.Apriori算法。Apriori算法是關(guān)聯(lián)規(guī)則挖掘算法，通過(guò)連接和剪枝運(yùn)算挖掘出頻繁項(xiàng)集，然后根據(jù)頻繁項(xiàng)集得到關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則的導(dǎo)出需要滿足最小置信度的要求。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43059211

8.FP-Tree(頻繁模式樹(shù))算法。這個(gè)算法也有被稱為FP-growth算法，這個(gè)算法克服了Apriori算法的產(chǎn)生過(guò)多侯選集的缺點(diǎn)，通過(guò)遞歸的產(chǎn)生頻度模式樹(shù)，然后對(duì)樹(shù)進(jìn)行挖掘，后面的過(guò)程與Apriori算法一致。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43234309

9.PageRank(網(wǎng)頁(yè)重要性/排名)算法。PageRank算法最早產(chǎn)生于Google,核心思想是通過(guò)網(wǎng)頁(yè)的入鏈數(shù)作為一個(gè)網(wǎng)頁(yè)好快的判定標(biāo)準(zhǔn)，如果1個(gè)網(wǎng)頁(yè)內(nèi)部包含了多個(gè)指向外部的鏈接，則PR值將會(huì)被均分，PageRank算法也會(huì)遭到Link Span攻擊。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43311943

10.HITS算法。HITS算法是另外一個(gè)鏈接算法，部分原理與PageRank算法是比較相似的，HITS算法引入了權(quán)威值和中心值的概念，HITS算法是受用戶查詢條件影響的，他一般用于小規(guī)模的數(shù)據(jù)鏈接分析，也更容易遭受到攻擊。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43311943

11.K-Means(K均值)算法。K-Means算法是聚類算法，k在在這里指的是分類的類型數(shù)，所以在開(kāi)始設(shè)定的時(shí)候非常關(guān)鍵，算法的原理是首先假定k個(gè)分類點(diǎn)，然后根據(jù)歐式距離計(jì)算分類，然后去同分類的均值作為新的聚簇中心，循環(huán)操作直到收斂。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43373159

12.BIRCH算法。BIRCH算法利用構(gòu)建CF聚類特征樹(shù)作為算法的核心，通過(guò)樹(shù)的形式，BIRCH算法掃描數(shù)據(jù)庫(kù)，在內(nèi)存中建立一棵初始的CF-樹(shù)，可以看做數(shù)據(jù)的多層壓縮。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43532111

13.AdaBoost算法。AdaBoost算法是一種提升算法，通過(guò)對(duì)數(shù)據(jù)的多次訓(xùn)練得到多個(gè)互補(bǔ)的分類器，然后組合多個(gè)分類器，構(gòu)成一個(gè)更加準(zhǔn)確的分類器。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43635115

14.GSP算法。GSP算法是序列模式挖掘算法。GSP算法也是Apriori類算法，在算法的過(guò)程中也會(huì)進(jìn)行連接和剪枝操作，不過(guò)在剪枝判斷的時(shí)候還加上了一些時(shí)間上的約束等條件。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43699083

15.PreFixSpan算法。PreFixSpan算法是另一個(gè)序列模式挖掘算法，在算法的過(guò)程中不會(huì)產(chǎn)生候選集，給定初始前綴模式，不斷的通過(guò)后綴模式中的元素轉(zhuǎn)到前綴模式中，而不斷的遞歸挖掘下去。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43766253

16.CBA(基于關(guān)聯(lián)規(guī)則分類)算法。CBA算法是一種集成挖掘算法，因?yàn)樗墙⒃陉P(guān)聯(lián)規(guī)則挖掘算法之上的，在已有的關(guān)聯(lián)規(guī)則理論前提下，做分類判斷，只是在算法的開(kāi)始時(shí)對(duì)數(shù)據(jù)做處理，變成類似于事務(wù)的形式。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43818787

17.RoughSets(粗糙集)算法。粗糙集理論是一個(gè)比較新穎的數(shù)據(jù)挖掘思想。這里使用的是用粗糙集進(jìn)行屬性約簡(jiǎn)的算法，通過(guò)上下近似集的判斷刪除無(wú)效的屬性，進(jìn)行規(guī)制的輸出。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43876001

18.gSpan算法。gSpan算法屬于圖挖掘算法領(lǐng)域。，主要用于頻繁子圖的挖掘，相較于其他的圖算法，子圖挖掘算法是他們的一個(gè)前提或基礎(chǔ)算法。gSpan算法用到了DFS編碼，和Edge五元組，最右路徑子圖擴(kuò)展等概念，算法比較的抽象和復(fù)雜。

詳細(xì)介紹鏈接：http://blog.csdn.net/androidlushangderen/article/details/43924273

第三篇：機(jī)器學(xué)習(xí)算法優(yōu)缺點(diǎn)改進(jìn)總結(jié)

Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)（2）Linear Regression Algorithm(線性回歸)（3）Local Weighted Regression(局部加權(quán)回歸)（4）k-Nearest Neighbor Algorithm for Regression(回歸k近鄰)（5）Linear Classifier(線性分類)（6）Perceptron Algorithm(線性分類)（7）Fisher Discriminant Analysis or Linear Discriminant Analysis(LDA)（8）k-NN Algorithm for Classifier(分類k近鄰)（9）Bayesian Decision Method(貝葉斯決策方法)Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多層感知器)（2）BP Algorithm

Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量機(jī))（此算法是重點(diǎn)，必考題）此處有一道必考題

Lecture 4 Introduction to Decision Rule Mining（1）Decision Tree Algorithm（2）ID3 Algorithm（3）C4.5 Algorithm（4）粗糙集……

Lecture 5 Classifier Assessment and Ensemble Methods（1）Bagging（2）Booting（3）Adaboosting Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms（2）FP-tree Algorithms Lecture 7 Introduction to Custering Analysis（1）k-means Algorithms（2）fuzzy c-means Algorithms（3）k-mode Algorithms（4）DBSCAN Algorithms Lecture 8 Basics of Feature Selection（1）Relief Algorithms（2）ReliefF Algorithms（3）mRMR Algorithms最小冗余最大相關(guān)算法（4）attribute reduction Algorithms

比較了幾種分類算法性質(zhì)。（以下兩個(gè)表格來(lái)自兩篇該領(lǐng)域經(jīng)典論文）

Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)①算法思想：

EM算法又稱期望最大化算法，是對(duì)參數(shù)極大似然估計(jì)的一種迭代優(yōu)化策略，它是一種可以從非完整的數(shù)據(jù)集中對(duì)參數(shù)進(jìn)行極大似然估計(jì)的算法,應(yīng)用于缺損數(shù)據(jù)，截尾數(shù)據(jù)，帶有噪聲的非完整數(shù)據(jù)。

最大期望算法經(jīng)過(guò)兩個(gè)步驟交替進(jìn)行計(jì)算：

第一步計(jì)算期望（E）：也就是將隱藏的變量對(duì)象能夠觀察到的一樣包含在內(nèi)，從而計(jì)算最大似然的期望值；

另外一步是最大化（M），也就是最大化在E步上找到的最大似然期望值，從而計(jì)算參數(shù)的似然估計(jì)。M步上找到的參數(shù)然后用于另一個(gè)E步計(jì)算。

重復(fù)上面2步直至收斂。

②優(yōu)點(diǎn)：1）Ｍ步僅涉及完全數(shù)據(jù)極大似然，通常計(jì)算比較簡(jiǎn)單

2）收斂是穩(wěn)定的，因?yàn)槊看蔚乃迫缓瘮?shù)是不斷增加的。

③缺點(diǎn)：1）表現(xiàn)在對(duì)缺失數(shù)據(jù)較多或是多維高斯分布的情形下，計(jì)算量大，收斂速度較慢。

2）對(duì)于某些特殊的模型，要計(jì)算算法中的M步，即完成對(duì)似然函數(shù)的估計(jì)是比較困難的。

3）在某些情況下，要獲得EM算法中E步的期望顯式是非常困難的。

4）EM算法的收斂速度，非常依賴初始值的設(shè)置，設(shè)置不當(dāng)，計(jì)算代價(jià)相當(dāng)大。

5）EM算法中的M-Step依然是采用求導(dǎo)函數(shù)的方法,所以它找到的是極值點(diǎn),即局

部最優(yōu)解,而不一定是全局最優(yōu)解。④改進(jìn)：針對(duì)1）改進(jìn)：擴(kuò)大參數(shù)空間來(lái)加快收斂

針對(duì)2）改進(jìn)：ECM算法，該算法通過(guò)在Ｍ步構(gòu)建計(jì)算比較簡(jiǎn)單的小循環(huán)對(duì)EM

算法進(jìn)行了改進(jìn)，從而使期望函數(shù)極大化更加容易和有效，從而解決這一問(wèn)題。

針對(duì)3）改進(jìn)：MCEM算法，將E步積分求期望用蒙特卡洛模擬方法來(lái)實(shí)現(xiàn)，使

得E步求期望更容易實(shí)現(xiàn)。

針對(duì)4）初始值的獲取可以通過(guò)k-means算法，層次聚類算法或是數(shù)據(jù)數(shù)據(jù)進(jìn)行隨

機(jī)分割，然后重復(fù)EM效果進(jìn)行初始點(diǎn)選擇。

針對(duì)5）結(jié)合遺傳算法的全局搜索能力，擴(kuò)大EM算法的搜索空間，有效降低EM

算法對(duì)初始值的依賴度，改善局部最優(yōu)值的缺陷。

（2）Linear Regression Algorithm(線性回歸)①算法思想：

線性回歸(Linear Regression)是利用稱為線性回歸方程的最小平方函數(shù)對(duì)一個(gè)或多個(gè)自變量和因變量之間關(guān)系進(jìn)行建模的一種回歸分析。這種函數(shù)是一個(gè)或多個(gè)稱為回歸系數(shù)的模型參數(shù)的線性組合。只有一個(gè)自變量的情況稱為簡(jiǎn)單回歸,大于一個(gè)自變量情況的叫做多元回歸。

回歸模型：

i

其中 ?和C是未知參數(shù)，對(duì)于每個(gè)訓(xùn)練樣本(xi，yi)可得到h(xi)，用來(lái)預(yù)測(cè)真實(shí)值y。損失函數(shù)：

即誤差值的平方。

1：對(duì)于訓(xùn)練集，求取θ，使得損失函數(shù)最小。（使用最小二乘法，梯度下降法）2：對(duì)于新輸入x，其預(yù)測(cè)輸出為θTx ②優(yōu)點(diǎn)：結(jié)果易于理解，實(shí)現(xiàn)簡(jiǎn)單，計(jì)算簡(jiǎn)單

③缺點(diǎn)：1）對(duì)于非線性的數(shù)據(jù)擬合效果不好（原因：因?yàn)榫€性回歸將數(shù)據(jù)視為線性的，可能出現(xiàn)欠擬合現(xiàn)象，導(dǎo)致結(jié)果不能取得最好的預(yù)測(cè)效果）

2）如果訓(xùn)練數(shù)據(jù)如果有些數(shù)據(jù)偏差特別大，這回造成最后訓(xùn)練的模型可能對(duì)整體

具備很好的準(zhǔn)確性

④改進(jìn)：針對(duì)2）改進(jìn) ：局部加權(quán)回歸

數(shù)據(jù)都不（3）Local Weighted Regression(局部加權(quán)回歸)①算法思想：

給每個(gè)待預(yù)測(cè)點(diǎn)周圍的點(diǎn)賦予一定的權(quán)重,越近的點(diǎn)權(quán)重越高,以此來(lái)選出該預(yù)測(cè)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)子集,然后在此數(shù)據(jù)子集上基于最小均方差進(jìn)行普通的回歸.局部加權(quán)回歸實(shí)質(zhì)上是對(duì)于需要預(yù)測(cè)的點(diǎn)，只是根據(jù)其附近的點(diǎn)進(jìn)行訓(xùn)練，其他的沒(méi)有改變。

對(duì)于局部線性加權(quán)算法：

1：對(duì)于輸入x，找到訓(xùn)練集中與x鄰域的訓(xùn)練樣本

2：對(duì)于其鄰域的訓(xùn)練樣本，求取θ，使得其

∈x的鄰域）最小。其中w(i)為權(quán)重值。

3.預(yù)測(cè)輸出為θTx

4.對(duì)于新輸入，重復(fù)1-3過(guò)程。

其中

τ 為帶寬(bandwidth)常量，距離輸入越遠(yuǎn)，權(quán)重越小，反之越大。

②優(yōu)點(diǎn)：1）局部加權(quán)回歸還是對(duì)訓(xùn)練數(shù)據(jù)擬合的比較好

2）不太依賴特征的選擇，而且只需要用線性模型就能夠訓(xùn)練出不錯(cuò)的擬合模型、③缺點(diǎn)：1）計(jì)算量較大。（因?yàn)榫植考訖?quán)回歸的損失數(shù)隨著預(yù)測(cè)值的不同而不同，這樣θ

就無(wú)法事先確定，每次預(yù)測(cè)時(shí)都需要掃描所有的數(shù)據(jù)并重新計(jì)算θ）

2）局部加權(quán)回歸容易出現(xiàn)過(guò)擬合現(xiàn)象，過(guò)擬合現(xiàn)象很明顯

3）關(guān)注局部的訓(xùn)練數(shù)據(jù)，忽略了全局?jǐn)?shù)據(jù)，如果預(yù)測(cè)點(diǎn)在出現(xiàn)偏差的訓(xùn)練數(shù)據(jù)附

近，那么預(yù)測(cè)值會(huì)偏差很大。

④改進(jìn)：

（4）k-Nearest Neighbor Algorithm for Regression(回歸k近鄰)①算法思想：

通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。

如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。

KNN算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成反比。②優(yōu)點(diǎn)：

1）簡(jiǎn)單、有效。

2）重新訓(xùn)練的代價(jià)較低（類別體系的變化和訓(xùn)練集的變化，在Web環(huán)境和電子商務(wù)應(yīng)用中是很常見(jiàn)的）。3）計(jì)算時(shí)間和空間線性于訓(xùn)練集的規(guī)模（在一些場(chǎng)合不算太大）。

4）由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。

5）該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。③缺點(diǎn)：

（1）KNN在對(duì)屬性較多的訓(xùn)練樣本進(jìn)行分類時(shí)，由于計(jì)算量大而使其效率大大降低，效果不是很理想。

（2）當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。

（3）對(duì)數(shù)據(jù)的局部結(jié)構(gòu)比較敏感。如果查詢點(diǎn)是位于訓(xùn)練集較密集的區(qū)域，那預(yù)測(cè)相對(duì)比其他稀疏集來(lái)說(shuō)更準(zhǔn)確。（4）對(duì)k值敏感。

（5）維數(shù)災(zāi)難：臨近距離可能被不相干屬性主導(dǎo)（因此特征選擇問(wèn)題）④改進(jìn)：

（1）分類效率：事先對(duì)樣本屬性進(jìn)行約簡(jiǎn)，刪除對(duì)分類結(jié)果影響較小的屬性，快速的得出待分類樣本的類別。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。（2）分類效果：采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)，Han等人于2002年嘗試?yán)秘澬姆ǎ槍?duì)文件分類實(shí)做可調(diào)整權(quán)重的k最近鄰居法WAkNN(weighted adjusted k nearest neighbor)，以促進(jìn)分類效果；而Li等人于2004年提出由于不同分類的文件本身有數(shù)量上有差異，因此也應(yīng)該依照訓(xùn)練集合中各種分類的文件數(shù)量，選取不同數(shù)目的最近鄰居，來(lái)參與分類。

（3）該算法在分類時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。該算法只計(jì)算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果。可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)。（4）K 值的選擇會(huì)對(duì)算法的結(jié)果產(chǎn)生重大影響。K值較小意味著只有與輸入實(shí)例較近的訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用，但容易發(fā)生過(guò)擬合；如果 K 值較大，優(yōu)點(diǎn)是可以減少學(xué)習(xí)的估計(jì)誤差，但缺點(diǎn)是學(xué)習(xí)的近似誤差增大，這時(shí)與輸入實(shí)例較遠(yuǎn)的訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用，是預(yù)測(cè)發(fā)生錯(cuò)誤。在實(shí)際應(yīng)用中，K 值一般選擇一個(gè)較小的數(shù)值，通常采用交叉驗(yàn)證的方法來(lái)選擇最優(yōu)的 K 值。隨著訓(xùn)練實(shí)例數(shù)目趨向于無(wú)窮和 K=1 時(shí)，誤差率不會(huì)超過(guò)貝葉斯誤差率的2倍，如果K也趨向于無(wú)窮，則誤差率趨向于貝葉斯誤差率。

（5）該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

（5）Linear Classifier(線性分類器)①算法思想：線性分類器使用線性判別函數(shù)，實(shí)現(xiàn)線性判別函數(shù)分類的方法有感知器算法、LMSE分類算法和Fisher分類。

在分類問(wèn)題中，因變量Y可以看做是數(shù)據(jù)的label，屬于分類變量。所謂分類問(wèn)題，就是能夠在數(shù)據(jù)的自變量X空間內(nèi)找到一些決策邊界，把label不同的數(shù)據(jù)分開(kāi)，如果某種方法所找出的這些決策邊界在自變量X空間內(nèi)是線性的，這時(shí)就說(shuō)這種方法是一種線性分類器。

C1和C2是要區(qū)分的兩個(gè)類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開(kāi)。

線性分類器在數(shù)學(xué)上被理解為線性判別函數(shù)(Linear Discriminant Functions)，在幾何上可以理解為決策超平面(Decision Hyperplanes)。②優(yōu)點(diǎn)：算法簡(jiǎn)單

③缺點(diǎn)：只能處理線性問(wèn)題

④改進(jìn)：要處理其他非線性問(wèn)題，可以向高維轉(zhuǎn)化，例如用SVM方法。線性分類器是分類方法，不是具體算法。

（6）Perceptron Algorithm(感知器算法)①算法思想：

感知機(jī)（Perceptron）是二類分類的線性分類模型，其輸入為實(shí)例的特征向量，輸出為實(shí)例的類別，取+1和-1二值。感知機(jī)對(duì)應(yīng)于輸入空間（特征空間）中將實(shí)例劃分為正負(fù)兩類的分離超平面，屬于判別模型。②優(yōu)點(diǎn)：

（1）感知機(jī)學(xué)習(xí)算法是基于隨機(jī)梯度下降法的對(duì)損失函數(shù)的最優(yōu)化算法，有原始形式和對(duì)偶形式。算法簡(jiǎn)單且易于實(shí)現(xiàn)；

（2）它提出了自組織自學(xué)習(xí)的思想。對(duì)能夠解決的問(wèn)題有一個(gè)收斂的算法，并從數(shù)學(xué)上給出了嚴(yán)格的證明。（3）當(dāng)樣本線性可分情況下，學(xué)習(xí)率 合適時(shí)，算法具有收斂性。③缺點(diǎn)：

（1）即感知機(jī)無(wú)法找到一個(gè)線性模型對(duì)異或問(wèn)題進(jìn)行劃分。

（2）其實(shí)不光感知機(jī)無(wú)法處理異或問(wèn)題，所有的線性分類模型都無(wú)法處理異或分類問(wèn)題。（3）收斂速度慢；當(dāng)樣本線性不可分情況下，算法不收斂，且無(wú)法判斷樣本是否線性可分。

④改進(jìn)：?jiǎn)蝹€(gè)感知器雖然無(wú)法解決異或問(wèn)題，但卻可以通過(guò)將多個(gè)感知器組合，實(shí)現(xiàn)復(fù)雜空間的分割。（7）線性判別分析（LDA，Linear Discriminant Analysis）①基礎(chǔ)概念

（1）判別分析概念

根據(jù)已知對(duì)象的某些觀測(cè)指標(biāo)和所屬類別來(lái)判斷未知對(duì)象所屬類別的統(tǒng)計(jì)方法。利用已知類別的樣本信息求判別函數(shù)，根據(jù)判別函數(shù)對(duì)未知樣本所屬類別進(jìn)行判別。（2）判別分析分類

按判別組數(shù)來(lái)分，有兩組判別分析和多組判別分析

按數(shù)學(xué)模型（函數(shù)形式）來(lái)分，有線性判別分析和非線性判別分析

按判別方法來(lái)分，有Fisher判別分析、Bayes判別分析和距離判別（K-NN）注:線性判別分析就是一般化的Fisher判別分析（3）Fisher判別分析與Bayes判別分析優(yōu)缺點(diǎn)比較

Fisher判別方法對(duì)總體分布沒(méi)有特殊要求，但是Fisher判別法未考慮各總體出現(xiàn)概率的大小，不能給出后驗(yàn)概率以及錯(cuò)判造成的損失。

Bayes判別法可以給出后驗(yàn)概率以及錯(cuò)判造成的損失。但是要求即各種變量必須服從多元正態(tài)分布、各組協(xié)方差矩陣必須相等、各組變量均值均有顯著性差異。②LDA缺點(diǎn)

LDA有兩個(gè)突出缺點(diǎn):（1）處理高維圖像時(shí)容易產(chǎn)生“小樣本問(wèn)題”, 即樣本維數(shù)大大超過(guò)訓(xùn)練圖像個(gè)數(shù)的問(wèn)題；（2）由此引發(fā)的邊緣類主導(dǎo)特征空間分解的問(wèn)題。（3）LDA的其余缺點(diǎn)（限制）：

LDA至多可生成C-1維子空間。

LDA不適合對(duì)非高斯分布的樣本進(jìn)行降維。

LDA在樣本分類信息依賴方差而不是均值時(shí)，效果不好。

LDA可能過(guò)度擬合數(shù)據(jù)。

③針對(duì)“小樣本問(wèn)題”的改進(jìn)方法

可以利用本文設(shè)計(jì)的改進(jìn)PCA 算法與LDA 算法相結(jié)合來(lái)解決小樣本問(wèn)題，即將結(jié)合了基于標(biāo)準(zhǔn)差和局部均值的圖像增強(qiáng)處理算法的PCA 算法與LDA 算法相結(jié)合。具體的應(yīng)用過(guò)程即為: 先采用改進(jìn)的PCA 算法對(duì)樣本進(jìn)行降維處理，以便確保樣本的類內(nèi)離散度矩陣為非奇異的，利用改進(jìn)的PCA 算法將原始樣本圖像往一個(gè)特征子空間中投影，從而使得樣本的類內(nèi)離散度矩陣是非奇異的。再利用LDA 算法在次特征子空間中求得最優(yōu)變換。

LDA與PCA的比較

兩者都是為了在對(duì)原始數(shù)據(jù)降維之后進(jìn)行分類。PCA（Principal Component Analysis，主成分分析）是無(wú)監(jiān)督的方式，它沒(méi)有分類標(biāo)簽，降維之后需要采用K-Means或自組織映射網(wǎng)絡(luò)等無(wú)監(jiān)督的算法進(jìn)行分類。LDA是有監(jiān)督的方式，它先對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行降維，然后找出一個(gè)線性判別函數(shù)。（8）k-NN(k-Nearest Neighbor for classifier,分類最近鄰估計(jì))①算法思想：（1）k-NN介紹

如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。（2）k-NN概念

k-NN算法通常以“歐氏距離(Euclidean Distance)”為其分類模型, 歐氏距離公式的定義如下: 設(shè)在n 維空間中有兩個(gè)點(diǎn)X =(x1,x2,?,xn)和Y =(y1,y2,?,yn), 它們之間的歐氏距離定義為:

其中, n是維數(shù), Xi和Yi分別是X和Y的第k個(gè)屬性值。②優(yōu)點(diǎn)

（1）簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無(wú)需估計(jì)參數(shù)，無(wú)需訓(xùn)練

（2）適合對(duì)稀有事件進(jìn)行分類（例如當(dāng)流失率很低時(shí)，比如低于0.5%，構(gòu)造流失預(yù)測(cè)模型）

（3）特別適合于多分類問(wèn)題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)，例如根據(jù)基因特征來(lái)判斷其功能分類，kNN比SVM的表現(xiàn)要好.③缺點(diǎn)

（1）計(jì)算量大，由于要逐個(gè)計(jì)算到每條記錄的歐氏距離, 對(duì)于海量數(shù)據(jù), 該算法時(shí)間效率非常低。它在對(duì)每一個(gè)查詢實(shí)例(Query Instance)進(jìn)行分類時(shí), 都需要搜索整個(gè)訓(xùn)練集來(lái)尋找最近鄰, 所以它的運(yùn)算開(kāi)銷巨大, 時(shí)間代價(jià)高昂, 這導(dǎo)致了它的運(yùn)行速度非常低下。

（2）可解釋性較差，無(wú)法給出決策樹(shù)那樣的規(guī)則。

（3）當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。該算法只計(jì)算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無(wú)論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果。（4）由于所有屬性均等地參與計(jì)算, 沒(méi)有突出屬性的重要程度, 分類結(jié)果易受單個(gè)屬性的影響;④改進(jìn)

缺點(diǎn)1：目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。缺點(diǎn)4：利用信息增益來(lái)衡量屬性的重要程度(即屬性權(quán)重系數(shù)),將屬性劃分為關(guān)鍵屬性、次要屬性及無(wú)關(guān)屬性, 解決屬性均等用力的問(wèn)題;缺點(diǎn)3，可考慮從K值設(shè)定回答

1、k值設(shè)定為多大？

k太小，分類結(jié)果易受噪聲點(diǎn)影響；k太大，近鄰中又可能包含太多的其它類別的點(diǎn)。（對(duì)距離加權(quán)，可以降低k值設(shè)定的影響）

k值通常是采用交叉檢驗(yàn)來(lái)確定（以k=1為基準(zhǔn)）經(jīng)驗(yàn)規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根

補(bǔ)充去年相關(guān)習(xí)題：

請(qǐng)闡述 kNN近鄰分類算法的基本思想，并分析它的主要優(yōu)缺點(diǎn)。關(guān)于 k 的取值，你有什么合理的建議（至少 1 條）。優(yōu)點(diǎn)

(1)簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無(wú)需估計(jì)參數(shù)，無(wú)需訓(xùn)練

(2)適合對(duì)稀有事件進(jìn)行分類（例如當(dāng)流失率很低時(shí)，比如低于0.5%，構(gòu)造流失預(yù)測(cè)模型）(3)特別適合于多分類問(wèn)題，例如根據(jù)基因特征來(lái)判斷其功能分類，kNN比SVM的表現(xiàn)要好 缺點(diǎn)

(1)懶惰算法，對(duì)測(cè)試樣本分類時(shí)的計(jì)算量大，內(nèi)存開(kāi)銷大，評(píng)分慢

(2)當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有 可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)；

(3)可解釋性較差，無(wú)法給出決策樹(shù)那樣的規(guī)則。k值設(shè)定

k值選擇過(guò)小，得到的近鄰數(shù)過(guò)少，會(huì)降低分類精度，同時(shí)也會(huì)放大噪聲數(shù)據(jù)的干擾；而如果k值選擇過(guò)大，并且待分類樣本屬于訓(xùn)練集中包含數(shù)據(jù)數(shù)較少的類，那么在選擇k個(gè)近鄰的時(shí)候，實(shí)際上并不相似的數(shù)據(jù)亦被包含進(jìn)來(lái)，造成噪聲增加而導(dǎo)致分類效果的降低。

k太小，分類結(jié)果易受噪聲點(diǎn)影響；k太大，近鄰中又可能包含太多的其它類別的點(diǎn)。（對(duì)距離加權(quán)，可以降低k值設(shè)定的影響）K值設(shè)定的建議

k值通常是采用交叉檢驗(yàn)來(lái)確定（以k=1為基準(zhǔn)）k一般低于訓(xùn)練樣本數(shù)的平方根

（9）貝葉斯決策方法（Bayesian Decision Method）①貝葉斯決策概念

貝葉斯決策（Bayesian Decision Theory）就是在不完全情報(bào)下，對(duì)部分未知的狀態(tài)用主觀概率估計(jì)，然后用貝葉斯公式對(duì)發(fā)生概率進(jìn)行修正，最后再利用期望值和修正概率做出最優(yōu)決策。貝葉斯決策屬于風(fēng)險(xiǎn)型決策，決策者雖不能控制客觀因素的變化，但卻掌握其變化的可能狀況及各狀況的分布概率，并利用期望值即未來(lái)可能出現(xiàn)的平均狀況作為決策準(zhǔn)則。

貝葉斯決策理論方法是統(tǒng)計(jì)模型決策中的一個(gè)基本方法，其基本思想是：

已知類條件概率密度參數(shù)表達(dá)式和先驗(yàn)概率。

利用貝葉斯公式轉(zhuǎn)換成后驗(yàn)概率。

根據(jù)后驗(yàn)概率大小進(jìn)行決策分類。②貝葉斯決策方法優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：

貝葉斯決策能對(duì)信息的價(jià)值或是否需要采集新的信息做出科學(xué)的判斷

它能對(duì)調(diào)查結(jié)果的可能性加以數(shù)量化的評(píng)價(jià),而不是像一般的決策方法那樣,對(duì)調(diào)查結(jié)果或者是完全相信,或者是 完全不相信

如果說(shuō)任何調(diào)查結(jié)果都不可能完全準(zhǔn)確,先驗(yàn)知識(shí)或主觀概率也不是完全可以相信的,那么貝葉斯決策則巧妙地將這兩種信息有機(jī)地結(jié)合起來(lái)了

它可以在決策過(guò)程中根據(jù)具體情況下不斷地使用,使決策逐步完善和更加科學(xué) 缺點(diǎn)：

它需要的數(shù)據(jù)多,分析計(jì)算比較復(fù)雜,特別在解決復(fù)雜問(wèn)題時(shí),這個(gè)矛盾就更為突出

有些數(shù)據(jù)必須使用主觀概率,有些人不太相信,這也妨礙了貝葉斯決策方法的推廣使用 ③貝葉斯決策改進(jìn)方法

將決策問(wèn)題轉(zhuǎn)化成收益矩陣,通過(guò)對(duì)收益矩陣的分析,得出各行動(dòng)方案的期望值,按照一定的準(zhǔn)則選出最優(yōu)方案。

以各狀況下最大收益值或效用值為基礎(chǔ),求出MaxE(x),以此作為完全確定情況下的收益值,用該值減去最優(yōu)方案的期望值得出完全信息價(jià)值(EVPⅠ),根據(jù)完全信息期望值判斷是否需要補(bǔ)充信息量。

在第2步得到肯定回答后,首先在預(yù)先后驗(yàn)分析中從理論上把各種可能的抽樣方案及結(jié)果列舉出來(lái),計(jì)算各種抽樣方案的抽樣信息期望值EVSI=EVPI-R(n),其中R(n)為抽樣風(fēng)險(xiǎn),其大小是樣本大小的函數(shù)。

以EVSI-C(其中C為抽樣成本)作為標(biāo)準(zhǔn)選取最大值對(duì)應(yīng)的抽樣方案為最優(yōu)抽樣方案。

按照理論上得出的最優(yōu)抽樣方案進(jìn)行抽樣,然后,根據(jù)貝葉斯理論公式推導(dǎo)出后驗(yàn)概率分布的數(shù)字描述,最后,以此為依據(jù)按照貝葉斯決策準(zhǔn)則選出最優(yōu)方案。補(bǔ)充樸素貝葉斯

樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。

同時(shí)，NBC模型所需估計(jì)的參數(shù)很少，對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡(jiǎn)單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實(shí)際上并非總是如此，這是因?yàn)镹BC模型假設(shè)屬性之間相互獨(dú)立，這個(gè)假設(shè)在實(shí)際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來(lái)了一定影響。在屬性個(gè)數(shù)比較多或者屬性之間相關(guān)性較大時(shí)，NBC模型的分類效率比不上決策樹(shù)模型。而在屬性相關(guān)性較小時(shí)，NBC模型的性能最為良好。

補(bǔ)充樸素貝葉斯優(yōu)點(diǎn)：

1）樸素貝葉斯算法是基于貝葉斯理論，邏輯清楚明了

2）本算法進(jìn)行分類是，時(shí)間快，在內(nèi)存上需要的也不大

3）本算法魯棒性高，即使數(shù)據(jù)包含的噪聲點(diǎn)，無(wú)關(guān)屬性和缺失值的屬性，分類性能不好又 太大的變化，健壯性好

補(bǔ)充樸素貝葉斯算法缺點(diǎn)：

1）樸素貝葉斯算法要求樣本各屬性直接是獨(dú)立的，而真實(shí)的數(shù)據(jù)符合這個(gè)條件很少。

2）當(dāng)樣本數(shù)據(jù)少時(shí)，分類器可能會(huì)無(wú)法正確分類

Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多層感知器)①算法思想

多層感知器（Multilayer Perceptron,縮寫(xiě)MLP）是一種前向結(jié)構(gòu)的人工神經(jīng)網(wǎng)絡(luò)。MLP算法一般包括三層，分別是一個(gè)輸入層，一個(gè)輸出層和一個(gè)或多個(gè)隱藏層的神經(jīng)網(wǎng)絡(luò)組成。一個(gè)“神經(jīng)元”的輸出就可以是另一個(gè)“神經(jīng)元”的輸入。MLP可以被看作是一個(gè)有向圖，由多個(gè)的節(jié)點(diǎn)層所組成，每一層都全連接到下一層。除了輸入節(jié)點(diǎn)，每個(gè)神經(jīng)元都有幾個(gè)輸入和輸出神經(jīng)元，每個(gè)神經(jīng)元通過(guò)輸入權(quán)重加上偏置計(jì)算輸出值，并選擇一種激活函數(shù)進(jìn)行轉(zhuǎn)換。一種被稱為反向傳播算法(BP)的監(jiān)督學(xué)習(xí)方法常被用來(lái)訓(xùn)練MLP。MLP是感知器的推廣，克服了感知器不能對(duì)線性不可分?jǐn)?shù)據(jù)進(jìn)行識(shí)別的弱點(diǎn)。

激活函數(shù)

若每個(gè)神經(jīng)元的激活函數(shù)都是線性函數(shù)，那么，任意層數(shù)的MLP都可被約簡(jiǎn)成一個(gè)等價(jià)的單層感知器。實(shí)際上，MLP本身可以使用任何形式的激活函數(shù)，但為了使用反向傳播算法進(jìn)行有效學(xué)習(xí)，激活函數(shù)必須限制為可微函數(shù)。由于具有良好可微性，很多乙形函數(shù)，尤其是雙曲正切函數(shù)（Hyperbolic tangent）及邏輯乙形函數(shù)（logistic sigmoid function），被采用為激活函數(shù)。激活函數(shù)常見(jiàn)的有三種，分別是恒等函數(shù)，Sigmoid函數(shù)和高斯函數(shù)。

②優(yōu)點(diǎn)：

（1）高度的并行性

人工神經(jīng)網(wǎng)絡(luò)是由許多相同的簡(jiǎn)單處理單元并聯(lián)組合而成，雖然每個(gè)單元的功能簡(jiǎn)單，但大量簡(jiǎn)單單元的并行活動(dòng)，使其對(duì)信息的處理能力與效果驚人。（2）高度的非線性全局作用

神經(jīng)網(wǎng)絡(luò)系統(tǒng)是由大量簡(jiǎn)單神經(jīng)元構(gòu)成的，每個(gè)神經(jīng)元接受大量其他神經(jīng)元的輸入，通過(guò)非線性輸入、輸出關(guān)系，產(chǎn)生輸出影響其它神經(jīng)元。網(wǎng)絡(luò)就是這樣互相制約相互影響，實(shí)現(xiàn)從輸入狀態(tài)空間到輸出狀態(tài)空間非線性映射的。網(wǎng)絡(luò)的演化遵從全局性作用原則，從輸入狀態(tài)演化到終態(tài)而輸出。從全局觀點(diǎn)來(lái)看，網(wǎng)絡(luò)整體性能不是網(wǎng)絡(luò)局部性能的簡(jiǎn)單迭加，而表現(xiàn)某種集體性行為；而電腦遵從串行式局域性操作原則，每一步計(jì)算與上一步計(jì)算緊密相關(guān)，并對(duì)下一步產(chǎn)生影響，問(wèn)題是通過(guò)算法逐步進(jìn)行處理的。（3）良好的容錯(cuò)性與聯(lián)想記憶功能

人工神經(jīng)網(wǎng)絡(luò)通過(guò)自身的網(wǎng)絡(luò)結(jié)構(gòu)能夠?qū)崿F(xiàn)對(duì)信息的記憶，而所記憶的信息是存儲(chǔ)在神經(jīng)元之間的權(quán)值中。從單個(gè)權(quán)值中看不出所儲(chǔ)存的信息內(nèi)容，因而是分布式的存儲(chǔ)方式。這使得網(wǎng)絡(luò)具有良好的容錯(cuò)性，并能進(jìn)行聚類分析、特征提取、缺損模式復(fù)原等模式信息處理工作。

（4）十分強(qiáng)的自適應(yīng)、自學(xué)習(xí)功能人工神經(jīng)網(wǎng)絡(luò)可以通過(guò)訓(xùn)練和學(xué)習(xí)來(lái)獲得網(wǎng)絡(luò)的權(quán)值與結(jié)構(gòu)，呈現(xiàn)出很強(qiáng)的自學(xué)習(xí)能力和對(duì)環(huán)境的自適應(yīng)能力。③缺點(diǎn)

（1）網(wǎng)絡(luò)的隱含節(jié)點(diǎn)個(gè)數(shù)選取問(wèn)題至今仍是一個(gè) 世界難題；

（2）停止閾值、學(xué)習(xí)率、動(dòng)量常數(shù)需要采用”trial-and-error”法，極其耗時(shí)（動(dòng)手實(shí)驗(yàn)）；（3）學(xué)習(xí)速度慢；

（4）容易陷入局部極值，學(xué)習(xí)不夠充分。④改進(jìn)

（1）改進(jìn)BP算法（見(jiàn)bp）（2）權(quán)值初始化

在初始化權(quán)值的時(shí)候，我們一般需要它們?cè)?附近，要足夠小（在激活函數(shù)的近似線性區(qū)域可以獲得最大的梯度）。另一個(gè)特性，尤其對(duì)深度網(wǎng)絡(luò)而言，是可以減小層與層之間的激活函數(shù)的方差和反向傳導(dǎo)梯度的方差。這就可以讓信息更好的向下和向上的傳導(dǎo)，減少層間差異。（3）學(xué)習(xí)率

隨著時(shí)間的推移減小學(xué)習(xí)速率有時(shí)候也是一個(gè)好主意。一個(gè)簡(jiǎn)單的方法是使用這個(gè)公式：u/(1+d*t)，u是初始速率（可以使用上面講的網(wǎng)格搜索選擇），d是減小常量，用以控制學(xué)習(xí)速率，可以設(shè)為0.001或者更小，t是迭代次數(shù)或者時(shí)間。可以基于分類錯(cuò)誤率自適應(yīng)的選擇學(xué)習(xí)率。（4）隱藏節(jié)點(diǎn)數(shù) 這個(gè)參數(shù)是非常基于數(shù)據(jù)集的。模糊的來(lái)說(shuō)就是，輸入分布越復(fù)雜，去模擬它的網(wǎng)絡(luò)就需要更大的容量，那么隱藏單元的數(shù)目就要更大。（5）正則化參數(shù)

典型的方法是使用L1/L2正則化。

L2正則化就是在代價(jià)函數(shù)后面再加上一個(gè)正則化項(xiàng)：

C0代表原始的代價(jià)函數(shù)，后面那一項(xiàng)就是L2正則化項(xiàng)，它是這樣來(lái)的：所有參數(shù)w的平方的和，除以訓(xùn)練集的樣本大小n。λ就是正則項(xiàng)系數(shù)，權(quán)衡正則項(xiàng)與C0項(xiàng)的比重。另外還有一個(gè)系數(shù)1/2，1/2經(jīng)常會(huì)看到，主要是為了后面求導(dǎo)的結(jié)果方便，后面那一項(xiàng)求導(dǎo)會(huì)產(chǎn)生一個(gè)2，與1/2相乘剛好湊整。

過(guò)擬合，就是擬合函數(shù)需要顧忌每一個(gè)點(diǎn)，最終形成的擬合函數(shù)波動(dòng)很大。在某些很小的區(qū)間里，函數(shù)值的變化很劇烈。這就意味著函數(shù)在某些小區(qū)間里的導(dǎo)數(shù)值（絕對(duì)值）非常大，由于自變量值可大可小，所以只有系數(shù)足夠大，才能保證導(dǎo)數(shù)值很大。而正則化是通過(guò)約束參數(shù)的范數(shù)使其不要太大，所以可以在一定程度上減少過(guò)擬合情況。

L1正則化項(xiàng)就是在原始的代價(jià)函數(shù)后面加上一個(gè)正則化項(xiàng)，即所有權(quán)重w的絕對(duì)值的和，乘以λ/n（這里不像L2正則化項(xiàng)那樣）：

比原始的更新規(guī)則多出了η * λ * sgn(w)/n這一項(xiàng)。當(dāng)w為正時(shí)，更新后的w變小。當(dāng)w為負(fù)時(shí)，更新后的w變大——因此它的效果就是讓w往0靠，使網(wǎng)絡(luò)中的權(quán)重盡可能為0，也就相當(dāng)于減小了網(wǎng)絡(luò)復(fù)雜度，防止過(guò)擬合。

（2）BP Algorithm ①算法思想

BP算法是一種有監(jiān)督式的學(xué)習(xí)算法，其主要思想是：輸入學(xué)習(xí)樣本，使用反向傳播算法對(duì)網(wǎng)絡(luò)的權(quán)值和偏差進(jìn)行反復(fù)的調(diào)整訓(xùn)練，使輸出的向量與期望向量盡可能地接近，當(dāng)網(wǎng)絡(luò)輸出層的誤差平方和小于指定的誤差時(shí)訓(xùn)練完成，保存網(wǎng)絡(luò)的權(quán)值和偏差。②優(yōu)點(diǎn)：

（1）網(wǎng)絡(luò)實(shí)質(zhì)上實(shí)現(xiàn)了一個(gè)從輸入到輸出的映射功能，而數(shù)學(xué)理論已證明它具有實(shí)現(xiàn)任何復(fù)雜非線性映射的功能。這使得它特別適合于求解內(nèi)部機(jī)制復(fù)雜的問(wèn)題；

（2）網(wǎng)絡(luò)能通過(guò)學(xué)習(xí)帶正確答案的實(shí)例集自動(dòng)提取“合理的”求解規(guī)則，即具有自學(xué)習(xí)能力；（3）網(wǎng)絡(luò)具有一定的推廣、概括能力。③缺點(diǎn)

主要包括以下幾個(gè)方面的問(wèn)題。

（1）由于學(xué)習(xí)速率是固定的，因此網(wǎng)絡(luò)的收斂速度慢，需要較長(zhǎng)的訓(xùn)練時(shí)間。對(duì)于一些復(fù)雜問(wèn)題，BP算法需要的訓(xùn)練時(shí)間可能非常長(zhǎng)，這主要是由于學(xué)習(xí)速率太小造成的。

（2）BP算法可以使權(quán)值收斂到某個(gè)值，但并不保證其為誤差平面的全局最小值，這是因?yàn)椴捎锰荻认陆捣赡墚a(chǎn)生一個(gè)局部最小值

（3）網(wǎng)絡(luò)隱含層的層數(shù)和單元數(shù)的選擇尚無(wú)理論上的指導(dǎo)，一般是根據(jù)經(jīng)驗(yàn)或者通過(guò)反復(fù)實(shí)驗(yàn)確定。因此，網(wǎng)絡(luò)往往存在很大的冗余性，在一定程度上也增加了網(wǎng)絡(luò)學(xué)習(xí)的負(fù)擔(dān)。

（4）網(wǎng)絡(luò)的學(xué)習(xí)和記憶具有不穩(wěn)定性。也就是說(shuō)，如果增加了學(xué)習(xí)樣本，訓(xùn)練好的網(wǎng)絡(luò)就需要從頭開(kāi)始訓(xùn)練，對(duì)于以前的權(quán)值和閾值是沒(méi)有記憶的。但是可以將預(yù)測(cè)、分類或聚類做的比較好的權(quán)值保存。

（5）網(wǎng)絡(luò)的預(yù)測(cè)能力（也稱泛化能力、推廣能力）與訓(xùn)練能力（也稱逼近能力、學(xué)習(xí)能力）的矛盾。一般情況下，訓(xùn)練能力差時(shí)，預(yù)測(cè)能力也差，并且一定程度上，隨訓(xùn)練能力地提高，預(yù)測(cè)能力也提高。但這種趨勢(shì)有一個(gè)極限，當(dāng)達(dá)到此極限時(shí)，隨訓(xùn)練能力的提高，預(yù)測(cè)能力反而下降，即出現(xiàn)所謂“過(guò)擬合”現(xiàn)象。此時(shí)，網(wǎng)絡(luò)學(xué)習(xí)了過(guò)多的樣本細(xì)節(jié)，而不能反映樣本內(nèi)含的規(guī)律。（6）網(wǎng)絡(luò)訓(xùn)練失敗的可能性較大，其原因有：

a 從數(shù)學(xué)角度看，BP算法為一種局部搜索的優(yōu)化方法，但它要解決的問(wèn)題為求解復(fù)雜非線性函數(shù)的全局極值，因此，算法很有可能陷入局部極值，使訓(xùn)練失敗；

b 網(wǎng)絡(luò)的逼近、推廣能力同學(xué)習(xí)樣本的典型性密切相關(guān)，而從問(wèn)題中選取典型樣本實(shí)例組成訓(xùn)練集是一個(gè)很困難的問(wèn)題。④改進(jìn).變步長(zhǎng)法

BP算法的有效性和收斂性在很大程度上取決于學(xué)習(xí)步長(zhǎng)η的值。采用一般的固定長(zhǎng)梯度下降法求解時(shí),起碼可能導(dǎo)致兩個(gè)主要問(wèn)題:局部極小解;收斂速度慢。所以,一般要求是,當(dāng)訓(xùn)練到誤差曲面的平坦區(qū)時(shí),梯度較小,為加快收斂應(yīng)使η增大;當(dāng)訓(xùn)練到深而窄的誤差曲面時(shí),應(yīng)使η減小,以免因步長(zhǎng)過(guò)大而出現(xiàn)振蕩現(xiàn)象。為加快收斂,應(yīng)使η合理化,可采用變步長(zhǎng)算法。變步長(zhǎng)算法的基本思想是,先設(shè)一個(gè)初始步長(zhǎng)η,若一次迭代后誤差增大,則將步長(zhǎng)乘以β(<1),沿原方向重新計(jì)算該迭代點(diǎn);若一次迭代后誤差減小,則將步長(zhǎng)乘以α(>1),計(jì)算下一個(gè)迭代點(diǎn),以縮短學(xué)習(xí)時(shí)間。2.加動(dòng)量項(xiàng)法

為了加速BP算法的收斂,可考慮在權(quán)值調(diào)整算式中加入動(dòng)量項(xiàng),即

式中,α為動(dòng)量因子,一般取0.1～0.8。這時(shí)權(quán)值修正量加上了有關(guān)上一時(shí)刻權(quán)值修改方向的記憶,加速了網(wǎng)絡(luò)的收斂。加動(dòng)量項(xiàng)法的具體原理:若相鄰兩次迭代點(diǎn)處的梯度方向是一致的,引入動(dòng)量項(xiàng)可使權(quán)值的調(diào)整量增大,從而加速收斂;若相鄰兩次迭代點(diǎn)處的梯度方向相反,引入動(dòng)量項(xiàng)可使權(quán)值的調(diào)整量減小,避免了來(lái)回振蕩,加快了收斂。3.串連法

BP算法的收斂速度主要取決于輸入-輸出模式間非線性映射的復(fù)雜程度。顯然,這種非線性映射關(guān)系越復(fù)雜,收斂時(shí)間越長(zhǎng)。因此,對(duì)那些高度復(fù)雜的非線性問(wèn)題,用兩個(gè)串連的BP網(wǎng)絡(luò)代替一個(gè)BP網(wǎng)絡(luò),能夠有效地縮短訓(xùn)練時(shí)間。4.利用遺傳算法優(yōu)化BP算法

BP算法的優(yōu)點(diǎn)是尋優(yōu)具有精確性,但它易陷入局部極小、收斂速度慢,而遺傳算法(GeneticAlgorithm,GA)是基于自然選擇和遺傳規(guī)律的全局優(yōu)化搜索算法,具有很強(qiáng)的宏觀搜索能力和尋優(yōu)全局性。因此,在BP神經(jīng)網(wǎng)絡(luò)理論中引入遺傳算法的思想,則可以很好地達(dá)到全局尋優(yōu)和快速高效的目的。

Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量機(jī))（此算法是重點(diǎn)，必考題）

①算法思想

SVM的主要思想是針對(duì)兩類分類問(wèn)題，尋找一個(gè)超平面作為兩類訓(xùn)練樣本點(diǎn)的分割，以保證最小的分類錯(cuò)誤率。在線性可分的情況下，存在一個(gè)或多個(gè)超平面使得訓(xùn)練樣本完全分開(kāi)，SVM的目標(biāo)是找到其中的最優(yōu)超平面，最優(yōu)超平面是使得每一類數(shù)據(jù)與超平面距離最近的向量與超平面之間的距離最大的這樣的平面，對(duì)于線性不可分的情況，通過(guò)使用核函數(shù)（一種非線性映射算法）將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分。②優(yōu)點(diǎn)

（1）小樣本，并不是說(shuō)樣本的絕對(duì)數(shù)量少（實(shí)際上，對(duì)任何算法來(lái)說(shuō)，更多的樣本幾乎總是能帶來(lái)更好的效果），而是說(shuō)與問(wèn)題的復(fù)雜度比起來(lái)，SVM算法要求的樣本數(shù)是相對(duì)比較少的。

（2）非線性，是指SVM擅長(zhǎng)應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過(guò)松弛變量（也有人叫懲罰變量）和核函數(shù)技術(shù)來(lái)實(shí)現(xiàn)，（3）高維模式識(shí)別是指樣本維數(shù)很高，例如文本的向量表示，如果沒(méi)有經(jīng)過(guò)降維處理，出現(xiàn)幾萬(wàn)維的情況很正常，其他算法基本就沒(méi)有能力應(yīng)付了，SVM卻可以，主要是因?yàn)镾VM 產(chǎn)生的分類器很簡(jiǎn)潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本，此為后話），使得即使樣本維數(shù)很高，也不會(huì)給存儲(chǔ)和計(jì)算帶來(lái)大麻煩（相對(duì)照而言，kNN算法在分類時(shí)就要用到所有樣本，樣本數(shù)巨大，每個(gè)樣本維數(shù)再一高，這日子就沒(méi)法過(guò)了??）。③缺點(diǎn)

（1）SVM算法對(duì)大規(guī)模訓(xùn)練樣本難以實(shí)施 由于SVM是借助二次規(guī)劃來(lái)求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的計(jì)算（m為樣本的個(gè)數(shù)），當(dāng)m數(shù)目很大時(shí)該矩陣的存儲(chǔ)和計(jì)算將耗費(fèi)大量的機(jī)器內(nèi)存和運(yùn)算時(shí)間。（2）用SVM解決多分類問(wèn)題存在困難 ④改進(jìn)：

經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，而在數(shù)據(jù)挖掘的實(shí)際應(yīng)用中，一般要解決多類的分類問(wèn)題。可以通過(guò)多個(gè)二類支持向量機(jī)的組合來(lái)解決。主要有

一對(duì)多組合模式、一對(duì)一組合模式和SVM決策樹(shù)； 再就是通過(guò)構(gòu)造多個(gè)分類器的組合來(lái)解決。

主要原理是克服SVM固有的缺點(diǎn)，結(jié)合其他算法的優(yōu)勢(shì)，解決多類問(wèn)題的分類精度。如：

與粗集理論結(jié)合，形成一種優(yōu)勢(shì)互補(bǔ)的多類問(wèn)題的組合分類器。此處有一道必考題

Lecture 4 Introduction to Decision Rule Mining（1）ID3 Algorithm ①算法思想：

補(bǔ)充：

ID3算法（Iterative Dichotomiser 3 迭代二叉樹(shù)3代）是一個(gè)由Ross Quinlan發(fā)明的用于決策樹(shù)的算法。這個(gè)算法便是：

從信息論知識(shí)中我們知道，期望信息越小，信息增益越大，從而純度越高。ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進(jìn)行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間。

所以，ID3的思想便是：

自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間構(gòu)造決策樹(shù)(此方法是ID3算法和C4.5算法的基礎(chǔ))； 從“哪一個(gè)屬性將在樹(shù)的根節(jié)點(diǎn)被測(cè)試”開(kāi)始；

使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力，分類能力最好的屬性作為樹(shù)的根結(jié)點(diǎn)測(cè)試(如何定義或者評(píng)判一個(gè)屬性是分類能力最好的呢？這便是下文將要介紹的信息增益，or 信息增益率)。

然后為根結(jié)點(diǎn)屬性的每個(gè)可能值產(chǎn)生一個(gè)分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Вㄒ簿褪钦f(shuō)，樣例的該屬性值對(duì)應(yīng)的分支）之下。重復(fù)這個(gè)過(guò)程，用每個(gè)分支結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例來(lái)選取在該點(diǎn)被測(cè)試的最佳屬性。

②優(yōu)點(diǎn)：

（1）分類精度高；

（2）實(shí)現(xiàn)比較簡(jiǎn)單，產(chǎn)生的規(guī)則如果用圖表示出來(lái)的話，清晰易懂；

優(yōu)點(diǎn)補(bǔ)充：

（4）ID3算法的假設(shè)空間包含了所有的決策樹(shù)，不存在無(wú)解風(fēng)險(xiǎn)

（5）ID3算法非常適合處理離散樣本數(shù)據(jù)，利用屬性結(jié)果提取分類規(guī)則，且容易理解（6）引進(jìn)了信息論的中的熵，使得算法得到結(jié)點(diǎn)最少的決策樹(shù) ③缺點(diǎn)：

（1）ID3算法往往偏向于選擇取值較多的屬性，而在很多情況下取值較多的屬性并不總是最重要的屬性，即按照使熵值最小的原則被ID3算法列為應(yīng)該首先判斷的屬性在現(xiàn)實(shí)情況中卻并不一定非常重要。例如：在銀行客戶分析中，姓名屬性取值多，卻不能從中得到任何信息。（簡(jiǎn)略寫(xiě)：由于使用信息增益，會(huì)在屬性選擇時(shí)偏向選擇取值多的屬性）

（2）ID3算法對(duì)于噪聲數(shù)據(jù)敏感，ID3算法不能處理具有連續(xù)值的屬性，也不能處理具有缺失數(shù)據(jù)的屬性。

（3）用互信息作為選擇屬性的標(biāo)準(zhǔn)存在一個(gè)假設(shè)，即訓(xùn)練子集中的正、反例的比例應(yīng)與實(shí)際問(wèn)題領(lǐng)域中正、反例的比例一致。一般情況很難保證這兩者的比例一致，這樣計(jì)算訓(xùn)練集的互信息就會(huì)存在偏差。

（4）在建造決策樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)僅含一個(gè)屬性，是一種單變?cè)乃惴ǎ率股傻臎Q策樹(shù)結(jié)點(diǎn)之間的相關(guān)性不夠強(qiáng)。雖然在一棵樹(shù)上連在一起，但聯(lián)系還是松散的。

（5）ID3算法雖然理論清晰，但計(jì)算比較復(fù)雜，在學(xué)習(xí)和訓(xùn)練數(shù)據(jù)集的過(guò)程中機(jī)器內(nèi)存占用率比較大，耗費(fèi)資源。（計(jì)算復(fù)雜，有很多對(duì)數(shù)計(jì)算）

（6）ID3不夠健壯，當(dāng)有一個(gè)項(xiàng)數(shù)據(jù)有改變時(shí)，整棵樹(shù)的結(jié)構(gòu)可能改變很大。

改進(jìn)：用R-C4.5的思想，在進(jìn)行測(cè)試屬性選擇時(shí)，合并分類貢獻(xiàn)小的分支，避免出現(xiàn)過(guò)細(xì)的分枝，提高樹(shù)的健壯性。補(bǔ)充：

（7）當(dāng)訓(xùn)練集增加或減少的時(shí)候，決策樹(shù)都會(huì)隨之改變，對(duì)漸進(jìn)學(xué)習(xí)不方便。

④改進(jìn)：（1）對(duì)決策樹(shù)進(jìn)行剪枝。可以采用交叉驗(yàn)證法和加入正則化的方法。

（2）使用基于決策樹(shù)的combination算法，如bagging算法，randomforest算法，可以解決過(guò)擬合的問(wèn)題（3）引入用戶興趣度

給定a(0≤a≤1)為用戶對(duì)不確定知識(shí)的興趣度，a的大小由決策者根據(jù)先驗(yàn)知識(shí)或領(lǐng)域知識(shí)來(lái)確定。它是一個(gè)模糊的概念，通常指關(guān)于某一事務(wù)的先驗(yàn)知識(shí)，包括領(lǐng)域知識(shí)和專家建議，具體到?jīng)Q策樹(shù)學(xué)習(xí)中則是指在決策樹(shù)訓(xùn)練過(guò)程中除了用于生成和修改決策樹(shù)的實(shí)例集之外的所有影響決策樹(shù)規(guī)則生成和選擇的因素。

（2）C4.5 Algorithm 補(bǔ)充：

既然說(shuō)C4.5算法是ID3的改進(jìn)算法，那么C4.5相比于ID3改進(jìn)的地方有哪些呢？

用信息增益率來(lái)選擇屬性。ID3選擇屬性用的是子樹(shù)的信息增益，這里可以用很多方法來(lái)定義信息，ID3使用的是熵(entropy，熵是一種不純度度量準(zhǔn)則),也就是熵的變化值，而C4.5用的是信息增益率。對(duì)，區(qū)別就在于一個(gè)是信息增益，一個(gè)是信息增益率。（因此，C4.5克服了ID3用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足。）在樹(shù)構(gòu)造過(guò)程中進(jìn)行剪枝，在構(gòu)造決策樹(shù)的時(shí)候，那些掛著幾個(gè)元素的節(jié)點(diǎn)，不考慮最好，不然容易導(dǎo)致overfitting。對(duì)非離散數(shù)據(jù)也能處理。能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理 ①算法思想：

②優(yōu)點(diǎn)：

（1）產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。（2）對(duì)非離散數(shù)據(jù)也能處理。

C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點(diǎn)上的分枝屬性時(shí)，對(duì)于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對(duì)于某個(gè)連續(xù)性描述屬性Ac，假設(shè)在某個(gè)結(jié)點(diǎn)上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理。

1）將該結(jié)點(diǎn)上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進(jìn)行排序，得到屬性值的取值序列{A1c，A2c，??Atotalc}。

2）在取值序列中生成total-1個(gè)分割點(diǎn)。第i（0

3）從total-1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，C4.5計(jì)算它的信息增益比，并且從中選擇信息增益比最大的分割點(diǎn)來(lái)劃分?jǐn)?shù)據(jù)集。（3）能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如〈x，c(x)〉是樣本集S中的一個(gè)訓(xùn)練實(shí)例，但是其屬 性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略是賦給它結(jié)點(diǎn)n所對(duì)應(yīng)的訓(xùn)練實(shí)例中該屬性的最常見(jiàn)值；另外一種更復(fù)雜的策略是為A的每個(gè)可能值賦予一個(gè)概率。例如，給定一個(gè)布爾屬性A，如果結(jié)點(diǎn)n包含6個(gè)已知A=1和4個(gè)A=0的實(shí)例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實(shí)例x的60%被分配到A=1的分支，40%被分配到另一個(gè)分支。這些片斷樣例（fractional examples）的目的是計(jì)算信息增益，另外，如果有第二個(gè)缺少值的屬性必須被測(cè)試，這些樣例可以在后繼的樹(shù)分支中被進(jìn)一步細(xì)分。C4.5就是使用這種方法處理缺少的屬性值。（4）克服了用信息增益來(lái)選擇屬性時(shí)偏向選擇值多的屬性的不足。（5）采用了一種后剪枝方法

避免樹(shù)的高度無(wú)節(jié)制的增長(zhǎng)，避免過(guò)度擬合數(shù)據(jù)，該方法使用訓(xùn)練樣本集本身來(lái)估計(jì)剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下：

其中N是實(shí)例的數(shù)量，f=E/N為觀察到的誤差率（其中E為N個(gè)實(shí)例中分類錯(cuò)誤的個(gè)數(shù)），q為真實(shí)的誤差率，c為置信度（C4.5算法的一個(gè)輸入?yún)?shù)，默認(rèn)值為0.25），z為對(duì)應(yīng)于置信度c的標(biāo)準(zhǔn)差，其值可根據(jù)c的設(shè)定值通過(guò)查正態(tài)分布表得到。通過(guò)該公式即可計(jì)算出真實(shí)誤差率q的一個(gè)置信度上限，用此上限為該節(jié)點(diǎn)誤差率e做一個(gè)悲觀的估計(jì)：

通過(guò)判斷剪枝前后e的大小，從而決定是否需要剪枝。

樹(shù)剪枝

在決策樹(shù)的創(chuàng)建時(shí)，由于數(shù)據(jù)中的噪聲和離群點(diǎn)，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝方法是用來(lái)處理這種過(guò)分?jǐn)M合數(shù)據(jù)的問(wèn)題。通常剪枝方法都是使用統(tǒng)計(jì)度量，剪去最不可靠的分枝。

剪枝一般分兩種方法：先剪枝和后剪枝。

先剪枝方法中通過(guò)提前停止樹(shù)的構(gòu)造（比如決定在某個(gè)節(jié)點(diǎn)不再分裂或劃分訓(xùn)練元組的子集）而對(duì)樹(shù)剪枝。一旦停止，這個(gè)節(jié)點(diǎn)就變成樹(shù)葉，該樹(shù)葉可能取它持有的子集最頻繁的類作為自己的類。先剪枝有很多方法，比如（1）當(dāng)決策樹(shù)達(dá)到一定的高度就停止決策樹(shù)的生長(zhǎng)；（2）到達(dá)此節(jié)點(diǎn)的實(shí)例具有相同的特征向量，而不必一定屬于同一類，也可以停止生長(zhǎng)（3）到達(dá)此節(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于某個(gè)閾值的時(shí)候也可以停止樹(shù)的生長(zhǎng)，不足之處是不能處理那些數(shù)據(jù)量比較小的特殊情況（4）計(jì)算每次擴(kuò)展對(duì)系統(tǒng)性能的增益，如果小于某個(gè)閾值就可以讓它停止生長(zhǎng)。先剪枝有個(gè)缺點(diǎn)就是視野效果問(wèn)題，也就是說(shuō)在相同的標(biāo)準(zhǔn)下，也許當(dāng)前擴(kuò)展不能滿足要求，但更進(jìn)一步擴(kuò)展又能滿足要求。這樣會(huì)過(guò)早停止決策樹(shù)的生長(zhǎng)。

另一種更常用的方法是后剪枝，它由完全成長(zhǎng)的樹(shù)剪去子樹(shù)而形成。通過(guò)刪除節(jié)點(diǎn)的分枝并用樹(shù)葉來(lái)替換它。樹(shù)葉一般用子樹(shù)中最頻繁的類別來(lái)標(biāo)記。

C4.5采用悲觀剪枝法，它使用訓(xùn)練集生成決策樹(shù)又用它來(lái)進(jìn)行剪枝，不需要獨(dú)立的剪枝集。

悲觀剪枝法的基本思路是：設(shè)訓(xùn)練集生成的決策樹(shù)是T，用T來(lái)分類訓(xùn)練集中的N的元組，設(shè)K為到達(dá)某個(gè)葉子節(jié)點(diǎn)的元組個(gè)數(shù)，其中分類錯(cuò)誤地個(gè)數(shù)為J。由于樹(shù)T是由訓(xùn)練集生成的，是適合訓(xùn)練集的，因此J/K不能可信地估計(jì)錯(cuò)誤率。所以用(J+0.5)/K來(lái)表示。設(shè)S為T的子樹(shù)，其葉節(jié)點(diǎn)個(gè)數(shù)為L(zhǎng)(s)，個(gè)數(shù)總和，為到達(dá)此子樹(shù)的葉節(jié)點(diǎn)的元組 為此子樹(shù)中被錯(cuò)誤分類的元組個(gè)數(shù)之和。在分類新的元組時(shí)，則其錯(cuò)誤分類個(gè)數(shù)為，其標(biāo)準(zhǔn)錯(cuò)誤表示為：。當(dāng)用此樹(shù)分類訓(xùn)練集時(shí)，設(shè)E為分類錯(cuò)誤個(gè)數(shù)，當(dāng)下面的式子成立時(shí)，則刪掉子樹(shù)S，用葉節(jié)點(diǎn)代替，且S的子樹(shù)不必再計(jì)算。

③缺點(diǎn)：

（1）構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。

（2）C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。（3）在構(gòu)造樹(shù)的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。④改進(jìn)：

（1）SLIQ算法

SLIQ算法對(duì)C4.5決策樹(shù)分類算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn)，在決策樹(shù)的構(gòu)造過(guò)程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。

1)預(yù)排序。對(duì)于連續(xù)屬性在每個(gè)內(nèi)部結(jié)點(diǎn)尋找其最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，都需要對(duì)訓(xùn)練集按照該屬性的取值進(jìn)行排序，而排序是很浪費(fèi)時(shí)間的操作。為此，SLIQ算法 采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對(duì)每個(gè)屬性的取值，把所有的記錄按照從小到大的順序進(jìn)行排序，以消除在決策樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行的排序。具體實(shí) 現(xiàn)時(shí)，需要為訓(xùn)練數(shù)據(jù)集的每個(gè)屬性創(chuàng)建一個(gè)屬性列表，為類別屬性創(chuàng)建一個(gè)類別列表。

2)廣度優(yōu)先策略。在C4.5算法中，樹(shù)的構(gòu)造是按照深度優(yōu)先策略完成的，需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描，費(fèi)時(shí)很多，為此，SLIQ采用 廣度優(yōu)先策略構(gòu)造決策樹(shù)，即在決策樹(shù)的每一層只需對(duì)每個(gè)屬性列表掃描一次，就可以為當(dāng)前決策樹(shù)中每個(gè)葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。

SLIQ算法由于采用了上述兩種技術(shù)，使得該算法能夠處理比C4.5大得多的訓(xùn)練集，在一定范圍內(nèi)具有良好的隨記錄個(gè)數(shù)和屬性個(gè)數(shù)增長(zhǎng)的可伸縮性。

然而它仍然存在如下缺點(diǎn)：

1)由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。

2)由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個(gè)數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能達(dá)到隨記錄數(shù)目增長(zhǎng)的線性可伸縮性。（2）SPRINT算法

為了減少駐留于內(nèi)存的數(shù)據(jù)量，SPRINT算法進(jìn)一步改進(jìn)了決策樹(shù)算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個(gè) 屬性列表中。這樣，在遍歷每個(gè)屬性列表尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，不必參照其他信息，將對(duì)結(jié)點(diǎn)的分裂表現(xiàn)在對(duì)屬性列表的分裂，即將每個(gè)屬性列表分成兩 個(gè)，分別存放屬于各個(gè)結(jié)點(diǎn)的記錄。

SPRINT算法的優(yōu)點(diǎn)是在尋找每個(gè)結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)變得更簡(jiǎn)單。其缺點(diǎn)是對(duì)非分裂屬性的屬性列表進(jìn)行分裂變得很困難。解決的辦法是對(duì)分裂屬性進(jìn)行分 裂時(shí)用哈希表記錄下每個(gè)記錄屬于哪個(gè)孩子結(jié)點(diǎn)，若內(nèi)存能夠容納下整個(gè)哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成 正比，當(dāng)訓(xùn)練集很大時(shí)，哈希表可能無(wú)法在內(nèi)存容納，此時(shí)分裂只能分批執(zhí)行，這使得SPRINT算法的可伸縮性仍然不是很好。

（3）隨機(jī)森林(Random Forest)（對(duì)C4.5,ID3改進(jìn)，提高準(zhǔn)確率）

隨機(jī)森林是一個(gè)最近比較火的算法，它有很多的優(yōu)點(diǎn)： 在數(shù)據(jù)集上表現(xiàn)良好

在當(dāng)前的很多數(shù)據(jù)集上，相對(duì)其他算法有著很大的優(yōu)勢(shì)

它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇 在訓(xùn)練完后，它能夠給出哪些feature比較重要

在創(chuàng)建隨機(jī)森林的時(shí)候，對(duì)generlization error使用的是無(wú)偏估計(jì) 訓(xùn)練速度快

在訓(xùn)練過(guò)程中，能夠檢測(cè)到feature間的互相影響 容易做成并行化方法 實(shí)現(xiàn)比較簡(jiǎn)單

隨機(jī)森林顧名思義，是用隨機(jī)的方式建立一個(gè)森林，森林里面有很多的決策樹(shù)組成，隨機(jī)森林的每一棵決策樹(shù)之間是沒(méi)有關(guān)聯(lián)的。在得到森林之后，當(dāng)有一個(gè)新的輸入樣本進(jìn)入的時(shí)候，就讓森林中的每一棵決策樹(shù)分別進(jìn)行一下判斷，看看這個(gè)樣本應(yīng)該屬于哪一類（對(duì)于分類算法），然后看看哪一類被選擇最多，就預(yù)測(cè)這個(gè)樣本為那一類。在建立每一棵決策樹(shù)的過(guò)程中，有兩點(diǎn)需要注意 – 采樣與完全分裂。首先是兩個(gè)隨機(jī)采樣的過(guò)程，random forest對(duì)輸入的數(shù)據(jù)要進(jìn)行行、列的采樣。對(duì)于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個(gè)，那么采樣的樣本也為N個(gè)。這樣使得在訓(xùn)練的時(shí)候，每一棵樹(shù)的輸入樣本都不是全部的樣本，使得相對(duì)不容易出現(xiàn)over-fitting。然后進(jìn)行列采樣，從M個(gè)feature中，選擇m個(gè)(m << M)。之后就 是對(duì)采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹(shù)，這樣決策樹(shù)的某一個(gè)葉子節(jié)點(diǎn)要么是無(wú)法繼續(xù)分裂的，要么里面的所有樣本的都是指向的同一個(gè)分類。一般很多的決策樹(shù)算法都一個(gè)重要的步驟 – 剪枝，但是這里不這樣干，由于之前的兩個(gè)隨機(jī)采樣的過(guò)程保證了隨機(jī)性，所以就算不剪枝，也不會(huì)出現(xiàn)over-fitting。

按這種算法得到的隨機(jī)森林中的每一棵都是很弱的，但是大家組合起來(lái)就很厲害了。我覺(jué)得可以這樣比喻隨機(jī)森林算法：每一棵決策樹(shù)就是一個(gè)精通于某一個(gè)窄領(lǐng)域的專家（因?yàn)槲覀儚腗個(gè)feature中選擇m讓每一棵決策樹(shù)進(jìn)行學(xué)習(xí)），這樣在隨機(jī)森林中就有了很多個(gè)精通不同領(lǐng)域的專家，對(duì)一個(gè)新的問(wèn)題（新的輸入數(shù)據(jù)），可以用不同的角度去看待它，最終由各個(gè)專家，投票得到結(jié)果。隨機(jī)森林的過(guò)程請(qǐng)參考Mahout的random forest。這個(gè)頁(yè)面上寫(xiě)的比較清楚了，其中可能不明白的就是Information Gain，可以看看之前推薦過(guò)的Moore的頁(yè)面。

Lecture 5 Classifier Assessment and Ensemble Methods

1、bagging bagging是一種用來(lái)提高學(xué)習(xí)算法準(zhǔn)確度的方法，這種方法通過(guò)構(gòu)造一個(gè)預(yù)測(cè)函數(shù)系列，然后以一定的方式將它們組合成一個(gè)預(yù)測(cè)函數(shù)。? 基本思想

1.給定一個(gè)弱學(xué)習(xí)算法,和一個(gè)訓(xùn)練集;2.單個(gè)弱學(xué)習(xí)算法準(zhǔn)確率不高;3.將該學(xué)習(xí)算法使用多次,得出預(yù)測(cè)函數(shù)序列,進(jìn)行投票;4.最后結(jié)果準(zhǔn)確率將得到提高.Bagging要求“不穩(wěn)定”（不穩(wěn)定是指數(shù)據(jù)集的小的變動(dòng)能夠使得分類結(jié)果的顯著的變動(dòng)）的分類方法。比如：決策樹(shù)，神經(jīng)網(wǎng)絡(luò)算法

2、Booting Boosting方法是一種用來(lái)提高弱分類算法準(zhǔn)確度的方法,這種方法通過(guò)構(gòu)造一個(gè)預(yù)測(cè)函數(shù)系列,然后以一定的方式將他們組合成一個(gè)預(yù)測(cè)函數(shù)。Boosting是一種提高任意給定學(xué)習(xí)算法準(zhǔn)確度的方法。他是一種框架算法,主要是通過(guò)對(duì)樣本集的操作獲得樣本子集,然后用弱分類算法在樣本子集上訓(xùn)練生成一系列的基分類器。可以用來(lái)提高其他弱分類算法的識(shí)別率。

? Bagging與Boosting的區(qū)別

二者的主要區(qū)別是取樣方式不同。Bagging采用均勻取樣，而B(niǎo)oosting根據(jù)錯(cuò)誤率來(lái)取樣，因此Boosting的分類精度要優(yōu)于Bagging。Bagging的訓(xùn)練集的選擇是隨機(jī)的，各輪訓(xùn)練集之間相互獨(dú)立，而B(niǎo)oostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)；Bagging的各個(gè)預(yù)測(cè)函數(shù)沒(méi)有權(quán)重，而B(niǎo)oosting是有權(quán)重的；Bagging的各個(gè)預(yù)測(cè)函數(shù)可以并行生成，而B(niǎo)oosting的各個(gè)預(yù)測(cè)函數(shù)只能順序生成。對(duì)于象神經(jīng)網(wǎng)絡(luò)這樣極為耗時(shí)的學(xué)習(xí)方法。Bagging可通過(guò)并行訓(xùn)練節(jié)省大量時(shí)間開(kāi)銷。

bagging和boosting都可以有效地提高分類的準(zhǔn)確性。在大多數(shù)數(shù)據(jù)集中，boosting的準(zhǔn)確性比bagging高。在有些數(shù)據(jù)集中，boosting會(huì)引起退化---Overfit。

Boosting思想的一種改進(jìn)型AdaBoost方法在郵件過(guò)濾、文本分類方面都有很好的性能。

3、Adaboost(Adaptive Boosting)? 算法簡(jiǎn)介

Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。其算法本身是通過(guò)改變數(shù)據(jù)分布來(lái)實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來(lái)確定每個(gè)樣本的權(quán)值。將修改過(guò)權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來(lái)，作為最后的決策分類器。使用adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。? 算法分析

該算法其實(shí)是一個(gè)簡(jiǎn)單的弱分類算法提升過(guò)程，這個(gè)過(guò)程通過(guò)不斷的訓(xùn)練，可以提高對(duì)數(shù)據(jù)的分類能力。整個(gè)過(guò)程如下所示：

1.先通過(guò)對(duì)N個(gè)訓(xùn)練樣本的學(xué)習(xí)得到第一個(gè)弱分類器； 2.將分錯(cuò)的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個(gè)新的N個(gè)的訓(xùn)練樣本，通過(guò)對(duì)這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器 ； 3.將1和2都分錯(cuò)了的樣本加上其他的新樣本構(gòu)成另一個(gè)新的N個(gè)的訓(xùn)練樣本，通過(guò)對(duì)這個(gè)樣本的學(xué)習(xí)得到第三個(gè)弱分類器；

4.最終經(jīng)過(guò)提升的強(qiáng)分類器。即某個(gè)數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定。

? 算法優(yōu)點(diǎn)： 高精度；簡(jiǎn)單，無(wú)需做特征篩選；可以使用各種方法構(gòu)建子分類器，Adaboost算法提供的是框架；當(dāng)使用簡(jiǎn)單分類器時(shí)，計(jì)算出的結(jié)果是可以理解的，而且弱分類器構(gòu)造極其簡(jiǎn)單；不會(huì)過(guò)度擬合。

對(duì)于boosting算法，存在兩個(gè)問(wèn)題：

1.如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行； 2.如何將訓(xùn)練得到的各個(gè)弱分類器聯(lián)合起來(lái)形成強(qiáng)分類器。針對(duì)以上兩個(gè)問(wèn)題，Adaboost算法進(jìn)行了調(diào)整：

1.使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上； 2.將弱分類器聯(lián)合起來(lái)，使用加權(quán)的投票機(jī)制代替平均投票機(jī)制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。

與Boosting算法不同的是，Adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。

? 算法缺點(diǎn)： 訓(xùn)練時(shí)間過(guò)長(zhǎng)，執(zhí)行效果依賴于弱分類器的選擇。對(duì)噪聲數(shù)據(jù)和離群值敏感。? 改進(jìn)：限制樣本權(quán)重的調(diào)整在各目標(biāo)類內(nèi)部進(jìn)行

1、權(quán)值更新方法的改進(jìn)

Allende等人提出了RADA算法，該算法是對(duì)原算法中誤分類樣本權(quán)值抑制的方法。算法最突出的貢獻(xiàn)有三點(diǎn)：第一點(diǎn)是對(duì)的抑制，第二點(diǎn)，用當(dāng)前層分類器來(lái)判斷樣本是否分類正

確，而非原算法中的當(dāng)前弱分類器，第三點(diǎn)，增加 age變量記錄誤分類情況，并作了閾值限制，這里有效緩解了過(guò)擬合的問(wèn)題。RADA 比傳統(tǒng) AdaBoost 算法更加穩(wěn)定，有效解決了誤分類樣本權(quán)值偏高的問(wèn)題。

2、訓(xùn)練方法的改進(jìn)

Merler等人提出了AdaBoost的并行計(jì)算方法P-AdaBoost算法。其主要思想是，將AdaBoost訓(xùn)練過(guò)程分為兩個(gè)階段，第一階段和原算法一樣，經(jīng)過(guò)多輪訓(xùn)練，獲得一個(gè)較為可靠的樣本分布ωi(s)，第二階段采用并行方法提高訓(xùn)練效率，訓(xùn)練中不再對(duì)樣本權(quán)值進(jìn)行更新，而統(tǒng)一采用ωi(s)，最后輸出為。

采用這種方法能大大減少訓(xùn)練成本，與原算法相比，多了S 輪的樣本分布初始化工作，并且避免了差樣本因多次分類而造成權(quán)值過(guò)大的問(wèn)題。

3、多算法結(jié)合的改進(jìn)

Yunlong提出了EAdaBoost算法，是AdaBoost結(jié)合k近鄰算法的產(chǎn)物。AdaBoost算法具有高度擬合的特點(diǎn)，噪聲會(huì)對(duì)訓(xùn)練產(chǎn)生很大的影響，Yunlong等人在AdaBoost算法的基礎(chǔ)之上加入了kNN算法，對(duì)噪聲樣本進(jìn)行了有效處理，提高了算法的精確度。EAdaBoost算法的主要過(guò)程如下：

(a)準(zhǔn)備訓(xùn)練樣本，對(duì)樣本權(quán)值進(jìn)行初始化。(b)計(jì)算訓(xùn)練誤差，并挑選最優(yōu)的弱分類器。(c)更新樣本權(quán)值。

(d)用 KNN 算法排除噪聲樣本，將權(quán)值設(shè)為 0。

該算法中有兩個(gè)非常關(guān)鍵的問(wèn)題，什么樣的樣本稱為噪聲樣本和每次要處理多少個(gè)噪聲樣本的問(wèn)題，原文中稱之為 suspect sample，算法中取的是那種難于學(xué)習(xí)、讓分類器出錯(cuò)過(guò)多的樣本。

4、綜合方法的改進(jìn)

Rong Xiao等人提出了Boosting Chain算法，用鏈表的方式來(lái)組織分類器，算法先用boosting特征快速排除 大量非人臉窗口，再用boosting chain和SVM分類器進(jìn)行再判別，實(shí)驗(yàn)效果相比FloatBoost還要略好。

Adaboosting

Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms ①算法思想：Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項(xiàng)集”用于搜索“K項(xiàng)集”。首先，找出頻繁“1項(xiàng)集”的集合，該集合記作L1。L1用于找頻繁“2項(xiàng)集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項(xiàng)集”。找每個(gè)Lk都需要一次數(shù)據(jù)庫(kù)掃描。

一、挖掘步驟：

1.依據(jù)支持度找出所有頻繁項(xiàng)集（頻度）2.依據(jù)置信度產(chǎn)生關(guān)聯(lián)規(guī)則（強(qiáng)度）二、一些定義： 對(duì)于A->B ①支持度：P(A∩B)，既有A又有B的概率

②置信度：P(B|A)，在A發(fā)生的事件中同時(shí)發(fā)生B的概率p(AB)/P(A)③如果事件A中包含k個(gè)元素，那么稱這個(gè)事件A為k項(xiàng)集事件A滿足最小支持度閾值的事件稱為頻繁k項(xiàng)集。④同時(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則。⑤候選集：通過(guò)向下合并得出的項(xiàng)集。

⑥頻繁集：支持度大于等于特定的最小支持度（Minimum Support/minsup）的項(xiàng)集。注意，頻繁集的子集一定是頻繁集。核心思想：連接步和剪枝步。連接步是自連接，原則是保證前k-2項(xiàng)相同，并按照字典順序連接。剪枝步，是使任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的。反之，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。簡(jiǎn)單的講，1、發(fā)現(xiàn)頻繁項(xiàng)集，過(guò)程為（1）掃描（2）計(jì)數(shù)（3）比較（4）產(chǎn)生頻繁項(xiàng)集（5）連接、剪枝，產(chǎn)生候選項(xiàng)集，重復(fù)步驟（1）~（5）直到不能發(fā)現(xiàn)更大的頻集

2、產(chǎn)生關(guān)聯(lián)規(guī)則，過(guò)程為:根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對(duì)于每個(gè)頻繁項(xiàng)集L，產(chǎn)生L的所有非空子集；（2）對(duì)于L的每個(gè)非空子集S，如果 P（L）/P（S）≧minsup 則輸出規(guī)則“SàL-S”

注：L-S表示在項(xiàng)集L中除去S子集的項(xiàng)集

②優(yōu)點(diǎn)： Apriori（先驗(yàn)的，推測(cè)的）算法應(yīng)用廣泛，可用于消費(fèi)市場(chǎng)價(jià)格分析，猜測(cè)顧客的消費(fèi)習(xí)慣；網(wǎng)絡(luò)安全領(lǐng)域中的入侵檢測(cè)技術(shù)；可用在用于高校管理中，根據(jù)挖掘規(guī)則可以有效地輔助學(xué)校管理部門有針對(duì)性的開(kāi)展貧困助學(xué)工作；也可用在移動(dòng)通信領(lǐng)域中，指導(dǎo)運(yùn)營(yíng)商的業(yè)務(wù)運(yùn)營(yíng)和輔助業(yè)務(wù)提供商的決策制定。

③缺點(diǎn)：此算法的的應(yīng)用非常廣泛，但是他在運(yùn)算的過(guò)程中會(huì)產(chǎn)生大量的侯選集，而且在匹配的時(shí)候要進(jìn)行整個(gè)數(shù)據(jù)庫(kù)的掃描（重復(fù)掃描），因?yàn)橐鲋С侄扔?jì)數(shù)的統(tǒng)計(jì)操作，在小規(guī)模的數(shù)據(jù)上操作還不會(huì)有大問(wèn)題，如果是大型的數(shù)據(jù)庫(kù)上呢，他的效率還是有待提高的。④改進(jìn)：

方法

一、Apriori優(yōu)化：Fp-tree 算法

關(guān)鍵點(diǎn)：以樹(shù)形的形式來(lái)展示、表達(dá)數(shù)據(jù)的形態(tài)；可以理解為水在不同河流分支的流動(dòng)過(guò)程； 生成Fp-tree的幾個(gè)點(diǎn)： 1.掃描原始項(xiàng)目集； 2.排列數(shù)據(jù)；

3.創(chuàng)建ROOT節(jié)點(diǎn)；

4.按照排列的數(shù)據(jù)進(jìn)行元素的流動(dòng)； 5.節(jié)點(diǎn)+1；

方法

二、Apriori優(yōu)化：垂直數(shù)據(jù)分布

關(guān)鍵點(diǎn)：相當(dāng)于把原始數(shù)據(jù)進(jìn)行行轉(zhuǎn)列的操作，并且記錄每個(gè)元素的個(gè)數(shù) Lecture 6有5種改進(jìn)方法：

1.基于哈希的項(xiàng)集數(shù)：小于閾值的哈希桶數(shù)的k項(xiàng)集不是頻繁的

2.縮減事務(wù)：在子頻繁集中掃描時(shí)，不包含任何k項(xiàng)頻繁集的事務(wù)是無(wú)用的 3.劃分DB：DB中的任何頻繁項(xiàng)集在部分DB中也一定是頻繁的 4.采樣：用一個(gè)小的支持閾值和方法挖掘給定數(shù)據(jù)的子集

5.動(dòng)態(tài)規(guī)劃項(xiàng)集數(shù)：只有當(dāng)他們的所有子集預(yù)計(jì)為頻繁時(shí)才添加一個(gè)新的候選項(xiàng)（1）基于hash的方法。基于哈希的算法仍是將所有所有數(shù)據(jù)放入內(nèi)存的方法。只要在計(jì)算的過(guò)程中能夠滿足算法對(duì)內(nèi)存的大量需求，針對(duì)C2候選項(xiàng)對(duì)過(guò)大，一些算法提出用來(lái)減少C2的大小。這里我們首先考慮PCY算法，這個(gè)算法使用了在Apriori算法的第一步里大量沒(méi)使用的內(nèi)存。接著，我們考慮Multistage（多步哈希）算法，這個(gè)算法使用PCY的技巧，但插入了額外的步驟來(lái)更多的減少C2的大小。類似的還有Multihash。

（2）基于劃分的方法。Savasere等設(shè)計(jì)了一個(gè)基于劃分(partition)的算法.這個(gè)算法先把數(shù)據(jù)庫(kù)從邏輯上分成幾個(gè)互不相交的塊，每次單獨(dú)考慮一個(gè)分塊并對(duì)它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來(lái)生成所有可能的頻集，最后計(jì)算這些項(xiàng)集的支持度。這里分塊的大小選擇要使得每個(gè)分塊可以被放入主存，每個(gè)階段只需被掃描一次。而算法的正確性是由每一個(gè)可能的頻集至少在某一個(gè)分塊中是頻集保證的。

（3）基于采樣的方法。基于前一遍掃描得到的信息，對(duì)此仔細(xì)地作組合分析，可以得到一個(gè)改進(jìn)的算法，Mannila等先考慮了這一點(diǎn)，他們認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個(gè)有效途徑。

（2）FP-tree Algorithms ①算法思想：

參考http://blog.csdn.net/sealyao/article/details/6460578 FP-tree 在不生成候選項(xiàng)的情況下，完成Apriori算法的功能。通過(guò)合并一些重復(fù)路徑，實(shí)現(xiàn)了數(shù)據(jù)的壓縮，從而使得將頻繁項(xiàng)集加載到內(nèi)存中成為可能。之后以樹(shù)遍歷的操作，替代了 Apriori 算法中最耗費(fèi)時(shí)間的事務(wù)記錄遍歷，從而大大提高了運(yùn)算效率。算法步驟如下：

1.掃描一遍數(shù)據(jù)庫(kù)，刪除頻率小于最小支持度的項(xiàng)，并降序排列。并將每個(gè)事務(wù)中的項(xiàng)都要按照這個(gè)順序進(jìn)行排列。處理后的數(shù)據(jù)庫(kù)記錄為：

2.構(gòu)建 FP-Tree，把每個(gè)事務(wù)中的數(shù)據(jù)項(xiàng)按降序依次插入到一棵以NULL為根結(jié)點(diǎn)的樹(shù)中，同時(shí)在每個(gè)結(jié)點(diǎn)處記錄該結(jié)點(diǎn)出現(xiàn)的支持度。如果插入時(shí)頻繁項(xiàng)節(jié)點(diǎn)已經(jīng)存在了，則把該頻繁項(xiàng)節(jié)點(diǎn)支持度加1；如果該節(jié)點(diǎn)不存在，則創(chuàng)建支持度為1的節(jié)點(diǎn)，并把該節(jié)點(diǎn)鏈接到項(xiàng)頭表中。

3.求出每個(gè)節(jié)點(diǎn)的條件模式基

4.為每個(gè)節(jié)點(diǎn)建立FP-Tree

5.遞歸 調(diào)用FP-growth(Tree，null)開(kāi)始進(jìn)行挖掘。偽代碼如下： procedure FP_growth(Tree, a)if Tree 含單個(gè)路徑P then{

for 路徑P中結(jié)點(diǎn)的每個(gè)組合（記作b）

產(chǎn)生模式b U a，其支持度support = b 中結(jié)點(diǎn)的最小支持度； } else {

for each a i 在Tree的頭部(按照支持度由低到高順序進(jìn)行掃描){ 產(chǎn)生一個(gè)模式b = a i U a，其支持度support = a i-support；

構(gòu)造b的條件模式基，然后構(gòu)造b的條件FP-樹(shù)Treeb； if Treeb 不為空 then 調(diào)用 FP_growth(Treeb, b)； } }

FP-growth的執(zhí)行過(guò)程：

1）在FP-growth遞歸調(diào)用的第一層，模式前后a=NULL，得到的其實(shí)就是頻繁1-項(xiàng)集。2）對(duì)每一個(gè)頻繁1-項(xiàng)，進(jìn)行遞歸調(diào)用FP-growth()獲得多元頻繁項(xiàng)集。②優(yōu)點(diǎn)：

（ppt翻譯）

1.算法結(jié)構(gòu)擁有完整性：

1）沒(méi)有破壞事務(wù)的長(zhǎng)模式；

2）能保留頻繁模式挖掘的完整信息。2.算法結(jié)構(gòu)擁有緊湊性：

1）不相關(guān)的項(xiàng)被刪除；

2）事務(wù)項(xiàng)按照頻率降序排列，因?yàn)楦l繁的項(xiàng)更可能被找到；

3）如果不計(jì)算鏈接和節(jié)點(diǎn)數(shù)目，存儲(chǔ)空間小于原始數(shù)據(jù)庫(kù)。

3.FP算法的效率比Apriori算法快一個(gè)數(shù)量級(jí),效率快的原因有以下4個(gè)：

1）沒(méi)有候選集，沒(méi)有候選測(cè)試

2）有緊湊的數(shù)據(jù)結(jié)構(gòu)

3）消除重復(fù)的數(shù)據(jù)庫(kù)遍歷

4）基礎(chǔ)操作是計(jì)數(shù)和FP-Tree的建立 ③缺點(diǎn)：

（參考http://www.tmdps.cn/wiki/Covariance_matrix

我們認(rèn)為bi代表B的第i行，那么由協(xié)方差矩陣

推知

<>表示向量的內(nèi)積，也就是每一項(xiàng)的積之和。⑤ 計(jì)算協(xié)方差矩陣C的特征值和特征向量

若XA=aA,其中A為一列向量，a為一實(shí)數(shù)。那么a就被稱為矩陣X的特征值，而A則是特征值a對(duì)應(yīng)的特征向量。

順便扯一下，在matlab里面，求解上述A以及a，使用eig函數(shù)。如[D,V] = eig(C)，那么D就是n個(gè)列特征向量，而V是對(duì)角矩陣，對(duì)角線上的元素就是特征值。⑥ 排序

將特征值按從大到小的順序排列，并根據(jù)特征值調(diào)整特征向量的排布。

D'=sort(D);V'=sort(V);

⑦ 計(jì)算總能量并選取其中的較大值

若V'為C的對(duì)角陣，那么總能量為對(duì)角線所有特征值之和S。

由于在步驟⑥里面已對(duì)V進(jìn)行了重新排序，所以當(dāng)v'前幾個(gè)特征值之和大于等于S的90%時(shí)，可以認(rèn)為這幾個(gè)特征值可以用來(lái)“表征”當(dāng)前矩陣。

假設(shè)這樣的特征值有L個(gè)。⑧ 計(jì)算基向量矩陣W

實(shí)際上，W是V矩陣的前L列，所以W的大小就是 MxL。⑨ 計(jì)算z-分?jǐn)?shù)（這一步可選可不選）

Z[i,j]=B[i,j]/sqrt(D[i,i])⑩ 計(jì)算降維后的新樣本矩陣

W*表示W(wǎng)的轉(zhuǎn)置的共軛矩陣，大小為 LxM , 而Z的大小為 MxN , 所以Y的大小為 LxN , 即降維為 N 個(gè) L 維向量。

②優(yōu)點(diǎn)： 該算法可以消除數(shù)據(jù)間的冗余，以簡(jiǎn)化數(shù)據(jù)，提高計(jì)算效率。③缺點(diǎn)：缺乏主成分的物理解釋，也就是缺乏有效的語(yǔ)義解釋。

PCA假設(shè)數(shù)據(jù)各主特征是分布在正交方向上，如果在非正交方向上存在幾個(gè)方差較大的方向，PCA的效果就大打折扣了。

PCA技術(shù)的一個(gè)很大的優(yōu)點(diǎn)是，它是完全無(wú)參數(shù)限制的。在PCA的計(jì)算過(guò)程中完全不需要人為的設(shè)定參數(shù)或是根據(jù)任何經(jīng)驗(yàn)?zāi)Ｐ蛯?duì)計(jì)算進(jìn)行干預(yù)，最后的結(jié)果只與數(shù)據(jù)相關(guān)，與用戶是獨(dú)立的。

但是，這一點(diǎn)同時(shí)也可以看作是缺點(diǎn)。如果用戶對(duì)觀測(cè)對(duì)象有一定的先驗(yàn)知識(shí)，掌握了數(shù)據(jù)的一些特征，卻無(wú)法通過(guò)參數(shù)化等方法對(duì)處理過(guò)程進(jìn)行干預(yù)，可能會(huì)得不到預(yù)期的效果，效率也不高

PCA也存在一些限制，例如它可以很好的解除線性相關(guān)，但是對(duì)于高階相關(guān)性就沒(méi)有辦法了，對(duì)于存在高階相關(guān)性的數(shù)據(jù)，可以考慮Kernel PCA，通過(guò)Kernel函數(shù)將非線性相關(guān)轉(zhuǎn)為線性相關(guān)

④改進(jìn)：

第四篇：斯坦福大學(xué)公開(kāi)課 ：機(jī)器學(xué)習(xí)課程note1翻譯

CS229 Lecture notes

Andrew Ng 監(jiān)督式學(xué)習(xí)

讓我們開(kāi)始先討論幾個(gè)關(guān)于監(jiān)督式學(xué)習(xí)的問(wèn)題。假設(shè)我們有一組數(shù)據(jù)集是波特蘭，俄勒岡州的47所房子的面積以及對(duì)應(yīng)的價(jià)格

我們可以在坐標(biāo)圖中畫(huà)出這些數(shù)據(jù)：

給出這些數(shù)據(jù)，怎么樣我們才能用一個(gè)關(guān)于房子面積的函數(shù)預(yù)測(cè)出其他波特蘭的房子的價(jià)格。

為了將來(lái)使用的方便，我們使用x表示“輸入變量”（在這個(gè)例子中就是房子的面積），也叫做“輸入特征”，y表示“輸出變量”也叫做“目標(biāo)變量”就是我們要預(yù)測(cè)的那個(gè)變量（這個(gè)例子中就是價(jià)格）。一對(duì)（x,y）叫做一組訓(xùn)練樣本，并且我們用來(lái)學(xué)習(xí)的---一列訓(xùn)練樣本｛（x,y）；i=1，?，m｝--叫做一個(gè)訓(xùn)練集。注意：這個(gè)上標(biāo)“（i）”在這個(gè)符號(hào)iiiiii表示法中就是訓(xùn)練集中的索引項(xiàng)，并不是表示次冪的概念。我們會(huì)使用χ表示輸入變量的定義域，使用表示輸出變量的值域。在這個(gè)例子中χ=Y=R

為了更正式的描述我們這個(gè)預(yù)測(cè)問(wèn)題，我們的目標(biāo)是給出一個(gè)訓(xùn)練集，去學(xué)習(xí)產(chǎn)生一個(gè)函數(shù)h：X→ Y 因此h(x)是一個(gè)好的預(yù)測(cè)對(duì)于近似的y。由于歷史性的原因，這個(gè)函數(shù)h被叫做“假設(shè)”。預(yù)測(cè)過(guò)程的順序圖示如下：

當(dāng)我們預(yù)測(cè)的目標(biāo)變量是連續(xù)的，就像在我們例子中的房子的價(jià)格，我們叫這一類的學(xué)習(xí)問(wèn)題為“回歸問(wèn)題”，當(dāng)我們預(yù)測(cè)的目標(biāo)變量?jī)H僅只能取到一部分的離散的值（就像如果給出一個(gè)居住面積，讓你去預(yù)測(cè)這個(gè)是房子還是公寓，等等），我們叫這一類的問(wèn)題是“分類問(wèn)題”

PART I Linear Reression 為了使我們的房子問(wèn)題更加有趣，我們假設(shè)我們知道每個(gè)房子中有幾間臥室：

在這里，x是一個(gè)二維的向量屬于R。例如，x1i就是訓(xùn)練集中第i個(gè)房子的居住面積，i是訓(xùn)練集中第i個(gè)房子的臥室數(shù)量。（通常情況下，當(dāng)設(shè)計(jì)一個(gè)學(xué)習(xí)問(wèn)題的時(shí)候，這些輸x22入變量是由你決定去選擇哪些，因此如果你是在Portland收集房子的數(shù)據(jù)，你可能會(huì)決定包含其他的特征，比如房子是否帶有壁爐，這個(gè)洗澡間的數(shù)量等等。我們以后可能會(huì)涉及到更多變量的問(wèn)題，現(xiàn)在我們先按照給定的變量的講解。）

為了完成監(jiān)督是學(xué)習(xí)，我們必須決定怎么樣去描述我們的函數(shù)/假設(shè) h 在計(jì)算機(jī)中。有一個(gè)最初的選擇，我們把y近似的看成是x的一個(gè)線性函數(shù)：h??x???0??1x1??2x2 在這里，θ(i)是參數(shù)（也叫做權(quán)重）是y關(guān)于x的線性函數(shù)之間的參數(shù)。當(dāng)y與x之間沒(méi)有其他影響因素的時(shí)候我們將會(huì)舍棄下標(biāo)θ，通常寫(xiě)為h(x)。為了簡(jiǎn)化我們的標(biāo)注，我們習(xí)慣上令x0=1（這個(gè)是截距），因此可以寫(xiě)成

右邊的θ和x都是向量并且這里n是輸入的變量的個(gè)數(shù)（不是計(jì)算x0的個(gè)數(shù)）。

現(xiàn)在給定一個(gè)訓(xùn)練集，我們?cè)趺催x擇、學(xué)習(xí)、計(jì)算權(quán)重θ？一個(gè)合理的方法類似與讓h?x?盡可能的接近于y，至少對(duì)于我們所訓(xùn)練的數(shù)據(jù)都是適合的。使這個(gè)近似形式化，我們定義一個(gè)測(cè)量函數(shù)去記錄對(duì)于每一個(gè)θ，h(x(i))有多接近于y(i)。我們定義一個(gè)代價(jià)函數(shù)

如果你以前了解過(guò)線性回歸，你會(huì)認(rèn)出這個(gè)和最小二乘法比較近似。不管你以前是否看過(guò)他，讓我們繼續(xù)，并且我們最終會(huì)證明這個(gè)知識(shí)眾多的算法大家庭中的一個(gè)特例而已。LMS algorithm(Least Mean Square 最小均方差算法)我們想去選擇一個(gè)θ使得J(θ)取的最小值。為了這樣做，我們用一個(gè)尋找算法給θ賦一個(gè)初值（隨機(jī)的），然后不斷的重復(fù)改變?chǔ)鹊拇笮∫员闶荍(θ)更小，直到我們找到一個(gè)θ是的J(θ)達(dá)到我們期望的最小值。特別的，我們考慮“梯度下降算法”，用下面這個(gè)公式尋找θ。

（這個(gè)更新過(guò)程同時(shí)的對(duì)所有的j=0…n執(zhí)行）α表示“學(xué)習(xí)速率”。這是一個(gè)自然算法，反復(fù)的對(duì)J在減小的方向上邁出一大步直到最小。

為了執(zhí)行這個(gè)算法，我們需要做的工作就是計(jì)算出等號(hào)右邊的偏導(dǎo)數(shù)。首先我們計(jì)算出一組（x，y）樣本的偏導(dǎo)數(shù)，這是我們可以先忽略掉對(duì)J的求和。（運(yùn)用求導(dǎo)定律很容易就能求出導(dǎo)數(shù)）

對(duì)于單一的訓(xùn)練樣本，這里給出了更新的規(guī)則：

這個(gè)規(guī)則就叫做LMS更新規(guī)則（LMS是least mean squares的縮寫(xiě)）也被叫做Widrow-Hoff（就是Widrow和Hoff這兩位大仙發(fā)明的這個(gè)算法。參考鏈接：http://baike.baidu.com/link?url=bmZNDF9xV8GMtSE_rk9eV_9UbE9wGrnAdYqyf876U3Lf4IKfkRZVCoACvxF2dm1zmRDu1UUYzW9nQs-8oPWhu_）學(xué)習(xí)規(guī)則。這個(gè)算法有幾個(gè)自然的和直觀的特性。例如，更新的量級(jí)正比于誤差項(xiàng)

(y(i)? h_(x(i)))；因此，當(dāng)我們遇到一組訓(xùn)練樣本的預(yù)測(cè)值非常接近他的真實(shí)值的時(shí)候，我們會(huì)發(fā)現(xiàn)在更新過(guò)程中權(quán)重項(xiàng)基本不變；相反的這個(gè)權(quán)重項(xiàng)會(huì)有一個(gè)大的變化當(dāng)我們的預(yù)測(cè)值hθ(x(i))有大的誤差的時(shí)候（例如預(yù)測(cè)值和真實(shí)值y(i)差別非常大的時(shí)候）

我們推斷出了當(dāng)有一個(gè)訓(xùn)練樣本是的LMS算法。我們有兩種方法可以讓這個(gè)算法去適應(yīng)多于一個(gè)訓(xùn)練樣本的例子。第一種是用下面這種算法替換:

可以很容易的證明上述的更新規(guī)則算法的運(yùn)算量?jī)H僅是

?J(?)（對(duì)J的初始化定義）。??j因此這是一個(gè)簡(jiǎn)單的梯度下降算法對(duì)于原始成本函數(shù)J。這個(gè)方法注重每一個(gè)訓(xùn)練樣本在訓(xùn)練過(guò)程中的每一步，所以也被叫做“批量梯度下降”。注意，梯度下降算法容易受到局部最小值的影響，這個(gè)優(yōu)化問(wèn)題我們對(duì)于線性回歸算法只有一個(gè)目標(biāo)就是找到最合適的，因此梯度下降算法總是收斂于全局最小值。（將設(shè)學(xué)習(xí)率α不是很大）實(shí)際上，J是一個(gè)凸函數(shù)。這里我們有一個(gè)梯度下降算法的例子，是使這個(gè)二次函數(shù)取得最小值。

B

這些橢圓表示了這個(gè)二次函數(shù)的等高線。這個(gè)紫色的線條表示的是取得最小值的軌跡，T初始化（48，30）。這個(gè)X標(biāo)識(shí)出來(lái)在圖中在梯度下降算法計(jì)算出的每個(gè)θ值，并且用實(shí)線連接起來(lái)。

當(dāng)我們運(yùn)行批量梯度算法去計(jì)算θ在我們以前的數(shù)據(jù)集去估計(jì)房子的價(jià)格使用房子的價(jià)格和房子面積的函數(shù)，我們得到?0=71.27，?1=0.1345.如果我們把 h?(x)當(dāng)作x（面積）的函數(shù)，使用訓(xùn)練樣本中的數(shù)據(jù)，我們能得到下面這張圖：

如果臥室數(shù)量也被當(dāng)作一組輸入變量，我們得到?0=89.60，?1=0.1392，?2=-8.738.上面這些結(jié)果都是我們使用批量梯度算法得到的。對(duì)于批量梯度算法算法可以有其他的選擇使他更好的預(yù)測(cè)。考慮一下下面這個(gè)算法：

在這個(gè)算法中，我們重復(fù)的使用梯度下降算法在訓(xùn)練樣本中，并且每一次我們遇到一個(gè)訓(xùn)練樣本，我們更新這個(gè)權(quán)重僅僅根據(jù)每一次對(duì)訓(xùn)練樣本訓(xùn)練的梯度誤差。這種算法叫做“隨機(jī)梯度下降法”（也叫做增量梯度下降法。）然而批量梯度下降法必須要掃描全部的訓(xùn)練集在進(jìn)行每一步之前----一個(gè)多余的操作如果m特別大的話----隨即梯度下降算法可以隨時(shí)開(kāi)始，并且可以繼續(xù)進(jìn)行下一步在他跟蹤的樣本上。一般情況下，隨即梯度下降算法會(huì)比批量梯度算法更快的使的θ“接近”最小值。（注意雖然根本不可能收斂到最小值，并且這個(gè)權(quán)重θ會(huì)一直震蕩在使的J(θ)取得最小值的θ的附近；但是實(shí)際上大多數(shù)在最小值附近的值已經(jīng)可以取了，已經(jīng)可以近似的使函數(shù)取得最小值了）。更多的原因，特別是當(dāng)這個(gè)訓(xùn)練集很大的時(shí)候，隨即梯度下降算法通常是優(yōu)先選擇相對(duì)于批量梯度算法。The normal equations 梯度下降法給出了一種方法最小化J。讓我們討論另一種方法最小化J，這個(gè)算法明確的求解最小化并且不依賴于迭代算法。使用這種方法，我們通過(guò)計(jì)算J的導(dǎo)數(shù)來(lái)最小化J并且使他們等于0。為了不在運(yùn)算過(guò)程中寫(xiě)過(guò)多的代數(shù)和大量的矩陣，這里對(duì)使用的計(jì)算矩陣的符號(hào)做一些介紹。

2.1 Matrix derivatives、定義一個(gè)函數(shù)，從m*n的矩陣到實(shí)數(shù)的映射，（f：Rm*n?R）定義f關(guān)于矩陣A的導(dǎo)數(shù)：

因此梯度?Af(A)本身就是

?A11?2f一個(gè)m*n維的矩陣，對(duì)于（i,j）的元素就是。舉個(gè)例子，假設(shè)A=??Aij?A212*2維的矩陣，并且函數(shù)f：R2*2A12??是一個(gè)A22??R 已給定為：f(A)?32A11?5A12?A21A22 2這里Aij表示矩陣

A中（i,j）維的元素。我們得到：

這里介紹一下跡算子記作“tr”。對(duì)于一個(gè)n*n維的矩陣A，A的跡就是矩陣主對(duì)角線上元素 的和trA??Ai?1nii。如果a是一個(gè)實(shí)數(shù)（例如a是一個(gè)1*1維的矩陣），tra=a。（如果你以前么有見(jiàn)到過(guò)這個(gè)運(yùn)算符號(hào)，你可以矩陣A的跡看作tr（A）或者對(duì)矩陣A求他的跡。）

跡運(yùn)算同樣適用于兩個(gè)矩陣A和B因此AB如果都是方陣，我們可以得到 tr(AB)=tr(BA)。下面是這個(gè)公式的一些推論，我們有如下：

下面對(duì)于跡的操作的一些公式也很同意證明。這里A和B都是方陣，并且a是一個(gè)實(shí)數(shù)

我們下面給出一些矩陣導(dǎo)數(shù)的跡推論并不進(jìn)行證明（本節(jié)中不會(huì)用到）。等式（4）僅僅適用于非奇異方陣A，|A|表示A的行列式。

為了使我們的矩陣符號(hào)更具體，讓我們現(xiàn)在詳細(xì)解釋第一類方程的意義。假設(shè)我們有一些固定的矩陣B∈Rn*m.我們可以定義一個(gè)函數(shù)f：Rn*mn*m→R根據(jù)F（a）= tr(AB)。注意，這個(gè)定義是有意義的，因?yàn)槿绻鸄?R確實(shí)是從Rn*m，然后AB是一個(gè)方陣，我們可以將其應(yīng)用到它，因此f到R的映射。我們可以運(yùn)用我們的定義矩陣導(dǎo)數(shù)找到?Af(A)，m*n矩陣。

T方程（1）在上述情況下，該矩陣的輸入（i，j）的值可以由B給出或者等價(jià)于Bji。方程的證明（1-3）是相當(dāng)簡(jiǎn)單的，留下作為給讀者的練習(xí)。方程（4）可以使用伴隨矩陣和矩陣的逆來(lái)推導(dǎo)。2.2 Least squares revisited

隨著矩陣導(dǎo)數(shù)，我們開(kāi)始繼續(xù)在封閉的模型中尋找θ使的J（θ）取得最小值，開(kāi)始先把J重新寫(xiě)入向量矩陣中。

給定一個(gè)訓(xùn)練集，定義m*n維的矩陣X（實(shí)際上是m*（n+1）維的，如果算上偏置項(xiàng)）在矩陣中包含給定的訓(xùn)練集的輸入值在

同時(shí)，定義y為一個(gè)一維的列向量，值為所有的目標(biāo)值?

現(xiàn)在，從我們可以很容易證明：

運(yùn)用定理

可以得到

最后，為了最小化J，我們尋找J(θ)關(guān)于θ的導(dǎo)數(shù)。結(jié)合式子（2）和（3），我們發(fā)現(xiàn)

因此有：

AT??,B?BT?XXT

在第三步中，我們使用了實(shí)數(shù)的跡就是實(shí)數(shù)本身這個(gè)定理；第四步我們使用了在第五步中我們對(duì)式5使用AT??,B?BT?XXT和C=I和公式1.為了最tr(A)?tr(AT)，小化J，我們使他的導(dǎo)數(shù)等于0可以得到如下等式：

因此，使的J(θ)最小的θ的值就可以有下式得到： Probabilistic interpretation

當(dāng)?shù)玫揭粋€(gè)回歸問(wèn)題時(shí)，什么時(shí)候使用線性回歸，什么時(shí)候選擇最小二乘算法去計(jì)算價(jià)值函數(shù)J？本節(jié)中，我們會(huì)給出一系列的假設(shè)來(lái)描述什么情況下使用最小二乘算法最合適。

假設(shè)我們的目標(biāo)變量和輸入變量的關(guān)系是：

xi?x

?i表示誤差項(xiàng)（就像我們預(yù)測(cè)房?jī)r(jià)例子中有很多其他因素比如地理位置，房屋年齡等這些我們考慮外的對(duì)房?jī)r(jià)有影響的因素我們沒(méi)有計(jì)算進(jìn)去），或者隨機(jī)噪聲。我們進(jìn)一步假定?i是分散的IID(independently and identically distributed)根據(jù)高斯分布（也叫正態(tài)分布）均值為0方差為?2。我們可以寫(xiě)出這個(gè)?i的定義?i?N(0,?2)。也就是說(shuō)?i的概率密度是給定的

這表明：

說(shuō)明yi的分布是由xi和θ控制的。注意，我們不能單獨(dú)以θ為的條件，因?yàn)棣炔皇且粋€(gè)隨機(jī)值。我們也能把這個(gè)式子寫(xiě)成另外一種形式：

給定X（設(shè)定好的矩陣包含所有的輸入變量xi）和θ，如何求的yi的分布呢？這個(gè)可能的值就是。這個(gè)值代表y（或者X）的一個(gè)關(guān)于θ的函數(shù)。當(dāng)我們明確

?的理解這個(gè)函數(shù)之后，我們給他起一個(gè)名字叫做似然函數(shù)：

注意由于這個(gè)偏差項(xiàng)?i的獨(dú)立性（同樣的y和xi之間）這個(gè)式子也可以寫(xiě)成

i

現(xiàn)在給定這個(gè)概率模型關(guān)于y和xi，怎么去選擇最合理的方法去最好的求解我們想

i要得到的參數(shù)θ？這個(gè)極大似然函數(shù)使的我們能盡可能的取得最好的θ。我們應(yīng)該選擇θ使的L(θ)最大。

最大化L(θ)，我們可以最大化任意的單調(diào)遞增函數(shù)L(θ)。特別的，求他的派生物（這里表示的是對(duì)數(shù)）的最大值回事比較簡(jiǎn)單的方法

：

因此，最大化相當(dāng)于最小化

我們認(rèn)出了這個(gè)J(θ)就是我們的最小二乘法函數(shù)。

小結(jié)：在前面的概率模型計(jì)算中，使用最小二乘算法去尋找θ使得極大似然函數(shù)取得最大值。這個(gè)是一種比較合理的方法使用最小二乘法算法求解問(wèn)題。（注意雖然這個(gè)方法是合理的和比較好的但是一定還有更加合適的方法去使用這個(gè)方法）

注意，在我們前面的討論中，我們最終的選擇θ并沒(méi)有使用到偏差項(xiàng)，而且也是因?yàn)榧词蛊铐?xiàng)我們不知道，計(jì)算的結(jié)果仍然是一樣的。這個(gè)結(jié)論我們會(huì)在后續(xù)討論指數(shù)族和廣義線性模型的時(shí)候用到。Locally weighted linear regression（局部加權(quán)線性回歸）

考慮這個(gè)問(wèn)題從x屬于R預(yù)測(cè) y。這個(gè)最左邊的模型顯示出這個(gè)預(yù)測(cè)得到的結(jié)果函數(shù)。我們看到這個(gè)數(shù)據(jù)并沒(méi)有全部落到這個(gè)線上，所以說(shuō)這個(gè)預(yù)測(cè)結(jié)果并不是很。

相反的，如果我們給這個(gè)函數(shù)加上一個(gè)額外的變量x2，預(yù)測(cè)函數(shù)則為，然后我們得到一個(gè)比剛才那個(gè)更適給定數(shù)據(jù)的預(yù)測(cè)函數(shù)（中間這幅圖）。看起來(lái)好像我們加上去的變量越多這個(gè)模型越好。然而，加上太多的模型也是危險(xiǎn)的對(duì)于我們的預(yù)測(cè)來(lái)說(shuō)：右邊這個(gè)模型是一個(gè)使用了五個(gè)自變量的預(yù)測(cè)模型。我們可以看到這個(gè)模型完美的適和我們給定的數(shù)據(jù)，我們不能期待這個(gè)是一個(gè)好的預(yù)測(cè)模型對(duì)于使用房子的面積去預(yù)測(cè)房子的價(jià)格。在沒(méi)有正式定義這些模型之前，我們可以看到左邊這個(gè)模型是低擬合度的例子-----給定訓(xùn)練集中的數(shù)據(jù)離我們給出的預(yù)測(cè)函數(shù)相差太多----右邊這個(gè)模型是過(guò)擬合度的例子。（本節(jié)課的后面，我們會(huì)給出這些定義的概念，并且給更加詳細(xì)的定義去判斷一個(gè)預(yù)測(cè)模型是好還是壞）

正如前面討論的和在上面例子中展示的，特征變量的選擇直接決定了一個(gè)學(xué)習(xí)模型的好壞。（當(dāng)我們討論模型選擇時(shí)候，我們會(huì)看到模型會(huì)自動(dòng)選擇特征變量。）在這部分，我們來(lái)討論一下局部加權(quán)線性回歸算法（LWR）假設(shè)有足夠的訓(xùn)練數(shù)據(jù)，特征變量未鑒定。這個(gè)方法是聰明的，你會(huì)得到機(jī)會(huì)去發(fā)現(xiàn)這個(gè)算法的一些優(yōu)異之處在你的作業(yè)中。

在經(jīng)典線性回歸算法中，我們?cè)谝粋€(gè)點(diǎn)x做出預(yù)測(cè)我們將會(huì)：

1、尋找使

2、輸出?Tx

相反的在局部加權(quán)線性回歸算法中我們會(huì)這樣做：

最小化的θ

1、尋找使T2、輸出?x

最小的θ

在這里是一些非負(fù)的權(quán)值。更直接的如果是一個(gè)非常大的特殊值關(guān)于i的，之后

更小。如果

很小，之在選擇θ的過(guò)程中，我們會(huì)盡最大努力去使后計(jì)算過(guò)程中的誤差項(xiàng)可以直接被忽略在尋找的過(guò)程中。

一個(gè)公平的標(biāo)準(zhǔn)選著權(quán)值的公式是：

i注意那些我們將要預(yù)測(cè)x并且對(duì)特別點(diǎn)x有依賴的權(quán)值。特別的是如果|x?x|很小，這個(gè)

i權(quán)值就會(huì)接近1；并且如果|x?x|很大，這個(gè)權(quán)值就會(huì)很小。因此，θ被選來(lái)作為更高的“權(quán)重”去減小誤差使的取得最合適的值在x偏差較大的點(diǎn)上。（注意，而權(quán)重公式外觀類似于高斯分布的密度，形成W是不直接跟高斯有任何聯(lián)系，和特別是W不是隨機(jī)變量，正態(tài)分布或其他參數(shù)τ控制。）如何快速的訓(xùn)練樣本的重量脫落的x距離從查詢點(diǎn)X；τ叫做帶寬參數(shù)，而且也是你會(huì)在你的家庭作業(yè)見(jiàn)到的東西。

局部加權(quán)線性回歸是我們看到的非參數(shù)化算法的第一個(gè)例子。（未加權(quán)）線性回歸算法，我們前面看到的是一個(gè)眾所周知的參數(shù)學(xué)習(xí)算法，因?yàn)樗幸粋€(gè)固定的，有限數(shù)量的參數(shù)（θ），這是適合這個(gè)數(shù)據(jù)的。一旦我們適應(yīng)θ并且儲(chǔ)存了他，我們不再需要保持訓(xùn)練數(shù)據(jù)進(jìn)行未來(lái)預(yù)測(cè)。相反，使用局部加權(quán)線性回歸預(yù)測(cè)，我們需要整個(gè)訓(xùn)練集。術(shù)語(yǔ)“非參數(shù)化”（粗略）指的是，我們需要保持的東西的量，以表示的假設(shè)小時(shí)增長(zhǎng)線性的訓(xùn)練集的大小。

Part II Classification and logistic Regression(分類和線性回歸)

現(xiàn)在讓我們來(lái)分析分類問(wèn)題。這就和回歸問(wèn)題一樣，除了我們現(xiàn)在要預(yù)測(cè)的值y僅僅是一些小的離散的值之外。現(xiàn)在開(kāi)始，我們將會(huì)把目光放在二元分類問(wèn)題上，也就是y只能去兩個(gè)值 0 和 1。（我們?cè)谶@說(shuō)的簡(jiǎn)單的形式可以推廣到更加復(fù)雜的形式）。例如，如果我們想要建立一個(gè)垃圾郵件分類系統(tǒng)，x是郵件的特征，y是1代表是垃圾郵件，是0則代表不是。0也叫做否定類，1也叫做肯定類，一些情況下也用“+、-”來(lái)表示。給定x，y也被叫做訓(xùn)練集的標(biāo)簽。Logistic regression 我們可以解決分類問(wèn)題不論y是否是離散值，并且用以前的線性回歸算法去試著預(yù)測(cè)我們給定x的y值。然而，非常容易證明這個(gè)方法是不足的。更直觀的是，他對(duì)于h?(x)沒(méi)有什么意義當(dāng)值大于1或者小于0的時(shí)候當(dāng)我們界定y?{0,1}。

為了解決這個(gè)問(wèn)題，我們改變這個(gè)假設(shè)函數(shù)h?(x)。我們選擇

邏輯函數(shù)，下面是他的函數(shù)圖像

注意g(z)趨近1當(dāng)z趨近于?，并且g(z)趨近于0當(dāng)z趨近于-?。另外g(z)和h(x)的值域都是[0,1]。我們約定x0?1，因此

從現(xiàn)在開(kāi)始，我們都假定g是已知的。其他函數(shù)如果是0—1之間的連續(xù)函數(shù)也是可以使用的，但是有兩個(gè)原因我們將會(huì)看到（當(dāng)我們討論GLMs是，還有討論生成學(xué)習(xí)算法的時(shí)候）選擇他做回歸函數(shù)是最合適的。在開(kāi)始下一節(jié)千，這里有一個(gè)重要的推論關(guān)于sigmoid函數(shù)的導(dǎo)數(shù)：

因此，給定這個(gè)邏輯回歸模型，怎么去找一個(gè)適合的θ？接下來(lái)我們將會(huì)使用最小二乘法和極大似然估計(jì)相結(jié)合來(lái)求出。將會(huì)結(jié)合概率和極大似然函數(shù)來(lái)球權(quán)重參數(shù)。

我們假設(shè)：

注意這個(gè)也可以簡(jiǎn)單的寫(xiě)為 假定給定的m個(gè)樣本之間都是相互獨(dú)立的，我們可以得到如下極大似然函數(shù)：

像以前一樣很容易對(duì)這個(gè)似然函數(shù)的對(duì)數(shù)求最大值：

怎么樣去最大化這個(gè)似然函數(shù)呢？像在線性回歸里面所做的一樣，我們可以使用梯度上升法。寫(xiě)成向量的形式，更新式子是

（注意這個(gè)公式中的正負(fù)號(hào)還有我們是要求的是最大值而不是最小值）。首先在一個(gè)訓(xùn)練樣本（x，y）上使用這個(gè)公式，并且對(duì)他的對(duì)數(shù)求導(dǎo)：

我們使用公式

。求出來(lái)的就是隨即梯度更新規(guī)則：

如果我們拿這個(gè)和LMS更新規(guī)則比較，我們會(huì)發(fā)現(xiàn)這兩個(gè)是完全一樣的；但是這是不一樣的算法得到的，因?yàn)閔?(xi)現(xiàn)在是有非線性的函數(shù)?Txi定義的。盡管如此，我們還是很好奇為什么不一樣的算法和不一樣的學(xué)習(xí)方法會(huì)得到同樣的結(jié)果。這是偶然嗎？或者有更深層次的原因在里面，我們將會(huì)解答這個(gè)問(wèn)題在GLM模型中。6 Digression: The perceptron learning algorithm（感知學(xué)習(xí)算法）

我們現(xiàn)在額外的增加一個(gè)算法由于一些歷史愛(ài)好，我們將會(huì)回歸到整體之后討論學(xué)習(xí)理論的時(shí)候。試著想一下改變這個(gè)邏輯回歸模型去要求他去預(yù)測(cè)一個(gè)值是0或1或者其他。為了達(dá)到目的自然而然的從新定義g為一個(gè)閥值函數(shù)

如果我們使用

在前面作為我們的預(yù)測(cè)函數(shù)，其他都不變我們更新規(guī)則如：我們叫新的算法為感知學(xué)習(xí)算法。

在19世紀(jì)60年代，這個(gè)“感知”被認(rèn)為是一個(gè)粗陋的模型對(duì)于人腦中工作的單個(gè)神經(jīng)元。考慮到這個(gè)算法比較簡(jiǎn)單并且作為一個(gè)開(kāi)始對(duì)于我們下節(jié)理論討論做一個(gè)開(kāi)頭來(lái)講一下。注意雖然這個(gè)感知學(xué)習(xí)算法看起來(lái)和我們其他的學(xué)習(xí)算法一樣，實(shí)際上他是一個(gè)不同于邏輯回歸和最小二乘回歸類型的算法，特別的是，他很難賦予感知算法概率的應(yīng)用，或者使用最大似然估計(jì)算法去求解。Another algorithm for maximizing ?(θ)回到邏輯回歸算法g(z)使用sigmoid函數(shù)，我們接下來(lái)講解一種不一樣的算法來(lái)最小化l(?)開(kāi)始之前，我們先看一下牛頓的方法去尋找一個(gè)函數(shù)的零點(diǎn)。特別的，假設(shè)我們有一系列的函數(shù)f：R—>R，并且我們想找到一個(gè)值使的f(θ)=0。這里θ輸入R是一個(gè)實(shí)數(shù)。牛頓的方法如下：。這個(gè)方法我們可以這樣理解，選定一個(gè)值做自變量的垂線過(guò)函數(shù)上這點(diǎn)做函數(shù)的切線與函數(shù)軸交與一點(diǎn)，再過(guò)這點(diǎn)做垂線，再過(guò)這點(diǎn)做函數(shù)的切下知道找到切線斜率為零的點(diǎn)。下面是一副圖表示牛頓法的過(guò)程

在左邊這張圖中我們看到函數(shù)f畫(huà)了一條直線在y=0處。我們希望找到的θ使得f(θ)=0;這個(gè)θ的值大約是1.3。假設(shè)我們初始化這個(gè)算法定義θ=4.5.牛頓的方法是通過(guò)函數(shù)上這點(diǎn)做f的切線，并且評(píng)估這條線的值是否為0.這給我們下一個(gè)猜想的對(duì)于θ，大約是2.8.最右邊的圖指出了這個(gè)最后一次迭代的結(jié)果，這時(shí)候更新的θ大約是1.8.一陣迭代之后我們能很快的接近θ=1.3.牛頓的方法給出了一種使f(θ)=0的方法。我們?cè)趺窗堰@個(gè)應(yīng)用到我們求解l函數(shù)中？這個(gè)函數(shù)的最大值相當(dāng)于去求他的一階導(dǎo)數(shù)等于0的點(diǎn)。因此令f(θ)=l`(θ),我們能使用相同的算法去是L最大，我們得到這個(gè)更新規(guī)則：

（需要考慮的問(wèn)題：如果我們想要求一個(gè)函數(shù)的最小值而不是最大值這個(gè)算法應(yīng)該如何改進(jìn)？）

最后，在我們的邏輯回歸設(shè)定中，θ是一個(gè)向量，因此我們需要推廣牛頓法到向量級(jí)別。這個(gè)推廣的方法是把牛頓法應(yīng)用到多維中（也叫做牛頓—拉普森方法）

這里???(?)是?(?)對(duì)θ的偏導(dǎo)數(shù)，H是一個(gè)n*n的矩陣（實(shí)際上是n+1*n+1維的，我們帶上截距項(xiàng)）叫做Hessian，是由下面的式子給定：

牛頓法更加快速的收斂到最小值比著梯度下降法，并且需要更少的迭代次數(shù)接近最小值。一次牛頓迭代會(huì)花費(fèi)更大的代價(jià)比著梯度下降算法，當(dāng)他要求找到和反相一個(gè)海森矩陣的時(shí)候，但是如果n不是很大的時(shí)候，牛頓算法通常是更快的。當(dāng)牛頓算法應(yīng)用到求邏輯回歸極大似然函數(shù)的最大值的時(shí)候，這個(gè)求解方法也被叫做Fisher scoring。

Part III Generalized Linear Models（廣義線性模型）

至今為止，我們已經(jīng)看來(lái)一個(gè)回歸分析的例子和一個(gè)分類分析的例子。在兩個(gè)例子中都有一些近似的函數(shù)，2回歸分析的例子中我們有yx;??N(?,?)，在分類的例子中有yx;??Bernoulli(?)

本節(jié)我們將會(huì)展示出這些都是廣義線性模型中的一部分。我們也會(huì)推到一些其他的適用于回歸和分類問(wèn)題中的廣義線性模型。The exponential family 為了引出GLMS，我們先說(shuō)一下指數(shù)分布。我們定義一個(gè)分布是指數(shù)分布如果他可以被寫(xiě)為如下形式：

?叫做特性參數(shù)（也叫做典型參數(shù)）；T(y)是充分統(tǒng)計(jì)量（通常情況下T(y)=y），a(?)是對(duì)數(shù)劃分函數(shù)。分量e?a(?)作用是歸一化參數(shù)，確保p(y;η)的和是大于1的。

T一個(gè)復(fù)雜的選擇，a和b定義一個(gè)分布族關(guān)于參數(shù)η；當(dāng)我們改變?chǔ)堑闹禃r(shí)，我們會(huì)得到不同的分布在這個(gè)分布族里面。

現(xiàn)在看到的Bernoulli和Gaussian分布都是指數(shù)分布的一個(gè)例子。Bernoulli分布均值為υ寫(xiě)為Bernoulli（υ），指定一個(gè)分布y∈｛0，1｝，寫(xiě)成p（y=1；υ）=Φ；p（y=0；υ）=1-υ

h?(x)

當(dāng)我們改變?chǔ)缘闹担覀兊玫讲煌档腂ernoulli分布。現(xiàn)在我們證明這一類的Bernoulli分布，在例子中選擇T，a和b所以式子（6）是Bernoulli分布。我們把Bernoulli分布寫(xiě)為：

因此，特性參數(shù)由??log?1??給出。有意思的是，當(dāng)我們使用η表示υ的時(shí)候我們會(huì)得到υ=1/（1+e^（-η））。這個(gè)看起來(lái)是不是和sigmoid函數(shù)很像。這將會(huì)再次被提到當(dāng)我們把邏輯回歸分析看作GLM時(shí)。為了完成Bernoulli分布是指數(shù)分布的一種的猜想，我們進(jìn)一步有：

這表明選擇適當(dāng)?shù)腡，a和b的時(shí)候，Bernoulli分布可以被寫(xiě)成式（6）的形式。我們進(jìn)一步來(lái)討論Gaussian分布。回想一下，當(dāng)我們推導(dǎo)線性回歸時(shí)，?的值對(duì)我們最終選擇的θ和

2h?(x)沒(méi)有任何影響。因此我們可以選擇任意值作為?2而不去改變他的值。為了簡(jiǎn)化式子我們定義?=1.我們可以得到： 2

因此我們看到高斯分布也在指數(shù)分布族里面，當(dāng)

有許多其他分布指數(shù)的家人:多項(xiàng)分布(我們稍后將看到),在泊松分布(造型計(jì)數(shù)數(shù)據(jù);也看到問(wèn)題集);伽瑪和指數(shù)(造型連續(xù)、非負(fù)隨機(jī)變量,如時(shí)間間隔),β和狄利克雷(對(duì)概率分布),和許多更多。在下一節(jié)中,我們將描述構(gòu)建模型的一般“食譜”,y(x和θ)來(lái)自這些發(fā)行版。Constructing GLMs 假設(shè)您想要構(gòu)建一個(gè)模型來(lái)估計(jì)客戶來(lái)到你的商店的數(shù)量y(或您的網(wǎng)站上的頁(yè)面瀏覽量數(shù)量)在任何給定時(shí)刻,基于某些特性x等商店促銷,最近的廣告、天氣、讀寫(xiě)等。我們知道,泊松分布通常提供了一個(gè)好的模型數(shù)量的游客。知道了這一點(diǎn),我們?cè)趺茨芟氤鲆粋€(gè)模型問(wèn)題?幸運(yùn)的是,泊松是一個(gè)指數(shù)族分布,所以我們可以應(yīng)用一個(gè)廣義線性模型(GLM)。我們將在本節(jié)中,我們將描述一個(gè)方法構(gòu)建全球語(yǔ)言監(jiān)測(cè)模型,諸如此類的問(wèn)題。

更為普遍的是,考慮這樣一個(gè)分類或回歸問(wèn)題,我們想要預(yù)測(cè)一些隨機(jī)變量的值y作為x的函數(shù)。獲得一個(gè)漠視這個(gè)問(wèn)題,我們將進(jìn)行以下三個(gè)假設(shè)條件分布的y x和關(guān)于我們的模型:

1、y | x;θ～ExponentialFamily(η)。即。鑒于x和θ,y的分布遵循一些指數(shù)族分布,參數(shù)η。

2、鑒于x,我們的目標(biāo)是預(yù)測(cè)T的預(yù)期值x(y)。在我們的大多數(shù)示例中,我們將T(y)= y,所以這意味著我們想預(yù)測(cè)h(x)的輸出由我們學(xué)習(xí)假說(shuō)h滿足h(x)= E[y | x]。(注意,這個(gè)假設(shè)是選擇滿足h(x)邏輯回歸和線性回歸。例如,在邏輯回歸,我們有h(x)= p(y = 1 | x;θ)= 0·p(y = 0 | x;θ)+ 1·p(y = 1 | x;θ)= E[y | x;θ]。)

3、η的自然參數(shù)和輸入x相關(guān)線性:η=θT x。(或者,如果η量值,那么ηi =θTi x)。第三的這些假設(shè)似乎是最合理的,而且它可能是更好的認(rèn)為是一種“設(shè)計(jì)選擇”在我們的配方設(shè)計(jì)的漠視,而不是作為一個(gè)假設(shè)本身。這三個(gè)假設(shè)/設(shè)計(jì)的選擇將使我們能夠獲得一個(gè)非常優(yōu)雅的classof學(xué)習(xí)算法,即全球語(yǔ)言監(jiān)測(cè)機(jī)構(gòu),有很多可取的屬性,如易于學(xué)習(xí)。此外,生成的模型往往是非常有效的模擬不同類型的分布在y;例如,我們不久將表明,邏輯回歸和普通最小二乘法都可以派生的漠視。9.1 Ordinary Least Squares 表明普通最小二乘法是一種特殊的GLM的家庭模型,考慮設(shè)置目標(biāo)變量y(也稱為響應(yīng)變量在GLM術(shù)語(yǔ))是連續(xù)的,而且我們模型x y給定的條件分布為高斯N(μ,σ2)。(在這里,μ可能取決于x)。所以,我們讓ExponentialFamily(η)分布是高斯分布。正如我們之前看到的,配方的高斯指數(shù)族分布,我們有μ=η。所以,我們有 上面的第一個(gè)假設(shè)2,平等;第二個(gè)平等的合集y | x;θ～N(μ,σ2),所以其預(yù)期值等于μ;第三個(gè)平等從假設(shè)1(和我們先前推導(dǎo)表明,μ=η配方的高斯指數(shù)族分布),和最后一個(gè)平等遵循從假設(shè)3。

9.2 Logistic Regression 我們現(xiàn)在考慮邏輯回歸。我們感興趣的是二進(jìn)制分類,因此y∈{ 0,1 }。鑒于y binary-valued,因此自然選擇的伯努利家族分布模型的條件分布x y。在我們制定的伯努利分布指數(shù)族分布,我們有υ= 1 /(1 + e?)。此外,請(qǐng)注意,如果x,y |θ～伯努利(υ),然后E x y |,θ=υ。similarderivation后,作為一個(gè)普通的最小二乘法,我們得到:

所以,這給了我們假設(shè)函數(shù)形式的h(x)= 1 /(1 + e?T x)。如果你以前想知道我們想出了物流功能的形式1 /(1 + e?z),這給了一個(gè)答案:一旦我們假設(shè)x y條件是伯努利,它產(chǎn)生的后果的漠視和指數(shù)族分布的定義。引入更多的術(shù)語(yǔ)中,該函數(shù)g給分配的平均作為自然參數(shù)的函數(shù)(g(η)= E(T(y);η))被稱為規(guī)范響應(yīng)函數(shù)。其逆,g?1,稱為規(guī)范化鏈接功能。因此,規(guī)范響應(yīng)函數(shù)為高斯家庭只是識(shí)別功能,和規(guī)范化是伯努利響應(yīng)函數(shù) 9.3 Softmax Regression 讓我們看看一個(gè)GLM的例子。考慮一個(gè)分類問(wèn)題的反應(yīng)變量y可以承擔(dān)任何一個(gè)k值,因此y∈{ 1 2,。、k}。例如,而不是電子郵件分類到兩類垃圾郵件或非垃圾郵件，將是一個(gè)二元分類問(wèn)題,我們可能需要分類成三個(gè)類,如垃圾郵件、個(gè)人郵件,與工作相關(guān)的郵件。響應(yīng)變量仍然是離散的,但現(xiàn)在能超過(guò)兩個(gè)值。我們將因此分布式根據(jù)多項(xiàng)分布模型。

允許派生的GLM造型這種類型的多項(xiàng)數(shù)據(jù)。這樣做,我們將首先表達(dá)了多項(xiàng)指數(shù)族分布。參數(shù)化一個(gè)多項(xiàng)式在k可能的結(jié)果,可以使用υ1 k參數(shù),。,υk指定每個(gè)結(jié)果的概率。然而,這些參數(shù)將是多余的,或者更正式,他們不會(huì)獨(dú)立(因?yàn)橹廊魏蝛?1υi獨(dú)特的決定 最后一個(gè),因?yàn)樗麄儽仨殱M足Pkiυi = 1 = 1)。所以,我們將參數(shù)化多項(xiàng)式只有k?1參數(shù),υ1,。,υk?1,υi = p(y =我;υ)和p(y = k;υ)= 1?Pk?1 i = 1υi。記數(shù)的便利,我們還將讓?duì)詋 = 1?Pk?1 i = 1υi,但我們應(yīng)該記住,這不是一個(gè)參數(shù),而且它完全υ1規(guī)定,。,υk?1。

表達(dá)多項(xiàng)指數(shù)族分布,我們將定義T(y)∈R^k?1如下: 與我們之前的例子,在這里我們沒(méi)有T(y)= y;此外,T(y)現(xiàn)在是一個(gè)k?1維向量,而不是一個(gè)實(shí)數(shù)。我們將編寫(xiě)(T(y))我表示的第i個(gè)元素的向量T(y)。我們介紹一個(gè)非常有用的符號(hào)。一個(gè)指標(biāo)函數(shù)1 {·}就值1如果它的參數(shù)是正確的,和0(1 {真正} = 1,1 {假} = 0)。例如,1 { 2 = 3 } = 0和1 { 3 =5?2 } = 1。所以,我們還可以寫(xiě)T之間的關(guān)系(y)和y(T(y)){ y =我} i = 1。(繼續(xù)閱讀之前,請(qǐng)確保你明白為什么這是真的!)進(jìn)一步,我們有E[(T(y))我]= P(y =我)=υi。

現(xiàn)在,我們可以證明這個(gè)多項(xiàng)式指數(shù)家族的一員，有如下：

至此我們制定的多項(xiàng)指數(shù)族分布。

鏈接函數(shù)給出了for i= 1,?,k)

為了方便起見(jiàn),我們也定義ηk=log(υk /υk)= 0 =。逆函數(shù)并獲得響應(yīng)函數(shù)的聯(lián)系,因此,我們有

這意味著υk = 1 / Pki = 1 ei,可代替回方程(7)給響應(yīng)函數(shù) 這個(gè)函數(shù)映射η的υ的叫做將softmax功能。

完成我們的模型,我們使用假設(shè)3,鑒于ηi的早些時(shí)候,x的線性相關(guān)。所以,ηi =θTi x(因?yàn)槲? 1,。θ1,k?1),。,θk?1∈Rn + 1是我們的模型的參數(shù)。記數(shù)的方便,我們還可以定義θk = 0,以便ηk =θT k x = 0,鑒于之前。因此,我們的模型假設(shè)的條件分布ygiven x等于

這個(gè)模型,這也適用于分類問(wèn)題y∈{ 1,?k },叫做softmax回歸。這是一個(gè)邏輯回歸的概括。

我們的假設(shè)將輸出

換句話說(shuō),我們的假設(shè)將輸出概率估計(jì)p(y =我| x;θ),為每一個(gè)值的我= 1,。k。(盡管h(x)如上定義只是k?1維,顯然p(y = x k |;θ)可以獲得1?Pk?1 i = 1υi)。最后,讓我們討論參數(shù)擬合。類似于我們最初派生的普通最小二乘法和邏輯回歸,如果我們有一個(gè)訓(xùn)練集m的例子{(x(i),y(i));i= 1,?,m },愿學(xué)習(xí)的參數(shù)θi這個(gè)模型中,我們將首先寫(xiě)下log-likelihood

獲得第二行以上,我們定義用于p(y | x;θ)給出了方程(8)。我們現(xiàn)在可以獲得的最大似然估計(jì)的參數(shù)通過(guò)最大化?(θ)θ,使用梯度上升或牛頓法等方法。

第五篇：機(jī)器學(xué)習(xí)報(bào)告

機(jī)器學(xué)習(xí)總結(jié)報(bào)告

劉皓冰

大部分人錯(cuò)誤地以為機(jī)器學(xué)習(xí)是計(jì)算機(jī)像人一樣去學(xué)習(xí)。事實(shí)上，計(jì)算機(jī)是死的，怎么可能像人類一樣“學(xué)習(xí)”呢，機(jī)器學(xué)習(xí)依靠的是數(shù)學(xué)，更確切地說(shuō)是靠統(tǒng)計(jì)。

如果我們讓計(jì)算機(jī)工作，是給它一串指令，然后計(jì)算機(jī)會(huì)遵照這個(gè)指令一步步執(zhí)行下去，有因有果，非常明確。但這種方式在機(jī)器學(xué)習(xí)中是行不通的。機(jī)器學(xué)習(xí)是不會(huì)接受你輸入的指令的，它接受的是你輸入的數(shù)據(jù)。也就是說(shuō)，機(jī)器學(xué)習(xí)是一種讓計(jì)算機(jī)利用數(shù)據(jù)而不是指令來(lái)進(jìn)行各種工作的方法。這聽(tīng)起來(lái)非常不可思議，但結(jié)果上卻是非常可行的。“統(tǒng)計(jì)”思想將在你學(xué)習(xí)“機(jī)器學(xué)習(xí)”相關(guān)理念時(shí)無(wú)時(shí)無(wú)刻不伴隨，相關(guān)而不是因果的概念將是支撐機(jī)器學(xué)習(xí)能夠工作的核心概念。

依據(jù)數(shù)據(jù)所做的判斷跟機(jī)器學(xué)習(xí)的思想根本上是一致的。機(jī)器學(xué)習(xí)方法是計(jì)算機(jī)利用已有的數(shù)據(jù)(輸入)，得出了某種模型，并利用此模型預(yù)測(cè)未來(lái)(輸出)的一種方法。從數(shù)據(jù)中學(xué)得模型的過(guò)程稱為“學(xué)習(xí)”（learning）或“訓(xùn)練”（training），這個(gè)過(guò)程通過(guò)執(zhí)行某個(gè)學(xué)習(xí)算法來(lái)完成。訓(xùn)練過(guò)程中使用的數(shù)據(jù)成為“訓(xùn)練數(shù)據(jù)”（training data），其中每個(gè)樣本稱為一個(gè)“訓(xùn)練樣本”（training sample），訓(xùn)練樣本組成的集合稱為“訓(xùn)練集“（training set）。學(xué)得模型對(duì)應(yīng)了關(guān)于數(shù)據(jù)的某種潛在的規(guī)律，因此亦稱”假設(shè)“（hypothesis）；這種潛在規(guī)律自身，則稱為”真相“或”真實(shí)“（ground-truth），學(xué)習(xí)過(guò)程就是為了找出或逼近真相。模型有時(shí)也被稱為”學(xué)習(xí)器“（learner），可看作學(xué)習(xí)算法在給定數(shù)據(jù)和參數(shù)空間上的實(shí)例化。

若欲預(yù)測(cè)的是離散值則此類學(xué)習(xí)任務(wù)被稱為“分類”；若欲預(yù)測(cè)的是連續(xù)值則此類學(xué)習(xí)任務(wù)稱為“回歸”；對(duì)只涉及兩個(gè)類別的“二分類”任務(wù)，通常稱其中一個(gè)類為“正類”，另一個(gè)類為“反類”；涉及多個(gè)類別時(shí)，則稱為“多分類”任務(wù)。

模型是否準(zhǔn)確依賴與數(shù)據(jù)。如果我的數(shù)據(jù)越多，我的模型就越能夠考慮到越多的情況，由此對(duì)于新情況的預(yù)測(cè)效果可能就越好。這是機(jī)器學(xué)習(xí)界“數(shù)據(jù)為王”思想的一個(gè)體現(xiàn)。一般來(lái)說(shuō)(不是絕對(duì))，數(shù)據(jù)越多，最后機(jī)器學(xué)習(xí)生成的模型預(yù)測(cè)的效果越好。

機(jī)器學(xué)習(xí)里面有非常多的經(jīng)典算法，每種算法都能形成一個(gè)模型。下面在簡(jiǎn)要介紹一下機(jī)器學(xué)習(xí)中的經(jīng)典代表方法。重點(diǎn)介紹的是這些方法內(nèi)涵的思想。

1、回歸算法 在大部分機(jī)器學(xué)習(xí)課程中，回歸算法都是介紹的第一個(gè)算法。原因有兩個(gè)：一.回歸算法比較簡(jiǎn)單，介紹它可以讓人平滑地從統(tǒng)計(jì)學(xué)遷移到機(jī)器學(xué)習(xí)中。二.回歸算法是后面若干強(qiáng)大算法的基石，如果不理解回歸算法，無(wú)法學(xué)習(xí)那些強(qiáng)大的算法。回歸算法有兩個(gè)重要的子類：即線性回歸和邏輯回歸。

線性回歸一般使用“最小二乘法”來(lái)求解。“最小二乘法”的思想是這樣的，假設(shè)我們擬合出的直線代表數(shù)據(jù)的真實(shí)值，而觀測(cè)到的數(shù)據(jù)代表?yè)碛姓`差的值。為了盡可能減小誤差的影響，需要求解一條直線使所有誤差的平方和最小。最小二乘法將最優(yōu)問(wèn)題轉(zhuǎn)化為求函數(shù)極值問(wèn)題。函數(shù)極值在數(shù)學(xué)上我們一般會(huì)采用求導(dǎo)數(shù)為0的方法。但這種做法并不適合計(jì)算機(jī)，可能求解不出來(lái)，也可能計(jì)算量太大。計(jì)算機(jī)科學(xué)界專門有一個(gè)學(xué)科叫“數(shù)值計(jì)算”，專門用來(lái)提升計(jì)算機(jī)進(jìn)行各類計(jì)算時(shí)的準(zhǔn)確性和效率問(wèn)題。例如，著名的“梯度下降”以及“牛頓法”就是數(shù)值計(jì)算中的經(jīng)典算法，也非常適合來(lái)處理求解函數(shù)極值的問(wèn)題。梯度下降法是解決回歸模型中最簡(jiǎn)單且有效的方法之一。

邏輯回歸是一種與線性回歸非常類似的算法，但是，從本質(zhì)上講，線型回歸處理的問(wèn)題類型與邏輯回歸不一致。線性回歸處理的是數(shù)值問(wèn)題，也就是最后預(yù)測(cè)出的結(jié)果是數(shù)字，例如預(yù)測(cè)一所房子大約可以買多少錢。而邏輯回歸屬于分類算法，也就是說(shuō)，邏輯回歸預(yù)測(cè)結(jié)果是離散的分類，例如判斷腫瘤是惡性還是良性等等。實(shí)現(xiàn)方面的話，邏輯回歸只是對(duì)對(duì)線性回歸的計(jì)算結(jié)果加上了一個(gè)Sigmoid函數(shù)，將數(shù)值結(jié)果轉(zhuǎn)化為了0到1之間的概率(Sigmoid函數(shù)的圖像一般來(lái)說(shuō)并不直觀，你只需要理解對(duì)數(shù)值越大，函數(shù)越逼近1，數(shù)值越小，函數(shù)越逼近0)，接著我們根據(jù)這個(gè)概率可以做預(yù)測(cè)，例如概率大于0.5，腫瘤就是惡性的等等。

2、神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)(也稱之為人工神經(jīng)網(wǎng)絡(luò)，ANN)算法是80年代機(jī)器學(xué)習(xí)界非常流行的算法，不過(guò)在90年代中途衰落。現(xiàn)在，攜著“深度學(xué)習(xí)”之勢(shì)，神經(jīng)網(wǎng)絡(luò)重裝歸來(lái)，重新成為最強(qiáng)大的機(jī)器學(xué)習(xí)算法之一。

神經(jīng)網(wǎng)絡(luò)的誕生起源于對(duì)大腦工作機(jī)理的研究。早期生物界學(xué)者們使用神經(jīng)網(wǎng)絡(luò)來(lái)模擬大腦。機(jī)器學(xué)習(xí)的學(xué)者們使用神經(jīng)網(wǎng)絡(luò)進(jìn)行機(jī)器學(xué)習(xí)的實(shí)驗(yàn)，發(fā)現(xiàn)在視覺(jué)與語(yǔ)音的識(shí)別上效果都相當(dāng)好。在BP算法(加速神經(jīng)網(wǎng)絡(luò)訓(xùn)練過(guò)程的數(shù)值算法)誕生以后，神經(jīng)網(wǎng)絡(luò)的發(fā)展進(jìn)入了一個(gè)熱潮。

下圖是一個(gè)簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)的邏輯架構(gòu)。在這個(gè)網(wǎng)絡(luò)中，分成輸入層，隱藏層，和輸出層。輸入層負(fù)責(zé)接收信號(hào)，隱藏層負(fù)責(zé)對(duì)數(shù)據(jù)的分解與處理，最后的結(jié)果被整合到輸出層。每層中的一個(gè)圓代表一個(gè)處理單元，可以認(rèn)為是模擬了一個(gè)神經(jīng)元，若干個(gè)處理單元組成了一個(gè)層，若干個(gè)層再組成了一個(gè)網(wǎng)絡(luò)，也就是”神經(jīng)網(wǎng)絡(luò)”。

圖神經(jīng)網(wǎng)絡(luò)的邏輯架構(gòu)

在神經(jīng)網(wǎng)絡(luò)中，每個(gè)處理單元事實(shí)上就是一個(gè)邏輯回歸模型，邏輯回歸模型接收上層的輸入，把模型的預(yù)測(cè)結(jié)果作為輸出傳輸?shù)较乱粋€(gè)層次。通過(guò)這樣的過(guò)程，神經(jīng)網(wǎng)絡(luò)可以完成非常復(fù)雜的非線性分類。

進(jìn)入90年代，神經(jīng)網(wǎng)絡(luò)的發(fā)展進(jìn)入了一個(gè)瓶頸期。其主要原因是盡管有BP算法的加速，神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過(guò)程仍然很困難。因此90年代后期支持向量機(jī)(SVM)算法取代了神經(jīng)網(wǎng)絡(luò)的地位。

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

支持向量機(jī)算法是誕生于統(tǒng)計(jì)學(xué)習(xí)界，同時(shí)在機(jī)器學(xué)習(xí)界大放光彩的經(jīng)典算法。

支持向量機(jī)算法從某種意義上來(lái)說(shuō)是邏輯回歸算法的強(qiáng)化：通過(guò)給予邏輯回歸算法更嚴(yán)格的優(yōu)化條件，支持向量機(jī)算法可以獲得比邏輯回歸更好的分類界線。但是如果沒(méi)有某類函數(shù)技術(shù)，則支持向量機(jī)算法最多算是一種更好的線性分類技術(shù)。

但是，通過(guò)跟高斯“核”的結(jié)合，支持向量機(jī)可以表達(dá)出非常復(fù)雜的分類界線，從而達(dá)成很好的的分類效果。“核”事實(shí)上就是一種特殊的函數(shù)，最典型的特征就是可以將低維的空間映射到高維的空間。

上述機(jī)器學(xué)習(xí)算法均為監(jiān)督學(xué)習(xí)算法。監(jiān)督學(xué)習(xí)，就是人們常說(shuō)的分類回歸，通過(guò)已有的訓(xùn)練樣本（即已知數(shù)據(jù)以及其對(duì)應(yīng)的輸出）去訓(xùn)練得到一個(gè)最優(yōu)模型（這個(gè)模型屬于某個(gè)函數(shù)的集合，最優(yōu)則表示在某個(gè)評(píng)價(jià)準(zhǔn)則下是最佳的），再利用這個(gè)模型將所有的輸入映射為相應(yīng)的輸出。在人對(duì)事物的認(rèn)識(shí)中，我們從孩子開(kāi)始就被大人們教授這是貓啊、那是狗啊、那是桌子啊，等等。我們所見(jiàn)到的景物就是輸入數(shù)據(jù)，而大人們對(duì)這些景物的判斷結(jié)果（是房子還是鳥(niǎo)啊）就是相應(yīng)的輸出。當(dāng)我們見(jiàn)識(shí)多了以后，腦子里就慢慢地得到了一些泛化的模型，這就是訓(xùn)練得到的那個(gè)（或者那些）函數(shù)，從而不需要大人在旁邊指點(diǎn)的時(shí)候，我們也能分辨的出來(lái)哪些是貓，哪些是狗。無(wú)監(jiān)督學(xué)習(xí)則是另一種研究的比較多的學(xué)習(xí)方法，它與監(jiān)督學(xué)習(xí)的不同之處，在于我們事先沒(méi)有任何訓(xùn)練樣本，而需要直接對(duì)數(shù)據(jù)進(jìn)行建模。這聽(tīng)起來(lái)似乎有點(diǎn)不可思議，但是在我們自身認(rèn)識(shí)世界的過(guò)程中很多處都用到了無(wú)監(jiān)督學(xué)習(xí)。比如我們?nèi)⒂^一個(gè)畫(huà)展，我們完全對(duì)藝術(shù)一無(wú)所知，但是欣賞完多幅作品之后，我們也能把它們分成不同的派別（比如哪些更朦朧一點(diǎn)，哪些更寫(xiě)實(shí)一些，即使我們不知道什么叫做朦朧派，什么叫做寫(xiě)實(shí)派，但是至少我們能把他們分為兩個(gè)類）。無(wú)監(jiān)督學(xué)習(xí)里典型的例子就是聚類了。聚類的目的在于把相似的東西聚在一起，而我們并不關(guān)心這一類是什么。因此，一個(gè)聚類算法通常只需要知道如何計(jì)算相似度就可以開(kāi)始工作了。

那么，什么時(shí)候應(yīng)該采用監(jiān)督學(xué)習(xí)，什么時(shí)候應(yīng)該采用非監(jiān)督學(xué)習(xí)呢？一種非常簡(jiǎn)單的回答就是從定義入手，如果我們?cè)诜诸惖倪^(guò)程中有訓(xùn)練樣本，則可以考慮用監(jiān)督學(xué)習(xí)的方法；如果沒(méi)有訓(xùn)練樣本，則不可能用監(jiān)督學(xué)習(xí)的方法。但是事實(shí)上，我們?cè)卺槍?duì)一個(gè)現(xiàn)實(shí)問(wèn)題進(jìn)行解答的過(guò)程中，即使我們沒(méi)有現(xiàn)成的訓(xùn)練樣本，我們也能夠憑借自己的雙眼，從待分類的數(shù)據(jù)中人工標(biāo)注一些樣本，并把他們作為訓(xùn)練樣本，這樣的話就可以把條件改善，用監(jiān)督學(xué)習(xí)的方法來(lái)做。然而對(duì)于不同的場(chǎng)景，正負(fù)樣本的分布如果會(huì)存在偏移（可能是大的偏移，也可能偏移比較小），這樣的話用監(jiān)督學(xué)習(xí)的效果可能就不如用非監(jiān)督學(xué)習(xí)了。

今天，在計(jì)算機(jī)科學(xué)的諸多分支學(xué)科領(lǐng)域中，都能找到機(jī)器學(xué)習(xí)技術(shù)的身影，尤其是在計(jì)算機(jī)視覺(jué)、語(yǔ)音識(shí)別、模式識(shí)別、自然語(yǔ)言處理等“計(jì)算機(jī)應(yīng)用技術(shù)”領(lǐng)域，機(jī)器學(xué)習(xí)已成為最重要的技術(shù)進(jìn)步源泉之一。此外，機(jī)器學(xué)習(xí)還為許多交叉學(xué)科提供了重要的技術(shù)支撐比如說(shuō)“生物信息學(xué)”。

可以說(shuō)“計(jì)算機(jī)視覺(jué)=圖像處理+機(jī)器學(xué)習(xí)“。圖像處理技術(shù)用于將圖像處理為適合進(jìn)入機(jī)器學(xué)習(xí)模型中的輸入，機(jī)器學(xué)習(xí)則負(fù)責(zé)從圖像中識(shí)別出相關(guān)的模式。計(jì)算機(jī)視覺(jué)相關(guān)的應(yīng)用非常的多，例如百度識(shí)圖、手寫(xiě)字符識(shí)別、車牌識(shí)別等等應(yīng)用。這個(gè)領(lǐng)域是應(yīng)用前景非常火熱的，同時(shí)也是研究的熱門方向。隨著機(jī)器學(xué)習(xí)的新領(lǐng)域深度學(xué)習(xí)的發(fā)展，大大促進(jìn)了計(jì)算機(jī)圖像識(shí)別的效果，因此未來(lái)計(jì)算機(jī)視覺(jué)界的發(fā)展前景不可估量。

如果說(shuō)“計(jì)算機(jī)視覺(jué)=圖像處理+機(jī)器學(xué)習(xí)“，那么”語(yǔ)音識(shí)別=語(yǔ)音處理+機(jī)器學(xué)習(xí)“。語(yǔ)音識(shí)別就是音頻處理技術(shù)與機(jī)器學(xué)習(xí)的結(jié)合。語(yǔ)音識(shí)別技術(shù)一般不會(huì)單獨(dú)使用，一般會(huì)結(jié)合自然語(yǔ)言處理的相關(guān)技術(shù)。目前的相關(guān)應(yīng)用有蘋(píng)果語(yǔ)音助手siri、微軟小娜等。

“自然語(yǔ)言處理=文本處理+機(jī)器學(xué)習(xí)“。自然語(yǔ)言處理技術(shù)主要是讓機(jī)器理解人類的語(yǔ)言的一門領(lǐng)域。在自然語(yǔ)言處理技術(shù)中，大量使用了編譯原理相關(guān)的技術(shù)，例如詞法分析，語(yǔ)法分析等等，除此之外，在理解這個(gè)層面，則使用了語(yǔ)義理解，機(jī)器學(xué)習(xí)等技術(shù)。作為唯一由人類自身創(chuàng)造的符號(hào)，自然語(yǔ)言處理一直是機(jī)器學(xué)習(xí)界不斷研究的方向。按照百度機(jī)器學(xué)習(xí)專家余凱的說(shuō)法“聽(tīng)與看，說(shuō)白了就是阿貓和阿狗都會(huì)的，而只有語(yǔ)言才是人類獨(dú)有的”。如何利用機(jī)器學(xué)習(xí)技術(shù)進(jìn)行自然語(yǔ)言的的深度理解，一直是工業(yè)和學(xué)術(shù)界關(guān)注的焦點(diǎn)。

談到對(duì)數(shù)據(jù)進(jìn)行分析利用，很多人會(huì)想到“數(shù)據(jù)挖掘”（data mining）。數(shù)據(jù)挖掘領(lǐng)域在二十世紀(jì)九十年代形成，它受到很多學(xué)科領(lǐng)域的影響，其中數(shù)據(jù)庫(kù)、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)無(wú)疑影響最大。數(shù)據(jù)挖掘是從海量數(shù)據(jù)中發(fā)掘知識(shí)，這就必然涉及對(duì)“海量數(shù)據(jù)”的管理和分析。大體來(lái)說(shuō)，“數(shù)據(jù)挖掘=機(jī)器學(xué)習(xí)+數(shù)據(jù)庫(kù)“——數(shù)據(jù)庫(kù)領(lǐng)域的研究為數(shù)據(jù)挖掘提供數(shù)據(jù)管理技術(shù)，而機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)的研究為數(shù)據(jù)挖掘提供數(shù)據(jù)分析技術(shù)。由于統(tǒng)計(jì)學(xué)往往醉心于理論的優(yōu)美而忽視實(shí)際的效用，因此，統(tǒng)計(jì)學(xué)界提供的很多技術(shù)通常都要在機(jī)器學(xué)習(xí)界進(jìn)一步研究，變成有效的機(jī)器學(xué)習(xí)算法之后才能再進(jìn)入數(shù)據(jù)挖掘領(lǐng)域。從這個(gè)意義上說(shuō)，統(tǒng)計(jì)學(xué)主要是通過(guò)機(jī)器學(xué)習(xí)來(lái)對(duì)數(shù)據(jù)挖掘發(fā)揮影響，而機(jī)器學(xué)習(xí)和數(shù)據(jù)庫(kù)則是數(shù)據(jù)挖掘的兩大支撐技術(shù)。從數(shù)據(jù)分析的角度來(lái)看，絕大多數(shù)數(shù)據(jù)挖掘技術(shù)都來(lái)自機(jī)器學(xué)習(xí)領(lǐng)域，但機(jī)器學(xué)習(xí)研究往往并不把海量數(shù)據(jù)作為處理對(duì)象，因此，數(shù)據(jù)挖掘要對(duì)算法進(jìn)行改造，使得算法性能和空間占用達(dá)到實(shí)用的地步。同時(shí)，數(shù)據(jù)挖掘還有自身獨(dú)特的內(nèi)容，即關(guān)聯(lián)分析。

通過(guò)上面的介紹，可以看出機(jī)器學(xué)習(xí)是多么的重要，應(yīng)用是多么的廣泛。現(xiàn)隨著大數(shù)據(jù)（big data）概念的興起，機(jī)器學(xué)習(xí)大量的應(yīng)用都與大數(shù)據(jù)高度耦合，幾乎可以認(rèn)為大數(shù)據(jù)是機(jī)器學(xué)習(xí)應(yīng)用的最佳場(chǎng)景。例如經(jīng)典的Google利用大數(shù)據(jù)預(yù)測(cè)了H1N1在美國(guó)某小鎮(zhèn)的爆發(fā)、百度預(yù)測(cè)2014年世界杯結(jié)果從淘汰賽到?jīng)Q賽全部正確。這實(shí)在太神奇了，那么究竟是什么原因?qū)е麓髷?shù)據(jù)具有這些魔力的呢？簡(jiǎn)單來(lái)說(shuō)，就是機(jī)器學(xué)習(xí)技術(shù)。正是基于機(jī)器學(xué)習(xí)技術(shù)的應(yīng)用，數(shù)據(jù)才能發(fā)揮其魔力。

大數(shù)據(jù)的核心是利用數(shù)據(jù)的價(jià)值，機(jī)器學(xué)習(xí)是利用數(shù)據(jù)價(jià)值的關(guān)鍵技術(shù)，對(duì)于大數(shù)據(jù)而言，機(jī)器學(xué)習(xí)是不可或缺的。相反，對(duì)于機(jī)器學(xué)習(xí)而言，越多的數(shù)據(jù)會(huì)越可能提升模型的精確性，同時(shí)，復(fù)雜的機(jī)器學(xué)習(xí)算法的計(jì)算時(shí)間也迫切需要分布式計(jì)算與內(nèi)存計(jì)算這樣的關(guān)鍵技術(shù)。因此，機(jī)器學(xué)習(xí)的興盛也離不開(kāi)大數(shù)據(jù)的幫助。大數(shù)據(jù)與機(jī)器學(xué)習(xí)兩者是互相促進(jìn)，相依相存的關(guān)系。

機(jī)器學(xué)習(xí)與大數(shù)據(jù)緊密聯(lián)系。但是，必須清醒的認(rèn)識(shí)到，大數(shù)據(jù)并不等同于機(jī)器學(xué)習(xí)，同理，機(jī)器學(xué)習(xí)也不等同于大數(shù)據(jù)。大數(shù)據(jù)中包含有分布式計(jì)算、內(nèi)存數(shù)據(jù)庫(kù)、多維分析等等多種技術(shù)。單從分析方法來(lái)看，大數(shù)據(jù)也包含以下四種分析方法：

1.大數(shù)據(jù)，小分析：即數(shù)據(jù)倉(cāng)庫(kù)領(lǐng)域的OLAP分析思路，也就是多維分析思想。2.大數(shù)據(jù)，大分析：這個(gè)代表的就是數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)分析法。3.流式分析：這個(gè)主要指的是事件驅(qū)動(dòng)架構(gòu)。4.查詢分析：經(jīng)典代表是NoSQL數(shù)據(jù)庫(kù)。

也就是說(shuō)，機(jī)器學(xué)習(xí)僅僅是大數(shù)據(jù)分析中的一種而已。盡管機(jī)器學(xué)習(xí)的一些結(jié)果具有很大的魔力，在某種場(chǎng)合下是大數(shù)據(jù)價(jià)值最好的說(shuō)明。但這并不代表機(jī)器學(xué)習(xí)是大數(shù)據(jù)下的唯一的分析方法。