一、前言

嗐，知识学多都学杂了，最近总是搞混这两个算法。今天终于有时间来整理一下。

二、算法简介

KNN（K-Nearest Neighbor）是机器学习中的分类算法，它将距离相近的样本点分为同一类，KNN 中的K指的是近邻个数，也就是最近的K个点，根据它距离最近的K个点的类别来判断属于哪个类别。KNN是有标签的

人以群分，物语类聚；近朱者赤，近墨者黑是 KNN 的核心思想。这其实和我们在日常生活中评价一个人是一样的，如果你想要知道一个人是什么样的，那就去找和他关系好的几个人看看对他的评价or看和他关系好的人是什么样子的，就可以大致判断出他是什么样的人了。

而K-means聚类当属无监督聚类算法中最经典的算法。该算法的主要作用是将相似的样本自动归到一个类别中

三、算法思想

话不多说，直接上算法思想

KNN的算法思想：

计算测试数据与各个样本数据之间的距离，通常为欧式距离；
按照距离的递增关系进行排序；
选取距离最小的K个点；（即最近的K个点）
确定前K个点所在类别的出现频率；
返回前K个点中出现频率最高的类别作为测试数据的预测分类。

优点：简单，易于理解，易于实现，无需估计参数。对数据没有假设，准确度高，对异常点不敏感。
缺点：计算量太大，尤其是特征数非常多的时候。每一个待分类文本都要计算它到全体已知样本的距离，才能得到它的第K个最近邻点。
样本不平衡的时候，对稀有类别的预测准确率低。当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

K-means算法思想：

随机选取k个点，作为聚类中心。
计算每个点分别到k个聚类中心的距离，然后将该点分到最近的聚类中心，这样就形成了k个簇。
再重新计算每个簇的中心。
重复以上2-3步，直到质心位置不在变化，或者达到设定的迭代次数。

如何选取K值：根据经验以及利用k-means聚类的目的来决定。最好选择数据中的点。
优点：广泛应用，速度快，鲁棒性强
缺点：刚开始的k值很难估计，进行k-means时，要给出聚类数量，但是并不知道要给出多少，希望算法可以给出一个合理的数量。刚开始的k值时随机给的，结果也有很大的随机性。数据量大时，算法的时间开销也是很大