1、K近邻算法的特点

k-近邻算法，也叫KNN算法(K-Nearest Neihbor，KNN)，是一个非常适合入门的算法，拥有如下特性：

• 适用于分类问题，尤其是二分类，当然也可以用来预测回归问题

• 思想极度简单，应用数学知识少(近乎为零)

  • 对于很多不擅长数学的小伙伴十分友好，KNN算法几乎用不到数学专业知识

  • 机器学习算法的hello world算法

• 效果好

  • 虽然算法简单，但效果也不错

  • 缺点也是存在的，后面会进行讲解

  • 作为第一个算法，首先归纳总结下解决监督学习中分类问题的一般方法和步骤。

2、解决分类问题的一般方法

根据目标的不同将监督学习任务分为了分类预测问题及回归预测问题。

监督学习任务的基本流程和架构：

（1）首先准备数据，可以是视频、音频、文本、图片等等

（2）抽取所需要的一些列特征，形成特征向量（Feature Vectors）

（3）将这些特征向量连同标记（Label）一并送人机器学习算法中，训练出一个预测模型（Predictive Model）

（4）然后，采用同样的特征提取方法作用于新数据，得到用于测试的特征向量

（5）接下来，使用预测模型对这些待测的特征向量进行预测并得到结果（Expected Model）

（6）最后，评估模型的准确性

注：分类是常见的监督学习问题，最基础的就是二分类问题，即判断是非，从两个类别中选择一个作为预测结果。

3、什么是K-近邻算法

上图中的数据点是分布在一个特征空间中

• 横轴表示肿瘤大小，纵轴表示发现时间

• 恶性肿瘤用蓝色表示，良性肿瘤用红色表示

• 新来了一个病人(下图绿色的点)，如何判断新来的病人(即绿色点)是良性肿瘤还是恶性肿瘤？

 

k-近邻算法的做法如下：

• 取一个值k=3(k值后面介绍，现在可以理解为算法的使用者根据经验取的最优值)

• 在所有的点中找到距离绿色点最近的三个点

• 让最近的点所属的类别进行投票

  • 最近的三个点都是蓝色的，所以该病人对应的应该也是蓝色，即恶性肿瘤。

本质：如两个样本足够相似，那他们两个大概率属于同一类别

• 选择K个样本判断相似：如果只看一个已知样本，可能不准确

• 如果K个样本中大多数属于同一个类别，则被预测的样本就很可能属于对应的类别

• 如何衡量“相似性”：依靠距离衡量

再举例：

 上图中和绿色的点距离最近的点包含两个红色和一个蓝色，此处红色点和蓝色点的数量比为2:1，则绿色点为红色的概率最大，最后判断结果为良性肿瘤。

通过上述例子不难发现，K近邻算法善于解决监督学习中的分类问题

2、K-近邻算法实现分类

2.1 绘制基本图像

import numpy as np
import matplotlib.pyplot as plt

#定义特征值
raw_data_x=[[3.3144558 , 2.33542461],
       [3.75497175, 1.93856648],
       [1.38327539, 3.38724496],
       [3.09203999, 4.47090056],
       [2.58593831, 2.13055653],
       [7.41206251, 4.80305318],
       [5.912852  , 3.72918089],
       [9.21547627, 2.8132231 ],
       [7.36039738, 3.35043406],
       [7.13698009, 0.40130301]]

#定义目标值
raw_data_y=[0,0,0,0,0,1,1,1,1,1]

X_train = np.array(raw_data_x)
y_train = np.array(raw_data_y)

#利用matplotlib绘制图像
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1],color='g')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1],color='r')
plt.show()

 2.2 加入预测点，绘制图像

x=np.array([8.093607318,3.365731514])

plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1],color='g')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1],color='r')
plt.scatter(x[0],x[1],color='b')
plt.show()

预测蓝色点属于哪一个类别，需要找到距离蓝色点最近的K个邻居，找到K个邻居需要计算距离：

• 欧式距离：任意空间下两个点的对应维度的坐标值相减的平方和再开方

• 欧式距离公式：

  • 平面中两点之间的欧式距离：

    $$\Large \sqrt{(x^{(a)}-x^{(b)})^2+(y^{(a)}-y^{(b)})^2}$$

  • 立体中两点之间的距离：

    $$\Large \sqrt{(x^{(a)}-x^{(b)})^2+(y^{(a)}-y^{(b)})^2+(z^{(a)}-z^{(b)})^2}$$

  • 任意维度下的欧拉距离：

    $$\Large \sqrt{(x{1}^{(a)}-x{1}^{(b)})^2+(x{2}^{(a)}-x{2}^{(b)})^2+...+(x{n}^{(a)}-x{n}^{(b)})^2}$$

  • 简化后：

    $$\Large \sqrt{\sum{i=1}^{n}(x{i}^{(a)}-x_{i}^{(b)})^2}$$

