[[376486]]

 上一篇文章講述了機器學習的基本知識點，這一篇就開啟一些算法的摸索之路。既然我們是前端研發(fā)工程師，那就選擇ml.js這個庫進行編碼。本次涉及到的算法包含：KNN、決策樹、隨機森林、樸素貝葉斯、支持向量機、線性回歸、K-均值聚類算法，這七個算法橫跨監(jiān)督學習算法(分類算法、回歸算法)、非監(jiān)督學習算法，可以作為前端入門機器學習的必修課程，也可作為既將到來的端智能時代的必讀刊物。

一、監(jiān)督學習算法

1.1 分類算法

1.1.1 K-近鄰分類算法(KNN)

一、定義

如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。(通常k是不大于20的整數(shù))

二、優(yōu)缺點

1.優(yōu)點

• 簡單有效
• 精度高
• 對異常值不敏感
• 無須訓練

2.缺點

• 計算復雜度高、空間復雜度高(計算量大，內(nèi)存開銷大)
• 必須指定K值，K值選擇不當則分類精度不能保證。(K值取很小，容易受到異常點的影響，容易出現(xiàn)過擬合;K值取很大，受到樣本均衡問題)

三、計算距離

對于KNN算法，最核心的內(nèi)容是計算距離，兩個樣本之間的距離可以通過歐氏距離計算。其計算公式為：

四、應用場景

小數(shù)據(jù)場景(幾千~幾萬樣本)，可用于字符識別、文本分類、圖像識別等領域

五、代碼

const KNN = require('ml-knn'); 
 
// 訓練集特征 
const dataset = [ 
    [1.0, 1.1], 
    [1.0, 1.0], 
    [0, 0], 
    [0, 0.1] 
]; 
 
// 訓練集目標 
const labels = ['A', 'A', 'B', 'B']; 
 
// 實例化KNN算法(進行訓練) 
const knn = new KNN(dataset, labels, { k: 3}); 
 
// 需要進行預測的點 
const predictDataSet = [[0, 0], [3, 1]]; 
 
// 進行預測 
predictLabels = knn.predict(predictDataSet); 
console.log(predictLabels);// [ 'B', 'A' ] 

1.1.2 決策樹

一、定義

決策樹(Decision Tree)是在已知各種情況發(fā)生概率的基礎上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。決策樹是一種樹形結(jié)構(gòu)，其中每個內(nèi)部節(jié)點表示一個屬性上的測試，每個分支代表一個測試輸出，每個葉節(jié)點代表一種類別。

二、優(yōu)缺點

1.優(yōu)點

• 計算復雜度不高
• 輸出結(jié)果易于理解
• 對中間值的缺失不敏感
• 可以處理連續(xù)和種類字段
• 可以處理不相關特征數(shù)據(jù)

2.缺點

• 可能出現(xiàn)過擬合現(xiàn)象，需要進行剪枝操作
• 對于各類別樣本數(shù)量不一致的數(shù)據(jù)，信息增益偏向于那些更多數(shù)值的特征

三、應用場景

常用于解決分類和回歸問題，用該算法的前提條件是：

1. 具有決策者期望達到的明確目標

2. 存在決策者可以選擇的兩個以上的可行的備選方案

3. 存在決策者無法控制的兩個以上不確定因素

4. 不同方案在不同因素下的收益或損失可以計算出來

5. 決策者可以估計不確定因素發(fā)生的概率

四、重點知識點

1.信息熵

信息是很抽象的概念，很難進行量化對量，為了解決對信息的量化度量問題，香農(nóng)提出了“信息熵”的概念。信息熵是在信息的基礎上，將有可能產(chǎn)生的信息定義為一個隨機變量，變量的期望就是信息熵。信息熵的計算公式為(單位為比特)：

注：熵是用來度量不確定性，熵越大則其不確定性越大，反之越小 2. 信息增益

信息增益在決策樹算法中是用來選擇特征的指標，信息增益越大，則這個特征的選擇性越好，在概率論中定義為：待分類的集合的熵和選定某個特征的條件熵之差。其計算公式為：

