Oct, 2023

公平且多样化的数据摘要核心集

PDF
TL;DR我们研究了在公平性 / 分区约束条件下多样性最大化任务中的一种核心集构建算法。给定一个被划分为 m 组的度量空间中的点集 P，以及给定的每组 i 中的 ki 个点，该问题的目标是从每个组中选择 ki 个点，使得选择的 k 个点的整体多样性最大化。我们考虑了两种自然的多样性度量方法：对点对距离求和和对最近邻距离求和，并展示了针对这些度量方法的改进的核心集构建算法。具体而言，我们展示了第一种相对于点对距离求和而言大小与数据集大小和纵横比无关的核心集，同时我们还展示了第一个相对于最近邻距离求和而言的核心集。最后，我们进行了几个实验证明了我们的核心集方法的有效性。特别是，我们将约束的多样性最大化应用于一个考虑到消息的新旧的定时消息集的总结。具体而言，总结应该包含比较近期的消息而不是较早的消息。这是在一个最大的通信平台中的一个真实任务，每天活跃用户的体验都会受到影响。通过利用我们的核心集方法，我们实现了 100 倍的加速，只损失了少数百分比的多样性。此外，我们的方法还可以改进流式设置中算法的空间利用率。
core-set construction algorithmsdiversity maximizationfairness/partition constraintsum-of-pairwise distancessum-of-nearest-neighbor distances
发现论文，激发创造
  • 具有公平约束的聚类核心集

    本文提出了一种公平的聚类方法，可以对数据点进行聚类而确保每个聚类中各类别比例的公平分配。该方法采用了基于新构建的核心集的方法，并使用该方法高效处理类别复杂、性别等多个敏感类型的数据，并在成人 (Adult)、银行 (Bank)、糖尿病 (Diabetes) 和运动员 (Athlete) 数据集上得到了实证结果。

    Jun, 2019

  • 度量空间中有界倍增维度的多样性最大化的 MapReduce 和 Streaming 算法

    该论文在关于点集的度量空间问题中，提出了一种基于流算法和 MapReduce 模型的高效多样性最大化算法，该算法通过核心集合和 α- 近似比的计算，能够在处理大量数据集时获得优秀的近似度。

    May, 2016

  • 多数据集流上用于多样性近似的可组合核心集

    介绍了一种用于构建可组合核心集合的核心集合构建算法，用于总结用于活动学习环境的流数据，结合技术如 CRAIG 和启发式方法以增强构建速度，可以在大数据传感器数据量较大时实时训练模型。通过考虑外推数据进行这种蛮力算法的运行时间性能经验分析，并通过平均经验回归进行效率分析，提出了关键结果和改进方向以便进一步研究该主题。

    Aug, 2023

  • 数据汇总的公平 k-Center 聚类

    本文研究数据汇总的公平性约束下的原型选择问题，提出了一种运行时间线性的近似算法，该算法对于少数人群，只会带来常数因子的开销。

    Jan, 2019

  • 公正和多样化的基于 DPP 的数据概述

    通过加入公平性约束条件，该文章提出了一种基于确定性多元分布的方法，并且使用了快速的抽样算法以产出多样化且公平的数据子集。

    Feb, 2018

  • 应用于网络图的向量摘要的核心集

    提供一种确定性数据汇总的算法来表示用户的好友群体和活动摘要，这可以被用于从 GPS 轨迹或信息交换来识别会议或好友组，并可以标识邻接矩阵中的重要节点。

    Jun, 2017

  • 公平聚类中用于度量空间和欧几里得空间的核心集及其应用

    本文针对公平聚类提出了一种基于随机抽样的核心集构建法，使得可以在一般度量空间中获得公平聚类的第一个核心集，以及在欧氏空间中实现核心集大小不呈指数级增长的公平聚类。此外，还推导了针对受限聚类问题的核心集构造方案，并通过此方案提出了一些新的近似算法。

    Jul, 2020

  • 分布式子模最大化的随机组合核心集

    在此论文中，我们研究和改善了基于随机聚类的可组合核心集的构建方法，并将其应用于在计算复杂度受限制的分布式和流式处理设置下的覆盖和子模极大化问题，并采用改进的分析技术和新算法提出了首个能够在恒定轮数下打败因子 1/2 的 MapReduce 算法。

    Jun, 2015

  • 公平 k 均值聚类的公平核心集和流算法

    本文研究公平聚类问题，提出一种利用核心集合来显著减小输入数据规模的算法，证明了核心集合的可组合性，提出了 Lloyd 算法的变体，并将其扩展为公平 k-means ++ 聚类算法，实现了这些算法并提供了经验证据，表明我们的方法得以规模化运行。

    Dec, 2018

  • GIST：贪婪独立集合阈值用于多样数据摘要

    我们提出了一种新颖的子集选择任务，称为最小距离多样化数据汇总（MDDS），它在机器学习中有广泛的应用，例如数据采样和特征选择。我们介绍了 GIST 算法，它通过将一系列最大独立集问题近似为双准则贪婪算法来实现 MDDS 的 2/3 近似保证。我们还证明了对于任意 ε>0，存在一个补充的（2/3+ε）- 近似难度。最后，我们通过实证研究证明了 GIST 在合成数据上优于现有方法，并且对于一个真实的图像分类实验，GIST 用于 ImageNet 的单次子集选择也表现出色。

    May, 2024