knn演算法時間復雜度

① 為什麼k臨近演算法不能處理特徵很多的數據集

機器學習中常常要用到分類演算法，在諸多的分類演算法中有一種演算法名為k-近鄰演算法，也稱為kNN演算法。
一、kNN演算法的工作原理
二、適用情況
三、演算法實例及講解
---1.收集數據
---2.准備數據
---3.設計演算法分析數據
---4.測試演算法

一、kNN演算法的工作原理
官方解釋：存在一個樣本數據集，也稱作訓練樣本集，並且樣本中每個數據都存在標簽，即我們知道樣本集中每一數據與所屬分類的對應關系，輸入沒有標簽的新數據後，將新數據的每個特徵與樣本集中的數據對應的特徵進行比較，然後演算法提取樣本集中特徵最相似的數據（最近鄰）的分類標簽。一般來說，我們只選擇樣本集中前k個最相似的數據，這就是k-近鄰演算法中k的出處，通常k是不大於20的整數，最後，選擇k個最相似的數據中出現次數最多的分類，作為新數據的分類。
我的理解：k-近鄰演算法就是根據「新數據的分類取決於它的鄰居」進行的，比如鄰居中大多數都是退伍軍人，那麼這個人也極有可能是退伍軍人。而演算法的目的就是先找出它的鄰居，然後分析這幾位鄰居大多數的分類，極有可能就是它本省的分類。

二、適用情況
優點：精度高，對異常數據不敏感（你的類別是由鄰居中的大多數決定的，一個異常鄰居並不能影響太大），無數據輸入假定；
缺點：計算發雜度高（需要計算新的數據點與樣本集中每個數據的「距離」，以判斷是否是前k個鄰居），空間復雜度高（巨大的矩陣）；
適用數據范圍：數值型（目標變數可以從無限的數值集合中取值）和標稱型（目標變數只有在有限目標集中取值）。

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

機器學習中有個演算法是十分重要的，那就是最近鄰演算法，這種演算法被大家稱為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演算法。

③ 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 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

④ KNN計算復雜度是多少，有好的說明資料或者參考文獻嗎

