knn演算法改進

㈠ k近鄰演算法的案例介紹

如 上圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬於哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。我們常說，物以類聚，人以群分，判別一個人是一個什麼樣品質特徵的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬於哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。 於此我們看到，當無法判定當前待分類點是從屬於已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰演算法的核心思想。
KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
KNN 演算法本身簡單有效，它是一種 lazy-learning 演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN 分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那麼 KNN 的分類時間復雜度為O(n)。
KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
K 近鄰演算法使用的模型實際上對應於對特徵空間的劃分。K 值的選擇，距離度量和分類決策規則是該演算法的三個基本要素： K 值的選擇會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。 該演算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別 距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。 KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
實現 K 近鄰演算法時，主要考慮的問題是如何對訓練數據進行快速 K 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

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

㈢ KNN演算法，結果報錯，幫忙怎麼改

knn演算法(k-Nearest Neighbor algorithm).是一種經典的分類演算法.
注意,不是聚類演算法.所以這種分類演算法必然包括了訓練過程.
然而和一般性的分類演算法不同,knn演算法是一種 懶惰演算法 .它並非
像其他的分類演算法先通過訓練建立分類模型.,而是一種被動的分類
過程.它是邊測試邊訓練建立分類模型.
演算法的一般描述過程如下:
1.首先計算每個測試樣本點到其他每個點的距離.
這個距離可以是歐氏距離,餘弦距離等.

㈣ KNN演算法-4-演算法優化-KD樹

KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。

Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。

k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。

必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：

首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。

常規的k-d tree的構建過程為：

對於構建過程，有兩個優化點：

例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：

如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。

如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：

kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。

如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。

首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。

以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。

接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。

以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。

遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢點（2.1,3.1）

星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。

舉例：查詢點（2，4.5）

一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：

上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。

一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：

但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：

研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。

同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。

Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。

㈤ 文本分類器（基於KNN演算法），語言最好是Matlab的，有測試數據集。。。。

function [ccr,pgroupt]=knnt(x,group,K,dist,xt,groupt)
%#
%# AIM: to classify test set objects or unknown objects with the
%# K Nearest Neighbour method
%#
%# PRINCIPLE: KNN is a supervised, deterministic, non-parametric
%# classification method. It uses the majority rule to
%# assign new objects to a class.
%# It is assumed that the number of objects in each class
%# is similar.
%# There are no assumptions about the data distribution and
%# the variance-covariance matrices of each class.
%# There is no limitation of the number of variables when
%# the Euclidean distance is used.
%# However, when the correlation coefficient is used, the
%# number of variables must be larger than 1.
%# Ref: Massart D. L., Vandeginste B. G. M., Deming S. N.,
%# Michotte Y. and Kaufman L., Chemometrics: a textbook,
%# Chapter 23, 395-397, Elsevier Science Publishers B. V.,
%# Amsterdam 1988.
%#
%# INPUT: x: (mxn) data matrix with m objects and n variables,
%# containing samples of several classes (training set)
%# group: (mx1) column vector labelling the m objects from the
%# training set
%# K: integer, number of nearest neighbours
%# dist: integer,
%# = 1, Euclidean distance
%# = 2, Correlation coefficient, (No. of variables >1)
%# xt: (mtxn) data matrix with mt objects and n variables
%# (test set or unknowns)
%# groupt: (mtx1) column vector labelling the mt objects from
%# the test set
%# --> if the new objects are unknown, input [].
%#
%# OUTPUT: ccr: scalar, correct classification rate
%# pgroupt:row vector, predicted class label for the test set
%# 0 means that the object is not classified to any
%# class
%#
%# SUBROUTINES: sortlab.m: sorts the group label vector into classes
%#
%# AUTHOR: Wen Wu
%# Copyright(c) 1997 for ChemoAc
%# FABI, Vrije Universiteit Brussel
%# Laarbeeklaan 103 1090 Jette
%#
%# VERSION: 1.1 (28/02/1998)
%#
%# TEST: Andrea Candolfi
%#

function [ccr,pgroupt]=knnt(x,group,K,dist,xt,groupt);

if nargin==5, groupt=[]; end % for unknown objects
distance=dist; clear dist % change variable
if size(group,1)>1,
group=group'; % change column vector into row vector
groupt=groupt'; % change column vector into row vector
end;
[m,n]=size(x); % size of the training set

if distance==2 & n<2, error('Number of variables must > 1'),end % to check the number of variables when using correlation coefficient

[mt,n]=size(xt); % size of the test set
dis=zeros(mt,m); % initial values for the distance (matrix of zeros)

% Calculation of the distance for each test set object
for i=1:mt
for j=1:m % between each training set object and each test set object
if distance==1
dis(i,j)=(xt(i,:)-x(j,:))*(xt(i,:)-x(j,:))'; % Euclidian distance
else
r=corrcoef(xt(i,:)',x(j,:)'); % Correlation coefficient matrix
r=r(1,2); % Correlation coefficient
dis(i,j)=1-r*r; % 1 - the power of correlation coefficient
end
end
end

% Finding of the nearest neighbours
lab=zeros(1,mt); % initial values of lab
for i=1:mt % for each test object
[a,b]=sort(dis(i,:)); % sort distances
b=b(find(a<=a(K))); % to find the nearest neighbours indices
b=group(b); % the nearest neighbours objects
[ng,lgroup]=sortlab(b); % calculate the number of objects from each class in the nearest neighbours
a=find(ng==max(ng)); % find the class with the maximum number of objects

if length(a)==1 % only one class
lab(i)=lgroup(a); % class label
else
lab(i)=0; % more than one class
end
end

% Calculation of the success rate
if ~isempty(groupt)
dif=groupt-lab; % difference between predicted class label and known class label
ccr=sum(dif==0)/mt; % success rate
end

pgroupt=lab; % the output vector

㈥ K-means 與KNN 聚類演算法

        K-means 演算法屬於聚類演算法的一種。聚類演算法就是把相似的對象通過靜態分類方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性。聚類演算法的任務是將數據集劃分為多個集群。在相同集群中的數據彼此會比不同集群的數據相似。通常來說，聚類演算法的目標就是通過相似特徵將數據分組並分配進不同的集群中。

K-means 聚類演算法是一種非監督學習演算法，被用於非標簽數據（data without defined categories or groups）。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。  演算法從 Κ 質心的初始估計開始，其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代：

每個質心定義一個集群。在此步驟中，基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點， ci  屬於質心集合  C  ，然後每個數據點  x  基於下面的公式被分配到一個集群中。

在此步驟中，重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下：

K-means 演算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即，沒有數據點改變集群，距離的總和最小化，或者達到一些最大迭代次數）。

上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數，用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常，沒有用於確定 K 的精確值的方法，但是可以使用以下技術獲得准確的估計。

Elbow point 拐點方法

通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離，因此當 K 與數據點的數量相同時，增加 K 將總是減小該度量，達到零的極值。因此，該指標不能用作唯一目標。相反，繪制了作為 K 到質心的平均距離的函數，並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。

DBI（Davies-Bouldin Index）

DBI 是一種評估度量的聚類演算法的指標，通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是：DBI 是聚類內的距離與聚類外的距離的比值。所以，DBI 的數值越小，表示分散程度越低，聚類效果越好。

還存在許多用於驗證 K 的其他技術，包括交叉驗證，信息標准，信息理論跳躍方法，輪廓方法和 G 均值演算法等等。

需要提前確定 K 的選值或者需嘗試很多 K 的取值

數據必須是數字的，可以通過歐氏距離比較

對特殊數據敏感，很容易受特殊數據影響

對初始選擇的質心/中心（centers）敏感

之前介紹了  KNN （K 鄰近）演算法 ，感覺這兩個演算法的名字很接近，下面做一個簡略對比。

