k近鄰算法
K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。
K近鄰算法的思想：
“近朱者赤，近墨者黑“
“物以類聚，人以群分”
如上圖所示，紅、綠為兩類問藍(lán)色點屬于哪一類呢？
我們可以通過測量藍(lán)色點距離紅綠兩類所有點之間的距離進行分類。
這樣我們就把分類問題轉(zhuǎn)移到求點與點之間的距離的問題上來了；
根據(jù)我們中學(xué)所學(xué)的兩點之間的距離公式計算：
上圖第一行是普通的兩點間兩個維度上的距離的公式，第二行推廣到三個維度 第三多個維度 維度也就是特征
K近鄰算法實現(xiàn)步驟如下：
1.計算輸入x與訓(xùn)練集各點的距離distance
2.按distance排序，取distance最近的k個點（k為超參）
3.對k個點的類別歸類計數(shù)，x歸為多數(shù)類（多數(shù)表決）或者對k個點的類別按1/distance權(quán)重歸類計數(shù)，x歸為計數(shù)大的類（加權(quán)表決）
K近鄰算法實現(xiàn)代碼如下：
import numpy as np
from math import sqrt
from collections import Counter
from .metrics import accuracy_score
class KNNClassifier:
def __init__(self, k):
"""初始化kNN分類器"""
assert k >= 1, "k must be valid"
self.k = k
self._X_train = None
self._y_train = None
def fit(self, X_train, y_train):
"""根據(jù)訓(xùn)練數(shù)據(jù)集X_train和y_train訓(xùn)練kNN分類器"""
assert X_train.shape[0] == y_train.shape[0], \
"the size of X_train must be equal to the size of y_train"
assert self.k <= X_train.shape[0], \
"the size of X_train must be at least k."
self._X_train = X_train
self._y_train = y_train
return self
def predict(self, X_predict):
"""給定待預(yù)測數(shù)據(jù)集X_predict，返回表示X_predict的結(jié)果向量"""
assert self._X_train is not None and self._y_train is not None, \
"must fit before predict!"
assert X_predict.shape[1] == self._X_train.shape[1], \
"the feature number of X_predict must be equal to X_train"
y_predict = [self._predict(x) for x in X_predict]
return np.array(y_predict)
def _predict(self, x):
"""給定單個待預(yù)測數(shù)據(jù)x，返回x的預(yù)測結(jié)果值"""
assert x.shape[0] == self._X_train.shape[1], \
"the feature number of x must be equal to X_train"
distances = [sqrt(np.sum((x_train - x) ** 2))
for x_train in self._X_train]
nearest = np.argsort(distances)
topK_y = [self._y_train[i] for i in nearest[:self.k]]
votes = Counter(topK_y)
return votes.most_common(1)[0][0]
def score(self, X_test, y_test):
"""根據(jù)測試數(shù)據(jù)集 X_test 和 y_test 確定當(dāng)前模型的準(zhǔn)確度"""
y_predict = self.predict(X_test)
return np.sum(y_test == y_predict) / len(y_test)
def __repr__(self):
return "KNN(k=%d)" % self.k
sklearn中k近鄰算法的實現(xiàn)
# 引入sklearn包中的knn類
from sklearn.neighbors import KNeighborsClassifier
# 取得knn分類器，并使用內(nèi)置參數(shù)調(diào)整KNN三要素
knn=KNeighborsClassifier(weights="distance",n_neighbors=5)
# 使用knn.fit()對訓(xùn)練集進行訓(xùn)練
knn.fit(x_train, y_train)
# 調(diào)用knn.predict()預(yù)測新輸入的類別
y_predict=knn.predict(x_test)
# 調(diào)用knn.predict_proba()，顯示每個測試集樣本對應(yīng)各個分類結(jié)果的概率
knn.predict_proba(x_test)
# 調(diào)用knn.score()計算預(yù)測的準(zhǔn)確率
score=knn.score(x_test, y_test, sample_weight=None)
K近鄰處理回歸問題的思路
KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的某些屬性做一定的處理（例如取平均值）賦給該樣本，就可以得到該樣本對應(yīng)屬性的值。
距離度量拓展
衡量特征空間中兩個實例點的距離，度量方法一邊用Lp距離，p取不同值時，分別有不同的名稱，常用歐氏距離作為距離度量。
Lp距離：
歐氏距離(p=2)
曼哈頓距離(p=1)
p無窮
不同的距離度量，得到的實例點之間的距離是不同的。
K近鄰算法優(yōu)缺點
優(yōu)點：
1、KNN可以處理分類問題，同時天然可以處理多分類問題。
2、簡單，易懂，同時也很強大，對于手寫數(shù)字的識別，鳶尾花這一類問題來說，準(zhǔn)確率很高。
3、KNN還可以處理回歸問題。
缺點：
1、效率低，因為每一次分類或者回歸，都要把訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)都算一遍，如果數(shù)據(jù)量很大的話，需要的算力會很驚人，但是在機器學(xué)習(xí)中，大數(shù)據(jù)處理又是很常見的一件事。
2、對訓(xùn)練數(shù)據(jù)依賴度特別大，雖然所有機器學(xué)習(xí)的算法對數(shù)據(jù)的依賴度很高，但是KNN尤其嚴(yán)重，因為如果我們的訓(xùn)練數(shù)據(jù)集中，有一兩個數(shù)據(jù)是錯誤的，剛剛好又在我們需要分類的數(shù)值的旁邊，這樣就會直接導(dǎo)致預(yù)測的數(shù)據(jù)的不準(zhǔn)確，對訓(xùn)練數(shù)據(jù)的容錯性太差。
3、維數(shù)災(zāi)難，KNN對于多維度的數(shù)據(jù)處理也不是很好。
例：[0, 0, 0, ...0]和[1, 1, 1,...1]，按歐拉定理計算，元素個數(shù)越多，兩點距離越大
