ML学习笔记(二)

KNN-K_means

Posted by QIY on June 4, 2020

Machine Learning 的学习需稳扎稳打

SVM

KNN

1 概述

设一个最小距离样本个数K=5,Xq内3-,2+,那么Xq为-。

原理就是当预测一个新的值x的时候,根据它距离最近的K个点是什么类别来判断x属于哪个类别。

KNN算法是有监督学习中的分类算法,它看起来和另一个机器学习算法Kmeans有点像(Kmeans是无监督学习算法)。

2 优缺点

优点

1.简单易用,相比其他算法,KNN算是比较简洁明了的算法。即使没有很高的数学基础也能搞清楚它的原理。

2.模型训练时间快,上面说到KNN算法是惰性的,这里也就不再过多讲述。

3.预测效果好。

4.对异常值不敏感

缺点

1.对内存要求较高,因为该算法存储了所有训练数据

2.预测阶段可能很慢

3.对不相关的功能和数据规模敏感

3 流程(百度百科)

  1. 准备数据,对数据进行预处理。 [4] 

  2. 选用合适的数据结构存储训练数据和测试元组。 [4] 

  3. 设定参数,如k。 [1] 

4.维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列。 [4] 

  1. 遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L 与优先级队列中的最大距离Lmax。 [2] 

  2. 进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L < Lmax,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列。 [3] 

  3. 遍历完毕,计算优先级队列中k 个元组的多数类,并将其作为测试元组的类别。 [2] 

8. 测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k 值。

4 K-means

K-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据他们的属性分为k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。其聚类过程可以用下图表示:

        如图所示,数据样本用圆点表示,每个簇的中心点用叉叉表示。(a)刚开始时是原始数据,杂乱无章,没有label,看起来都一样,都是绿色的。(b)假设 数据集可以分为两类,令K=2,随机在坐标上选两个点,作为两个类的中心点。(c-f)演示了聚类的两种迭代。先划分,把每个数据样本划分到最近的中心点 那一簇;划分完后,更新每个簇的中心,即把该簇的所有数据点的坐标加起来去平均值。这样不断进行”划分—更新—划分—更新”,直到每个簇的中心不在移动为 止。

5 KNN和K-Means的区别

KNN

1.KNN是分类算法;

2.监督学习;

3.喂给它的数据集是带label的数据,已经是完全正确的数据;

4.没有明显的前期训练过程,属于memory-based learning;

K的含义:来了一个样本x,要给它分类,即求出它的y,就从数据集中,在x附近找离它最近的K个数据点,这K个数据点,类别c占的个数最多,就把x的label设为c;

K-Means

1.K-Means是聚类算法;

2.非监督学习;

3.喂给它的数据集是无label的数据,是杂乱无章的,经过聚类后才变得有点顺序,先无序,后有序;

4.有明显的前期训练过程;

K的含义:K是人工固定好的数字,假设数据集合可以分为K个簇,由于是依靠人工定好,需要一点先验知识;

相似点:都包含这样的过程,给定一个点,在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法,一般用KD树来实现NN。

参考:https://blog.csdn.net/iamqianrenzhan/article/details/91488700