1
介紹
關於機器學習算法的研究已經獲得了巨大的成功，哈佛商業評論甚至將數據科學家稱為二十一世紀最具誘惑力的工作。
機器學習算法是在沒有人為幹涉的情況下，從大量的數據和歷史經驗中學習數據的結構並提升對某一目標的估計的算法。學習任務包括：
學習從輸入到輸出的函數學習沒有標籤的數據的潛在結構基於實體的學習（『instance-based learning』），譬如根據訓練數據，對新的實體分類，判斷其的類別。
2 機器學習算法的類型
1 有監督學習（supervised learning）：
有監督學習通常是利用帶有專家標註的標籤的訓練數據，學習一個從輸入變量X到輸入變量Y的函數映射。
Y = f (X)
訓練數據通常是(n×x,y)的形式，其中n代表訓練樣本的大小，x和y分別是變量X和Y的樣本值。
（專家標註是指，需要解決問題所需要的領域專家，對數據預先進行人為的分析）
利用有監督學習解決的問題大致上可以被分為兩類：
分類問題：預測某一樣本所屬的類別（離散的）。比如給定一個人（從數據的角度來說，是給出一個人的數據結構，包括：身高，年齡，體重等信息），然後判斷是性別，或者是否健康。回歸問題：預測某一樣本的所對應的實數輸出（連續的）。比如預測某一地區人的平均身高。
本文中所介紹的前五個算法（線性回歸，邏輯回歸，分類回歸樹，樸素貝葉斯，K最近鄰算法）均是有監督學習的例子。
除此之外，集成學習也是一種有監督學習。它是將多個不同的相對較弱的機器學習模型的預測組合起來，用來預測新的樣本。本文中所介紹的第九個和第十個算法（隨機森林裝袋法，和XGBoost算法）便是集成技術的例子。
2 無監督學習（Unsupervised learning）：
無監督學習問題處理的是，只有輸入變量X沒有相應輸出變量的訓練數據。它利用沒有專家標註訓練數據，對數據的結構建模。
可以利用無監督學習解決的問題，大致分為兩類：
關聯分析：發現不同事物之間同時出現的概率。在購物籃分析中被廣泛地應用。如果發現買麵包的客戶有百分之八十的概率買雞蛋，那麼商家就會把雞蛋和麵包放在相鄰的貨架上。聚類問題：將相似的樣本劃分為一個簇（cluster）。與分類問題不同，聚類問題預先並不知道類別，自然訓練數據也沒有類別的標籤。維度約減：顧名思義，維度約減是指減少數據的維度同時保證不丟失有意義的信息。利用特徵提取方法和特徵選擇方法，可以達到維度約減的效果。特徵選擇是指選擇原始變量的子集。特徵提取是將數據從高緯度轉換到低緯度。廣為熟知的主成分分析算法就是特徵提取的方法。
本文介紹的第六-第八（Apriori算法，K-means算法，PCA主成分分析）都屬於無監督學習。
3 強化學習（Reinforcement learning）：
通過學習可以獲得最大回報的行為，強化學習可以讓agent（個體）根據自己當前的狀態，來決定下一步採取的動作。
強化學習算法通過反覆試驗來學習最優的動作。這類算法在機器人學中被廣泛應用。在與障礙物碰撞後，機器人通過傳感收到負面的反饋從而學會去避免衝突。在視頻遊戲中，我們可以通過反覆試驗採用一定的動作，獲得更高的分數。Agent能利用回報去理解玩家最優的狀態和當前他應該採取的動作。
3
哪些是最流行的機器學習算法
有很多調查報告都對最流行的十種數據挖掘算法進行了統計。然而，這些報告都帶有非常重的主觀色彩。並且就引用文件而言，參與調查的人樣本規模和類型都很窄。大部分都是數據挖掘的高級從業人員，ACM KDD創新獎、IEEE ICDM研究貢獻獎的獲獎者，KDD-06，ICDM'06和SDM'06的計劃委員會成員;和ICDM'06的145名與會者。
而本文中top10的算法更適用於初學者，主要是原文作者在孟買大學學習「數據倉庫與挖掘」的課程中學習到的。
4
有監督學習算法
1 線性回歸
在機器學習當中，我們有一個變量X的集合用來決定輸出變量Y。在輸入變量X和輸出變量Y之間存在著某種關係。機器學習的目的就是去量化這種關係。
圖 1：用直線y=a+bx表示的線性回歸
在線性回歸裡，輸入變量X和輸出變量Y之間的關係，用等式Y = a + bX 來表示。因此，線性回歸的目標便是找出係數a和b的值。在這裡，a是截距，b是斜率。
圖1繪製了數據中X和Y的值。我們的目標是去擬合一條最接近所有點的直線。這意味著，直線上每一個X對應點的Y值與實際數據中點X對應的Y值，誤差最小。
2 邏輯回歸
使用一個轉換函數後，線性回歸預測的是連續的值（比如降雨量），而邏輯回歸預測的是離散的值（比如一個學生是否通過考試，是：0，否：1）。
邏輯回歸最適用於二分類（數據只分為兩類，Y = 0或1，一般用1作為默認的類。比如：預測一個事件是否發生，事件發生分類為1；預測一個人是否生病，生病分類為1）。我們稱呼其為邏輯回歸（logistic regression）是因為我們的轉換函數採用了logistic function (h(x)=1/(1+e的-x次方)) 。
在邏輯回歸中，我們首先得到的輸出是連續的默認類的概率p（0小於等於p小於等於1）。轉換函數 (h(x)=1/(1+e的-x次方))的值域便是（0,1）。我們對該函數設置一個域值t。若概率p>t，則預測結果為1。
圖 2 使用邏輯回歸來判斷腫瘤是惡性還是良性。如果概率p大於0.5，則是惡性
在圖2中，判斷腫瘤是惡性還是良性。默認類y=1（腫瘤是惡性）。當變量X是測量腫瘤的信息，如腫瘤的尺寸。如圖所示，logistic函數由變量X得到輸出p。域值t在這裡設置為0.5。如果p大於t，那麼腫瘤則是惡性。
我們考慮邏輯回歸的一種變形：
因此，邏輯回歸的目標便是訓練數據找到適當的參數的值，使得預測的輸出和實際的輸出最小。我們使用最大似然估計來對參數進行估計。
3 分類回歸樹（CART）
分類回歸樹是諸多決策樹模型的一種實現，類似還有ID3、C4.5等算法。
非終端節點有根節點（Root Node）和內部節點(Internal Node)。終端節點是葉子節點(Leaf Node)。每一個非終端節點代表一個輸出變量X和一個分岔點，葉葉子節點代表輸出變量Y，見圖3。沿著樹的分裂（在分岔點做一次決策）到達葉子節點，輸出便是當前葉子節點所代表的值。
圖3中的決策樹，根據一個人的年齡和婚姻狀況進行分類：1.購買跑車；2.購買小型貨車。如果這個人30歲還沒有結婚，我們沿著決策樹的過程則是：『超過30年？--是--已婚？--否，那麼我們的輸出便是跑車。
圖 3 決策樹的某一部分
4 樸素貝葉斯
在給定一個事件發生的前提下，計算另外一個事件發生的概率——我們將會使用貝葉斯定理。
設先驗知識為d，為了計算我們的假設h為真的概率，我們將要使用如下貝葉斯定理：
其中：
P(h|d)=後驗概率。這是在給定數據d的前提下，假設h為真的概率。P(d|h)=可能性。這是在給定假設h為真的前提下，數據d的概率。P(h)=類先驗概率。這是假設h為真時的概率（與數據無關）P(d)=預測器先驗概率。這是數據的概率（與假設無關）
之所以稱之為樸素是因為該算法假定所有的變量都是相互獨立的（在現實生活大多數情況下都可以做這樣的假設）。
圖 4 樸素貝葉斯，用變量天氣來預測選手的狀態
如圖4，當天氣是晴天的時候（第一列第一行），選手的狀態是如何的呢？
在給定變量天氣是晴天（sunny）的時候，為了判斷選手的狀態是『yes』還是『no』，計算概率，然後選擇概率更高的作為輸出。
因此，當天氣是晴天的時候，選手的狀態是『yes』
5 K最近鄰（KNN）
K最近鄰算法是利用整個數據集作為訓練集，而不是將數據集分成訓練集和測試集。
當要預測一個新的輸入實體的輸出時，k最近鄰算法尋遍整個數據集去發現k個和新的實體距離最近的實體，或者說，k個與新實體最相似的實體，然後得到這些輸出的均值（對於回歸問題）或者最多的類（對於分類問題）。而k的值一般由用戶決定。
不同實體之間的相似度，不同的問題有不同的計算方法，包括但不限於：Euclidean distance 和Hamming distance。
5
無監督學習算法
6 關聯規則算法
關聯規則算法在資料庫的候選項集中用來挖掘出現頻繁項集，並且發現他們之間的關聯規則。關聯規則算法在購物籃分析中得到了很好的應用。所謂的購物籃分析，是指找到資料庫中出現頻率最高的事物的組合。通常，如果存在關聯規則：「購買了商品x的人，也會購買商品y」，我們將其記作：x--y。
比如，如果一個人購買了牛奶和糖，那麼他很有可能會購買咖啡粉。在充分考慮了支持度（support）和置信度（confidence）後，得到關聯規則。
圖 5 關聯規則x--y的支持度，置信度和提升度公式。Frq(x)代表x的頻數。
支持度（support）檢驗項目集是否頻繁。支持度的檢驗是符合Apriori原理的，即當一個項目集是頻繁的，那麼它所有的子集一定也是頻繁的。
我們通過置信度（confidence）的高低，從頻繁項集中找出強關聯規則。
根據提升度（lift），從強關聯規則中篩選出有效的強關聯規則。
7. K-means算法
k-means算法是一個迭代算法的聚類算法，它將相似的數據化到一個簇（cluster）中。該算法計算出k個簇的中心點，並將數據點分配給距離中心點最近的簇。
圖 6 k-means算法的步驟
1. k-means初始化：
a) 選擇一個k值。如圖6，k=3。
b) 隨機分配每一個數據點到三個簇中的任意一個。
c) 計算每一個簇的中心點。如圖6，紅色，藍色，綠色分別代表三個簇的中心點。
2. 將每一個觀察結果與當前簇比較：
a) 重新分配每一個點到距中心點最近的簇中。如圖6，上方5個點被分配給藍色中心點的簇。
3. 重新計算中心點：
a) 為新分配好的簇計算中心點。如圖六，中心點改變。
4. 迭代，不再改變則停止：
a) 重複步驟2-3，直到所有點所屬簇不再改變。
8. 主成分分析（PCA）
主成分分析是通過減少變量的維度，去除數據中冗餘的部分或實現可視化。基本的思路將數據中最大方差的部分反映在一個新的坐標系中，這個新的坐標系則被稱為「主要成分」。其中每一個成分，都是原來成分的線性組合，並且每一成分之間相互正交。正交性保證了成分之間是相互獨立的。
第一主成分反映了數據最大方差的方向。第二主成分反映了數據中剩餘的變量的信息，並且這些變量是與第一主成分無關的。同樣地，其他主成分反映了與之前成分無關的變量的信息。
圖 7 三維的變量降維到二維的主成分分析
6
集成學習技術
集成學習是一種將不同學習模型（比如分類器）的結果組合起來，通過投票或平均來進一步提高準確率。一般，對於分類問題用投票；對於回歸問題用平均。這樣的做法源於「眾人拾材火焰高」的想法。
集成算法主要有三類：Bagging，Boosting 和Stacking。本文將不談及stacking。
9. 使用隨機森林的Bagging
隨機森林算法（多個模型）是袋裝決策樹（單個模型）的提升版。
Bagging的第一步是針對數據集，利用自助抽樣法（Bootstrap Sampling method）建造多個模型。
所謂的自助抽樣，是指得到一個由原始數據集中隨機的子集組成的新的訓練集。每一個這樣的訓練集都和原始訓練集的大小相同，但其中有一些重複的數據，因此並不等於原始訓練集。並且，我們將原始的數據集用作測試集。因此，如果原始數據集的大小為N，那麼新的訓練集的大小也為N（其中不重複的數據數量為2N/3），測試集的大小為N。
Bagging的第二步是在抽樣的不同的訓練集上，利用相同的算法建造多個模型。
在這裡，我們以隨機森林為例。決策樹是靠每一個節點在最重要的特徵處分離來減小誤差的，但與之不同，隨機森林中，我們選擇了隨機塞選的特徵來構造分裂點。這樣可以減小所得預測之間的相關性。
每一個分裂點搜索的特徵的數量，是隨機森林算法的參數。
因此，用隨機森林算法實現的Bagging，每一個樹都是用隨機樣本構造的，每一個分裂點都是用隨機的預測器構造的。
10.用AdaBoost實現的Boosting
a) 因為Bagging中的每一個模型是獨立構造的，我們認為它是並行集成的。與之不同，Boosting中的每一個模型，都是基於對前一個模型的過失進行修正來構造的，因此Boosting是線性的。
b) Bagging中採用的是簡單的投票，每一個分類器相當於一個投票（節點分裂，相當於進行一次投票），最後的輸出是與大多數的投票有關；而在Boosting中，我們對每一個投票賦予權重，最後的輸出也與大多數的投票有關——但是它卻是線性的，因為賦予了更大的權重給被前一個模型錯誤分類的實體（擁有更大的權重，則其誤差的影響被放大，有助於我們得到使得更小誤差的模型）。
AdaBoost指的是自適應增強（Adaptive Boosting）
圖 8 決策樹的AdaBoost
在圖8中，第一、二、三步中弱學習模型被稱作決策樹樁（一個一級的決策樹只依據一個輸入特徵進行預測；一個決策樹的根節點直接連接到它的葉子節點）。構造弱學習模型的過程持續到，a）達到用戶定義的數量，或者 b）繼續訓練已經無法提升。第四步，將三個決策樹樁組合起來。
第一步：從一個決策樹樁開始，根據一個輸入變量作出決定
從圖中可以看見，其中有兩個圓圈分類錯誤，因此我們可以給他們賦予更大的 權重，運用到下一個決策樹樁中。
第二步：依據不同的輸入變量，構造下一個決策樹樁
可以發現第二個決策將會嘗試將更大權重的數據預測正確。和如圖的情況中， 我們需要對另外三個圓圈賦予更大的權重。
第三步：依據不同的輸入變量，訓練不同的決策樹樁
之前步驟一樣，只是這次被預測錯誤的是三角形的數據，因此我們需要對其賦 予更大的權重。
第四步：將決策樹樁組合起來
我們將三個模型組合起來，顯而易見，集成的模型比單個模型準確率更高。
7
結論
在本文中，我們學習到了：
a) 五個有監督學習的算法：線性回歸，邏輯回歸，分類回歸樹，樸素貝葉斯，K最近鄰
b) 三個無監督學習的算法：關聯規則算法，K-means聚類算法，主成分分析
c) 兩個集成算法：用隨機森林實現的Bagging，用XGBoost實現的Boosting。
愛創客邀請函
精彩回顧，點這裡！