一.实验目的

1.理解K-近邻算法原理，能实现算法K近邻算法；

2.掌握常见的距离度量方法；

3.掌握K近邻树实现算法；

4.针对特定应用场景及数据，能应用K近邻解决实际问题。

二.实验内容

1.实现曼哈顿距离、欧氏距离、闵式距离算法，并测试算法正确性。

2.实现K近邻树算法；

3.针对iris数据集，应用sklearn的K近邻算法进行类别预测。

4.针对iris数据集，编制程序使用K近邻树进行类别预测。

三.实验报告要求

1.对照实验内容，撰写实验过程、算法及测试结果；

2.代码规范化：命名规则、注释；

3.分析核心算法的复杂度；

4.查阅文献，讨论K近邻的优缺点；

5.举例说明K近邻的应用场景。

四.实验代码及结果

1.曼哈顿距离、欧氏距离、闵式距离算法

·曼哈顿距离
简介：曼哈顿距离使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。它又被称为出租车距离，这是因为在像纽约曼哈顿区这样的地区有很多由横平竖直的街道所切成的街区，出租车司机计算从一个位置到另一个位置的距离，通常直接用街区的两个坐标分别相减，再相加，这个结果就是他即将开车通过的街区数量。

·欧氏距离
简介： 欧式距离是指m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。

计算公式

1、二维表示

2、推广到n维

·闵式距离算法
简介： 闵氏距离不是一种距离，而是一组距离的定义。

常见的p值有：
p=1 曼哈顿距离
p=2 欧氏距离
p=∞ 切比雪夫距离

# 导入数学模块
import math
from itertools import combinations

# 计算距离
def L(x, y, p=2):
    if len(x) == len(y) and len(x) > 1:  //当两个特征的维数相等时，并且维度大于1时
        sum = 0  //目前总的损失函数值为0
        for i in range(len(x)):  //用range函数来遍历x所有的维度，x与y的维度相等。
            sum += math.pow(abs(x[i] - y[i]), p)  //math.pow( x, y )函数是计算x的y次方
        return math.pow(sum, 1/p)  //距离公式
    else:
        return 0

# 输入样例
x1 = [1, 1]
x2 = [5, 1]
x3 = [4, 4]

# 计算x1与x2和x3之间的距离
for i in range(1, 5):
    r = { '1-{}'.format(c):L(x1, c, p=i) for c in [x2, x3]}  //创建一个字典
    print(min(zip(r.values(), r.keys())))  //当p=i时选出x2和x3中距离x1最近的点

运行结果：
(4.0, '1-[5, 1]')
(4.0, '1-[5, 1]')
(3.7797631496846193, '1-[4, 4]')
(3.5676213450081633, '1-[4, 4]')

2.实现K近邻树算法

python实现，遍历所有数据点，找出n个距离最近的点的分类情况，少数服从多数(不使用直接的python中现有的K-近邻算法包)

# 导包
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter

# data 输入数据
iris = load_iris()  //获取python中鸢尾花Iris数据集
df = pd.DataFrame(iris.data, columns=iris.feature_names)  //将数据集使用DataFrame建表
df['label'] = iris.target  //将表的最后一列作为目标列
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']  //定义表中每一列
# data = np.array(df.iloc[:100, [0, 1, -1]])

df # 打印表

# 绘制数据散点图
plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')  //绘制前50个数据的散点图
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')  //绘制50-100个数据的散点图
plt.xlabel('sepal length')
plt.ylabel('sepal width')  //设置x，y轴坐标名
plt.legend()  //绘图

运行结果：

data = np.array(df.iloc[:100, [0, 1, -1]])  //iloc函数：通过行号来取行数据,读取数据前100行的第0,1列和最后一列
X, y = data[:,:-1], data[:,-1] //X为data数据集中去除最后一列所形成的新数据集,y为data数据集中最后一列数据所形成的新数据集
# 选取训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)  //train_test_split函数用于将矩阵随机划分为训练子集和测试子集

# 建立一个类KNN，用于k-近邻的计算
class KNN:
    # 初始化
    def __init__(self, X_train, y_train, n_neighbors=3, p=2):  //初始化数据，neighbor表示邻近点，p为欧氏距离
        self.n = n_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train
    
    def predict(self, X):
        //取出n个点，放入空的列表，列表中存放预测点与训练集点的距离及其对应标签
        knn_list = []
        for i in range(self.n):  //遍历邻近点
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)  //计算训练集和测试集之间的距离
            knn_list.append((dist, self.y_train[i]))
           //取出训练集剩下的点，然后与n_neighbor个点比较大叫，将距离大的点更新
           //保证knn_list列表中的点是距离最小的点
            
        for i in range(self.n, len(self.X_train)): 
               '''max(num,key=lambda x: x[0])用法：
               x:x[]字母可以随意修改，求最大值方式按照中括号[]里面的维度，
               [0]按照第一维，
               [1]按照第二维
               '''
            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))  //找出列表中距离最大的点
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)  //计算训练集和测试集之间的距离
            if knn_list[max_index][0] > dist:  //若当前数据的距离大于之前得出的距离，就将数值替换
                knn_list[max_index] = (dist, self.y_train[i])
                
        # 统计
        knn = [k[-1] for k in knn_list]
        count_pairs = Counter(knn)  //统计标签的个数
        max_count = sorted(count_pairs, key=lambda x:x)[-1]  //将标签升序排列
        return max_count
    
    # 计算测试算法的正确率
    def score(self, X_test, y_test):
        right_count = 0 
        n = 10
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            if label == y:
                right_count += 1
        return right_count / len(X_test)

clf = KNN(X_train, y_train)  //调用KNN算法进行计算

clf.score(X_test, y_test)  //计算正确率

