knn最近鄰演算法公式

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. 簡單數字識別(knn演算法)

knn演算法，即k-NearestNeighbor，後面的nn意思是最近鄰的意思，前面的k是前k個的意思，就是找到前k個離得最近的元素

離得最近這個詞具體實現有很多種，我使用的是歐式幾何中的距離公式

二維中兩點x(x1,y1),y(x2,y2)間距離公式為sqrt( (x1-x2)^2+(y1-y2)^2 )

推廣到n維就是

x(x1,x2, … ,xn),y(y1,y2, … ,yn)

sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)

knn演算法是要計算距離的，也就是數字之間的運算，而圖像是png，jpg這種格式，並不是數字也不能直接參與運算，所以我們需要進行一下轉換

如圖所示一個數字8，首先要確定的是這一步我做的是一個最簡單的轉換，因為我假定背景和圖之間是沒有雜物的，而且整個圖只有一個數字（0-9）如果遇到其他情況，比如背景色不純或者有其他干擾圖像需要重新設計轉換函數

接下來就是最簡單的轉換，將圖片白色部分（背景）變0，有圖像的部分變1。轉換後的大小要合適，太小會影響識別准確度，太大會增加計算量。所以我用的是書上的32*32，轉換後結果如圖所示

這樣一來，圖片就變成了能進行計算的數字了。

接下來我們需要創建一個庫，這個庫裡面存著0-9這些數字的各種類似上圖的實例。因為我們待識別的圖像要進行對比，選出前k個最近的，比較的對象就是我們的庫。假定庫中有0-9十個數字，每個數字各有100個這種由0和1表示的實例，那麼我們就有了一共1000個實例。

最後一步就是進行對比，利用開頭說的歐式幾何距離計算公式，首先這個32*32的方陣要轉換成一個1*1024的1024維坐標表示，然後拿這個待識別的圖像和庫中的1000個實例進行距離計算，選出前k個距離最近的。比如50個，這50個裡面出現次數最多的數字除以50就是結果數字的概率。比如50個裡面數字8出現40次，那麼待識別數字是8的可能性就是40/50 = 80%

個人理解：

只能識別單個數字，背景不能有干擾。如果想多數字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉01的方法。

數字識別非常依賴庫中的圖像，庫中的圖像的樣子嚴重影響圖像的識別（因為我們是和庫中的一一對比找出距離最近的前k個），所以數字的粗細，高低，胖瘦等待都是決定性因素，建庫時一定全面考慮數字的可能樣子

計算量比較大，待識別圖像要和庫中所有實例一一計算，如果使用32*32，就已經是1024維了。如果庫中有1000個，那就是1024維向量之間的1000次計算，圖像更清晰，庫更豐富只會使計算量更大

對於其他可以直接計算距離的數值型問題，可以用歐式距離，也可以用其他能代表距離的計算公式，對於非數值型的問題需要進行合適的轉換，轉換方式很重要，我覺得首先信息不能丟失，其次要精確不能模糊，要實現圖片轉換前後是一對一的關系

參考資料：機器學習實戰 [美] Peter Harrington 人民郵電出版社

python源碼

import numpy

import os

from PIL import Image

import heapq

from collections import Counter

def pictureconvert(filename1,filename2,size=(32,32)):

    #filename1待識別圖像，filename2 待識別圖像轉換為01txt文件輸出，size圖像大小，默認32*32

    image_file = Image.open(filename1)

    image_file = image_file.resize(size)

    width,height = image_file.size

    f1 = open(filename1,'r')

    f2 = open(filename2,'w')

    for i in range(height):

        for j in range(width):

            pixel = image_file.getpixel((j,i))

            pixel = pixel[0] + pixel[1] + pixel[2]

            if(pixel == 0):

                pixel = 0

            elif(pixel != 765 and pixel != 0):

                pixel = 1

            # 0代表黑色（無圖像），255代表白色（有圖像）

            # 0/255 = 0,255/255 = 1

            f2.write(str(pixel))

            if(j == width-1):

                f2.write('\n')

    f1.close()

    f2.close()

def imgvector(filename):

    #filename將待識別圖像的01txt文件轉換為向量

    vector = numpy.zeros((1,1024),numpy.int)

    with open(filename) as f:

        for i in range(0,32):

            linestr = f.readline()

            for j in range(0,32):

                vector[0,32*i+j] = int(linestr[j])

    return  vector

