本节书摘来自华章计算机《大数据架构和算法实现之路：电商系统的技术实战》一书中的第2章，第2.2节，作者 黄 申，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.2 算法：K均值和层次型聚类
2.2.1 K均值聚类
K均值聚类（K-Means Clustering）算法是一种最普遍的、通过不断迭代调整k个聚类质心的算法。这里的质心是群组的中心点，通常用其中成员的平均值来计算。K-Means是在一个任意多数据集合的基础上，得到一个事先定好群组数量的聚类结果。其中心思想是：最大化总的群组内相似度，而群组内相似度是通过群组各个成员和群组质心相比较得到的相似度来确定的。想法很简单，但是在样本数量达到一定规模后，希望通过排列组合所有的群组划分，来找到最大总群组内的相似则几乎是不可能的。于是人们提出了如下的近似解。
1）从N个数据对象中随机选取k个对象作为质心。因为是第一轮，所以第i个群组的质心就是选择的第i个对象，而且只有这一个组员。
2）对于剩余的每个对象，测量其和每个质心的相似度，并把它归到最近的质心的群组。
3）重新计算已经得到的各个群组的质心。这里质心的计算是关键，如果是用特制向量来表示的数据对象，那么最基本的方法是取群组内成员的特制向量，将它们的平均值作为质心的向量表示。
4）迭代第2步和第3步，直至新的质心与原质心相等或相差之值小于指定阈值，算法结束。
如果我们将所有的数据对象向量映射到二维空间，图2-1的a、b、c分别展示了质心和群组逐步调整的过程。步骤a是第一轮聚类，以及随后计算每个群组的质心。其中的“+”表示质心；步骤b是第二轮聚类，根据新的质心，计算每个数据点应该属于哪个新的群组；步骤c，如此往复，进入下一轮聚类。
细心的读者会发现，这个过程和KNN分类非常类似，都会涉及某个数据对象和其他对象或群组质心的相似度计算。最主要的区别在于KNN是针对监督式学习，训练数据中的分类标签都已经确定，所以无需多次迭代的优化过程。而K均值算法中，一开始质心和群组的选择都是临时的，在之后的迭代中才逐步逼近局部优化的解，直到达到一个稳定的状态。
“小明哥，这个方法虽然简单易懂，但是一开始怎样选择这个群组的数量啊，针对一个新的数据集合，多少才比较合适呢？如果k值取得太大，那么群组可能切分得太细，每个之间的区别不大。如果k值取得太小，就怕粒度太粗，群组内又差异明显。无论怎样对最后的分析都不利啊。”
“好问题，这种非监督式的学习确实有一些参数很难得到准确的预估。可以事先在一个较小的数据集合上进行尝试，然后根据结果和应用场景确定一个经验值。当然，如果还是不够理想，可以使用层次型的聚类（Hierarchical Clustering）在一定程度上缓解这个问题。”
2.2.2 层次型聚类
还有一种类型的聚类方法，仅仅使用数据对象之间的相似性，使得同一群组中对象的相似度，远远大于不同群组之间的相似度。这就是层次型的聚类。具体又可分为分裂和融合两种方案。分裂的层次型聚类采用自顶向下的策略，它首先是将所有对象置于同一个群组中，然后逐渐细分为越来越小的群组，直到每个对象自成一组，或者达到了某个阈值条件而终止。融合的层次聚类与分裂的层次聚类相反，是一种自底向上的策略，首先将每个对象作为一个群组，然后将这些原始群组合并成为越来越大的群组，直到所有的对象都在一个群组中，或者达到某个阈值条件而终止。融合的方式在计算上更加简单快捷，因此绝大多数层次型聚类方法属于这一类，只是在群组间相似度的定义上有所不同而已。其大致流程概括如下。
1）最初给定n个数据对象，将每个对象看成一个群组。这样共得到n个组，每组仅包含一个对象，组与组之间的相似度就是它们所包含的对象之间的相似度。
2）找到最接近的两个组并合并成一个，于是总的组数少了一个。
3）重新计算新的组与所有旧组之间的距离。
4）重复第2步和第3步，直到最后合并成一个组为止。如果设置了组数，或者是组间相似度的阈值，也可以提前结束聚合。
图2-2展示了融合聚类的概念。以左下角圆框标出的部分为例，可以看到其中的若干数据对象的情况，包括14、17、13、22和12号。第一次，14和17号对象的相似度很高，优先聚为一组，而在第二次13和22号聚为另外一组。第三次，再次查找群组之间的相似度，会发现在{14，17}的群组、{13，22}的群组，以及12单独成立的群组中，{14，17}群组和{13，22}群组的相似度更高，因此会再次融合成为{14，17，13，22}，最后第四次{14，17，13，22}再次和12融合。
那么接下来就有一个有趣的问题，如何计算群组之间的相似度呢？之前在K-Means聚类中，计算的是单个数据对象和质心间的相似度，就是两个向量之间的比较。而现在计算的是两个群组之间的相似度，是两组向量的比较。两组之间比较的工作量肯定更大，常见的方式有三种，分别是单一连接（Single Linkage）、完全连接（Complete Linkage）和平均连接（Average Linkage）。
（1）单一连接
群组间的相似度使用两组对象之间的最大相似度表示，公式如下：
其中sim (ci, cj)表示群组i和群组j之间的相似度，x和y分别是群组i和j内的数据对象。单一连接对两组对象之间相似度的要求不高，只要两个对象间存在较大的相似值就能够使两组优先融合。单一连接会产生链式效应，通过这种连接方式来融合可以得到丝状结构。
（2）完全连接
群组间的相似度使用两组对象之间的最小相似度来表示，公式如下：
只有在两组对象之间的相似度很高时，才能优先考虑融合。当各个群组聚集得比较紧密，类似球状，不太符合丝状结构时，使用单一连接效果不佳。这时可以考虑完全连接。
（3）平均连接
群组间的相似度使用两组对象之间的平均相似度来表示，公式如下：
相对而言，这种计算对于各类形状都是比较有效的。
“懂了。这样看来层次型聚类虽然计算量大，但是对于确定合适的聚类群组还是有所帮助的。另外，整体感觉，好像聚类算法比较简单，也完全不用人工的标注哦，这样岂不是比分类方便很多？”
“确实不需要人工的分类标注，节省了很多运营的人力。不过，聚类通常只能发现数据结构内部的特征，聚集出来的群组其解释性比不上分类。因此，聚类比较适合业务需求变化快，而且对精度要求不高的分析，例如侦测异常行为、用户分组等。而分类则更适合于需求相对稳定、对精度要求很高的分析，例如搜索查询分类、商品目录的分类等。或者，我们也可以结合这两者，先用聚类进行初步的分析，然后再让运营人员通过聚类的结果来构建分类的标注数据。”
