這個(gè)題目取得比較奇怪，原因是：雖然號(hào)稱數(shù)學(xué)是世界上最簡(jiǎn)潔的語言，但是太多的公式難免看的人心慌；其次公式在hexo+mathjax打起來比較的費(fèi)勁，還有兼容性問題。其實(shí)，本意就是想把常用算法羅列一下，用個(gè)一兩段文字描述一下基本意思和原理，還有用途和局限性，如果看看記不起來了，再去尋求一大堆資料溫習(xí)一下。其實(shí)機(jī)器學(xué)習(xí)常用的算法都比較老了，各種語言的學(xué)習(xí)庫也久經(jīng)考驗(yàn)，正如越來越多的碼農(nóng)淪為系統(tǒng)集成工程師一樣，數(shù)據(jù)挖掘雖然不用從頭實(shí)現(xiàn)算法的各個(gè)部分，但是如果能對(duì)流程和數(shù)據(jù)特性了如指掌，對(duì)各種算法適用范圍、優(yōu)缺點(diǎn)、參數(shù)含義爛熟于心，對(duì)各種業(yè)務(wù)指標(biāo)期望有的放矢，豈不樂哉～

在此還想啰嗦的一句是，這么多算法無論復(fù)雜與簡(jiǎn)單，大多（統(tǒng)計(jì)類的可能有些例外）遵循了給出一個(gè)模型—計(jì)算誤差—修正系統(tǒng)，直到得到最優(yōu)解或者可以接受的誤差為止，由此不得不感嘆道維納“控制論”之偉大！

一、分類

1.1 貝葉斯

遵循貝葉斯公式框架的理論，后驗(yàn)概率正比于先驗(yàn)概率與似然度之積。

1.1.1 樸素貝葉斯

樸素貝葉斯之所以樸素，是基于“屬性條件的獨(dú)立性假設(shè)”而使得模型的計(jì)算被簡(jiǎn)化了。具體來說，就是輸入樣本有N維的屬性，所有屬性之間相互獨(dú)立，每個(gè)屬性單獨(dú)獨(dú)立的對(duì)分類結(jié)果產(chǎn)生影響。

對(duì)于離散值，就考慮每個(gè)屬性出現(xiàn)的頻率關(guān)系得到概率關(guān)系，而對(duì)于連續(xù)的屬性，可以考慮其分布類型的概率密度函數(shù)。離散屬性中，貝葉斯分布一般可以分為Bernoulli /Multinomial，前者是二項(xiàng)式分布，后者是多項(xiàng)式分布。對(duì)于統(tǒng)計(jì)的元素前者出現(xiàn)與否只有0、1兩個(gè)狀態(tài)，后者多項(xiàng)式分布，會(huì)記錄出每個(gè)元素的具體出現(xiàn)頻率。一般短文本分類的情況，適用于二項(xiàng)式分布，長(zhǎng)文本分析的類似情況，使用多項(xiàng)式分布效果較好。

在文本分類（情感分析）中，使用過貝葉斯分類，很明顯：先驗(yàn)概率就是訓(xùn)練文檔各個(gè)分類的文檔比重，此時(shí)你沒有觀測(cè)數(shù)據(jù)，那么按照這么個(gè)比例把握比較大，相似度就統(tǒng)計(jì)各個(gè)分類中詞的出現(xiàn)與否/頻率，然后對(duì)待測(cè)的數(shù)據(jù)，衡量待測(cè)數(shù)據(jù)中出現(xiàn)的詞在各個(gè)分類中的比率來計(jì)算和各個(gè)分類的相似程度，最終修正先驗(yàn)概率得到后驗(yàn)概率。關(guān)于伯努利分布和多項(xiàng)式分布，在具體文本測(cè)試中兩者估計(jì)就一個(gè)多點(diǎn)的差異，尚不是很明顯。

這兩個(gè)實(shí)現(xiàn)和求解的過程都比較簡(jiǎn)單，性能還不錯(cuò)，注意建模時(shí)候需要平滑處理，防止最終計(jì)算概率時(shí)候未出現(xiàn)詞導(dǎo)致概率為0，其中常用的拉普拉斯修正~“+1”平滑實(shí)現(xiàn)簡(jiǎn)單而且有效。

1.1.2 半樸素貝葉斯

樸素貝葉斯有屬性獨(dú)立性假設(shè)，這種假設(shè)在現(xiàn)實(shí)中并不是總是成立的，所以對(duì)屬性獨(dú)立性假設(shè)進(jìn)行放松就形成了版樸素貝葉斯，比如常見的“獨(dú)依賴估計(jì)”(ODE)，其就是假設(shè)每個(gè)屬性在類別之外最多依賴一個(gè)其他的屬性（如果增加依賴的屬性可能計(jì)算結(jié)果會(huì)變好，但是高階聯(lián)合概率計(jì)算十分復(fù)雜），而這個(gè)被依賴的屬性選擇方法就成了這類算法的研究點(diǎn)：比如所有屬性都依賴同一個(gè)屬性，而這個(gè)父屬性可以通過交叉驗(yàn)證來選擇最好的。

1.1.3 貝葉斯網(wǎng)絡(luò)

又稱為信念網(wǎng)絡(luò)(Belief Network)，借助于有向無環(huán)圖(DAG)來刻畫屬性之間的依賴關(guān)系。

1.2 最大熵估計(jì)

