Jun, 2021

高维情况下近似最优的可解释 k 均值算法

PDF
TL;DR介绍了一种可解释性聚类方法，算法通过应用决策树将数据划分为轴平行超平面聚类，使得聚类边界简单，同时保证聚类代价函数的可解释性约束，聚类的代价至多是比不考虑可解释性约束的情况最小代价增加 $k^{1-2/d}$ 倍，与其他方法的代价上界取最小值可得到 $k^{1-2/d} polylog (k)$ 倍，此为 $k,d ≥ 2$ 下的最优代价上界。
发现论文，激发创造
  • 可解释聚类的近乎紧密且无感知算法

    提出了一个算法，用于在 $k$-medians 目标和 $k$-means 目标下输出可解释的聚类，与最佳聚类最多相差 $O (\log^2 k)$ 和 $O (k\log^2 k)$ 的因子，算法时间为 $O (dk\log^2 k)$ 。

    Jun, 2021

  • 可解释聚类中深度减少的不可能性

    本文研究可解释 K-means 和 K-median 聚类问题，证明了在欧几里得平面上，解释深度降低会导致聚类成本的无界损失，并将其扩展到 K-center 目标。

    May, 2023

  • 可解释的 k-Medians 和 k-Means 的近似最优算法

    研究在可解释的 k - 中位数和 k - 均值问题中，提出了一种新的算法并分析了其竞争性和下界。

    Jul, 2021

  • 关于可解释性的代价在某些聚类问题中的研究

    通过测试，我们发现，在进行 k-means 分类问题时，通过利用决策树可增强算法可解释性，提高性能表现。

    Jan, 2021

  • 可解释的 K 均值和 K 中值聚类

    本文提出了一种使用决策树对数据集进行聚类的算法，并探讨了该方法对 k-means 和 k-medians 目标函数的适用性。作者证明了常见的自顶向下决策树算法可能会导致成本任意大的聚类结果，但设计了一种有效的方法使用具有 k 个叶子的树生成可解释的聚类，并对于两个中心点的情况，仅需要一个阈值切割即可实现常数近似。

    Feb, 2020

  • 可解释聚类的近似最紧算法

    本文研究了一个最近提出的可解释聚类框架，专注于 k-medians 和 k-means 问题，并提供了近似算法和上下界。

    Jul, 2021

  • ExKMC: 扩展可解释的 K - 均值聚类

    我们研究了基于解释和准确性之间的平衡的 $k$-means 聚类算法，设计了一种新的解释性 $k$-means 聚类算法 ExKMC，用于有效地将数据集划分为 $k'$ 个叶子节点，并以 $k$ 个簇之一的形式对叶子节点进行标记。经实验验证，ExKMC 的聚类效果优于标准的决策树方法和其他解释性聚类算法。

    Jun, 2020

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

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

    Oct, 2023

  • 通过决策树解读核聚类

    探索可解释的核聚类算法，提出构建决策树来近似核 k-means 引发的分区的算法，并展示了适当选择特征如何在不损失可解释模型的近似保证的情况下保持可解释性。

    Feb, 2024

  • 基于分层分离树的可扩展差分隐私聚类

    通过利用树嵌入和标准的降维技术，我们提出了一种高效易实现的算法，能够解决 $k$- 中位数和 $k$- 均值的私有聚类问题，具有很好的时间和空间复杂度，适用于大规模分布式计算环境，并有可观的隐私保障.

    Jun, 2022