摘要：近鄰算法的三要素值的選擇即分類決策時選擇個最近鄰實例距離度量即預測實例點和訓練實例點間的距離，一般使用距離即歐氏距離分類決策規則。近鄰法的分類決策規則往往采用多數表決的方式，這等價于經驗風險最小化。

k近鄰算法是一種基本的分類和回歸方法，這里只實現分類的k近鄰算法。
k近鄰算法的輸入為實例的特征向量，對應特征空間的點；輸出為實例的類別，可以取多類。
k近鄰算法不具有顯式的學習過程，實際上k近鄰算法是利用訓練數據集對特征向量空間進行劃分。將劃分的空間模型作為其分類模型。

k值的選擇：即分類決策時選擇k個最近鄰實例；

距離度量：即預測實例點和訓練實例點間的距離，一般使用L2距離即歐氏距離；

分類決策規則。

下面對三要素進行一下說明：
1.歐氏距離即歐幾里得距離，高中數學中用來計算點和點間的距離公式；
2.k值選擇：k值選擇會對k近鄰法結果產生重大影響，如果選擇較小的k值，相當于在較小的鄰域中訓練實例進行預測，這樣有點是“近似誤差”會減小，即只與輸入實例較近（相似）的訓練實例才會起作用，缺點是“估計誤差”會增大，即對近鄰的實例點很敏感。而k值過大則相反。實際中取較小的k值通過交叉驗證的方法取最優k值。
3.k近鄰法的分類決策規則往往采用多數表決的方式，這等價于“經驗風險最小化”。

實現k近鄰法是要考慮的主要問題是如何退訓練數據進行快速的k近鄰搜索，當訓練實例數很大是顯然通過一般的線性搜索方式效率低下，因此為了提高搜索效率，需要構造特殊的數據結構對訓練實例進行存儲。kd樹就是一種不錯的數據結構，可以大大提高搜索效率。
本質商kd樹是對k維空間的一個劃分，構造kd樹相當與使用垂直于坐標軸的超平面將k維空間進行切分，構造一系列的超矩形，kd樹的每一個結點對應一個這樣的超矩形。
kd樹本質上是一棵二叉樹，當通過一定規則構造是他是平衡的。
下面是過早kd樹的算法：

開始：構造根結點，根節點對應包含所有訓練實例的k為空間。 選擇第1維為坐標軸，以所有訓練實例的第一維數據的中位數為切分點，將根結點對應的超矩形切分為兩個子區域。由根結點生成深度為1的左右子結點，左結點對應第一維坐標小于切分點的子區域，右子結點對應第一位坐標大于切分點的子區域。
重復：對深度為j的結點選擇第l維為切分坐標軸，l=j(modk)+1,以該區域中所有訓練實例的第l維的中位數為切分點，重復第一步。
直到兩個子區域沒有實例存在時停止。形成kd樹。

準備工作

#讀取數據準備
def file2matrix(filename):
    fr = open(filename)
    returnMat = []          #樣本數據矩陣
    for line in fr.readlines():
        line = line.strip().split("	")
        returnMat.append([float(line[0]),float(line[1]),float(line[2]),float(line[3])])
    return returnMat
    
#將數據歸一化，避免數據各維度間的差異過大
def autoNorm(data):
    #將data數據和類別拆分
    data,label = np.split(data,[3],axis=1)
    minVals = data.min(0)     #data各列的最大值
    maxVals = data.max(0)       #data各列的最小值
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(data))
    m = data.shape[0]
    #tile函數將變量內容復制成輸入矩陣同樣大小的矩陣
    normDataSet = data - np.tile(minVals,(m,1))        
    normDataSet = normDataSet/np.tile(ranges,(m,1))
    #拼接
    normDataSet = np.hstack((normDataSet,label))
    return normDataSet

//數據實例
40920    8.326976    0.953952    3
14488    7.153469    1.673904    2
26052    1.441871    0.805124    1
75136    13.147394    0.428964    1
38344    1.669788    0.134296    1
72993    10.141740    1.032955    1
35948    6.830792    1.213192    3
42666    13.276369    0.543880    3
67497    8.631577    0.749278    1
35483    12.273169    1.508053    3
//每一行是一個數據實例，前三維是數據值，第四維是類別標記

樹結構定義

