# k近鄰算法
* [第一部分 knn概述](#第一節)
* [第二部分 knn使用場景](#第二節)
* [第三部分 knn原理](#第三節)
* [第四部分 knn具體實例1(優化約會網站的配對效果)](#第四節)
* [4.1 項目概述](#4.1)
* [4.2 開發流程](#4.2)
* [第五部分 knn具體實例2(手寫數字識別系統)](#第五節)
* [5.1 項目概述](#4.1)
* [5.2 開發流程](#4.2)
* [第六部分 knn小節](#第六節)
<h3 id="第一節">第一部分:knn概述</h5>
k-近鄰(knn, k-NearestNeighbor)算法是一種基本分類回歸算法,我們這里只討論分類問題中的k-近鄰算法。
k-近鄰算法的輸入為實例的特征向量,對應于特征空間中的點;輸出為實例的類別。可以取多類。k近鄰算法假定給定一個訓練數據集,其中的實例類別已經確定。分類時,對新的實例,根據其k個最近的訓練實例的類別,通過多數表決等方式進行預測。因此,k近鄰算法不具有顯示的學習過程。
k近鄰算法實際上利用訓練數據集對特征空間進行劃分,并作為其分類的“模型”。**k值得選擇**、**距離度量**以及**分類決策規則**是k近鄰算法的三個基本要素。
<h3 id="第二節">第二部分:knn使用場景</h5>
電影可以按照題材分類,那么如何區分動作片和愛情片呢?
1動作片:打斗次數更多 2愛情片:親吻次數更多
基于電影中的親吻、打斗出現的次數,使用k-近鄰算法構造程序,就可以自動劃分電影的題材類型。

> 現在根據上面我們得到的樣本集中所有電影與未知電影的距離,按照距離遞增排序,可以找到 k 個距離最近的電影。
假定 k=3,則三個最靠近的電影依次是, He's Not Really into Dudes 、 Beautiful Woman 和 California Man。
knn 算法按照距離最近的三部電影的類型,決定未知電影的類型,而這三部電影全是愛情片,因此我們判定未知電影是愛情片。
<h3 id="第三節">第三部分:knn原理</h5>
> KNN 工作原理
>
1.假設有一個帶有標簽的樣本數據集(訓練樣本集),其中包含每條數據與所屬分類的對應關系。
2.輸入沒有標簽的新數據后,將新數據的每個特征與樣本集中數據對應的特征進行比較。<br>a.計算新數據與樣本數據集中每條數據的距離。<br>b.對求得的所有距離進行排序(從小到大,越小表示越相似)。c.取前 k (k 一般小于等于 20 )個樣本數據對應的分類標簽。
3.求 k 個數據中出現次數最多的分類標簽作為新數據的分類。
> KNN 通俗理解
>
給定一個訓練數據集,對新的輸入實例,在訓練數據集中找到與該實例最鄰近的 k 個實例,這 k 個實例的多數屬于某個類,就把該輸入實例分為這個類。
> KNN 開發流程
> 收集數據:任何方法
> 準備數據:距離計算所需要的數值,最好是結構化的數據格式
> 分析數據:任何方法
> 訓練算法:此步驟不適用于 k-近鄰算法
> 測試算法:計算錯誤率
> 使用算法:輸入樣本數據和結構化的輸出結果,然后運行 k-近鄰算法判斷輸入數據分類屬于哪個分類,最后對計算出的分類執行后續處理
>
> KNN 算法特點
> 優點:精度高、對異常值不敏感、無數據輸入假定
缺點:計算復雜度高、空間復雜度高
適用數據范圍:數值型和標稱型
<h3 id="第四節">第四部分:knn具體實例1(優化約會網站的配對效果)</h5>
<h5 id="4.1">項目概述</h5>
海倫使用約會網站尋找約會對象。經過一段時間之后,她發現曾交往過三種類型的人:不喜歡的人、魅力一般的人、極具魅力的人。
她希望:1,工作日與魅力一般的人約會 2.周末與極具魅力的人約會3.不喜歡的人則直接排除掉
現在她收集到了一些約會網站未曾記錄的數據信息,這更有助于匹配對象的歸類。
<h5 id="4.2">開發流程</h5>、
> 收集數據:提供文本文件
> 準備數據:使用 Python 解析文本文件
> 分析數據:使用 Matplotlib 畫二維散點圖
> 訓練算法:此步驟不適用于 k-近鄰算法
> 測試算法:使用海倫提供的部分數據作為測試樣本。
測試樣本和非測試樣本的區別在于:
測試樣本是已經完成分類的數據,如果預測分類與實際類別不同,則標記為一個錯誤。
使用算法:產生簡單的命令行程序,然后海倫可以輸入一些特征數據以判斷對方是否為自己喜歡的類型。
下面我們來事先該算法。
1. 收集數據
海倫把這些約會對象的數據存放在文本文件 datingTestSet2.txt 中,總共有 1000 行。海倫約會的對象主要包含以下 3 種特征:
* 每年獲得的飛行常客里程數
* 玩視頻游戲所耗時間百分比
* 每周消費的冰淇淋公升數
文本文件數據格式如下:
| 40920 | 8.326976 | 0.953952 | 3 |
| --- | --- | --- | --- |
| 14488 | 7.153469 | 1.673904 | 2 |
| 75136 | 13.147394 | 0.428964 | 1 |
| 38344 | 1.669788 | 0.134296 | 1 |
> 最后的1、2、3表示屬于第幾類。數據下載地址:https://github.com/apachecn/MachineLearning/blob/master/input/2.KNN/datingTestSet2.txt
>
2.準備數據:使用python解析文本文件
將文本記錄轉換為NumPy的解析函數。
我們使用前面環境搭建一章搭建好的機器學習環境建立一個項目:knn

我們新建一個python文件knn.py然后輸入一下代碼:
~~~
from numpy import *
def file2matrix(filename):
"""
desc:
導入訓練數據
:param filename: 數據文件路徑
:return:數據矩陣 returnMat 和對應的類別 classLabelVector
"""
fr = open(filename)
# 獲取文件中的數據行的行數
numberOfLine = len(fr.readlines())
# 生成對應的空矩陣
# 例如:zeros(2,3)就是生成一個2*3的矩陣,各個位置上全是0
returnMat = zeros((numberOfLine, 3)) # prepare matrix to raturn
classLabelVector = [] #prepare labels return
index = 0
for line in fr.readlines():
# str.strip([chars]) --用于移除字符串頭尾指定的字符(默認為空格或換行符)或字符序列
line = line.strip()
# 以'\t'切割字符串
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
# 每列的類別數據,就是label標簽數據
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
~~~
3.
- 序言
- 第一章 機器學習概述
- 第二章 機器學習環境搭建
- 環境搭建
- 第三章 機器學習之基礎算法
- 第一節:基礎知識
- 第二節:k近鄰算法
- 第三節:決策樹算法
- 第四節:樸素貝葉斯
- 第五節:邏輯斯蒂回歸
- 第六節:支持向量機
- 第四章 機器學習之深度學習算法
- 第一節: CNN
- 4.1.1 CNN介紹
- 4.1.2 CNN反向傳播
- 4.1.3 DNN實例
- 4.1.4 CNN實例
- 第五章 機器學習論文與實踐
- 第一節: 語義分割
- 5.1 FCN
- 5.1.1 FCN--------實現FCN16S
- 5.1.2 FCN--------優化FCN16S
- 5.2 DeepLab
- 5.2.1 DeepLabv2
- 第六章 機器學習在實際項目中的應用