在單一機(jī)器算法中算是性能上乘的。它基于一個(gè)事實(shí)：對(duì)于我們確信的東西，我們用規(guī)則去約束它，對(duì)于我們不確定的東西，我們不做任何的假設(shè)。新手很容易繞進(jìn)去，說最大熵不就是最不確定么，我們的目的就是要消除不確定度，讓熵降低，那你這個(gè)算法讓不確定度最大，搞毛線啊。

其實(shí)舉個(gè)例子，比如投骰子，如果什么不規(guī)定，你肯定知道投下去1向上的概率是1/6；然后我告訴你投下去1，2，3向上的概率是2/3，那你就知道1向上的概率就是2/9；然后我再約定3向上的概率為1/3，那么你幾就推斷出1向上的概率就是1/6了。為什么我要做出這么個(gè)判斷，緣由我們不知道信息的時(shí)候，就讓他平均分布，不加入人為的任何假設(shè)，這時(shí)候相對(duì)來說風(fēng)險(xiǎn)最小，但同時(shí)也是在滿足約束條件下熵最大的時(shí)候。

在文本分類中，最大熵估計(jì)準(zhǔn)確度確實(shí)比貝葉斯估計(jì)多4~5個(gè)百分點(diǎn)，但是最大熵估計(jì)需要不斷的迭代約束條件來讓他收斂，性能問算是這個(gè)算法最大的問題，常用的解法包括GIS(Generalized Iterative Scaling)、IIS(Improved Iterative Scaling)、L-BFGS，前者的計(jì)算效率最低，但是原理清晰，適于學(xué)習(xí)，而后者算法效率較高，適于工程實(shí)踐。

1.3 決策樹

決策樹直觀上感覺是跟數(shù)學(xué)關(guān)聯(lián)最小的一種，其實(shí)就是建立一個(gè)個(gè)的判別規(guī)則，形似流程圖一樣，讓樣本走到最終的葉節(jié)點(diǎn)完成分類。但是，決策樹在數(shù)據(jù)挖掘和商業(yè)決策中用的情況非常的廣泛，同時(shí)一個(gè)專業(yè)的決策樹還是有一些技巧的。由于決策樹就是從屬性集中選擇屬性來進(jìn)行樣本劃分，所以希望決策樹的分支節(jié)點(diǎn)的樣本盡可能是同類別的，稱之為純度。

決策樹的屬性有連續(xù)和離散之分，對(duì)于離散屬性，其只會(huì)在整個(gè)決策樹中出現(xiàn)一次，而每個(gè)步驟的決策屬性不是隨便選的，而是基于一定的數(shù)學(xué)規(guī)則來進(jìn)行，比如ID3使用的信息增益、C4.5使用到的增益率。

信息增益是先計(jì)算這個(gè)節(jié)點(diǎn)的信息熵，然后對(duì)于每一個(gè)可選屬性，假設(shè)該種算法計(jì)算其分類后各個(gè)節(jié)點(diǎn)的信息熵，再根據(jù)各個(gè)節(jié)點(diǎn)數(shù)目加權(quán)進(jìn)行整合，計(jì)算分類之前的信息熵和這個(gè)整合值之間的差異，定義為信息增益，大者說明該屬性的劃分信息增益大，取之。但是信息增益有個(gè)問題，就是比較偏向于可選類型值較多的屬性，因此還有個(gè)增益率選擇法，用之前的信息熵整合值處以“屬性固有值”IV，而這個(gè)IV對(duì)于可選值較多的類型結(jié)果會(huì)比較大，所以偏向與屬性類型值取值較小的屬性。通常而言，是使用信息增益率先篩選掉一部分屬性，在選擇剩余的信息增益大的屬性來劃分。而CART使用的是Gini值，其表示了樣本的分散度。

決策樹還有的處理是剪枝處理，這對(duì)于處理過擬合十分的重要。一些情況下決策樹學(xué)習(xí)的過于細(xì)致，一些樣本的個(gè)性也被計(jì)算進(jìn)去了，導(dǎo)致了模型的泛化很弱。剪枝分預(yù)剪枝（在生成樹的過程中決定是否繼續(xù)劃分）和后剪枝（生成成功之后，從底向上查看非葉節(jié)點(diǎn)能否將其子樹整合為葉節(jié)點(diǎn)）。一般來說，預(yù)剪枝有欠擬合的風(fēng)險(xiǎn)，而后剪枝欠擬合風(fēng)險(xiǎn)小，但是計(jì)算相對(duì)復(fù)雜一些。

對(duì)于連續(xù)值的預(yù)測(cè)，可以按照樣本的值從小到大進(jìn)行排序，然后兩兩去中位數(shù)，得到n-1個(gè)分類點(diǎn)。然后依次分類點(diǎn)分別計(jì)算分類的信息增益，取信息增益大的分類點(diǎn)來決策。還需要注意的是，連續(xù)值分類，其屬性可以在分類樹中使用多次的。

決策樹中常會(huì)用到的算法有：ID3、CART、C4.5。

二、回歸(Regression)和正則化(Regularization )

回歸問題屬于有監(jiān)督學(xué)習(xí)范疇，其相對(duì)與分類，回歸的最大區(qū)別是輸出變量是連續(xù)值，然而這兩者沒有必然的區(qū)分，因?yàn)閷?duì)于回歸的結(jié)果，也可以設(shè)定一個(gè)閾值區(qū)域用來實(shí)現(xiàn)分類效果。

