K 近邻算法：
输入：训练数据集 T = {(x1,y1), (x2,y2),...,(xn,yn)} 其中，xi为属于R的实例特征向量，yi是属于{c1,c2,...,ck}的实例类别实例特征向量为xi。
输出：实例 x 所属的类 y。步骤：
1.根据给定的距离度量，在训练集 T 中找出与 x 最近邻的 k 个点，涵盖这 k 个点的 x 的领域记作 Nk(x);2.在 Nk(x) 中根据分类决策规则（如多数表决）决定 x 的类别 y；
K 近邻算法的伪代码：对未知类别属性的数据集中的点进行如下的操作
1.计算已知类别的数据集中的点与当前点之间的距离(欧几里得距离)；2.按照距离递增次序排序；3.选取与当前点距离最小的 K 个点；4.确定前 K 个点所在类别的出现频率；5.返回前 K 个点出现频率最高的类别作为当前点的预测分类。
python实现KNN算法
# 自编程实现 KNN 算法
def knn_self(data, dataset, label, k):
leth, _ = dataset.shape
dist_key = {}
for i in range(leth):
tmp = np.sqrt(np.sum(np.square(data - dataset[i])))
dist_key[str(tmp)] = label[i][0]
dist_key = sorted(dist_key.items(),key=operator.itemgetter(0),reverse=False) # 对距离进行排序
rate = []
print(dist_key)
for j in range(k):
distance, lab = dist_key[j]
rate.append(lab)
pre = {}
for x in set(rate):
p = rate.count(x)
pre[str(x)] = p
pre_x = sorted(pre.items(),key=operator.itemgetter(1),reverse=True)
print(pre_x)
prediction, rate = pre_x[0]
return [prediction]
sklearn实现knn
def sk_knn(data_test, dataset, label, k):
model_knn = KNeighborsClassifier(n_neighbors=k)
model_knn.fit(dataset, label)
predtion = model_knn.predict(data_test)
return predtion
常用参数解释：
class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,
weights=’uniform’,
algorithm=’auto’,
leaf_size=30,p=2,
metric=’minkowski’,
metric_params=None,
n_jobs=1, **kwargs)
n_neighbors：就是选取最近的点的个数：kleaf_size：这个是构造树的大小，值一般选取默认值即可，太大会影响速度。n_jobs ：默认值1，选取-1占据CPU比重会减小，但运行速度也会变慢，所有的core都会运行。
dataset = np.array([[5, 4], [9, 6], [4, 7], [2, 3], [8, 1], [7, 2]])
label = np.array([[1], [1], [1], [-1], [-1], [-1]])
data = np.array([[5, 3]])
pre_self = knn_self(data, dataset, label, 4)
print('The pretion of self model is:', pre_self)
pre_sk = sk_knn(data, dataset, label, 4)
print('The pretion of sklearn model is:', pre_sk)
[('1.0', 1), ('2.23606797749979', -1), ('3.0', -1), ('3.605551275463989', -1), ('4.123105625617661', 1), ('5.0', 1)]
[('-1', 3), ('1', 1)]
The pretion of self model is: ['-1']
The pretion of sklearn model is: [-1]
注意：
1.KNN算法的结构复杂度主要体现与K值的选择： K值越小，模型就越复杂，从而容易产生过拟合； K值越大模型越简单，但是学习的近似误差也就越大。 2.KNN算法的不足： 假如某些类的样本容量很大，而其他类的样本容量很小，即已知样本数量不均匀时，有可能当输入一个和样本容量小的同类型的数据时，该样本的K个邻居中大容量类的样本占多数，就会造成误分类；对此问题的解决办法是：加权平均于距离。