K-means  ：

聚類演算法

用於非監督學習

使用無標簽數據

需要訓練過程

K-NN ：

分類演算法

用於監督學習

使用標簽數據

沒有明顯的訓練過程

鄰近演算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類演算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。Cover和Hart在1968年提出了最初的鄰近演算法。KNN是一種分類(classification)演算法，它輸入基於實例的學習（instance-based learning），屬於懶惰學習（lazy learning）即KNN沒有顯式的學習過程，也就是說沒有訓練階段，數據集事先已有了分類和特徵值，待收到新樣本後直接進行處理。與急切學習（eager learning）相對應。

KNN是通過測量不同特徵值之間的距離進行分類。 

思路是：如果一個樣本在特徵空間中的k個最鄰近的樣本中的大多數屬於某一個類別，則該樣本也劃分為這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

提到KNN，網上最常見的就是下面這個圖，可以幫助大家理解。

我們要確定綠點屬於哪個顏色（紅色或者藍色），要做的就是選出距離目標點距離最近的k個點，看這k個點的大多數顏色是什麼顏色。當k取3的時候，我們可以看出距離最近的三個，分別是紅色、紅色、藍色，因此得到目標點為紅色。

演算法的描述：

1）計算測試數據與各個訓練數據之間的距離；

2）按照距離的遞增關系進行排序；

3）選取距離最小的K個點；

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

5）返回前K個點中出現頻率最高的類別作為測試數據的預測分類

二、關於 K 的取值

K：臨近數，即在預測目標點時取幾個臨近的點來預測。

K值得選取非常重要，因為：

如果當K的取值過小時，一旦有雜訊得成分存在們將會對預測產生比較大影響，例如取K值為1時，一旦最近的一個點是雜訊，那麼就會出現偏差，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

如果K的值取的過大時，就相當於用較大鄰域中的訓練實例進行預測，學習的近似誤差會增大。這時與輸入目標點較遠實例也會對預測起作用，使預測發生錯誤。K值的增大就意味著整體的模型變得簡單；

如果K==N的時候，那麼就是取全部的實例，即為取實例中某分類下最多的點，就對預測沒有什麼實際的意義了；

K的取值盡量要取奇數，以保證在計算結果最後會產生一個較多的類別，如果取偶數可能會產生相等的情況，不利於預測。

K的取法：

 常用的方法是從k=1開始，使用檢驗集估計分類器的誤差率。重復該過程，每次K增值1，允許增加一個近鄰。選取產生最小誤差率的K。

一般k的取值不超過20，上限是n的開方，隨著數據集的增大，K的值也要增大。

三、關於距離的選取

距離就是平面上兩個點的直線距離

關於距離的度量方法，常用的有：歐幾里得距離、餘弦值（cos）, 相關度 （correlation）, 曼哈頓距離 （Manhattan distance）或其他。

Euclidean Distance 定義：

兩個點或元組P1=（x1，y1）和P2=（x2，y2）的歐幾里得距離是

距離公式為：（多個維度的時候是多個維度各自求差）

四、總結

KNN演算法是最簡單有效的分類演算法，簡單且容易實現。當訓練數據集很大時，需要大量的存儲空間，而且需要計算待測樣本和訓練數據集中所有樣本的距離，所以非常耗時

KNN對於隨機分布的數據集分類效果較差，對於類內間距小，類間間距大的數據集分類效果好，而且對於邊界不規則的數據效果好於線性分類器。

KNN對於樣本不均衡的數據效果不好，需要進行改進。改進的方法時對k個近鄰數據賦予權重，比如距離測試樣本越近，權重越大。

KNN很耗時，時間復雜度為O(n)，一般適用於樣本數較少的數據集，當數據量大時，可以將數據以樹的形式呈現，能提高速度，常用的有kd-tree和ball-tree。

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

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

（本節完。）

推薦閱讀：

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

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

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

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

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

㈧ knn演算法如何選擇一個最佳k值

K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。