從概念到案例：初學者須知的十大機器學習算法
本文先為初學者介紹了必知的十大機器學習(ML)算法，并且我們通過一些圖解和實例生動地解釋這些基本機器學習的概念。我們希望本文能為理解機器學習(ML)基本算法提供簡單易讀的入門概念。
一、機器學習模型
在《哈佛商業(yè)評論》發(fā)表「數(shù)據(jù)科學家是 21 世紀最性感的職業(yè)」之后，機器學習的研究廣受關(guān)注。所以，對于初入機器學習領(lǐng)域的學習者，我們放出來一篇頗受歡迎的博文——《初學者必知的十大機器學習算法》，盡管這只是針對初學者的。
機器學習算法就是在沒有人類干預的情況下，從數(shù)據(jù)中學習，并在經(jīng)驗中改善的一種方法，學習任務(wù)可能包括學習從輸入映射到輸出的函數(shù)，學習無標簽數(shù)據(jù)的隱含結(jié)構(gòu);或者是「基于實例的學習」，通過與存儲在記憶中的訓練數(shù)據(jù)做比較，給一個新實例生成一個類別標簽?；趯嵗膶W習(instance-based learning)不會從具體實例中生成抽象結(jié)果。
二、機器學習算法的類型
有三類機器學習算法：
1. 監(jiān)督學習
可以這樣來描述監(jiān)督學習：使用有標簽的訓練數(shù)據(jù)去學習從輸入變量(X)到輸出變量(Y)的映射函數(shù)。
- Y = f (X)
它分為兩種類型：
- 分類：通過一個給定的輸入預測一個輸出，這里的輸出變量以類別的形式展示。例如男女性別、疾病和健康。
- 回歸：也是通過一個給定的輸入預測一個輸出，這里的輸出變量以實數(shù)的形式展示。例如預測降雨量、人的身高等實數(shù)值。
本文介紹的前 5 個算法就屬于監(jiān)督學習：線性回歸、Logistic 回歸、CART、樸素貝葉斯和 KNN。
集成學習也是一種監(jiān)督學習方法。它意味著結(jié)合多種不同的弱學習模型來預測一個新樣本。本文介紹的第 9、10 兩種算法--隨機森林 Bagging 和 AdaBoost 提升算法就是集成學習技術(shù)。
2. 非監(jiān)督學習
非監(jiān)督學習問提僅僅處理輸入變量(X)，但不會處理對應(yīng)的輸出(也就是說，沒有標簽)。它使用無標簽的訓練數(shù)據(jù)建模數(shù)據(jù)的潛在結(jié)構(gòu)。
非監(jiān)督學習可以分為3種類型：
- 關(guān)聯(lián)：就是去發(fā)覺在同一個數(shù)據(jù)集合中不同條目同時發(fā)生的概率。廣泛地用于市場籃子分析。例如：如果一位顧客買了面包，那么他有 80% 的可能性購買雞蛋。
- 聚類：把更加相似的對象歸為一類，而不是其他類別對象。
- 降維：顧名思義，降維就是減少數(shù)據(jù)集變量，同時要保證重要信息不丟失。降維可以通過使用特征提取和特征選擇方法來完成。特征選擇方法會選擇原始變量的一個子集。特征提取完成了從高維空間到低維空間的數(shù)據(jù)變換。例如，主成分分析(PCA)就是一個特征提取方法。
本文介紹的算法 6-8 都是非監(jiān)督學習的例子：包括 Apriori 算法、K-均值聚類、主成分分析(PCA)。
3. 強化學習
強化學習是這樣一種學習方法，它允許智能體通過學習最大化獎勵的行為，并基于當前狀態(tài)決定下一步要采取的最佳行動。
強化學習一般通過試錯學習到最佳行動。強化學習應(yīng)用于機器人，機器人在碰到障礙物質(zhì)之后會收到消極反饋，它通過這些消極反饋來學會避免碰撞;也用在視頻游戲中，通過試錯發(fā)現(xiàn)能夠極大增長玩家回報的一系列動作。智能體可以使用這些回報來理解游戲中的最佳狀態(tài)，并選擇下一步的行動。
三、監(jiān)督學習
1. 線性回歸
在機器學習中，我們用輸入變量 x 來決定輸出變量 y。輸入變量和輸出變量之間存在一個關(guān)系。機器學習的目標就是去定量地描述這種關(guān)系。
圖 1：以一條直線的形式展示出來的線性回歸：y = ax +b
在線性回歸中，輸入變量 x 和輸出變量 y 的關(guān)系可以用一個方程的形式表達出來：y=ax+b。所以，線性回歸的目標就是尋找參數(shù) a 和 b 的值。這里，a 是直線的斜率，b 是直線的截距。
圖 1 將一個數(shù)據(jù)集中的 x 和 y 用圖像表示出來了。如圖所示，這里的目標就是去尋找一條離大多數(shù)點最近的一條直線。這就是去減小一個數(shù)據(jù)點的 y 值和直線之間的距離。
2. Logistic 回歸
線性回歸預測是連續(xù)值(如厘米級的降雨量)，logistic 回歸預測是使用了一種變換函數(shù)之后得到的離散值(如一位學生是否通過了考試)。
Logistic 回歸最適合于二元分類問題(在一個數(shù)據(jù)集中，y=0 或者 1，1 代表默認類。例如：在預測某個事件是否會發(fā)生的時候，發(fā)生就是 1。在預測某個人是否患病時，患病就是 1)。這個算法是拿它所使用的變換函數(shù)命名的，這個函數(shù)稱為 logistics 函數(shù)(logistics function，h(x)= 1/ (1 + e^x))，它的圖像是一個 S 形曲線。
在 logistic 回歸中，輸出是默認類別的概率(不像線性回歸一樣，輸出是直接生成的)。因為是概率，所以輸出的值域是 [0,1]。輸出值 y 是通過輸入值 x 的對數(shù)變換 h(x)= 1/ (1 + e^ -x) 得到的。然后使用一個閾值強制地讓輸出結(jié)果變成一個二元分類問題。
圖 2：確定一個腫瘤是惡性的還是良性的回歸。如果概率 h(x)>0.5，則是惡性的
在圖 2 中，為了判斷一個腫瘤是不是惡性，默認變量被設(shè)置為 y=1(腫瘤是惡性的);變量 x 可能是對一個腫瘤的檢測結(jié)果，例如腫瘤的尺寸。如圖中所示，logistics 函數(shù)將變量 x 的值變換到了 0 到 1 之間。如果概率超過了 0.5(圖中的水平線為界)，腫瘤就被歸類為惡性。
logistic 回歸的方程 P(x) = e ^ (b0 +b1*x) / (1 + e^(b0 + b1*x))可以被轉(zhuǎn)換為對數(shù)形式： ln(p(x) / 1-p(x)) = b0 + b1*x。
logistic 回歸的目標就是使用訓練數(shù)據(jù)來尋找參數(shù) b0 和 b1 的值，最小化預測結(jié)果和實際值的誤差。這些參數(shù)的評估使用的是最大似然估計的方法。
3. 分類和回歸樹
分類和回歸樹(CART)是決策樹的一種補充。
非終端節(jié)點(non-terminal node)包含根節(jié)點 (root node) 和中間節(jié)點 (internal node)。每一個非終端節(jié)點代表一個單獨的輸入變量 x 和這個變量的分支節(jié)點;葉節(jié)點代表的是輸出變量 y。這個模型按照以下的規(guī)則來作出預測：
圖 3：決策樹的一些部分
4. 樸素貝葉斯法
在給定一個早已發(fā)生的事件的概率時，我們用貝葉斯定理去計算某個事件將會發(fā)生的概率。在給定一些變量的值時，我們也用貝葉斯定理去計算某個結(jié)果的概率，也就是說，基于我們的先驗知識(d)去計算某個假設(shè)(h)為真的概率。計算方法如下：
- P(h|d)= (P(d|h) * P(h)) / P(d)
其中，
- P(h|d) = 后驗概率。就是假設(shè) h 為真概率，給定的數(shù)據(jù)相當于先驗知識 d。其中 P(h|d)= P(d1| h)* P(d2| h)*....*P(dn| h)* P(d)。
- P(d|h) = 似然度。假設(shè) h 正確時，數(shù)據(jù) d 的概率。
- P(h) = 類先驗概率。假設(shè) h 正確的額概率。(無關(guān)數(shù)據(jù))
- P(d) = 預測器先驗概率。數(shù)據(jù)的概率(無關(guān)假設(shè))
這個算法被稱為「樸素」的原因是：它假設(shè)所有的變量是相互獨立的，這也是現(xiàn)實世界中做出的一個樸素的假設(shè)。
圖 4：使用樸素貝葉斯法來預測變量「天氣」變化狀態(tài)
以圖 4 為例，如果天氣=晴天，那么輸出是什么呢?
在給定變量天氣=晴天時，為了判斷結(jié)果是或者否，就要計算 P(yes|sunny) 和 P(no|sunny)，然后選擇概率較大的結(jié)果。
計算過程如下：
- ->P(yes|sunny)= (P(sunny|yes) * P(yes)) / P(sunny)
- = (3/9 * 9/14 ) / (5/14)
- = 0.60
- -> P(no|sunny)= (P(sunny|no) * P(no)) / P(sunny)
- = (2/5 * 5/14 ) / (5/14)
- = 0.40
所以，天氣=晴天時，結(jié)果為是。
5. KNN
KNN 使用了整個數(shù)據(jù)集作為訓練集，而不是將它分為訓練集和測試集。
當給定的一個數(shù)據(jù)實例時，KNN 算法會在整個數(shù)據(jù)集中尋找 k 個與其新樣本距離最近的，或者 k 個與新樣本最相似的，然后，對于回歸問題，輸出結(jié)果的平均值，或者對于分類問題，輸出頻率最高的類。k 的值是用戶自定義的。
樣本之間的相似性是用歐氏距離或者漢明(Hamming)距離來計算的。
四、非監(jiān)督學習算法
6. Apriori 算法
Apriori 算法被用來在交易數(shù)據(jù)庫中進行挖掘頻繁的子集，然后生成關(guān)聯(lián)規(guī)則。常用于市場籃子分析，分析數(shù)據(jù)庫中最常同時出現(xiàn)的交易。通常，如果一個顧客購買了商品 X 之后又購買了商品 Y，那么這個關(guān)聯(lián)規(guī)則就可以寫為：X -> Y。
例如：如果一位顧客購買了牛奶和甜糖，那他很有可能還會購買咖啡粉。這個可以寫成這樣的關(guān)聯(lián)規(guī)則： {牛奶，甜糖} -> 咖啡粉。關(guān)聯(lián)規(guī)則是交叉了支持度(support)和置信度(confidence)的閾值之后產(chǎn)生的。
圖 5： 關(guān)聯(lián)規(guī)則 X→Y 支持度、置信度和提升度的公式表示。
支持度的程度幫助修改在頻繁的項目集中用來作為候選項目集的數(shù)量。這種支持度的衡量是由 Apriori 原則來指導的。Apriori 原則說明：如果一個項目集是頻繁的，那么它的所有子集都是頻繁的。
7. K-均值聚類算法
K-均值是一個對相似的數(shù)據(jù)進行聚類的迭代算法。它計算出 k 個聚類的中心點，并給某個類的聚類分配一個與其中心點距離最近的數(shù)據(jù)點。
圖 6：K-均值算法的步驟
步驟 1：K-均值初始化
- 選擇一個 k 值。這里我們令 k=3。
- 將數(shù)據(jù)點隨機地分配給三個聚類。
- 計算出每個聚類的中心點。圖中的紅色、藍色和綠色的星分別代表三個聚類的中心點。
步驟 2：將每一個觀測值與一個聚類關(guān)聯(lián)起來
- 將每一個數(shù)據(jù)點重新分配給離它最近的一個聚類中心點。如圖所示，上邊的五個數(shù)據(jù)點被分配給了藍星代表的聚類。按照相同的步驟將數(shù)據(jù)點分配給紅色和綠色星代表的聚類中心點。
步驟 3：重新計算中心點
- 計算新聚類的中心點。如圖所示，舊中心點是灰色的，新中心點是紅色、藍色和綠色的。
步驟 4：迭代，然后在數(shù)據(jù)點所屬的聚類不變的時候退出整個過程
- 重復步驟 2-3，直至每一個聚類中的點不會被重新分配到另一個聚類中。如果在兩個連續(xù)的步驟中不再發(fā)生變化，那么就退出 K-均值算法。
8. 主成分分析(PCA)
主成分分析(PCA)通過減少變量的數(shù)目來使數(shù)據(jù)變得更加易于探索和可視化。這通過將數(shù)據(jù)中擁有最大方差的數(shù)據(jù)抽取到一個被稱為「主成分」的新坐標系中。每一個成分都是原始變量的一個新的線性組合，且是兩兩統(tǒng)計獨立的。統(tǒng)計獨立意味著這些成分的相關(guān)系數(shù)是 0。
第一主成分捕獲的是數(shù)據(jù)中最大方差的數(shù)據(jù)。第二主成分捕獲的是剩下的數(shù)據(jù)中方差最大但是與第一主成分相互獨立的數(shù)據(jù)。相似地，后續(xù)的主成分(例如 PC3、PC4)都是剩下的數(shù)據(jù)中方差最大的但是與之前的主成分保持獨立的數(shù)據(jù)。
圖 7：使用主成分分析方法(PCA)，三種初始變量(基因)被降為兩種新變量
五、集成學習技術(shù)
集成意味著通過投票或者取平均值的方式，將多個學習器(分類器)結(jié)合起來以改善結(jié)果。在分類的時候進行投票，在回歸的時候求平均值。核心思想就是集成多個學習器以使性能優(yōu)于單個學習器。有三種集成學習的方法：裝袋(Bagging)、提升(Boosting)和堆疊(Stacking)。本文不涉及堆疊。
9. 隨機森林 Bagging
隨機森林(多個學習器)是在裝袋決策樹(單個學習器)上做的改進。
Bagging：Bagging 的第一步就是在使用 Bootstrap 采樣方法得到的數(shù)據(jù)庫中創(chuàng)建多個模型，每個生成的訓練集都是原始數(shù)據(jù)集的子集。每個訓練集都有相同的大小，但是有些樣本重復出現(xiàn)了很多次，有些樣本一次未出現(xiàn)。然后，整個原始數(shù)據(jù)集被用為測試集。那么，如果原始數(shù)據(jù)集的大小為 N，則每個生成的訓練集的大小也是 N，唯一(沒有重復)樣本的大小大約是 2*N/3;測試集的大小也是 N。
Bagging 的第二步就是使用同一個算法在不同的數(shù)據(jù)集上生成多個模型。然后，我們討論一下隨機森林。在決策樹中，每個節(jié)點都在最好的、能夠最小化誤差的最佳特征上進行分支，而隨機森林與之不同，我們選擇隨機分支的特征來構(gòu)建最佳的分支。進行隨機處理的原因在于：即便使用了 Bagging，當決策樹選擇最佳特征來分支的時候，它們最終會有相似的模型和相關(guān)聯(lián)的預測結(jié)果。但是用隨機子集上的特征進行分支意味著子樹做的預測是沒有多少相關(guān)性的。
10. AdaBoost 提升算法
a)Bagging 是并行集成，因為每個模型都是獨立建立的。然而，提升是一個順序性集成，每個模型都要糾正前面模型的錯誤分類。
b)Bagging 主要涉及到「簡單投票」，每個分類器都投票得到一個最終結(jié)果，這個分類結(jié)果是由并行模型中的大多數(shù)模型做出的;提升則使用「權(quán)重投票」。每個分類器都會投票得到一個由大多數(shù)模型做出的結(jié)果—但是建立這些順序性模型的時候，給之前誤分類樣本的模型賦予了較大的權(quán)重。
Adaboost 指的是適應(yīng)性提升。
圖 9：一個決策樹的 Adaboost
在圖 9 中，步驟 1、2、3 指的是被稱為決策樁(decision stump)的弱學習器(是一個僅依靠一個輸入作出決策的 1 級決策樹;是一種根節(jié)點直接連接到葉節(jié)點的決策樹)。構(gòu)造決策樹的過程會一直持續(xù)，直到用戶定義了一個弱學習器的數(shù)目，或者訓練的時候再也沒有任何提升的時候。步驟 4 結(jié)合了之前模型中的 3 個決策樁(所以在這個決策樹中就有 3 種分支規(guī)則)。
步驟 1：開始用 1 個決策樁來根據(jù) 1 個輸入變量做決策
- 數(shù)據(jù)點的大小說明我們應(yīng)用了等權(quán)重來將它們分為圓形或者三角形。決策樁在圖的上半部分用一條水平線來對這些點進行分類。我們可以看到，有兩個圓被誤分為三角形。所以，我們會賦予這兩個圓更大的權(quán)重，然后使用另一個決策樁(decision stump)。
步驟 2：轉(zhuǎn)向下一個決策樁，對另一個輸入變量進行決策
- 我們可以看到，之前的步驟中誤分類的兩個圓要比其余數(shù)據(jù)點大。現(xiàn)在，第二個決策樁要嘗試正確地預測這兩個圓。
- 賦予更大權(quán)重的結(jié)果就是，這兩個圓被左邊的豎線正確地分類了。但是這又導致了對上面 3 個小圓的誤分類。因此，我們要在另一個決策樁對這三個圓賦予更大的權(quán)重。
步驟 3：訓練另一個決策樁對下一個輸入變量進行決策。
- 上一步誤分類的 3 個圓要比其他的數(shù)據(jù)點大?，F(xiàn)在，在右邊生成了一條豎線，對三角形和圓進行分類。
步驟 4：結(jié)合決策樁
- 我們結(jié)合了之前 3 步的決策樁，然后發(fā)現(xiàn)一個復雜的規(guī)則將數(shù)據(jù)點正確地分類了，性能要優(yōu)于任何一個弱學習器。
六、結(jié)語
回顧一下，本文主要學到的內(nèi)容：
- 5 種監(jiān)督學習技術(shù)：線性回歸、Logistic 回歸、CART(分類和決策樹)、樸素貝葉斯法和 KNN。
- 3 種非監(jiān)督學習技術(shù)：Apriori 算法、K-均值聚類、主成分分析(PCA)。
- 兩種集成學習方法：Bagging 隨機森林、AdaBoost 提升。
綜上所述，機器學習的基本屬性可以總結(jié)為以下：
- 機器學習是(使用樣本獲取近似函數(shù)的)統(tǒng)計學的一個分支。我們有一個確實存在的理論函數(shù)或分布用以生成數(shù)據(jù)，但我們目前不知道它是什么。我們可以對這個函數(shù)進行抽樣，這些樣本選自我們的訓練集。
- 以圖片描述任務(wù)為例：函數(shù)：f⋆(圖片)→圖片描述，樣本：data∈(image，description)。注意：由于一個物體有許多有效的描述，所以描述是文本空間中的一個分布：圖片描述〜文本。
- 機器的目標是找到模型：有足夠的表現(xiàn)力來逼近真正的函數(shù)，找到一個高效的算法，它使用訓練數(shù)據(jù)找到函數(shù)最優(yōu)解。而且此最優(yōu)解必須對未知輸入有良好的泛化能力。
