机器学习算法总结_K近邻.doc

第一章 k近邻 1.1 K近邻简介 k近邻（k-Nearest Neighbor，k-NN）是一种基本的、有监督学习的分类方法，于1968年由Cover和Hart提出，其用于判断某个对象的类别。k近邻的输入为对象特征向量，对应于特征空间上的点；输出为对象的类别。 k近邻算法实例引入： 图1.1 k近邻实例 如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。 所谓物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手。要判别上图中那个绿色的圆是属于哪一类数据，只需根据它周围的邻居即可。但一次性看多少个邻居呢？从上图中，你还能看到： 如果k=3，绿色圆点的最近的3个邻居（欧式距离）是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。 上面这个小例子基本上体现了k近邻算法的三个基本要素：确定度量方式（欧式距离）、选着k值（2 or 3）、分类决策规则（少数服从多数）。 下面，给出k近邻算法的数学表述： 输入：训练数据集 其中，为实例的特征向量，为实例的类别，;实例特征向量; 输出：实例所属的类。 （1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作； （2）在中根据分类决策规则（如多数表决）决定x的类别y： （1-1） 其中，为指示函数，即当时为1,否则为0。 k近邻的特殊情况是k=1的情形，称为最近邻算法，对于输入的对象（特征向量）x，最近邻法将训练数据集中于x最近邻点所属的类作为x的类。 1.2 K近邻模型建立 建立数学模型的过程实质就是确定三个基本要素的过程。 1.2.1 距离度量方式的确定 样本空间（特征空间）中两个对象的距离是它们相似程度的量化反映。k近邻模型的特征空间可被抽象为n维的向量空间R，现在两个对象之间的距离就可转化为两个向量之间的距离，这样研究起来就方便多了。在k近邻模型中，计算向量之间距离的公式列举如下： （1） 欧式距离： （1-2） （2）曼哈顿距离： （1-3） （3）切比雪夫距离： （1-4） （4）闵可夫斯基距离： （1-5） 特点：为综合性的公式 。 （5）马氏距离： 　　 （1-6） 特点：可排除对象间的相关性。 （6）相关距离： （1-7） （7）夹角余弦距离和Tonimoto系数： （I）夹角余弦距离： （1-8）