KNN 算法的原理以及理解
1算法原理
KNN,全称k-NearestNeighbor。
算法的核心思想是:未标记样本的类别由距离其最近的K个邻居投票来决定。
可解决分类或者回归问题。由其思想可以看出,KNN是通过测量不同特征值之间的距离进行分类,而且在决策样本类别时,只参考样本周围k个“邻居”样本的所属类别。因此比较适合处理样本集存在较多重叠的场景,主要用于聚类分析、预测分析、文本分类、降维等,也常被认为是简单数据挖掘算法的分类技术之一。
2 算法的优缺点
优点:
①简单,易于理解,易于实现,无需参数估计,无需训练;
②精度高,对异常值不敏感(个别噪音数据对结果的影响不是很大);
③适合对稀有事件进行分类;
④特别适合于多分类问题(multi-modal,对象具有多个类别标签),KNN要比SVM表现要好.;
缺点:
①对测试样本分类时的计算量大,空间开销大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本;
②可解释性差,无法给出决策树那样的规则;(黑盒模型)
③最大的缺点是当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进;
④消极学习方法。
3 算法的代码
3.1算法的伪代码
如下:
Algorithm KNN(A[n], k)
{
Input: A[n]为N个训练样本的分类特征;
k为近邻个数;
Initialize:
选择A[1]至A[k]作为x的初始近邻;
计算初始近邻与测试样本x间的欧氏距离d(x, A[i]), i=1,2,...k;
按d(x, A[i])从小到大排序;
计算最远样本与x间的距离D,即max{d(x, A[j]) | j=1,2...k};
for(i=k+1; i<n+1; i++)
计算A[i]与x间的距离d(x, A[i]);
if (d(x, A[i]) < D ) then
用A[i]代替最远样本;
按照d(x, A[i])从小到大排序;
计算最远样本与x间的距离D,即max{d(x, A[j]) | j=1,...i};
计算前k个样本A[i]所属类别的概率,i=1,2,...k;
具有最大概率的类别即为样本x的类;
end for
Output: x所属的类别。
}
3.2 算法的代码
后续补充
3.3算法的包以及调参
from sklearn.model_selection import train_test_split feautre_train,feautre_test,label_train,label_test=train_test_split(feature,labels,test_size=0.2) # 指出训练集的标签和特征以及测试集的标签和特征,0.2为参数,对测试集以及训练集按照2:8进行划分 from sklearn.neighbors import KNeighborsClassifier model=KNeighborsClassifier(n_neighbors= 9)
4工程优化以及改进
1:采用Kd_TRee或者BALL_tree的数据结构来优化算法。在数据之间建立关联关系,然后查询关系,免去一一遍历的问题。
算法的复杂度从(DN**2)降低到(O(DNlogN))
2:算法策略的改进。
1:紧邻的规则的改进(增加点的权重,某个半径内的点)
2:距离阈值的测量(欧式距离,余弦距离,曼哈顿距离等)
总结: