前言：

最近在研究机器学习，过程中的心得体会会记录到blog里，文章与代码均为原创。会不定期龟速更新，注意这不是正式的教程，因为本人也是初学者，但是估计C#版本的代码能帮到一些刚入门的同学去理解复杂的公式。

------------------------ 我是分割线 ------------------------

k近邻（k-Nearest Neighbor，KNN）算法，应该是机器学习里最基础的算法，其核心思想是：给定一个未知分类的样本，如果与它最相似的k个已知样本中的多数属于某一个分类，那么这个未知样本也属于这个分类。

所谓相似，是指两个样本之间的欧氏距离小，其计算公式为：

其中Xi为样本X的第i个特征。

k近邻算法的优点在于实现简单，缺点在于时间和空间复杂度高。

上C#版代码，这里取k=1，即只根据最相近的一个点确定分类：

首先是DataVector，包含N维数据和分类标签，用于表示一个样本。

usingSystem;namespaceMachineLearning{///<summary>///数据向量///</summary>///<typeparamname="T"></typeparam>publicclassDataVector<T>{///<summary>///N维数据///</summary>publicT[]Data{get;privateset;}///<summary>///分类标签///</summary>publicstringLabel{get;set;}///<summary>///构造///</summary>///<paramname="dimension">数据维度</param>publicDataVector(intdimension){Data=newT[dimension];}publicintDimension{get{returnthis.Data.Length;}}}}

然后是核心算法：

usingSystem;usingSystem.Collections.Generic;namespaceMachineLearning{///<summary>///k近邻法///</summary>publicclassNearestNeighbour{privateintm_K;privateList<DataVector<double>>m_TrainingSet;publicNearestNeighbour(intk=1){m_K=k;}///<summary>///训练///</summary>///<paramname="trainingSet"></param>publicvoidTrain(List<DataVector<double>>trainingSet){m_TrainingSet=trainingSet;}///<summary>///分类///</summary>///<paramname="vector"></param>///<returns></returns>publicstringClassify(DataVector<double>vector){//K=1时可简化处理提高效率if(m_K==1){doubleminDist=double.PositiveInfinity;inttargetIndex=-1;for(inti=0;i<m_TrainingSet.Count;i++){//计算距离doubledistance=ComputeDistance(vector,m_TrainingSet[i],minDist);//找最小值if(distance<minDist){minDist=distance;targetIndex=i;}}returnm_TrainingSet[targetIndex].Label;}else{vardict=newSortedDictionary<double,string>();for(inti=0;i<m_TrainingSet.Count;i++){//计算距离并记录doubledistance=ComputeDistance(vector,m_TrainingSet[i]);dict[distance]=m_TrainingSet[i].Label;}//找最多的Labelvarlabels=newList<string>();intcount=0;foreach(varlabelindict.Values){labels.Add(label);if(++count>m_K-1)break;}returnGetMajorLabel(labels);}}///<summary>///计算距离///</summary>///<paramname="v1"></param>///<paramname="v2"></param>///<paramname="minValue"></param>///<returns></returns>privatedoubleComputeDistance(DataVector<double>v1,DataVector<double>v2,doubleminValue=double.PositiveInfinity){doubledistance=0.0;minValue=minValue*minValue;for(inti=0;i<v1.Data.Length;++i){doublediff=v1.Data[i]-v2.Data[i];distance+=diff*diff;//如果当前累加的距离已经大于给定的最小值，不用继续计算了if(distance>minValue)returndouble.PositiveInfinity;}returnMath.Sqrt(distance);}///<summary>///取多数///</summary>///<paramname="dataSet"></param>///<returns></returns>privatestringGetMajorLabel(List<string>labels){vardict=newDictionary<string,int>();foreach(variteminlabels){if(!dict.ContainsKey(item))dict[item]=0;dict[item]++;}stringlabel=string.Empty;intcount=-1;foreach(varkeyindict.Keys){if(dict[key]>count){label=key;count=dict[key];}}returnlabel;}}}

需要注意的是，计算距离时，数量级大的维度会对距离影响大，因此大多数情况下，不能直接计算，要对原始数据做归一化，并根据重要性进行加权。归一化可以使用公式：value = (old-min)/(max-min)，其中old是原始值，max是所有数据的最大值，min是所有数据的最小值。这样计算得到的value将落在0至1的区间上。

这个算法太简单，暂时不上测试代码了，有时间再补吧。