​一、k-means算法基本原理：

(1) 随机选取k个中心点；

(2) 在第j次迭代中，对于每个样本点，选取最近的中心点，归为该类；

(3) 更新中心点为每类的均值；

(4) j<-j+1 ,重复(2)(3)迭代更新，直至误差小到某个值或者到达一定的迭代步数，误差不变.

空间复杂度o(N)   时间复杂度o(I*K*N)

其中N为样本点个数，K为中心点个数，I为迭代次数

二、如何自适应确定k值

1、手肘法

• Elbow method就是“肘”方法，对于n 个点的数据集，迭代计算k from 1 to n，每次聚类完成后计算每个点到其所属的簇中心的距离的平方和，可以想象到这个平方和是会逐渐变小的，直到k==n 时平方和为0，因为每个点都是它所在的簇中心本身。但是在这个平方和变化过程中，会出现一个拐点也即“肘”点，下图可以看到下降率突然变缓时即认为是最佳的k值。
•     我们知道K-means是以最小化样本与质点平方误差作为目标函数，将每个簇的质点与簇内样本点的平方距离误差和称为畸变程度(distortions)，那么，对于一个簇，它的畸变程度越低，代表簇内成员越紧密，畸变程度越高，代表簇内结构越松散。 畸变程度会随着类别的增加而降低，但对于有一定区分度的数据，在达到某个临界点时畸变程度会得到极大改善，之后缓慢下降，这个临界点就可以考虑为聚类性能较好的点。

2、轮廓系数法

轮廓系数（Silhouette Coefficient）结合了聚类的凝聚度（Cohesion）和分离度（Separation），用于评估聚类的效果。该值处于-1~1 之间，值越大，表示聚类效果越好。具体计算方法如下：

对于每个样本点i ，计算点i 与其同一个簇内的所有其他元素距离的平均值，记作a(i) ，用于量化簇内的凝聚度。

选取i 外的一个簇b ，计算i 与b 中所有点的平均距离，遍历所有其他簇，找到最近的这个平均距离,记作b(i) ，即为i 的邻居类，用于量化簇之间分离度。

对于样本点i ，轮廓系数s(i) = (b(i)–a(i))/max{a(i),b(i)} 。计算所有i 的轮廓系数，求出平均值即为当前聚类的整体轮廓系数，度量数据聚类的紧密程度。从上面的公式，不难发现若s(i) 小于0，说明i 与其簇内元素的平均距离小于最近的其他簇，表示聚类效果不好。如果a(i) 趋于0，或者b(i) 足够大，即a(i)<<b(i) ，那么s(i) 趋近与1，说明聚类效果比较好。

3、Calinski-Harabasz准则

其中SSB是类间方差，，m为所有点的中心点,mi为某类的中心点；SSW是类内方差，；(N-k)/(k-1)是复杂度；比率越大，数据分离度越大.

​