2.3 实现距离计算

# np.sqrt() 开方
# np.square() 平方
distances=np.sqrt(np.sum(np.square(X_train-x),axis=1))
distances
# 结果展示
# array([4.88894892, 4.56733605, 6.71036641, 5.12221381, 5.64447297,
#        1.59072213, 2.2108345 , 1.25054208, 0.7333695 , 3.11495939])

# 对计算的距离进行排序
nearest = np.argsort(distances)
nearest
# 结果展示,对索引下标排序
# array([8, 7, 5, 6, 9, 1, 0, 3, 4, 2])

2.4 定义k值，得出计算结果

k=6

# 获取距离最近的前k个数据
# y_train[i],通过i索引下标获取具体的y值
topK_y = [y_train[i] for i in nearest[:k]]
topK_y
# [1, 1, 1, 1, 1, 0]

# 统计每个y值出现的次数
from collections import Counter
votes = Counter(topK_y)
votes
# Counter({1: 5, 0: 1})

# 获取出现次数最多的那个y的取值
predict_y = votes.most_common(1)[0][0]
predict_y
# 1
votes.most_common(1)
# [(1, 5)]

2.5 K-近邻算法的特点

• knn算法没有得到模型，它是机器学习中唯一一个不需要训练过程的算法

• 没有模型的算法

• 为了和其他算法统一，可以认为数据集就是模型本身

3、sklearn中knn算法的应用

3.1 在sklearn中实现KNN算法

from sklearn.neighbors import KNeighborsClassifier

# 创建knn算法的分类器实例
# n_neighbors=6,指定选取邻居的个数
knn_classifier = KNeighborsClassifier(n_neighbors=6)

# 拟合训练数据
knn_classifier.fit(X_train,y_train)

# 将样本维度变为二维,X_train,y_train为二维数组
x1 = x.reshape(1, -1)
x1
# array([[8.09360732, 3.36573151]])

# 利用knn算法进行预测
y_predict = knn_classifier.predict(x1)

# 得出预测结果
y_predict[0]
# 1

3.2  模仿Sklearn重新整合前面的代码

整合为python代码，记做：knn.py

import numpy as np
from math import sqrt
from collections import Counter

class KNNClassifier:
  def __init__(self, k):
      """初始化kNN分类器"""
      assert k >= 1, "k must be valid"
      self.k = k
      self._X_train = None
      self._y_train = None

  def fit(self, X_train, y_train):
      """根据训练数据集X_train和y_train训练kNN分类器"""
      assert X_train.shape[0] == y_train.shape[0], \
          "the size of X_train must be equal to the size of y_train"
      assert self.k <= X_train.shape[0], \
          "the size of X_train must be at least k."

      self._X_train = X_train
      self._y_train = y_train
      return self

  def predict(self, X_predict):
      """给定待预测数据集X_predict，返回表示X_predict的结果向量"""
      assert self._X_train is not None and self._y_train is not None, \
              "must fit before predict!"
      assert X_predict.shape[1] == self._X_train.shape[1], \
              "the feature number of X_predict must be equal to X_train"

      y_predict = [self._predict(x) for x in X_predict]
      return np.array(y_predict)

  def _predict(self, x):
      """给定单个待预测数据x，返回x的预测结果值"""
      assert x.shape[0] == self._X_train.shape[1], \
          "the feature number of x must be equal to X_train"

      distances = [sqrt(np.sum((x_train - x) ** 2))
                   for x_train in self._X_train]
      nearest = np.argsort(distances)

      topK_y = [self._y_train[i] for i in nearest[:self.k]]
      votes = Counter(topK_y)

      return votes.most_common(1)[0][0]

  def __repr__(self):
      return "KNN(k=%d)" % self.k

 将knn.py文件放入到和jupyter的代码相同的目录的knn目录下，利用Jupyter notebook的命令来加载knn.py

#利用%run 加载KNN.py文件
%run knn/knn.py

#创建实例
knn_clf = KNNClassifier(k=6)
#拟合训练集
knn_clf.fit(X_train,y_train)
#预测输入样例
y_predict = knn_clf.predict(x1)
#得出预测结果
y_predict[0]

 4、数据集的划分

4.1 划分数据集的原因

• 将所有的数据都作为训练数据，训练出一个模型

• 每当得到一个新的数据，则计算新数据到训练数据的距离，预测得到新数据的类别

4.2 划分数据集

• 一般将数据中的70%-80%作为训练数据，将剩余的作为测试数据

• 训练数据用于训练模型，测试数据用于判断模型好坏

• 代码：

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

