基于样本的大数据集高效聚类方法

12403一种基于样本的大数据集高效聚类方法Georgios Exarchakis*IHU法国斯特拉斯堡ICube，斯特拉斯堡大学，CNRS，法国索邦大学，INSERM，CNRS，法国视觉研究所，17 rue Moreau，F-75012巴黎，法国georgios. ihu-strasbourg.eu奥马尔·乌巴里索邦大学、INSERM、CNRS、视觉研究所，17 rue Moreau，F-75012巴黎，法国格雷戈尔·伦茨索邦大学、INSERM、CNRS、视觉研究所，17 rue Moreau，F-75012巴黎，法国摘要我们提出了一种简单有效的聚类方法，用于具有大量聚类的多维数据。我们的算法通过评估具有集群中心子集的数据点的分布来实现高性能我们的贡献比k-平均值效率高得多，因为它不需要对数据点和聚类进行全面比较。我们证明了近似的最优解与精确解相同。然而，与最先进的方法相比，我们的方法在提取这些聚类方面要有效得多。我们在一系列标准化聚类任务上将我们的近似与精确k均值和替代近似进行了比较对于评估，我们考虑算法的复杂性，包括收敛的运算次数和结果的稳定性。该算法的有效实现可在线获得。1. 简介数据聚类是机器学习文献中普遍存在的问题。最流行的聚类方法之一是k-means算法。由于算法的简单性和识别聚类的相对效率，该算法已在广泛的领域中使用，例如医学、物理学和计算机视觉等。随着数据供应量的不断增加，计算*通讯作者。效率的提高变得更加重要。近似推理方法的最新进展已经允许训练具有收敛性能的算法，该收敛性能对于聚类的数量是亚线性的[16]。这通常是通过避免在数据点和在特征空间中相距甚远的簇之间进行比较来实现的。在高斯混合模型（GMM）中可以找到与k-均值算法相关的概率数据模型。特别地，Lücke和Forster [31]详细描述了k-均值和各向同性GMs的期望最大化（EM）算法的变分近似之间的关系。在大多数情况下，基于GMM的聚类问题公式提供了更高的可能性，而不会产生不切实际的约束。高斯混合模型（GMM）收敛分析的理论发展[9，32，35]涉及全局和最优收敛，重新引起了该领域的兴趣。正在积极开发旨在提高稳定性[22，24]和效率[16，21]的新训练算法。马尔可夫链蒙特卡罗（MCMC）方法也已用于拟合GMM以解释输入变化[13，27，36]。基于树的方法也被提出用于k-均值的有效推理[19，34]。然而，已知基于树的方法在面对数据中的小扰动时表现出不稳定性，这是由于它们的重复结构，因此可能对于输入中的小变化产生实质上不同的在本文中，我们提出了一种基于EM的有效学习方法，该方法使用E步中后向的截断近似[29，30]为了确定截断的空间，我们12404.Σ|NU{}YCYY|CC.ΣC.ΣD-2（n）（n）2C= C |Y = y（n）; θ后向分布p音乐元数据集[5]和SUSY，一个高能量的从基于前一迭代的截断子空间的建议分布中抽取样本，并青睐前一截断后的最佳聚类附近的聚类。我们的算法结合了初始化方法[1，2]的最新发展，并且可以应用于核心集[3，20]，以保持与最先进方法相当的性能。截断近似在过去已用于多原因模型[8，11，12，15]，以实现离散潜在变量模型中的有效还提出了截断空间上的随机近似[18，29]，重点关注深度学习模型。我们期待一个随机近似来避免与基于EM的GMM学习相关的众所周知的局部最优问题[23]聚类算法上的截断近似仅使用确定性近似技术[16，21]。事实上，我们的文献研究表明，vc-GMM [21]在具有类似约束条件的GMM的计算效率方面是最先进的。在保持集群性能的同时执行各种任务。2. GMM的稀疏采样聚类EM为了在优化框架下引入k-均值算法，我们考虑了一个与期望最大化算法相匹配的高斯混合模型Lücke和Forster详细描述了k均值和变分近似之间的关系。使用基于GMM的形式化，我们可以推导出一种新的聚类算法，其全局最优性与原始算法相同，并且具有显著的计算效率优势。对于N个数据点的数据集，=y（1）。. .，y（N）我们希望识别，M，聚类中心µ c，c 1，. .. ..和M.为此，每个数据点y（n）被视为随机变量Y的实例，该随机变量Y遵循M个可能的高斯分布p（Y C= c;θ）=（Y; µ c，σ1）中的一个，其中C取我们研究的那些。vc-GMM在一组索引上的关系按顺序分配给同一群集的数据点{1. .. .. M}和θ ={µ}M.1：M，σ}不注释设置识别相似的聚类。在每个步骤中识别最相似的集群，并立即将其分配给数据点的截断空间，以有效地导航到最佳集群解决方案。然而，该方法是确定性的，并且这种方法通常表现出初始化不稳定并且频繁地收敛于局部最优的结果。因此，探索这些近似值的随机类似物是谨慎的我们在本研究中采用的方法与vc-GMM非常相似，但我们使用了相似性。模型参数。 我们可以学习最优参数θ ={µ1，...，M，σ}，通过使用EM算法最大化数据对数似然性（θ），logp（Y = θ）。 EM算法将变分下限优化为对数可能性：L（Y，θ），\（\）\）\（\）\（\）C=c，Y=y（n）|θάNC+ΔH.p（n）⇒（1）在集群上建立矩阵，以便识别靠近数据点的概率更高的集群，而不必估计其到所有集群的距离。评估Simi-=>>NCp（n）lognPC=C|Y=y（n），θp（n）早期后向近似的稀疏矩阵相关性并且不需要过多的计算。我们证明了我们的随机方法在vc-GMM的性能上有所改进，并且我们认为我们的算法的定义和实现非常简单。在数值实验部分，我们评估了C+Σlogp。Y=Y（n）|θά（2）其中Hp（n）表示分布的香农熵。 p（n）分布通常设置为算法性能及与相关C的比较文学。 在人工数据部分，我们评估我们的.C就这样该算法在提取地面真相方面进行了改进，并将其与k-平均值进行了比较，以观察到性能的改善。在真实数据聚类部分，我们将算法应用于等式的第一项2到0和变小下限等于对数似然1。在假设之下定义了每个高斯分布的模型约束四个不同的数据集，称为KDD，一种蛋白质同源性作为PC. Y=Y（n）|C = c; θΣ =C.2πσ2 Σ−2eC2σ ，在哪里数据集[7]，CIFAR-10，图像数据集[25]，SONG，ad=y−μ是平方欧几里得距离be −物理数据集[4]。我们在效率、稳定性和准确的聚类恢复方面将我们的算法与最先进的算法进行了比较。结果表明，我们的算法在效率方面处于最先进的水平，而不会影响稳定性，并可能提高稳定性。我们的方法可以广泛应用。nD12405C将数据点y（n）与高斯指数的平均值相加由c表示，D是观测变量的数量。Exact EM是一种迭代算法，通过在两个步骤之间交替来优化可能性。第一步，1方程的第一项 2是分布bP（n）和exactposterio r，p之间的负KL-发散。C=C|Y=y（n），θά。12406C我⇒PjC（n）（n）CCCqlogpp>→→OCKKCΣC我们注意到这个等式。3是一个softmax函数，q（n）logcc'≤ K（n）C' p（n）E-step是识别设置最低证明的p（n）分布。 因为所有高斯都是可能相等的（n）<在等式中绑定2等于对数可能性。这是p（n）必须等于后一个，以便设置KL-（n）j（n）我>p（n）。 注意limx→0xlogx=0。它C方程中的发散。2等于0。对于本工作中的高斯混合模型，它将是：以下内容：KL[q（n）p（n）]KL[q′（n）p（n）]p（n）=经验值.−dc/2σ2άM./c'=1经验值.−dc'/2σά（3）c>K（n）q（n）对数（n）C（n）C K'（n）q′（n）logq′（n）（n）C（n）/（n）→→p（n）Duces的值大多为0。 事实上，对于σ2 0 ，它正好是等于（负数）的Cc> K（n）Σ（n）Cp（n）/άp（n）0代表所有其他人，通常被认为是k-means的胆汁类似物[6，26，31]。第二步，M步，最大化方程的量。1关于θ，使用梯度更新为：c> K'（n）Cc>K（n）（n）C（n）Cc'> K（n）（n）C'N（n）μ =（n）q′（n）logp（n）C⇒N（n）c> K'（n）日志Σp（n）>log⇒c'交存K'（n）σ2=1 （5）第（2）款所指的第（1）款所指的第（1）款所指的第（2）款所指的第（2）款所指的第（3）款所指的第（3）款所指的第（4）款所指的第（5）款所指的第（5）款所指的第（6）款所指的第（6）款所指的第c'> K（n）c'交存K'（n）EM算法在E步和M步之间迭代，直到θ收敛。更新σ2，与σ20在k-均值中产生的硬赋值相反，增加了变分下限，并提供了更好、更有效的对数似然近似。E-step需要估计所有聚类和所有数据点之间的差异。因此，E-step（DNM）的复杂性使其成为非常有效的算法。在这里，我们集中在一种方法，以避免估计软最大的所有维度，因为它导致冗余计算。为了避免复杂度对M的依赖性，我们使用后r，p（n），overa的近似值q（命题1表明，为了减少每个E步的发散，我们只需要用接近数据点y（n）的聚类迭代地更新集合（n）。M阶跃可以修改为使用q（n），而不是p（n），并保持单调收敛。要识别（n）中的聚类，我们从选择H均匀随机聚集。我们反复更新（n）通过在最接近数据点y（n）的聚类的邻近区域中使用R随机采样聚类。为了有效地识别以数据点附近为中心的集 群 ， 我 们 定 义 了 一 个 分 布 式 b 函 数 p（Ct|Ct−1=cn;S），其中cn=最小值d（n）|c> K（n）C. - 的参数S奏效RM×M（n）实验室−d（n）/2σ2ά（n）.（n）⇒（6）注意分配的聚类之间的相似性矩阵更高的值，Si，j，到群集对等体，{i，j}，可能qc=c'> K（n）经验-dc'/2σ2Δδc> K接近相同的数据点，如等式中所示。 12. 迭代K（n）的更新定义为：δ在哪里。C（n）是克罗内克三角洲。 换句话说，K（n）DQppp距离，即返回最小距离的值1。（四）C'我jDN n=1c =1-12407|CC'CCttCc'> K（n）C、C（n），（n）、我们假设外部聚类（n）的概率为0表示数据点y（n），因此不进行估计。使用Kt=Kt−1C1：R|ci~p（C t）|Ct−1=c>n）>ci>/Kt−1（七）q（n）而不是p（n），将exactEM算法修改为K（n）=，c|c>K（n），其中H最小d（n），（8）我们可以推导出一个单调的算法通过识别q（n）来增加v的算术l或wer绑定这减少了每个E步处的KL发散建议1. 设K（n）是一组聚类指数，并且其中t表示EM迭代。p（CtCt−1=cūn;S）是在将对应于K（n）的概率设置为0之后由聚类相似性矩阵S的归一化行给出的分布：K′（n）=K（n）\{i}{j}，其中r ei>K（n），j>/K（n）。然后我jC，C.（n）⇒如果（>CK（n）如算法1中所更新。AFK-MC2算法σ2= DNn=1c÷ K（n）q（n）（11）初始中心µ1≤ Y的样本随机且均匀然后将其用于Iv e建议分发bg（y|1）。A相似性矩阵基于距离定义。d（n）在假设邻近聚类到相似数据点的距离较小的情况下长度为m的马尔可夫链用于充分采样tinct新中心，µ2 ： M，迭代。AFK-MC2的复杂度是（ND）来定义命题分布g（yμ1）。使用马尔可夫链从数据中采样中心1，d（n）+d（n），..（n）⇒长度为m，复杂度为O。m（M−1）2Dά。i，j=EINn=1jδ{i，j}K（十二）轻型Coresets（LWCS）。为了进一步提高会计效率，我们可以选择使用算法1数据相似性高斯混合模型（D-GMM）要求：数据集，中心数量M1：初始化μ1：M，σ，（n），对于所有n，S=02：重复3：µnew=0，σnew=0，Snew=0数据集[3，14，28]。核心集较小，N′< K（n）q（n）logp.C=c，Y=y（n）|θά.Σ6：cn=argminc y-μc|c>K（n）8：K（n）=。C1：R|ci~p（C t）|Ct−1=cn;S）ci/K（n）9：K（n）=K（n）=K（n）10：f或c>K>（n）do11：d=y-μC（十三）因为参数更新是基于梯度的更新。13，权重w1：N'是参数上的乘法常数，因此参数更新为：13：K（n）=C|c>K（n），其中H最小d（n）14：结束µC=N'N'wnq（n）y（n）/wnq（n）（十四）15：计算µ1：Mσ2和S，使用等式。10n=1n=116：直到μ和σ2收敛N'1：M21⇒（n）（n）等式12产生对称正定矩阵，σ=DN'"Nn=1cwn qcµC（十五）用于对每个最佳点附近的数据点进行采样该过程的步骤，对预先计算的值进行简单的归约操作。在等式之间迭代。第六章和爸爸1N′n=1d（n）+d（n），..Σ更新，方程式。10-12 ，详细描述了我们称之为数据相似性GMM（D-GMM）的算法，Alg. 1，由于相似性矩阵是基于数据"投票"过程。与精确EM算法的E步相比，D-GMM算法的EC2Y（n）使用AFK初始化i，j=WNE我jδ {i，j} KΣ（十六）12409对 于 从 O （ NMD ） 到 O （ N （ R+H ） D ） 的GMM，其中这些更新可能会取代等式。算法1中的10到12允许应用程序在一个核心集上运行。在coresets上的工作引入了一个在早期工作中被严格分析的近似误差。[3构建核心集需要对数据进行两次复杂性迭代（ND）。在核心上工作可将D-GMM的复杂性降低到124101e5地面真相D-GMM预测变式下限.OOO2.01e6-800-1000-12001.514001.00.50.0VC-GMMk-平均值D-GMM-1600-1800-2000二四六八十迭代算法的876Y54322 3 4 5 6 7 8x1e5图1.二维合成数据集验证：D-GMM在500项试验中优于其他方法（顶部），并完全恢复所有中心（底部）（N′（R+H）D）用于E步，N′HD+N′H2用于M步。 AFK-MC 2的复杂度也降低了，因为命题分布被定义在复杂度为O（N ′D）的核心集上。3. 实验和结果我们评估了实验算法在三类任务上的性能用于实验的软件是在补充材料中提供的矢量化C++实现首先，我们研究了人工数据的融合，在这种情况下，基本事实是已知的。我们继续与最先进的算法进行比较，以在流行的聚类数据集上训练具有类似vc-GMM约束的GMM [21对于所有任务，使用AFK-MC2算法初始化高斯中心，m=5。此外，我们遵循与[21]中相同的收敛协议，并在以下等式的变分下限增量时终止算法。13小于=10−3。除此之外，我们还评估了所有实验重复10次的结果稳定性。为了清楚起见，下面是超参数符号的提醒：• M表示中心图2. 与精确算法算术的对数似然性相比，通过EM迭代的D-GMM的变弱定界值：我们可以看到，我们的近似收敛得更慢，然而，每次迭代的效率要高得多。• N'denotes核心尺寸H和C′分别表示D-GMM和vc-GMM的截断子空间的大小。R和G分别是D-GMM和vc-GMM的搜索空间超参数当选择截断超参数H（C′）时，我们在假设较低的概率值将是可忽略的情况下，考虑精确的后一次衰减的概率值呈指数且一致地设置H=5（C′=5）。对于截断更新R（G），我们遵循相同的原理。我们为M和N'使用了各种配置，因此我们可以将其与最先进的配置进行比较。3.1. 人工数据在本节中，我们对N = 5000个数据点和15个高斯中心的人工数据[ 17 ]进行了收敛分析。图左边的1显示了算法的学习中心和地面真实中心之间的根均方误差。我们将我们的算法D-GMM与vc-GMM和标准k-均值进行了比较，将超参数设置为M=15、N′=1000、H=3和R=5。 VC-GMM用C′=3和G=5参数化。结果表明，两种截断算法都能像精确算法一样有效地恢复中心。轻微改进（低于标准差）可能归因于这样一个事实，即截断近似将使用D-GMM算法，随机行为也可能对避免局部最优解有影响。在右侧的图1中，我们显示了一个运行示例，其中中心被成功恢复。3.2. 聚类分析为了与现有技术进行更详细的比较，我们考虑一系列众所周知的聚类数据集。标签。精确GMMD-GMM根均方误差··12411错误是CQ-Q QQC表1.相对量化误差和距离评估速度数据集相关算法距离评估。加速Iters.名称N′H（C′）R（G）M=500CIFAR-10KN列=50，000k-N试验=10，000VD=3，072M=500DM= 4000苏西·KN=5，000，000k-D=18VM= 2000D1详细比较了k-means、vc-GMM [16，21]和D-GMM。我们在完整数据集上使用k-均值算法来定义中心的基线。其余算法的准确性使用相对值来测量。误差η=（算法由于D-GMM和VC- GMM在每次迭代中每个数据点通过更少的簇，因此这两种算法的收敛速度较慢。(see图2）。然而，算法的效率由距离评估的总数确定。在Tab的最后两列中。1，我们将从初始化到收敛的平均迭代次数表示为距离估计方面的平均速度，d（n），相对于k-均值。结果显示，在大多数情况下，D-GMM的速度明显加快，相对误差相当。图3.比较了增加核心集大小的高效聚类算法完整数据集的K-平均值作为基线。图3中每个标记的大小表示环的大小。我们发现，在大多数情况下，D-GMM聚类数据与距离评估最小量的基线相比相对误差较低复杂性我们使用的近似方法是集中的在避免距离评估的情况下，d（n）与所有可用的聚类。因此，它在数据集中预期存在大量聚类的问题中非常有效。图4（左）显示了CIFAR-10数据集上M个聚类数量增加时算法的缩放行为，M的范围从100到1500个聚类中心。每个算法的距离估计由跨越所有M的最小值进行非恶意化，并以对数对数图表示，该对数图指示操作复杂性和聚类数量之间的关系的强度。我们对两个轴进行了归一化，以便于可视化复杂性。正如预期的那样，k-均值的缩放行为与聚类的数量是线性的，而近似值是亚线性的。随着聚类中心数量的增加，D-GMM是距离评估方面最有效的算法稳定性我们测试算法使用不同初始化恢复相同聚类的能力。我们使用超参数M=500、H=5、R=5在CIFAR-10上运行聚类算法100次，并在重新洗牌后使用中心之间的l2所有误差之间的平均偏差和标准偏差如图4（右）所示。在图5中，我们看到了超参数H和R对优化速度的影响。在上图中，我们设置H=5，并查看R对算法的运算次数和运行时间的影响。我们看到，R值的减小逐渐减少了所需的操作量。就运行时而言，低于R=40的值会导致较低的速度。这是因为我们需要执行更多的迭代，因此实例化采样器所花费的时间比- 平均值--0。0± 0。0%×1。0± 0。07. 6 ± 0。4平均值+LWCS 2 12--7。0± 0。1%x 48。9± 3。55. 4± 0。4c-GMM212557. 0± 0。0%×674。7± 45。811. 8± 0。8- 平均值--0。0± 0。0%×1。0± 0。014. 7 ± 0。4平均值+LWCS 2 16--6。0± 0。1%×11。1± 0。414. 1± 0。5c-GMM216556. 0± 0。1%×663。1± 17。125. 4± 0。6KDDk-平均值---0. 0± 0。7%的×1。0±0。05. 0± 0。0N=145， 751k-平均值+lwcs212--14. 0± 0。5%×35。1±0。05. 0± 0。0D=74vc-GMM21255512. 0± 0。百分之四12. 0± 1。0%533. 1± 36。5622. 1± 28。011. 7± 1。0宋克--0. 0± 0。0%×1。0± 0。05. 0± 0。0N=515.345k-平均值+lwcs216--8. 0± 0。0%×7。8± 0。05. 0± 0。0D=90vc-GMM2165D-GMM2165558. 0± 0。1%8. 0± 0。2%698年。2±0。7862年。1±12. 0± 0。021. 7± 0。12412VC-GMMk-平均值+LWCSD-GMM基线核心尺寸k-meansvc-GMMD-GMM根均方误差0.120.100.080.060.040.020.008.5 9.0 9.5 10.0 10.5 11.011.50.120.100.080.060.040.02500010000150002000025000三万人CIFAR-10M=5000.250.200.250.200.150.100.050.008.0 8.5 9.0 9.510.010.511.0。11.512.00.150.100.05歌曲M=400020000400006000080000100000120，000140，0000.1750.1500.1250.1000.0750.0500.0250.0008.0 8.5 9.0 9.510.010.511.011.5log10距离评估0.180.160.140.120.100.080.060.040.02苏西M=200020000400006000080000100000120，000140，000核心尺寸图3.在越来越大的数据集上，距离估计与相对量化误差复杂性1e3稳定性8 2.0641.51.020.5二四六八0.0标准化对数10聚类数vc-GMMk-meansD-GMM算法图4.CIFAR-10的操作复杂性和稳定性超过100次试验。（右）学习中心之间的MSMR（M = 500）。（左）M增加的标准化对数距离评估，每个M有100次试验。（两个）误差条不包括1个标准差。从它们中为了确定最优超参数H，我们将R=10，并观察H的值对算法的运行时间和运算次数的变化影响。运行时和操作数单调减少具有较小的截断空间H。建议仅缓存少量中心就足以有效地对数据点进行群集。为了测试D-GMM到更大数据集的可扩展性，我们使用了整个ImageNet数据集，该数据集被采样为64 x64分辨率。VC-GMMk-平均值+LWCSD-GMM基线核心尺寸VC-GMMk-平均值+LWCSD-GMM基线核心尺寸VC-GMMk-平均值+LWCSD-GMM核心尺寸VC-GMMk-平均值+LWCSD-GMM核心尺寸VC-GMMk-平均值+LWCSD-GMM核心尺寸相对量化误差标准化Log10距离评估12413k-平均基线D-GMM距离评估速度D-GMM运行时速度据我们所知，它是最高效的GMM算法100美元，可供出租。在计算复杂性方面，我们的算法在大多数情况下效率更高，与vc-GMM相比，随着数据点数量的增加和聚类数量的增加此外，如CIFAR所示，集群中心的恢复更加稳定，从而补充了效率方面的10个数据库。101000140 60 80 100截断子空间的新样本R值得强调的是，与vc-GMM相比，D-GMM的直观性基本上是简单的。有争议的是，在矩阵容器上使用基本操作比在任务特定容器上进行比较更容易。当涉及到在不同的上下文中通信和实现算法时，算法的简单性是一个相当大的优势。我们的实验表明，D-GMM的瓶颈与低级运算符（如计算指数和从离散分布采样改善这些运营商可能是一个有趣的未来10十二十三十四十五十截断子空间大小H图5. R（顶部）和H（底部）的超参数搜索。蓝线显示了计算方面的性能提升绿线在运行时间方面表现出更高的性能。结果是相对于点黑线，这是确切的k-平均值。进化[10]。对于这样一个大数据集，使用k-均值作为基线是不切实际的，因为它不会在合理的时间内收敛，因此我们将比较从初始化到两种算法收敛的距离评估数量的对于核心集大小213、214、215、216和217，与vc-GMM相比，当我们使用D-GMM时，我们的距离评估数量分别减少了22%、31%、40%、44%和49%4. 讨论我们提出了一种新的数据聚类算法。通过计算聚类的数据特定子集上的后验值，我们的算法与k-均值相比显著提高了计算效率通过在每个EM迭代中对性能最佳的聚类的邻近区域进行采样来迭代地重新组合子集。为了识别每个聚类的邻近性，我们提出了一种基于聚类和数据点之间的计算距离的相似性矩阵，此外，我们分别实现了数据预处理和GMM中心初始化文献中最先进的轻量级参数集和AFK-MC 2初始化[1，3]。我们将我们的算法与vc-GMM [16，21]进行了比较，在这部作品中，影响了相当广泛的文学作品。我们认为D-GMM对进一步开发有价值的一个关键特性是，降低的计算复杂性意味着更低的能量需求。因此，在考虑聚类算法中使用的低级运算符来设置未来的软件开发策略时，我们可以考虑D-GMM减少的运算数我们在GMM数据模型上引入的约束对于D-GMM近似至关重要，然而，它们对我们的算法的表达潜力有影响。未来的工作希望以一种允许训练具有更少协方差和先验结构约束的GMM的方式来开发优化算法。为了进一步发展这项工作，我们将与在补充材料中找到的D-GMM实现将在开源许可证下贡献给该组织，并通过与大量研究人员的合作进一步开发。总之，我们发现D-GMM在基于GMM的聚类的效率和稳定性方面是最先进的。在优化低级别运营商和放松GMM限制方面仍有改进空间。一项发展和普及高效集群的长期计划正在进行中。确认;我们要感谢Jörg Lücke在准备这份手稿时的宝贵见解。这项工作得到了法国国家研究局"未来投资计划"（参考ANR-10-IAHU-02）管理的法国国家基金的部分支持k-平均基线D-GMM距离评估速度D-GMM运行时速度加速加速12414参考文献[1] 奥利维尔·巴赫姆、马里奥·卢西奇、哈米德·哈桑尼和安德烈亚斯·克劳斯。快速和可证明的好种子为k-means。《神经信息处理系统的进展》，第55-63页第二、四、八[2] 奥利维耶·巴赫姆、马里奥·卢西奇、S·哈米德·哈桑尼和安德烈亚斯·克劳斯。亚耳时间的近似k-均值++。2016年第十三届AAAI人工智能会议。2[3] 奥利维尔·巴赫姆、马里奥·卢西奇和安德烈亚斯·克劳斯。通过轻量级向量集的可扩展k平均聚类。第24届ACM SIGKDD知识发现数据挖掘论文集，第1119-1127页，2018年第二、四、八[4] 皮埃尔·巴尔迪、彼得·萨多夫斯基和丹尼尔·惠特森。利用深度学习在高能物理中搜索奇异粒子。《自然通讯》，5：4308，2014年。2[5] 蒂埃里·贝尔坦-马希厄丹尼尔·P·W埃利斯、布莱恩·怀特曼和保罗·拉米尔。百万首歌曲数据集。第12 届 音 乐 信 息 检 索 国 际 会 议 论 文 集 （ ISMIR2011），2011年2[6] 塔玛拉·布罗德里克、布莱恩·库利斯和迈克尔·乔丹。Mad-Bayes：基于地图的贝叶斯渐近推导。在机器学习国际会议上，第226-234页PMLR，2013年。3[7] 里奇·卡鲁阿纳、托尔斯滕·约阿希姆和拉尔斯·巴克斯特罗姆。Kdd-cup 2004：结果和分析。ACMSIGKDD探索通讯，6（2）：95-108，2004年。2[8] 戴振文、乔治斯·埃克萨基斯和约尔格·吕克。什么是图像补片的不变闭塞组件概率生成方法。《神经信息处理系统的广告趋势》，第243-251页2[9] 康斯坦丁诺斯·达斯卡拉基斯和高塔姆·卡马特。高斯自学习混合的快速和采样近最优算法在学习理论会议上，第1183-1213页，2014年。1个[10] 贾登、魏东、理查德·索彻、李佳、李凯、李飞飞。Imagenet：一个大规模的分层图像数据库。在2009年IEEE计算机视觉和模式识别会议上，第248-255页2009年。8.[11] Georgios Exarchakis 、 Marc Henniges 、 JulianEggert和Jörg Lücke三元稀疏编码。在潜在变量分析和信号分离国际会议上，第204-212页。施普林格，2012年。2[12] Georgios Exarchakis和Jörg Lücke离散稀疏编码。神经计算，29（11）：29792[13] Stefano Favaro，Yee Whye Teh，et al.非标准化随机测量混合模型的Mcmc。《统计科学》，28（3）：335-359，2013年。1个[14] 丹·费尔德曼、马修·福克纳和安德烈亚斯·克劳斯。通过Coresets可扩展混合模型的训练。《神经信息处理系统的进展》，第2142-2150页，2011年。4个[15] 丹尼斯·福斯特和约格·吕克。半监督神经单电子的截断变分EM。2017年神经网络国际联合会议（IJCNN），第3769-3776页。IEEE，2017年。2[16] 丹尼斯·福斯特和约尔格·吕克。集群能否以亚线性方式扩展其集群？gmms和k-means的变分EM加速。在国际会议-人工智能和统计会议，第124-132页，2018年。1、2、6、8[17] P. Fränti和O. Virmajoki.聚类问题的迭代收缩方法。模式识别，39（5）：761-765，2006。5个[18] 恩里科·吉罗（Enrico Guiraud）、雅各布·德雷夫斯（Jakob Drefs）和约尔格·吕克（Jörg Lücke）。进化期望最大化。在遗传学和进化计算会议论文集，第442-449页，2018年。2[19] 格雷格·哈默利。让K-Means更快。在Pro-2010年SIAM数据挖掘国际会议的会议记录中，第130-140页SIAM，2010年。1个[20] 萨里尔·哈佩德和索姆·马祖姆达尔。关于k-均值和k-中值聚类的尾集。在第三十六届ACM计算理论研讨会论文集，第291-300页，2004年。2[21] 弗洛里安·赫希伯格、丹尼斯·福斯特和约尔格·吕克。用亚线方法的融合加速大尺度高斯混合的训练。IEEE模式分析和机器智能学报。1050：12，2021年。1、2、5、6、8[22] Reshad Hosseini和Suvrit Sra. 高斯混合模型的替代方法：批处理和随机黎曼优化。数学编程，第1-37页，2019年。1个[23] 志进、张玉晨、西瓦拉曼·巴拉克里希南、马廷·J·温赖特和迈克尔·I·乔丹。局部极大值12415高斯混合模型的可能性：结构结果和算法后果。《神经信息处理系统的广告趋势》，第4116-4124页2[24] 索海尔·科洛里，古斯塔沃·K.罗德和海科·霍夫曼。学习高斯混合模型的平滑Wasserstein 距离IEEE计算机视觉和模式识别会议（CVPR），2018年6月。1个[25] 亚历克斯·克里热夫斯基。从小图像中学习多个图层多伦多大学，2012年5月。2[26] 布 莱 恩 · 库 利 斯 和 迈 克 尔 · 乔 丹 。 重 新 审 视 k-means：使用贝叶斯非参数的新算法。arXiv预印本arXiv：1111.0352，2011年。3[27] Y.李，S.帕尔和M。J·科茨。可反转粒子流序列MCMC，扩展到高斯混合噪声模型。IEEE信号处理学报，67（9）：2499-2512，2019年。1个[28] 马里奥·卢西奇、马修·福克纳、安德烈亚斯·克劳斯和丹·费尔德曼。使用Coresets训练高斯混合模型。机器学习研究杂志，18（1）：5885-5909，2017年。4个[29] Jörg Lücke 、 Zhenwen Dai 和 Georgios Exar-Chakis。生成模型的"黑盒"优化的截断变分采样。在潜在变量分析和信号分离国际会议上，第467-478页施普林格，2018年。1、2[30] 约尔格·吕克和朱利安·埃格特。期望截断和预选在训练生成模型中的益处机器学习研究杂志，11（10月）：2855-2900，2010年。1个[31] 约尔格·吕克和丹尼斯·福斯特。k-均值作为高斯混合模型的变分EM近似。模式识别函，125：349-356，2019年。1，2，3[32] Ankur Moitra和Gregory Valiant。确定高斯混合的多项式可学习性。2010年IEEE第51届通信基础年度研讨会-计算机科学，第93-102页。IEEE，2010年。1个[33] 雷德福·M·尼尔和杰弗里·E·辛顿证明增量、稀疏和其他变体合理的EM算法的概述。在学习图形模型中，第355-368页施普林格，1998年。3[34] 詹姆斯·纽林和弗朗索瓦·弗勒雷。具有精确边界的快速k平均值。在机器学习国际会议上，第936-944页PMLR，2016年。1个[35] 徐智、徐智和阿里安·马利基。两个高斯混合物预期最大化的全局分析在神经信息处理系统的进展，第2676-2684页，2016年。1个[36] 杨明贤和阿胡贾。人类皮肤颜色的高斯混合模型及其在图像和视频数据库中的应用在图像和视频数据库的存储和检索中，第3656卷，第458-466页国际光学与光子学会，1998年。1个