輕鬆入門機器學習之概念總結（一）

04-03

歡迎大家前往騰訊雲社區，獲取更多騰訊海量技術實踐乾貨哦~

作者：許敏

前言

1，機器學習演算法分類

1）監督學習：有train set，train set裡面y的取值已知。

2）無監督學習：有train set, train set裡面y的取值未知。

3）半監督學習：有train set， train set裡面y的取值有些知道有些不知道。

4）增強學習：reinforcement learning，無train set。

2，常見演算法

3，演算法概念學習

1）最小二乘回歸

最小二乘回歸（英文名：Ordinary Least Squares RegressionOLS，又叫Generalized Least SquaresGLS）是常見的線性回歸方法。最小二乘法的基本原則是：最優擬合直線應該使各點到直線的距離的和最小，也可表述為距離的平方和最小。

經典線性回歸模型的基本假設：（1），殘差具有零均值；（2）var <∞,即殘差具有常數方差，且對於所有x值是有限的；（3）殘差項之間在統計意義上是相互獨立的；（4）殘差項與變數x無關；（5）殘差項服從正態分布；

如果滿足假設(1)－(4)，由最小二乘法得到的估計量具有一些特性，它們是最優線性無偏估計量（Best Linear Unbiased Estimators，簡記BLUE）。1）線性（linear）：意味著x與隨機變數y之間是線性函數關係；2）無偏（unbiased）：意味著平均而言，實際由樣本數據得到的x的參數值與其總體數據中的真實值是一致的；3）最優（best）：意味著在所有線性無偏估計量里，OLS估計量具有最小方差。

回歸常見的3個必須要解決的問題在於：

1）Heterroskedasticity異方差性：殘差的方差不為常數，殘差與x相關（eg，x變大，殘差變大），違反了假設2和4

2）Autocorrelation自相關性：殘差項之間自相關，違反了假設3

3）Multicollinearity多重共線性：多個x之間不獨立，即xi與xj之間存在相關性。

2）嶺回歸

嶺回歸(英文名：ridge regression, Tikhonov regularization)是一種專用於共線性數據分析的有偏估計回歸方法，實質上是一種改良的最小二乘估計法（OLS回歸），通過放棄最小二乘法的無偏性，以損失部分信息、降低精度為代價獲得回歸係數更為符合實際、更可靠的回歸方法，對病態數據的擬合要強於最小二乘法。

一般線性回歸是最小二乘法回歸，殘差計算是平方誤差項。嶺回歸(Ridge Regression)是在平方誤差的基礎上增加正則項，通過確定的值可以使得在方差和偏差之間達到平衡：隨著的增大，模型方差減小而偏差增大。

嶺回歸是對最小二乘回歸的一種補充，它損失了無偏性，來換取高的數值穩定性，從而得到較高的計算精度。通常嶺回歸方程的R平方值會稍低於普通回歸分析，但回歸係數的顯著性往往明顯高於普通回歸，在存在共線性問題和病態數據偏多的研究中有較大的實用價值。

備註：回歸問題時，如果x選擇個數太多，會導致模型複雜度膨脹性增大。如果x選擇太少，可能導致模型的預測能力不夠。x選擇數目過多，一方面太複雜，另外一方面會使得構建出來的模型對train set的數據over-fit，導致這個模型應用於test set時效果並不好。因此需要有一個機制來做特徵選擇，即需要對x的集合有所取捨。特徵選擇有3種類型：1）子集選擇；2）收縮方法（Shrinkage method），又叫做正則化（Regularization)，這裡就會出現嶺回歸方法和LASSO回歸方法。3）維數縮減，即降維

3）LASSO回歸

LASSO回歸（英文名： Least Absolute Shrinkage and Selectionator Operator）其實本質是一種降維方法，由Tibshirani(1996)提出。這種演算法通過構造一個懲罰函數獲得一個精鍊的模型；通過最終確定一些指標的係數為零，LASSO演算法實現了指標集合精簡的目的。這是一種處理具有復共線性數據的有偏估計。Lasso的基本思想是在回歸係數的絕對值之和小於一個常數的約束條件下，使殘差平方和最小化，從而能夠產生某些嚴格等於0的回歸係數，得到解釋力較強的模型。

4）LARS回歸

LARS回歸（英文名： Least Angle Regression，最小角回歸）。Efron於2004年提出的一種變數選擇的方法，類似於向前逐步回歸(Forward Stepwise)的形式。從解的過程上來看它是LASSO回歸的一種高效解法。

