knn演算法原理與應用場景

⑴ KNN 演算法-理論篇-如何給電影進行分類

KNN 演算法 的全稱是 K-Nearest Neighbor ，中文為 K 近鄰 演算法，它是基於 距離 的一種演算法，簡單有效。

KNN 演算法 即可用於分類問題，也可用於回歸問題。

假如我們統計了一些 電影數據，包括電影名稱，打鬥次數，接吻次數，電影類型 ，如下：

可以看到，電影分成了兩類，分別是動作片和愛情片。

如果現在有一部新的電影A，它的打鬥和接吻次數分別是80 和7，那如何用KNN 演算法對齊進行分類呢？

我們可以將打鬥次數作為 X 軸 ，接吻次數作為 Y 軸 ，將上述電影數據畫在一個坐標系中，如下：

通過上圖可以直觀的看出，動作電影與愛情電影的分布范圍是不同的。

KNN 演算法 基於距離，它的原理是： 選擇與待分類數據最近的K 個點，這K 個點屬於哪個分類最多，那麼待分類數據就屬於哪個分類 。

所以，要判斷電影A 屬於哪一類電影，就要從已知的電影樣本中，選出距離電影A 最近的K 個點：

比如，我們從樣本中選出三個點（即 K 為 3），那麼距離電影A 最近的三個點是《功夫》，《黑客帝國》和《戰狼》，而這三部電影都是動作電影。因此，可以判斷電影A 也是動作電影。

另外，我們還要處理兩個問題：

關於點之間的距離判斷，可以參考文章 《計算機如何理解事物的相關性》 。

至於K 值的選擇，K 值較大或者較小都會對模型的訓練造成負面影響，K 值較小會造成 過擬合 ，K 值較大 欠擬合 。

因此，K 值的選擇，一般採用 交叉驗證 的方式。

交叉驗證的思路是，把樣本集中的大部分樣本作為訓練集，剩餘部分用於預測，來驗證分類模型的准確度。一般會把 K 值選取在較小范圍內，逐一嘗試K 的值，當模型准確度最高時，就是最合適的K 值。

可以總結出， KNN 演算法 用於分類問題時，一般的步驟是：

如果，我們現在有一部電影B，知道該電影屬於動作電影，並且知道該電影的接吻次數是 7 ，現在想預測該電影的打鬥次數是多少？

這個問題就屬於 回歸問題 。

首先看下，根據已知數據，如何判斷出距離電影B 最近的K 個點。

我們依然設置K 為3，已知數據為：

根據已知數據可以畫出下圖：

圖中我畫出了一條水平線，這條線代表所有接吻次數是7 的電影，接下來就是要找到距離 這條線 最近的三部（K 為 3）動作電影。

可以看到，距離這條水平線最近的三部動作電影是《功夫》，《黑客帝國》和《戰狼》，那麼這三部電影的打鬥次數的平均值，就是我們預測的電影B 的打鬥次數。

所以，電影B 的打鬥次數是：

本篇文章主要介紹了 KNN 演算法 的基本原理，它簡單易懂，即可處理分類問題，又可處理回歸問題。

KNN 演算法 是基於 距離 的一種機器學習演算法，需要計算測試點與樣本點之間的距離。因此，當數據量大的時候，計算量就會非常龐大，需要大量的存儲空間和計算時間。

另外，如果樣本數據分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會很低。因此，在實際應用中，要特別注意這一點。

（本節完。）

推薦閱讀：

決策樹演算法-理論篇-如何計算信息純度

決策樹演算法-實戰篇-鳶尾花及波士頓房價預測

樸素貝葉斯分類-理論篇-如何通過概率解決分類問題

樸素貝葉斯分類-實戰篇-如何進行文本分類

計算機如何理解事物的相關性-文檔的相似度判斷

⑵ 01 KNN演算法 - 概述

KNN演算法 全稱是K近鄰演算法 （K-nearst neighbors，KNN）

KNN是一種基本的機器學習演算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它 最接近的k個鄰近位置的樣本 來代替。

KNN是個相對比較簡單的演算法，比起之前提過的回歸演算法和分類演算法更容易。如果一個人從來沒有接觸過機器學習的演算法，拿到數據後最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然後你們發現我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。

KNN演算法即可以應用於 分類演算法 中，也可以應用於 回歸演算法 中。

