K-近鄰演算法簡介

K-近鄰演算法(KNN)概念

K Nearest Neighbor演算法又叫KNN演算法，這個演算法是機器學習里面一個比較經典的演算法， 總體來說KNN演算法是相對比較容易理解的演算法，

定義:
如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別，

距離公式：

兩個樣本的距離可以通過如下公式計算，又叫歐式距離 ，

實作流程

(1）計算已知類別資料集中的點與當前點之間的距離

(2）按距離遞增次序排序

(3）選取與當前點距離最小的k個點

(4）統計前k個點所在的類別出現的頻率

(5）回傳前k個點出現頻率最高的類別作為當前點的預測分類

k近鄰演算法api初步使用

機器學習流程：

1.獲取資料集
2.資料基本處理
3.特征工程
4.機器學習
5.模型評估

Scikit-learn工具介紹

Scikit-learn簡介：

Python語言的機器學習工具
Scikit-learn包括許多知名的機器學習演算法的實作
Scikit-learn檔案完善，容易上手，豐富的API
目前穩定版本0.19.1

安裝：

pip3 install scikit-learn==0.19.1

安裝好之后可以通過以下命令查看是否安裝成功

import sklearn

注：安裝scikit-learn需要Numpy, Scipy等庫

Scikit-learn包含的內容

分類、聚類、回歸
特征工程
模型選擇、調優

K-近鄰演算法API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)

n_neighbors：int,可選（默認= 5），k_neighbors查詢默認使用的鄰居數

案例：

from sklearn.neighbors import KNeighborsClassifier

x=[[1],[2],[0],[0]]
y=[5,10,1,1]
estimator=KNeighborsClassifier(n_neighbors=2)
estimator.fit(x,y)
ret=estimator.predict([[1000]])

print(ret)

距離度量

歐式距離(Euclidean Distance)

歐氏距離是最容易直觀理解的距離度量方法，我們小學、初中和高中接觸到的兩個點在空間中的距離一般都是指歐氏距離，

曼哈頓距離(Manhattan Distance)

在曼哈頓街區要從一個十字路口開車到另一個十字路口，駕駛距離顯然不是兩點間的直線距離，這個實際駕駛距離就是“曼哈頓距離”，曼哈頓距離也稱為“城市街區距離”(City Block distance)，

切比雪夫距離 (Chebyshev Distance)

國際象棋中，國王可以直行、橫行、斜行，所以國王走一步可以移動到相鄰8個方格中的任意一個，國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？這個距離就叫切比雪夫距離，

閔可夫斯基距離(Minkowski Distance)

閔氏距離不是一種距離，而是一組距離的定義，是對多個距離度量公式的概括性的表述，

兩個n維變數a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的閔可夫斯基距離定義為：

其中p是一個變引數：

當p=1時，就是曼哈頓距離；

當p=2時，就是歐氏距離；

當p→∞時，就是切比雪夫距離，

根據p的不同，閔氏距離可以表示某一類/種的距離，

標準化歐氏距離 (Standardized EuclideanDistance)

標準化歐氏距離是針對歐氏距離的缺點而作的一種改進，

思路：既然資料各維分量的分布不一樣，那先將各個分量都“標準化”到均值、方差相等，假設樣本集X的均值(mean)為m，標準差(standard deviation)為s，X的“標準化變數”表示為：

如果將方差的倒數看成一個權重，也可稱之為加權歐氏距離(Weighted Euclidean distance)，

余弦距離(Cosine Distance)

幾何中，夾角余弦可用來衡量兩個向量方向的差異；機器學習中，借用這一概念來衡量樣本向量之間的差異，
二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：

兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角余弦為：

漢明距離(Hamming Distance)

漢明距離是使用在資料傳輸差錯控制編碼里面的，漢明距離是一個概念，它表示兩個（相同長度）字對應位不同的數量，我們以d（x,y）表示兩個字x,y之間的漢明距離，對兩個字串進行異或運算，并統計結果為1的個數，那么這個數就是漢明距離，

漢明距離的計算方式：計算兩個等長字串之間對應位置上不同字符的個數，也就是說要求輸入的兩個字串必須長度一致，

杰卡德距離(Jaccard Distance)

杰卡德相似系數(Jaccard similarity coefficient)：兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的杰卡德相似系數，用符號J(A,B)表示：

杰卡德距離(Jaccard Distance)：與杰卡德相似系數相反，用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區分度：

馬氏距離(Mahalanobis Distance)

馬氏距離(Mahalanobis distance)是由印度統計學家馬哈拉諾比斯(P. C. Mahalanobis)提出的，表示點與一個分布之間的距離，它是一種有效的計算兩個未知樣本集的相似度的方法，與歐氏距離不同的是，它考慮到各種特性之間的聯系（例如：一條關于身高的資訊會帶來一條關于體重的資訊，因為兩者是有關聯的），并且是尺度無關的(scale-invariant)，即獨立于測量尺度，

對于一個均值為μ，協方差矩陣為Σ的多變數向量，其馬氏距離為：

當m=1時

馬氏距離特性：

1.量綱無關，排除變數之間的相關性的干擾；

2.馬氏距離的計算是建立在總體樣本的基礎上的，如果拿同樣的兩個樣本，放入兩個不同的總體中，最后計算得出的兩個樣本間的馬氏距離通常是不相同的，除非這兩個總體的協方差矩陣碰巧相同；

3 .計算馬氏距離程序中，要求總體樣本數大于樣本的維數，否則得到的總體樣本協方差矩陣逆矩陣不存在，這種情況下，用歐式距離計算即可，

4.還有一種情況，滿足了條件總體樣本數大于樣本的維數，但是協方差矩陣的逆矩陣仍然不存在，比如三個樣本點（3，4），（5，6），（7，8），這種情況是因為這三個樣本在其所處的二維空間平面內共線，這種情況下，也采用歐式距離計算，

K值的選擇

K值過小：

?

容易受到例外點的影響，

k值過大：

?

? 受到樣本均衡的問題

選擇較小的K值，就相當于用較小的領域中的訓練實體進行預測，“學習”近似誤差會減小，只有與輸入實體較近或相似的訓練實體才會對預測結果起作用，與此同時帶來的問題是“學習”的估計誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

選擇較大的K值，就相當于用較大領域中的訓練實體進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大，這時候，與輸入實體較遠（不相似的）訓練實體也會對預測器作用，使預測發生錯誤，且K值的增大就意味著整體的模型變得簡單，

K=N（N為訓練樣本個數），則完全不足取，因為此時無論輸入實體是什么，都只是簡單的預測它屬于在訓練實體中最多的類，模型過于簡單，忽略了訓練實體中大量有用資訊，

在實際應用中，K值一般取一個比較小的數值，例如采用交叉驗證法（簡單來說，就是把訓練資料在分成兩組:訓練集和驗證集）來選擇最優的K值，對這個簡單的分類器進行泛化，用核方法把這個線性模型擴展到非線性的情況，具體方法是把低維資料集映射到高維特征空間，

近似誤差：

對現有訓練集的訓練誤差，關注訓練集，如果近似誤差過小可能會出現過擬合的現象，對現有的訓練集能有很好的預測，但是對未知的測驗樣本將會出現較大偏差的預測，模型本身不是最接近最佳模型，

估計誤差：

可以理解為對測驗集的測驗誤差，關注測驗集，估計誤差小說明對未知資料的預測能力好，模型本身最接近最佳模型，

Kd樹

實作k近鄰法時，主要考慮的問題是如何對訓練資料進行快速k近鄰搜索，

k近鄰法最簡單的實作是線性掃描（窮舉搜索），即要計算輸入實體與每一個訓練實體的距離，計算并存盤好以后，再查找K近鄰，當訓練集很大時，計算非常耗時，

為了提高kNN搜索的效率，可以考慮使用特殊的結構存盤訓練資料，以減小計算距離的次數，

kd樹：為了避免每次都重新計算一遍距離，演算法會把距離資訊保存在一棵樹里，這樣在計算之前從樹里查詢距離資訊，盡量避免重新計算，其基本原理是，如果A和B距離很遠，B和C距離很近，那么A和C的距離也很遠，有了這個資訊，就可以在合適的時候跳過距離遠的點，這樣優化后的演算法復雜度可降低到O（DNlog（N））

資料集采集

案例：鳶尾花種類預測

Iris資料集是常用的分類實驗資料集，由Fisher, 1936收集整理，Iris也稱鳶尾花卉資料集，是一類多重變數分析的資料集，關于資料集的具體介紹：

scikit-learn資料集API介紹：

sklearn.datasets

加載獲取流行資料集

datasets.load_*()

獲取小規模資料集，資料包含在datasets里

datasets.fetch_*(data_home=None)

獲取大規模資料集，需要從網路上下載，函式的第一個引數是data_home，表示資料集下載的目錄,默認是 ~/scikit_learn_data/

sklearn小資料集:

sklearn.datasets.load_iris()

加載并回傳鳶尾花資料集

sklearn大資料集:

sklearn.datasets.fetch_20newsgroups(data_home=None,subset=‘train’)

subset：‘train’或者’test’，‘all’，可選，選擇要加載的資料集，
訓練集的“訓練”，測驗集的“測驗”，兩者的“全部”

sklearn資料集回傳值介紹:

load和fetch回傳的資料型別datasets.base.Bunch(字典格式)

data：特征資料陣列，是 [n_samples * n_features] 的二維 numpy.ndarray 陣列
target：標簽陣列，是 n_samples 的一維 numpy.ndarray 陣列
DESCR：資料描述
feature_names：特征名,新聞資料，手寫數字、回歸資料集沒有
target_names：標簽名

查看資料分布:
Seaborn 是基于 Matplotlib 核心庫進行了更高級的 API 封裝，可以讓你輕松地畫出更漂亮的圖形，而 Seaborn 的漂亮主要體現在配色更加舒服、以及圖形元素的樣式更加細膩，

sns.lmplot() 里的 x, y 分別代表橫縱坐標的列名,
data= 是關聯到資料集,
hue=*代表按照 species即花的類別分類顯示,
fit_reg=是否進行線性擬合，

import seaborn as sns
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris=load_iris()
iris_d = pd.DataFrame(iris['data'], columns = ['Sepal_Length', 'Sepal_Width', 'Petal_Length', 'Petal_Width'])

iris_d['target'] = iris.target

def plot_iris (iris,col1,col2):
    sns.lmplot(data=iris,x=col1,y=col2,hue = "target",fit_reg = False)
    plt.show()

plot_iris(iris_d,"Sepal_Length","Petal_Length")

資料集的劃分:
機器學習一般的資料集會劃分為兩個部分：

訓練資料：用于訓練，構建模型
測驗資料：在模型檢驗時使用，用于評估模型是否有效

劃分比例：

訓練集：70% 80% 75%
測驗集：30% 20% 25%

資料集劃分api

**sklearn.model_selection.train_test_split(arrays, *options)**
    x 資料集的特征值
    y 資料集的標簽值
    test_size 測驗集的大小，一般為float
    random_state 亂數種子,不同的種子會造成不同的隨機采樣結果，相同的種子采樣結果相同，
    return 測驗集特征訓練集特征值值，訓練標簽，測驗標簽(默認隨機取)

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()

x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=2)
print("x_train:\n", x_train.shape)
# 亂數種子
x_train1, x_test1, y_train1, y_test1 = train_test_split(iris.data, iris.target, random_state=6)
x_train2, x_test2, y_train2, y_test2 = train_test_split(iris.data, iris.target, random_state=6)
print("如果亂數種子不一致：\n", x_train == x_train1)
print("如果亂數種子一致：\n", x_train1 == x_train2)

特征工程-特征預處理

特征預處理定義

scikit-learn的解釋

provides several common utility functions and transformer classes to change raw feature vectors into a representation that is more suitable for the downstream estimators.

翻譯過來：通過一些轉換函式將特征資料轉換成更加適合演算法模型的特征資料程序，

為什么要進行歸一化/標準化

特征的單位或者大小相差較大，或者某特征的方差相比其他的特征要大出幾個數量級，容易影響（支配）目標結果，使得一些演算法無法學習到其它的特征，

歸一化

定義：

通過對原始資料進行變換把資料映射到(默認為[0,1])之間，

公式：

API：

sklearn.preprocessing.MinMaxScaler (feature_range=(0,1)… )

MinMaxScalar.fit_transform(X)

X:numpy array格式的資料[n_samples,n_features]
回傳值：轉換后的形狀相同的array，

注意：最大值最小值是變化的，另外，最大值與最小值非常容易受例外點影響，所以這種方法魯棒性較差，只適合傳統精確小資料場景，

標準化

定義：
通過對原始資料進行變換把資料變換到均值為0,標準差為1范圍內，

公式：

對于歸一化來說：如果出現例外點，影響了最大值和最小值，那么結果顯然會發生改變
對于標準化來說：如果出現例外點，由于具有一定資料量，少量的例外點對于平均值的影響并不大，從而方差改變較小

API:

sklearn.preprocessing.StandardScaler( )

處理之后每列來說所有資料都聚集在均值0附近標準差差為1

StandardScaler.fit_transform(X)

X:numpy array格式的資料[n_samples,n_features]
回傳值：轉換后的形狀相同的array

案例：

import pandas as pd
from sklearn.preprocessing import StandardScaler

data = pd.read_csv("dating.txt")
print(data)
transfer = StandardScaler()
data = transfer.fit_transform(data[['milage','Liters','Consumtime']])
print("標準化的結果:\n", data)
print("每一列特征的平均值：\n", transfer.mean_)
print("每一列特征的方差：\n", transfer.var_)

流程實作

案例：鳶尾花種類預測

近鄰演算法API：

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm=‘auto’)

n_neighbors：
int,可選（默認= 5），k_neighbors查詢默認使用的鄰居數

algorithm：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}

快速k近鄰搜索演算法，默認引數為auto，可以理解為演算法自己決定合適的搜索演算法，除此之外，用戶也可以自己指定搜索演算法ball_tree、kd_tree、brute方法進行搜索，

brute是蠻力搜索，也就是線性掃描，當訓練集很大時，計算非常耗時，

kd_tree，構造kd樹存盤資料以便對其進行快速檢索的樹形資料結構，kd樹也就是資料結構中的二叉樹，以中值切分構造的樹，每個結點是一個超矩形，在維數小于20時效率高，

ball tree是為了克服kd樹高緯失效而發明的，其構造程序是以質心C和半徑r分割樣本空間，每個節點是一個超球體，

步驟分析

1.獲取資料集
2.資料基本處理
3.特征工程
4.機器學習(模型訓練)
5.模型評估

匯入模塊 ：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

1.獲取資料集

iris = load_iris()

2.資料基本處理

x_train,x_test,y_train,y_test = train_test_split(iris.data,iris.target,test_size=0.2)

3.特征工程

transfer = StandardScaler()
x_train = transfer.fit_transform(x_train)
x_test = transfer.fit_transform(x_test)

4.機器學習(模型訓練)

estimator = KNeighborsClassifier(n_neighbors= 5)
estimator.fit(x_train,y_train)

5.模型評估

y_predict = estimator.predict(x_test)
print("預測結果為：\n",y_predict)
print("比對真實值和預測值:\n",y_predict == y_test)

score = estimator.score(x_test,y_test)
print("準確率為：\n",score)

全部代碼：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# 1.獲取資料集
iris = load_iris()

# 2.資料基本處理
x_train,x_test,y_train,y_test = train_test_split(iris.data,iris.target,test_size=0.2)

# 3.特征工程：標準化
transfer = StandardScaler()
x_train = transfer.fit_transform(x_train)
x_test = transfer.fit_transform(x_test)

# 4.機器學習（模型訓練）
estimator = KNeighborsClassifier(n_neighbors= 5)
estimator.fit(x_train,y_train)

# 5.模型評估
y_predict = estimator.predict(x_test)
print("預測結果為：\n",y_predict)
print("比對真實值和預測值:\n",y_predict == y_test)

score = estimator.score(x_test,y_test)
print("準確率為：\n",score)

交叉驗證與網格搜索

交叉驗證簡介

交叉驗證：將拿到的訓練資料，分為訓練和驗證集，以下圖為例：將資料分成4份，其中一份作為驗證集，然后經過4次(組)的測驗，每次都更換不同的驗證集，即得到4組模型的結果，取平均值作為最終結果，又稱4折交叉驗證，

我們之前知道資料分為訓練集和測驗集，但是為了讓從訓練得到模型結果更加準確，做以下處理

訓練集：訓練集+驗證集
測驗集：測驗集

交叉驗證目的：為了讓被評估的模型更加準確可信，

網格搜索簡介

通常情況下，有很多引數是需要手動指定的（如k-近鄰演算法中的K值），這種叫超引數，但是手動程序繁雜，所以需要對模型預設幾種超引陣列合，每組超引數都采用交叉驗證來進行評估，最后選出最優引陣列合建立模型，交叉驗證，網格搜索（模型選擇與調優）API：
sklearn.model_selection.GridSearchCV(estimator, param_grid=None,cv=None)

對估計器的指定引數值進行詳盡搜索
estimator：估計器物件
param_grid：估計器引數(dict){“n_neighbors”:[1,3,5]}
cv：指定幾折交叉驗證
fit：輸入訓練資料
score：準確率

結果分析：
bestscore__:在交叉驗證中驗證的最好結果
bestestimator：最好的引數模型
cvresults:每次交叉驗證后的驗證集準確率結果和訓練集準確率結果

鳶尾花案例增加K值調優：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split,GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# 1.獲取資料集
iris = load_iris()

# 2.資料基本處理
x_train,x_test,y_train,y_test = train_test_split(iris.data,iris.target,test_size=0.2)

# 3.特征工程：標準化
transfer = StandardScaler()
x_train = transfer.fit_transform(x_train)
x_test = transfer.fit_transform(x_test)

# 4.機器學習（模型訓練）
estimator = KNeighborsClassifier()
param_dict = {"n_neighbors":[1,3,5]}
estimator = GridSearchCV(estimator, param_grid = param_dict,cv=20,n_jobs=-1)
estimator.fit(x_train,y_train)

# 5.模型評估
y_predict = estimator.predict(x_test)
print("預測結果為：\n",y_predict)
print("比對真實值和預測值:\n",y_predict == y_test)

score = estimator.score(x_test,y_test)
print("準確率為：\n",score)


print("在交叉驗證中驗證的最好結果：\n", estimator.best_score_)
print("最好的引數模型：\n", estimator.best_estimator_)
print("每次交叉驗證后的準確率結果：\n", estimator.cv_results_)