最小角回歸和模型選擇比較像，是一個逐步的過程，每一步都選擇一個相關性最大的特徵，總的運算步數只和特徵的數目有關，和訓練集的大小無關。最小角回歸訓練時的輸入為特徵矩陣 X={X1,X2,...,XP}，和期輸出向量Y={y1,y2,...,yN}，Xi 是長度為N的矩陣，N表示訓練集的大小，P則是特徵的數目。還有一點需要注意的是，向量Xi 和 Y 都是正則化之後的向量，即它們的元素的均值為0，且每個向量的長度都是1，這樣做的目的是為了後面計算相關性以及角度的方便。

有點像Forward Stepwise（向前逐步回歸），但和Forward Stepwise不同點在於，Forward Stepwise每次都是根據選擇的變數子集，完全擬合出線性模型，計算出RSS，再設計統計量（如AIC）對較高的模型複雜度作出懲罰，而LARS是每次先找出和因變數相關度最高的那個變數, 再沿著LSE的方向一點點調整這個predictor的係數，在這個過程中，這個變數和殘差的相關係數會逐漸減小，等到這個相關性沒那麼顯著的時候，就要選進新的相關性最高的變數，然後重新沿著LSE的方向進行變動。而到最後，所有變數都被選中，估計就和LSE相同了。

LARS的演算法實際執行步驟如下： 1. 對Predictors進行標準化（去除不同尺度的影響），對Target Variable進行中心化（去除截距項的影響），初始的所有係數都設為0，此時殘差 r 就等於中心化後的Target Variable。 2. 找出和殘差r相關度最高的變數X_j。 3. 將X_j的係數Beta_j 從0開始沿著LSE（只有一個變數X_j的最小二乘估計）的方向變化，直到某個新的變數X_k與殘差r的相關性大於X_j時。4. X_j和X_k的係數Beta_j和Beta_k，一起沿著新的LSE【Least Squares Estimate最小二乘估計】（加入了新變數X_k的最小二乘估計）的方向移動，直到有新的變數被選入。5. 重複2，3，4，直到所有變數被選入，最後得到的估計就是普通線性回歸的OLS。

5）支持向量回歸

SVR支持向量回歸（英文名： Support-Vector Regression）。支持向量機（ SVM ）是一種比較好的實現了結構風險最小化思想的方法。它的機器學習策略是結構風險最小化原則為了最小化期望風險，應同時最小化經驗風險和置信範圍）

支持向量機方法可以用於回歸和分類，它的基本思想：（ 1 ）它是專門針對有限樣本情況的學習機器，實現的是結構風險最小化：在對給定的數據逼近的精度與逼近函數的複雜性之間尋求折衷，以期獲得最好的推廣能力；（ 2 ）它最終解決的是一個凸二次規劃問題，從理論上說，得到的將是全局最優解，解決了在神經網路方法中無法避免的局部極值問題；（ 3 ）它將實際問題通過非線性變換轉換到高維的特徵空間，在高維空間中構造線性決策函數來實現原空間中的非線性決策函數，巧妙地解決了維數問題，並保證了有較好的推廣能力，而且演算法複雜度與樣本維數無關。

目前， SVM 演算法在模式識別、回歸估計、概率密度函數估計等方面都有應用，且演算法在效率與精度上已經超過傳統的學習演算法或與之不相上下。對於經驗風險R，可以採用不同的損失函數來描述，如e不敏感函數、Quadratic函數、Huber函數、Laplace函數等。核函數一般有多項式核、高斯徑向基核、指數徑向基核、多隱層感知核、傅立葉級數核、樣條核、 B 樣條核等，雖然一些實驗表明在分類中不同的核函數能夠產生幾乎同樣的結果，但在回歸中，不同的核函數往往對擬合結果有較大的影響。

支持向量回歸演算法主要是通過升維後，在高維空間中構造線性決策函數來實現線性回歸，用e不敏感函數時，其基礎主要是 e 不敏感函數和核函數演算法。若將擬合的數學模型表達多維空間的某一曲線，則根據e 不敏感函數所得的結果，就是包括該曲線和訓練點的「 e管道」。在所有樣本點中，只有分布在「管壁」上的那一部分樣本點決定管道的位置。這一部分訓練樣本稱為「支持向量」。為適應訓練樣本集的非線性，傳統的擬合方法通常是在線性方程後面加高階項。此法誠然有效，但由此增加的可調參數未免增加了過擬合的風險。支持向量回歸演算法採用核函數解決這一矛盾。用核函數代替線性方程中的線性項可以使原來的線性演算法「非線性化」，即能做非線性回歸。與此同時，引進核函數達到了「升維」的目的，而增加的可調參數是過擬合依然能控制。