KNN在做回歸和分類的主要區別，在於最後做預測時候的決策不同。在分類預測時，一般採用 多數表決法 。在做回歸預測時，一般使用 平均值法 。

多數表決法： 分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。

平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。

再舉個例子：
分別根據甜度和脆度兩個特徵來判斷食物的種類。
根據樣本我們普遍發現：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質。
不甜，比較脆的食物是蔬菜。
於是根據目標的樣本甜度和脆度兩個特徵，我們可以對其進行分類了。

k值的選擇:
先選一個較小的值，然後通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至於過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。

距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。

決策規劃:
分類：多數表決法、加權多數表決法。
回歸：平均值法、加權平均值法。

加權多數表決法：

平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6

加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43

1、蠻力實現(brute)：
計算預測樣本到所有訓練集樣本的距離，然後選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特徵數多、樣本數多時，演算法的效率比較低。

2、KD樹 (kd_tree)：
首先對訓練數據進行建模，構建KD樹，然後根據建好的模型來獲取鄰近樣本數據。
後續內容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現要少檢索多少數據。

⑶ 聚類分析之KNN

我們先用一個例子體會下。

假設，我們想對電影的類型進行分類，統計了電影中打鬥次數、接吻次數，當然還有其他的指標也可以被統計到，如下表所示。

我們很容易理解《戰狼》《紅海行動》《碟中諜 6》是動作片，《前任 3》《春嬌救志明》《泰坦尼克號》是愛情片，但是有沒有一種方法讓機器也可以掌握這個分類的規則，當有一部新電影的時候，也可以對它的類型自動分類呢？

我們可以把打鬥次數看成 X 軸，接吻次數看成 Y 軸，然後在二維的坐標軸上，對這幾部電影進行標記，如下圖所示。對於未知的電影 A，坐標為 (x,y)，我們需要看下離電影 A 最近的都有哪些電影，這些電影中的大多數屬於哪個分類，那麼電影 A 就屬於哪個分類。實際操作中，我們還需要確定一個 K 值，也就是我們要觀察離電影 A 最近的電影有多少個。

KNN 的工作原理

「近朱者赤，近墨者黑」可以說是 KNN 的工作原理。整個計算過程分為三步：

計算待分類物體與其他物體之間的距離；

統計距離最近的 K 個鄰居；

對於 K 個最近的鄰居，它們屬於哪個分類最多，待分類物體就屬於哪一類。

K 值如何選擇

你能看出整個 KNN 的分類過程，K 值的選擇還是很重要的。那麼問題來了，K 值選擇多少是適合的呢？

如果 K 值比較小，就相當於未分類物體與它的鄰居非常接近才行。這樣產生的一個問題就是，如果鄰居點是個雜訊點，那麼未分類物體的分類也會產生誤差，這樣 KNN 分類就會產生過擬合。

如果 K 值比較大，相當於距離過遠的點也會對未知物體的分類產生影響，雖然這種情況的好處是魯棒性強，但是不足也很明顯，會產生欠擬合情況，也就是沒有把未分類物體真正分類出來。

所以 K 值應該是個實踐出來的結果，並不是我們事先而定的。在工程上，我們一般採用交叉驗證的方式選取 K 值。

交叉驗證的思路就是，把樣本集中的大部分樣本作為訓練集，剩餘的小部分樣本用於預測，來驗證分類模型的准確性。所以在 KNN 演算法中，我們一般會把 K 值選取在較小的范圍內，同時在驗證集上准確率最高的那一個最終確定作為 K 值。

距離如何計算

在 KNN 演算法中，還有一個重要的計算就是關於距離的度量。兩個樣本點之間的距離代表了這兩個樣本之間的相似度。距離越大，差異性越大；距離越小，相似度越大。

關於距離的計算方式有下面五種方式：

歐氏距離；

曼哈頓距離；

閔可夫斯基距離；

切比雪夫距離；

餘弦距離。

其中前三種距離是 KNN 中最常用的距離，我給你分別講解下。

歐氏距離是我們最常用的距離公式，也叫做歐幾里得距離。在二維空間中，兩點的歐式距離就是：

同理，我們也可以求得兩點在 n 維空間中的距離：