#構建kdTree將特征空間劃分
class kd_tree:
    """
    定義結點
    value:節點值
    dimension：當前劃分的維數
    left:左子樹
    right:右子樹
    """
    def __init__(self, value):
        self.value = value
        self.dimension = None       #記錄劃分的維數
        self.left = None
        self.right = None
    
    def setValue(self, value):
        self.value = value
    
    #類似Java的toString()方法
    def __str__(self):
        return str(self.value)

kd樹構造

def creat_kdTree(dataIn, k, root, deep):
    """
    data:要劃分的特征空間（即數據集）
    k:表示要選擇k個近鄰
    root:樹的根結點
    deep:結點的深度
    """
    #選擇x(l)(即為第l個特征)為坐標軸進行劃分，找到x(l)的中位數進行劃分
#     x_L = data[:,deep%k]        #這里選取第L個特征的所有數據組成一個列表
    #獲取特征值中位數，這里是難點如果numpy沒有提供的話
    
    if(dataIn.shape[0]>0):      #如果該區域還有實例數據就繼續
        dataIn = dataIn[dataIn[:,int(deep%k)].argsort()]       #numpy的array按照某列進行排序
        data1 = None; data2 = None
        #拿取根據xL排序的中位數的數據作為該子樹根結點的value
        if(dataIn.shape[0]%2 == 0):     #該數據集有偶數個數據
            mid = int(dataIn.shape[0]/2)
            root = kd_tree(dataIn[mid,:])
            root.dimension = deep%k
            dataIn = np.delete(dataIn,mid, axis = 0)
            data1,data2 = np.split(dataIn,[mid], axis=0) 
            #mid行元素分到data2中，刪除放到根結點中
        elif(dataIn.shape[0]%2 == 1):
            mid = int((dataIn.shape[0]+1)/2 - 1)    #這里出現遞歸溢出，當shape為(1,4)時出現，原因是np.delete時沒有賦值給dataIn
            root = kd_tree(dataIn[mid,:])
            root.dimension = deep%k
            dataIn = np.delete(dataIn,mid, axis = 0)
            data1,data2 = np.split(dataIn,[mid], axis=0) #mid行元素分到data1中，刪除放到根結點中
        #深度加一
        deep+=1
        #遞歸構造子樹
        #這里犯了嚴重錯誤，遞歸調用是將root傳遞進去，造成程序混亂，應該給None
        root.left = creat_kdTree(data1, k, None, deep)
        root.right = creat_kdTree(data2, k, None, deep)
    return root

前序遍歷測試

#前序遍歷kd樹
def preorder(kd_tree,i):
    print(str(kd_tree.value)+" :"+str(kd_tree.dimension)+":"+str(i))
    if kd_tree.left != None:
        preorder(kd_tree.left,i+1)
    if kd_tree.right != None:
        preorder(kd_tree.right,i+1)

最近鄰搜索算法，k近鄰搜索在此基礎上實現
原理：首先找到包含目標點的葉節點；然后從該也結點出發，一次退回到父節點，不斷查找與目標點最近的結點，當確定不可能存在更近的結點是停止。

def findClosest(kdNode,closestPoint,x,minDis,i=0):
    """
    這里存在一個問題，當傳遞普通的不可變對象minDis時，遞歸退回第一次找到
    最端距離前，minDis改變，最后結果混亂，這里傳遞一個可變對象進來。
    kdNode:是構造好的kd樹。
    closestPoint：是存儲最近點的可變對象，這里是array
    x：是要預測的實例
    minDis：是當前最近距離。
    """
    if kdNode == None:
        return
    #計算歐氏距離
    curDis = (sum((kdNode.value[0:3]-x[0:3])**2))**0.5
    if minDis[0] < 0 or curDis < minDis[0] :
        i+=1
        minDis[0] = curDis 
        closestPoint[0] = kdNode.value[0]
        closestPoint[1] = kdNode.value[1]
        closestPoint[2] = kdNode.value[2]
        closestPoint[3] = kdNode.value[3]
        print(str(closestPoint)+" : "+str(i)+" : "+str(minDis))
    #遞歸查找葉節點
    if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]:
        findClosest(kdNode.left,closestPoint,x,minDis,i)
    else:
        findClosest(kdNode.right, closestPoint, x, minDis,i) 
    #計算測試點和分隔超平面的距離，如果相交進入另一個葉節點重復
    rang = abs(x[kdNode.dimension] - kdNode.value[kdNode.dimension])
    if rang > minDis[0] :
        return
    if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]:
        findClosest(kdNode.right,closestPoint,x,minDis,i)
    else:
        findClosest(kdNode.left, closestPoint, x, minDis,i) 