6）CART回歸

CART（英文名： Classification And Regression Tree分類回歸樹），是一種很重要的機器學習演算法，既可以用於創建分類樹（Classification Tree），也可以用於創建回歸樹（Regression Tree）。將CART用於回歸分析時就叫做CART回歸。

CART演算法的重要基礎包含以下三個方面：（1）二分(Binary Split)：在每次判斷過程中，都是對觀察變數進行二分。CART演算法採用一種二分遞歸分割的技術，演算法總是將當前樣本集分割為兩個子樣本集，使得生成的決策樹的每個非葉結點都只有兩個分枝。因此CART演算法生成的決策樹是結構簡潔的二叉樹。因此CART演算法適用於樣本特徵的取值為是或非的場景，對於連續特徵的處理則與C4.5演算法相似。（2）單變數分割(Split Based on One Variable)：每次最優劃分都是針對單個變數。（3）剪枝策略：CART演算法的關鍵點，也是整個Tree-Based演算法的關鍵步驟。剪枝過程特別重要，所以在最優決策樹生成過程中佔有重要地位。有研究表明，剪枝過程的重要性要比樹生成過程更為重要，對於不同的劃分標準生成的最大樹(Maximum Tree)，在剪枝之後都能夠保留最重要的屬性劃分，差別不大。反而是剪枝方法對於最優樹的生成更為關鍵。

當數據擁有眾多特徵並且特徵之間關係十分複雜時，構建全局模型的想法就顯得太難了，也略顯笨拙。而且，實際生活中很多問題都是非線性的，不可能使用全局線性模型來擬合任何數據。一種可行的方法是將數據集切分成很多份易建模的數據，然後利用線性回歸技術來建模。如果首次切分後仍然難以擬合線性模型就繼續切分。在這種切分方式下，樹結構和回歸法就相當有用。

創建回歸樹時，觀察值取值是連續的、沒有分類標籤，只有根據觀察數據得出的值來創建一個預測的規則。在這種情況下，Classification Tree的最優劃分規則就無能為力，CART則使用最小剩餘方差(Squared Residuals Minimization)來決定Regression Tree的最優劃分，該劃分準則是期望劃分之後的子樹誤差方差最小。創建模型樹，每個葉子節點則是一個機器學習模型，如線性回歸模型。

回歸樹與分類樹的思路類似，但葉節點的數據類型不是離散型，而是連續型，對CART稍作修改就可以處理回歸問題。CART演算法用於回歸時根據葉子是具體值還是另外的機器學習模型又可以分為回歸樹和模型樹。但無論是回歸樹還是模型樹，其適用場景都是：標籤值是連續分布的，但又是可以劃分群落的，群落之間是有比較鮮明的區別的，即每個群落內部是相似的連續分布，群落之間分布確是不同的。所以回歸樹和模型樹既算回歸，也稱得上分類。

回歸是為了處理預測值是連續分布的情景，其返回值應該是一個具體預測值。回歸樹的葉子是一個個具體的值，從預測值連續這個意義上嚴格來說，回歸樹不能稱之為「回歸演算法」。因為回歸樹返回的是「一團」數據的均值，而不是具體的、連續的預測值（即訓練數據的標籤值雖然是連續的，但回歸樹的預測值卻只能是離散的）。所以回歸樹其實也可以算為「分類」演算法，其適用場景要具備「物以類聚」的特點，即特徵值的組合會使標籤屬於某一個「群落」，群落之間會有相對鮮明的「鴻溝」。如人的風格是一個連續分布，但是卻又能「群分」成文藝、普通和2B三個群落，利用回歸樹可以判斷一個人是文藝還是2B，但卻不能度量其有多文藝或者多2B。所以，利用回歸樹可以將複雜的訓練數據劃分成一個個相對簡單的群落，群落上可以再利用別的機器學習模型再學習。

模型樹的葉子是一個個機器學習模型，如線性回歸模型，所以更稱的上是「回歸」演算法。利用模型樹就可以度量一個人的文藝值了。回歸樹和模型樹也需要剪枝,剪枝理論和分類樹相同。為了獲得最佳模型，樹剪枝常採用預剪枝和後剪枝結合的方法進行。

