K-近邻算法（KNN）概述 （有监督算法，分类算法）
最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来，当测试对象的属性和某个训练对象的属性完全匹配时，便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢，其次就是存在一个测试对象同时与多个训练对象匹配，导致一个训练对象被分到了多个类的问题，基于这些问题呢，就产生了KNN。
KNN是通过测量不同特征值之间的距离进行分类。它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
由此也说明了KNN算法的结果很大程度取决于K的选择。
在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：
同时，KNN通过依据k个对象中占优的类别进行决策，而不是单一的对象类别决策。这两点就是KNN算法的优势。
对KNN算法的思想总结一下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
from：http://www.cnblogs.com/ybjourney/p/4702562.html
K-均值聚类（K-means）（无监督学习、聚类算法，随机算法）
1. 聚类
“类”指的是具有相似性的集合。聚类是指将数据集划分为若干类，使得类内之间的数据最为相似，各类之间的数据相似度差别尽可能大。聚类分析就是以相似性为基础，对数据集进行聚类划分，属于无监督学习。
2、 K-means
k-means算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有值的均值得到，每个类用聚类中心来描述。对于给定的一个包含n个d维数据点的数据集X以及要分得的类别K,选取欧式距离作为相似度指标，聚类目标是使得各类的聚类平方和最小。
a. 最常用的无监督算法
b. 计算距离方法：欧式距离，曼哈顿距离
c. 应用：去除孤立点，离群点（只针对度量算法）；可以离散化
d. 最常用归一化预处理方法
f. k-means设置超参数k时，只需要设置最大的k值。
g. k-means算法最终肯定会得到稳定的k个中心点，可以用EM(Expectation Maximum)算法解释
h. k-means算法k个随机初始值怎么选？ 多选几次，比较，找出最好的那个
i. 调优的方法：1. bi-kmeans 方法（依次“补刀”）
j. 调优的方法：2. 层次聚类（逐步聚拢法）k=5 找到5个中心点，把中心点喂给k-means。初始中心点不同，收敛的结果也可能不一致。
k. 聚类效果怎么判断？用SSE误差平方和指标判断，SSE越小越好，也就是肘部法则的拐点处。也可以用轮廓系数法判断，值越大，表示聚类效果越好，簇与簇之间距离越远越好，簇内越紧越好。
l. k-means算法最大弱点：只能处理球形的簇（理论）
3、算法流程
K-means是一个反复迭代的过程，算法分为四个步骤：
1） 选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心；
2） 对于样本中的数据对象，根据它们与这些聚类中心的欧氏距离，按距离最近的准则将它们分到距离它们最近的聚类中心（最相似）所对应的类；
3） 更新聚类中心：将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值；
4） 判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回2）。
用以下例子加以说明：
图1：给定一个数据集；
图2：根据K = 5初始化聚类中心，保证 聚类中心处于数据空间内；
图3：根据计算类内对象和聚类中心之间的相似度指标，将数据进行划分；
图4：将类内之间数据的均值作为聚类中心，更新聚类中心。
最后判断算法结束与否即可，目的是为了保证算法的收敛。