測試：

data = file2matrix("datingTestSet2.txt")
data = np.array(data)
normDataSet = autoNorm(data)
sys.setrecursionlimit(10000)            #設置遞歸深度為10000
trainSet,testSet = np.split(normDataSet,[900],axis=0) 
kdTree = creat_kdTree(trainSet, 3, None, 0)
newData = testSet[1,0:3]
closestPoint = np.zeros(4)
minDis = np.array([-1.0])
findClosest(kdTree, closestPoint, newData, minDis)
print(closestPoint)
print(testSet[1,:])
print(minDis)

測試結果

[0.35118819 0.43961918 0.67110669 3.        ] : 1 : [0.40348346]
[0.11482037 0.13448927 0.48293309 2.        ] : 2 : [0.30404792]
[0.12227055 0.07902201 0.57826697 2.        ] : 3 : [0.22272422]
[0.0645755  0.10845299 0.83274698 2.        ] : 4 : [0.07066192]
[0.10020488 0.15196271 0.76225551 2.        ] : 5 : [0.02546591]
[0.10020488 0.15196271 0.76225551 2.        ]
[0.08959933 0.15442555 0.78527657 2.        ]
[0.02546591]

在最近鄰的基礎上進行改進得到：
這里的closestPoint和minDis合并，一同處理

#k近鄰搜索
def findKNode(kdNode, closestPoints, x, k):
    """
    k近鄰搜索，kdNode是要搜索的kd樹
    closestPoints:是要搜索的k近鄰點集合,將minDis放入closestPoints最后一列合并
    x：預測實例
    minDis：是最近距離
    k:是選擇k個近鄰
    """
    if kdNode == None:
        return
    #計算歐式距離
    curDis = (sum((kdNode.value[0:3]-x[0:3])**2))**0.5
    #將closestPoints按照minDis列排序,這里存在一個問題，排序后返回一個新對象
    #不能將其直接賦值給closestPoints
    tempPoints = closestPoints[closestPoints[:,4].argsort()]
    for i in range(k):
        closestPoints[i] = tempPoints[i]
    #每次取最后一行元素操作
    if closestPoints[k-1][4] >=10000  or closestPoints[k-1][4] > curDis:
        closestPoints[k-1][4] = curDis
        closestPoints[k-1,0:4] = kdNode.value 
        
    #遞歸搜索葉結點
    if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]:
        findKNode(kdNode.left, closestPoints, x, k)
    else:
        findKNode(kdNode.right, closestPoints, x, k)
    #計算測試點和分隔超平面的距離，如果相交進入另一個葉節點重復
    rang = abs(x[kdNode.dimension] - kdNode.value[kdNode.dimension])
    if rang > closestPoints[k-1][4]:
        return
    if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]:
        findKNode(kdNode.right, closestPoints, x, k)
    else:
        findKNode(kdNode.left, closestPoints, x, k)  

測試

data = file2matrix("datingTestSet2.txt")
data = np.array(data)
normDataSet = autoNorm(data)
sys.setrecursionlimit(10000)            #設置遞歸深度為10000
trainSet,testSet = np.split(normDataSet,[900],axis=0) 
kdTree = creat_kdTree(trainSet, 3, None, 0)
newData = testSet[1,0:3]
print("預測實例點："+str(newData))
closestPoints = np.zeros((3,5))         #初始化參數
closestPoints[:,4] = 10000.0            #給minDis列賦值
findKNode(kdTree, closestPoints, newData, 3)
print("k近鄰結果："+str(closestPoints))

測試結果

預測實例點：[0.08959933 0.15442555 0.78527657]
k近鄰結果：[[0.10020488 0.15196271 0.76225551 2.         0.02546591]
 [0.10664709 0.13172159 0.83777837 2.         0.05968697]
 [0.09616206 0.20475001 0.75047289 2.         0.06153793]]