KNN算法(东拼西凑版本)

0.KNN是什么

KNN算法中文名称叫做K近邻算法，是众多机器学习算法里面最基础入门的算法。它是一个有监督的机器学习算法，既可以用来做分类任务也可以用来做回归任务。KNN算法的核心思想是未标记的样本的类别，由距离他最近的K个邻居投票来决定。

K近邻法使用的模型，实际上是特征空间的划分。模型由三个基本要素决定：

• 距离度量
• k值
• 分类决策规则

其中两个实例点之间的距离反映了相似程度。一般来说使用欧氏距离来计算。

1.算法流程

假设X_test为待标记的样本，X_train为已标记的样本数据集：

1、求距离：遍历X_train中的所有样本，计算每个样本与X_test的之间的距离(一般为欧式距离)。并且把距离保存在一个distince 的数组中。

2、排序：对distince数组进行排序，取距离最近的K个点。记作X_knn。

3、统计：在X_knn中统计每个类别的个数，既class0在X_knn中有几个样本，class1在X_knn中有几个样本等。

4、投票：待标记样本的类别就是X_knn中样本个数最多的那个类别。

2.算法实现

代码实现：

###1.准备数据

import numpy as np
import matplotlib.pyplot as plt

# raw_data_x是特征，raw_data_y是标签，0为良性，1为恶性
raw_data_X = [[3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343853454, 3.368312451],
              [3.582294121, 4.679917921],
              [2.280362211, 2.866990212],
              [7.423436752, 4.685324231],
              [5.745231231, 3.532131321],
              [9.172112222, 2.511113104],
              [7.927841231, 3.421455345],
              [7.939831414, 0.791631213]
             ]
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)

# 将数据可视化
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = 'Tumor Size')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = 'Time')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.axis([0,10,0,5])
plt.show()

###2.求距离：求点x到数据集中每个点的距离，首先计算距离，使用欧氏距离

from math import sqrt

distances = []  # 用来记录x到样本数据集中每个点的距离
for x_train in X_train:
    d = sqrt(np.sum((x_train - x) ** 2))
    distances.append(d)
    
# 使用列表生成器，一行就能搞定，对于X_train中的每一个元素x_train都进行前面的运算，把结果生成一个列表
distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]

distances

输出：
[5.611968000921151,
 6.011747706769277,
 7.565483059418645,
 5.486753308891268,
 6.647709180746875,
 1.9872648870854204,
 3.168477291709152,
 0.8941051007010301,
 0.9830754144862234,
 2.7506238644678445]

###3.排序：要找到最小的距离，要知道距离最小的k个点是在样本集中的位置
nearest = np.argsort(distances)
nearest

输出：
array([7, 8, 5, 9, 6, 3, 0, 1, 4, 2])

###4.选k值

k = 6
topK_y = [y_train[i] for i in nearest[:k]]
topK_y

输出：
[1, 1, 1, 1, 1, 0]

###5.决策
from collections import Counter
votes = Counter(topK_y)
votes

输出：一个字典，原数组中值为0的个数为1，值为1的个数为5
Counter({0:1, 1:5})

# Counter.most_common(n) 找出票数最多的n个元素，返回的是一个列表，列表中的每个元素是一个元组，元组中第一个元素是对应的元素是谁，第二个元素是频次
votes.most_common(1)

输出：
[(1,5)]

predict_y = votes.most_common(1)[0][0] 
predict_y

输出：
1

工程代码封装：

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

class kNNClassifier:

    def __init__(self, k):
        """初始化分类器"""
        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):
        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]
        votes = Counter(topK_y)
        return votes.most_common(1)[0][0]

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

%run myAlgorithm/kNN.py

knn_clf = kNNClassifier(k=6)
knn_clf.fit(X_train, y_train)
X_predict = x.reshape(1,-1)
y_predict = knn_clf.predict(X_predict)
y_predict

输出：
array([1])

很明显KNN算法的时间复杂度为O(DNN)。其中D为维度数，N为样本总数。从时间复杂度上我们可以很清楚的就知道KNN非常不适合高维度的数据集，容易发生维度爆炸的情况。同时我们也发现了一个问题在关于K的选择上面，我们一般也要选择K的值应该尽量选择为奇数，并且不要是分类结果的偶数倍，否则会出现同票的情况。我们到底应该怎么去选择K的大小比较合适呢？答案是交叉验证。交叉验证指的是将训练数据集进一步分成训练数据和验证数据，选择在验证数据里面最好的超参数组合，也就是调参。参数一般分为模型参数和超级参数。模型参数是需要我们通过不断的调整模型和超参数训练得到的最佳参数。而超参数则是我们人为手动设定的值。像在KNN中超参数就是K的值。我们可以通过交叉验证的方式，选择一组最好的K值作为模型最终的K值。

3.sklearn 中的KNN

##流程：训练数据集 -> 机器学习算法 -fit-> 模型 输入样例 -> 模型 -predict-> 输出结果

from sklearn.neighbors import KNeighborsClassifier

# 创建kNN_classifier实例
kNN_classifier = KNeighborsClassifier(n_neighbors=6)

# kNN_classifier做一遍fit(拟合)的过程，没有返回值，模型就存储在kNN_classifier实例中
kNN_classifier.fit(X_train, y_train)

# kNN进行预测predict，需要传入一个矩阵，而不能是一个数组。reshape()成一个二维数组，第一个参数是1表示只有一个数据，第二个参数-1，numpy自动决定第二维度有多少
y_predict = kNN_classifier.predict(x.reshape(1,-1))
y_predict

输出：
array([1])

参数及方法说明：

class 
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’, metric_params=None, n_jobs=None, **kwargs)

方法名	含义
fit(X, y)	使用X作为训练数据，y作为目标值（类似于标签）来拟合模型。
get_params([deep])	获取估值器的参数。
neighbors([X, n_neighbors, return_distance])	查找一个或几个点的K个邻居。
kneighbors_graph([X, n_neighbors, mode])	计算在X数组中每个点的k邻居的（权重）图。
predict(X)	给提供的数据预测对应的标签。
predict_proba(X)	返回测试数据X的概率估值。
score(X, y[, sample_weight])	返回给定测试数据和标签的平均准确值。
set_params(**params)	设置估值器的参数。

4.注意点

1、大数吞小数
　　在进行距离计算的时候，有时候某个特征的数值会特别的大，那么计算欧式距离的时候，其他的特征的值的影响就会非常的小被大数给覆盖掉了。所以我们很有必要进行特征的标准化或者叫做特征的归一化。

2、如何处理大数据量
　　一旦特征或者样本的数目特别的多，KNN的时间复杂度将会非常的高。解决方法是利用KD-Tree这种方式解决时间复杂度的问题，利用KD树可以将时间复杂度降到O(logDNN)。D是维度数，N是样本数。但是这样维度很多的话那么时间复杂度还是非常的高，所以可以利用类似哈希算法解决高维空间问题，只不过该算法得到的解是近似解，不是完全解。会损失精确率。

3、怎么处理样本的重要性
　　利用权重值。我们在计算距离的时候可以针对不同的邻居使用不同的权重值，比如距离越近的邻居我们使用的权重值偏大，这个可以指定算法的weights参数来设置。

待完善...