一訂教你如何學習演算法

機器學習模型

機器學習演算法就是在沒有人類干預的情況下，從資料中學習，並在經驗中改善的一種方法，學習任務可能包括學習從輸入對映到輸出的函式，學習無標籤資料的隱含結構；或者是「基於例項的學習」，透過與儲存在記憶中的訓練資料做比較，給一個新例項生成一個類別標籤。基於例項的學習（instance-based learning）不會從具體例項中生成抽象結果。

機器學習演算法的型別

有三類機器學習演算法：

1. 監督學習:

可以這樣來描述監督學習：使用有標籤的訓練資料去學習從輸入變數（X）到輸出變數（Y）的對映函式。

Y = f (X)

它分為兩種型別：

a. 分類：透過一個給定的輸入預測一個輸出，這裡的輸出變數以類別的形式展示。例如男女性別、疾病和健康。

b. 迴歸：也是透過一個給定的輸入預測一個輸出，這裡的輸出變數以實數的形式展示。例如預測降雨量、人的身高等實數值。

本文介紹的前 5 個演算法就屬於監督學習：線性迴歸、Logistic 迴歸、CART、樸素貝葉斯和 KNN。

整合學習也是一種監督學習方法。它意味著結合多種不同的弱學習模型來預測一個新樣本。本文介紹的第 9、10 兩種演算法–隨機森林 Bagging 和 AdaBoost 提升演算法就是整合學習技術。

2. 非監督學習:

非監督學習問提僅僅處理輸入變數（X），但不會處理對應的輸出（也就是說，沒有標籤）。它使用無標籤的訓練資料建模資料的潛在結構。

非監督學習可以分為 2 種類型：

a. 關聯：就是去發覺在同一個資料集合中不同條目同時發生的機率。廣泛地用於市場籃子分析。例如：如果一位顧客買了麵包，那麼他有 80% 的可能性購買雞蛋。

b. 聚類：把更加相似的物件歸為一類，而不是其他類別物件。

c. 降維：顧名思義，降維就是減少資料集變數，同時要保證重要資訊不丟失。降維可以透過使用特徵提取和特徵選擇方法來完成。特徵選擇方法會選擇原始變數的一個子集。特徵提取完成了從高維空間到低維空間的資料變換。例如，主成分分析（PCA）就是一個特徵提取方法。

本文介紹的演算法 6-8 都是非監督學習的例子：包括 Apriori 演算法、K-均值聚類、主成分分析（PCA）。

3. 強化學習:

強化學習是這樣一種學習方法，它允許智慧體透過學習最大化獎勵的行為，並基於當前狀態決定下一步要採取的最佳行動。

強化學習一般透過試錯學習到最佳行動。強化學習應用於機器人，機器人在碰到障礙物質之後會收到消極反饋，它透過這些消極反饋來學會避免碰撞；也用在影片遊戲中，透過試錯發現能夠極大增長玩家回報的一系列動作。智慧體可以使用這些回報來理解遊戲中的最佳狀態，並選擇下一步的行動。

監督學習

1. 線性迴歸

在機器學習中，我們用輸入變數 x 來決定輸出變數 y。輸入變數和輸出變數之間存在一個關係。機器學習的目標就是去定量地描述這種關係。

2.Logistic 迴歸

線性迴歸預測是連續值（如釐米級的降雨量），logistic 迴歸預測是使用了一種變換函式之後得到的離散值（如一位學生是否通過了考試）。

Logistic 迴歸最適合於二元分類問題（在一個數據集中，y=0 或者 1，1 代表預設類。例如：在預測某個事件是否會發生的時候，發生就是 1。在預測某個人是否患病時，患病就是 1）。這個演算法是拿它所使用的變換函式命名的，這個函式稱為 logistics 函式（logistics function，h(x)= 1/ (1 + e^x)），它的影象是一個 S 形曲線。

在 logistic 迴歸中，輸出是預設類別的機率（不像線性迴歸一樣，輸出是直接生成的）。因為是機率，所以輸出的值域是 [0,1]。輸出值 y 是透過輸入值 x 的對數變換 h(x)= 1/ (1 + e^ -x) 得到的。然後使用一個閾值強制地讓輸出結果變成一個二元分類問題。

3. 分類和迴歸樹

分類和迴歸樹（CART）是決策樹的一種補充。

非終端節點（non-terminal node）包含根節點 (root node) 和中間節點 (internal node)。每一個非終端節點代表一個單獨的輸入變數 x 和這個變數的分支節點；葉節點代表的是輸出變數 y。這個模型按照以下的規則來作出預測：

決策樹的一些部分

4. 樸素貝葉斯法

在給定一個早已發生的事件的機率時，我們用貝葉斯定理去計算某個事件將會發生的機率。在給定一些變數的值時，我們也用貝葉斯定理去計算某個結果的機率，也就是說，基於我們的先驗知識（d）去計算某個假設（h）為真的機率。計算方法如下：