2.1 線性回歸(Linear Regression)

線性回歸問題，目的在于得到一個(gè)線性模型，使得盡可能的能夠讓給定的輸入能夠準(zhǔn)確的預(yù)測(cè)出對(duì)應(yīng)的輸出?？梢员硎緸椋瑢?duì)于訓(xùn)練數(shù)據(jù)集D，其每個(gè)樣本x(i)由多個(gè)屬性所描述，然后我們?cè)噲D得到函數(shù)模型y=h(x)，讓y(i)≈h(x(i))，然后可以對(duì)任意的新樣本輸入都能給出連續(xù)的輸入出值，稱之為多元線性回歸。記為

h(x)=∑iθixi=θTx

上式中每個(gè)x是一個(gè)樣本，為了方便添加x0=1和截距θ0截距。然后實(shí)際的輸出和模型的輸出肯定是有差距的，因此定義代價(jià)函數(shù)

J(θ)=12∑i(h(x(i))?y(i))2=12∑i(θ?x(i)?y(i))2

然后我們就是要通過訓(xùn)練樣本來調(diào)整θ，使得J(θ)最小化（1/2為了求導(dǎo)方便）。最常用的方法有：梯度下降法、最小二乘法。

梯度下降法

對(duì)于梯度下降法，有批量梯度下降法和隨機(jī)梯度下降法。區(qū)別在于批量梯度下降法每次都考慮全部樣本，運(yùn)算量較大；隨機(jī)梯度下降法在考慮單個(gè)樣本之后就會(huì)更新θ值，所以可以快速收斂。

批量梯度下降法θ更新公式：θj:=θj+α∑mi=1(y(i)?hθ(x(i)))x(i)j

隨機(jī)梯度下降法θ更新公式：θj:=θj?α?J(θ)?θj=θj+α(y(i)?hθ(x(i)))x(i)j

最小二乘法

相比較梯度下降法需要迭代求取參數(shù)θ。

2.2 邏輯回歸(Logistic Regression)

邏輯回歸其本質(zhì)還是在于線性回歸，只是對(duì)之前無約束的線性輸出做了一個(gè)映射g(z)，對(duì)于sigmoid函數(shù)輸出范圍為[0,1]，對(duì)tanh函數(shù)為[-1,1]，下面假設(shè)以sigmoid函數(shù)為例，可得

hθ(x)=g(θTx)=11+e?θTx

這個(gè)得到的結(jié)果hθ(x)就是x分類為1的概率，而1?hθ(x)就是分類為0的概率，訓(xùn)練的目的就是對(duì)于標(biāo)記為1的樣本輸出最可能的大，二標(biāo)記為0的樣本輸出的值盡可能的小。其誤差函數(shù)定義為：

J(θ)=∑iy(i)log(hθ(x(i)))+(1?y(i))log(1?hθ(x(i)))

其用梯度下降法計(jì)算同上面的線性回歸是一樣的。

2.3 Softmax回歸

邏輯回歸只能用于二分類的情況，而Softmax更像其在多分類情況下的推廣，在使用中，如果目標(biāo)的分類是多分類互斥的，那么用Softmax，否則可以為每個(gè)分類建立一個(gè)邏輯回歸分類器。

2.4 正則化

為了防止模型過擬合的現(xiàn)象，在損失函數(shù)中增加一個(gè)對(duì)每個(gè)特征的懲罰因子的過程。過擬合出現(xiàn)的原因往往是特征維度太多，通過去處不重要的特征可以防止過擬合現(xiàn)象，但是去除特征會(huì)損失信息，這種情況下采用正則化就比較的方便（個(gè)人的直觀感受就是增加了一個(gè)阻尼項(xiàng)，使得各個(gè)特征的表現(xiàn)不像之前那么明顯激進(jìn)）。工程約定中通常不對(duì)θ0進(jìn)行正則化，同時(shí)正則化系數(shù)不能選擇太大，否則會(huì)有欠擬合的風(fēng)險(xiǎn)。

常見的正則化有L-2范數(shù)正則化（嶺回歸 Ridge Regression）、L-1范數(shù)正則化（LASSO）

minw∑i=1n(yi?w??Tx??i)2+λ||w??||1

minw∑i=1n(yi?w??Tx??i)2+λ||w??||22

L-1范數(shù)和L-2范數(shù)都有助于降低過擬合的風(fēng)險(xiǎn)，而且相比L-2正則化，L-1正則化更容易得到稀疏解，等于起到了特征選擇的作用。

2.5 支持向量機(jī) SVM

2.5.1 支持向量機(jī)

2.5.2 支持向量回歸（SVR）

其實(shí)一看模型f(x??)=w??Tx??+b就類似于回歸模型。SVR同一般的回歸模型不同的是，一般的回歸模型除非輸出和標(biāo)記完全一樣，否則肯定會(huì)產(chǎn)生和記錄誤差，但是對(duì)于SVR，相當(dāng)于在回歸線的附近產(chǎn)生了一個(gè)緩沖帶，在這個(gè)緩沖帶的誤差不計(jì)算，超過這個(gè)緩沖帶的誤差才會(huì)就算中。

2.5.3 核方法

通常的SVM是假設(shè)訓(xùn)練樣本是線性可分的，就是可以通過超平面將數(shù)據(jù)正確分類。對(duì)于有些不能達(dá)到這個(gè)要求的樣本，就只有想辦法將原始特征映射到一個(gè)更高維度的特征空間。

