K近臨演算法的優點

1. 實驗二 K-近鄰演算法及應用

（1）簡單，易於理解，易於實現，無需估計參數。

（2）訓練時間為零。它沒有顯示的訓練，不像其它有監督的演算法會用訓練集train一個模型（也就是擬合一個函數），然後驗證集或測試集用該模型分類。KNN只是把樣本保存起來，收到測試數據時再處理，所以KNN訓練時間為零。

（3）KNN可以處理分類問題，同時天然可以處理多分類問題，適合對稀有事件進行分類。

（4）特別適合於多分類問題(multi-modal,對象具有多個類別標簽)， KNN比SVM的表現要好。

（5）KNN還可以處理回歸問題，也就是預測。

（6）和樸素貝葉斯之類的演算法比，對數據沒有假設，准確度高，對異常點不敏感。

（1）計算量太大，尤其是特徵數非常多的時候。每一個待分類文本都要計算它到全體已知樣本的距離，才能得到它的第K個最近鄰點。

（2）可理解性差，無法給出像決策樹那樣的規則。

（3）是慵懶散學習方法，基本上不學習，導致預測時速度比起邏輯回歸之類的演算法慢。

（4）樣本不平衡的時候，對稀有類別的預測准確率低。當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。

（5）對訓練數據依賴度特別大，對訓練數據的容錯性太差。如果訓練數據集中，有一兩個數據是錯誤的，剛剛好又在需要分類的數值的旁邊，這樣就會直接導致預測的數據的不準確。

需要一個特別容易解釋的模型的時候。
比如需要向用戶解釋原因的推薦演算法。

通過此次實驗我了解了K近鄰演算法及其思路，該方法的思路是：如果一個樣本在特徵空間中的k個最相似的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
所謂k近鄰演算法，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的k個實例。

2. k近鄰&kd樹

k近鄰演算法是懶惰學習的代表演算法。之所以說k近鄰懶惰，是因為它沒有顯示的訓練過程。它的思路很簡單， 手頭有一些帶標簽的樣本，現在給定一個新的樣本，找出已有樣本中距離新樣本最近的k個樣本點，然後取這k個樣本點標簽的投票結果。

k近鄰演算法本身並不復雜，但有幾個細節需要注意：

（1）距離度量

不同的距離度量可能產生不同的k近鄰，從而直接影響預測結果。至於度量的選取要結合應用場景， 關鍵在於我們需要知道在特定場景中如何量化兩樣本之間的相似度。

（2）k值選擇

k值的選擇沒有經驗性的方法，一般只能通過交叉驗證來選取合適的k值。

如果k值選擇較小，就相當於用較小的鄰域中的訓練實例進行預測，「學習」的近似誤差會減小，只有與輸入實例較近的訓練實例才會對預測起作用，但估計誤差會增大，預測結果會對近鄰的實例點非常敏感，如果近鄰的實例點恰巧是雜訊，預測就會出錯。相反如果k值選擇較大，就相當於用較大的領域中的訓練實例進行預測，近似誤差會增大，但估計誤差會減小。

對於k近鄰法來說，k越大模型越簡單，這一點乍一看不容易理解，但其實我們可以考慮極端情況k=N（N為樣本數），此時任何新樣本都會被歸入當前樣本集中實例最多的類別，從而丟失大量信息。反之，k越小模型越復雜，模型將面臨過擬合風險。

（3）投票法

k近鄰使用多數表決亮鬧的投票法看起來十分自然，但我們也可以從 最小化經驗誤差 的角度來理解，如果分類的損失函數為0-1損失函數，則誤分類概率為：

對於給定實例 ，其最近鄰的k個訓練實例構成集合 ，若涵蓋 的區域的類別是 ，則誤分類概率為：

要使誤分類率最小即經驗風險最小，就要使 最大，這正是投票法（多數表決）所做的事情。

kd樹是一種對k維空間中的實例點進行儲存以便對其進行快速檢索的樹形數據結構。 kd樹是二叉樹，表示對k維空間的一個劃分。構造kd樹相當於不斷用垂直於坐標軸的超平面將k維空間切分，構成一系列k維超矩形區域。

構造平衡kd樹的流程 如下：

輸入：k維空間數據集

（1）構造根結點，根結點對應於包含 的k維空間的超矩形區域。

（2）對深度為 的結點，選擇 為切分的坐標軸（ ），以該結點區域中所有實例的 坐標的中位數為切分點，將該結點對應的超矩形區域劃分為兩個子區域，切分由通過切分點並與坐標軸 垂直的超平面實現。

（3）重復（2）直至劃分得到的兩個子區域中沒有實例存在為止。

用kd樹進行最近鄰搜索的流程 如下：

