英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
全局k均值聚类算法
摘要
本文提出了全局k均值算法，它是一种增量式聚类方法，它通过一个确定性的全局搜索过程动态地添加一个聚类中心，该过程由N个（其中N是数据大小）k-均值算法从适当的初始位置。 我们还提出了降低计算负载而且显著提高解决问题质量修改方案。 所提出的聚类方法在为大众所知的数据集上进行测试，并且与随机的k-means算法相比较。
关键词：聚类; k-Means算法; 全局优化; kd树; 数据挖掘
1.介绍
一个基本问题经常出现在诸如模式识别，图像处理，机器学习和统计等各种各样的问题上，这就是聚类问题[1]。 在其基本形式中，聚类问题被定义为给定数据集中的同组数据分组的问题。 这些组中的每一个都被称为一个簇，并且可以定义为一个区域，其中物体的密度局部高于其他区域。
最简单的聚类形式是分区聚类，旨在将给定的数据集划分为不相交的子集，以便优化特定的聚类准则。 最广泛应用的标准是聚类误差准则，该准则针对每个点计算其距离相应聚类中心的平均距离，然后获取数据集中所有点的这些距离的总和。 一种流行的聚类方法，最小化聚类是k均值算法。 然而，k-均值算法是一个本地搜索过程，它有一个严重的缺点，即其性能严重依赖于最初的约束条件[2]。 为了解决这个问题，已经开发了几种基于随机全局优化方法（例如模糊算法，遗传算法）等其他技术。然而，必须指出的是，这些技术还没有得到广泛的接受，并且在许多实际应用中使用的聚类方法是具有多次重启的k-均值算法[1]。
在本文我们提出了全局k均值聚类算法，它构成了一个确定性有效的全局聚类算法，用于最小化使用k均值算法作为局部搜索过程的聚类误差。 该算法以增量方式进行：用M个群集来解决聚类问题，所有中间问题都是各簇依次求解。 所提出的方法的基本思想是，使用一系列局部搜索（使用k均值算法）可以获得具有M个群集的聚类问题的最优解。 在每个局部搜索中，聚类中心始终被放置在与M1个聚类的聚类问题对应的最佳位置。 剩余的第M个聚类中心最初放置在数据空间内的多个位置。 因为对于M=1，已知最优解，所以我们可以迭代地将上述过程应用于针对所有k聚类问题k=1...M的第二最优解。 除了有效性之外，该方法是确定性的并且不依赖于该方法在任何初始条件或经验可调参数。 与上述所有聚类方法相比，这些都具有显着的优势。
minus;
minus;
在下面的章节中，我们首先对均值聚类进行形式化定义并简要描述k均值算法，然后我们描述所提出的全局k均值算法。 第3节描述了基本方法的修改，这些修改需要较少的计算，但代价是见效甚微。 第4节提供了实验结果并与多重启动的k均值算法进行比较。最后，第5部分提供结论并描述未来研究的方向。
2.全局k均值算法
假设我们得到一个数据集：
M聚类问题旨在将这个数据集划分为M个不相交的子集（集群）C1，...，CM ，从而优化聚类准则。 最广泛使用的聚类准则是包含xi的子集Ck的每个数据节点xi和质心mk（聚类中心）之间的欧几里得距离的平方和。 这个标准被称为聚类平衡并且依赖于聚类中心m1...，mM
其中如果X在定义域内则I（X）= 1，否则为0。
k-means算法针对聚类错误提出局部最优解。 它是一种快速迭代算法，已被用于许多聚类应用中。 它是一种基于点的聚类方法，从最初放置在任意位置的聚类中心开始，并通过在聚类中心的每一步移动来进行，以最小化聚类错误。 该方法的主要缺点在于它对集群中心初始位置的敏感性。 因此，为了使用k-means算法获得接近最优的解决方案，必须将多个运行安排在集群中心的初始位置。
在本文中，提出了全局k均值聚类算法，该算法构成了确定性全局优化方法，其不依赖于任何初始参数值并且使用k均值算法作为局部搜索过程。 与大多数全局聚类算法的情况一样，不是像所有聚类中心那样随机选择初始值，而是以增量的方式进行尝试，以在每个阶段最佳地添加一个新的聚类中心。
更具体地说，为了解决M个群集的聚类问题，该方法如下进行。 我们从一个聚类（k = 1）开始，第二个聚类的最佳位置对应于数据集X的质心。 为了解决两个群集（k = 2）的问题，我们从聚类中心的以下初始位置执行k均值算法的N次执行：始终放置第2个聚类中心
在k = 1的问题的最佳位置处，而在执行n处的第二中心位于数据点xn（n = 1... N）的位置。 在k-means算法的N个执行之后获得的最佳解决方案被认为是k = 2的聚类问题的解决方案。
从初始状态（m1*（k 1） ...m(kminus;1)lowast;k-1）,xn）开始。 从N次运行中获得的最佳解被认为是k聚类问题的解（m1(k); ...：mk(k)）。 通过以上述方式进行，我们通常会获得一个M群集解决方案也为所有人提供了解决方案k-M的k-聚类问题。
minus; minus;
后者的特征在许多应用中都是有利的，其中目标还在于发现“正确”数量的簇。 为了达到这个目的，我们必须解决各种数量聚类的k-聚类问题，然后采用适当的标准来选择最合适的k值[3]。 在这种情况下，所提出的方法直接为k的所有中间值提供聚类解决方案，因此不需要额外的计算e3ort。在计算复杂性方面，该方法需要N次执行k均值算法。对于k（k = 1...M）的每个值。 根据可用的资源和N和M的值，算法可能是一种有吸引力的方法，因为如实验结果所示，该方法的性能非常好。 而且，正如我们稍后将会展示的那样，为了减少计算负担，可以应用几种修改。
所提出的方法背后的基本原理是基于以下假设：具有k个群集的最优聚类解决方案可以通过从初始状态开始的局部搜索（使用k均值）
*1：（k-1）个中心放置在（k-1）聚集位置
*2：剩下的第（k-1）个中心被放置在适当的位置被发现
这个假设看起来很自然：我们期望k-聚类问题的解决方案（通过本地搜索）可以从（k -1）聚类问题的解决方案中获得，一旦将附加中心置于数据中的适当位置组。 将第k个中心的可能初始位置的集合限制为可用数据点的集合X也是合理的。 必须指出的是，这是一个相当计算量的重大假设，也可以考虑其他几种选择（检查较少的初始位置）。 由于在所有实验中（并且对于所有k值），上述假设也通过实验得到验证，所以通过所提出的方法获得的解与使用k均值算法的大量随机重新启动所获得的解相比至少是一样好的。 本着这种精神，我们可以谨慎地陈述这一点所提出的方法在实验上是最优的（尽管从理论上证明是很难的）。
minus;
3.加快执行
基于全局k均值算法的总体思想，可以设计几种启发式算法来减少计算负载，而不会显着影响解决方案的质量。 在下面的小节中提出了两个修改，每个修改都涉及该方法的一个不同方面。
3.1快速的全局k均值算法
快速全局k均值算法构成了加速全局k均值算法的直接方法。 考虑到解决方案，差异在于获得k聚类问题的解决方案（k - 1）聚类问题。 对于N个初始状态（m(1)（k 1）...m(kminus;1)*（k 1）;xn）中的每一个，我们不执行k均值算法，直到收敛以获得2nal聚类错误En。 相反，我们针对所有可能的分配位置xn计算所得误差En上的上限En6Ebn，其中E是（k1）聚类问题中的误差，b n如方程 （2）。 然后，我们在最小化En的点xi处初始化新聚类中心的位置，或等价地使bn最大化，然后执行k-均值算法以获得具有k个聚类的解。正式我们有：
3.2用kd树初始化
kd树[6,7]是标准一维二叉搜索树的多维推广，有利于kd数据集的存储和搜索。kd树将数据空间递归划分为不相交的子空间。 树的每个节点定义原始数据空间的子空间，并且因此包含驻留在该子空间中的数据点的子集。 每个非终结节点有两个后继者，每个后继者都与使用切割超平面对父空间进行划分而获得的两个子空间中的一个相关联。 kd树结构最初用于加速基于距离的搜索操作，如最近的邻居查询，范围查询等。在我们的例子中，我们使用原始kd树的变体。参考文献中提出。 [7]。 在那里，切割超平面被定义为垂直于方向的平面对应于每个节点的数据点的主成分，因此该算法可以被看作是一种方法用于嵌套（递归）主成分分析的数据集。 如果创建的终端节点（称为存储桶）包含少于预定数量的点b（称为存储桶大小）或已创建预定数量的存储桶，则递归通常会终止。 事实证明，即使该算法不用于最近邻居查询，只是树的构造提供了数据集的非常好的初步聚类。 这个想法是使用桶中心（比数据点少）作为提供算法的可能插入位置。
在图1中，平均性能结果显示在10上数据集每一个由从15个高斯分量的相同混合物绘制的300个数据点组成。 高斯混合物的成分很好地分离并且显示出有限的偏心率。我们将三种方法的结果与k = 15个中心的聚类问题进行比较：
- 虚线表示使用快速全局k均值算法和所有数据点构成潜在插入位置时的结果。 10个数据集的平均聚类误差为15：7标准偏差1：2。
- 实线表示使用标准k-means算法时的结果：对每个数据集进行一次运行。 在每次运行中，15个集群中心最初被定位到从应用kd树算法获得的桶的质心，直到15个桶被创建。 10个数据集的平均聚类误差为24.4，标准差为9.8。
- 实线（误差线表示与平均值的标准差）表示使用快速全局k均值算法时的结果，其中潜在插入位置受kd树的桶的质心约束。 在横轴上，我们改变最后一个方法的kd树的桶数。
图1.从具有15个分量的高斯混合物得到的数据的性能结果。
我们还计算了每个数据集的“理论”聚类误差，即通过使用真正的聚类中心计算的误差。 10个数据组的平均误差值为14：9，标准偏差为1：3。 这些结果与标准的快速全局k均值的结果太接近，将它们包含在2gure中。
我们可以从这个实验得出结论：（a）快速全局k均值方法比使用kd树方法初始化所有中心时的性能显着提高，并且（b）限制插入位置对于那些由kd树给出的快速全局k均值（而不是使用所有数据点），如果我们考虑kd树中超过大量的桶（通常大于数组的簇数），则不会显着降低性能）。
显然，也可以将上面提出的kd树方法与全局k均值算法一起使用。
4.实验结果
我们已经在几个众所周知的数据集上测试了所提出的聚类算法，即虹膜数据集[8]，合成数据集[9]和图像分割数据集[8]。 在所有的数据集中，我们对通过只考虑特征向量和忽略类标签获得的聚类问题进行了实验。 虹膜数据集包含150个四维数据点，合成数据集250个二维数据点，对于图像分割数据集，我们考虑通过原始18维数据点上的PCA获得的210个六维数据点。 所获得的解决方案的质量根据2nal聚类错误的值进行评估。
对于每个数据集，我们进行了以下实验：
对于M = 15，全局k-均值算法的一次运行。对于M = 15，快速全局k均值算法的一次运行。k = 1的k-均值算法; 对于k的每个值，k-means算法执行N次（其中N是数据点的数量），从k个中心的随机初始位置开始，并且我们计算了最小和平均聚类误差以及它的标准偏差。
对于三个数据集中的每一个，实验结果显示在图1和2中。 2-4，分别。 每个2gure图将聚类错误值显示为聚类数量的函数。 很显然，全局k均值算法是非常有效的在所有情况下提供与k均值算法相同或更好质量的解。 就算法的快速版本而言，令人鼓舞的是，尽管执行速度更快，但它提供了与原始方法相媲美的卓越质量解决方案。 因此，它构成了一个非常高效的算法，无论是在解决方案质量和计算复杂度方面，如果使用前面章节解释的kd树，运行速度会更快。
在下面的小节中，我们提供了将该算法的快速版本与具有随机初始化的常规k均值算法进行比较的大量实验结果。
图2.虹膜数据集的性能结果。
图3.合成数据集的性能结果。
图4.图像分割数据集的性能结果。
4.1纹理分割
在这个聚类实验中，目标是聚类从一组37个Brodatz纹理图像中提取16*16像素图像块[10]。 每个完整的纹理图像由256*256像素和500个贴图组成，每个纹理通过随机选择16个窗口来提取。 预计源自相同纹理图像的补丁形成单个群集（或多个群集）。
对于每个数量的纹理k =2...6，我们随机构建了100个数据集。 每个数据集通过先随机选择37个纹理中的k个，然后为每个纹理选择200个补丁来创建，每个数据集产生200k个补丁。 所有报告的结果均为100个数据集的平均值。
我们比较了三种算法的性能：
（1）使用均匀选择的随机对k均值进行初始化
- 快速全局k均值，
（3）快速全局k均值，插入位置限于相应kd树的前2k个节点。 为了评估不同的方法，我们考虑了贴片的均方聚类误差（MSE）与其最接近的均值。 在第二个实验中，数字集群被认为与选择创建数据集的纹理数量相等。 结果在图5中给出，我们也提供了相应的执行时间（以秒为单位）。 表中的粗体值表示在聚类错误方面具有最佳性能的方法。
我们还进行了第二个系列的实验，其中我们使用了两倍于纹理的簇。 结果显示在图6中。
可以观察到（平均而言）具有随机初始化的k均值算法几乎对每个数量的聚类和纹理给出最差的结果。 值得注意的是，快速
全文共7828字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13483]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
