机器学习算法：k近邻

前言：

最近在研究机器学习，过程中的心得体会会记录到blog里，文章与代码均为原创。会不定期龟速更新。注意这不是教程，但是估计能帮到一些刚入门的同学。

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

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

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

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

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

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

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

using System;

namespace MachineLearning
{
    /// <summary>
    /// 数据向量
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class DataVector<T>
    {
        /// <summary>
        /// N维数据
        /// </summary>
        public T[] Data { get; private set; }
        /// <summary>
        /// 分类标签
        /// </summary>
        public string Label { get; set; }

        /// <summary>
        /// 构造
        /// </summary>
        /// <param name="dimension">数据维度</param>
        public DataVector(int dimension)
        {
            Data = new T[dimension];
        }
        
        public int Dimension
        {
            get { return this.Data.Length; }
        }
    }
}

然后是核心算法：

using System;
using System.Collections.Generic;

namespace MachineLearning
{
    /// <summary>
    /// k近邻法(k=1)
    /// </summary>
    public class NearestNeighbour
    {
        private List<DataVector<double>> m_TrainingSet;
        
        /// <summary>
        /// 训练
        /// </summary>
        /// <param name="trainingSet"></param>
        public void Train(List<DataVector<double>> trainingSet)
        {
            m_TrainingSet = trainingSet;
        }

        /// <summary>
        /// 分类
        /// </summary>
        /// <param name="vector"></param>
        /// <returns></returns>
        public string Classify(DataVector<double> vector)
        {
            double minDist = double.PositiveInfinity;
            int targetIndex = -1;
            for(int i = 0;i < m_TrainingSet.Count;i++)
            {
                //计算距离
                double distance = ComputeDistance(vector, m_TrainingSet[i], minDist);

                //找最小值
                if(distance < minDist)
                {
                    minDist = distance;
                    targetIndex = i;
                }
            }
            
            return m_TrainingSet[targetIndex].Label;
        }
    
        /// <summary>
        /// 计算距离
        /// </summary>
        /// <param name="v1"></param>
        /// <param name="v2"></param>
        /// <param name="minValue"></param>
        /// <returns></returns>
        private double ComputeDistance(DataVector<double> v1, DataVector<double> v2, double minValue = double.PositiveInfinity)
        {
            double distance = 0.0;
            minValue = minValue * minValue;
            for(int i = 0;i < v1.Data.Length;++i)
            {
                double diff = v1.Data[i] - v2.Data[i];
                distance += diff * diff;
            
                //如果当前累加的距离已经大于给定的最小值，不用继续计算了
                if(distance > minValue)
                    return double.PositiveInfinity;
            }

            return Math.Sqrt(distance);
        }
    }
}

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

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

本文出自 “兔子窝” 博客，请务必保留此出处http://boytnt.blog.51cto.com/966121/1569629