#获取sklearn中的内置数据集
iris = datasets.load_iris()

#获取特征值和目标值
X = iris.data
y = iris.target

#将长度X对应的索引值进行随机排列
shuffle_indexes = np.random.permutation(len(X))

#定义测试机的比例
test_ratio = 0.2
#得到测试集对应的数据量
test_size = int(len(X) * test_ratio)

#获取测试集的索引和训练集的索引
test_indexes = shuffle_indexes[:test_size]
train_indexes = shuffle_indexes[test_size:]

#获取训练数据集
X_train = X[train_indexes]
y_train = y[train_indexes]

#获取测试数据集
X_test = X[test_indexes]
y_test = y[test_indexes]

 4.3 sklearn中的train_test_split

from sklearn.model_selection import train_test_split
# test_size=0.2,可以指定比例,也可以指定数量
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2)

• 在模型训练中，会将数据划分为训练集和测试集，目的是为了验证模型效果

• 在sklearn中可以通过sklearn.model_selection中train_test_split函数完成训练集测试集的划分

5 分类算法的评估

5.1如何评估分类算法？

• 利用训练好的模型使用测试集的特征值进行预测

• 将预测结果和测试集的目标值比较，计算预测正确的百分比

• 这个百分比就是准确率 accuracy， 准确率越高说明模型效果越好

import numpy as np
from sklearn import datasets

#加载鸢尾花数据
iris = datasets.load_iris()

 使用SKlearn的KNeighborsClassifier进行分类预测

from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
#训练集 测试集划分
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2)
# 创建KNN分类器对象 近邻数为6
knn_clf = KNeighborsClassifier(n_neighbors=6)
#训练集训练模型
knn_clf.fit(X_train,y_train)
#使用训练好的模型进行预测
y_predict = knn_clf.predict(X_test)



# 计算准确率：
sum(y_predict==y_test)/y_test.shape[0]

• 分类算法可以通过计算准确率（accuracy_score）来评估模型的好坏

• 准确率比较了模型预测的结果和测试集的真实标签，计算正确预测的结果占所有测试集数据的比例， 比例越高说明模型效果越好

 6、归一化和标准化

6.1 归一化和标准化的计算方法

• 归一化(Normalization)：把所有数据映射到(0,1)之间

  • 计算流程：$$\Large x{scale}=\frac{x-x{min}}{x{max}-x{min}}$$

    • 先计算所有样本的每个特征的最大值和最小值计算出来

    • 用每个样本的特征值减去对应的最小值$$x-x_{min}$$，

    • 再计算最大值和最小值的差值 $$x{max}-x{min}$$

    • 最后将两个结果进行除法操作，得到最终的特征归一化结果$$x_{scale}$$。

  • 适用情况：分布有明显边界

    举例：学生分数0-100有明显边界，图片像素点的值0-255有明显边界。

  • 缺点：受异常值（outlier）影响较大

    观察公式，结果受$$x{max}$$和$$x{min}$$影响严重

• 标准化(standardization)：把所有数据利用均值和标准差进行转换,均值为0,标准差为1

  • $$\Large x{scale}=\frac{x-x{mean}}{S}$$

    • 利用每个特征值减去特征值均值再除以特征值的标准差得到标准化的结果

  • 适用情况：数据分布没有明显边界

  • 优点：不容易受到极端数据值的影响

6.2 代码实现

加载数据

import numpy as np
import matplotlib.pyplot as plt
#加载数据
data = np.loadtxt('data/data1.txt', delimiter='\t')  # 读取数据
#可视化查看数据分布情况
plt.scatter(data[:,0],data[:,1])
plt.show()

 

 数据归一化

data_minmax = data.copy()
#对两列特征进行归一化
min0 = np.min(data_minmax[:,0])
max0 = np.max(data_minmax[:,0])
data_minmax[:,0]=(data_minmax[:,0]-min0)/(max0-min0)
min1 = np.min(data_minmax[:,1])
max1 = np.max(data_minmax[:,1])
data_minmax[:,1]=(data_minmax[:,1]-min1)/(max1-min1)
#数据可视化
plt.scatter(data_minmax[:,0],data_minmax[:,1])
plt.show()

 从上图可以看出，数据经过归一化之后，两个特征的分布都落在0~1之间

标准化实现

data_std = data.copy()
# 计算每一列特征的均值和方差
mean0 = np.mean(data_std[:,0]) 
std0=np.std(data_std[:,0])

mean1 = np.mean(data_std[:,1])
std1=np.std(data_std[:,1])

#对每一列特征分别进行标准化转换
data_std[:,0] = (data_std[:,0]-mean0)/std0
data_std[:,1] = (data_std[:,1]-mean1)/std1

