# 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.