本章節(jié)主要介紹機(jī)器學(xué)習(xí)傳統(tǒng)算法的監(jiān)督學(xué)習(xí)部分蒋搜。監(jiān)督學(xué)習(xí)算法主要解決回歸和分類兩大問題。只能做回歸的算法是線性回歸判莉，只能做分類的算法是邏輯回歸和貝葉斯分類豆挽。其他的算法既可以做回歸又可以做分類。

1. 線性回歸(Linear Regression)

線性回歸屬于監(jiān)督學(xué)習(xí)骂租，因此方法和監(jiān)督學(xué)習(xí)應(yīng)該是一樣的祷杈，先給定一個訓(xùn)練集，根據(jù)這個訓(xùn)練集學(xué)習(xí)出一個線性函數(shù)渗饮，然后測試這個函數(shù)訓(xùn)練的好不好（即此函數(shù)是否足夠擬合訓(xùn)練集數(shù)據(jù)）但汞，挑選出最好的函數(shù)（cost function最小）即可互站。

1.1 線性回歸分類

(1) 單變量回歸

我們能夠給出單變量線性回歸的模型：

我們需要使用到Cost Function（代價函數(shù)）私蕾，代價函數(shù)越小，說明線性回歸地越好（和訓(xùn)練集擬合地越好）胡桃，當(dāng)然最小就是0踩叭，即完全擬合。

(2) 多變量回歸

多變量線性回歸之前必須要Feature Scaling翠胰。思想：將各個feature的值標(biāo)準(zhǔn)化容贝，使得取值范圍大致都在-1<=x<=1之間。

這里我們可以定義出多變量線性回歸的模型：

1.2 求擬合方程方法

(1) 最小二乘法

“最小二乘法”的核心就是保證所有數(shù)據(jù)偏差的平方和最小之景。（“平方”的在古時侯的稱謂為“二乘”）斤富。

(2) 嶺回歸

嶺回歸(Ridge Regression)是在平方誤差的基礎(chǔ)上增加正則項。通過確定lamda的值可以使得在方差和偏差之間達(dá)到平衡锻狗。

嶺回歸優(yōu)于最小二乘回歸的原因在于方差-偏倚選擇满力。隨著lambda的增大焕参，模型方差減小而偏倚（輕微的）增加。

嶺回歸的一個缺點：在建模時油额，同時引入p個預(yù)測變量叠纷，罰約束項可以收縮這些預(yù)測變量的待估系數(shù)接近0,但并非恰好是0（除非lambda為無窮大）。這個缺點對于模型精度影響不大潦嘶，但給模型的解釋造成了困難涩嚣。這個缺點可以由lasso來克服。(所以嶺回歸雖然減少了模型的復(fù)雜度衬以，并沒有真正解決變量選擇的問題)

(3) Lasso回歸

lasso是在RSS最小化(Residual Sum of Squares)的計算中加入一個l1范數(shù)作為罰約束：

l1范數(shù)的好處是當(dāng)lambda充分大時可以把某些待估系數(shù)精確地收縮到0缓艳。

2. 邏輯回歸(Logistic Regression)

(1 ) 邏輯回歸模型

簡單來說線性回歸就是直接將特征值和其對應(yīng)的概率進(jìn)行相乘得到一個結(jié)果，邏輯回歸則是這樣的結(jié)果上加上一個邏輯函數(shù)看峻，這里選用的就是Sigmoid函數(shù)。邏輯回歸分為二分類和多分類衙吩。

假設(shè)我們的樣本是{x, y}互妓，y是0或者1，表示正類或者負(fù)類坤塞，x是我們的m維的樣本特征向量冯勉。那么這個樣本x屬于正類，也就是y=1的“概率”可以通過下面的邏輯函數(shù)來表示：