曼哈頓距離在幾何空間中用的比較多。以下圖為例，綠色的直線代表兩點之間的歐式距離，而紅色和黃色的線為兩點的曼哈頓距離。所以曼哈頓距離等於兩個點在坐標繫上絕對軸距總和。用公式表示就是：

閔可夫斯基距離不是一個距離，而是一組距離的定義。對於 n 維空間中的兩個點 x(x1,x2,…,xn) 和 y(y1,y2,…,yn) ， x 和 y 兩點之間的閔可夫斯基距離為：

其中 p 代表空間的維數，當 p=1 時，就是曼哈頓距離；當 p=2 時，就是歐氏距離；當 p→∞時，就是切比雪夫距離。

那麼切比雪夫距離怎麼計算呢？二個點之間的切比雪夫距離就是這兩個點坐標數值差的絕對值的最大值，用數學表示就是：max(|x1-y1|,|x2-y2|)。

餘弦距離實際上計算的是兩個向量的夾角，是在方向上計算兩者之間的差異，對絕對數值不敏感。在興趣相關性比較上，角度關系比距離的絕對值更重要，因此餘弦距離可以用於衡量用戶對內容興趣的區分度。比如我們用搜索引擎搜索某個關鍵詞，它還會給你推薦其他的相關搜索，這些推薦的關鍵詞就是採用餘弦距離計算得出的。

KD 樹

其實從上文你也能看出來，KNN 的計算過程是大量計算樣本點之間的距離。為了減少計算距離次數，提升 KNN 的搜索效率，人們提出了 KD 樹（K-Dimensional 的縮寫）。KD 樹是對數據點在 K 維空間中劃分的一種數據結構。在 KD 樹的構造中，每個節點都是 k 維數值點的二叉樹。既然是二叉樹，就可以採用二叉樹的增刪改查操作，這樣就大大提升了搜索效率。

在這里，我們不需要對 KD 樹的數學原理

了解太多，你只需要知道它是一個二叉樹的數據結構，方便存儲 K 維空間的數據就可以了。而且在 sklearn 中，我們直接可以調用 KD 樹，很方便。

用 KNN 做回歸

KNN 不僅可以做分類，還可以做回歸。首先講下什麼是回歸。在開頭電影這個案例中，如果想要對未知電影進行類型劃分，這是一個分類問題。首先看一下要分類的未知電影，離它最近的 K 部電影大多數屬於哪個分類，這部電影就屬於哪個分類。

如果是一部新電影，已知它是愛情片，想要知道它的打鬥次數、接吻次數可能是多少，這就是一個回歸問題。

那麼 KNN 如何做回歸呢？

對於一個新電影 X，我們要預測它的某個屬性值，比如打鬥次數，具體特徵屬性和數值如下所示。此時，我們會先計算待測點（新電影 X）到已知點的距離，選擇距離最近的 K 個點。假設 K=3，此時最近的 3 個點（電影）分別是《戰狼》，《紅海行動》和《碟中諜 6》，那麼它的打鬥次數就是這 3 個點的該屬性值的平均值，即 (100+95+105)/3=100 次。

總結

今天我給你講了 KNN 的原理，以及 KNN 中的幾個關鍵因素。比如針對 K 值的選擇，我們一般採用交叉驗證的方式得出。針對樣本點之間的距離的定義，常用的有 5 種表達方式，你也可以自己來定義兩個樣本之間的距離公式。不同的定義，適用的場景不同。比如在搜索關鍵詞推薦中，餘弦距離是更為常用的。

另外你也可以用 KNN 進行回歸，通過 K 個鄰居對新的點的屬性進行值的預測。

KNN 的理論簡單直接，針對 KNN 中的搜索也有相應的 KD 樹這個數據結構。KNN 的理論成熟，可以應用到線性和非線性的分類問題中，也可以用於回歸分析。

不過 KNN 需要計算測試點與樣本點之間的距離，當數據量大的時候，計算量是非常龐大的，需要大量的存儲空間和計算時間。另外如果樣本分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會低很多。

當然在實際工作中，我們需要考慮到各種可能存在的情況，比如針對某類樣本少的情況，可以增加該類別的權重。

同樣 KNN 也可以用於推薦演算法，雖然現在很多推薦系統的演算法會使用 TD-IDF、協同過濾、Apriori 演算法，不過針對數據量不大的情況下，採用 KNN 作為推薦演算法也是可行的。