#绘图显示
plt.scatter(data_std[:,0],data_std[:,1])
plt.show()

 6.3 sklearn中的归一化API

• 在sklearn中 提供了归一化和标准化的相关API

  • from sklearn.preprocessing import MinMaxScaler

  • from sklearn.preprocessing import StandardScaler

• sklearn中的归一化API的使用方法

  • Scalar类中有三个方法 fit,transform,fit_transform

  • 调用fit方法时会计算每个特征关键信息（均值，标准差，极值等）并保存

  • 调用transform时，会使用fit方法保存的关键信息（均值，标准差，极值等）进行归一化/标准化转换

  • fit_transform, 相当于fit 和 transform一起调用

• 训练集和测试集的归一化

  • 是否要对训练数据和测试数据分别做归一化/标准化操作？

  • 利用训练集得到均值和方差:

    • X_train.fit()

  • 训练集和测试集均利用训练集得到的均值和方差来进行归一化处理

    • 调用transform的时候，使用训练集的关键信息（均值，方差，极值等）进行归一化/标准化进行转换

    • x_test-mean_train/std_train

  • 不能使用 X_test.fit()

    • 测试数据的目的是为了模拟真实环境，真实环境下很有可能无法计算均值和方差（仅预测一个样本）

• 代码实现：

import numpy as np
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data
y = iris.target

# 划分训练集和测试集,random_state=1,指定随机数种子为1,数据不再随机
from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=1)

#进行归一化处理
from sklearn.preprocessing import MinMaxScaler
mmScaler = MinMaxScaler()
mmScaler.fit(X_train)


#转换训练集和测试集
X_train1 = mmScaler.transform(X_train)
X_test1 = mmScaler.transform(X_test)

#对比准确率
from sklearn.neighbors import KNeighborsClassifier
knn_clf = KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(X_train1,y_train)
knn_clf.score(X_test1,y_test)

 7、超参数与交叉验证

7.1 超参数的概念

• 超参数概念：

  在前面案例中，介绍knn算法时，k的取值为随意定义，但传什么值才是最优的呢，这样的问题在机器学习中就是超参数问题。

  定义：超参数就是在运行机器学习算法之前需要指定值的参数

• 超参数和模型参数概念对比：

  超参数：在算法运行前需要指定的参数

  模型参数：算法过程中学习的参数（后面介绍到其它算法时再详细介绍）

  • knn算法中没有模型参数

• knn中的k就是典型的超参数

• 寻找最优的超参数

  • 领域知识：在不同的知识领域中，最优的超参数值不一样

  • 经验数值：在处理问题时，存在一些较好的经验数值，可以借鉴。通常机器学习中会对超参数设置默认数值，这个值即为经验数值。sklearn中knn算法中的k值默认为5。

  • 实验搜索：在处理具体问题中，经验数值不适用，则需要使用此项操作，来得到不同的超参数。

7.2 SKlearn中的超参数搜索与交叉验证

• 什么是网格搜索(Grid Search)

• Sklearn中寻找最佳的超参数的组合的过程称为网格搜索

• 什么是交叉验证(cross validation)

  • 交叉验证：将拿到的训练数据，分为训练和验证集。以下图为例：

    • 将数据分成10份，其中一份作为验证集(k折交叉验证)

    • 经过10次(组)的测试，每次都更换不同的验证集。即得到10组模型的结果，取平均值作为最终结果。又称10折交叉验证。

案例：使用GridSearchCV对鸢尾花案例进行调优：

from sklearn.model_selection import train_test_split,GridSearchCV
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import load_iris

# 1、获取数据集
iris = load_iris()
# 2、数据基本处理 -- 划分数据集
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)
# 3、特征工程：标准化
# 实例化一个转换器类
transfer = StandardScaler()
# 调用fit_transform
x_train = transfer.fit_transform(x_train)
x_test = transfer.transform(x_test)
# 4、KNN预估器流程
#  4.1 实例化预估器类
estimator = KNeighborsClassifier()

# 4.2 模型选择与调优——网格搜索和交叉验证
# 准备要调的超参数
param_dict = {"n_neighbors": [1, 3, 5],'weights':["uniform","distance"]}
estimator = GridSearchCV(estimator, param_grid=param_dict, cv=3)
# 4.3 fit数据进行训练
estimator.fit(x_train, y_train)
# 5、评估模型效果
# 方法a：比对预测结果和真实值
y_predict = estimator.predict(x_test)
print("比对预测结果和真实值：\n", y_predict == y_test)
# 方法b：直接计算准确率
score = estimator.score(x_test, y_test)
print("直接计算准确率：\n", score)

查看 交叉验证的最终结果

print("在交叉验证中验证的最好结果：\n", estimator.best_score_)
print("最好的参数模型：\n", estimator.best_params_)