KNN算法入门_cosine knn

近邻算法介绍

KNN是数据挖掘算法中最简单的一种算法，该算法的核心思想是通过比较K个最近的样本的距离来度量样本的相似程度，找到K个最近的样本，通过这K个样本的类别，确定要比较的新样本的类别，该算法最重要的就是比较两两之间的距离，故而在样本和特征较大的情况下，计算复杂度高，比较适合少量数据。

距离计算方法

欧式距离

二维平面上的两点$a(x_1,y_1)$和$b(x_2,y_2)$之间的距离:
D_{(x, y)} = $\sqrt{(x_1-y_1{)}^2+(x_2-y_2{)}^2}$

多维空间上的两点$a(x_1,...,y_n)$和$b(x_2,...,y_n)$之间的距离:
D_{(x, y)} = $\sqrt{(x_1-y_1{)}^2+...+(x_n-y_n{)}^2}$

也可以表示为以下形式：

D_{(x, y)} = $\sqrt{{\sum }_i^n(x_i-y_i{)}^2}$

余弦相似度

余弦相似度可以求两个样本之间的余弦值
$\cos \theta$=$\frac{\vec{a}\cdot \vec{b}}{|a|\ast |b|}$

曼哈顿距离

D_{(x, y)} = ${\sum }_i^n|x_i-y_i|$

Python代码实现

import numpy as np
from collections import Counter
X = np.random.random_sample((100, 3))
y = np.random.randint(low=0, high=3, size=100, dtype=np.int)
test_rate = 0.25
random_list = np.random.permutation(100)
train_index = random_list[:int((1-test_rate) * X.shape[0])]
test_index = random_list[int((1-test_rate) * X.shape[0]):]
X_train = X[train_index]
y_train = y[train_index]
X_test = X[test_index]
y_test = y[test_index]
d = [((X_train - x) ** 2).sum(axis=1) for x in X_test]
p_label = []
for i in d[:]:
    sort_index = np.argsort(i)
    max_index = sort_index[-5:]
    counter = Counter(y_train[max_index])
    p_label.append(counter.most_common(1)[0][0])
zhunquelv = sum(p_label == y_test) / 25

由于以上是造的数据，所以准确率不高，真实环境中的数据类同比例会比较高，预测准确率会大幅提升，由以上的过程可以看出，这个算法还是存在很大的问题，计算距离的时候会把预测数据和每个样本都计算一遍距离，对于大量数据的时候，性能会较低。

KNN除了可以做分类外，还可以预测连续型数据，把训练数据最大的K个数做平均，就可以预测出答案，除此之外，在做分类时，还可以依据所选的K个值，做加权，可以用预测的倒数来比较到底应该属于哪个类别，可能我们预测的是类别A，但是虽然类别A是我们选择的K中的出现最多的，但是他们离得比较远，所以按照权值可能结果不一样，这就要看数据是否强依赖距离了，这也体现了距离的思想