三、聚類

聚類算法中比較核心的是距離的度量，距離近的才會(huì)被視為一類。常用的距離是Minkowski距離：

(∑i=1n|xi?yi|p)1p

當(dāng)上式的p=2，就退化成了歐拉距離；當(dāng)p=1，就退化成了麥哈頓距離。當(dāng)然屬性有離散型和連續(xù)型之分，連續(xù)型的屬性計(jì)算距離沒有什么問題，對(duì)于離散型的屬性，如果是數(shù)值型的，也可以用Minkowski距離計(jì)算，而對(duì)于{顏色深,顏色淺}等無序?qū)傩裕梢圆捎肰DM(Value Difference Metric)計(jì)算其距離：

VDMp(a,b)=∑i=1k|mu,a,imu,a?mu,b,imu,b|

上面的公式表示，對(duì)于k個(gè)樣本簇，a、b為屬性u(píng)的兩個(gè)取值，兩個(gè)比值表示每個(gè)簇中樣本a、b占總數(shù)的比例。

3.1 K均值算法(K-means)

其迭代過程表示為：通過對(duì)聚得到的每個(gè)簇i計(jì)算其均值向量μi→，然后再將樣本集中的每個(gè)元素，計(jì)算其與各個(gè)簇均值向量的距離，找到距離最近的聚類j，再將這個(gè)元素添加到j(luò)簇中。這樣進(jìn)行過一輪迭代之后，計(jì)算每個(gè)簇的新均值向量，如果簇均值向量不再更新，那么迭代停止。

當(dāng)然K-means也有其缺點(diǎn)：（1）具體K聚類個(gè)數(shù)不太好把握；（2）初始聚類的種子選擇是隨機(jī)的。

3.2 學(xué)習(xí)向量化(Learning Vector Quantization)

要求訓(xùn)練的樣本帶有標(biāo)記，算是監(jiān)督類學(xué)習(xí)的一種，其目標(biāo)是對(duì)每一個(gè)聚類簇學(xué)習(xí)得到一個(gè)屬性向量。在訓(xùn)練樣本中隨機(jī)選擇帶標(biāo)記的樣本，然后計(jì)算與各個(gè)簇向量的距離，選擇距離最近的那個(gè)簇，然后比較兩者的標(biāo)記是否一致，如果一致就讓簇向量向樣本屬性向量靠攏；否則就反向遠(yuǎn)離之。

當(dāng)達(dá)到最大迭代數(shù)目，或者各個(gè)簇向量更新很小的時(shí)候，就停止迭代。此時(shí)可以對(duì)任意樣本與各個(gè)簇向量計(jì)算得到所劃分的簇。

3.3 層次聚類(Hierarchical Clustering)

試圖在不同層次對(duì)數(shù)據(jù)進(jìn)行劃分，形成樹形的聚類結(jié)構(gòu)，有自頂向下和自底向上之分。常見的AGNES是一種自底向上的算法。該算法首先將每個(gè)樣本看作一個(gè)初始聚類，然后在運(yùn)算的每一步中選擇距離最近的兩個(gè)簇進(jìn)行合并，重復(fù)之直到達(dá)到要求的聚類數(shù)目。這個(gè)算法的核心是計(jì)算各個(gè)簇之間的距離，當(dāng)然簇也是由元素組成的，其實(shí)就映射到兩個(gè)簇中選擇元素進(jìn)行計(jì)算，然后會(huì)有最小距離、最大距離、平均距離等方式來決定結(jié)果。

3.4 Latent Dirichlet Allocation (LDA)

這個(gè)算法最初發(fā)表，作者就是研究的文字類的分類，所以注定其在自然語言處理方便應(yīng)用非常之很多，比如社交媒體熱點(diǎn)監(jiān)控、政府輿論監(jiān)控等，而其中騰訊的廣告系統(tǒng)就是基于這個(gè)算法的一個(gè)并行化實(shí)現(xiàn)。

本算法是個(gè)無指導(dǎo)的分類，只需參數(shù)提供聚類的數(shù)目即可（該算法還有一個(gè)變種，Labelled-LDA，可以實(shí)現(xiàn)指導(dǎo)分類）。同時(shí)，這個(gè)算法還比較有個(gè)性的是，其涉及到的數(shù)學(xué)概念和知識(shí)是相當(dāng)之多。

3.5 Probabilistic Latent Semantic Analysis（PLSA）

其實(shí)按照出現(xiàn)的順序來說或，算是PLSA先出來（據(jù)說作者搞完這個(gè)就去開公司了，也算瀟灑），看看PLSA和LDA就感覺是頻率派和貝葉斯派的區(qū)別：比如在PLSA中在可觀測(cè)的doc和term之間，隱藏了一個(gè)堅(jiān)信存在的主題變量z，然后用EM方法估計(jì)這個(gè)z；相比前者LDA添加了個(gè)Dirichlet先驗(yàn)分布和一個(gè)Gibbs采樣。

理論上人家說LDA由于有先驗(yàn)分布，所以對(duì)于超短文本應(yīng)當(dāng)可靠性較好，但是在現(xiàn)實(shí)的工程實(shí)現(xiàn)中，PLSA比較的簡(jiǎn)單，計(jì)算高效而且可以并行化實(shí)現(xiàn)，所以PLSA應(yīng)當(dāng)更具實(shí)用性。

