從零開始實現KNN分類演算法

聲明：版權所有，轉載請聯繫作者並註明出處: 風雪夜歸子 - CSDN博客

知乎專欄： https://www.zhihu.com/people/feng-xue-ye-gui-zi

由於知乎不支持markdown格式，所以有公式的地方都使用了截圖，若影響閱讀效果，可移步我的Blog：風雪夜歸子 - CSDN博客，文章會同步更新！

K近鄰分類演算法 (K-Nearest Neighbor)

KNN分類演算法非常簡單，該演算法的核心思想是如果一個樣本在特徵空間中的k個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在確定分類決策上只依據最鄰近K個樣本的類別來決定待分樣本所屬的類別。KNN是一個懶惰演算法，也就是說在平時不好好學習，考試（對測試樣本分類）時才臨陣發力（臨時去找k個近鄰），因此在預測的時候速度比較慢。

KNN模型是非參數模型，既然有非參數模型，那就肯定還有參數模型，那何為參數模型與非參數模型呢？

1. 參數模型與非參數模型

1.1 參數模型

參數模型是指選擇某種形式的函數並通過機器學慣用一系列固定個數的參數儘可能表徵這些數據的某種模式。參數模型具有如下特徵：

1. 不管數據量有多大，在模型確定了，參數的個數就確定了，即參數個數不隨著樣本量的增大而增加，從關係上說它們相互獨立；
2. 一般參數模型會對數據有一定的假設，如分布的假設，空間的假設等，並且這些假設可以由參數來描述；
3. 參數模型預測速度快。

常用參數學習的模型有：

• 回歸模型（線性回歸、嶺回歸、lasso回歸、多項式回歸）
• 邏輯回歸
• 線性判別分析（Linear Discriminant Analysis）
• 感知器
• 樸素貝葉斯
• 神經網路
• 使用線性核的SVM
• Mixture models
• K-means
• Hidden Markov models
• Factor analysis / pPCA / PMF

1.2 非參數模型

非參數模型是指系統的數學模型中非顯式地包含可估參數。注意不要被名字誤導，非參不等於無參。非參數模型具有以下特徵：

1. 數據決定了函數形式，函數參數個數不固定；
2. 隨著訓練數據量的增加，參數個數一般也會隨之增長，模型越來越大；
3. 對數據本身做較少的先驗假設；
4. 預測速度慢。

一些常用的非參學習模型：

• k-Nearest Neighbors
• Decision Trees like CART and C4.5
• 使用非線性核的SVM
• Gradient Boosted Decision Trees
• Gaussian processes for regression
• Dirichlet process mixtures
• infinite HMMs
• infinite latent factor models

2. KNN演算法步驟：

1. 準備數據，對數據進行預處理；
2. 設定參數，如k；
3. 遍歷測試集，

對測試集中每個樣本，計算該樣本（測試集中）到訓練集中每個樣本的距離；

取出訓練集中到該樣本（測試集中）的距離最小的k個樣本的類別標籤；

對類別標籤進行計數，類別標籤次數最多的就是該樣本（測試集中）的類別標籤。

4. 遍歷完畢.

3. KNN演算法優點和缺點

3.1 KNN演算法優點

1. 簡單，易於理解，易於實現，無需估計參數，無需訓練；
2. 適合對稀有事件進行分類；
3. 特別適合於多分類問題(multi-modal,對象具有多個類別標籤)， kNN比SVM的表現要好；
4. 由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合；
5. 該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。

3.2 KNN演算法缺點

1. 該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進；
2. 該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。
3. 屬於硬分類，即直接給出這個樣本的類別，並不是給出這個樣本有多大的可能性屬於該類別；
4. 可解釋性差，無法給出像決策樹那樣的規則；
5. 計算量較大。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。

from __future__ import print_functionimport sysimport osimport mathimport numpy as npfrom sklearn import datasetsimport matplotlib.pyplot as pltfrom collections import Counterfrom sklearn.datasets import make_classification%matplotlib inlinedef shuffle_data(X, y, seed=None): if seed: np.random.seed(seed) idx = np.arange(X.shape[0]) np.random.shuffle(idx) return X[idx], y[idx]# 正規化數據集 Xdef normalize(X, axis=-1, p=2): lp_norm = np.atleast_1d(np.linalg.norm(X, p, axis)) lp_norm[lp_norm == 0] = 1 return X / np.expand_dims(lp_norm, axis)# 標準化數據集 Xdef standardize(X): X_std = np.zeros(X.shape) mean = X.mean(axis=0) std = X.std(axis=0) # 做除法運算時請永遠記住分母不能等於0的情形 # X_std = (X - X.mean(axis=0)) / X.std(axis=0) for col in range(np.shape(X)[1]): if std[col]: X_std[:, col] = (X_std[:, col] - mean[col]) / std[col] return X_std# 劃分數據集為訓練集和測試集def train_test_split(X, y, test_size=0.2, shuffle=True, seed=None): if shuffle: X, y = shuffle_data(X, y, seed) n_train_samples = int(X.shape[0] * (1-test_size)) x_train, x_test = X[:n_train_samples], X[n_train_samples:] y_train, y_test = y[:n_train_samples], y[n_train_samples:] return x_train, x_test, y_train, y_testdef accuracy(y, y_pred): y = y.reshape(y.shape[0], -1) y_pred = y_pred.reshape(y_pred.shape[0], -1) return np.sum(y == y_pred)/len(y)class KNN(): """ K近鄰分類演算法. Parameters: ----------- k: int 最近鄰個數. """ def __init__(self, k=5): self.k = k # 計算一個樣本與訓練集中所有樣本的歐氏距離的平方 def euclidean_distance(self, one_sample, X_train): one_sample = one_sample.reshape(1, -1) X_train = X_train.reshape(X_train.shape[0], -1) distances = np.power(np.tile(one_sample, (X_train.shape[0], 1)) - X_train, 2).sum(axis=1) return distances # 獲取k個近鄰的類別標籤 def get_k_neighbor_labels(self, distances, y_train, k): k_neighbor_labels = [] for distance in np.sort(distances)[:k]: label = y_train[distances==distance] k_neighbor_labels.append(label) return np.array(k_neighbor_labels).reshape(-1, ) # 進行標籤統計，得票最多的標籤就是該測試樣本的預測標籤 def vote(self, one_sample, X_train, y_train, k): distances = self.euclidean_distance(one_sample, X_train) #print(distances.shape) y_train = y_train.reshape(y_train.shape[0], 1) k_neighbor_labels = self.get_k_neighbor_labels(distances, y_train, k) #print(k_neighbor_labels.shape) find_label, find_count = 0, 0 for label, count in Counter(k_neighbor_labels).items(): if count > find_count: find_count = count find_label = label return find_label # 對測試集進行預測 def predict(self, X_test, X_train, y_train): y_pred = [] for sample in X_test: label = self.vote(sample, X_train, y_train, self.k) y_pred.append(label) #print(y_pred) return np.array(y_pred)def main(): data = make_classification(n_samples=200, n_features=4, n_informative=2, n_redundant=2, n_repeated=0, n_classes=2) X, y = data[0], data[1] X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, shuffle=True) clf = KNN(k=5) y_pred = clf.predict(X_test, X_train, y_train) accu = accuracy(y_test, y_pred) print ("Accuracy:", accu)if __name__ == "__main__": main()

推薦閱讀：