KNN分类算法

k近邻算法(knn,knearestneighbor)算法基本介绍•k近邻的非正式描述，就是给定一个样本集exset，样本数为M，每个样本点是N维向量，对于给定目标点d，d也为N维向量，要从exset中找出与d距离最近的k个点(k=N)，当k=1时，knn问题就变成了最近邻问题。最原始的方法就是求出exset中所有样本与d的距离，进行按出小到大排序，取前k个即为所求，但这样的复杂度为O(N)，当样本数大时，效率非常低下.算法描述•该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的K篇文本，根据这K篇文本所属的类别判定新文本所属的类别•右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。算法描述•算法分为以下几步：一、:根据特征项集合重新描述训练文本向量二、:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示三、:在训练文本集中选出与新文本最相似的K个文本，计算公式为：算法描述•其中，K值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整K值，一般初始值定为几百到几千之间。（这里K采取随机取值）•四、:在新文本的K个邻居中，依次计算每类的权重，计算公式如下：•其中，x为新文本的特征向量，Sim(x,di)为相似度计算公式，与上一步骤的计算公式相同，而y(di,Cj)为类别属性函数，即如果di属于类Cj，那么函数值为1，否则为0。•五、:比较类的权重，将文本分到权重最大的那个类别中。运行结果•训练及测试样例