def compare(filename1,filename2):

    #compare直接讀取資源庫識別

    #filename1資源庫目錄，filename2 待識別圖像01txt文檔路徑

    trainingfilelist = os.listdir(filename1)

    m = len(trainingfilelist)

    labelvector = []

    trainingmatrix = numpy.zeros((m, 1024), numpy.int8)

    for i in range(0,m):

        filenamestr = trainingfilelist[i]

        filestr = filenamestr.split('.')[0]

        classnumber = int(filestr.split('_')[0])

        labelvector.append(classnumber)

        trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)

    textvector = imgvector(filename2)

    resultdistance = numpy.zeros((1,m))

    result = []

    for i in range(0,m):

        resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])

    resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)

    for i in resultindices:

        result.append(labelvector[i])

    number = Counter(result).most_common(1)

    print('此數字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))

def distinguish(filename1,filename2,filename3,size=(32,32)):

    # filename1 png，jpg等格式原始圖像路徑，filename2 原始圖像轉換成01txt文件路徑，filename3 資源庫路徑

    pictureconvert(filename1,filename2,size)

    compare(filename3,filename2)

url1 = "/Users/wang/Desktop/number.png"

url2 = "/Users/wang/Desktop/number.txt"

traininglibrary = "/Users/wang/Documents/trainingDigits"

distinguish(url1,url2,traininglibrary)

3. K-近鄰演算法 KNN

K值選擇問題 ，李航博士的一書「統計學習方法」上所說：

近似誤差（train loss）：

估計誤差（test loss）：

 在實際應用中，K值一般取一個比較小的數值，例如採用交叉驗證法（簡單來說，就是把訓練數據在分成兩組:訓練集和驗證集）來選擇最優的K值。

 例如：將數據分成4份，其中一份作為驗證集。然後經過4次(組)的測試，每次都更換不同的驗證集。即得到4組模型的結果，取平均值作為最終結果。又稱4折交叉驗證。

 據KNN每次需要預測一個點時，我們都需要計算訓練數據集里每個點到這個點的距離，然後選出距離最近的k個點進行投票。當數據集很大時，這個計算成本非常高，針對N個樣本，D個特徵的數據集，其演算法復雜度為O(DN ² )。

在構建kd樹時，有2個關鍵問題：
（1）選擇向量的哪一維進行劃分? 隨機選擇某一維或按順序選擇，但是更好的方法應該是在數據比較分散的那一維進行劃分（分散的程度可以根據方差來衡量）。
（2）如何劃分數據? 好的劃分方法可以使構建的樹比較平衡，可以每次選擇中位數來進行劃分。
構造方法

  給定一個二維空間數據集：T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}，構造一個平衡kd樹。

 優點：

 缺點：

4. kNN（k-NearestNeighbor）演算法

參考《數據挖掘10大演算法》對kNN演算法進行基本總結，附有一個Python3的簡例。

基本思想
從訓練集中找出 k 個最接近測試對象的訓練對象，再從這 k 個對象中找出居於主導的類別，將其賦給測試對象。

定位
由於這種總體占優的決策模式，對於類域的交叉、重疊較多的或者多模型、多標簽的待分樣本集來說，kNN方法較其他方法更為適合。kNN演算法屬於有監督學習的分類演算法。

避開了兩個問題
（1）分類時對象之間不可能完全匹配（kNN方法計算的是對象之間的距離）；
（2）具有相同屬性的對象有不同的類別（kNN方法依據總體占優的類別進行決策，而不是單一對象的類別進行決策）。

需要考慮幾個關鍵要素
（1）訓練集；
（2）用於計算對象之間臨近的程度或者其他相似的指標；
（3）最近鄰的個數 k；
（4）基於 k 個最近鄰及其類別對目標對象類別進行判定的方法。

kNN方法很容易理解和實現，在一定條件下，其分類錯誤率不會超過最優貝葉斯錯誤率的兩倍。一般情況下，kNN方法的錯誤率會逐漸收斂到最優貝葉斯錯誤率，可以用作後者的近似。

基本演算法

演算法的存儲復雜度為O(n)，時間復雜度為O(n)，其中 n 為訓練對象的數量。

影響kNN演算法性能的幾個關鍵因素
（1）k 值的選擇；
如果 k 值選得過小，結果就會對雜訊點特別敏感；k 值選得過大就會使得近鄰中包含太多別的類的點。最佳 k 值的估計可以使用交叉驗證的方法。通常，使用 k=1會有一個比較好的結果（特別是對於小數據集的情況）。但是，在樣本很充足的情況下，選擇較大的 k 值可以提高抗噪能力。

（2）類別決策時的綜合方法；
對目標對象的類別進行決策，最簡單的就是使用總體占優方法（簡單投票，票數最多的一類勝出）。稍微復雜一點，考慮近鄰中每個點與目標對象的距離不同，對決策的份量進行加權考慮。

（3）距離測量標準的選擇。
距離測量的標准一般選擇 歐幾里得距離 或者 曼哈頓距離 。

簡單例子

5. 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'))

6. K-近鄰演算法（KNN）

簡單地說，K-近鄰演算法採用測量不同特徵值之間的距離方法進行分類。

歐氏距離是最常見的距離度量，衡量的是多維空間中各個點之間的絕對距離。公式如下：

身高、體重、鞋子尺碼數據對應性別

導包，機器學習的演算法KNN、數據鳶尾花

獲取訓練樣本 datasets.load_iris()

