1. 原理

KNN算法就是在其表征空間中，求K個最鄰近的點。根據(jù)已知的這幾個點對其進行分類。如果其特征參數(shù)只有一個，那么就是一維空間。如果其特征參數(shù)只有兩個，那么就是二維空間。如果其特征參數(shù)只有三個，那么就是三維空間。如果其特征參數(shù)大于三個，那么就是N維抽象空間。在表征空間中，不同點的距離采用如下所示的歐幾里得方法進行計算。

K值根據(jù)經(jīng)驗選擇最合適的參數(shù)，太小不夠穩(wěn)健，太大的話容易受樣本不足制約。也可以根據(jù)交叉驗證的方法，確定最優(yōu)的K值。一般取5~10之間的一個數(shù)。

如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 看下面這幅圖：

KNN的算法過程是是這樣的： 從上圖中我們可以看到，圖中的數(shù)據(jù)集是良好的數(shù)據(jù)，即都打好了label，一類是藍色的正方形，一類是紅色的三角形，那個綠色的圓形是我們待分類的數(shù)據(jù)。 如果K=3，那么離綠色點最近的有2個紅色三角形和1個藍色的正方形，這3個點投票，于是綠色的這個待分類點屬于紅色的三角形 如果K=5，那么離綠色點最近的有2個紅色三角形和3個藍色的正方形，這5個點投票，于是綠色的這個待分類點屬于藍色的正方形 我們可以看到，KNN本質(zhì)是基于一種數(shù)據(jù)統(tǒng)計的方法！其實很多機器學(xué)習(xí)算法也是基于數(shù)據(jù)統(tǒng)計的。 KNN是一種memory-based learning，也叫instance-based learning，屬于lazy learning。即它沒有明顯的前期訓(xùn)練過程，而是程序開始運行時，把數(shù)據(jù)集加載到內(nèi)存后，不需要進行訓(xùn)練，就可以開始分類了。 具體是每次來一個未知的樣本點，就在附近找K個最近的點進行投票。

1. 三個距離算法

歐氏距離：是一個通常采用的距離定義，指在n維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離），在二維和n維空間中的歐氏距離就是兩點之間的實際距離。

def euclideanDistance(x1, x2):
??? # 歐氏距離
??? tempDistance = 0
??? for i in range(x1.shape[0]):
??????? difference = x1[i] - x2[i]
??????? tempDistance += difference * difference

??? tempDistance = tempDistance ** 0.5
??? return tempDistance

馬氏距離：馬氏距離(Mahalanobis Distance)是一種距離的度量，可以看作是歐氏距離的一種修正，修正了歐式距離中各個維度尺度不一致且相關(guān)的問題。其中Σ是多維隨機變量的協(xié)方差矩陣，μ為樣本均值，如果協(xié)方差矩陣是單位向量，也就是各維度獨立同分布，馬氏距離就變成了歐氏距離。

def mashi_distance(x,y):
??? X = numpy.vstack([x, y])
??? XT = X.T
??? # 方法一：根據(jù)公式求解
??? S = numpy.cov(X)? # 兩個維度之間協(xié)方差矩陣
??? SI = numpy.linalg.inv(S)? # 協(xié)方差矩陣的逆矩陣
??? # 馬氏距離計算兩個樣本之間的距離
??? n = XT.shape[0]
??? d1 = 0
??? for i in range(0, n):
??????? for j in range(i + 1, n):
??????????? delta = XT[i] - XT[j]
??????????? d = numpy.sqrt(numpy.dot(numpy.dot(delta, SI), delta.T))
????? ??????d1 = d1 + d
??? return d1

曼哈頓距離：種使用在幾何度量空間的幾何學(xué)用語，用以標(biāo)明兩個點在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距總和。

def ManhattanDistance(x, y):
??? x = numpy.array(x)
??? y = numpy.array(y)
??? return numpy.sum(numpy.abs(x-y))

1. 三個數(shù)據(jù)集