注：

• g(D, A)表示特征A對訓練數(shù)據(jù)集D的信息增益
• H(D)表示集合D的信息熵
• H(D|A)表示條件熵

3.常用算法

(1)ID3算法

ID3算法是采用信息增益作為特征選擇的標準，信息增益越大，說明按此特征分類后越能消除信息的不確定性。

(2)C4.5算法

ID3算法具有兩大缺點：一個是類別越多的特征計算出的信息增益越大，易導致生成的決策樹廣而淺;另一個是只能處理離散變量，不能處理連續(xù)變量。C4.5是在ID3的算法基礎上采用信息增益率作為特征選擇，通過增加類別的懲罰因子，規(guī)避了類別越多信息增益越大的問題，同時也可以對連續(xù)變量通過均值離散化的方式解決無法處理連續(xù)變量的問題。

(3)CART算法

C4.5存在不能處理回歸問題的缺點，該缺點由CART解決。CART不在通過信息熵的方式選取最優(yōu)劃分特征，而是采用基尼系數(shù)(基尼不純度)，兩者衡量信息量的作用相當，但基尼系數(shù)由于沒有對數(shù)運算，可大大減少計算開銷。

五、代碼

const irisDataset = require('ml-dataset-iris'); 
const { DecisionTreeClassifier } = require('ml-cart'); 
 
// 獲取訓練集中的特征值 
const dataSet = irisDataset.getNumbers(); 
// 獲取訓練集中的目標值，并轉(zhuǎn)換為標量 
const labels = irisDataset 
    .getClasses() 
    .map(elem => irisDataset.getDistinctClasses().indexOf(elem)); 
 
// 實例化決策樹的分類器 
const dTClassifier = new DecisionTreeClassifier({ 
    gainFunction: 'gini', 
    maxDepth: 10, 
    minNumSamples: 3 
}); 
 
// 進行訓練 
dTClassifier.train(dataSet, labels); 
 
const predictDataset = [[5.1,3.5,1.4,0.2]]; 
 
// 進行預測 
const result = dTClassifier.predict(predictDataset); 
 
// 結(jié)果轉(zhuǎn)換為對應的文本形式 
console.log(result.map(value => irisDataset.getDistinctClasses()[value])); 

1.1.3 隨機森林

一、定義

在機器學習中，隨機森林是一個包含多個決策樹的分類器，其輸出的類別是由個別樹輸出的類別的眾數(shù)而定(隨機森林就是通過集成學習的思想將多棵樹集成的一種算法，其基本單元是決策樹)。

二、優(yōu)缺點

1.優(yōu)點

• 具有極好的準確率(由集成算法的特點引入)
• 抗過擬合能力：通過平均決策樹，降低過擬合的風險性(由隨機這個特點引入)
• 能夠有效地運行在大數(shù)據(jù)集上，處理具有高維特征的輸入樣本，而且不需要降維
• 能夠評估各個特征在分類問題上的重要性

2.缺點

• 在某些噪音較大的分類或回歸問題上會過擬合
• 比決策樹算法更復雜，計算成本更高

三、重要知識點

1.隨機森林的每棵樹的生成規(guī)則(A表示訓練集總樣本個數(shù)、N表示訓練樣本個數(shù)、M表示特征個數(shù))

(1)對于每棵樹隨機有放回的從訓練集中抽取N個訓練樣本，作為該樹的訓練集 (2)指定一個常數(shù)m<

2..為什么要隨機抽樣訓練集?

隨機抽樣是為了保證每棵樹的訓練集都不一樣，若不隨機抽樣會導致最終訓練出的分類結(jié)果完全一樣。

3.為什么要有放回的抽樣?

有放回的抽樣才能保證每次抽取時的概率是一樣的，達到獨立同分布，可保證每一棵決策樹都是相互獨立的。

4.隨機森林分類效果(錯誤率)相關因素?

(1)森林中任意兩棵樹的相關性：相關性越大，錯誤率越大

