1102 機器學習

這篇文章是學習時整理的一些筆記，讓自己複習時方便，文章內容為上課之內容及閱讀清單之整理

監督式學習最常處理的兩個問題：分類、迴歸
當預測的數值為連續的我們稱為迴歸，若是離散的，我們稱為分類
簡單來說，
迴歸就是找一條線，而該線盡可能的通過所有的資料點
分類就是把資料分到指定的幾個分類中

本篇主要是在講迴歸，若要看分類的在另外一則文章喔！

linear 文章筆記整理

分類問題

  • 判斷資料是否屬於某一個類別
  • 可分為二元分類(binary)或多元分類(multi-class)
  • 屬於監督式學習的一種

Logistic regression 雖然有迴歸的名稱，但實際上是一個二元分類（Binary classification）演算法

接下來介紹幾個不同的分類模型～
常見的演算法有決策樹、邏輯迴歸、SVM、樸素貝斯葉

Decision Tree 決策樹

決策樹就像一棵樹一樣，而每個節點都代表一個特徵，依據特徵一步一步的分類

classification

決策樹會依據訓練資料產生一棵樹，決策樹演算法可以使用不同方法來評估分枝的亂度，如information gain, gain ratio, gini index，依據訓練資料來找出最適合的規則。

決策樹如何生成的？

決策樹是以貪婪演算法來決定每一層要用哪一個特徵分類，最好的情況是使用某一個特徵後，所有的資料都可以很精準的被分類，如下圖所示：(使用右邊的特徵分類會更好)

貪婪演算法是一種在每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇，從而希望導致結果是最好或最佳的演算法 - wiki

classification

  • Tree is constructed in a top-down recursive divide-and-conquer manner
  • attributes are categorical(if an attribute is a continuous number, it needs to be discretized in advance)

Divide-and-Conquer分治算法，先將原問題分解成「「問題相同但規模小」的子問題，再反覆重複這個過程直到問題規模小到可以求解為止

  • At start, all the training examples are at the root
  • Examples are partitioned recursively based on selected attributes
  • Test attributes are selected on the basis of a heuristic or statistical measure (eg. information gain): maximizing an information gain measure)

favoring the partitioning which makes the majority of examples belong to a single class

Conditions for stopping partitioning:

  1. all samples for a given node belong to the same class
  2. There are no remaining attributes for further partitioning - majority voting is employed for classifying the leaf
  3. There are no samples left

決策樹建構議題

  1. 分裂的準則 Split criterion (goodness function)
    • used to select the attribures to be split at a tree node during the tree generation phase
    • different algorithms may use different goodness functions:
      • information gain used in ID3/C4.5
      • Gini index used in CART
  2. 分枝的方案 Branch scheme
    • determining the tree branch to which a sample belongs
    • binary or k-ary splitting
  3. 何時停止分枝
    • impurity measure
  4. 訂定標籤的規則
    • a node is labeled as the class to which most samples at the node belongs

決策樹亂度評估準則

我們需要訂定一個指標、標準來評估決策樹的每個節點，常用的指標有：

  1. Information gain 資訊獲利
  2. Gain ratio 吉尼獲利
  3. Gini index 吉尼係數 (Gini impurity 吉尼不純度)

以上的指標都是在衡量一個序列中的亂度，數值越高代表越混亂
我們的目標是找出一個規則，透過從訓練資料中找出規則讓每一個決策都可以使訊息增益最大化

How to use a Tree?

  1. Directly
    • test the attributes value of unknown sample against the tree
    • a path is traced from root to a leaf which holds the label
  2. Indirectly
    • decision tree is converted to classification rules
    • one rules is created for each path from the root to a leaf
    • IF-THEN is easier for humans to understand

評估分割資訊量

常見的評估資訊分割量方法有兩種：

  1. Information gain
  2. Gini impurity

Information gain主要的算法是在計算「熵」(entropy)，因此決策樹分割後後的資訊量要越小越好
而Gini的數值越大代表序列越混亂，值介在0~1之間，其中0代表資料被完美分類