四、數(shù)據(jù)降維

在高緯數(shù)據(jù)處理中，數(shù)據(jù)降維和特征選擇是兩大主流技術(shù)。

4.1 主成分分析(Principal Component Analysis, PCA)

PCA是最常見的降維方法，常常作為一般算法對(duì)于數(shù)據(jù)的預(yù)處理操作。其原理就是將高維屬性空間變換為一個(gè)低維屬性空間，讓這個(gè)空間中的樣本密度大幅提高，因?yàn)榕c學(xué)習(xí)任務(wù)密切相關(guān)的信息只是高維屬性空間中的某些低維屬性，而且通常是各個(gè)樣本變化比較大的那些屬性而應(yīng)當(dāng)被保留，而差異比較小的，通常是干擾噪聲應(yīng)當(dāng)被去除。

然后PCA跟SVD(Singular Value Decomposition)，很多資料分開討論，其實(shí)算是一個(gè)東西：SVD是底層的數(shù)學(xué)基礎(chǔ)，不僅可以降維屬性而且可以降維樣本數(shù)甚至不降維用另外的方式表示數(shù)據(jù)，PCA算是在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)中的一個(gè)降低屬性維度的約定吧。

算法的過程：（1）對(duì)所有輸入樣本去直流化，并將數(shù)據(jù)映射到[0-1]區(qū)間；（2）計(jì)算樣本的協(xié)方差矩陣X??X??T；（3）對(duì)協(xié)方差矩陣X??X??T做特征值分解；（4）取最大的d個(gè)特征值對(duì)應(yīng)的特征向量w??1,w??2,…w??d;（5）生成投影矩陣W??=w??1,w??2,…w??d;

這樣生成的投影矩陣W??是正交基向量，Y??=W??TX??就實(shí)現(xiàn)了數(shù)據(jù)的降維。PCA認(rèn)為一個(gè)隨機(jī)信號(hào)最有用的信息體包含在方差里，在投影的時(shí)候就希望找到的超平面上各個(gè)樣本能夠經(jīng)可能的分開，所以上面得到的Y??各個(gè)向量不僅是獨(dú)立的，而且是按照方差從大到小的順序排列的。同時(shí)既然進(jìn)行了降維，那么必定有些數(shù)據(jù)信息被舍棄了，舍棄這些信息后能讓原本的采樣密度更大，同時(shí)這些被舍棄的特征向量往往跟噪聲有關(guān)，PCA此時(shí)也起到了降噪的作用。

同時(shí)，PCA還可以有的作用比如：

數(shù)據(jù)壓縮，比如對(duì)于圖片這種數(shù)據(jù)，如果λ的選取的比較少，原來的(m,n)二維矩陣就可以用U,S,V三個(gè)小矩陣來近似等價(jià)存儲(chǔ)了；

高維數(shù)據(jù)的可視化，將數(shù)據(jù)降維到2~3維就可以可視化了。

4.2 特征選擇

特征選擇就是對(duì)于高維的屬性，挑選那些對(duì)當(dāng)前學(xué)習(xí)有用的“相關(guān)特征”作為屬性子集，去除那些沒什么用的“無關(guān)特征”或者“冗余特征”，這樣不但降低了計(jì)算的復(fù)雜度，同時(shí)也免除了那些無關(guān)特征對(duì)計(jì)算結(jié)果的干擾。

產(chǎn)生特征集，不能窮舉所有的組合類型，因?yàn)樘卣鬟x擇本來就是應(yīng)對(duì)高維屬性的，窮舉的組合類型就會(huì)非常的多，因此必須采用合適的子集生成和評(píng)價(jià)方法。前向搜索方法是：將所有屬性分割成單個(gè)屬性的子集，然后選擇單個(gè)子集中評(píng)價(jià)最好的，再依次添加剩余的屬性，形成兩個(gè)元素的屬性子集，選擇評(píng)價(jià)最好的，依次類推，直到添加特征后評(píng)價(jià)還不如不添加，那么添加結(jié)束，返回該結(jié)果；類似的還有“后向”搜索、“雙向”搜索。關(guān)于子集的評(píng)價(jià)，可以使用決策樁形式的信息增益來評(píng)價(jià)，或者分類準(zhǔn)確度等各種評(píng)價(jià)指標(biāo)。

常見的特征選擇算法：

過濾式選擇

主要特點(diǎn)是先進(jìn)行特征選擇，然后進(jìn)行訓(xùn)練學(xué)習(xí)，兩者是無關(guān)的。代表方法是Relief(Relevant Features)，其設(shè)計(jì)了一個(gè)相關(guān)統(tǒng)計(jì)量來度量特征的重要性，該變量是個(gè)向量，每個(gè)分量代表了其特征的重要性，選擇的時(shí)候：對(duì)每個(gè)樣本，在其周圍選擇最近的同類樣本和不同類樣本，然后依照如下方法進(jìn)行更新：

δj=∑i?diff(xji,xji,nh)2+diff(xji,xji,nm)2

前者為同類樣本的距離，后者為不同類樣本的距離（離散類型根據(jù)是否相同為0/1，連續(xù)類型歸一化到0~1）。

包裹式選擇

把學(xué)習(xí)器的最終性能作為屬性子集的選擇評(píng)判標(biāo)準(zhǔn)，所以等于是一種所見即所得的特征選擇方法，但是其需要多次訓(xùn)練學(xué)習(xí)器，因此計(jì)算開銷比較大。