樹回歸中，為成功構建以分段常數為葉節點的樹，需要度量出數據的一致性。分類決策樹創建時會在給定節點時計算分類數據的混亂度。那麼如何計算連續型數值的混亂度呢？事實上，在連續數據集上計算混亂度是非常簡單的–度量按某一特徵劃分前後標籤數據總差值，每次選取使數據總差值最小的那個特徵做最佳分支特徵為了對正負差值同等看待，一般使用絕對值或平方值來代替上述差值）。為什麼選擇計算差值呢》差值越小，相似度越高，越可能屬於一個群落咯。那麼如果選取方差做差值，總方差的計算方法有兩種：（1）計算數據集均值std，計算每個數據點與std的方差，然後n個點求和。（2）計算數據集方差var，然後var_sum = var*n，n為數據集數據數目。Python Matrix中可以利用var方法求得數據集方差，因此該方法簡單、方便。

與Gini Gain對離散特徵和連續特徵的處理方法類似，多值離散特徵需要選擇最優二分序列，連續特徵則要找出最優分裂點。那麼，每次最佳分支特徵的選取過程為：function chooseBestSplitFeature()(1)先令最佳方差為無限大bestVar=inf。(2)依次計算根據某特徵（FeatureCount次迭代）劃分數據後的總方差currentVar（，計算方法為：劃分後左右子數據集的總方差之和），如果currentVar<bestVar，則bestVar=currentVar.(3)返回最佳分支特徵、分支特徵值（離散特徵則為二分序列、連續特徵則為分裂點的值），左右分支子數據集。

7）CART分類

當將CART用於分類問題時需要構建CART分類樹。

創建分類樹遞歸過程中，CART每次都選擇當前數據集中具有最小Gini信息增益的特徵作為結點劃分決策樹。ID3演算法和C4.5演算法雖然在對訓練樣本集的學習中可以儘可能多地挖掘信息，但其生成的決策樹分支、規模較大，CART演算法的二分法可以簡化決策樹的規模，提高生成決策樹的效率。對於連續特徵，CART也是採取和C4.5同樣的方法處理。為了避免過擬合(Overfitting)，CART決策樹需要剪枝。預測過程當然也就十分簡單，根據產生的決策樹模型，延伸匹配特徵值到最後的葉子節點即得到預測的類別。

CART與C4.5的不同之處是節點分裂建立在GINI指數這個概念上，GINI指數主要是度量數據劃分或訓練數據集的不純度為主。GINI值越小，表明樣本的純凈度越高（即該樣本只屬於同一類的概率越高）。衡量出數據集某個特徵所有取值的Gini指數後，就可以得到該特徵的Gini Split info，也就是GiniGain。不考慮剪枝情況下，分類決策樹遞歸創建過程中就是每次選擇GiniGain最小的節點做分叉點，直至子數據集都屬於同一類或者所有特徵用光了。

因為CART二分的特性，當訓練數據具有兩個以上的類別，CART需考慮將目標類別合併成兩個超類別，這個過程稱為雙化。GINI指數是一種不等性度量，通常用來度量收入不平衡，可以用來度量任何不均勻分布，是介於0~1之間的數，0-完全相等，1-完全不相等。分類度量時，總體內包含的類別越雜亂，GINI指數就越大(跟熵的概念很相似)。對於一個數據集T，其Gini計算方式為：

分析分類回歸樹的遞歸建樹過程，不難發現它實質上存在著一個數據過度擬合問題。在決策樹構造時，由於訓練數據中的噪音或孤立點，許多分枝反映的是訓練數據中的異常，使用這樣的判定樹對類別未知的數據進行分類，分類的準確性不高。因此試圖檢測和減去這樣的分支，檢測和減去這些分支的過程被稱為樹剪枝。樹剪枝方法用於處理過分適應數據問題。通常，這種方法使用統計度量，減去最不可靠的分支，這將導致較快的分類，提高樹獨立於訓練數據正確分類的能力。決策樹常用的剪枝常用的簡直方法有兩種：預剪枝(Pre-Pruning)和後剪枝(Post-Pruning)。預剪枝是根據一些原則及早的停止樹增長，如樹的深度達到用戶所要的深度、節點中樣本個數少於用戶指定個數、不純度指標下降的最大幅度小於用戶指定的幅度等；後剪枝則是通過在完全生長的樹上剪去分枝實現的，通過刪除節點的分支來剪去樹節點，可以使用的後剪枝方法有多種，比如：代價複雜性剪枝、最小誤差剪枝、悲觀誤差剪枝等等。CART常採用事後剪枝方法，構建決策樹過程中的第二個關鍵就是用獨立的驗證數據集對訓練集生長的樹進行剪枝。