K-均值是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。
K-均值是一个迭代算法，假设我们想要将数据聚类成K个组，其方法为:
- 首先选择$K$个随机的点，称为聚类中心（cluster centroids）；
- 对于数据集中的每一个数据，按照距离$K$个中心点的距离，将其与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类。
- 计算每一个组的平均值，将该组所关联的中心点移动到平均值的位置。
- 重复步骤2-4直至中心点不再变化。
优化目标
K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此 K-均值的代价函数（又称畸变函数 Distortion function）为：
$$J(c^1,…,c^m,μ_1,…,μ_K)=\dfrac {1}{m}\sum^{m}{i=1}\left| X^{\left( i\right) }-\mu{c^{(i)}}\right| ^{2}$$
其中$\mu_c^{(i)}$代表与$x^i$最近的聚类中心点。
我们的的优化目标便是找出使得代价函数最小的 $c^1$,$c^2$,…,$c^m$和$μ^1$,$μ^2$,…,$μ^k$。
K值选择
在运行K-均值算法的之前，我们首先要随机初始化所有的聚类中心点，下面介绍怎样做：
- 我们应该选择$K<m$，即聚类中心点的个数要小于所有训练集实例的数量
- 随机选择$K$个训练实例，然后令$K$个聚类中心分别与这$K$个训练实例相等
K-均值的一个问题在于，它有可能会停留在一个局部最小值处，而这取决于初始化的情况:
为了解决这个问题，我们通常需要多次运行K-均值算法，每一次都重新进行随机初始化，最后再比较多次运行K-均值的结果，选择代价函数最小的结果。这种方法在$K$较小的时候（2–10）还是可行的，但是如果$K$较大，这么做也可能不会有明显地改善。
没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的，但有一个可能会谈及的方法叫作“肘部法则”。关于“肘部法则”，我们所需要做的是改变$K$值，然后计算成本函数$J$。我们可能会得到一条类似于这样的曲线，像一个人的肘部：
你会发现这种模式，它的畸变值会迅速下降，从1到2，从2到3之后，你会在3的时候达到一个肘点。在此之后，畸变值就下降的非常慢，看起来就像使用3个聚类来进行聚类是正确的，这是因为那个点是曲线的肘点，畸变值下降得很快，$K=3$之后就下降得很慢，那么我们就选$K=3$。当你应用“肘部法则”的时候，如果你得到了一个像上面这样的图，那么这将是一种用来选择聚类个数的合理方法。
例如，我们的 T-恤制造例子中，我们要将用户按照身材聚类，我们可以分成3个尺寸:$S,M,L$，也可以分成5个尺寸$XS,S,M,L,XL$，这样的选择是建立在回答“聚类后我们制造的T-恤是否能较好地适合我们的客户”这个问题的基础上作出的。
聚类的衡量指标
- 均一性$p$: 类似于精确率，一个簇中只包含一个类别的样本，则满足均一性。其实也可以认为就是正确率(每个聚簇中正确分类的样本数占该聚簇总样本数的比例和)
- 完整性$r$: 类似于召回率，同类别样本被归类到相同簇中，则满足完整性; 每个聚簇中正确分类的样本数占该类型的总样本数比例的和
- V-measure(均一性和完整性的加权平均): $V = \frac{(1+\beta^2)pr}{\beta^2p+r}$
- 簇内不相似度: 计算样本$i$到同簇其它样本的平均距离为$a_i$，应尽可能小。
- 簇间不相似度: 计算样本$i$到其它簇$C_j$的所有样本的平均距离$b_{ij}$，应尽可能大。
- 轮廓系数：样本$s(i)$值越接近1表示样本$i$聚类越合理，越接近-1，表示样本$i$应该分类到 另外的簇中，近似为0，表示样本$i$应该在边界上;所有样本的$s(i)$的均值被成为聚类结果的轮廓系数。$s(i) = \frac{b_i-a_i}{max(a_i,b_i)}$