⑷ 什麼叫做knn演算法

在模式識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和回歸的非參數統計方法。

在這兩種情況下，輸入包含特徵空間（Feature Space）中的k個最接近的訓練樣本。

1、在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k=1，則該對象的類別直接由最近的一個節點賦予。

2、在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最近鄰居的值的平均值。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN是一種基於實例的學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習。k-近鄰演算法是所有的機器學習演算法中最簡單的之一。

無論是分類還是回歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為1/ d，其中d是到鄰居的距離。

鄰居都取自一組已經正確分類（在回歸的情況下，指屬性值正確）的對象。雖然沒要求明確的訓練步驟，但這也可以當作是此演算法的一個訓練樣本集。

k-近鄰演算法的缺點是對數據的局部結構非常敏感。

K-均值演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關系。數據標准化可以大大提高該演算法的准確性。

參數選擇

如何選擇一個最佳的K值取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一個較好的K值能通過各種啟發式技術（見超參數優化）來獲取。

雜訊和非相關性特徵的存在，或特徵尺度與它們的重要性不一致會使K近鄰演算法的准確性嚴重降低。對於選取和縮放特徵來改善分類已經作了很多研究。一個普遍的做法是利用進化演算法優化功能擴展，還有一種較普遍的方法是利用訓練樣本的互信息進行選擇特徵。

在二元（兩類）分類問題中，選取k為奇數有助於避免兩個分類平票的情形。在此問題下，選取最佳經驗k值的方法是自助法。

⑸ 什麼是knn演算法

作為一種非參數的分類演算法，K-近鄰(KNN)演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。在應用KNN演算法解決問題的時候，要注意兩個方面的問題--樣本權重和特徵權重。利用SVM來確定特徵的權重，提出了基於SVM的特徵加權演算法(FWKNN,feature
weighted
KNN)。實驗表明，在一定的條件下，FWKNN能夠極大地提高分類准確率。

⑹ K-近鄰演算法簡介

1.K-近鄰(KNearestNeighbor,KNN)演算法簡介 ：對於一個未知的樣本，我們可以根據離它最近的k個樣本的類別來判斷它的類別。

以下圖為例，對於一個未知樣本綠色小圓，我們可以選取離它最近的3的樣本，其中包含了2個紅色三角形，1個藍色正方形，那麼我們可以判斷綠色小圓屬於紅色三角形這一類。
我們也可以選取離它最近的5個樣本，其中包含了3個藍色正方形，2個紅色三角形，那麼我們可以判斷綠色小圓屬於藍色正方形這一類。

3.API文檔

下面我們來對KNN演算法中的參數項做一個解釋說明：

'n_neighbors'：選取的參考對象的個數（鄰居個數），默認值為5，也可以自己指定數值，但不是n_neighbors的值越大分類效果越好，最佳值需要我們做一個驗證。
'weights': 距離的權重參數，默認uniform。
'uniform': 均勻的權重，所有的點在每一個類別中的權重是一樣的。簡單的說，就是每個點的重要性都是一樣的。
'distance'：權重與距離的倒數成正比，距離近的點重要性更高，對於結果的影響也更大。
'algorithm':運算方法，默認auto。
'auto'：根絕模型fit的數據自動選擇最合適的運算方法。
'ball_tree'：樹模型演算法BallTree
'kd_tree'：樹模型演算法KDTree
'brute'：暴力演算法
'leaf_size'：葉子的尺寸，默認30。只有當algorithm = 'ball_tree' or 'kd_tree'，這個參數需要設定。
'p'：閔可斯基距離，當p = 1時，選擇曼哈頓距離；當p = 2時，選擇歐式距離。
n_jobs：使用計算機處理器數目，默認為1。當n=-1時，使用所有的處理器進行運算。

