Mini-batch k-means在O(d/ε)次迭代内终止
本文提出了一种双树算法,用于加速k-means聚类算法在大规模K簇和数据集下进行迭代,在使用了覆盖树后,该算法的单次迭代运行时间为O(N + k log k),并且在实践中表现得很好。
Jan, 2016
我们提出了一种新颖的加速精确k-means算法,在18个实验中比现有低维算法更优秀,速度快了最多三倍。 我们还通过更好地估计用于减少距离计算次数的距离界限,对现有最先进的加速精确k-means算法进行了总体改进,在44个实验中实现了速度提升,最高达到1.8倍。最后,我们提出了标准方法的简化版本,并表明它们在59个实验中比其全面版本更快。
Feb, 2016
通过使用Elkan(2003)的距离界限方法来加速Sculley(2010)的Mini-Batch K-Means算法,提出了一种新算法。使用嵌套的Mini-Batches提出了两个困难。实验表明,得到的嵌套Mini-Batch算法非常有效,通常比标准Mini-Batch算法早100次到达经验最小值的1%。
Feb, 2016
该论文研究了在线学习和小批量k均值变体算法在大规模聚类和无监督特征学习中的应用,通过对算法的解空间轨迹的描述和对几何洞察的利用,克服了$k$-均值目标函数的非凸和不可微问题,并证明了在一般条件下,它们能以速率$O(rac{1}{t})$收敛到一个局部最优解,并且在可聚类数据集上,小批量$k$-means算法还可以在高概率下收敛到最优$k$-means解。
Nov, 2016
本文针对一类损失函数和梯度提升算法,展示了停止迭代估计器的性能与相关函数类的本地高斯复杂度之间的直接联系,并证明了高斯或Rademacher 复杂性的本地不动点分析可以用于推导最佳停止规则,为各种核类别推导了这种停止规则,并说明了我们理论和实践的对应关系。
Jul, 2017
本文研究在实际应用中,哪些加性扰动稳定性的实例可以设计有效算法,并证明它们能找到最优聚类。我们提出了一种稳定性定义,并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时,我们显示出一种具有证明保证的鲁棒算法,也能容忍异常值。通过研究真实数据集的稳定性,我们补充了这些结果,并展示了我们的算法在这些基准数据集上的表现。
Dec, 2017
本研究使用能量景观方法探寻$K$-means算法中数据集异常值对其性能的影响,发现其代价函数表面会形成更窄的漏斗形态,每个漏斗之间会有一些不支持聚类的区域,而其中的浅漏斗则对应不同类型的聚类解决方案,而异常值的逐渐增多会导致漏斗内的路径变长以及准确性和成本函数之间的相关性降低。最后,本研究提出了一种新的聚类相似度测量方法,能够忽略异常值的影响,并在多异常值的数据集中进行了应用。
Jun, 2023
我们研究了无重复抽样的最小批量梯度下降在最小二乘回归中的离散动力学。我们证明最小批量梯度下降的动力学和泛化误差取决于原始特征X和一组新特征X̃之间的样本交叉协方差矩阵Z,在学习过程中每个特征都被之前出现的最小批次平均修改。利用这个表示,我们严格证明了最小批量梯度下降的动力学与全批量梯度下降在步长的线性尺度规则下达到了一致的主导阶。我们还研究了连续时间梯度流分析不能检测到的离散化效应,并显示最小批量梯度下降收敛到与步长相关的解,与全批量梯度下降相反。最后,我们利用自由概率理论工具,在假设随机矩阵模型的情况下,数值计算了Z的谱。
Jun, 2024