k-NN法

最近看一些面试试题，发现很多以前学习过的知识点几乎都很难系统的描述出来，故打算从今往后，学习过的知识点好好整理到****上。

K近邻算法简单，直观，给定训练集，输入一个实例样本，计算样本与训练集样本的距离，选取离样本最为接近的K个实例，采取一定的判别准则（例如:多数投票表决），判定样本为某类。

K近邻模型三大要素

距离度量
k值的选择
判别准则

距离度量

k近邻模型的特征空间一般为n维的实数向量空间 $R^n$ ,一般使用欧式距离，下面给出一些常见的距离公式：
$L_p$ 距离
$L_{p}(x_{i},x_{j})=(\sum_{l=1}^{n}\left | x_{i}^{(l)}-x_{j}^{(l)} \right |^p)^\frac{1}{p}$
当P=2时，称为欧式距离：

$L_{2}(x_{i},x_{j})=(\sum_{l=1}^{n}\left | x_{i}^{(l)}-x_{j}^{(l)} \right |^2)^\frac{1}{2}$
当P=1时，称为曼哈顿距离

K值的选择

如果k值选择较小，意味着模型容量较高，泛化误差较大，训练集拟合效果好；反过来，如果k值选择较大，则训练集拟合效果差，泛化能力强，使得模型更为简单，一般来说，k值的选择可以使用交叉验证来得到一个较优的值。

判别准则

判别准则一般为多数表决，即由输入实例的k个邻近的训练实例的多数类来决定输入实例的类别。

k-mean算法

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
　如果用数据表达式表示，假设簇划分为 $(C_1,C_2,...C_k)$ ，则我们的目标是最小化平方误差E：
　 $E = \sum_{i=1}^k\sum\limits_{x \in C_i} ||x-\mu_i||_2^2$
　其中 $μ_i$ 是簇 $C_i$ 的均值向量，有时也称为质心，表达式为：
　 $μ_i=\frac{1}{ || C_i ||}\sum_{x \in C_i}x$
　如果我们想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。
　K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述。
　【机器学习】K近邻算法、k-mean算法
上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

当然在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

传统K-mean的算法流程如下：

输入:训练集D={(x_1,y_1),(x_2,y_2),...}
输出:k个聚类簇
初始化k个聚类中心
while  聚类簇不再改变 or 达到一定迭代次数或其他某些条件：
	for 每个样本点 ：
		for 每个聚类中心：
			计算样本点与聚类中心距离
		将样本归为最近的样本中心
	重新计算聚类中心
输出聚类中心

k-mean算法小结：

K-Means是个简单实用的聚类算法，这里对K-Means的优缺点做一个总结。

K-Means的主要优点有：

1）原理比较简单，实现也是很容易，收敛速度快。
2）聚类效果较优。
3）算法的可解释度比较强。
4）主要需要调参的参数仅仅是簇数k。

K-Means的主要缺点有：

1）K值的选取不好把握
2）对于不是凸的数据集比较难收敛
3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
4）采用迭代方法，得到的结果只是局部最优。
5）对噪音和异常点比较的敏感。

【机器学习】K近邻算法、k-mean算法