❶ K-means 与KNN 聚类算法
K-means 算法属于聚类算法的一种。聚类算法就是把相似的对象通过静态分类方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性。聚类算法的任务是将数据集划分为多个集群。在相同集群中的数据彼此会比不同集群的数据相似。通常来说，聚类算法的目标就是通过相似特征将数据分组并分配进不同的集群中。
K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。 算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：
每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。
在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：
K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。
上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。
Elbow point 拐点方法
通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。
DBI（Davies-Bouldin Index）
DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。
还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。
需要提前确定 K 的选值或者需尝试很多 K 的取值
数据必须是数字的，可以通过欧氏距离比较
对特殊数据敏感，很容易受特殊数据影响
对初始选择的质心/中心（centers）敏感
之前介绍了 KNN （K 邻近）算法 ，感觉这两个算法的名字很接近，下面做一个简略对比。
K-means ：
聚类算法
用于非监督学习
使用无标签数据
需要训练过程
K-NN ：
分类算法
用于监督学习
使用标签数据
没有明显的训练过程
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类(classification)算法，它输入基于实例的学习（instance-based learning），属于懒惰学习（lazy learning）即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。与急切学习（eager learning）相对应。
KNN是通过测量不同特征值之间的距离进行分类。
思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
提到KNN，网上最常见的就是下面这个图，可以帮助大家理解。
我们要确定绿点属于哪个颜色（红色或者蓝色），要做的就是选出距离目标点距离最近的k个点，看这k个点的大多数颜色是什么颜色。当k取3的时候，我们可以看出距离最近的三个，分别是红色、红色、蓝色，因此得到目标点为红色。
算法的描述：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类
二、关于 K 的取值
K：临近数，即在预测目标点时取几个临近的点来预测。
K值得选取非常重要，因为：
如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；
K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
K的取法：
常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。
一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。
三、关于距离的选取
距离就是平面上两个点的直线距离
关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。
Euclidean Distance 定义：
两个点或元组P1=（x1，y1）和P2=（x2，y2）的欧几里得距离是
距离公式为：（多个维度的时候是多个维度各自求差）
四、总结
KNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时
KNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。
KNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。
KNN很耗时，时间复杂度为O(n)，一般适用于样本数较少的数据集，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有kd-tree和ball-tree。
❷ K-Means 聚类算法
问题导入
假如有这样一种情况，在一天你想去某个城市旅游，这个城市里你想去的有70个地方，现在你只有每一个地方的地址，这个地址列表很长，有70个位置。事先肯定要做好攻略，你要把一些比较接近的地方放在一起组成一组，这样就可以安排交通工具抵达这些组的“某个地址”，然后步行到每个组内的地址。那么，如何确定这些组，如何确定这些组的“某个地址”？答案就是聚类。而本文所提供的k-means聚类分析方法就可以用于解决这类问题。
一，聚类思想
所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图：
根据样本之间的距离或者说相似性，把越相似，差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
二，K-Means聚类分析算法
K-Means是一种基于自下而上的聚类分析方法，基本概念就是空间中有N个点，初始选择K个点作为中心聚类点，将N个点分别与K个点计算距离，选择自己最近的点作为自己的中心点，不断地更新中心聚集点。
相关概念：
K值：要得到的簇的个数
质心：每个簇的均值向量，即向量各维取品军即可
距离度量：常用欧几里得距离和余弦相似度(先标准化)
两点之间的距离：
算法流程：
1 首先确定一个K值，即我们希望将数据集经过聚类得到 K个集合；
2 从数据集中随机选择K个数据点作为质心；
3 对数据集中每一个点，计算其与每个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合
4 把所有数据归好集合，一共有K个集合，然后重新计算每个集合的质心；
5 如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。
6 如果新质心和原质心距离变化大，需要迭代3-5步骤
K-means实现过程
K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。
算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：
1.数据分配：
每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。
其中 dist（·）是标准（L2）欧氏距离。让指向第 i 个集群质心的数据点集合定为 Si 。
2. 质心更新：
在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：
K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。
K 值的选择
上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。
Elbow point 拐点方法
通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。
DBI（Davies-Bouldin Index）
DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。
还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。
三，数学原理
K-Means采用的启发式很简单，可以用下面一组图来形象的描述：
上述a表达了初始的数据集，假设 k=2 。在图b中，我们随机选择了两个 k 类所对应的类别质点，即图中的红色质点和蓝色质点，然后分别求样本中所有点到这两个质心的距离，并标记每个样本类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心大热位置已经发生了变化。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求出新的质心。最终我们得到的两个类别如图f.
四，实例
坐标系中有六个点：
1、我们分两组，令K等于2，我们随机选择两个点：P1和P2
2、通过勾股定理计算剩余点分别到这两个点的距离：
3、第一次分组后结果：
组A：P1
组B：P2、P3、P4、P5、P6
4、分别计算A组和B组的质心：
A组质心还是P1=（0，0）
B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
5、再次计算每个点到质心的距离：
6、第二次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
7、再次计算质心：
P哥1=（1.33，1）
P哥2=（9，8.33）
8、再次计算每个点到质心的距离：
9、第三次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。
五、K-Means的优缺点
优点：
1、原理比较简单，实现也是很容易，收敛速度快。
2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
3、主要需要调参的参数仅仅是簇数k。
缺点：
1、K值需要预先给定，很多情况下K值的估计是非常困难的。
2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
3、对噪音和异常点比较的敏感。用来检测异常值。
4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。
六、细节问题
1、K值怎么定？
答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。
2、初始的K个质心怎么选？
答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。 当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
3、关于离群值？
答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
4、单位要一致！
答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
5、标准化
答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。
❸ 找出一个二维数组的拐点算法
拐点可以这样去求：判断条件：(data[n+1]-data[n])*(data[n+2]-data[n+1])<0,不论波谷还是波峰都可以求，如果要求即使两个相邻数一样也算是拐点的话，那么条件改为<=0即可！