所以說上面的logistic回歸就是一個線性分類模型摹芙，它與線性回歸的不同點在于：為了將線性回歸輸出的很大范圍的數(shù)灼狰，例如從負(fù)無窮到正無窮，壓縮到0和1之間浮禾，這樣的輸出值表達(dá)為“可能性”才能說服廣大民眾交胚。當(dāng)然了，把大值壓縮到這個范圍還有個很好的好處盈电，就是可以消除特別冒尖的變量的影響（不知道理解的是否正確）蝴簇。而實現(xiàn)這個偉大的功能其實就只需要平凡一舉，也就是在輸出加一個logistic函數(shù)匆帚。另外熬词，對于二分類來說，可以簡單的認(rèn)為：如果樣本x屬于正類的概率大于0.5吸重，那么就判定它是正類互拾，否則就是負(fù)類。

所以說嚎幸，LogisticRegression 就是一個被logistic方程歸一化后的線性回歸颜矿，僅此而已。

(2) 代價函數(shù)

那代價函數(shù)有了鞭铆，我們下一步要做的就是優(yōu)化求解了或衡。我們先嘗試對上面的代價函數(shù)求導(dǎo)焦影，看導(dǎo)數(shù)為0的時候可不可以解出來，也就是有沒有解析解封断，有這個解的時候斯辰，就皆大歡喜了，一步到位坡疼。如果沒有就需要通過迭代了彬呻，耗時耗力。

我們先變換下L(θ)：取自然對數(shù)柄瑰，然后化簡（不要看到一堆公式就害怕哦闸氮，很簡單的哦，只需要耐心一點點教沾，自己動手推推就知道了蒲跨。注：有xi的時候，表示它是第i個樣本授翻，下面沒有做區(qū)分了或悲，相信你的眼睛是雪亮的），得到：

然后我們令該導(dǎo)數(shù)為0堪唐，你會很失望的發(fā)現(xiàn)巡语，它無法解析求解。不信你就去嘗試一下淮菠。所以沒辦法了男公，只能借助高大上的迭代來搞定了。運用用了經(jīng)典的梯度下降算法就可以了合陵。

3. 貝葉斯分類（Bayes Classification）

貝葉斯分類是一類分類算法的總稱枢赔，這類算法均以貝葉斯定理為基礎(chǔ)，故統(tǒng)稱為貝葉斯分類曙寡。本文作為分類算法的第一篇糠爬，將首先介紹分類問題，對分類問題進(jìn)行一個正式的定義举庶。然后执隧，介紹貝葉斯分類算法的基礎(chǔ)——貝葉斯定理。最后户侥，通過實例討論貝葉斯分類中最簡單的一種：樸素貝葉斯分類镀琉。

(1) 貝葉斯定理

這個定理解決了現(xiàn)實生活里經(jīng)常遇到的問題：已知某條件概率，如何得到兩個事件交換后的概率蕊唐，也就是在已知P(A|B)的情況下如何求得P(B|A)屋摔。這里先解釋什么是條件概率：

(2) 樸素貝葉斯分類

樸素貝葉斯分類是一種十分簡單的分類算法，叫它樸素貝葉斯分類是因為這種方法的思想真的很樸素替梨，樸素貝葉斯的思想基礎(chǔ)是這樣的：對于給出的待分類項钓试，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，哪個最大弓熏，就認(rèn)為此待分類項屬于哪個類別恋谭。通俗來說清寇，就好比這么個道理堤魁，你在街上看到一個黑人，我問你你猜這哥們哪里來的淆游，你十有八九猜非洲。為什么呢？因為黑人中非洲人的比率最高空凸，當(dāng)然人家也可能是美洲人或亞洲人嚎花，但在沒有其它可用信息下，我們會選擇條件概率最大的類別呀洲，這就是樸素貝葉斯的思想基礎(chǔ)紊选。

4. 決策樹(Decision Tree)

決策樹（Decision Tree）是一種簡單但是廣泛使用的分類器。通過訓(xùn)練數(shù)據(jù)構(gòu)建決策樹两嘴，可以高效的對未知的數(shù)據(jù)進(jìn)行分類丛楚。決策數(shù)有兩大優(yōu)點：1）決策樹模型可以讀性好，具有描述性憔辫，有助于人工分析趣些；2）效率高，決策樹只需要一次構(gòu)建贰您，反復(fù)使用坏平，每一次預(yù)測的最大計算次數(shù)不超過決策樹的深度拢操。