最常見的包裹式特征選擇法是LVM(Las Vegas Wrapper)算法，其算法的主要概念為：采用隨機(jī)策略產(chǎn)生特征子集A’，采用交叉驗(yàn)證的方法得到學(xué)習(xí)誤差?′，如果它比當(dāng)前特征子集A誤差更小，或者特征子集包含的特征數(shù)量更小，則保留A’。這種算法算是比較簡(jiǎn)單粗暴的，且其停止條件是迭代次數(shù)……

嵌入式選擇

這其實(shí)是L-1范數(shù)正則化(LASSO)的副產(chǎn)品，因?yàn)閷?duì)于

minw∑i=1n(yi?w??Tx??i)2+λ||w??||1

LASSO正則化后w??是稀疏的，而w??中非零的分量特征才會(huì)出現(xiàn)在最終的模型中，所以等于在使用了L-1正則化的時(shí)候，本身就潛入了特征選擇的過程。

4.3 隱形語義分析類(Latent Semantic Indexing, LSI)和潛在語義索引(Latent Semantic Analysis, LSA)

這里的方法是基于上面的SVD的，通常應(yīng)用于文本處理和信息檢索之中（LSI將自己定位為Information Retrival）。

這些方法通過TruncatedSVD（其實(shí)就是降維啦），一方面可以去除那些不重要的噪音，還可以帶來的好處有：對(duì)原始的數(shù)據(jù)進(jìn)行了新的表示方式，可以處理Synonymy（同一個(gè)語義可以有不同種的表達(dá)方式）、Polysemy（對(duì)于多義詞，他們可能工作的不是很好，因?yàn)樽罱K得到的向量是加權(quán)平均的，所以會(huì)展示為接近平均值的語義項(xiàng)）、Term Dependence（原始的空間是基于獨(dú)立性假設(shè)的，但是這往往是不成立的，但是進(jìn)過SVD變換后，我們可以輕易的使用這個(gè)假設(shè)）。

經(jīng)過TruncatedSVD之后，新的Doc-Term表示就可以做很多的事情了：如果要作為文本或者話題分類，就可以按照各個(gè)Doc的向量來進(jìn)行聚類；如果要用作信息檢索的話，就將要檢索的文本計(jì)算其投影后向量，然后在這些文檔的向量中尋找最接近的即可；不僅僅對(duì)文檔，詞匯也是按照向量表示的，因此還可以對(duì)詞匯進(jìn)行研究，比如尋找某個(gè)詞關(guān)系最密切的詞匯等。

對(duì)于使用A??=word×docs的矩陣（與常理的習(xí)慣有些差異），進(jìn)行SVD之后，word以U??的行向量表示，docs以V??的行向量表示（而不是其轉(zhuǎn)置），他們降維之后的版本就是U??S??和V??S??。

五、相關(guān)學(xué)習(xí)算法

5.1 Apriori algorithm

該算法屬于關(guān)聯(lián)分析中的經(jīng)典算法，用于找到各種集合中頻繁出現(xiàn)的項(xiàng)，在商家產(chǎn)品推薦中應(yīng)用廣泛，常常也被稱為購物籃分析，用于挖掘常見的商品購買組合。如果產(chǎn)品的數(shù)據(jù)有限，道可以窮舉所有的組合來統(tǒng)計(jì)，但是一般商家的產(chǎn)品數(shù)目眾多，這種笨辦法顯然是不合適的。

支持度(support)：表示某個(gè)子集合在數(shù)據(jù)集所有集合中所占的比例；

置信度/可信度(confidence)：針對(duì)A->B這條規(guī)則，可信度表示為 支持度(A,B)/支持度(A)；

從原理上說，Apriori實(shí)際是一個(gè)自底到頂?shù)纳伤惴?，Apriori的原理是：如果某個(gè)集合是頻繁項(xiàng)，那么他的所有子集也是頻繁項(xiàng)；反之，如果某個(gè)集合是非頻繁項(xiàng)，那么他的所有超級(jí)肯定也不是頻繁項(xiàng)。通過后面的原理，加上支持度的約束，可以省略很多集合項(xiàng)的統(tǒng)計(jì)操作。

其生成步驟描述為：

(1)首先創(chuàng)建長(zhǎng)度為1的子集合，然后掃描數(shù)據(jù)集計(jì)算支持度，去掉支持度不滿足的元素；

(2)將元素組合，生成長(zhǎng)度為2的子集合，進(jìn)行支持度的計(jì)算和排除；

(3)后面對(duì)于要生成長(zhǎng)度為k的子集合，具有一定的技巧操作——對(duì)上一輪的(k-1)長(zhǎng)度的子集合，進(jìn)行兩兩比較，如果排序后其前(k-2)個(gè)元素相同，就取(k-2)|(k-1)~1|(k-1)~2這樣組合成長(zhǎng)度為k的子集合；（注意，這里有點(diǎn)像Eclat算法）

(4)依次進(jìn)行(3)，直到不能產(chǎn)生子集合為止。

Apriori算法的缺點(diǎn)是：需要產(chǎn)生大量的候選子集合，而且需要不斷掃描原始數(shù)據(jù)集，算法效率比較低。

5.2 FP-growth

