程序員必學(xué)的10大算法

程序員必學(xué)的10大算法線性回歸在統(tǒng)計學(xué)和機器學(xué)習(xí)領(lǐng)域，線性回歸可能是最廣為人知也最易理解的算法之一。預(yù)測建模主要關(guān)注的是在犧牲可解釋性的情況下，盡可能最小化模型誤差或做出最準(zhǔn)確的預(yù)測。我們將借鑒、重用來自許多其它領(lǐng)域的算法（包括統(tǒng)計學(xué)）來實現(xiàn)這些目標(biāo)。線性回歸模型被表示為一個方程式，它為輸入變量找到特定的權(quán)重（即系數(shù)B），進(jìn)而描述一條最佳擬合了輸入變量（x）和輸出變量（y）之間關(guān)系的直線。例如：y=B0+B1*x我們將在給定輸入值x的條件下預(yù)測y，線性回歸學(xué)習(xí)算法的目的是找到系數(shù)B0和B1的值。我們可以使用不同的技術(shù)來從數(shù)據(jù)中學(xué)習(xí)線性回歸模型，例如普通最小二乘法的線性代數(shù)解和梯度下降優(yōu)化。線性回歸大約有200多年的歷史，并已被廣泛地研究。在使用此類技術(shù)時，有一些很好的經(jīng)驗規(guī)則:我們可以刪除非常類似（相關(guān)）的變量，并盡可能移除數(shù)據(jù)中的噪聲。線性回歸是一種運算速度很快的簡單技術(shù)，也是一種適合初學(xué)者嘗試的經(jīng)典算法。Logistic回歸Logistic回歸是機器學(xué)習(xí)從統(tǒng)計學(xué)領(lǐng)域借鑒過來的另一種技術(shù)。它是二分類問題的首選方法。像線性回歸一樣，Logistic回歸的目的也是找到每個輸入變量的權(quán)重系數(shù)值。但不同的是，Logistic回歸的輸出預(yù)測結(jié)果是通過一個叫作「logistic函數(shù)」的非線性函數(shù)變換而來的。logistic函數(shù)的形狀看起來像一個大的「S」，它會把任何值轉(zhuǎn)換至0-1的區(qū)間內(nèi)。這十分有用，因為我們可以把一個規(guī)則應(yīng)用于logistic函數(shù)的輸出，從而得到0-1區(qū)間內(nèi)的捕捉值（例如，將閾值設(shè)置為0.5,則如果函數(shù)值小于0.5，則輸出值為1），并預(yù)測類別的值。

LogisticRegressionExampleOLogisticRegressionExampleO0.20.40/60.8ixBoundaryFalsesamplesTrue5amplei由于模型的學(xué)習(xí)方式，Logistic回歸的預(yù)測結(jié)果也可以用作給定數(shù)據(jù)實例屬于類0或類1的概率。這對于需要為預(yù)測結(jié)果提供更多理論依據(jù)的問題非常有用。與線性回歸類似，當(dāng)刪除與輸出變量無關(guān)以及彼此之間非常相似（相關(guān)）的屬性后，Logistic回歸的效果更好。該模型學(xué)習(xí)速度快，對二分類問題十分有效。線性判別分析Logistic回歸是一種傳統(tǒng)的分類算法，它的使用場景僅限于二分類問題。如果你有兩個以上的類，那么線性判別分析算法（LDA）

是首選的線性分類技術(shù)。LDA的表示方法非常直接。它包含為每個類計算的數(shù)據(jù)統(tǒng)計屬性。對于單個輸入變量而言，這些屬性包括：每個類的均值。所有類的方差。R加LEM婦：我3R加LEM婦：我3r~|Unfftn_cnn￡itlti.弟Eb；LJzEq*□Do虹iEiWR切普建25il■StiTLcnntal姑21"大的類而得出的。該技術(shù)假設(shè)數(shù)據(jù)符合高斯分布（鐘形曲線），因此最好預(yù)先從數(shù)據(jù)中刪除異常值。LDA是一種簡單而有效的分類預(yù)測建模方法。

