今天我們要說的是：
KNN，也叫作K近鄰，他是一個(gè)常用的分類模型，他的設(shè)計(jì)思想要比之前的容易理解一些，但是他也有讓人頭大的地方，就是kd-tree，不過那都是后話了
例子
今天我們先看一個(gè)例子:
有一個(gè)老師，在想要在所有同學(xué)里面找到一個(gè)“老師眼里的小內(nèi)褲，同學(xué)心中的小混蛋”來作為自己的耳目，但是苦于剛剛開學(xué)誰也不認(rèn)識(shí)誰，這個(gè)工作就變得艱難起來，怎么才能最快找到這么一個(gè)小混蛋呢？老師想到一個(gè)辦法，去看他身邊的幾個(gè)朋友，如果都有成為小混蛋的趨勢(shì)，那么，這個(gè)八成也是個(gè)小混蛋了。
當(dāng)然，這個(gè)例子并不是那么貼切，因?yàn)槟阍趺粗绖e人有成為小混蛋的趨勢(shì)。但是，重點(diǎn)不在這里，家長經(jīng)常和孩子說，要去找學(xué)習(xí)好的孩子一起玩；也有俗語說：近朱者赤近墨者黑。
這其實(shí)都表明了一個(gè)道理：
一個(gè)人的好壞可以通過周圍人的好壞判斷出來。
同理，一個(gè)特征向量所表征的特征也可以通過特征空間里與他相近的幾個(gè)點(diǎn)表示出來。
什么是KNN
knn，k nearest neighbor,是一個(gè)常用的分類器（或用于聚類），我們通過選取K個(gè)鄰近的點(diǎn)，來判斷某個(gè)點(diǎn)的類別。但是怎么判斷呢？
分類決策規(guī)則
knn使用了投票表決的方式進(jìn)行分類，就像他的名字，“少數(shù)服從多數(shù)”，也就是說，K個(gè)鄰近的點(diǎn)中，占比最多的類別就是該點(diǎn)的類別。
K值的選擇
k值的選擇十分關(guān)鍵：
如果你的K值取得過大，就會(huì)出現(xiàn)不相干的點(diǎn)也被算到了里面，從而學(xué)習(xí)不到特征，就是欠擬合。
如果你的K值取得特別的小，那么模型就會(huì)對(duì)細(xì)節(jié)特別的敏感，而且周圍一旦出現(xiàn)噪聲，就會(huì)使模型變得特別差，也就是過擬合。
距離量度
如何表征兩個(gè)特征向量之間的距離呢？
而兩個(gè)特征向量的距離又表示在什么呢？
如何表征兩個(gè)特征向量之間的距離？
我們?cè)谶@里簡單的介紹一下常見的距離。
Lp距離，也叫作：Lp范數(shù)，我理解他就是對(duì)于向量長度的某種表征
當(dāng)然，p是一個(gè)常數(shù)，一般來說，常被用到的有：
L1范數(shù)其實(shí)就是向量各個(gè)分量的差的絕對(duì)值之和，又叫做曼哈頓距離，據(jù)說這個(gè)名字來源于曼哈頓的出租車司機(jī)在曼哈頓區(qū)沿著正方形的路徑行駛得來的。
L2范數(shù)，也叫歐幾里得距離，想必這個(gè)大家都熟悉，就不冗述了。
無窮范數(shù)，就是求兩個(gè)特征向量中相差最大的維度。
需要注意的是：在不同距離量度下，點(diǎn)與點(diǎn)之間的距離是不同的
而在knn中，我們用的是L2范數(shù)，也就是歐幾里得距離
KD-tree
根據(jù)前面說的，其實(shí)我們的KNN已經(jīng)做好，那kd-tree是用來干嘛的呢？我們來思考這樣的一個(gè)問題：
我們一共有五個(gè)點(diǎn)作為訓(xùn)練數(shù)據(jù)，然后又給了一個(gè)點(diǎn)作為測試數(shù)據(jù)，現(xiàn)在，我們想要的到測試點(diǎn)的類別，請(qǐng)問我們一共進(jìn)行了多少次運(yùn)算？
首先，我們算出了測試點(diǎn)到五個(gè)點(diǎn)的距離，總共5次運(yùn)算，
然后，我們還需要對(duì)距離排序，使用快排的話，時(shí)間復(fù)雜度是O(nlogn)
那么我們?cè)賮砜矗F(xiàn)在給你1000000個(gè)點(diǎn)，請(qǐng)問你要計(jì)算多少次？
所以，問題就擺在我們面前了，如何有效的減少計(jì)算次數(shù)就是我們要進(jìn)行優(yōu)化的。
A K-D Tree(also called as K-Dimensional Tree) is a binary search tree where data in each node is a K-Dimensional point in space. In short, it is a space partitioning(details below) data structure for organizing points in a K-Dimensional space.
上面是來自GeeksForGeeks的解答
就是說什么呢？
kd樹，就是K Dimensional Tree，是一個(gè)用來劃分空間的特殊二叉樹。具體如何搭建比較簡單，網(wǎng)上也有很多教程，在這里我想說一些不一樣的東西。
需要注意的是:這里的K不是Knn里面的K，而是說特征空間的維數(shù)。
為什么kd樹可以減少運(yùn)算次數(shù)
KD樹以二叉樹的形式，將每一個(gè)特征向量表示，然后，我們就可以利用某些剪枝算法，對(duì)樹進(jìn)行剪枝，然后我們就可以減少運(yùn)算次數(shù)，這樣說有些抽象，我們可以看一個(gè)例子。
例子：
我們假設(shè)要在這6個(gè)點(diǎn)中找到離（3,2）最近的點(diǎn)，我們需要怎么做呢？
很簡單，根據(jù)切割超平面不斷向下走，直到葉子節(jié)點(diǎn)（2,3），我們管這個(gè)葉子節(jié)點(diǎn)叫做“當(dāng)前最近點(diǎn)”，但他其實(shí)并不是最近的點(diǎn)，只是我們最初估計(jì)的。
然后呢？就開始回溯，我們知道，如果（2,3）不是最近的點(diǎn)，那么，最近的點(diǎn)一定在以兩點(diǎn)連線為半徑r的圓里面，那么，我們就回溯到父節(jié)點(diǎn)，計(jì)算（3,2）到父節(jié)點(diǎn)所在切割超平面的距離d，如果d > r,那么說明超平面切割不到超矩形區(qū)域，與這個(gè)圓是沒有交點(diǎn)的，也就是說，實(shí)際上，兄弟節(jié)點(diǎn)的那個(gè)點(diǎn)是無論如何都不可能成為最近點(diǎn)的，所以在下一次時(shí)，我們就直接回溯到父節(jié)點(diǎn)的父節(jié)點(diǎn)。這里，我們看到，實(shí)際上就是一次剪枝操作，兄弟節(jié)點(diǎn)被跳過了，我們?nèi)斡?jì)算變成了兩次計(jì)算，可以想象如果數(shù)據(jù)多了的話，會(huì)節(jié)省多少時(shí)間。
代碼：
import numpy as np
import matplotlib.pyplot as plt
import math
from stack import stack
class knn:
def __init__(self):
self.data = self.data_produce()
self.tree = self.create_branch(self.data, 0)
def data_produce(self, num=6):
x = np.random.randint(0, 50, num)
y = np.random.randint(0, 50, num)
data = []
for i in range(num):
tmp = [x[i], y[i]]
data.append(tmp)
return data
def draw_figure(self):
x = []
y = []
for i in self.data:
x.append(i[0])
y.append(i[1])
plt.scatter(x, y)
plt.show()
def create_branch(self, data, axia):
tree_branch = {}
if len(data) != 0 and len(data) != 1:
sorted_data = self.sort(data, axia)
if axia == 0:
axia = 1
else:
axia = 0
length = len(data)
index = length // 2
tree_branch['data'] = sorted_data[index]
tree_branch['left'] = self.create_branch(sorted_data[:index], axia)
tree_branch['right'] = self.create_branch(sorted_data[index+1:], axia)
elif len(data) == 1:
tree_branch['data'] = data[0]
return tree_branch
def search(self, point, axia):
"""
利用kd-tree進(jìn)行最近鄰搜索
思路：
首先，我們通過切分超平面找到近似最近點(diǎn)，
然后，我們?nèi)デ蟹殖矫娴牧硪粋?cè)去看看有沒有更近的點(diǎn)（通過到切分超平面的距離與到近似最近點(diǎn)的距離的比較）
一直回溯上去
"""
path_stack = stack()
def find_fake_near(tree, point, axia):
if 'left' not in tree.keys() and 'right' not in tree.keys():
return tree
else:
if point[axia] < tree['data'][axia]:
if axia == 0:
axia =1
else:
axia = 0
path_stack.push(tree)
return find_fake_near(tree['left'], point, axia)
else:
if axia == 0:
axia = 1
else:
axia = 0
path_stack.push(tree)
return find_fake_near(tree['right'], point, axia)
tree = self.tree
"""
initial three points
"""
cur_nearest_poi = find_fake_near(tree, point, 0)['data']
target_poi = point
doubt_poi = path_stack.pop()
axia = path_stack.length() % 2
def backtrace(cur_nearest_poi, target_poi, doubt_poi):
nonlocal axia
d1 = cal_distance(target_poi, cur_nearest_poi)
d2 = abs(doubt_poi['data'][axia] - target_poi[axia])
cnp_father = doubt_poi
if d1 > d2:
tmp = cur_nearest_poi
cur_nearest_poi = doubt_poi['data']
if 'left' in cnp_father.keys() and 'right' in cnp_father.keys():
if cnp_father['left'] == tmp:
return backtrace(cur_nearest_poi, target_poi, cnp_father['right'] )
else:
return backtrace(cur_nearest_poi, target_poi, cnp_father['left'] )
else:
if path_stack.length() != 0:
cnp_grand = path_stack.pop()
axia = path_stack.length() % 2
return backtrace(cur_nearest_poi, target_poi, cnp_grand)
else:
return cur_nearest_poi
elif d1 < d2 and path_stack.length() != 0:
doubt_poi = path_stack.pop()
return backtrace(cur_nearest_poi, target_poi, doubt_poi)
else:
return cur_nearest_poi
def cal_distance(poi1, poi2):
return math.sqrt(pow((poi1[0] - poi2[0]), 2) + pow((poi1[1] - poi2[1]), 2))
return backtrace(cur_nearest_poi, target_poi, doubt_poi)
def sort(self, data, axia):
if len(data) < 2:
return data
else:
pivot = data[0]
less = [i for i in data[1:] if i[axia] <= pivot[axia]]
greater = [i for i in data[1:] if i[axia] > pivot[axia]]
return self.sort(less, axia) + [pivot] + self.sort(greater, axia)
if __name__ == "__main__":
k = knn()
Nearest = k.search([20, 5], 0)
x = [i[0] for i in k.data if i != Nearest]
y = [j[1] for j in k.data if j != Nearest]
print(Nearest)
plt.scatter(x,y)
plt.scatter(20, 5)
plt.scatter(Nearest[0],Nearest[1])
plt.show()
在這里，說一下我寫的代碼：
1、首先，他還是有一些小bug的，但是大體是沒錯(cuò)的，也歡迎大家?guī)臀姨翦e(cuò)。
2、在構(gòu)建KD樹時(shí)，我使用了棧去維護(hù)我的樹，當(dāng)然，手工實(shí)現(xiàn)了一個(gè)簡單的棧（沒有技術(shù)含量，下面貼代碼）
3、在程序搭建里，大量使用了遞歸，盡可能的使用了尾遞歸優(yōu)化，避免出現(xiàn)stack overflow，同時(shí)，不得不說，在處理樹這個(gè)結(jié)構(gòu)時(shí)，遞歸的思想既簡單，又方便設(shè)計(jì)。而且涉及到需要回溯的問題，棧也是我們的不二選擇。
下面是棧的簡單實(shí)現(xiàn)：
class stack:
def __init__(self):
self.s_list = []
self._length = 0
self.top = None
self.bottom = None
def pop(self):
return self.s_list.pop()
def push(self, data):
self.s_list.append(data)
self.top = data
def is_empty(self):
if len(self.s_list) == 0:
return True
else:
return False
def length(self):
return len(self.s_list)
總的來說，沒有顯式的學(xué)習(xí)過程，knn的設(shè)計(jì)思想還是比較簡單的。
以上為我的個(gè)人看法，希望大家指出我的錯(cuò)誤之處。
更新
晚上和小伙伴討論了一下這個(gè)KD樹的搭建，現(xiàn)在有一些新的想法記錄一下。
對(duì)于回溯算法，開始我不知道怎么實(shí)現(xiàn)于是使用了一個(gè)路徑棧來記錄來的時(shí)候的路徑，但是在在和小伙伴聊完以后，我又去查了一下回溯算法，這里簡單的說一下：
回溯算法分為兩種：
1、遞歸調(diào)用方法
2、非遞歸調(diào)用方法
我想先說一下第二個(gè)：
我在實(shí)現(xiàn)KD樹的樹結(jié)構(gòu)時(shí)，采用的是python的dict作為基本結(jié)構(gòu)，這樣就導(dǎo)致我用非遞歸的方法回溯很困難，后來我想，如果我用list實(shí)現(xiàn)樹的結(jié)構(gòu)，應(yīng)該就會(huì)簡單不少，因?yàn)閘ist可以使用index訪問（也不知道為啥我對(duì)dict情有獨(dú)鐘，可能是哈希表看起來洋氣吧）。
至于遞歸的回溯方法，大家先看一下別人是怎么介紹的；
回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。
回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。
不知道大家看完有沒有感覺，就我而言，我想起了一個(gè)算法：
深度優(yōu)先探索
遞歸到葉子節(jié)點(diǎn)，然后剪枝，最后回溯。
和KD樹的搭建思想一模一樣，之前還是太天真了。
想看更多有關(guān)回溯算法以及代碼實(shí)現(xiàn)，請(qǐng)繼續(xù)關(guān)注我的更新。