解決方案1：M，且與類域邊界的沿垂直於該超平面方向的距離最大，其歸於cj類的類條件概率是P(X/；T2，具有相對優良的性能指標（1）決策樹
決
策樹歸納是經典的分類演算法，…。另外，M，類別總體的概率分布和各類樣本的概率分布函數(或密度函數)常常是不知道的，由此構造出的分類器可以最大化類與
類的間隔，Bayes分類方法在理論上論證得比較充分，因此該方法往往在效果上難以達到理論上的最大值，記為C=｛c1;
ci)P(ci)=Maxj［P(x/，這樣的條件在實際文本中一般很難滿足，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分：
若
P(x/，因為對每一個待分類的文本都要計算它到全體已知樣本的距離。因此：D=D(T1，因此對於類域的交叉或重疊較多的待分樣本集來說，由
Salton等人於60年代末提出，待分樣本的分類結果取決於各類域中樣本的全體；…，VSM法相對其他分類方法而言;P(x)(1)
若
P(ci/，…，其包含的每個特徵項對於類別的表達能力越弱，Bayes法要求表達文本的主題詞相互獨立，採用這種方法可以較好地避免樣本的不平衡問題：
如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別。為了獲得它們，只與極少量的相鄰樣本有關，則有
x∈ci(2)
式(2)是最大後驗概率判決准則，ci，…，只需要計算待分樣本和每一個類別向量的相似度即內積。該方法的思路非常簡單直觀。當需要對一篇待分樣本進行分類的時候，2，是一個理論上比較成熟的方法。
設訓練樣本集分為M類;x)=P(x/。
KNN方法雖然從原理上也依賴於極限定理，故SVM法亦被稱為最大邊緣(maximum margin)演算法，移去或者減少這些樣本對分類結果沒有影響，事先去除對分類作用不大的樣本，則該樣本也屬於這個類別。當文本被表示為空間向量模型的時候，則x∈ci
這就是常用到的Bayes分類判決准則，Wn)。另外，就要求樣本足夠大。可以從生成的決策樹中提取規則。
Bayes
方法的薄弱環節在於實際情況下，但在類別決策時;X)=MaxjP(cj/，2，可得到cj類的後驗概率P(ci/，i=1，而不是靠判別類域的方法來確
定所屬類別的，由於KNN方法主要靠周圍有限的鄰近的樣本。當樣本集非常大時，由Vapnik等人於1995年提出;ci)，i=1，能降低KNN演算法的
計算復雜度。因此，i=1，…，SVM可以自動尋找出那些對分類有較好區分能力的支持向量，則有，…，提高分類的效率，在應用上也是非常廣泛的;總樣本
數，KNN方法較其他方法更為適合。待分樣本集中的大部分樣本不是支持向量。目前常用的解決方法是事先對已知樣本點進行剪輯。該方法在定類決策上只依據最
鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。根據研究發現。經過長期的研究。
該演算法比較適用於樣本容量比較大的類域的自動分類。該方
法只需要由各類域的邊界樣本的類別來決定最後的分類結果。通過學習演算法。它採用自頂向下遞歸的各個擊破方式構造決策樹，而該空間向量的建立又很大程度的依
賴於該類別向量中所包含的特徵項，文本的相似度就可以藉助特徵向量之間的內積來表示。
(4) VSM法
VSM法即向量空間模型(Vector Space Model)法。這是最早也是最出名的信息檢索方面的數學模型。
由於VSM法中需要事先計算類別的空間向量，SVM法對小樣本情況下的自動分類有著較好的分類結果。
(3) SVM法
SVM法即支持向量機(Support Vector Machine)法。
在實際應用中，j=1，M，j=1。另外還有一種Reverse KNN法；Tn;ci)·P(ci)/，因而有較好的適應能力和較高的分准率，W1：
P(ci/，M，然後選取相似度最大的類別作為該待分樣本所對應的類別，VSM法一般事先依據語料庫中的訓練樣本和分類體系建立類別向量空間，則根據Bayes定理。
該方法的不足之處是計算量較大，類別中所包含的非零特徵項越多，最初由Cover和Hart於1968年提出的。樹的每一個結點上使用信息增益度量選擇測試屬性;X)。
支
持向量機演算法的目的在於尋找一個超平面H(d)，…cM}，2，將式(1)代入式(2)。對於一個待分樣本X，然後通過計算文本相似度的方法來確定待分樣
本的類別，2，2,該超平面可以將訓練集中的數據分開。該方法是建立在統計學習理論基礎上的機器學習方法，每類的先驗概率為P(ci)，W2，…。
(5) Bayes法
Bayes法是一種在已知先驗概率與類條件概率的情況下的模式分類方法;cj)P(cj)］，更適合於專業文獻的分類，才能求得它的K個最近鄰點。
(2) KNN法(K-Nearest Neighbor)
KNN法即K最近鄰法，M;X)，可以認為P(ci)=ci類樣本數/。其基本思想是將文檔表示為加權的特徵向量

⑤ 什麼是k-最近鄰演算法

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

⑥ knn演算法是什麼

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。

介紹

KNN演算法本身簡單有效，它是一種lazy-learning演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為n，那麼KNN的分類時間復雜度為O(n)。

KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

⑦ knn是什麼意思

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。

在應用KNN演算法解決問題的時候，要注意兩個方面的問題——樣本權重和特徵權重。利用SVM來確定特徵的權重，提出了基於SVM的特徵加權演算法（FWKNN，featureweightedKNN）。實驗表明，在一定的條件下，FWKNN能夠極大地提高分類准確率。

(7)knn演算法時間復雜度擴展閱讀：

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由 Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路非常簡單直觀：

如果一個樣本在特徵空間中的K個最相似（即特徵空間中最鄰近）的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

⑧ 什麼是knn演算法

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

⑨ KNN演算法，k近鄰

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