Iris數(shù)據(jù)集：Iris Data Set（鳶尾屬植物數(shù)據(jù)集）是我現(xiàn)在接觸到的歷史最悠久的數(shù)據(jù)集，它首次出現(xiàn)在著名的英國統(tǒng)計學(xué)家和生物學(xué)家Ronald Fisher?1936年的論文《The use of multiple measurements in taxonomic problems》中，被用來介紹線性判別式分析。在這個數(shù)據(jù)集中，包括了三類不同的鳶尾屬植物：Iris Setosa，Iris Versicolour，Iris Virginica。每類收集了50個樣本，因此這個數(shù)據(jù)集一共包含了150個樣本。

該數(shù)據(jù)集測量了所有150個樣本的4個特征，分別是：sepal length（花萼長度）；sepal width（花萼寬度）；petal length（花瓣長度）；petal width（花瓣寬度）以上四個特征的單位都是厘米（cm）。通常使用mm表示樣本量的大小，nn表示每個樣本所具有的特征數(shù)。因此在該數(shù)據(jù)集中，m=150,n=4m=150,n=4。

# iris數(shù)據(jù)集
tempDataset = sklearn.datasets.load_iris()

葡萄酒分類數(shù)據(jù)集：Wine葡萄酒數(shù)據(jù)集是來自UCI上面的公開數(shù)據(jù)集，這些數(shù)據(jù)是對意大利同一地區(qū)種植的葡萄酒進行化學(xué)分析的結(jié)果，這些葡萄酒來自三個不同的品種。該分析確定了三種葡萄酒中每種葡萄酒中含有的13種成分的數(shù)量。從UCI數(shù)據(jù)庫中得到的這個wine數(shù)據(jù)記錄的是在意大利某一地區(qū)同一區(qū)域上三種不同品種的葡萄酒的化學(xué)成分分析。數(shù)據(jù)里含有178個樣本分別屬于三個類別，這些類別已經(jīng)給出。每個樣本含有13個特征分量(化學(xué)成分)，分析確定了13種成分的數(shù)量，然后對其余葡萄酒進行分析發(fā)現(xiàn)該葡萄酒的分類。

在wine數(shù)據(jù)集中，這些數(shù)據(jù)包括了三種酒中13種不同成分的數(shù)量。文件中，每行代表一種酒的樣本，共有178個樣本；一共有14列，其中，第一個屬性是類標(biāo)識符，分別是1/2/3來表示，代表葡萄酒的三個分類。后面的13列為每個樣本的對應(yīng)屬性的樣本值。剩余的13個屬性是，酒精、蘋果酸、灰、灰分的堿度、鎂、總酚、黃酮類化合物、非黃烷類酚類、原花色素、顏色強度、色調(diào)、稀釋葡萄酒的OD280/OD315、脯氨酸。其中第1類有59個樣本，第2類有71個樣本，第3類有48個樣本。

# 葡萄酒分類數(shù)據(jù)集
tempDataset = sklearn.datasets.load_wine()

手寫分類數(shù)據(jù)集：在這個數(shù)據(jù)集中，包含1797張8*8灰度的圖像。每個數(shù)據(jù)點都是一個數(shù)字，共有10種類別（數(shù)字0~9）。

# 手寫數(shù)字分類數(shù)據(jù)集
tempDataset = sklearn.datasets.load_digits()

1. 實驗對比

1. 結(jié)論

本次實驗內(nèi)容包括三種數(shù)據(jù)集分別對三種距離測量算法進行knn預(yù)測分類，同一種數(shù)據(jù)集在不同距離測量算法下計算精度也不盡相同。其中，手寫數(shù)字?jǐn)?shù)據(jù)集在使用馬氏距離過程中計算量過大，不適宜使用馬氏距離計算。