輸入：構造好的kd樹，目標節點x

（1）在kd樹中找到包含目標節點 的葉結點：從根結點出發，遞歸地向下訪問kd樹。若目標 當前維的坐標小於切分點坐標則移動敬物罩到左子結點，否則移動到右子結點，直至子結點為葉結點為止。

（2）以此葉結點為「當前最近點」。

（3）遞歸地向上回退：

（4）當回退到根結點，搜索結束，此時的「當前最近點」即為 的最近鄰點。螞檔

以上就是利用kd樹進行最近鄰搜索的過程，同樣的方法可以推廣到k近鄰。現在我們來思考一下這個演算法的本質。

其實我個人理解的是， kd樹的構造就是二分法在k維的應用。 但是不太相同的是，kd樹演算法並不是選定一個軸後不斷二分直至結束，而是做一次二分換一個軸，這是因為如果我們只選定一個軸做二分得到的結果並不能反映各樣本之間距離的遠近，而兼顧各個軸則能一定程度上度量樣本之間的距離。

我們可以想像3維的情況，kd樹最終會形成一系列的小正方體，我們要想找距離一個新樣本點最近的樣本點，只需要找到新樣本點所在的小正方體，然後check這個小正方體中的樣本以及和這個小正方體 相鄰 的小正方體中的樣本哪個距離新樣本最近即可（相鄰這個概念是很重要的，為便於理解，考慮在一維的情況下，此過程為找到新樣本所在區間，然後檢查此區間以及左右相鄰區間中的樣本點即可）。而 相鄰 這個概念剛好和kd樹的構造過程相符，我們不斷回退的過程其實就是檢查 各個不同方向上 的相鄰超矩形的過程。這個過程十分高效，不難看出，平衡kd樹尋找最近鄰的復雜度是 。

3. 機器學習中演算法的優缺點之最近鄰演算法

機器學習中有個演算法是十分重要的，那就是最近鄰演算法，這種演算法被大家稱為KNN。我們在學習機器學習知識的時候一定要學習這種演算法，其實不管是什麼演算法都是有自己的優缺點的，KNN演算法也不例外，在這篇文章中我們就詳細的給大家介紹一下KNN演算法的優缺點，大家一定要好好學起來喲。
說到KNN演算法我們有必要說一下KNN演算法的主要過程，KNN演算法的主要過程有四種，第一就是計算訓練樣本和測試樣本中每個樣本點的距離，第二個步驟就是對上面所有的距離值進行排序(升序)。第三個步驟就是選前k個最小距離的樣本。第四個步驟就是根據這k個樣本的標簽進行投票，得到最後的分類類別。
那麼大家是否知道如何選擇一個最佳的K值，這取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一般來說，一個較好的K值可通過各種啟發式技術來獲取，比如說交叉驗證。另外雜訊和非相關性特徵向量的存在會使K近鄰演算法的准確性減小。近鄰演算法具有較強的一致性結果，隨著數據趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些好的K值，K近鄰保證錯誤率不會超過貝葉斯理論誤差率。
那麼KNN演算法的優點是什麼呢？KNN演算法的優點具體體現在六點，第一就是對數據沒有假設，准確度高，對outlier不敏感。第二就是KNN是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練。第三就是KNN理論簡單，容易實現。第四就是理論成熟，思想簡單，既可以用來做分類也可以用來做回歸。第五就是可用於非線性分類。第六就是訓練時間復雜度為O(n)。由此可見，KNN演算法的優點是有很多的。
那麼KNN演算法的缺點是什麼呢？這種演算法的缺點具體體現在六點，第一就是樣本不平衡時，預測偏差比較大。第二就是KNN每一次分類都會重新進行一次全局運算。第三就是k值大小的選擇沒有理論選擇最優，往往是結合K-折交叉驗證得到最優k值選擇。第四就是樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）效果差。第五就是需要大量內存。第六就是對於樣本容量大的數據集計算量比較大。
正是由於這些優點和缺點，KNN演算法應用領域比較廣泛，在文本分類、模式識別、聚類分析，多分類領域中處處有KNN演算法的身影。
在這篇文章中我們給大家介紹了很多關於KNN演算法的相關知識，通過對這些知識的理解相信大家已經知道該演算法的特點了吧，希望這篇文章能夠幫助大家更好的理解KNN演算法。

4. K-近鄰演算法（K-NN）

給定一個訓練數據集，對於新的輸入實例， 根據這個實例最近的 k 個實例所屬的類別來決定其屬於哪一類 。所以相對於其它機器學習模型和演算法，k 近鄰總體上而言是一種非常簡單的方法。

找到與該實例最近鄰的實例，這里就涉及到如何找到，即在特徵向量空間中，我們要採取 何種方式來對距離進行度量 。

