如果我们在搜索引擎中搜索术语“火星”，我们将得到像“星球火星”和“巧克力，糖果和饮料集团”这样的结果，这些结果在语义上是完全不同的。在发现的文档集中，有两个明显不同的集群。例如，谷歌仍然以非结构化的方式列出结果。如果搜索引擎将群集分开并相应地将它们呈现给用户会更好，因为用户通常只对其中一个群集感兴趣。
与监督学习相比，聚类的区别在于训练数据是未标记的。因此，缺少主管对数据的预构建。相反，寻找结构是整个聚类的重点。在训练数据的空间中，可以找到数据的累积，例如第 207 页的图 8.31中的数据。在聚类中，相邻点的距离通常小于不同聚类的点之间的距离。因此，为点进行合适的距离度量的选择，即对于要分组的对象和对于簇的选择，具有根本重要性。和以前一样，我们假设每个数据对象都由数字属性向量描述。
图8.31 简单
具有四个明显分离的簇的二维示例
1.
距离指标
因此为每个应用程序，各种距离度量对的距离限定d两个向量之间的X和ÿ在ř Ñ。最常见的是欧氏距离
ñ
de（x，y）=
i = 1
（xi – yi）2。
距离平方的总和稍微简单一些
ñ
dq（x，y）= （xi – yi）2，
i = 1
对于仅比较距离的算法，其等效于欧几里德距离（第 220 页的练习 8.19 ）。还使用了前面提到的曼哈顿距离
ñ
dm（x，y）= | xi – yi |
i = 1
以及最大组件的距离
=∞ 我
d（x，y）max
= 1 ，…，n
| xi – yi |
这是基于最大规范。在文本分类期间，两个向量相互之间的归一化投影，即标准化的标量积
XY
| x | | y |
| |
经常计算，其中X是欧几里德范X。因为该公式是两个向量的相似性的度量，所以作为距离度量，反向
d（x，y）= | x | | y |
s xy
可以使用，或“ > ”和“ < ”可以交换进行所有比较。在搜索文本时，属性x 1 ，…，xn的计算类似于朴素贝叶斯，作为向量x的组成部分，如下所示。对于包含50,000个单词的字典，值为xi
等于文本中第 i 个字典单词的频率。由于通常在这样的矢量中几乎所有分量都是零，因此在计算标量乘积期间，几乎所有求和项都为零。通过利用这种信息，可以显着加快实施（第 220页的练习 8.20）。
2.
k-Means和EM算法
每当预先知道簇的数量时，就可以使用k均值算法。顾名思义，k簇是由它们的平均值定义的
值。首先ķ簇中点μ 1 ，…，μ ķ随机或手工initial-源化。然后重复执行以下两个步骤：
•
•
将所有数据分类到最近的群集中点重新计算群集中点。
以下方案作为算法得出：
K – MEANS（x 1，…，x n，k）
初始化 μ 1 ，…， μ ķ （例如随机地）
重复
分类X
1 ，…，X Ñ每个是最近的μ我
重新计算 μ 1
，…， μ ķ 直到在没有变化 μ 1
，…， μ ķ 返回（ μ 1
，…， μ ķ ）
点x 1 ，…，x l的簇中点μ的计算由下式完成
升
升
一世
μ = 1 x 。
i = 1
i = 1
对于两个类的情况，一个例子的执行如第209 页的图8.32 所示。我们看到在三次迭代之后，首先随机选择的类中心如何稳定。虽然该算法不能保证收敛，但它通常会很快收敛。这意味着迭代步骤的数量通常远小于数据点的数量。其复杂度为O（ndkt），其中n是点的总数，d是特征空间的维数，t是迭代步骤的数量。
在许多情况下，提前提供课程数量的必要性造成了不方便的限制。因此，接下来我们将介绍一种更灵活的算法。
然而，在此之前，我们将提到EM算法，它是k-means的连续变体，因为它没有将数据牢固地分配给类，而是为每个点返回它属于的概率。各种课程。
|
|
|
|
|
=
图8.32 k-means，两个类（ k 2）应用于30个数据点。最左边是具有初始中心的数据集，右边是每次迭代后的集群。经过三次迭代后，达到了收敛
在这里我们必须假设概率分布的类型是已知的。通常使用正态分布。EM算法的任务是确定的PA rameters（平均μ我和协方差矩阵ΣI所述的ķ多维正态分布）为每个群集。与k-means类似，重复执行以下两个步骤：
|
期望：对于每个数据点，计算它属于每个聚类的概率 P（Cj × i）。
最大化：使用新计算的概率，重新计算分布的参数。
从而实现更柔和的聚类，这在许多情况下导致更好的结果。期望和最大化之间的这种交替给出了算法的名称。除了聚类之外，例如，EM算法用于学习贝叶斯网络[DHS01]。
3. 分层聚类
重复
H IERARCHICAL
C
LUSTERING（x 1，…，x n，k）
在层次聚类中，我们从n个聚类开始，每个聚类由一个点组成。然后组合最近的邻居群集，直到所有点已经组合到单个群集中，或者直到达到终止标准。我们获得了该计划
初始化C 1 = { x 1 } ，…，Cn = { x n }
发现两个集群词和CJ与最小距离合并词和CJ
直到达到终止条件
返回（带有簇的树）
图8.33 在分层聚类中，每个步骤中组合具有最小距离的两个聚类
可以选择终止条件，例如，期望数量的簇或簇之间的最大距离。在图 8.33中，该算法被示意性地表示为二叉树，其中在每个步骤中从下到上，即在每个级别，连接两个子树。在顶层，所有点都统一为一个大型集群。
到目前为止还不清楚如何计算簇之间的距离。实际上，在上一节中，我们为点定义了各种距离度量，但这些度量不能用于群集。一个方便且经常使用的度量标准是两个簇Ci和Cj中两个最近点之间的距离：
= X ∈
dmin（Ci，Cj）min
Ç 我，ÿ ∈ Ç Ĵ
d（x，y）。
因此，我们获得了最近邻算法，其应用如图 8.34 在 211 页所示。9 我们看到此算法生成最小生成树。10 该示例进一步表明，所描述的两种算法产生了完全不同的聚类。这告诉我们，对于具有未明确分离的聚类的图形，结果在很大程度上取决于算法或所选择的距离度量。
–
为了有效地实现该算法，我们首先创建一个邻接矩阵，其中保存所有点之间的距离，这需要O（n 2 ）时间和内存。如果簇的数量没有上限，则循环将迭代n次，并且渐近计算时间变为O（n 3 ）。
要计算两个星团之间的距离，我们还可以使用两个最远点之间的距离
= X ∈
dmax（Ci，Cj）max
Ç 我，ÿ ∈ Ç Ĵ
d（x，y）
9 不要将最近邻算法与Sect的分类最近邻算法混淆。8.3 。
10 最小生成树是一个非循环的无向图，边长最小。
图8.34最近邻算法适用于第 209页图 8.32中不同级别的数据，分别为12,6,3,1个簇
并获得最远的邻居算法。或者，使用簇的中点 dμ（Ci，Cj） = d（ μi， μj）的距离。除了这里介绍的聚类算法，还有很多其他的，对此我们直接读者[DHS01]
进一步研究。