(2)森林中每棵樹的分類能力：每棵樹的分類能力越強，整個森林的錯誤率越低

(注：減小特征選擇個數(shù)m，樹的相關性和分類能力會相應降低，反之會隨之增大)

四、代碼

const irisDataset = require('ml-dataset-iris'); 
const { RandomForestClassifier } = require('ml-random-forest'); 
 
// 獲取訓練集中的特征值 
const dataSet = irisDataset.getNumbers(); 
// 獲取訓練集中的目標值，并轉(zhuǎn)換為標量 
const labels = irisDataset 
    .getClasses() 
    .map(elem => irisDataset.getDistinctClasses().indexOf(elem)); 
 
// 實例化分類器 
const rFClassifier = new RandomForestClassifier({ 
    seed: 3, 
    maxFeatures: 0.8, 
    replacement: true, 
    nEstimators: 25 
}); 
 
// 進行訓練 
rFClassifier.train(dataSet, labels); 
 
const predictDataset = [[5.1,3.5,1.4,0.2]]; 
 
// 進行預測 
const result = rFClassifier.predict(predictDataset); 
 
// 結(jié)果轉(zhuǎn)換為對應的文本形式 
console.log(result.map(value => irisDataset.getDistinctClasses()[value])); 

1.1.4 樸素貝葉斯

一、定義

樸素貝葉斯法(NBC)是基于貝葉斯定理與特征條件獨立假設的分類方法。先通過已給定的訓練集，以特征詞之間獨立作為前提假設，學習從輸入到輸出的聯(lián)合概率分布，再基于學習到的模型，輸入X求出使得后驗概率最大的輸出Y。

二、優(yōu)缺點

1.優(yōu)點

• 樸素貝葉斯模型發(fā)源于古典數(shù)學理論，有穩(wěn)定的分類效率
• 對缺失數(shù)據(jù)不敏感，算法簡單，常用于文本分類
• 分類準確度高，速度快

2.缺點

• 使用了樣本獨立性的假設，如果特征屬性有關聯(lián)性，其效果較差

三、應用場景

• 文本分類
• 文字識別
• 圖像識別

四、重要知識點

1.貝葉斯公式

注：貝葉斯公式是打通P(W|C)和P(C|W)的橋梁

2.為什么引入拉普拉斯平滑系數(shù)

為了防止計算出的分類概率為0，所以引入拉普拉斯平滑系數(shù)，即讓P(W1|C)不為0，其計算公式為： 

注：其中α為指定系數(shù)，一般為1;m為訓練文檔中統(tǒng)計出的特征詞個數(shù)

三種貝葉斯模型

(1)高斯分布樸素貝葉斯——用于一般分類問題

(2)多項式分布樸素貝葉斯——適用于文本數(shù)據(jù)(特征表示的是次數(shù))

(3)伯努利分布樸素貝葉斯——適用于伯努利分布、文本數(shù)據(jù)(特征表示的是是否出現(xiàn))

五、代碼

const irisDataset = require('ml-dataset-iris'); 
const { GaussianNB } = require('ml-naivebayes'); 
 
// 獲取訓練集中的特征值 
const dataSet = irisDataset.getNumbers(); 
 
// 獲取訓練集中的目標值 
const labels = irisDataset 
    .getClasses() 
    .map(elem => irisDataset.getDistinctClasses().indexOf(elem)); 
 
 
//實例化分類器 
const gaussianNB = new GaussianNB(); 
// 進行訓練 
gaussianNB.train(dataSet, labels); 
 
const predictDataset = [[5.1,3.5,1.4,0.2]]; 
 
// 進行預測 
const result = gaussianNB.predict(predictDataset); 
 
// 結(jié)果轉(zhuǎn)換為對應的文本形式 
console.log(result.map(value => irisDataset.getDistinctClasses()[value])); 

1.1.5 支持向量機

一、定義

支持向量機(SVM)是一類按監(jiān)督學習方式對數(shù)據(jù)進行二元分類的廣義線性分類器，其決策邊界是對學習樣本求解的最大邊距超平面。

二、優(yōu)缺點