畫圖研究前兩個特徵和分類之間的關系（二維散點圖只能展示兩個維度）

第二步預測數據：所預測的數據，自己創造，就是上面所顯示圖片的背景點

生成預測數據

對數據進行預測

ocr 光學字元識別（Optical Character Recognition） 我們先做一個基礎班：識別數字

7. knn是什麼意思

knn是鄰近演算法，或者說K最鄰近分類演算法，全稱為K-NearestNeighbor，是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，是K個最近的鄰居的意思，說的是每個樣本都可以用最接近的K個鄰近值來代表。近鄰演算法是將數據集合中每一個記錄進行分類的方法。

knn演算法的核心思想：

如果一個樣本在特徵空間中的K個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

8. 大數據演算法：分類演算法

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%。其實這個結果我們根據常識也能推斷出來，但是很多時候，常識受各種因素的干擾，會出現偏差。比如有人看到一篇博士生給初中學歷老闆打工的新聞，就感嘆讀書無用。事實上，只是少見多怪，樣本量太少而已。而大量數據的統計規律則能准確反映事物的分類概率。

貝葉斯分類的一個典型的應用場合是垃圾郵件分類，通過對樣本郵件的統計，我們知道每個詞在郵件中出現的概率 ，我們也知道正常郵件概率 和垃圾郵件的概率 ，還可以統計出垃圾郵件中各個詞的出現概率 ，那麼現在一封新郵件到來，我們就可以根據郵件中出現的詞，計算 ，即得到這些詞出現情況下，郵件為垃圾郵件的概率，進而判斷郵件是否為垃圾郵件。

現實中，貝葉斯公式等號右邊的概率，我們可以通過對大數據的統計獲得，當有新的數據到來的時候，我們就可以帶入上面的貝葉斯公式計算其概率。而如果我們設定概率超過某個值就認為其會發生，那麼我們就對這個數據進行了分類和預測，具體過程如下圖所示。

訓練樣本就是我們的原始數據，有時候原始數據並不包含我們想要計算的維度數據，比如我們想用貝葉斯公式自動分類垃圾郵件，那麼首先要對原始郵件進行標注，需要標注哪些郵件是正常郵件、哪些郵件是垃圾郵件。這一類需要對數據進行標注才能進行的機器學習訓練也叫作有監督的機器學習。

9. 人工智慧十大演算法

人工智慧十大演算法如下

線性回歸（Linear Regression）可能是最流行的機器學習演算法。線性回歸就是要找一條直線，並且讓這條直線盡可能地擬合散點圖中的數據點。它試圖通過將直線方程與該數據擬合來表示自變數（x值）和數值結果（y值）。然後就可以用這條線來預測未來的值！

邏輯回歸（Logistic regression）與線性回歸類似，但它是用於輸出為二進制的情況（即，當結果只能有兩個可能的值）。對最終輸出的預測是一個非線性的S型函數，稱為logistic function, g()。

決策樹（Decision Trees）可用於回歸和分類任務。

樸素貝葉斯（Naive Bayes）是基於貝葉斯定理。它測量每個類的概率，每個類的條件概率給出x的值。這個演算法用於分類問題，得到一個二進制「是/非」的結果。看看下面的方程式。

支持向量機（Support Vector Machine，SVM）是一種用於分類問題的監督演算法。支持向量機試圖在數據點之間繪制兩條線，它們之間的邊距最大。為此，我們將數據項繪制為n維空間中的點，其中，n是輸入特徵的數量。在此基礎上，支持向量機找到一個最優邊界，稱為超平面（Hyperplane），它通過類標簽將可能的輸出進行最佳分離。

K-最近鄰演算法（K-Nearest Neighbors，KNN）非常簡單。KNN通過在整個訓練集中搜索K個最相似的實例，即K個鄰居，並為所有這些K個實例分配一個公共輸出變數，來對對象進行分類。

K-均值（K-means）是通過對數據集進行分類來聚類的。例如，這個演算法可用於根據購買歷史將用戶分組。它在數據集中找到K個聚類。K-均值用於無監督學習，因此，我們只需使用訓練數據X，以及我們想要識別的聚類數量K。

隨機森林（Random Forest）是一種非常流行的集成機器學習演算法。這個演算法的基本思想是，許多人的意見要比個人的意見更准確。在隨機森林中，我們使用決策樹集成（參見決策樹）。

由於我們今天能夠捕獲的數據量之大，機器學習問題變得更加復雜。這就意味著訓練極其緩慢，而且很難找到一個好的解決方案。這一問題，通常被稱為「維數災難」（Curse of dimensionality）。

人工神經網路（Artificial Neural Networks，ANN）可以處理大型復雜的機器學習任務。神經網路本質上是一組帶有權值的邊和節點組成的相互連接的層，稱為神經元。在輸入層和輸出層之間，我們可以插入多個隱藏層。人工神經網路使用了兩個隱藏層。除此之外，還需要處理深度學習。