文本分類演算法knn
① R語言-KNN演算法
1、K最近鄰(k-NearestNeighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
2、KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
3、KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。
簡言之，就是將未標記的案例歸類為與它們最近相似的、帶有標記的案例所在的類 。
原理及舉例
工作原理：我們知道樣本集中每一個數據與所屬分類的對應關系，輸入沒有標簽的新數據後，將新數據與訓練集的數據對應特徵進行比較，找出「距離」最近的k（通常k<20）數據，選擇這k個數據中出現最多的分類作為新數據的分類。
演算法描述
1、計算已知數據集中的點與當前點的距離
2、按距離遞增次序排序
3、選取與當前數據點距離最近的K個點
4、確定前K個點所在類別出現的頻率
5、返回頻率最高的類別作為當前類別的預測
距離計算方法有"euclidean"（歐氏距離）,」minkowski」（明科夫斯基距離）, "maximum"（切比雪夫距離）, "manhattan"（絕對值距離）,"canberra"（蘭式距離）, 或 "minkowski"（馬氏距離）等
Usage
knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)
Arguments
train
matrix or data frame of training set cases.
test
matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case.
cl
factor of true classifications of training set
k
number of neighbours considered.
l
minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even
ifkis increased by ties.)
prob
If this is true, the proportion of the votes for the
winning class are returned as attributeprob.
use.all
controls handling of ties. If true, all distances equal
to thekth largest are
included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.
kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))
參數：
formula A formula object.
train Matrix or data frame of training set cases.
test Matrix or data frame of test set cases.
na.action A function which indicates what should happen when the data contain 』NA』s.
k Number of neighbors considered.
distance Parameter of Minkowski distance.
kernel Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".
ykernel Window width of an y-kernel, especially for prediction of ordinal classes.
scale Logical, scale variable to have equal sd.
contrasts A vector containing the 』unordered』 and 』ordered』 contrasts to use
kknn的返回值如下：
fitted.values Vector of predictions.
CL Matrix of classes of the k nearest neighbors.
W Matrix of weights of the k nearest neighbors.
D Matrix of distances of the k nearest neighbors.
C Matrix of indices of the k nearest neighbors.
prob Matrix of predicted class probabilities.
response Type of response variable, one of continuous, nominal or ordinal.
distance Parameter of Minkowski distance.
call The matched call.
terms The 』terms』 object used.
iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)
library（kknn）
data（iris）
dim(iris)
m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))
建立訓練數據集
data.train<-iris[-val,]
建立測試數據集
data.test<-iris[val,]
調用kknn 之前首先定義公式
formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width
iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")
summary(iris.kknn)
# 獲取fitted.values
fit <- fitted(iris.kknn)
# 建立表格檢驗判類准確性
table(iris.valid$Species, fit)
# 繪畫散點圖，k-nearest neighbor用紅色高亮顯示
pcol <- as.character(as.numeric(iris.valid$Species))
pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]
二、R語言knn演算法
install.packages("class")
library(class)
對於新的測試樣例基於距離相似度的法則，確定其K個最近的鄰居，在K個鄰居中少數服從多數
確定新測試樣例的類別
1、獲得數據
2、理解數據
對數據進行探索性分析，散點圖
如上例
3、確定問題類型，分類數據分析
4、機器學習演算法knn
5、數據處理，歸一化數據處理
normalize <- function(x){
num <- x - min(x)
denom <- max(x) - min(x)
return(num/denom)
}
iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))
summary(iris_norm)
6、訓練集與測試集選取
一般按照3:1的比例選取
方法一、set.seed(1234)
ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))
iris_train <-iris[ind==1, 1:4]
iris_test <-iris[ind==2, 1:4]
train_label <-iris[ind==1, 5]
test_label <-iris[ind==2, 5]
方法二、
ind<-sample(1:150,50)
iris_train<-iris[-ind,]
iris_test<-iris[ind,1:4]
iris_train<-iris[-ind,1:4]
train_label<-iris[-ind,5]
test_label<-iris[ind,5]
7、構建KNN模型
iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)
8、模型評價
交叉列聯表法
table（test_label,iris_pred)
實例二
數據集
http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data
導入數據
dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)
names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')
table(wdbc.data$Diagnosis)## M = malignant, B = benign
wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))
② KNN庫簡介
機器學習經典庫scikit-learn中的sklearn.neighbors包集成了近鄰法相關的演算法，KNN分類樹演算法使用KNeighborsClassifier，回歸樹使用KNeighborsRegressor。除此之外，還有KNN的擴展，即限定半徑最近鄰分類樹RadiusNeighborsClassifier和限定半徑最近鄰回歸樹RadiusNeighborsRegressor，以及最近質心分類演算法NearestCentroid。
在這些演算法中，KNN分類和回歸的類參數完全一樣。限定半徑最近鄰法分類和回歸的類的主要參數也和KNN基本一樣。比較特別是的最近質心分類演算法，由於它是直接選擇最近質心來分類，所以僅有兩個參數，距離度量和特徵選擇距離閾值。
限定半徑最近鄰演算法，即樣本中某系類別的樣本非常的少，甚至少於K，這導致稀有類別樣本在找K個最近鄰的時候，會把距離其實較遠的其他樣本考慮進來，而導致預測不準確。為了解決這個問題，我們限定最近鄰的一個最大距離，也就是說，我們只在一個距離范圍內搜索所有的最近鄰，這避免了上述問題。這個距離我們一般稱為限定半徑。
最近質心演算法首先把樣本按輸出類別歸類。對於第 L類的Cl個樣本。它會對這Cl個樣本的n維特徵中每一維特徵求平均值，最終該類別所有維度的n個平均值形成所謂的質心點。對於樣本中的所有出現的類別，每個類別會最終得到一個質心點。當我們做預測時，僅僅需要比較預測樣本和這些質心的距離，最小的距離對於的質心類別即為預測的類別。這個演算法通常用在文本分類處理上。
KNN的主要優點有：
1） 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸
2） 可用於非線性分類
3） 訓練時間復雜度比支持向量機之類的演算法低，僅為O(n)
4） 和樸素貝葉斯之類的演算法比，對數據沒有假設，准確度高，對異常點不敏感
5） 由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合
6）該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分
KNN的主要缺點有：
1）計算量大，尤其是特徵數非常多的時候
2）樣本不平衡的時候，對稀有類別的預測准確率低
3）KD樹，球樹之類的模型建立需要大量的內存
4）使用懶散學習方法，基本上不學習，導致預測時速度比起邏輯回歸之類的演算法慢
5）相比決策樹模型，KNN模型可解釋性不強
③ 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 演算法 是基於 距離 的一種機器學習演算法，需要計算測試點與樣本點之間的距離。因此，當數據量大的時候，計算量就會非常龐大，需要大量的存儲空間和計算時間。
另外，如果樣本數據分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會很低。因此，在實際應用中，要特別注意這一點。
（本節完。）
推薦閱讀：
決策樹演算法-理論篇-如何計算信息純度
決策樹演算法-實戰篇-鳶尾花及波士頓房價預測
樸素貝葉斯分類-理論篇-如何通過概率解決分類問題
樸素貝葉斯分類-實戰篇-如何進行文本分類
計算機如何理解事物的相關性-文檔的相似度判斷
④ 文本分類方法有哪些
文本分類問題： 給定文檔p（可能含有標題t），將文檔分類為n個類別中的一個或多個
文本分類應用： 常見的有垃圾郵件識別，情感分析
文本分類方向： 主要有二分類，多分類，多標簽分類
文本分類方法： 傳統機器學習方法（貝葉斯，svm等），深度學習方法（fastText，TextCNN等）
本文的思路： 本文主要介紹文本分類的處理過程，主要哪些方法。致力讓讀者明白在處理文本分類問題時應該從什麼方向入手，重點關注什麼問題，對於不同的場景應該採用什麼方法。
文本分類的處理大致分為 文本預處理 、文本 特徵提取 、 分類模型構建 等。和英文文本處理分類相比，中文文本的預處理是關鍵技術。
針對中文文本分類時，很關鍵的一個技術就是中文分詞。特徵粒度為詞粒度遠遠好於字粒度，其大部分分類演算法不考慮詞序信息，基於字粒度的損失了過多的n-gram信息。下面簡單總結一下中文分詞技術:基於字元串匹配的分詞方法、基於理解的分詞方法和基於統計的分詞方法 [1]。
1，基於字元串匹配的分詞方法：
過程：這是 一種基於詞典的中文分詞 ，核心是首先建立統一的詞典表，當需要對一個句子進行分詞時，首先將句子拆分成多個部分，將每一個部分與字典一一對應，如果該詞語在詞典中，分詞成功，否則繼續拆分匹配直到成功。
核心： 字典，切分規則和匹配順序是核心。
分析：優點是速度快，時間復雜度可以保持在O（n）,實現簡單，效果尚可；但對歧義和未登錄詞處理效果不佳。
2， 基於理解的分詞方法：基於理解的分詞方法是通過讓計算機模擬人對句子的理解 ，達到識別詞的效果。其基本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現象。它通常包括三個部分：分詞子系統、句法語義子系統、總控部分。在總控部分的協調下，分詞子系統可以獲得有關詞、句子等的句法和語義信息來對分詞歧義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。由於漢語語言知識的籠統、復雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基於理解的分詞系統 還處在試驗階段 。
3，基於統計的分詞方法:
過程：統計學認為分詞是一個 概率最大化問題 ，即拆分句子，基於語料庫，統計 相鄰的字組成的詞語出現的概率 ，相鄰的詞出現的次數多，就出現的概率大， 按照概率值進行分詞 ，所以一個完整的語料庫很重要。
主要的統計模型有： N元文法模型（N-gram），隱馬爾可夫模型（Hidden Markov Model ，HMM），最大熵模型（ME），條件隨機場模型（Conditional Random Fields，CRF）等。
1， 分詞 ： 中文任務分詞必不可少，一般使用jieba分詞，工業界的翹楚。
2， 去停用詞：建立停用詞字典 ，目前停用詞字典有2000個左右，停用詞主要包括一些副詞、形容詞及其一些連接詞。通過維護一個停用詞表，實際上是一個特徵提取的過程，本質 上是特徵選擇的一部分。
3， 詞性標注 ： 在分詞後判斷詞性（動詞、名詞、形容詞、副詞…），在使用jieba分詞的時候設置參數就能獲取。
文本分類的核心都是如何從文本中抽取出能夠體現文本特點的關鍵特徵，抓取特徵到類別之間的映射。 所以特徵工程很重要，可以由四部分組成：
1，基於詞袋模型的特徵表示：以詞為單位（Unigram）構建的詞袋可能就達到幾萬維，如果考慮二元片語（Bigram）、三元片語（Trigram）的話詞袋大小可能會有幾十萬之多，因此基於詞袋模型的特徵表示通常是極其稀疏的。
（1）詞袋特徵的方法有三種：
（2）優缺點：
2，基於embedding的特徵表示： 通過詞向量計算文本的特徵。（主要針對短文本）
4，基於任務本身抽取的特徵：主要是針對具體任務而設計的，通過我們對數據的觀察和感知，也許能夠發現一些可能有用的特徵。有時候，這些手工特徵對最後的分類效果提升很大。舉個例子，比如對於正負面評論分類任務，對於負面評論，包含負面詞的數量就是一維很強的特徵。
5，特徵融合：對於特徵維數較高、數據模式復雜的情況，建議用非線性模型（如比較流行的GDBT, XGBoost）；對於特徵維數較低、數據模式簡單的情況，建議用簡單的線性模型即可（如LR）。
6，主題特徵：
LDA（文檔的話題）： 可以假設文檔集有T個話題，一篇文檔可能屬於一個或多個話題，通過LDA模型可以計算出文檔屬於某個話題的概率，這樣可以計算出一個DxT的矩陣。LDA特徵在文檔打標簽等任務上表現很好。
LSI（文檔的潛在語義）： 通過分解文檔-詞頻矩陣來計算文檔的潛在語義，和LDA有一點相似，都是文檔的潛在特徵。
這部分不是重點，傳統機器學習演算法中能用來分類的模型都可以用，常見的有：NB模型，隨機森林模型（RF），SVM分類模型，KNN分類模型，神經網路分類模型。
這里重點提一下貝葉斯模型，因為工業用這個模型用來識別垃圾郵件[2]。
1，fastText模型： fastText 是word2vec 作者 Mikolov 轉戰 Facebook 後16年7月剛發表的一篇論文： Bag of Tricks for Efficient Text Classification [3]。
模型結構：
改進：注意力（Attention）機制是自然語言處理領域一個常用的建模長時間記憶機制，能夠很直觀的給出每個詞對結果的貢獻，基本成了Seq2Seq模型的標配了。實際上文本分類從某種意義上也可以理解為一種特殊的Seq2Seq，所以考慮把Attention機制引入近來。
過程：
利用前向和後向RNN得到每個詞的前向和後向上下文的表示：
詞的表示變成詞向量和前向後向上下文向量連接起來的形式：
模型顯然並不是最重要的： 好的模型設計對拿到好結果的至關重要，也更是學術關注熱點。但實際使用中，模型的工作量占的時間其實相對比較少。雖然再第二部分介紹了5種CNN/RNN及其變體的模型，實際中文本分類任務單純用CNN已經足以取得很不錯的結果了，我們的實驗測試RCNN對准確率提升大約1%，並不是十分的顯著。最佳實踐是先用TextCNN模型把整體任務效果調試到最好，再嘗試改進模型。
理解你的數據： 雖然應用深度學習有一個很大的優勢是不再需要繁瑣低效的人工特徵工程，然而如果你只是把他當做一個黑盒，難免會經常懷疑人生。一定要理解你的數據，記住無論傳統方法還是深度學習方法，數據 sense 始終非常重要。要重視 badcase 分析，明白你的數據是否適合，為什麼對為什麼錯。
超參調節： 可以參考 深度學習網路調參技巧 - 知乎專欄
一定要用 dropout： 有兩種情況可以不用：數據量特別小，或者你用了更好的正則方法，比如bn。實際中我們嘗試了不同參數的dropout，最好的還是0.5，所以如果你的計算資源很有限，默認0.5是一個很好的選擇。
未必一定要 softmax loss： 這取決與你的數據，如果你的任務是多個類別間非互斥，可以試試著訓練多個二分類器，也就是把問題定義為multi lable 而非 multi class，我們調整後准確率還是增加了>1%。
類目不均衡問題： 基本是一個在很多場景都驗證過的結論：如果你的loss被一部分類別dominate，對總體而言大多是負向的。建議可以嘗試類似 booststrap 方法調整 loss 中樣本權重方式解決。
避免訓練震盪： 默認一定要增加隨機采樣因素盡可能使得數據分布iid，默認shuffle機制能使得訓練結果更穩定。如果訓練模型仍然很震盪，可以考慮調整學習率或 mini_batch_size。
知乎的文本多標簽分類比賽，給出第一第二名的介紹網址：
NLP大賽冠軍總結：300萬知乎多標簽文本分類任務(附深度學習源碼)
2017知乎看山杯 從入門到第二
⑤ knn和kmeans的區別
knn屬於監督學習,類別是已知的,通過對已知分類的數據進行訓練和學習,找到這些不同類的特徵,再對未分類的數據進行分類。kmeans屬於非監督學習,事先不知道數據會分為幾類,通過聚類分析將數據聚合成幾個群體。
knn和kmeans的區別
1.KNN演算法是分類演算法，分類演算法肯定是需要有學習語料，然後通過學習語料的學習之後的模板來匹配我們的測試語料集，將測試語料集合進行按照預先學習的語料模板來分類
2Kmeans演算法是聚類演算法，聚類演算法與分類演算法最大的區別是聚類演算法沒有學習語料集合。
K-means演算法是聚類分析中使用最廣泛的演算法之一。它把n個對象根據他們的屬性分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。
Kmeans演算法的缺陷
聚類中心的個數K 需要事先給定，但在實際中這個 K 值的選定是非常難以估計的，很多時候，事先並不知道給定的數據集應該分成多少個類別才最合適
Kmeans需要人為地確定初始聚類中心，不同的初始聚類中心可能導致完全不同的聚類結果。(可以使用Kmeans++演算法來解決)
針對上述第2個缺陷，可以使用Kmeans++演算法來解決
K-Means ++ 演算法
k-means++演算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠。
從輸入的數據點集合中隨機選擇一個點作為第一個聚類中心
對於數據集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)
選擇一個新的數據點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的概率較大
重復2和3直到k個聚類中心被選出來
利用這k個初始的聚類中心來運行標準的k-means演算法
從上面的演算法描述上可以看到，演算法的關鍵是第3步，如何將D(x)反映到點被選擇的概率上，一種演算法如下：
先從我們的資料庫隨機挑個隨機點當「種子點」
對於每個點，我們都計算其和最近的一個「種子點」的距離D(x)並保存在一個數組里，然後把這些距離加起來得到Sum(D(x))。
然後，再取一個隨機值，用權重的方式來取計算下一個「種子點」。這個演算法的實現是，先取一個能落在Sum(D(x))中的隨機值Random，然後用Random -= D(x)，直到其<=0，此時的點就是下一個「種子點」。
重復2和3直到k個聚類中心被選出來
利用這k個初始的聚類中心來運行標準的k-means演算法
⑥ 文本分類器（基於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
⑦ 什麼叫做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值的方法是自助法。
⑧ 用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方法較其他方法更為適合。