P(h|d)= (P(d|h) * P(h)) / P(d)

其中，

P(h|d) = 後驗機率。就是假設 h 為真機率，給定的資料相當於先驗知識 d。其中 P(h|d)= P(d1| h)* P(d2| h)*….*P(dn| h)* P(d)。

P(d|h) = 似然度。假設 h 正確時，資料 d 的機率。

P(h) = 類先驗機率。假設 h 正確的額機率。(無關資料)

P(d) = 預測器先驗機率。資料的機率（無關假設)

這個演算法被稱為「樸素」的原因是：它假設所有的變數是相互獨立的，這也是現實世界中做出的一個樸素的假設。

使用樸素貝葉斯法來預測變數「天氣」變化狀態

以上圖為例，如果天氣=晴天，那麼輸出是什麼呢？

在給定變數天氣=晴天時，為了判斷結果是或者否，就要計算 P(yes|sunny) 和 P(no|sunny)，然後選擇機率較大的結果。

計算過程如下：

->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

所以，天氣=晴天時，結果為是。

5.KNN

KNN 使用了整個資料集作為訓練集，而不是將它分為訓練集和測試集。

當給定的一個數據實例時，KNN 演算法會在整個資料集中尋找 k 個與其新樣本距離最近的，或者 k 個與新樣本最相似的，然後，對於迴歸問題，輸出結果的平均值，或者對於分類問題，輸出頻率最高的類。k 的值是使用者自定義的。

樣本之間的相似性是用歐氏距離或者漢明（Hamming）距離來計算的。

非監督學習演算法

6.Apriori 演算法

Apriori 演算法被用來在交易資料庫中進行挖掘頻繁的子集，然後生成關聯規則。常用於市場籃子分析，分析資料庫中最常同時出現的交易。通常，如果一個顧客購買了商品 X 之後又購買了商品 Y，那麼這個關聯規則就可以寫為：X -> Y。

例如：如果一位顧客購買了牛奶和甜糖，那他很有可能還會購買咖啡粉。這個可以寫成這樣的關聯規則： {牛奶，甜糖} -> 咖啡粉。關聯規則是交叉了支援度（support）和置信度（confidence）的閾值之後產生的。

支援度的程度幫助修改在頻繁的專案集中用來作為候選專案集的數量。這種支援度的衡量是由 Apriori 原則來指導的。Apriori 原則說明：如果一個專案集是頻繁的，那麼它的所有子集都是頻繁的。

7.K-均值聚類演算法

K-均值是一個對相似的資料進行聚類的迭代演算法。它計算出 k 個聚類的中心點，並給某個類的聚類分配一個與其中心點距離最近的資料點。

K-均值演算法的步驟

步驟 1：K-均值初始化

a) 選擇一個 k 值。這裡我們令 k=3。

b) 將資料點隨機地分配給三個聚類。

c) 計算出每個聚類的中心點。圖中的紅色、藍色和綠色的星分別代表三個聚類的中心點。

步驟 2：將每一個觀測值與一個聚類關聯起來

將每一個數據點重新分配給離它最近的一個聚類中心點。如圖所示，上邊的五個資料點被分配給了藍星代表的聚類。按照相同的步驟將資料點分配給紅色和綠色星代表的聚類中心點。

步驟 3：重新計算中心點

計算新聚類的中心點。如圖所示，舊中心點是灰色的，新中心點是紅色、藍色和綠色的。

步驟 4：迭代，然後在資料點所屬的聚類不變的時候退出整個過程

重複步驟 2-3，直至每一個聚類中的點不會被重新分配到另一個聚類中。如果在兩個連續的步驟中不再發生變化，那麼就退出 K-均值演算法。

8. 主成分分析（PCA）

主成分分析（PCA）透過減少變數的數目來使資料變得更加易於探索和視覺化。這透過將資料中擁有最大方差的資料抽取到一個被稱為「主成分」的新座標系中。每一個成分都是原始變數的一個新的線性組合，且是兩兩統計獨立的。統計獨立意味著這些成分的相關係數是 0。

第一主成分捕獲的是資料中最大方差的資料。第二主成分捕獲的是剩下的資料中方差最大但是與第一主成分相互獨立的資料。相似地，後續的主成分（例如 PC3、PC4）都是剩下的資料中方差最大的但是與之前的主成分保持獨立的資料。

整合意味著透過投票或者取平均值的方式，將多個學習器（分類器）結合起來以改善結果。在分類的時候進行投票，在迴歸的時候求平均值。核心思想就是整合多個學習器以使效能優於單個學習器。有三種整合學習的方法：裝袋（Bagging）、提升（Boosting）和堆疊（Stacking）。本文不涉及堆疊。

9. 隨機森林 Bagging