決策樹（decision tree）是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試舶替，每個分支代表這個特征屬性在某個值域上的輸出令境，而每個葉節(jié)點存放一個類別。使用決策樹進(jìn)行決策的過程就是從根節(jié)點開始顾瞪，測試待分類項中相應(yīng)的特征屬性舔庶，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點陈醒，將葉子節(jié)點存放的類別作為決策結(jié)果惕橙。

4.1 決策樹的構(gòu)造

不同于貝葉斯算法，決策樹的構(gòu)造過程不依賴領(lǐng)域知識钉跷，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性弥鹦。所謂決策樹的構(gòu)造就是進(jìn)行屬性選擇度量確定各個特征屬性之間的拓?fù)浣Y(jié)構(gòu)。

構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性爷辙。所謂分裂屬性就是在某個節(jié)點處按照某一特征屬性的不同劃分構(gòu)造不同的分支彬坏，其目標(biāo)是讓各個分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別膝晾。分裂屬性分為三種不同的情況：

1栓始、屬性是離散值且不要求生成二叉決策樹。此時用屬性的每一個劃分作為一個分支血当。

2混滔、屬性是離散值且要求生成二叉決策樹。此時使用屬性劃分的一個子集進(jìn)行測試歹颓，按照“屬于此子集”和“不屬于此子集”分成兩個分支。

3油湖、屬性是連續(xù)值巍扛。此時確定一個值作為分裂點split_point，按照>split_point和<=split_point生成兩個分支乏德。

構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進(jìn)行屬性選擇度量撤奸，屬性選擇度量是一種選擇分裂準(zhǔn)則，是將給定的類標(biāo)記的訓(xùn)練集合的數(shù)據(jù)劃分D“最好”地分成個體類的啟發(fā)式方法喊括，它決定了拓?fù)浣Y(jié)構(gòu)及分裂點split_point的選擇胧瓜。

屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法郑什，并采用不回溯的貪心策略府喳。這里介紹ID3和C4.5兩種常用算法。

4.2 ?量化純度

4.3 停止條件

決策樹的構(gòu)建過程是一個遞歸的過程兜粘，所以需要確定停止條件弯蚜，否則過程將不會結(jié)束。一種最直觀的方式是當(dāng)每個子節(jié)點只有一種類型的記錄時停止路鹰，但是這樣往往會使得樹的節(jié)點過多收厨，導(dǎo)致過擬合問題（Overfitting）。另一種可行的方法是當(dāng)前節(jié)點中的記錄數(shù)低于一個最小的閥值帽氓，那么就停止分割，將max(P(i))對應(yīng)的分類作為當(dāng)前葉節(jié)點的分類浓领。

4.4 優(yōu)化方案

采用上面算法生成的決策樹在事件中往往會導(dǎo)致過濾擬合势腮。也就是該決策樹對訓(xùn)練數(shù)據(jù)可以得到很低的錯誤率联贩，但是運用到測試數(shù)據(jù)上卻得到非常高的錯誤率。過渡擬合的原因有以下幾點：

(1) 修剪枝葉

決策樹過渡擬合往往是因為太過“茂盛”捎拯，也就是節(jié)點過多泪幌，所以需要裁剪（Prune Tree）枝葉。裁剪枝葉的策略對決策樹正確率的影響很大署照。主要有兩種裁剪策略祸泪。

前置裁剪在構(gòu)建決策樹的過程時，提前停止建芙。那么没隘，會將切分節(jié)點的條件設(shè)置的很苛刻，導(dǎo)致決策樹很短小禁荸。結(jié)果就是決策樹無法達(dá)到最優(yōu)右蒲。實踐證明這中策略無法得到較好的結(jié)果搓萧。

后置裁剪決策樹構(gòu)建好后坎藐，然后才開始裁剪奔害。采用兩種方法：1）用單一葉節(jié)點代替整個子樹蚕断，葉節(jié)點的分類采用子樹中最主要的分類罕邀；2）將一個子樹完全替代另外一顆子樹旦棉。后置裁剪有個問題就是計算效率潮尝，有些節(jié)點計算后就被裁剪了少孝，導(dǎo)致有點浪費。

(2) K-Fold Cross Validation

