from numpy import * 

# create a dataset which contains 4 samples with 2 classes 
def createDataSet(): 
  # create a matrix: each row as a sample 
  group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]]) 
  labels = ['A', 'A', 'B', 'B'] # four samples and two classes 
  return group, labels
# classify using kNN (k Nearest Neighbors ) 
# Input:   newInput: 1 x N
#       dataSet: M x N (M samples N, features)
#       labels:  1 x M  
#       k: number of neighbors to use for comparison 
# Output:   the most popular class label  
def kNNClassify(newInput, dataSet, labels, k): 
  numSamples = dataSet.shape[0] # shape[0] stands for the num of row 
  ## step 1: calculate Euclidean distance 
  # tile(A, reps): Construct an array by repeating A reps times 
  # the following copy numSamples rows for dataSet 
  diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise 
  squaredDiff = diff ** 2 # squared for the subtract 
  squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row 
  distance = squaredDist ** 0.5 
  ## step 2: sort the distance 
  # argsort() returns the indices that would sort an array in a ascending order 
  sortedDistIndices = argsort(distance) 
  classCount = {} # define a dictionary (can be append element) 
  for i in xrange(k): 
    ## step 3: choose the min k distance 
    voteLabel = labels[sortedDistIndices[i]] 
    ## step 4: count the times labels occur 
    # when the key voteLabel is not in dictionary classCount, get() 
    # will return 0 
    classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 
  ## step 5: the max voted class will return 
  maxCount = 0 
  for key, value in classCount.items(): 
    if value > maxCount: 
      maxCount = value 
      maxIndex = key 
  return maxIndex  
  if __name__== "__main__":  
  dataSet, labels = createDataSet() 
  testX = array([1.2, 1.0]) 
  k = 3 
  outputLabel = kNNClassify(testX, dataSet, labels, 3) 
  print "Your input is:", testX, "and classified to class: ", outputLabel 
  testX = array([0.1, 0.3]) 
  outputLabel = kNNClassify(testX, dataSet, labels, 3) 
  print "Your input is:", testX, "and classified to class: ", outputLabel

import numpy as np
import matplotlib.pyplot as plt
import cv2
# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)
# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')
# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
# Testing data
newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
knn = cv2.KNearest()
knn.train(trainData,responses) # Trains the model
# Finds the neighbors and predicts responses for input vectors.
ret, results, neighbours ,dist = knn.find_nearest(newcomer, 3)
print "result: ", results,"\n"
print "neighbours: ", neighbours,"\n"
print "distance: ", dist
plt.show()

>>> 
result: [[ 0.]]
neighbours: [[ 0. 0. 0.]]
distance: [[ 65. 145. 178.]]

# -*- coding: utf-8 -*-
#from operator import itemgetter
import sys
reload(sys)
sys.setdefaultencoding('utf8')
# kd-tree每個結(jié)點中主要包含的數(shù)據(jù)結(jié)構(gòu)如下 
class KdNode(object):
  def __init__(self, dom_elt, split, left, right):
    self.dom_elt = dom_elt # k維向量節(jié)點(k維空間中的一個樣本點)
    self.split = split   # 整數(shù)（進行分割維度的序號）
    self.left = left    # 該結(jié)點分割超平面左子空間構(gòu)成的kd-tree
    self.right = right   # 該結(jié)點分割超平面右子空間構(gòu)成的kd-tree
class KdTree(object):
  def __init__(self, data):
    k = len(data[0]) # 數(shù)據(jù)維度
    
    def CreateNode(split, data_set): # 按第split維劃分數(shù)據(jù)集exset創(chuàng)建KdNode
      if not data_set:  # 數(shù)據(jù)集為空
        return None
      # key參數(shù)的值為一個函數(shù)，此函數(shù)只有一個參數(shù)且返回一個值用來進行比較
      # operator模塊提供的itemgetter函數(shù)用于獲取對象的哪些維的數(shù)據(jù)，參數(shù)為需要獲取的數(shù)據(jù)在對象中的序號
      #data_set.sort(key=itemgetter(split)) # 按要進行分割的那一維數(shù)據(jù)排序
      data_set.sort(key=lambda x: x[split])
      split_pos = len(data_set) // 2   # //為Python中的整數(shù)除法
      median = data_set[split_pos]    # 中位數(shù)分割點       
      split_next = (split + 1) % k    # cycle coordinates      
      # 遞歸的創(chuàng)建kd樹
      return KdNode(median, split, 
             CreateNode(split_next, data_set[:split_pos]),   # 創(chuàng)建左子樹
             CreateNode(split_next, data_set[split_pos + 1:])) # 創(chuàng)建右子樹                
    self.root = CreateNode(0, data)     # 從第0維分量開始構(gòu)建kd樹,返回根節(jié)點
