機器學習經典算法總結

語言: CN / TW / HK
時間 2023-03-15 00:15:11

開啟掘金成長之旅！這是我參與「掘金日新計劃 · 2 月更文挑戰」的第 10 天，點擊查看活動詳情。

一，機器學習系統分類

一，KNN 算法

K 近鄰算法（KNN）是一種基本分類和迴歸方法。KNN 算法的核心思想是如果一個樣本在特徵空間中的 k 個最相鄰的樣本中的大多數屬於一個類別，那該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分類樣本所屬的類別。 如下圖：

KNN算法可視化

在 KNN 中，通過計算對象間距離來作為各個對象之間的非相似性指標，避免了對象之間的匹配問題，在這裏距離一般使用歐氏距離或曼哈頓距離，公式如下：

歐幾里得和曼哈頓距離計算公式

同時，KNN通過依據 k 個對象中佔優的類別進行決策，而不是單一的對象類別決策，這兩點就是KNN算法的優勢。

1.1，k 值的選取

  • k 值較小，模型會變得複雜，容易發生過擬合
  • k 值較大，模型比較簡單，容易欠擬合

所以 k 值得選取也是一種調參？

1.2，KNN 算法思路

KNN 思想就是在訓練集中數據和標籤已知的情況下，輸入測試數據，將測試數據的特徵與訓練集中對應的特徵進行相互比較，找到訓練集中與之最為相似的前 K 個數據，則該測試數據對應的類別就是K個數據中出現次數最多的那個分類，其算法的描述為： 1. 計算測試數據與各個訓練數據之間的距離； 2. 按照距離的遞增關係進行排序； 3. 選取距離最小的 K 個點； 4. 確定前 K 個點所在類別的出現頻率； 5. 返回前 K 個點中出現頻率最高的類別作為測試數據的預測分類。

二，支持向量機算法

機器學習中的算法(2)-支持向量機(SVM)基礎

2.1，支持向量機簡述

  • 支持向量機（Support Vector Machines, SVM）是一種二分類模型。它的基本模型是定義在特徵空間上的間隔最大的線性分類器，間隔最大使它有別於感知機；支持向量機還包括核技巧，這使其成為實質上的非線性分類器。
  • SVM 的學習策略是找到最大間隔（兩個異類支持向量到超平面的距離之和 $\gamma = \frac{2}{||w}$ 稱為“間隔”），可形式化為一個求解凸二次規劃的問題，也等價於正則化的合頁損失函數的最小化問題。
  • SVM 的最優化算法是求解凸二次規劃的最優化算法。

2.2，SVM 基本型

$$ min \frac{1}{2}||w||^2 \ s.t. y_{i}(w^Tx_i + b) \geq 1, i = 1,2,...,m $$

SVM 的最優化算法是一個凸二次規劃（convex quadratic programming）問題，對上式使用拉格朗日乘子法可轉化為對偶問題，並優化求解。

2.3，對偶問題求解

對 SVM 基本型公式的每條約束添加拉格朗日乘子 $\alpha_i \geq 0$，則式子的拉格朗日函數如下：

$$ L(w,b,a) = \frac 1 2||w||^2 - \sum{i=1}{n} \alpha_i (y_i(w^Tx_i+b) - 1) $$

經過推導（參考機器學習西瓜書），可得 SVM 基本型的對偶問題：

$$\max\limits_{\alpha} \sum_{i=1}^{m}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x^{T}_{i} x_j$$ $$s.t. \sum_{i=1}^{m} = \alpha_{i}y_{i} = 0$$ $$\alpha_{i}\geq 0, i=1,2,...,m$$

繼續優化該問題，有 SMO 方法，SMO 的基本思路是先固定 $\alpha_i$ 之外的的所有參數，然後求 $\alpha_i$ 上的極值。

三，K-means 聚類算法

3.1，分類與聚類算法

  • 分類簡單來説，就是根據文本的特徵或屬性，劃分到已有的類別中。也就是説，這些類別是已知的，通過對已知分類的數據進行訓練和學習，找到這些不同類的特徵，再對未分類的數據進行分類。
  • 聚類，就是你壓根不知道數據會分為幾類，通過聚類分析將數據或者説用户聚合成幾個羣體，那就是聚類了。聚類不需要對數據進行訓練和學習。
  • 分類屬於監督學習，聚類屬於無監督學習。常見的分類比如決策樹分類算法、貝葉斯分類算法等聚類的算法最基本的有系統聚類，K-means 均值聚類。

3.2，K-means 聚類算法

聚類的目的是找到每個樣本 $x$ 潛在的類別 $y$，並將同類別 $y$ 的樣本 $x$ 放在一起。在聚類問題中，假定訓練樣本是 ${x^1,...,x^m}$，每個 $x^i \in R^n$，沒有 $y$。K-means 算法是將樣本聚類成 $k$ 個簇（cluster），算法過程如下：

  1. 隨機選取 $k$ 個聚類中心（cluster centroids）為 $\mu_1, \mu_1,...,\mu_k \in R^n$。
  2. 重複下面過程，直到質心不變或者變化很小：
    • 對於每一個樣例 $i$ ，計算其所屬類別：$$c^i = \underset{j}{argmin}||x^i - \mu_j||^2$$
    • 對於每一個類 $j$，重新計算該類的質心：$$\mu_j = \frac {\sum_{i=1}^{m} 1{c^i} = jx^{i}} { \sum_{i=1}^{m}1 c^{i} = j}$$

$K$ 是我們事先給定的聚類數，$c^i$ 代表樣例 $i$ 與 $k$ 個類中距離最近的那個類，$c^i$ 的值是 $1$ 到 $k$ 中的一個。質心 $\mu_j$ 代表我們對屬於同一個類的樣本中心點的猜測。

參考資料

K-means聚類算法

「」
「」