首先計算出整體的決策樹T眶诈，葉節(jié)點個數(shù)記作N，設(shè)i屬于[1,N]浴骂。對每個i溯警，使用K-Fold Cross Validation方法計算決策樹梯轻，并裁剪到i個節(jié)點，計算錯誤率伊诵，最后求出平均錯誤率曹宴。這樣可以用具有最小錯誤率對應(yīng)的i作為最終決策樹的大小，對原始決策樹進(jìn)行裁剪版扩，得到最優(yōu)決策樹资厉。

(3) Random Forest

Random Forest是用訓(xùn)練數(shù)據(jù)隨機(jī)的計算出許多決策樹湘捎，形成了一個森林舷胜。然后用這個森林對未知數(shù)據(jù)進(jìn)行預(yù)測翻伺，選取投票最多的分類吨岭。實踐證明辣辫，此算法的錯誤率得到了經(jīng)一步的降低。這種方法背后的原理可以用“三個臭皮匠定一個諸葛亮”這句諺語來概括葬馋。一顆樹預(yù)測正確的概率可能不高畴嘶，但是集體預(yù)測正確的概率卻很高。

5. K最近鄰法(KNN)

K最近鄰(k-Nearest Neighbor蟀瞧，KNN)分類算法悦污，是一個理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一踏枣。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別茵瀑，則該樣本也屬于這個類別。KNN算法中鸿捧，所選擇的鄰居都是已經(jīng)正確分類的對象堆巧。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別恳邀。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時乳附，只與極少量的相鄰樣本有關(guān)赋除。由于KNN方法主要靠周圍有限的鄰近的樣本举农，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說棱貌，KNN方法較其他方法更為適合婚脱。

KNN算法不僅可以用于分類，還可以用于回歸篮洁。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本锋叨，就可以得到該樣本的屬性娃磺。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比（組合函數(shù)）听诸。

該算法在分類時有個主要的不足是蚕泽，當(dāng)樣本不平衡時仔蝌，如一個類的樣本容量很大敛惊，而其他類樣本容量很小時瞧挤，有可能導(dǎo)致當(dāng)輸入一個新樣本時皿伺，該樣本的K個鄰居中大容量類的樣本占多數(shù)。 該算法只計算“最近的”鄰居樣本妒穴，某一類的樣本數(shù)量很大讼油，那么或者這類樣本并不接近目標(biāo)樣本乏屯，或者這類樣本很靠近目標(biāo)樣本辰晕。無論怎樣含友，數(shù)量并不能影響運行結(jié)果∫酥洌可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)汉形。該方法的另一個不足之處是計算量較大概疆，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點使套。目前常用的解決方法是事先對已知樣本點進(jìn)行剪輯，事先去除對分類作用不大的樣本厌杜。該算法比較適用于樣本容量比較大的類域的自動分類瞧壮，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分咆槽。

K-NN可以說是一種最直接的用來分類未知數(shù)據(jù)的方法麦射》ㄈ欤基本通過下面這張圖跟文字說明就可以明白K-NN是干什么的。

簡單來說呐萨，K-NN可以看成：有那么一堆你已經(jīng)知道分類的數(shù)據(jù)，然后當(dāng)一個新數(shù)據(jù)進(jìn)入的時候惨远，就開始跟訓(xùn)練數(shù)據(jù)里的每個點求距離，然后挑離這個訓(xùn)練數(shù)據(jù)最近的K個點看看這幾個點屬于什么類型贺氓，然后用少數(shù)服從多數(shù)的原則辙培，給新數(shù)據(jù)歸類。

6. 支持向量機(jī)( SVM)

6.1 SVM原理

SVM從線性可分情況下的最優(yōu)分類面發(fā)展而來。最優(yōu)分類面就是要求分類線不但能將兩類正確分開(訓(xùn)練錯誤率為0),且使分類間隔最大蛮穿。SVM考慮尋找一個滿足分類要求的超平面,并且使訓(xùn)練集中的點距離分類面盡可能的遠(yuǎn),也就是尋找一個分類面使它兩側(cè)的空白區(qū)域(margin)最大。

過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面上H1,H2的訓(xùn)練樣本就叫做支持向量羔飞。