4.應用案例演示
下面以Sklearn庫中自帶的數據集--手寫數字識別數據集為例，來測試下kNN演算法。上一章，我們簡單的介紹了機器學習的一般步驟：載入數據集 - 訓練模型 - 結果預測 - 保存模型。這一章我們還是按照這個步驟來執行。
[手寫數字識別數據集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

5.模型的方法
每一種模型都有一些它獨有的屬性方法（模型的技能，能做些什麼事），下面我們來了解下knn演算法常用的的屬性方法。

6.knn演算法的優缺點
優點：
簡單，效果還不錯，適合多分類問題
缺點：
效率低（因為要計算預測樣本距離每個樣本點的距離，然後排序），效率會隨著樣本量的增加而降低。

⑺ R語言-KNN演算法

1、K最近鄰(k-NearestNeighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。

2、KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

3、KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。

簡言之，就是將未標記的案例歸類為與它們最近相似的、帶有標記的案例所在的類 。

原理及舉例

工作原理：我們知道樣本集中每一個數據與所屬分類的對應關系，輸入沒有標簽的新數據後，將新數據與訓練集的數據對應特徵進行比較，找出「距離」最近的k（通常k<20）數據，選擇這k個數據中出現最多的分類作為新數據的分類。

演算法描述

1、計算已知數據集中的點與當前點的距離

2、按距離遞增次序排序

3、選取與當前數據點距離最近的K個點

4、確定前K個點所在類別出現的頻率

5、返回頻率最高的類別作為當前類別的預測

距離計算方法有"euclidean"（歐氏距離）,」minkowski」（明科夫斯基距離）, "maximum"（切比雪夫距離）, "manhattan"（絕對值距離）,"canberra"（蘭式距離）, 或 "minkowski"（馬氏距離）等

Usage

knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)

Arguments

train

matrix or data frame of training set cases.

test

matrix or data frame of test set cases. A vector will  be interpreted as a row vector for a single case.

cl

factor of true classifications of training set

k

number of neighbours considered.

l

minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even

ifkis  increased by ties.)

prob

If this is true, the proportion of the votes for the

winning class are returned as attributeprob.

use.all

controls handling of ties. If true, all distances equal

to thekth largest are

included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.

kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))

參數：

formula                            A formula object.

train                                 Matrix or data frame of training set cases.

test                                   Matrix or data frame of test set cases.

na.action                         A function which indicates what should happen when the data contain 』NA』s.

k                                       Number of neighbors considered.

distance                          Parameter of Minkowski distance.

kernel                              Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".

ykernel                            Window width of an y-kernel, especially for prediction of ordinal classes.

scale                                Logical, scale variable to have equal sd.

contrasts                         A vector containing the 』unordered』 and 』ordered』 contrasts to use

kknn的返回值如下：

fitted.values              Vector of predictions.

CL                              Matrix of classes of the k nearest neighbors.

W                                Matrix of weights of the k nearest neighbors.

D                                 Matrix of distances of the k nearest neighbors.

C                                 Matrix of indices of the k nearest neighbors.

prob                            Matrix of predicted class probabilities.

response                   Type of response variable, one of continuous, nominal or ordinal.

distance                     Parameter of Minkowski distance.

call                              The matched call.

terms                          The 』terms』 object used.

iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)

library（kknn）
data（iris）

dim(iris)

m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))

建立訓練數據集

data.train<-iris[-val,]

建立測試數據集

data.test<-iris[val,]

調用kknn  之前首先定義公式

formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width

iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")

summary(iris.kknn)

# 獲取fitted.values

fit <- fitted(iris.kknn)

# 建立表格檢驗判類准確性

table(iris.valid$Species, fit)
# 繪畫散點圖，k-nearest neighbor用紅色高亮顯示

pcol <- as.character(as.numeric(iris.valid$Species))

pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]

二、R語言knn演算法

install.packages("class")

library(class)

對於新的測試樣例基於距離相似度的法則，確定其K個最近的鄰居，在K個鄰居中少數服從多數

確定新測試樣例的類別

1、獲得數據

2、理解數據

對數據進行探索性分析，散點圖

如上例

3、確定問題類型，分類數據分析

4、機器學習演算法knn

5、數據處理，歸一化數據處理

normalize <- function(x){

num <- x - min(x)

denom <- max(x) - min(x)

return(num/denom)

}

iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))

summary(iris_norm)

6、訓練集與測試集選取

一般按照3:1的比例選取

方法一、set.seed(1234)

ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

iris_train <-iris[ind==1, 1:4]

iris_test <-iris[ind==2, 1:4]

train_label <-iris[ind==1, 5]

test_label <-iris[ind==2, 5]

方法二、

ind<-sample(1:150,50)

iris_train<-iris[-ind,]

iris_test<-iris[ind,1:4]

