ICMLJul, 2021

基于随机化的降维在设施定位和单链接聚类中的应用

PDF
TL;DR本文研究将输入点集 $X$ 投影到随机 $d=O (d_X)$ 维子空间（其中 $d_X$ 是 $X$ 的双倍维数）的随机降维应用到聚类问题中，主要探讨了设施选址问题和单链接层次聚类问题。研究表明，这种方法在维度映射到一定程度时，可以达到在原始空间中找到的最优的设施选址近似值，同时这种方法还可以用于解决最小生成树等问题。
发现论文，激发创造
  • k-Means 聚类和低秩逼近的降维

    研究采用缩略图替代数据矩阵来加速 k - 均值聚类和约束 k - 秩近似问题的精确、近似或启发式算法，并提供降维和草图技术及近似算法来解决这些普遍问题。

    Oct, 2014

  • k-means 聚类的随机投影

    该论文研究了使用降维技术来提高 $k$-means 聚类算法的效率和精度，通过使用随机矩阵对多维数据进行投影，并经过大量实验验证了该方法的准确性。

    Nov, 2010

  • 随机降维的普适性定律及其应用

    该论文研究了一类随机降维映射及其在高维随机几何学中的新普适性，证明在特定数据集上降维成功的概率存在相变现象，从而为数值线性代数算法、压缩感知、随机线性编码等提供了设计原则，并在随机实验设计下为统计估计方法的性能提供了启示。

    Nov, 2015

  • 降维子空间聚类

    本文探讨了三种基于稀疏信号恢复原理的子空间聚类算法在随机投影降维后的表现，发现在数据降维后仍能达到较好的聚类效果，进一步降维则会导致聚类问题无解。

    Jul, 2015

  • 随机降维 k-means 聚类

    本文研究了 $k$-means 聚类的降维问题，提出了第一个能够保证准确的特征选择方法，并针对特征提取提出了两种方法，分别基于随机投影和快速近似 SVD 分解。所提出的算法是随机的，并对最优 $k$-means 目标值提供一定的近似保证。

    Oct, 2011

  • 近线性时间内对倍增度量聚类的近似算法

    针对度量空间中的经典设施定位、$k$- 中位数和 $k$- 均值问题，我们提供了近线性时间的逼近方案，并展示了针对各种变型问题的技术扩展。

    Dec, 2018

  • 具有统计保证的随机降维

    研究论文通过研究快速执行和数据利用的算法，探索了大型模型和数据利用的有效维度减少策略，以及提高泛化和分布鲁棒性的数据增强方法。

    Oct, 2023

  • 降维数据的子空间聚类

    本文研究了基于随机投影降维对稀疏子空间聚类和基于阈值的子空间聚类算法的性能影响，并发现即使将数据维度降到子空间维度的数量级，也不会受到显著的性能损失

    Apr, 2014

  • 一维投影聚类的简单、可扩展和有效方法

    非监督学习中的聚类是一个基础问题，本研究介绍了一种简单的随机聚类算法，它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn)，并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法，通过实验证明与现有方法相比，我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。

    Oct, 2023

  • 学习增强的降维 K 均值聚类

    使用主成分分析（PCA）降低数据集的维度，提高 k-means 算法在特定质心下的预测性能和降低成本。

    Jan, 2024