聚类–分区和分配算法
K-means算法是一种用于数据聚类和分类的流行且有效的方法。当我进行图像压缩研究时，我第一次介绍K-means算法。在此应用程序中，聚类的目的是提供仅用一个对象/向量表示一组对象或向量的能力，而这些对象或向量的信息损失是可以接受的。更具体地，聚类过程中，聚类的质心对于聚类是最佳的，并且聚类相对于质心是最佳的。
向量的维数范围为4到70，甚至更高，其中N维向量的每个群集都将由单个向量表示，同时最小化某些保真度标准或信息丢失。设计过程包括使用向量训练集并将结果应用于训练集向量之外。
在这里，自然会出现几个问题。首先，应该使用哪种成本函数，保真度准则或失真度量来表示将由我们的聚类过程支付的惩罚，以及仅由单个向量表示的惩罚。
其次，应该有多少个群集，以及如何将样本分配给每个群集。要选择的群集数量是一项艰巨的任务。当然，如果聚类与样本或向量一样多，则可以实现这种最小化。但是，那不被认为是数据的集群。在任何实际应用中，您都必须使用几个样本/向量来表示所有样本/向量，因此需要创建一组向量簇。
让我们讨论每个问题。
哪个成本函数，失真度量或保真度准则？
该问题的答案取决于您的应用程序。广泛使用的度量是均方误差，也称为L2-范数。L2范数通常用于大多数应用，包括信号处理，图像压缩和视频压缩。有些应用程序使用绝对误差差L1范数，也称为曼哈顿距离。还有许多其他错误度量，例如用于语音的一种错误度量，它使用称为Itakura-Saito度量的加权失真度量。失真度表示通过单个向量表示簇的成员要付出的代价。结果，代表群集本身的群集质心是群集的广义重心。当使用均方误差作为失真度量时，聚类的重心是指聚类中所有矢量的平均值。为了将其推广到其他失真度量，我们使用广义重心来表示其他失真度量的群集质心。
第二个问题涉及多少个聚类以及如何将样本分配给聚类？问题的第二部分的答案很容易，因为将向量分配给聚类直接遵循系统中使用的成本函数。但是，簇的数量是重要的，将在后面讨论。
现在，我们如何确定群集及其表示形式？我们可以通过使用迭代优化技术来回答这个问题。
更具体地说，通过这种方法，我们不断优化
a）给定质心的簇，和
b）簇的质心，
直到达到最佳的群集划分和质心分配。
我们可以通过以下算法来表示这种方法。
迭代算法：
初始化：给定质心数N及其值A（m），失真阈值e> 0，以及所有聚类的点，设置迭代数m = 0和失真值
D（-1）=无穷大
给定质心集合，找到质心集合A（m）的最小失真分区S（m），然后根据失真准则计算所得的失真D（m）。
如果（D（m-1）-D（m））/ D（m）<e，则停止A（m）和S（m）代表最终的质心和分区。否则继续。
将m替换为m + 1并找到分区S（m）的最佳质心A（m）。
给定群集的当前分区，找到群集的最佳质心，然后转到步骤1。
阈值e取决于设计者的选择，0.05可被视为常用值。所得的划分和质心将至少提供局部最小值，如果不是全局最优值的话。
给定以上算法，我们将能够找到最佳的分区和分区的最佳表示形式。上述算法中缺少的重要部分是初始质心和初始聚类，没有它们我们就无法执行该算法。在这种情况下，我们让聚类样本/向量使用以下算法引导我们进行分区和质心选择，该算法称为分裂算法以获得N个分区。
分割算法：
初始化：设置质心数M = 1，并将A（1）定义为整个可用点/矢量的质心。
给定包含M个点的A（M），将每个a（M）点扰动为（1 + d）a（M），其中d是一个小数。给定结果2M向量，将M替换为2M。
对M个点运行“迭代算法”以获得新的A（M）。
是M = N吗？如果是这样，请停止上一步的结果作为最终的聚类及其表示。否则，请转到步骤1。
前面的算法会为每个聚类创建聚类以及最佳质心。您观察到，由于拆分过程，使用上述算法的群集大小将为2的幂。当然，我们可以通过更改步骤1中的拆分过程为每次生成的质心选择任意大小，以一次仅扰动一个质心，可能是表现出最大失真的质心。使用这种方法，在每次迭代中将簇数增加一个单位，直到获得所需的簇数。
如前所述，群集的最终数量很难确定。用户需要考虑多少个群集才能最适合该应用程序。作为替代方案，我们可以考虑增加簇的数量，直到达到簇的总失真所需的阈值为止。
1