iris_train<-iris[-ind,1:4]

train_label<-iris[-ind,5]

test_label<-iris[ind,5]

7、構建KNN模型

iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)

8、模型評價

交叉列聯表法

table（test_label,iris_pred)

實例二

數據集

http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data

導入數據

dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)

names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')

table(wdbc.data$Diagnosis)## M = malignant, B = benign

wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))

⑻ 大數據演算法：分類演算法

KNN演算法，即K近鄰（K Nearest Neighbour）演算法，是一種基本的分類演算法。其主要原理是：對於一個需要分類的數據，將其和一組已經分類標注好的樣本集合進行比較，得到距離最近的K個樣本，K個樣本最多歸屬的類別，就是這個需要分類數據的類別。下面我給你畫了一個KNN演算法的原理圖。

圖中，紅藍綠三種顏色的點為樣本數據，分屬三種類別 、 、 。對於待分類點 ，計算和它距離最近的5個點（即K為5），這5個點最多歸屬的類別為 （4個點歸屬 ，1個點歸屬 ），那麼 的類別被分類為 。

KNN的演算法流程也非常簡單，請看下面的流程圖。

KNN演算法是一種非常簡單實用的分類演算法，可用於各種分類的場景，比如新聞分類、商品分類等，甚至可用於簡單的文字識別。對於新聞分類，可以提前對若干新聞進行人工標注，標好新聞類別，計算好特徵向量。對於一篇未分類的新聞，計算其特徵向量後，跟所有已標注新聞進行距離計算，然後進一步利用KNN演算法進行自動分類。

讀到這你肯定會問，如何計算數據的距離呢？如何獲得新聞的特徵向量呢？

KNN演算法的關鍵是要比較需要分類的數據與樣本數據之間的距離，這在機器學習中通常的做法是：提取數據的特徵值，根據特徵值組成一個n維實數向量空間（這個空間也被稱作特徵空間），然後計算向量之間的空間距離。空間之間的距離計算方法有很多種，常用的有歐氏距離、餘弦距離等。

對於數據 和 ，若其特徵空間為n維實數向量空間 ，即 ， ，則其歐氏距離計算公式為

這個歐式距離公式其實我們在初中的時候就學過，平面幾何和立體幾何里兩個點之間的距離，也是用這個公式計算出來的，只是平面幾何（二維幾何）里的n=2，立體幾何（三維幾何）里的n=3，而機器學習需要面對的每個數據都可能有n維的維度，即每個數據有n個特徵值。但是不管特徵值n是多少，兩個數據之間的空間距離的計算公式還是這個歐氏計算公式。大多數機器學習演算法都需要計算數據之間的距離，因此掌握數據的距離計算公式是掌握機器學習演算法的基礎。

歐氏距離是最常用的數據計算公式，但是在文本數據以及用戶評價數據的機器學習中，更常用的距離計算方法是餘弦相似度。

餘弦相似度的值越接近1表示其越相似，越接近0表示其差異越大，使用餘弦相似度可以消除數據的某些冗餘信息，某些情況下更貼近數據的本質。我舉個簡單的例子，比如兩篇文章的特徵值都是：「大數據」「機器學習」和「極客時間」，A文章的特徵向量為（3, 3, 3），即這三個詞出現次數都是3；B文章的特徵向量為（6, 6, 6），即這三個詞出現次數都是6。如果光看特徵向量，這兩個向量差別很大，如果用歐氏距離計算確實也很大，但是這兩篇文章其實非常相似，只是篇幅不同而已，它們的餘弦相似度為1，表示非常相似。

餘弦相似度其實是計算向量的夾角，而歐氏距離公式是計算空間距離。餘弦相似度更關注數據的相似性，比如兩個用戶給兩件商品的打分分別是（3, 3）和（4, 4），那麼兩個用戶對兩件商品的喜好是相似的，這種情況下，餘弦相似度比歐氏距離更合理。

我們知道了機器學習的演算法需要計算距離，而計算距離需要還知道數據的特徵向量，因此提取數據的特徵向量是機器學習工程師們的重要工作，有時候甚至是最重要的工作。不同的數據以及不同的應用場景需要提取不同的特徵值，我們以比較常見的文本數據為例，看看如何提取文本特徵向量。