隨機森林（多個學習器）是在裝袋決策樹（單個學習器）上做的改進。

Bagging：Bagging 的第一步就是在使用 Bootstrap 取樣方法得到的資料庫中建立多個模型，每個生成的訓練集都是原始資料集的子集。每個訓練集都有相同的大小，但是有些樣本重複出現了很多次，有些樣本一次未出現。然後，整個原始資料集被用為測試集。那麼，如果原始資料集的大小為 N，則每個生成的訓練集的大小也是 N，唯一（沒有重複）樣本的大小大約是 2*N/3；測試集的大小也是 N。

Bagging 的第二步就是使用同一個演算法在不同的資料集上生成多個模型。然後，我們討論一下隨機森林。在決策樹中，每個節點都在最好的、能夠最小化誤差的最佳特徵上進行分支，而隨機森林與之不同，我們選擇隨機分支的特徵來構建最佳的分支。進行隨機處理的原因在於：即便使用了 Bagging，當決策樹選擇最佳特徵來分支的時候，它們最終會有相似的模型和相關聯的預測結果。但是用隨機子集上的特徵進行分支意味著子樹做的預測是沒有多少相關性的。

10. AdaBoost 提升演算法

a）Bagging 是並行整合，因為每個模型都是獨立建立的。然而，提升是一個順序性整合，每個模型都要糾正前面模型的錯誤分類。

b）Bagging 主要涉及到「簡單投票」，每個分類器都投票得到一個最終結果，這個分類結果是由並行模型中的大多數模型做出的；提升則使用「權重投票」。每個分類器都會投票得到一個由大多數模型做出的結果—但是建立這些順序性模型的時候，給之前誤分類樣本的模型賦予了較大的權重。

Adaboost 指的是適應性提升。

一個決策樹的 Adaboost

在上圖 中，步驟 1、2、3 指的是被稱為決策樁（decision stump）的弱學習器（是一個僅依靠一個輸入作出決策的 1 級決策樹；是一種根節點直接連線到葉節點的決策樹）。構造決策樹的過程會一直持續，直到使用者定義了一個弱學習器的數目，或者訓練的時候再也沒有任何提升的時候。步驟 4 結合了之前模型中的 3 個決策樁（所以在這個決策樹中就有 3 種分支規則）。

步驟 1：開始用 1 個決策樁來根據 1 個輸入變數做決策

資料點的大小說明我們應用了等權重來將它們分為圓形或者三角形。決策樁在圖的上半部分用一條水平線來對這些點進行分類。我們可以看到，有兩個圓被誤分為三角形。所以，我們會賦予這兩個圓更大的權重，然後使用另一個決策樁（decision stump）。

步驟 2：轉向下一個決策樁，對另一個輸入變數進行決策

我們可以看到，之前的步驟中誤分類的兩個圓要比其餘資料點大。現在，第二個決策樁要嘗試正確地預測這兩個圓。

賦予更大權重的結果就是，這兩個圓被左邊的豎線正確地分類了。但是這又導致了對上面 3 個小圓的誤分類。因此，我們要在另一個決策樁對這三個圓賦予更大的權重。

步驟 3：訓練另一個決策樁對下一個輸入變數進行決策。

上一步誤分類的 3 個圓要比其他的資料點大。現在，在右邊生成了一條豎線，對三角形和圓進行分類。

步驟 4：結合決策樁

我們結合了之前 3 步的決策樁，然後發現一個複雜的規則將資料點正確地分類了，效能要優於任何一個弱學習器。

結語

回顧一下，本文主要學到的內容：

5 種監督學習技術：線性迴歸、Logistic 迴歸、CART（分類和決策樹）、樸素貝葉斯法和 KNN。

3 種非監督學習技術：Apriori 演算法、K-均值聚類、主成分分析（PCA）。

兩種整合學習方法：Bagging 隨機森林、AdaBoost 提升。

綜上所述，機器學習的基本屬性可以總結為以下：

機器學習是（使用樣本獲取近似函式的）統計學的一個分支。我們有一個確實存在的理論函式或分佈用以生成資料，但我們目前不知道它是什麼。我們可以對這個函式進行抽樣，這些樣本選自我們的訓練集。

以圖片描述任務為例：函式：f⋆（圖片）→圖片描述，樣本：data∈（image，description）。注意：由於一個物體有許多有效的描述，所以描述是文字空間中的一個分佈：圖片描述〜文字。

機器的目標是找到模型：有足夠的表現力來逼近真正的函式，找到一個高效的演算法，它使用訓練資料找到函式最優解。而且此最優解必須對未知輸入有良好的泛化能力。

洛谷

進去可以先註冊一個賬號，從新手村開始

支援多種程式語言，如C/C++ python

可以線上編寫，線上提交

介面比較清新，可以建立或者加入團隊，參加一些演算法比賽，個人覺得這個網站十分有助於你學習演算法