机器学习19：k近邻(kNN)模型
机器学习19：k近邻(kNN)模型
1，k近邻(k-Nearest Neighbor)：
k近邻(k-NearestNeighbor)学习是一种最简单的监督学习算法，工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最近的k个训练样本，然后基于这k个邻居的信息来进行预测。通常，在分类任务中使用投票法，即选择这k个样本职工出现最多的类别标记作为预测结果；在回归任务中可以使用平均法，即将这k个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近来进行加权平均或者加权投票，距离越远的样本权重越大。
Knn有一个独特的特征：它似乎没有显式的训练过程。事实上knn是懒惰学习(lazylearning)的著名代表，这类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；对应地，那些在训练阶段就对样本进行学习处理的方法称为急切学习(eagerlearning)。
显然，k是一个重要的超参数。另外，采用不同的距离计算方式，则可以找出的近邻可能由于显著的差异，总而也会导致分类结果又显著不同。
给定测试样本x，若其最近邻的样本为z，则最近邻分类器出错的概率就是x与z类别标记不同的概率，即：
贝叶斯最优分类器的结果记为P_B，相关论文证明KNN算法的误差率为：
可见，k近邻分类器虽然简单，但他的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。然而这基于一个重要假设：任意测试样本x附近任意小的δ距离范围内总能找到一个测试样本，即训练样本的采样密度足够大(密采样，dense sample)。然而这个假设在现实中很难满足，假设δ=0.001，单个属性就需要1000个样本，当有10(n)个甚至更多的属性时，需要10^(3*n)个样本，这样的数据量在大数据时代也是很可怕的天文数字，再加上距离的计算，这对硬件的要求是极高的，因此现实中很难达到：k近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。
2，KD-Tree(k-dimensionaltree)：
2.1，KD-Tree原理：
KD-Tree是一种能维护高维数据空间的结构,主要支持几个操作：1).插入点；
2).进行距离查询（例如：查询距离某个点第k近的点)。
KD-Tree 是一棵二叉搜索树。与普通的二叉搜索树一样，它具有左儿子比父亲小，右儿子比父亲大的特点。但是，比较点的大小是没有实际意义的，因此，KD-Tree并不是整体比较点的大小，而是比较某一维的大小。
Kd-Tree和二叉搜索树(BST)的区别：BST的每个节点存储的是值，而Kd-Tree的根节点和中间节点存储的是对某个维度的划分信息，只有叶节点里才是存储的值.
2.2，KD-Tree与knn、DBSCAN：
KD Tree可以用于KNN算法中计算最近邻的快速、便捷构建方式，时间复杂度是O(n1-1/k+m) ，m:每次要搜索的最近点个数；还可以用于密度聚类(DBSCAN)算法中计算样本和核心对象之间距离来获取最近邻。
当样本数据量少的时候，我们可以使用brute这种暴力的方式进行求解最近邻， 即计算到所有样本的距离。但是当样本量比较大的时候，直接计算所有样本的距 离，工作量有点大，所以在这种情况下，我们可以使用kdtree来快速的计算。
KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用方差最大的第k维特征nk作为根节点。对于这个特征，选择取值的中位数nkv作为样本的划 分点，对于小于该值的样本划分到左子树，对于大于等于该值的样本划分到右子 树，对左右子树采用同样的方式找方差最大的特征作为根节点，递归即可产生KD树。
2.3，KD-tree查找最近邻样本:
当我们生成KD树以后，就可以去预测测试集里面的样本目标点了。对于一个目 标点，我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在 这个超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形 体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话 就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一 个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。
3，kNN与K-means比较：
kNN是分类算法，监督算法，而K-means是聚类算法，非监督算法。
4，code
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier#KNN
from sklearn.preprocessing import label_binarize
from sklearn import metrics
import warnings
warnings.filterwarnings("ignore") # 拦截异常
# 1，加载数据：
names = ['sepal length', 'sepal width', 'petal length', 'petal width', 'cla']
df = pd.read_csv('../DataSets/iris.data', header=None, names=names)
df['cla'].value_counts()
print(df.columns.values)
df.head()
# 2,数据清洗：
def parseRecord(record):
result=[]
r = zip(names,record)
for name,v in r:
if name == 'cla':
if v == 'Iris-setosa':
result.append(1)
elif v == 'Iris-versicolor':
result.append(2)
elif v == 'Iris-virginica':
result.append(3)
else:
result.append(np.nan)
else:
result.append(float(v))
return result
data = df.apply(lambda r: parseRecord(r), axis=1, broadcast='None') # 数据转换为数字
data = df.dropna(how='any') # 异常数据删除
X = data[df.columns.values[0:-1]]
Y = data[df.columns.values[-1]]
X_train,X_test,Y_train,Y_test = train_test_split(X, Y, test_size=0.4, random_state=0)
print ("原始数据条数:%d；训练数据条数:%d；特征个数:%d；测试样本条数:%d" % (len(X), len(X_train), X_train.shape[1], X_test.shape[0]))
# 3,模型训练：kNN
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, Y_train)
y_test_hot = label_binarize(Y_test,classes=(1,2,3)) # 将正确的数据转换为矩阵形式
knn_y_score = knn.predict_proba(X_test) # 评分
knn_fpr, knn_tpr, knn_threasholds = metrics.roc_curve(y_test_hot.ravel(),knn_y_score.ravel()) # 计算roc的值
knn_auc = metrics.auc(knn_fpr, knn_tpr) # 计算auc的值
print ("KNN算法R值：", knn.score(X_train, Y_train))
print ("KNN算法AUC值：", knn_auc)
knn_y_predict = knn.predict(X_test) # 预测
knn_y_predict本文分享自 MiningAlgorithms 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！