1.優(yōu)點

• 有嚴格的數(shù)學理論支持，可解釋性強，不依靠統(tǒng)計方法，簡化了通常的分類和回歸問題。
• 上述支持向量決定了最終結(jié)果，對異常值不敏感，可以幫助抓住關鍵樣本，剔除大量冗余樣本
• 該算法簡單且具有較好的“魯棒性”
• 計算的復雜度取決于支持向量的數(shù)目，而不是樣本空間的維數(shù)，某種意義上避免了“維數(shù)災難”
• 泛化能力較強

2.缺點

• 對大規(guī)模訓練樣本難以實施：SVM的空間消耗主要是存儲訓練樣本和核矩陣，由于SVM是借助二次規(guī)劃來求解支持向量，而求解二次規(guī)劃將涉及m階矩陣的運算，當m數(shù)目很大時該矩陣的存儲和計算將耗費大量的機器內(nèi)存和運算時間。
• 解決多分類問題困難：經(jīng)典的支持向量機算法只給出了二類分類算法，解決多分類問題需要通過多個二類支持向量機的組合來解決(一對多組合模式、一對一組合模式和SVM決策樹)。
• 對參數(shù)和核函數(shù)選擇敏感：支持向量機性能的優(yōu)劣主要取決于核函數(shù)的選取。

三、應用場景

SVM在各領域的模式識別問題中有應用，包括人像識別、文本分類、手寫字符識別、生物信息學等。

四、重要知識點

1.重要概念

(1) 線性可分：在二維空間上，兩類點被一條直線完全分開叫做線性可分

(2)最大間隔超平面：從二維擴展到多維空間中，將兩個點集完全正確地劃分開就形成一個超平面，為了使這個超平面更具魯棒性，則會找最佳超平面(即為最大間隔超平面，該平面是以最大間隔把兩類樣本分開的超平面)。(兩類樣本分別分割在該超平面的兩側(cè)、兩側(cè)距離超平面最近的樣本點到超平面的距離被最大化了)

(3)支持向量：樣本中距離超平面最近的一些點叫支持向量

(4)軟間隔：對于不能夠完全線性可分的樣本可引入軟間隔，相比于硬間隔的苛刻條件，軟間隔允許個別樣本出現(xiàn)在間隔帶里面。(注：硬間隔和軟間隔均是在說樣本的完全線性可分或者大部分樣本點的線性可分)

2.對于線性不可分處理方式

將線性不可分樣本映射到高維空間中，使樣本在高維空間線性可分，此時由于維度提高會導致計算量增大，所以需要使用核函數(shù)幫助處理，引入核函數(shù)后就不需要計算高維甚至無窮維空間的內(nèi)積了。

3.引入核函數(shù)的好處

(1)減少了計算量

(2)減少了存儲數(shù)據(jù)的內(nèi)存使用量

4.常見核函數(shù)分類

(1)線性核函數(shù) (2)多項式核函數(shù) (3)高斯核函數(shù)

五、代碼

const SVM = require('libsvm-js/asm'); 
 
const svm = new SVM({ 
    kernel: SVM.KERNEL_TYPES.RBF, 
    type: SVM.SVM_TYPES.C_SVC, 
    gamma: 1, 
    cost: 1 
}); 
 
const dataSet = [[0, 0], [1, 1], [1, 0], [0, 1]]; 
const labels = [0, 0, 1, 1]; 
// 進行訓練 
svm.train(dataSet, labels); 
 
// 進行預測 
const predictedLabel = svm.pred 

1.2 回歸算法

1.2.1 線性回歸

一、定義

線性回歸是利用回歸方程(函數(shù))對一個或多個自變量(特征值)和因變量(目標值)之間關系進行建模的一種分析方式。只有一個自變量的情況稱為單變量回歸，大于一個自變量的情況叫做多元回歸。

二、優(yōu)缺點

1.優(yōu)點

• 思想簡單、容易實現(xiàn)、建模迅速，對于小數(shù)據(jù)量、簡單關系情形的很有效
• 是需要強大的非線性模型的基礎
• 理解容易，其結(jié)果具有很好的可解釋型，有利于決策分析。
• 能解決回歸問題

