1. 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演算法的優缺點
優點：
簡單，效果還不錯，適合多分類問題
缺點：
效率低（因為要計算預測樣本距離每個樣本點的距離，然後排序），效率會隨著樣本量的增加而降低。
2. 使用Node.js如何實現K最近鄰分類演算法
源於數據挖掘的一個作業， 這里用Node.js技術來實現一下這個機器學習中最簡單的演算法之一k-nearest-neighbor演算法(k最近鄰分類法)。
k-nearest-neighbor-classifier
還是先嚴謹的介紹下。急切學習法（eager learner）是在接受待分類的新元組之前就構造了分類模型，學習後的模型已經就緒，急著對未知的元組進行分類，所以稱為急切學習法，諸如決策樹歸納，貝葉斯分類等都是急切學習法的例子。惰性學習法（lazy learner）正好與其相反，直到給定一個待接受分類的新元組之後，才開始根據訓練元組構建分類模型，在此之前只是存儲著訓練元組，所以稱為惰性學習法，惰性學習法在分類進行時做更多的工作。
本文的knn演算法就是一種惰性學習法，它被廣泛應用於模式識別。knn基於類比學習，將未知的新元組與訓練元組進行對比，搜索模式空間，找出最接近未知元組的k個訓練元組，這里的k即是knn中的k。這k個訓練元祖就是待預測元組的k個最近鄰。
balabala了這么多，是不是某些同學想大喊一聲..speak Chinese! 還是來通俗的解釋下，然後再來看上面的理論應該會明白很多。小時候媽媽會指著各種各樣的東西教我們，這是小鴨子，這個紅的是蘋果等等，那我們哼哧哼哧的看著應答著，多次被教後再看到的時候我們自己就能認出來這些事物了。主要是因為我們在腦海像給這個蘋果貼了很多標簽一樣，不只是顏色這一個標簽，可能還有蘋果的形狀大小等等。這些標簽讓我們看到蘋果的時候不會誤認為是橘子。其實這些標簽就對應於機器學習中的特徵這一重要概念，而訓練我們識別的過程就對應於泛化這一概念。一台iphone戴了一個殼或者屏幕上有一道劃痕，我們還是能認得出來它，這對於我們人來說非常簡單，但蠢計算機就不知道怎麼做了，需要我們好好調教它，當然也不能過度調教2333，過度調教它要把其他手機也認成iphone那就不好了，其實這就叫過度泛化。
所以特徵就是提取對象的信息，泛化就是學習到隱含在這些特徵背後的規律，並對新的輸入給出合理的判斷。
我們可以看上圖，綠色的圓代表未知樣本，我們選取距離其最近的k個幾何圖形，這k個幾何圖形就是未知類型樣本的鄰居，如果k=3，我們可以看到有兩個紅色的三角形，有一個藍色的三正方形，由於紅色三角形所佔比例高，所以我們可以判斷未知樣本類型為紅色三角形。擴展到一般情況時，這里的距離就是我們根據樣本的特徵所計算出來的數值，再找出距離未知類型樣本最近的K個樣本，即可預測樣本類型。那麼求距離其實不同情況適合不同的方法，我們這里採用歐式距離。
綜上所述knn分類的關鍵點就是k的選取和距離的計算。
2. 實現
我的數據是一個xls文件，那麼我去npm搜了一下選了一個叫node-xlrd的包直接拿來用。
// node.js用來讀取xls文件的包
var xls = require('node-xlrd');
然後直接看文檔實例即可，把數據解析後插入到自己的數據結構里。
var data = [];// 將文件中的數據映射到樣本的屬性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 讀取文件
xls.open('data.xls', function(err,bk){
if(err) {console.log(err.name, err.message); return;}
var shtCount = bk.sheet.count;
for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
var sht = bk.sheets[sIdx],
rCount = sht.row.count,
cCount = sht.column.count;
for(var rIdx = 0; rIdx < rCount; rIdx++){
var item = {};
for(var cIdx = 0; cIdx < cCount; cIdx++){
item[map[cIdx]] = sht.cell(rIdx,cIdx);
}
data.push(item);
}
}
// 等文件讀取完畢後 執行測試
run();
});
然後定義一個構造函數Sample表示一個樣本，這里是把剛生成的數據結構里的對象傳入，生成一個新的樣本。
// Sample表示一個樣本
var Sample = function (object) {
// 把傳過來的對象上的屬性克隆到新創建的樣本上
for (var key in object)
{
// 檢驗屬性是否屬於對象自身
if (object.hasOwnProperty(key)) {
this[key] = object[key];
}
}
}
再定義一個樣本集的構造函數
// SampleSet管理所有樣本 參數k表示KNN中的kvar SampleSet = function(k) {
this.samples = [];
this.k = k;
};
// 將樣本加入樣本數組
SampleSet.prototype.add = function(sample) {
this.samples.push(sample);
}
然後我們會在樣本的原型上定義很多方法，這樣每個樣本都可以用這些方法。
// 計算樣本間距離 採用歐式距離
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {
for (var i in this.neighbors)
{
var neighbor = this.neighbors[i];
var a = neighbor.a - this.a;
var b = neighbor.b - this.b;
var c = neighbor.c - this.c;
var d = neighbor.d - this.d;
var e = neighbor.e - this.e;
var f = neighbor.f - this.f;
var g = neighbor.g - this.g;
var h = neighbor.h - this.h;
var i = neighbor.i - this.i;
var j = neighbor.j - this.j;
var k = neighbor.k - this.k;
// 計算歐式距離
neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
}
};
// 將鄰居樣本根據與預測樣本間距離排序
Sample.prototype.sortByDistance = function() {
this.neighbors.sort(function (a, b) {
return a.distance - b.distance;
});
};
// 判斷被預測樣本類別
Sample.prototype.guessType = function(k) {
// 有兩種類別 1和-1
var types = { '1': 0, '-1': 0 };
// 根據k值截取鄰居裡面前k個
for (var i in this.neighbors.slice(0, k))
{
var neighbor = this.neighbors[i];
types[neighbor.trueType] += 1;
}
// 判斷鄰居里哪個樣本類型多
if(types['1']>types['-1']){
this.type = '1';
} else {
this.type = '-1';
}
}
注意到我這里的數據有a-k共11個屬性，樣本有1和-1兩種類型，使用truetype和type來預測樣本類型和對比判斷是否分類成功。
最後是樣本集的原型上定義一個方法，該方法可以在整個樣本集里尋找未知類型的樣本，並生成他們的鄰居集，調用未知樣本原型上的方法來計算鄰居到它的距離，把所有鄰居按距離排序，最後猜測類型。
// 構建總樣本數組，包含未知類型樣本
SampleSet.prototype.determineUnknown = function() {
for (var i in this.samples)
{
// 如果發現沒有類型的樣本
if ( ! this.samples[i].type)
{
// 初始化未知樣本的鄰居
this.samples[i].neighbors = [];
// 生成鄰居集
for (var j in this.samples)
{
// 如果碰到未知樣本 跳過
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 計算所有鄰居與預測樣本的距離
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有鄰居按距離排序
this.samples[i].sortByDistance();
// 猜測預測樣本類型
this.samples[i].guessType(this.k);
}
}
};
最後分別計算10倍交叉驗證和留一法交叉驗證的精度。
留一法就是每次只留下一個樣本做測試集，其它樣本做訓練集。
K倍交叉驗證將所有樣本分成K份，一般均分。取一份作為測試樣本，剩餘K-1份作為訓練樣本。這個過程重復K次，最後的平均測試結果可以衡量模型的性能。
k倍驗證時定義了個方法先把數組打亂隨機擺放。
// helper函數 將數組里的元素隨機擺放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩餘測試代碼好寫，這里就不貼了。
測試結果為
用餘弦距離等計算方式可能精度會更高。
3. 總結
knn演算法非常簡單，但卻能在很多關鍵的地方發揮作用並且效果非常好。缺點就是進行分類時要掃描所有訓練樣本得到距離，訓練集大的話會很慢。
可以用這個最簡單的分類演算法來入高大上的ML的門，會有點小小的成就感。
3. 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'))
4. 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 演算法 是基於 距離 的一種機器學習演算法，需要計算測試點與樣本點之間的距離。因此，當數據量大的時候，計算量就會非常龐大，需要大量的存儲空間和計算時間。
另外，如果樣本數據分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會很低。因此，在實際應用中，要特別注意這一點。
（本節完。）
推薦閱讀：
決策樹演算法-理論篇-如何計算信息純度
決策樹演算法-實戰篇-鳶尾花及波士頓房價預測
樸素貝葉斯分類-理論篇-如何通過概率解決分類問題
樸素貝葉斯分類-實戰篇-如何進行文本分類
計算機如何理解事物的相關性-文檔的相似度判斷
5. 大數據演算法：分類演算法
KNN演算法，即K近鄰（K Nearest Neighbour）演算法，是一種基本的分類演算法。其主要原理是：對於一個需要分類的數據，將其和一組已經分類標注好的樣本集合進行比較，得到距離最近的K個樣本，K個樣本最多歸屬的類別，就是這個需要分類數據的類別。下面我給你畫了一個KNN演算法的原理圖。
圖中，紅藍綠三種顏色的點為樣本數據，分屬三種類別 、 、 。對於待分類點 ，計算和它距離最近的5個點（即K為5），這5個點最多歸屬的類別為 （4個點歸屬 ，1個點歸屬 ），那麼 的類別被分類為 。
KNN的演算法流程也非常簡單，請看下面的流程圖。
KNN演算法是一種非常簡單實用的分類演算法，可用於各種分類的場景，比如新聞分類、商品分類等，甚至可用於簡單的文字識別。對於新聞分類，可以提前對若干新聞進行人工標注，標好新聞類別，計算好特徵向量。對於一篇未分類的新聞，計算其特徵向量後，跟所有已標注新聞進行距離計算，然後進一步利用KNN演算法進行自動分類。
讀到這你肯定會問，如何計算數據的距離呢？如何獲得新聞的特徵向量呢？
KNN演算法的關鍵是要比較需要分類的數據與樣本數據之間的距離，這在機器學習中通常的做法是：提取數據的特徵值，根據特徵值組成一個n維實數向量空間（這個空間也被稱作特徵空間），然後計算向量之間的空間距離。空間之間的距離計算方法有很多種，常用的有歐氏距離、餘弦距離等。
對於數據 和 ，若其特徵空間為n維實數向量空間 ，即 ， ，則其歐氏距離計算公式為
這個歐式距離公式其實我們在初中的時候就學過，平面幾何和立體幾何里兩個點之間的距離，也是用這個公式計算出來的，只是平面幾何（二維幾何）里的n=2，立體幾何（三維幾何）里的n=3，而機器學習需要面對的每個數據都可能有n維的維度，即每個數據有n個特徵值。但是不管特徵值n是多少，兩個數據之間的空間距離的計算公式還是這個歐氏計算公式。大多數機器學習演算法都需要計算數據之間的距離，因此掌握數據的距離計算公式是掌握機器學習演算法的基礎。
歐氏距離是最常用的數據計算公式，但是在文本數據以及用戶評價數據的機器學習中，更常用的距離計算方法是餘弦相似度。
餘弦相似度的值越接近1表示其越相似，越接近0表示其差異越大，使用餘弦相似度可以消除數據的某些冗餘信息，某些情況下更貼近數據的本質。我舉個簡單的例子，比如兩篇文章的特徵值都是：「大數據」「機器學習」和「極客時間」，A文章的特徵向量為（3, 3, 3），即這三個詞出現次數都是3；B文章的特徵向量為（6, 6, 6），即這三個詞出現次數都是6。如果光看特徵向量，這兩個向量差別很大，如果用歐氏距離計算確實也很大，但是這兩篇文章其實非常相似，只是篇幅不同而已，它們的餘弦相似度為1，表示非常相似。
餘弦相似度其實是計算向量的夾角，而歐氏距離公式是計算空間距離。餘弦相似度更關注數據的相似性，比如兩個用戶給兩件商品的打分分別是（3, 3）和（4, 4），那麼兩個用戶對兩件商品的喜好是相似的，這種情況下，餘弦相似度比歐氏距離更合理。
我們知道了機器學習的演算法需要計算距離，而計算距離需要還知道數據的特徵向量，因此提取數據的特徵向量是機器學習工程師們的重要工作，有時候甚至是最重要的工作。不同的數據以及不同的應用場景需要提取不同的特徵值，我們以比較常見的文本數據為例，看看如何提取文本特徵向量。
文本數據的特徵值就是提取文本關鍵詞，TF-IDF演算法是比較常用且直觀的一種文本關鍵詞提取演算法。這種演算法是由TF和IDF兩部分構成。
TF是詞頻（Term Frequency），表示某個單詞在文檔中出現的頻率，一個單詞在一個文檔中出現的越頻繁，TF值越高。
詞頻：
IDF是逆文檔頻率（Inverse Document Frequency），表示這個單詞在所有文檔中的稀缺程度，越少文檔出現這個詞，IDF值越高。
逆文檔頻率：
TF與IDF的乘積就是TF-IDF。
所以如果一個詞在某一個文檔中頻繁出現，但在所有文檔中卻很少出現，那麼這個詞很可能就是這個文檔的關鍵詞。比如一篇關於原子能的技術文章，「核裂變」「放射性」「半衰期」等詞彙會在這篇文檔中頻繁出現，即TF很高；但是在所有文檔中出現的頻率卻比較低，即IDF也比較高。因此這幾個詞的TF-IDF值就會很高，就可能是這篇文檔的關鍵詞。如果這是一篇關於中國原子能的文章，也許「中國」這個詞也會頻繁出現，即TF也很高，但是「中國」也在很多文檔中出現，那麼IDF就會比較低，最後「中國」這個詞的TF-IDF就很低，不會成為這個文檔的關鍵詞。
提取出關鍵詞以後，就可以利用關鍵詞的詞頻構造特徵向量，比如上面例子關於原子能的文章，「核裂變」「放射性」「半衰期」這三個詞是特徵值，分別出現次數為12、9、4。那麼這篇文章的特徵向量就是（12, 9, 4），再利用前面提到的空間距離計算公式計算與其他文檔的距離，結合KNN演算法就可以實現文檔的自動分類。
貝葉斯公式是一種基於條件概率的分類演算法，如果我們已經知道A和B的發生概率，並且知道了B發生情況下A發生的概率，可以用貝葉斯公式計算A發生的情況下B發生的概率。事實上，我們可以根據A的情況，即輸入數據，判斷B的概率，即B的可能性，進而進行分類。
舉個例子：假設一所學校里男生佔60%，女生佔40%。男生總是穿長褲，女生則一半穿長褲一半穿裙子。假設你走在校園中，迎面走來一個穿長褲的學生，你能夠推斷出這個穿長褲學生是男生的概率是多少嗎？
答案是75%，具體演算法是：
這個演算法就利用了貝葉斯公式，貝葉斯公式的寫法是：
意思是A發生的條件下B發生的概率，等於B發生的條件下A發生的概率，乘以B發生的概率，除以A發生的概率。還是上面這個例子，如果我問你迎面走來穿裙子的學生是女生的概率是多少。同樣帶入貝葉斯公式，可以計算出是女生的概率為100%。其實這個結果我們根據常識也能推斷出來，但是很多時候，常識受各種因素的干擾，會出現偏差。比如有人看到一篇博士生給初中學歷老闆打工的新聞，就感嘆讀書無用。事實上，只是少見多怪，樣本量太少而已。而大量數據的統計規律則能准確反映事物的分類概率。
貝葉斯分類的一個典型的應用場合是垃圾郵件分類，通過對樣本郵件的統計，我們知道每個詞在郵件中出現的概率 ，我們也知道正常郵件概率 和垃圾郵件的概率 ，還可以統計出垃圾郵件中各個詞的出現概率 ，那麼現在一封新郵件到來，我們就可以根據郵件中出現的詞，計算 ，即得到這些詞出現情況下，郵件為垃圾郵件的概率，進而判斷郵件是否為垃圾郵件。
現實中，貝葉斯公式等號右邊的概率，我們可以通過對大數據的統計獲得，當有新的數據到來的時候，我們就可以帶入上面的貝葉斯公式計算其概率。而如果我們設定概率超過某個值就認為其會發生，那麼我們就對這個數據進行了分類和預測，具體過程如下圖所示。
訓練樣本就是我們的原始數據，有時候原始數據並不包含我們想要計算的維度數據，比如我們想用貝葉斯公式自動分類垃圾郵件，那麼首先要對原始郵件進行標注，需要標注哪些郵件是正常郵件、哪些郵件是垃圾郵件。這一類需要對數據進行標注才能進行的機器學習訓練也叫作有監督的機器學習。
6. 01 KNN演算法 - 概述
KNN演算法 全稱是K近鄰演算法 （K-nearst neighbors，KNN）
KNN是一種基本的機器學習演算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它 最接近的k個鄰近位置的樣本 來代替。
KNN是個相對比較簡單的演算法，比起之前提過的回歸演算法和分類演算法更容易。如果一個人從來沒有接觸過機器學習的演算法，拿到數據後最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然後你們發現我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。
KNN演算法即可以應用於 分類演算法 中，也可以應用於 回歸演算法 中。
KNN在做回歸和分類的主要區別，在於最後做預測時候的決策不同。在分類預測時，一般採用 多數表決法 。在做回歸預測時，一般使用 平均值法 。
多數表決法： 分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。
平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。
再舉個例子：
分別根據甜度和脆度兩個特徵來判斷食物的種類。
根據樣本我們普遍發現：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質。
不甜，比較脆的食物是蔬菜。
於是根據目標的樣本甜度和脆度兩個特徵，我們可以對其進行分類了。
k值的選擇:
先選一個較小的值，然後通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至於過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。
距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
決策規劃:
分類：多數表決法、加權多數表決法。
回歸：平均值法、加權平均值法。
加權多數表決法：
平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6
加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43
1、蠻力實現(brute)：
計算預測樣本到所有訓練集樣本的距離，然後選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特徵數多、樣本數多時，演算法的效率比較低。
2、KD樹 (kd_tree)：
首先對訓練數據進行建模，構建KD樹，然後根據建好的模型來獲取鄰近樣本數據。
後續內容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現要少檢索多少數據。
7. 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近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。