針對(duì)Apriori的缺點(diǎn)，F(xiàn)P不生成候選子集合，同時(shí)只需要掃描兩遍數(shù)據(jù)集，將原始數(shù)據(jù)集壓縮成一個(gè)頻繁模樹，然后依據(jù)這個(gè)頻繁模式樹生成關(guān)聯(lián)規(guī)則，比Apriori算法快一個(gè)數(shù)量級(jí)。

5.3 Eclat algorithm

Eclat算法的思想采用了倒排的概念，一般的數(shù)據(jù)集都是(TID, items)的形式，而Eclat將數(shù)據(jù)轉(zhuǎn)換成(item,TIDs)的組織方式。

子集的元素按照順序排列，假設(shè)其前(k-1)項(xiàng)相同，那么就可以進(jìn)行或操作得到k項(xiàng)子集了，而同時(shí)兩個(gè)集合的TIDs進(jìn)行并操作，就得到了新子集的TIDs，所以不需要掃描原始數(shù)據(jù)集，算法的效率比較的高。

這個(gè)算法的缺點(diǎn)是要保留所有子集合的TID交易集，所以如果數(shù)據(jù)規(guī)模大的話，需要耗費(fèi)大量的內(nèi)存。

六、半監(jiān)督學(xué)習(xí)

針對(duì)標(biāo)記的樣本數(shù)量比較的少，未標(biāo)記樣本數(shù)目比較大的情況，而假設(shè)標(biāo)記樣本和未標(biāo)記樣本都是從數(shù)據(jù)源中獨(dú)立同分布采樣而得到的，那么就可以考慮使用標(biāo)記和未標(biāo)記樣本的半監(jiān)督的學(xué)習(xí)方法來建立模型。

七、集成學(xué)習(xí)

通過構(gòu)建多個(gè)學(xué)習(xí)器來完成學(xué)習(xí)任務(wù)，將個(gè)體學(xué)習(xí)器的結(jié)果運(yùn)用某些策略集合產(chǎn)生最終的結(jié)果。對(duì)于個(gè)體學(xué)習(xí)器，如果是相同的稱為同質(zhì)學(xué)習(xí)器，如果不同的則稱為異質(zhì)學(xué)習(xí)器。

其實(shí)在整個(gè)集成學(xué)習(xí)的理論中，追求的就是各個(gè)基學(xué)習(xí)器“好而不同”，其實(shí)對(duì)每個(gè)基學(xué)習(xí)器的要求不會(huì)像平常單個(gè)學(xué)習(xí)方法那么高（當(dāng)然高更好，可以減少基學(xué)習(xí)器的數(shù)目），關(guān)鍵是各個(gè)基學(xué)習(xí)器之間要有差異，有自己的個(gè)性，如果大家對(duì)相同的樣本做出的判斷都一樣，其實(shí)對(duì)最終的準(zhǔn)確性和泛化能力沒有任何的幫助

基學(xué)習(xí)器多樣性的方法有：

數(shù)據(jù)樣本擾動(dòng)：基本基于樣本采樣實(shí)現(xiàn)，主要對(duì)決策樹、神經(jīng)網(wǎng)絡(luò)等不穩(wěn)定基學(xué)習(xí)器有效，而對(duì)線性學(xué)習(xí)器、支持向量機(jī)、樸素貝葉斯等穩(wěn)定學(xué)習(xí)器效果很小。

輸入屬性擾動(dòng)：當(dāng)屬性比較多的時(shí)候推薦，比如隨機(jī)森林的機(jī)制。

輸出表示擾動(dòng)：

算法參數(shù)擾動(dòng)：

集成學(xué)習(xí)的集合策略有：

平均法和加權(quán)平均法：前者可為后者權(quán)重相同時(shí)候的一個(gè)特例，一般來說，除非各個(gè)基學(xué)習(xí)器之前性能差異十分明顯，否則建議蠶蛹平均法集成學(xué)習(xí)結(jié)果。

投票法：可分為絕對(duì)多數(shù)投票法（只有當(dāng)投票超過半數(shù)才接受，否則不輸出結(jié)果，用于對(duì)可靠性要求高，可以不輸出結(jié)果的情形）、相對(duì)多數(shù)投票法、加權(quán)投票法。

根據(jù)個(gè)體學(xué)習(xí)器的生成方式，集成學(xué)習(xí)分為兩類：個(gè)體學(xué)習(xí)器之間有強(qiáng)依賴關(guān)系，必須串行化生成，代表的有Boosting；個(gè)體學(xué)習(xí)器之間沒有強(qiáng)依賴關(guān)系，代表有Bagging和隨機(jī)森林(Random Forest)。

7.1 Boosting及著名代表AdaBoost

如上文的描述，整個(gè)模型是串行生成的。算法首先給訓(xùn)練樣本權(quán)值均勻化，使用一個(gè)基分類器訓(xùn)練之，然后根據(jù)樣本的輸出與標(biāo)記進(jìn)行對(duì)比：如果一致，那么樣本的權(quán)重會(huì)相應(yīng)降低，如果不一致，那么樣本的權(quán)重會(huì)相應(yīng)的增加，然后用這些新權(quán)重的樣本去訓(xùn)練下一個(gè)分類器，直到達(dá)到指定數(shù)目的分類器。這里每一步訓(xùn)練的時(shí)候，會(huì)對(duì)結(jié)果的誤差θ進(jìn)行評(píng)判，如果小于0.5（還不如隨機(jī)分布），整個(gè)訓(xùn)練以失敗結(jié)束。