缺點

• 對于非線性數(shù)據(jù)或者數(shù)據(jù)特征間具有相關性多項式回歸難以建模
• 難以很好地表達高度復雜的數(shù)據(jù)

三、應用場景

1. 趨勢線(時間序列數(shù)據(jù)的長期走勢)
2. 流行病學
3. 金融(分析和計算投資的系統(tǒng)風險)
4. 經(jīng)濟學(預測消費支出、固定投資支出等)

四、重要知識點

1. 回歸目的——預測數(shù)值型的目標值
2. 回歸性能評價指標——均方誤差(MSE)
3. 過擬合

(1)定義：一個建設在訓練數(shù)據(jù)上能夠獲得比其它假設更好的擬合，但是在測試數(shù)據(jù)集上卻不能很好地擬合數(shù)據(jù)，此時認為這個假設出現(xiàn)了過擬合現(xiàn)象。(模型過于復雜)

(2)原因：原始特征過多，存在一些嘈雜特征

(3)解決辦法：正則化

4.欠擬合

(1)定義：一個假設在訓練數(shù)據(jù)集上不能獲得很好的擬合，并且在測試數(shù)據(jù)集上也不能很好地擬合數(shù)據(jù)，此時認為這個假設出現(xiàn)了欠擬合的現(xiàn)象。(模型過于簡單)

(2)原因：學習到數(shù)據(jù)的特征過少

(3)解決辦法：增加數(shù)據(jù)的特征數(shù)量

5.正則化

(1)L2正則化

L2正則化可以使得其中一些W都很小(接近于0)，削弱某個特征影響。Ridge回歸就是用的L2正則化。

(2)L1正則化

L1正則化可以使得其中一些W的值直接為0，刪除整個特征的影響。LASSO回歸用的就是L1正則化。

五、代碼

const SimpleLinearRegression = require('ml-regression-simple-linear'); 
 
const x = [0.5, 1, 1.5, 2, 2.5]; 
const y = [0, 1, 2, 3, 4]; 
 
const regression = new SimpleLinearRegression(x, y); 
 
const result = regression.predict(3); 
 
console.log(result); 

二、非監(jiān)督學習算法

2.1 K-均值聚類算法

一、定義

K均值聚類算法是一種迭代求解的聚類分析算法，其步驟為：

隨機設置K個特征空間內(nèi)的點作為初始的聚類中心

對于其它每個點計算到K個中心的距離，位置的點選擇最近的一個聚類中心點作為標記類別

接著重新計算出每個聚類的新中心點(平均值)

如果計算得出的新中心點與原中心點一樣，則結(jié)束，否則重新進行第二步過程

二、優(yōu)缺點

1.優(yōu)點

• 原理簡單，容易實現(xiàn)，算法復雜度低
• 可解釋度較強
• 處理大數(shù)據(jù)集的時候，該算法可以保證較好的伸縮性
• 當簇近似高斯分布的時候效果很好

2.缺點

• K值需要人為設定，不同K值得到的結(jié)果不一樣
• 對初始的簇中心敏感，不同選取方式會得到不同結(jié)果
• 對異常值敏感
• 需樣本存在均值(限定數(shù)據(jù)種類)
• 不適合太離散的分類、樣本類別不均衡的分類、非凸形狀的分類
• 可能收斂到局部最小值

三、代碼

const kmeans = require('ml-kmeans'); 
 
// 需要進行聚類的全部數(shù)據(jù) 
const data = [[1, 1, 1], [-1, -1, -1], [-1, -1, -1.5], [1, 2, 1]]; 
 
// 質(zhì)心 
const centers = [[1, 2, 1], [-1, -1, -1]]; 
 
const ans = kmeans(data, 2, { 
    initialization: centers 
}); 
 
console.log(ans); 

本文轉(zhuǎn)載自微信公眾號「執(zhí)鳶者」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系執(zhí)鳶者眾號。