import sklearn.datasets, sklearn.neighbors, sklearn.model_selection
import numpy
from sklearn import metricsdef sklearnKnnTest():#Step 1. Load the dataset# iris數(shù)據(jù)集#tempDataset = sklearn.datasets.load_iris()# 葡萄酒分類數(shù)據(jù)集#tempDataset = sklearn.datasets.load_wine()# 手寫數(shù)字分類數(shù)據(jù)集tempDataset = sklearn.datasets.load_digits()x = tempDataset.datay = tempDataset.target#print("x = ", x)#print("y = ", y)#Step 2. Split the dataX1, X2, Y1, Y2 = sklearn.model_selection.train_test_split(x, y, test_size = 0.2)print("X1 = ", X1)print("Y1 = ", Y1)print("X2 = ", X2)print("Y2 = ", Y2)#Step 3. Indicate the training set.tempClassifier = sklearn.neighbors.KNeighborsClassifier(n_neighbors = 5)tempClassifier.fit(X1, Y1)#Step 4. Test.tempScore = tempClassifier.score(X2, Y2)print("The score is: ", tempScore)def euclideanDistance(x1, x2):# 歐氏距離tempDistance = 0for i in range(x1.shape[0]):difference = x1[i] - x2[i]tempDistance += difference * differencetempDistance = tempDistance ** 0.5return tempDistance
# 馬氏距離
def mashi_distance(x,y):X = numpy.vstack([x, y])XT = X.T# 方法一：根據(jù)公式求解S = numpy.cov(X)  # 兩個維度之間協(xié)方差矩陣SI = numpy.linalg.inv(S)  # 協(xié)方差矩陣的逆矩陣# 馬氏距離計算兩個樣本之間的距離n = XT.shape[0]d1 = 0for i in range(0, n):for j in range(i + 1, n):delta = XT[i] - XT[j]d = numpy.sqrt(numpy.dot(numpy.dot(delta, SI), delta.T))d1 = d1 + dreturn d1
# 曼哈頓距離
def ManhattanDistance(x, y):x = numpy.array(x)y = numpy.array(y)return numpy.sum(numpy.abs(x-y))def mfKnnTest(k = 3):#Step 1. Load the dataset# iris數(shù)據(jù)集#tempDataset = sklearn.datasets.load_iris()# 葡萄酒分類數(shù)據(jù)集#tempDataset = sklearn.datasets.load_wine()# 手寫數(shù)字分類數(shù)據(jù)集tempDataset = sklearn.datasets.load_digits()x = tempDataset.datay = tempDataset.target#print("x = ", x)#print("y = ", y)#Step 2. Split the dataX1, X2, Y1, Y2 = sklearn.model_selection.train_test_split(x, y, test_size = 0.2)# print("X1 = ", X1)# print("Y1 = ", Y1)# print("X2 = ", X2)# print("Y2 = ", Y2)#Step 3. ClassifytempPredicts = numpy.zeros(Y2.shape[0])for i in range(X2.shape[0]):#Step 3.1 Find k neigbhors#InitializetempNeighbors = numpy.zeros(k + 2)tempDistances = numpy.zeros(k + 2)for j in range(k + 2):tempDistances[j] = 1000tempDistances[0] = -1for j in range(X1.shape[0]):# 歐氏距離#tempDistance = euclideanDistance(X2[i], X1[j])# 馬氏距離tempDistance = mashi_distance(X2[i], X1[j])# 曼哈頓距離#tempDistance = ManhattanDistance(X2[i], X1[j])tempIndex = kwhile True:if tempDistance < tempDistances[tempIndex]:#Move forward#print("tempDistance = {} and tempDistances[{}] = {}".format(tempDistance, tempIndex, tempDistances[tempIndex]))tempNeighbors[tempIndex + 1] = tempNeighbors[tempIndex]tempDistances[tempIndex + 1] = tempDistances[tempIndex]tempIndex -= 1else:#Insert heretempNeighbors[tempIndex + 1] = jtempDistances[tempIndex + 1] = tempDistance#print("Insert to {}.".format(tempIndex))break#print("Classifying ", X2[i])#print("tempNeighbors = ", tempNeighbors)#Step 3.2 Vote#Step 2.2 Vote for the classtempLabels = []for j in range(k):tempIndex = int(tempNeighbors[j + 1])tempLabels.append(int(Y1[tempIndex]))tempCounts = []for label in tempLabels:#print("count = ", tempLabels.count(label))tempCounts.append(int(tempLabels.count(label)))tempPredicts[i] = tempLabels[numpy.argmax(tempCounts)]print("The predictions are: ", tempPredicts)print("The true labels are: ", Y2)print('The accuracy of the KNN is: {:.3f}'.format(metrics.accuracy_score(tempPredicts, Y2)))return metrics.accuracy_score(tempPredicts, Y2)def main():#sklearnKnnTest()#print("Life is short, so I study python.")list = []for i in range(6):list.append(mfKnnTest())print(list)main()