機器學習經典算法總結
開啟掘金成長之旅!這是我參與「掘金日新計劃 · 2 月更文挑戰」的第 10 天,點擊查看活動詳情。
一,機器學習系統分類
一,KNN 算法
K
近鄰算法(KNN)是一種基本分類和迴歸方法。KNN
算法的核心思想是如果一個樣本在特徵空間中的 k
個最相鄰的樣本中的大多數屬於一個類別,那該樣本也屬於這個類別,並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分類樣本所屬的類別。 如下圖:
在 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.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
),算法過程如下:
- 隨機選取 $k$ 個聚類中心(
cluster centroids
)為 $\mu_1, \mu_1,...,\mu_k \in R^n$。 - 重複下面過程,直到質心不變或者變化很小:
- 對於每一個樣例 $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$ 代表我們對屬於同一個類的樣本中心點的猜測。
參考資料
- ssh遠程連接方式總結
- 深度學習基礎-損失函數詳解
- 模型壓縮-剪枝算法詳解
- 機器學習經典算法總結
- 深度學習基礎-優化算法詳解
- 深度學習基礎-機器學習基本原理
- 機器學習基本概念總結
- 手把手教你註冊和使用ChatGPT
- 深入淺出動態規劃算法(中)
- 深度學習煉丹-數據預處理和增強
- 深入淺出回溯算法
- 深入淺出動態規劃算法(上)
- GitHub 車牌檢測識別項目調研
- 卷積神經網絡壓縮方法總結
- 神經網絡模型複雜度分析
- MobileNetv1 論文詳解
- ShuffleNetv2論文詳解
- Pytorch基礎-tensor數據結構
- Fast YOLO:用於實時嵌入式目標檢測(附論文下載)
- 嵌入式新聞早班車-第24期