K_means聚类算法介绍
1.K_means算法
K_menas算法流程
输入是样本集D={x1,x2,…xN}，聚类的簇数k，最大迭代次数T
输出是簇划分C={C1,C2,…Ck}
1）从数据集D中随机选择k个样本作为初始的k个质心向量： {μ1,μ2,…,μk}，将每个簇初始化为空集
2）对于t=1,2,…,T
a) 对于i=1,2…N，计算样本 xi 和各个质心向量 μj，j=1,2,…k的欧式距离，将 xi 划分到最近的簇中，即更新Cj=Cj∪{xi}
b) 对于j=1,2,…,k,对Cj中所有的样本点重新计算新的质心
c) 如果所有的k个质心向量都没有发生变化，则转到步骤3）
3） 输出簇划分C={C1,C2,…Ck}
值得一提的是关于聚类中心数目（K值）的选取，的确存在一种可行的方法，叫做Elbow Method：通过绘制K-means代价函数与聚类数目K的关系图，选取直线拐点处的K值作为最佳的聚类中心数目。但在这边不做过多的介绍，因为上述方法中的拐点在实际情况中是很少出现的。比较提倡的做法还是从实际问题出发，人工指定比较合理的K值，通过多次随机初始化聚类中心选取比较满意的结果。
2.K_means++算法
2007年由D. Arthur等人提出的K-means++针对图1中的第一步做了改进。可以直观地将这改进理解成这K个初始聚类中心相互之间应该分得越开越好。整个算法的描述如下图所示：
下面结合一个简单的例子说明K-means++是如何选取初始聚类中心的。数据集中共有8个样本，分布以及对应序号如下图所示：
假设经过图2的步骤一后6号点被选择为第一个初始聚类中心，那在进行步骤二时每个样本的D(x)和被选择为第二个聚类中心的概率如下表所示：
其中的P(x)就是每个样本被选为下一个聚类中心的概率。最后一行的Sum是概率P(x)的累加和，用于轮盘法选择出第二个聚类中心。方法是随机产生出一个0~1之间的随机数，判断它属于哪个区间，那么该区间对应的序号就是被选择出来的第二个聚类中心了。例如1号点的区间为[0,0.2)，2号点的区间为[0.2, 0.525)。
从上表可以直观的看到第二个初始聚类中心是1号，2号，3号，4号中的一个的概率为0.9。而这4个点正好是离第一个初始聚类中心6号点较远的四个点。这也验证了K-means的改进思想：即离当前已有聚类中心较远的点有更大的概率被选为下一个聚类中心。可以看到，该例的K值取2是比较合适的。当K值大于2时，每个样本会有多个距离，需要取最小的那个距离作为D(x)。
3.ISODATA算法
放在最后也是最复杂的就是ISODATA算法。正如之前所述，K-means和K-means++的聚类中心数K是固定不变的。而ISODATA算法在运行过程中能够根据各个类别的实际情况进行两种操作来调整聚类中心数K：(1)分裂操作，对应着增加聚类中心数；(2)合并操作，对应着减少聚类中心数
下面首先给出ISODATA算法的输入（输入的数据和迭代次数不再单独介绍）
[1] 预期的聚类中心数目Ko：虽然在ISODATA运行过程中聚类中心数目是可变的，但还是需要由用户指定一个参考标准。事实上，该算法的聚类中心数目变动范围也由Ko决定。具体地，最终输出的聚类中心数目范围是 [Ko/2, 2Ko]。
[2] 每个类所要求的最少样本数目Nmin：用于判断当某个类别所包含样本分散程度较大时是否可以进行分裂操作。如果分裂后会导致某个子类别所包含样本数目小于Nmin，就不会对该类别进行分裂操作
[3] 最大方差Sigma：用于衡量某个类别中样本的分散程度。当样本的分散程度超过这个值时，则有可能进行分裂操作（注意同时需要满足[2]中所述的条件）。
[4] 两个类别对应聚类中心之间所允许最小距离dmin：如果两个类别靠得非常近（即这两个类别对应聚类中心之间的距离非常小），则需要对这两个类别进行合并操作。是否进行合并的阈值就是由dmin决定。
相信很多人看完上述输入的介绍后对ISODATA算法的流程已经有所猜测了。的确，ISODATA算法的原理非常直观，不过由于它和其他两个方法相比需要额外指定较多的参数，并且某些参数同样很难准确指定出一个较合理的值，因此ISODATA算法在实际过程中并没有K-means++受欢迎。
首先给出ISODATA算法主体部分的描述，如下图所示
上面描述中没有说明清楚的是第5步中的分裂操作和第6步中的合并操作。下面首先介绍合并操作：
最后是ISODATA算法中的分裂操作。
最后，针对ISODATA算法总结一下：该算法能够在聚类过程中根据各个类所包含样本的实际情况动态调整聚类中心的数目。如果某个类中样本分散程度较大（通过方差进行衡量）并且样本数量较大，则对其进行分裂操作；如果某两个类别靠得比较近（通过聚类中心的距离衡量），则对它们进行合并操作
可能没有表述清楚的地方是ISODATA-分裂操作的第1步和第2步。同样地以图三所示数据集为例，假设最初1，2，3，4，5，6，8号被分到了同一个类中，执行第1步和第2步结果如下所示：
而在正确分类情况下（即1，2，3，4为一类；5，6，7，8为一类），方差为0.33。因此，目前的方差远大于理想的方差，ISODATA算法就很有可能对其进行分裂操作。
4.k_means算法的缺点
- 缺点一：聚类中心的个数K需要事先给定，但在实际中K值的选定是非常困难的，很多时候我们并不知道给定的数据集应该聚成多少个类别才最合适
- 缺点二：k-means算法需要随机地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果，有可能导致算法收敛很慢甚至出现聚类出错的情况
- 针对第一个缺点：很难在k-means算法以及其改进算法中解决，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过“肘方法”选择一个合适的k值
- 针对第二个缺点：可以通过k-means++算法来解决
5.DBSCAN VS K-Means
和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点。
那么我们什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。
6.DBSCAN 优缺点
DBSCAN的主要优点有：
1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
7.DBSCAN的主要缺点有：
1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2） 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。