6.2 核函數(shù)

看一個例子來知道核函數(shù)是干什么用的。

故事是這樣子的：在很久以前的情人節(jié)卡儒，大俠要去救他的愛人骨望，但魔鬼和他玩了一個游戲擎鸠。

魔鬼在桌子上似乎有規(guī)律放了兩種顏色的球，說：“你用一根棍分開它們绢涡？要求：盡量在放更多球之后，仍然適用滞项∥呐校”

一般用線性核和高斯核仁热，也就是Linear核與RBF核

需要注意的是需要對數(shù)據(jù)歸一化處理举哟，很多使用者忘了這個小細(xì)節(jié)

然后一般情況下RBF效果是不會差于Linear

但是時間上RBF會耗費更多，其他同學(xué)也解釋過了

下面是吳恩達(dá)的見解：

1. 如果Feature的數(shù)量很大壶硅，跟樣本數(shù)量差不多销斟，這時候選用LR或者是Linear Kernel的SVM

2. 如果Feature的數(shù)量比較小森瘪，樣本數(shù)量一般，不算大也不算小票堵，選用SVM+Gaussian Kernel

3. 如果Feature的數(shù)量比較小，而樣本數(shù)量很多逮栅，需要手工添加一些feature變成第一種情況

6.3 松弛變量

如果兩個分類樣本有重疊悴势，如下圖：

這時候可以考慮采取松弛變量 。

7. AdaBoost

Adaboost是一種迭代算法措伐，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器（弱分類器）担败，然后把這些弱分類器集合起來宙搬，構(gòu)成一個更強的最終分類器（強分類器）闲孤。Adaboost算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的建峭，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率则拷，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次得到的分類器最后融合起來燎字，作為最后的決策分類器滨砍。

7.1 算法概述

1绒窑、先通過對N個訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器；

2噩峦、將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓(xùn)練樣本厉熟，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器岛琼；

3、將1和2都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第三個弱分類器

4、最終經(jīng)過提升的強分類器蜻展。即某個數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定曹仗。

7.2 Adaboost算法的基本思路

7.3 示例

每個區(qū)域是屬于哪個屬性赫悄，由這個區(qū)域所在分類器的權(quán)值綜合決定毒费。比如左下角的區(qū)域，屬于藍(lán)色分類區(qū)的權(quán)重為h1 中的0.42和h2 中的0.65，其和為1.07；屬于淡紅色分類區(qū)域的權(quán)重為h3 中的0.92；屬于淡紅色分類區(qū)的權(quán)重小于屬于藍(lán)色分類區(qū)的權(quán)值，因此左下角屬于藍(lán)色分類區(qū)。因此可以得到整合的結(jié)果如上圖所示，從結(jié)果圖中看竿痰，即使是簡單的分類器孵户，組合起來也能獲得很好的分類效果。

7.4 分類器權(quán)值調(diào)整的原因

由公式可以看到诸衔，權(quán)值是關(guān)于誤差的表達(dá)式。每次迭代都會提高錯分點的權(quán)值，當(dāng)下一次分類器再次錯分這些點之后桦踊，會提高整體的錯誤率椅野，這樣就導(dǎo)致分類器權(quán)值變小，進(jìn)而導(dǎo)致這個分類器在最終的混合分類器中的權(quán)值變小籍胯，也就是說竟闪，Adaboost算法讓正確率高的分類器占整體的權(quán)值更高，讓正確率低的分類器權(quán)值更低杖狼，從而提高最終分類器的正確率炼蛤。

7.5 優(yōu)缺點分析

優(yōu)點：

1)Adaboost是一種有很高精度的分類器

2)可以使用各種方法構(gòu)建子分類器,Adaboost算法提供的是框架

3)當(dāng)使用簡單分類器時，計算出的結(jié)果是可以理解的蝶涩。而且弱分類器構(gòu)造極其簡單

4)簡單理朋，不用做特征篩選

5)不用擔(dān)心overfitting(過度擬合)

缺點：

1)容易受到噪聲干擾，這也是大部分算法的缺點

2)訓(xùn)練時間過長

3)執(zhí)行效果依賴于弱分類器的選擇