运行结果：

test_point = [6.0, 3.0]  //用于算法测试的数据
print('Test Point: {}'.format(clf.predict(test_point)))

运行结果：

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')  //将数据的前50个数据绘制散点图
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')  //将数据的50-100个数据绘制散点图
plt.plot(test_point[0], test_point[1], 'bo', label='test_point')  //将测试数据点绘制在图中
plt.xlabel('sepal length')  
plt.ylabel('sepal width')  //x,y轴命名
plt.legend()  //绘图

运行结果：

3.针对iris数据集，应用sklearn的K近邻算法进行类别预测

# 导包
from sklearn.neighbors import KNeighborsClassifier

# 调用
clf_sk = KNeighborsClassifier()
clf_sk.fit(X_train, y_train)

运行结果：

clf_sk.score(X_test, y_test)  //计算正确率

运行结果：

4.针对iris数据集，编制程序使用K近邻树进行类别预测

# 建造kd树
# kd-tree每个结点中主要包含的数据结构如下
 class KdNode(object):
   def __init__(self, dom_elt, split, left, right):
       self.dom_elt = dom_elt  //k维向量节点(k维空间中的一个样本点)
       self.split = split  //整数（进行分割维度的序号）
       self.left = left  //该结点分割超平面左子空间构成的kd-tree
       self.right = right  //该结点分割超平面右子空间构成的kd-tree

class KdTree(object):
   def __init__(self, data):
       k = len(data[0])  //数据维度
 
       def CreateNode(split, data_set):  //按第split维划分数据集exset创建KdNode
           if not data_set:  //数据集为空
              return None
              '''
              1.key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较
              2.operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为需要获取的数据在对象
              3.data_set.sort(key=itemgetter(split))按要进行分割的那一维数据排序
              '''
              data_set.sort(key=lambda x: x[split])
              split_pos = len(data_set)
              median = data_set[split_pos]  //中位数分割点 
              split_next = (split + 1) % k # cycle coordinates
 
              # 递归的创建kd树
              return KdNode(median, split, 
                           CreateNode(split_next, data_set[:split_pos])  //创建左子树
                           CreateNode(split_next, data_set[split_pos + 1:]))  //创建右子树
 
       self.root = CreateNode(0, data)  //从第0维分量开始构建kd树,返回根节点

# KDTree的前序遍历 
def preorder(root): 
    print (root.dom_elt) 
    if root.left:  //节点不为空
       preorder(root.left) 
    if root.right: 
       preorder(root.right)

#对构建好的kd树进行搜索，寻找与目标点最近的样本点：
from math import sqrt
from collections import namedtuple

#定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数
result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited")
 
def find_nearest(tree, point):
	k = len(point)  //数据维度
	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  //下一个访问节点为左子树根节点
			further_node = kd_node.right  //同时记录下右子树
		else:  //目标离右子树更近
			nearer_node = kd_node.right  //下一个访问节点为右子树根节点
			further_node = kd_node.left
		
		temp1 = travel(nearer_node, target, max_dist)  //进行遍历找到包含目标点的区域
 
		nearest = temp1.nearest_point  //以此叶结点作为“当前最近点”
		dist = temp1.nearest_dist  //更新最近距离
 
		nodes_visited += temp1.nodes_visited 

		if dist < max_dist: 
			max_dist = dist  //最近点将在以目标点为球心，max_dist为半径的超球体内
 
		temp_dist = abs(pivot[s] - target[s])  //第s维上目标点与分割超平面的距离
		if max_dist < temp_dist:  //判断超球体是否与超平面相交
		return result(nearest, dist, nodes_visited)  //不相交则可以直接返回，不用继续判断
 
		
		# 计算目标点与分割点的欧氏距离 
		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  //更新超球体半径
 
		# 检查另一个子结点对应的区域是否有更近的点
		temp2 = travel(further_node, target, max_dist) 
 
		nodes_visited += temp2.nodes_visited
		if temp2.nearest_dist < dist:  //如果另一个子结点内存在更近距离
			nearest = temp2.nearest_point  //更新最近点
			dist = temp2.nearest_dist  //更新最近距离

		return result(nearest, dist, nodes_visited)
	
	return travel(tree.root, point, float("inf"))  //从根节点开始递归

# 数据测试
data= [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
kd=KdTree(data)
preorder(kd.root)

运行结果：

# 导包
from time import clock
from random import random

# 产生一个k维随机向量，每维分量值在0~1之间
def random_point(k): 
    return [random() for _ in range(k)]

# 产生n个k维随机向量
def random_points(k, n):
    return [random_point(k) for _ in range(n)]

# 输入数据进行测试
ret = find_nearest(kd, [3,4.5])
print (ret)

运行结果：

N = 400000
t0 = clock()
kd2 = KdTree(random_points(3, N))  //构建包含四十万个3维空间样本点的kd树
ret2 = find_nearest(kd2, [0.1,0.5,0.8])  //四十万个样本点中寻找离目标最近的点
t1 = clock()
print ("time: ",t1-t0, "s")
print (ret2)

运行结果:

四.作业小结

1.psp表格

2.心得和经验

K近邻分类算法是数据挖掘分类技术中最简单的方法之一。 所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特征。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少数的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或者重叠较多的待分样本集来说，kNN方法较其他方法更为适合。KNN做回归和分类的主要区别在于最后做预测的时候决策方式不同。KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。而KNN做回归时，一般选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。

优点：精确度高，对异常数据不敏感，无数据输入假定
缺点：计算复杂度高和空间复杂度高。因为要存储全部已知的样本数据，在每次分类的时候要计算全部的举例，所以时间复杂度和空间复杂度高
适用数据类型：数值型和标称型