分類和回歸樹決策樹是一類重要的機器學(xué)習(xí)預(yù)測建模算法。決策樹可以被表示為一棵二叉樹。這種二叉樹與算法設(shè)計和數(shù)據(jù)結(jié)構(gòu)中的二叉樹是一樣的，沒有什么特別。每個節(jié)點都代表一個輸入變量（X）和一個基于該變量的分叉點（假設(shè)該變量是數(shù)值型的）。決策樹的葉子結(jié)點包含一個用于做出預(yù)測的輸出變量（y）。預(yù)測結(jié)果是通過在樹的各個分叉路徑上游走，直到到達(dá)一個葉子結(jié)點并輸出該葉子結(jié)點的類別值而得出。決策樹的學(xué)習(xí)速度很快，做出預(yù)測的速度也很快。它們在大量問題中往往都很準(zhǔn)確，而且不需要為數(shù)據(jù)做任何特殊的預(yù)處理準(zhǔn)備。樸素貝葉斯樸素貝葉斯是一種簡單而強大的預(yù)測建模算法。該模型由兩類可直接從訓(xùn)練數(shù)據(jù)中計算出來的概率組成：1）數(shù)據(jù)屬于每一類的概率；2）給定每個x值，數(shù)據(jù)從屬于每個類的條件概率。一旦這兩個概率被計算出來，就可以使用貝葉斯定理，用概率模型對新數(shù)據(jù)進(jìn)行預(yù)測。當(dāng)你的數(shù)據(jù)是實值的時候，通常假設(shè)數(shù)據(jù)符合高斯分布（鐘形曲線），這樣你就可以很容易地估計這些概率。樸素貝葉斯之所以被稱為「樸素」，是因為它假設(shè)每個輸入變量相互之間是獨立的。這是一種很強的、對于真實數(shù)據(jù)并不現(xiàn)實的假設(shè)。不過，該算法在大量的復(fù)雜問題中十分有效。K最近鄰算法K最近鄰（KNN）算法是非常簡單而有效的。KNN的模型表示就是整個訓(xùn)練數(shù)據(jù)集。這很簡單吧？對新數(shù)據(jù)點的預(yù)測結(jié)果是通過在整個訓(xùn)練集上搜索與該數(shù)據(jù)點最相似的K個實例（近鄰）并且總結(jié)這K個實例的輸出變量而得出的。對于回歸問題來說，預(yù)測結(jié)果可能就是輸出變量的均值；而對于分類問題來說，預(yù)測結(jié)果可能是眾數(shù)（或最常見的）的類的值。關(guān)鍵之處在于如何判定數(shù)據(jù)實例之間的相似程度。如果你的數(shù)據(jù)特征尺度相同（例如，都以英寸為單位），那么最簡單的度量技術(shù)就是使用歐幾里得距離，你可以根據(jù)輸入變量之間的差異直接計算出該值。

