Aug, 2023

数据易于 (对于 K-Means)

PDF
TL;DR该论文研究了 $k$-means 算法的能力，正确地恢复互相分离的簇群。基于常见的簇群定义，考虑了簇内同质性和簇间多样性的要求，并找到了一种特殊情况的互相分离簇群，使得 $k$-means 的代价函数全局最小值与互相分离性一致。通过实验发现各种 $k$-means 品牌实际上无法发现互相分离的簇群，因此提出了一种新的算法，通过重复子抽样选择种子的方式，对 $k$-means++ 进行变体改进，并在任务中胜过 $k$-means 系列中的其他四种算法。
clustersk-means algorithmwell-separatednesscost functionnew algorithm
发现论文，激发创造
  • 易实例的不同 ially-Private 聚类

    本文研究的是隐私保护聚类算法，提出了一个依据难易程度来组合本来不带保护性质的聚类算法和隐私保护结果的框架，并在高斯混合数据和 $k$-means 算法中实现了样本复杂度较小的聚类效果进行了实证评估。

    Dec, 2021

  • 可解释聚类与可区分性标准

    基于全局的可区分性准则，本文提出了用于验证聚类分析结果以及确定数据集中聚类数量的方法，并将该准则与常用的聚类方法进行了整合，包括层次聚类、k-means 和有限混合模型。通过模拟研究和实际数据应用，我们展示了这些新算法的结果。

    Apr, 2024

  • 广泛间隔与聚类公理

    这篇研究论文介绍了对 k-means 算法的扩展，以符合 Kleinberg 的公理系统，并提出了新的聚类性质，进一步解释了算法的特点和适用性。

    Aug, 2023

  • 欧几里得 k - 均值问题的近似难度

    本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。

    Feb, 2015

  • 多样性感知聚类：计算复杂度和近似算法

    在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $k$-median、$k$-means 或 $k$-supplier。我们提出了参数化逼近算法，逼近比例分别为 $1+ rac {2}{e}$、$1+ rac {8}{e}$ 和 $3$，用于多样性感知 $k$-median、多样性感知 $k$-means 和多样性感知 $k$-supplier。这些逼近比例在假设 Gap-ETH 和 FPT $ eq$ W [2] 的情况下是紧密的。对于公平 $k$-median 和公平 $k$-means 与不相交设施组，我们分别提出了参数化逼近算法，逼近比例为 $1+ rac {2}{e}$ 和 $1+ rac {8}{e}$。对于公平 $k$-supplier 与不相交设施组，我们提出了一个多项式时间逼近算法，其因子为 $3$，改进了先前已知的逼近比例因子为 $5$。

    Jan, 2024

  • 增强 k-means 的聚类效果

    本技术报告介绍了一种名为增强的 k-means 的算法，该算法是 k-means 和逻辑回归的混合体，通过逻辑回归预测当前聚类标签并使用聚类归属概率来控制后续集群均值的重新估计，能有效提高聚类准确性。该算法在 Python 环境下实现。

    May, 2017

  • 从大到小的数据集：聚类算法选择的尺寸泛化

    在半监督环境中，通过引入聚类算法准确性的大小泛化概念，我们可以通过对较小的实例集进行评估，并保证在原始大型实例上具有最好准确性的算法也在小实例上具有最好准确性。

    Feb, 2024

  • 从流形学习的角度重新思考 k-means

    该论文提出了一种基于流形学习和张量正则化的聚类算法，不同于传统的基于 k-means 的方法，该算法通过构建距离矩阵来直接检测数据簇，同时应用于多视图数据中，证明了其优越性能。

    May, 2023

  • 基于聚类敏感性采样的数据高效学习：基础模型与扩展

    我们研究数据选择问题，将利用 $k$-means 聚类和敏感性抽样方法，基于模型损失的嵌入表示，可选择一组典型样本，其平均损失与整个数据集的平均损失相对应，具有可证明的性质，并且在微调基础模型上表现优于最先进的方法，同时展示了它如何应用于线性回归，提供了一个更简单且可扩展性更强的抽样策略。

    Feb, 2024

  • 可微分的深度聚类 + 聚类大小限制

    通过将 $k$-means 聚类算法重写为最优传输任务，并加入熵正则化，我们提出了一种全新的方法，其中嵌入是由深度神经网络执行的，表明与现有的基于软 $k$-means 的最新方法相比，我们的最优传输方法提供更好的无监督准确度，不需要预训练阶段。

    Oct, 2019