k近邻算法（K-Nearest Neighbor，KNN）是机器学习一切算法中实际最简单，最好了解的算法；是一种基本的分类与回归方法，他的输入为实例的特征向量，经过计算新数据与数据特征值之间的间隔，然后选取K（K>=1）个间隔最近的临近数据停止分类判别或回归。假如K=1，那么新数据被简单地分配给起近邻。
对于分类成绩：输入为实例的类别。分类时，对于新的实例，根据其k个近邻的训练实例的类别，经过多数表决方式停止预测。
对于回归成绩：输入为实例的值，对于新的实例，取其k个最近邻的数据的平均值作为预测值。
K近邻算法不具有显示的学习过程，它是直接预测，实践上它是应用训练数据集对特征向量空间停止划分，并且作为划分的模型。
K近邻三要素：k值选择（K值越小，则对应的“学习”误差小，可以照顾到大多数分类，但是预测效果较差，模型较为复杂）、间隔度量（普通运用欧氏间隔最为间隔度量）和分类决策规则（权重）。在实践运用中，k值普通取一个较小的值，通常采用交叉验证来选取最优的K值（就是比较不同的k值在交叉验证中的平均误差率。），然后选择误差最小的那个。
kd树：K近邻算法中如何对训练集停止搜索是个成绩，最直观的方式就是线性扫描（经过计算输入样本与每个训练样本的间隔，来找出最近邻的k个训练样本）。不过该方法在数据训练集很大时，非常耗时。为了处理该方法带来的不足，我们运用kd树来停止代替。
kd树的算法步骤：首先构造根节点；其次反复末尾的操作切分域，最后在一切节点的两个子域中没有样本时结束。
KNeighborsClassifier（KNN分类）的函数原型：sklearn.neighbors.KNeighborsClassifier(n_neigbors=5,weights='unform',algorithm='auto',leaf_size=30,p=2,metric='minkowski',metric_params=None,n_jobs=1,**kwargs)
参数阐明：
n_neighbors: 一个整数，指定k值。
weight：一个字符串或者可调用对象，指定投票权重类型。也就是这些邻居投票可以相反或者不同（uniform：本节点的一切邻居节点的投票权重都相等。distance:本节点的一切邻居节点的投票权重和间隔成反比。callable：一个可调用对象，他传入间隔的数组，前往异样外形的数组）。
algorithm：一个字符串，指定计算最临近的算法（ball_tree: 运用BallTree算法。ke_tree: 运用KDTree算法。brute：运用暴力搜素法。auto：自动决议最合适的算法）。
leaf_size: 一个整数，指定BallTree或者KDTree节点规模，他影响输的构造和查询速度。
metric：一个字符串，指定间隔度量，默以为minkowski间隔。
p:整数值，指定在Minkowski度量上的指数，假如p=1，对应曼哈顿间隔；p=2，对应偶拉间隔。
n_jobs:并行性。默以为-1，表示派发义务到一切计算机的CPU上。
方法阐明：
fit（x, y）:训练模型。
predict（x）:用模型停止预测，前往预测值
score（x, y[,sample_weight]）:前往测试功能得分（测试分数不超过1，但是能够为负数（当预测效果太差的时分），score值越接近1，阐明预测效果越好）。
predict_proba(x)：前往一个数值，数组元素依次是x预测为各个类别的概率值。
kneighbors(x, n_neighbors, return_distance)：前往样本的k近邻点。假如return_distance=True，同时还前往到这些点的间隔。
kneighbors_graph(x, n_neighbors, mode)：前往样本点的衔接图。
代码示例如下：
def load_digits_data():
#运用load_digits
digits = load_digits()
#前往一个元组，元组依次是：训练样本集、测试样本集、训练样本集对应的标签值、测试样本对应的标签值
#这里采用分层采样，保证了测试样本集中各类别样本的比例与原样本中各类别的比例相反。
#假如不采用分层采样，那么最后切分的测试集数据就不是无偏的了
return cross_validation.train_test_split(digits.data, digits.target, test_size=0.25,
random_state=0)
def create_regression_data(n):
x = 5 * np.random.rand(n, 1)
y = np.sin(x).ravel()
y[::5] += 1 * (0.5 - np.random.rand(int(n/5)))
return cross_validation.train_test_split(x, y, test_size=0.25,
random_state=0, stratify=digits.target)
def test_KNerghborsClassifier(*data):
x_train, x_test, y_train, y_test = data
cls = KNeighborsClassifier()
cls.fit(x_train, y_train)
print("KNerghbors training score set is: {:.3f}".format(cls.score(x_train, y_train)))
print("KNerghbors test score set is: {:.3f}".format(cls.score(x_test, y_test)))
x_train, x_test, y_train, y_test = load_digits_data()
test_KNerghborsClassifier(x_train, x_test, y_train, y_test)
#weights参数对预测功能的影响
def test_KNeighborsClassifier_k_w(*data):
#不同的binarize值对测试功能的影响
x_train,x_test,y_train,y_test=data
ks = np.linspace(1, y_train.size, num=100, endpoint=False, dtype='int')
weights = ['uniform', 'distance']
fig=plt.figure()
ax=fig.add_subplot(1,1,1)
for weight in weights:
training_scores=[]
testing_scores=[]
for k in ks:
cls = KNeighborsClassifier(weights=weight, n_neighbors=k)
cls.fit(x_train, y_train)
training_scores.append(cls.score(x_train, y_train))
testing_scores.append(cls.score(x_test, y_test))
## 将对应的结果可视化
ax.plot(ks,training_scores,label="KNeighbors traing score: weight=%s"%weight)
ax.plot(ks,testing_scores,label="KNeighbors test set score: weight=%s"%weight)
ax.legend(loc='best')
ax.set_xlabel("K value")
ax.set_ylabel("score value")
ax.set_ylim(0,1.05)
ax.set_title("KNeighbors")
plt.show()
x_train, x_test, y_train, y_test = load_digits_data()
test_KNeighborsClassifier_k_w(x_train, x_test, y_train, y_test)
test_KNerghborsClassifier(x_train, x_test, y_train, y_test)
上述代码运转后其结果如图：
weights权重参数对KNeighbors中队预测功能的影响
从上述运转结果可以看出，运用uniform投票策略下，分类器随着k的增长，预测波动性下降，这是由于k增大时，输入实例较远的训练集和较近的加权值一样，对预测的功能影响也一样，使得预测值产生错误。而运用distance策略时，其预测值随着k值的增大，表现波动，这是由于distance策略中间隔较远的训练数据加权会越来越小，对预测功能影响也较小。
下面我们来看参数p对预测功能的影响，代码如下：
#参数p对预测功能的影响
def test_KNeighborsClassifier_k_p(*data):
#不同的binarize值对测试功能的影响
x_train,x_test,y_train,y_test=data
ks = np.linspace(1, y_train.size, num=100, endpoint=False, dtype='int')
ps = [1,2,8]
fig=plt.figure()
ax=fig.add_subplot(1,1,1)
for p in ps:
training_scores=[]
testing_scores=[]
for k in ks:
cls = KNeighborsClassifier(p=p, n_neighbors=k)
cls.fit(x_train, y_train)
training_scores.append(cls.score(x_train, y_train))
testing_scores.append(cls.score(x_test, y_test))
## 将对应的结果可视化
ax.plot(ks,training_scores,label="KNeighbors traing score: p=%d"%p)
ax.plot(ks,testing_scores,label="KNeighbors test set score: p=%d"%p)
ax.legend(loc='best')
ax.set_xlabel("K value")
ax.set_ylabel("score value")
ax.set_ylim(0,1.05)
ax.set_title("KNeighbors")
plt.show()
x_train, x_test, y_train, y_test = load_digits_data()
test_KNeighborsClassifier_k_p(x_train, x_test, y_train, y_test)
运转后其结果如下：
从运转结果来看，参数p值的改变对预测功能基本上没有影响或者说影响很小，阐明曼哈顿算法和欧式间隔两者算法对分类器的影响是基本一样的。 |
