機(jī)器學(xué)習(xí)的經(jīng)典代表算法總結(jié)（一）

1980年機(jī)器學(xué)習(xí)作為一支獨(dú)立的力量登上了歷史舞臺(tái)。在這之后的10年里出現(xiàn)了一些重要的方法和理論，典型的代表是：分類與回歸樹(CART，1984)、反向傳播算法(1986)、卷積神經(jīng)網(wǎng)絡(luò)(1989)。

從1990到2012年，機(jī)器學(xué)習(xí)逐漸走向成熟和應(yīng)用，在這20多年里機(jī)器學(xué)習(xí)的理論和方法得到了完善和充實(shí)，可謂是百花齊放的年代。代表性的重要成果有：支持向量機(jī)(SVM，1995)、AdaBoost算法(1997)、循環(huán)神經(jīng)網(wǎng)絡(luò)和LSTM(1997)、流形學(xué)習(xí)(2000)、隨機(jī)森林(2001)。

下面我們對(duì)部分機(jī)器學(xué)習(xí)代表算法進(jìn)行介紹。

?線性回歸

在機(jī)器學(xué)習(xí)中，我們有一組輸入變量(x)用于確定輸出變量(y)。輸入變量和輸出變量之間存在某種關(guān)系，機(jī)器學(xué)習(xí)的目標(biāo)是量化這種關(guān)系。

在線性回歸中，輸入變量(x)和輸出變量(y)之間的關(guān)系表示為y=ax+b的方程。因此，線性回歸的目標(biāo)是找出系數(shù)a和b的值。這里，a是直線的斜率，b是直線的截距。上圖顯示了數(shù)據(jù)集的x和y值，線性回歸的目標(biāo)是擬合最接近大部分點(diǎn)的線。

?分類與回歸樹(CART)

CART是決策樹的一個(gè)實(shí)現(xiàn)方式，由ID3，C4.5演化而來，是許多基于樹的bagging、boosting模型的基礎(chǔ)。CART可用于分類與回歸。

CART是在給定輸入隨機(jī)變量x條件下輸出隨機(jī)變量y的條件概率分布，與ID3和C4.5的決策樹不同的是，ID3和C4.5生成的決策樹可以是多叉的，每個(gè)節(jié)點(diǎn)下的叉數(shù)由該節(jié)點(diǎn)特征的取值種類而定，比如特征年齡分為(青年，中年，老年)，那么該節(jié)點(diǎn)下可分為3叉。而CART的假設(shè)決策樹為二叉樹，內(nèi)部結(jié)點(diǎn)特征取值為“是”和“否”。左分支取值為“是”，右分支取值為“否”。這樣的決策樹等價(jià)于遞歸地二分每一個(gè)特征，將輸入空間劃分為有限個(gè)單元，并在這些單元上預(yù)測(cè)概率分布，也就是在輸入給定的條件下輸出條件概率分布。

?隨機(jī)森林(Random Forest)

隨機(jī)森林指的是利用多棵決策樹對(duì)樣本進(jìn)行訓(xùn)練并預(yù)測(cè)的一種分類器。它包含多個(gè)決策樹的分類器，并且其輸出的類別是由個(gè)別樹輸出的類別的眾數(shù)而定。隨機(jī)森林是一種靈活且易于使用的機(jī)器學(xué)習(xí)算法，即便沒有超參數(shù)調(diào)優(yōu)，也可以在大多數(shù)情況下得到很好的結(jié)果。隨機(jī)森林也是最常用的算法之一，因?yàn)樗芎?jiǎn)易，既可用于分類也能用于回歸。

其基本的構(gòu)建算法過程如下：

1)用N來表示訓(xùn)練用例(樣本)的個(gè)數(shù)，M表示特征數(shù)目。

2)輸入特征數(shù)目m，用于確定決策樹上一個(gè)節(jié)點(diǎn)的決策結(jié)果;其中m應(yīng)遠(yuǎn)小于M。

3)從N個(gè)訓(xùn)練用例(樣本)中以有放回抽樣的方式取樣N次，形成一個(gè)訓(xùn)練集(即bootstrap取樣)，并用未抽到的用例(樣本)作預(yù)測(cè)，評(píng)估其誤差。

4)對(duì)于每一個(gè)節(jié)點(diǎn)，隨機(jī)選擇m個(gè)特征，決策樹上每個(gè)節(jié)點(diǎn)的決定都是基于這些特征確定的。根據(jù)這m個(gè)特征，計(jì)算其最佳的分裂方式。

5)每棵樹都會(huì)完整成長(zhǎng)而不會(huì)剪枝，這有可能在建完一棵正常樹狀分類器后被采用。

?邏輯回歸

邏輯回歸最適合二進(jìn)制分類(y=0或1的數(shù)據(jù)集，其中1表示默認(rèn)類)例如：在預(yù)測(cè)事件是否發(fā)生時(shí)，發(fā)生的事件被分類為1(在預(yù)測(cè)人會(huì)生病或不生病，生病的實(shí)例記為1)。它是以其中使用的變換函數(shù)命名的，稱為邏輯函數(shù)h(x)=1/(1+e-x)，它是一個(gè)S形曲線。

在邏輯回歸中，輸出是以缺省類別的概率形式出現(xiàn)的。因?yàn)檫@是一個(gè)概率，所以輸出在0-1的范圍內(nèi)。輸出(y值)通過對(duì)數(shù)轉(zhuǎn)換x值，使用對(duì)數(shù)函數(shù)h(x)=1/(1+e-x)來生成，然后應(yīng)用一個(gè)閾值來強(qiáng)制這個(gè)概率進(jìn)入二元分類。

樸素貝葉斯(Naive Bayesian)

樸素貝葉斯法是基于貝葉斯定理與特征條件獨(dú)立假設(shè)的分類方法。樸素貝葉斯分類器基于一個(gè)簡(jiǎn)單的假定：給定目標(biāo)值時(shí)屬性之間相互條件獨(dú)立。

通過以上定理和“樸素”的假定，我們知道：

P(Category|Document)=P(Document|Category)*P(Category)/P(Document)

樸素貝葉斯的基本方法：在統(tǒng)計(jì)數(shù)據(jù)的基礎(chǔ)上，依據(jù)條件概率公式，計(jì)算當(dāng)前特征的樣本屬于某個(gè)分類的概率，選擇最大的概率分類。

對(duì)于給出的待分類項(xiàng)，求解在此項(xiàng)出現(xiàn)的條件下各個(gè)類別出現(xiàn)的概率。哪個(gè)概率最大，就認(rèn)為此待分類項(xiàng)屬于哪個(gè)類別。其計(jì)算流程表述如下：

1)x={a1,a2,...,am}為待分類項(xiàng)，每個(gè)ai為x的一個(gè)特征屬性

2)有類別集合C={y1,y2,...,yn}

3)計(jì)算P(y1|x),P(y2|x),...,P(yn|x)

4)如果P(yk|x)=max{P(y1|x)

?k最近鄰(kNN)

kNN(k-Nearest Neighbor)的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。該方法在確定分類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。kNN方法在做類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，kNN方法較其他方法更為適合。