實(shí)踐中，有的屬性是可以賦值權(quán)重的，對(duì)于不能賦值權(quán)重的，可以通過重采樣來實(shí)現(xiàn)（估計(jì)就是將錯(cuò)誤的樣本大概率多采集點(diǎn)）。同時(shí)，AdaBoost只支持二分類的計(jì)算。

7.2 Bootstrapped Aggregation (Bagging)

主要是基于自助采樣法(bootstrap sampling)，進(jìn)行有放回的采樣得到采樣集（初始樣本約有63.2%的幾率會(huì)出現(xiàn)在采樣集中），然后用每個(gè)采樣集訓(xùn)練每個(gè)基學(xué)習(xí)器，再將這些基學(xué)習(xí)器的結(jié)果進(jìn)行集合（常用簡(jiǎn)單投票法）就可以了。同時(shí)由于對(duì)于每個(gè)基學(xué)習(xí)器都有36.8%的樣本沒有用于訓(xùn)練，所以這些“包外樣本”可以用于驗(yàn)證基學(xué)習(xí)器的泛化性能等。

7.3 隨機(jī)森林 Random Forest

實(shí)際是Bagging的一個(gè)擴(kuò)展變體。RF以決策樹作為基學(xué)習(xí)器來構(gòu)建Bagging集成學(xué)習(xí)，同時(shí)在決策樹訓(xùn)練的時(shí)候，引入隨機(jī)屬性選擇的機(jī)制，因?yàn)閭鹘y(tǒng)的決策樹都會(huì)按照信息增益、增益率等方式選擇出一個(gè)最好的屬性來用于每一步劃分，而隨機(jī)森林會(huì)在這之前每次隨機(jī)選擇一個(gè)屬性集的子集合，然后在子集和中選擇最優(yōu)屬性進(jìn)行劃分，k為隨機(jī)度——k=1就是完全隨機(jī)，k=d就是傳統(tǒng)的決策樹，推薦k=log2d。

八、暴力類

之所以這么稱，源于這類算法對(duì)計(jì)算量要求實(shí)在是高，網(wǎng)絡(luò)層數(shù)少了模型能力有限（單層神經(jīng)網(wǎng)絡(luò)甚至不能執(zhí)行異或操作），層數(shù)深了吧計(jì)算量和對(duì)訓(xùn)練數(shù)據(jù)的要求也斗升，所以不搞個(gè)Nvdia支持Cuda的GPU，很多樣例復(fù)現(xiàn)都費(fèi)勁。深度學(xué)習(xí)自然是當(dāng)前機(jī)器學(xué)習(xí)的研究熱點(diǎn)，相關(guān)論文發(fā)布很多，成果也很誘人，同時(shí)漫山遍野的深度庫使得是個(gè)碼農(nóng)都能玩兩下——但請(qǐng)謹(jǐn)慎入坑，其毛病也多多：

訓(xùn)練出來的模型是黑核的，不具備解釋性，改進(jìn)、微調(diào)等都比較麻煩，部署風(fēng)險(xiǎn)很高；網(wǎng)絡(luò)結(jié)構(gòu)，參數(shù)設(shè)置，訓(xùn)練樣本涉及到的因素太多，對(duì)開發(fā)者經(jīng)驗(yàn)要求好，而且最終一個(gè)工作的模型可能是不斷試錯(cuò)最終得出來的；欠擬合、過擬合問題比大多數(shù)算法都為的嚴(yán)重（包外數(shù)據(jù)驗(yàn)證）；最不低碳環(huán)保的算法。

8.1 神經(jīng)網(wǎng)絡(luò) BP神經(jīng)網(wǎng)絡(luò)

早期的神經(jīng)網(wǎng)絡(luò)主要以BP網(wǎng)絡(luò)最為常見和重要。由控制論得知，如果沒有BP機(jī)制反向傳遞系統(tǒng)誤差用于修正，就很難實(shí)現(xiàn)復(fù)雜穩(wěn)定的模型。

8.2 深度學(xué)習(xí)

8.2.1 Convolutional Neural Network (CNN)

卷積神經(jīng)網(wǎng)絡(luò)，主要適用于固定維度的輸入信號(hào)，以圖像處理最為代表。

8.2.2 Recurrent Neural Network (RNN)

表現(xiàn)為這一層網(wǎng)絡(luò)的那個(gè)神經(jīng)元，除了接受上一層神經(jīng)元的輸出作為輸入之外，還接受同層相鄰神經(jīng)元的輸出作為輸入，這些輸入會(huì)有個(gè)類似開關(guān)的東西控制各個(gè)輸入源的權(quán)重。常見的RNN網(wǎng)絡(luò)有LSTM、GRU。

最后，我不得不說——不用公式記錄算法根本做不到~~~

同時(shí)，如果有些科學(xué)計(jì)算不方便，但是有沒有裝Matlab的，推薦這個(gè)GNU OCTAVE ONLINE，很好用！

#參考目錄

機(jī)器學(xué)習(xí) - 周志華

A Tour of Machine Learning Algorithms

Machine Learning Library (MLlib) Guide

中文語言處理工具

LDA漫游指南

[LDA工程實(shí)踐之算法篇-1]算法實(shí)現(xiàn)正確性驗(yàn)證

scikit-learn docs

Apriori算法

查看原文