距離的度量用在 k 近鄰中我們也可以稱之為 相似性度量 ，即特徵空間中兩個實例點相似程度的反映。在機器學習中，常用的距離度量方式包括歐式距離、曼哈頓距離、餘弦距離以及切比雪夫距離等。 在 k 近鄰演算法中常用的距離度量方式是歐式距離，也即 L2 距離， L2 距離計算公式如下：

一般而言，k 值的大小對分類結果有著重大的影響。 當選擇的 k 值較小的情況下，就相當於用較小的鄰域中的訓練實例進行預測，只有當與輸入實例較近的訓練實例才會對預測結果起作用。但與此同時預測結果會對實例點非常敏感，分類器抗噪能力較差，因而容易產生過擬合 ，所以一般而言，k 值的選擇不宜過小。但如果選擇較大的 k 值，就相當於在用較大鄰域中的悶鄭握訓練實例進行預測，但相應的分類誤差也會增大，模型整體變得簡單，會產生一定程度的欠擬合。所以一般而言，我們需要 採用交叉驗證的方式來選擇合適的 k 值 。

k 個實例的多數屬於哪叢褲個類，明顯是多數表決的歸類規則。當然還可能使用其他規則，所以第三個關鍵就是 分類決策規則。

回歸：k個實例該屬性值的平均值

它是一個二叉樹的數據結構，方便存儲 K 維空間的數據

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

如果是做分類，你需要引用：from sklearn.neihbors import KNeighborsClassifier
如果是回歸， 需要引用：from sklearn.neighbors import KNeighborsRegressor

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs)

5. k近鄰演算法精確度的提高有什麼科學性，先進性和獨特之處

K近鄰(k-Nearest Neighbour，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
K-近鄰法就是一種基於文本特徵向量空間模型表示的文本分類方法,有很多優點,演算法簡單,易於實現,分類精度較高。

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

7. k近鄰演算法特徵值非數字

k-近鄰演算法採用測量不同特徵值之間的距離來進行分類。
優點：精度高，對異常值不敏感，無數據輸入假定。缺點：計算復雜度高、空間復雜度高。適用數據范圍：數值型和分類型。原理：首先，我們必須得有一份含有分類標簽的數據集，為訓練數據集。比如我們要預測用戶是否會流失，那麼分類標簽就是流失和未流失。然後有一份新的數據集，這份數據集並沒有分類標簽，k-近鄰演算法就會將新的數據集和訓練數據集進行比較，從訓練數據集中選出與新數據集每個數據最相近的K個數據，查看這K個數據所屬標簽哪類最多，比如流失，就把新數據集中的那個數據分類為流失。怎麼判斷是否相近呢？K-近鄰是計算不同數據的距離。k-近鄰演算法的原理偽代碼。
對未知類別屬性的數據集中的每個數據點依次執行以下操作：(1)計算已知類別數據集中的點與當前點之間的距離。(2)按照距離遞增次序排序。(3)選出與當前距離最近的K個點。(4)統計出K個點所屬類別的頻率。(5)返回K個點出現頻率最高的的類別作為當前點的預測類別

8. k近鄰演算法中關鍵的要素是

k近鄰演算法中關鍵的要素是：k值的選取、鄰居距離的度量和分類決策的制訂。

1.k值的選取：

k近鄰演算法優點很明顯，簡單易用，可解釋性強，但也有其不足之處。例如，「多數表決」會在類別分布偏斜時浮現缺陷。也就是說，k值的選取非常重要，出現頻率較多的樣本將會主導測試點的預測結果。

3.分類決策的制訂：

本質上，分類器就是一個由特徵向量，到預測類別的映射函數。k近鄰演算法的分類流程大致如下三步走：（1）計算待測試樣本與訓練集合中每一個樣本的歐式距離；（2）對每一個距離從小到大排序；（3）選擇前k個距離最短的樣本，分類任務採用「少數服從多數」的表決規則。回歸任務則可採用k個近鄰的平均值舉茄作為預測值。

9. 什麼叫做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值的方法是自助法。

10. k近鄰演算法是有監督還是無監督

k近鄰演算法是有監督。

k近鄰演算法的流程和優點：

k近鄰演算法的一般流程是：

1、收集數據。

2、計算待測數據與訓練數據之間的距離（一般採用歐式距離）。

3、將計算的距離排序。

4、找出距離最小的k個值。

5、計算找出值中每個類別的頻次。

6、返回最高頻次的類別。

優點：精度高、對異常值不敏感缺點：計算復雜度高、空間復雜度高。K近鄰最直接的利用了樣本之間的關系，減少了類別特徵選擇不當對分類結果造成的不利影響，可以最大程度減少分類過程中的做察派誤差項。