# KDTree的前序遍歷
def preorder(root): 
  print root.dom_elt 
  if root.left:   # 節(jié)點不為空
    preorder(root.left) 
  if root.right: 
    preorder(root.right) 
if __name__ == "__main__":
  data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
  kd = KdTree(data)
  preorder(kd.root)

from math import sqrt
from collections import namedtuple
# 定義一個namedtuple,分別存放最近坐標點、最近距離和訪問過的節(jié)點數(shù)
result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited") 
def find_nearest(tree, point):
  k = len(point) # 數(shù)據(jù)維度
  def travel(kd_node, target, max_dist):
    if kd_node is None:   
      return result([0] * k, float("inf"), 0) # python中用float("inf")和float("-inf")表示正負無窮 
    nodes_visited = 1    
    s = kd_node.split    # 進行分割的維度
    pivot = kd_node.dom_elt # 進行分割的“軸”    
    if target[s] <= pivot[s]:      # 如果目標點第s維小于分割軸的對應值(目標離左子樹更近)
      nearer_node = kd_node.left   # 下一個訪問節(jié)點為左子樹根節(jié)點
      further_node = kd_node.right  # 同時記錄下右子樹
    else:                # 目標離右子樹更近
      nearer_node = kd_node.right  # 下一個訪問節(jié)點為右子樹根節(jié)點
      further_node = kd_node.left 
    temp1 = travel(nearer_node, target, max_dist) # 進行遍歷找到包含目標點的區(qū)域    
    nearest = temp1.nearest_point    # 以此葉結(jié)點作為“當前最近點”
    dist = temp1.nearest_dist      # 更新最近距離    
    nodes_visited += temp1.nodes_visited 
    if dist < max_dist:   
      max_dist = dist  # 最近點將在以目標點為球心，max_dist為半徑的超球體內(nèi)
    temp_dist = abs(pivot[s] - target[s])  # 第s維上目標點與分割超平面的距離
    if max_dist < temp_dist:        # 判斷超球體是否與超平面相交
      return result(nearest, dist, nodes_visited) # 不相交則可以直接返回，不用繼續(xù)判斷 
    #---------------------------------------------------------------------- 
    # 計算目標點與分割點的歐氏距離 
    temp_dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(pivot, target)))   
    if temp_dist < dist:     # 如果“更近”
      nearest = pivot     # 更新最近點
      dist = temp_dist     # 更新最近距離
      max_dist = dist     # 更新超球體半徑
    
    # 檢查另一個子結(jié)點對應的區(qū)域是否有更近的點
    temp2 = travel(further_node, target, max_dist) 
    nodes_visited += temp2.nodes_visited
    if temp2.nearest_dist < dist:    # 如果另一個子結(jié)點內(nèi)存在更近距離
      nearest = temp2.nearest_point  # 更新最近點
      dist = temp2.nearest_dist    # 更新最近距離
    return result(nearest, dist, nodes_visited)
  return travel(tree.root, point, float("inf")) # 從根節(jié)點開始遞歸

from time import clock
from random import random
# 產(chǎn)生一個k維隨機向量，每維分量值在0~1之間
def random_point(k):
  return [random() for _ in range(k)]
 # 產(chǎn)生n個k維隨機向量 
def random_points(k, n):
  return [random_point(k) for _ in range(n)]    
   if __name__ == "__main__":
  data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]] # samples
    kd = KdTree(data)
    ret = find_nearest(kd, [3,4.5])
  print ret
  N = 400000
  t0 = clock()
  kd2 = KdTree(random_points(3, N))      # 構(gòu)建包含四十萬個3維空間樣本點的kd樹
  ret2 = find_nearest(kd2, [0.1,0.5,0.8])   # 四十萬個樣本點中尋找離目標最近的點
  t1 = clock()
  print "time: ",t1-t0, "s"
  print ret2