KNN可能需要大量的內(nèi)存或空間來存儲所有數(shù)據(jù)，但只有在需要預(yù)測時才實時執(zhí)行計算（或?qū)W習(xí)）。隨著時間的推移，你還可以更新并管理訓(xùn)練實例，以保證預(yù)測的準(zhǔn)確率。使用距離或接近程度的度量方法可能會在維度非常高的情況下（有許多輸入變量）崩潰，這可能會對算法在你的問題上的性能產(chǎn)生負(fù)面影響。這就是所謂的維數(shù)災(zāi)難。這告訴我們，應(yīng)該僅僅使用那些與預(yù)測輸出變量最相關(guān)的輸入變量。學(xué)習(xí)向量量化KNN算法的一個缺點是，你需要處理整個訓(xùn)練數(shù)據(jù)集。而學(xué)習(xí)向量量化算法（LVQ）允許選擇所需訓(xùn)練實例數(shù)量，并確切地學(xué)習(xí)這些實例。l"UTLAYtRCOMPETITIVELAYERLVQ的表示是一組碼本向量。它們在開始時是隨機選擇的，經(jīng)過多輪學(xué)習(xí)算法的迭代后，最終對訓(xùn)練數(shù)據(jù)集進(jìn)行最好的總結(jié)。通過學(xué)習(xí)，碼本向量可被用來像K最近鄰那樣執(zhí)行預(yù)測。通過計算每個碼本向量與新數(shù)據(jù)實例之間的距離，可以找到最相似的鄰居（最匹配的碼本向量）。然后返回最匹配單元的類別值（分類）或?qū)嵵担ɑ貧w）作為預(yù)測結(jié)果。如果將數(shù)據(jù)重新放縮放到相同的范圍中（例如0到1之間），就可以獲得最佳的預(yù)測結(jié)果。如果你發(fā)現(xiàn)KNN能夠在你的數(shù)據(jù)集上得到不錯的預(yù)測結(jié)果，那么不妨試一試LVQ技術(shù)，它可以減少對內(nèi)存空間的需求，不需要像KNN那樣存儲整個訓(xùn)練數(shù)據(jù)集。支持向量機支持向量機（SVM）可能是目前最流行、被討論地最多的機器學(xué)習(xí)算法之一。超平面是一條對輸入變量空間進(jìn)行劃分的「直線」。支持向量機會選出一個將輸入變量空間中的點按類（類0或類1）進(jìn)行最佳分割的超平面。在二維空間中，你可以把他想象成一條直線，假設(shè)所有輸入點都可以被這條直線完全地劃分開來。SVM學(xué)習(xí)算法旨在尋找最終通過超平面得到最佳類別分割的系數(shù)。超平面與最近數(shù)據(jù)點之間的距離叫作間隔（margin）。能夠?qū)蓚€類分開的最佳超平面是具有最大間隔的直線。只有這些點與超平面的定義和分類器的構(gòu)建有關(guān)，這些點叫作支持向量，它們支持或定義超平面。在實際應(yīng)用中，人們采用一種優(yōu)化算法來尋找使間隔最大化的系數(shù)值。支持向量機可能是目前可以直接使用的最強大的分類器之一，值得你在自己的數(shù)據(jù)集上試一試。袋裝法和隨機森林隨機森林是最流行也最強大的機器學(xué)習(xí)算法之一，它是一種集成機器學(xué)習(xí)算法。自助法是一種從數(shù)據(jù)樣本中估計某個量（例如平均值）的強大統(tǒng)計學(xué)方法。你需要在數(shù)據(jù)中取出大量的樣本，計算均值，然后對每次取樣計算出的均值再取平均，從而得到對所有數(shù)據(jù)的真實均值更好的估計。Bagging使用了相同的方法。但是最常見的做法是使用決策樹，而不是對整個統(tǒng)計模型進(jìn)行估計lagging會在訓(xùn)練數(shù)據(jù)中取多個樣本，然后為每個數(shù)據(jù)樣本構(gòu)建模型。當(dāng)你需要對新數(shù)據(jù)進(jìn)行預(yù)測時，每個模型都會產(chǎn)生一個預(yù)測結(jié)果，Bagging會對所有模型的預(yù)測結(jié)果取平均，以便更好地估計真實的輸出值。隨機森林是這種方法的改進(jìn)，它會創(chuàng)建決策樹，這樣就不用選擇最優(yōu)分割點，而是通過引入隨機性來進(jìn)行次優(yōu)分割。因此，為每個數(shù)據(jù)樣本創(chuàng)建的模型比在其它情況下創(chuàng)建的模型更加獨特，但是這種獨特的方式仍能保證較高的準(zhǔn)確率。結(jié)合它們的預(yù)測結(jié)果可以更好地估計真實的輸出值。如果你使用具有高方差的算法（例如決策樹）獲得了良好的結(jié)果，那么你通?？梢酝ㄟ^對該算法執(zhí)行Bagging獲得更好的結(jié)果。Boosting和AdaBoostBoosting是一種試圖利用大量弱分類器創(chuàng)建一個強分類器的集成技術(shù)。要實現(xiàn)Boosting方法，首先你需要利用訓(xùn)練數(shù)據(jù)構(gòu)建一個

模型，然后創(chuàng)建第二個模型（它企圖修正第一個模型的誤差）。直到最后模型能夠?qū)τ?xùn)練集進(jìn)行完美地預(yù)測或加入的模型數(shù)量已達(dá)上限，我們才停止加入新的模型。AdaBoost是第一個為二分類問題開發(fā)的真正成功的Boosting算法。它是人們?nèi)腴T理解Boosting的最佳起點。當(dāng)下的Boosting方法建立在AdaBoost基礎(chǔ)之上，最著名的就是隨機梯度提升機。AlgorithmAdaboost-ExampleOriKinuldntHD,UpdlHteTrainied!elftiiAEfiercl*8sifirerMhlerhllr>^±1：ieau±iMiVl^ssesl,3012F-?7]a?ac.1idri-ti*!ri---,i'DSdiltjr：hameBi1&-CT,is.erjiihtspdfcl*8sifirerAdaBoost使用淺層決策樹。在創(chuàng)建第一棵樹之后，使用該樹在每個訓(xùn)