knn演算法演算法應用

❶ 用KNN演算法判斷知識掌握程度高低

KNN演算法既可以解決分類問題，也可以解決預測問題。
基礎思想：通過計算每個訓練樣例到待分類樣品的距離，取和待分類樣品距離最近的K個訓練樣例，K個樣品中哪個類別的訓練樣例佔多數，則待分類樣品就屬於哪個類別。

對於離散型因變數，從k個最近的已知類別樣本中挑選出頻率最高的類別用於未知樣本的判斷；對於連續型因變數，將k個最近的已知樣本均值用作未知樣本的預測。

k值過小，模型過擬合，例如k=1，未知樣本的類別將由最近的1個已知樣本點來決定，對於訓練數據來說，訓練誤差幾乎為0，對於測試數據來說，訓練誤差可能會很大，因為距離最近的1個已知樣本點可以是異常觀測值，也可以是正常觀測值。

k值過大，模型欠擬合，例如k=N，未知樣本的類別將由所有已知樣本中頻數最高的類別決定，不管是訓練集還是測試集被判為一種類別，易欠擬合。

一般利用多重交叉驗證得到平均誤差最小的k值。還有一種方法是設置k近鄰樣本的投票權重，對已知樣本距離較遠的設置權重低一些，較近的設置權重高一些，通常將權重設置為距離的倒數。

點與點之間的距離即相似性，一般用歐氏距離，即L2范數
或者曼哈頓距離，即L1范數
或者餘弦相似度cosα
或者傑卡德相似系數，即J=|A∩B|/|A∪B|

在使用距離方法來度量相似性時，要使所有變數數值化（通過啞變數或者重編碼為0,1,2），而且採用標准化方法進行歸一化，防止數值變數的量綱影響

近鄰搜尋方法包括：暴力搜尋法（全表掃描），kd樹（k為訓練集中包含的變數個數，而非KNN中的k個鄰近樣本，先用所有已知類別的樣本點構造一棵樹，再將未知類別應用在樹上），球樹搜尋（將kd樹中的超矩形體換成了超球體）。

優點：
精度高，對異常值不敏感，無數據輸入假定；
KNN 是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練；
KNN 理論簡單，容易實現。

缺點：
對於樣本容量大的數據集計算量比較大，即計算復雜度高；
必須保存全部數據集，即空間復雜度高；
KNN 每一次分類都會重新進行一次全局運算；
樣本不平衡時，預測偏差比較大。如：某一類的樣本比較少，而其它類樣本比較多；
K 值大小的選擇；
KNN 無法給出基礎結構信息，無法知曉平均實例樣本與典型實例樣本具有什麼特徵，即無法給出數據的內在含義。

應用領域：
文本分類；模式識別；聚類分析；多分類領域。

行表示每一個被觀測的學生，
STG：在目標學科上的學習時長，
SCG：重復次數
STR：相關科目的學習時長
LPR：相關科目的考試成績
PEG：目標科目的考試成績
（以上指標均已標准化）
UNG：對知識的掌握程度高低

利用多重交叉驗證獲取符合數據的理想k值

經過10重交叉驗證，最佳的近鄰個數為6

weights=uniform，表示投票權重一樣
=distance，表示投票權重與距離成反比

從主對角線看，絕大多數樣本被正確分類

通過熱力圖可視化混淆矩陣

行代表真實地，列代表預測的，主對角線上的顏色比較深，說明絕大多數樣本是被正確分類的。

下面得到模型在測試集上的預測准確率：

整體預測准確率為91.09%，要得到每個類別的准確率：

第一列為預測精度，即」預測正確的類別個數/該類別預測的所有個數"
第二列為預測覆蓋率，即」預測正確的類別個數/該類別實際的所有個數"
第三列為前兩列的加權結果
第四列為類別實際的樣本個數

對於預測問題的解決同決策樹中一樣，用MSE衡量

❷ knn演算法是什麼

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

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

介紹

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

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