本节将讨论一种最流行的聚类算法：k-means算法，它在学术领域及业界都得到了广泛应用。聚类（或称为聚类分析）是一种可以找到相似对象群组的技术，与组间对象相比，组内对象之间具有更高的相似度。聚类在商业领域的应用包括：按照不同主题对文档、音乐、电影等进行分组，或基于常见的购买行为，发现有相同兴趣爱好的顾客，并以此构建推荐引擎。
读者稍后将看到，与其他聚类算法相比，k-means算法易于实现，且具有很高的计算效率，这也许就是它得到广泛使用的原因。k-means算法是基于原型的聚类。在本章的后续内容中，我们还将讨论另外两种聚类：层次（hierarchical）聚类和基于密度（density-based）的聚类。基于原型的聚类意味着每个簇都对应一个原型，它可以是一些具有连续型特征的相似点的中心点（centroid）（平均值），或者是类别特征情况下相似点的众数（medoid）——最典型或是出现频率最高的点。虽然k-means算法可以高效识别球形簇，但是此算法的缺点在于必须事先指定先验的簇数量k。如果k值选择不当，则可能导致聚类效果不佳。本章后续还将讨论肘（elbow）方法和轮廓图（silhouette plot），它们可以用来评估聚类效果，并帮助我们选出最优k值。
尽管k-means聚类适用于高维数据，但出于可视化需要，我们将使用一个二维数据集的例子进行演示：
我们刚才创建的数据集中包含150个随机生成的点，它们大致分为三个高密度区域，其二维散点图如下：
在聚类算法的实际应用中，我们没有任何关于这些样本的类别基础信息；否则算法就要划分到监督学习的范畴了。由此，我们的目标就是根据样本自身特征的相似性对其进行分组，对此可采用k-means算法，具体有如下四个步骤：
1）从样本点中随机选择k个点作为初始簇中心。
2）将每个样本点划分到距离它最近的中心点μ（j）,j∈{1,…,k}所代表的簇中。
3）用各簇中所有样本的中心点替代原有的中心点。
4）重复步骤2和3，直到中心点不变或者达到预定迭代次数时，算法终止。
现在面临的一个问题就是：如何度量对象之间的相似性？我们可以将相似性定义为距离的倒数，在m维空间中，对于特征取值为连续型实数的聚类分析来说，常用的距离度量标准是欧几里得距离的平方：
请注意，在前面的公式中，下标索引j为样本点x和y的第j个维度（特征列）。本节后续内容将分别使用上标i和j来代表样本索引和簇索引。
基于欧几里得度量标准，我们可以将k-means算法描述为一个简单的优化问题，通过迭代使得簇内误差平方和（within-cluster sum of squared errors，SSE）最小，也称作簇惯性（cluster intertia）。
其中，μ（j）为簇j的中心点，如果样本x（i）属于簇j，则有w（i,j）＝1，否则w（i,j）＝0。
至此，我们已经知道了简单k-means算法的工作原理，现在借助scikit-learn中的KMeans类将k-means算法应用于我们的示例数据集：
使用上述代码，我们将簇数量设定为3个；指定先验的簇数量是k-means算法的一个缺陷，设置n_init＝10，程序能够基于不同的随机初始中心点独立运行算法10次，并从中选择SSE最小的作为最终模型。通过max_iter参数，指定算法每轮运行的迭代次数（在本例中为300次）。请注意，在scikit-learn对k-means算法的实现中，如果模型收敛了，即使未达到预定迭代次数，算法也将终止。
不过，在k-means算法的某轮迭代中，可能会发生无法收敛的情况，特别是当我们设置了较大的max_iter值时，更有可能产生此类问题。解决收敛问题的一个方法就是为tol参数设置一个较大的值，此参数控制对簇内误差平方和的容忍度，此容忍度用于判定算法是否收敛。在上述代码中，我们设置的容忍度为1e-04（0.0001）。