文本數據的特徵值就是提取文本關鍵詞，TF-IDF演算法是比較常用且直觀的一種文本關鍵詞提取演算法。這種演算法是由TF和IDF兩部分構成。

TF是詞頻（Term Frequency），表示某個單詞在文檔中出現的頻率，一個單詞在一個文檔中出現的越頻繁，TF值越高。

詞頻：

IDF是逆文檔頻率（Inverse Document Frequency），表示這個單詞在所有文檔中的稀缺程度，越少文檔出現這個詞，IDF值越高。

逆文檔頻率：

TF與IDF的乘積就是TF-IDF。

所以如果一個詞在某一個文檔中頻繁出現，但在所有文檔中卻很少出現，那麼這個詞很可能就是這個文檔的關鍵詞。比如一篇關於原子能的技術文章，「核裂變」「放射性」「半衰期」等詞彙會在這篇文檔中頻繁出現，即TF很高；但是在所有文檔中出現的頻率卻比較低，即IDF也比較高。因此這幾個詞的TF-IDF值就會很高，就可能是這篇文檔的關鍵詞。如果這是一篇關於中國原子能的文章，也許「中國」這個詞也會頻繁出現，即TF也很高，但是「中國」也在很多文檔中出現，那麼IDF就會比較低，最後「中國」這個詞的TF-IDF就很低，不會成為這個文檔的關鍵詞。

提取出關鍵詞以後，就可以利用關鍵詞的詞頻構造特徵向量，比如上面例子關於原子能的文章，「核裂變」「放射性」「半衰期」這三個詞是特徵值，分別出現次數為12、9、4。那麼這篇文章的特徵向量就是（12, 9, 4），再利用前面提到的空間距離計算公式計算與其他文檔的距離，結合KNN演算法就可以實現文檔的自動分類。

貝葉斯公式是一種基於條件概率的分類演算法，如果我們已經知道A和B的發生概率，並且知道了B發生情況下A發生的概率，可以用貝葉斯公式計算A發生的情況下B發生的概率。事實上，我們可以根據A的情況，即輸入數據，判斷B的概率，即B的可能性，進而進行分類。

舉個例子：假設一所學校里男生佔60%，女生佔40%。男生總是穿長褲，女生則一半穿長褲一半穿裙子。假設你走在校園中，迎面走來一個穿長褲的學生，你能夠推斷出這個穿長褲學生是男生的概率是多少嗎？

答案是75%，具體演算法是：

這個演算法就利用了貝葉斯公式，貝葉斯公式的寫法是：

意思是A發生的條件下B發生的概率，等於B發生的條件下A發生的概率，乘以B發生的概率，除以A發生的概率。還是上面這個例子，如果我問你迎面走來穿裙子的學生是女生的概率是多少。同樣帶入貝葉斯公式，可以計算出是女生的概率為100%。其實這個結果我們根據常識也能推斷出來，但是很多時候，常識受各種因素的干擾，會出現偏差。比如有人看到一篇博士生給初中學歷老闆打工的新聞，就感嘆讀書無用。事實上，只是少見多怪，樣本量太少而已。而大量數據的統計規律則能准確反映事物的分類概率。

貝葉斯分類的一個典型的應用場合是垃圾郵件分類，通過對樣本郵件的統計，我們知道每個詞在郵件中出現的概率 ，我們也知道正常郵件概率 和垃圾郵件的概率 ，還可以統計出垃圾郵件中各個詞的出現概率 ，那麼現在一封新郵件到來，我們就可以根據郵件中出現的詞，計算 ，即得到這些詞出現情況下，郵件為垃圾郵件的概率，進而判斷郵件是否為垃圾郵件。

現實中，貝葉斯公式等號右邊的概率，我們可以通過對大數據的統計獲得，當有新的數據到來的時候，我們就可以帶入上面的貝葉斯公式計算其概率。而如果我們設定概率超過某個值就認為其會發生，那麼我們就對這個數據進行了分類和預測，具體過程如下圖所示。

訓練樣本就是我們的原始數據，有時候原始數據並不包含我們想要計算的維度數據，比如我們想用貝葉斯公式自動分類垃圾郵件，那麼首先要對原始郵件進行標注，需要標注哪些郵件是正常郵件、哪些郵件是垃圾郵件。這一類需要對數據進行標注才能進行的機器學習訓練也叫作有監督的機器學習。