classification

Information gain 資訊獲利

「熵」(entropy)計算是information gain的一種方式，在了解information gain之前先介紹一下entropy的計算
有關熵的詳細介紹前往這則文章

Entropy 文章筆記整理

下圖中p代表是的機率、q代表否的機率
classification
當資料被分類一致的時候entropy為0，當資料各為一半的時後為1
再舉一個例子
classification

則information gain 就可以這樣得來囉～
classification

Gini impurity 不純度

不純度是另外一種衡量資訊亂度的方式，他的數值越大代表資料越混亂
classification

Ramdom Forest 隨機森林

隨機森林的基本原理是結合多個CART決策樹，並加入隨機分配的訓練資料，結合多個「弱學習」來建構一個「強學習器」的概念，這種方法又稱為Ensemble Method

classification

  • each classifier in the ensemble is a decision tree classifier and is generated using a random selection of attributes at each node to determine the split
  • during classification, each tree votes and the most popular class is returned

樹的產生

不過若是我們想要產生多個不同的CART樹，我們就要產生不同的數據集，產生數據集的做法有兩種：

  1. Bagging(Boostrap Aggregation)
  2. Boosting

Bagging(Boostrap Aggregation)

此種作法是從原有的數據集內重新取樣產生新的數據集，且取的過程是「均勻且可重複取樣的」
這種做法會從原有的數據集內產生新的k個數據集，再訓練出k個分類器(CART樹)，每次取出的數據都會放回原數據集，因此彼此之間可能會有資料重複，不過每個樹還是會有不同的樣本，因此每棵樹還是不同的，最後每個樹的權重統一由投票方式決定(Majority vote)

Boosting

和Bagging方式類似，不過更強調「對錯誤的部分加強學習」，將舊分類器錯誤資料的權重提高，加重對錯誤資料的訓練，訓練出新的分類器，這樣新的分類器就會學習到錯誤資料的特性。

classification
（boosting會將上一個產生的樹分類錯的資料加入訓練）

森林的產生

故綜合上述所說的，產生隨機森林的步驟就是：(以bagging說明)

  1. 從原數據集中取出n筆數據產生一個新的數據集，取完後放回
  2. 用先前產生的新數據集訓練一個決策樹，對每個節點選取特徵後分割該節點
  3. 重複k次步驟1、2會得到k個決策樹
  4. 綜合所有決策樹以多數決的方式決定最後分類

Support Vector Machine 支援向量機

下圖每條線都可以將資料點分類，不過哪一條更好呢？
classification

那SVM是怎麼得到那條很好的線呢？以直線來說，首先紅色的線會創造兩條黑色平行於紅色線的虛線，並讓黑線平移碰到最近的一個點，紅線到黑線的距離稱為Margin，而SVM就是透過去找Margin最大的那個紅線，來找最好的線reference
classification

定義線性分類器的margin，在沒有碰到資料點內增加寬度，目標是最大化這個寬度(Linear SVM)
而碰到margin的點即為support vector(支援向量)
classification

虛線上的點X1,X2 其實就是所謂的支援向量(Support vector)，我們主要是利用支援向量來算出Margin，並最大化Margin。那要怎麼計算margin呢？ 利用高中數學的知識將X1向量-X2向量得到的向量投影到W就可以了！接下來就是在Y*(W*X) ≥k 的條件下(虛線中間沒有點)，來最大化margin reference
classification

SVM的優點是他可以處理多維度的資料，且學習速度快，分類效果也很好，在手寫文字辨別上是目前最好的分類器，不過SVM只能做二元分類

更多閱讀，分類模型的評估

confusion matrix

閱讀清單

  1. [Day 12] 決策樹 (Decision tree)
  2. Entropy (熵)是甚麼？在資訊領域的用途是？
  3. ML入門（十七）隨機森林(Random Forest)
  4. [資料分析&機器學習] 第3.4講：支援向量機(Support Vector Machine)介紹