On Finding Rank Regret Representatives
On Finding Rank Regret Representatives
复制标题
论寻找排名遗憾代表
DOI：
10.1145/3531054
复制
发表时间：
2022
影响因子：
1.8
通讯作者：
Zhao, Jianwen
中科院分区：
文献类型：
--
作者：
Asudeh, Abolfazl;Das, Gautam;Jagadish, H. V.;Lu, Shangqi;Nazi, Azade;Tao, Yufei;Zhang, Nan;Zhao, Jianwen
在数据浏览中选择数据集中的最佳项是一项常见的任务。然而，“最佳”的概念在于观察者的眼睛：不同的用户可能认为不同的属性更重要，因此得出不同的排名。然而，人们可以删除“主要的”项，并创建数据的“代表性”子集，包括其中的“最佳项”。帕累托最优代表保证包含每个可能排名的最佳项目，但它可以是很大一部分数据。如果我们放松对每个用户最好的商品的要求，而只是限制用户的“遗憾”，那么就会发现一个小得多的代表。现有的研究将遗憾定义为分数的损失，对于任何选择的排序函数，通过限制对代表而不是整个数据集的考虑，但是分数通常不是一个有意义的数字，用户可能不了解其绝对值。有时分数的小范围可以包括数据集的大部分。相比之下，用户确实理解排名排序的概念。因此，在定义遗憾时，我们考虑了条目在排序列表中的位置，并提出了作为包含任何可能的排序函数中的至少一个前KOF的数据的最小子集的排序-后悔表示。这个问题在二维空间中是多项式时间可解的，但在三维或更多维空间上是NP难的。我们设计了一套算法来满足不同的目的，例如是否允许放松，结果的大小，或者两者都允许，是否已知分布，理论保证或实际效率是否重要，等等。在真实数据集上的实验表明，我们可以有效地找到具有较小排名遗憾的小子集。
Selecting the best items in a dataset is a common task in data exploration. However, the concept of “best” lies in the eyes of the beholder: Different users may consider different attributes more important and, hence, arrive at different rankings. Nevertheless, one can remove “dominated” items and create a “representative” subset of the data, comprising the “best items” in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be a large portion of data. A much smaller representative can be found if we relax the requirement of including the best item for each user and instead just limit the users’ “regret.” Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full dataset, for any chosen ranking function.However, the score is often not a meaningful number, and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the dataset. In contrast, users do understand the notion of rank ordering. Therefore, we consider items’ positions in the ranked list in defining the regret and propose therank-regret representativeas the minimal subset of the data containing at least one of the top-kof any possible ranking function. This problem is polynomial time solvable in two-dimensional space but is NP-hard on three or more dimensions. We design a suite of algorithms to fulfill different purposes, such as whether relaxation is permitted onk, the result size, or both, whether a distribution is known, whether theoretical guarantees or practical efficiency is important, and so on. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.
登录
查看更多内容
DOI：
10.1016/0925-7721(92)90006-e
发表时间：
1992-11
期刊：
--
影响因子：
--
作者：
J. Matoušek
通讯作者：
J. Matoušek
影响因子：
0.8
作者：
M. Sharir;Shakhar Smorodinsky;G. Tardos
通讯作者：
G. Tardos
关于随机凸壳的预期复杂度
DOI：
--
发表时间：
2011
期刊：
arXiv.org
影响因子：
--
作者：
Sariel Har
通讯作者：
Sariel Har
通过总是包含许多点的两个点的圆
DOI：
--
发表时间：
1989
期刊：
影响因子：
--
作者：
H. Edelsbrunner;N. Hasan;R. Seidel;X. Shen
通讯作者：
X. Shen
平面 k 集和相关问题的改进界限
影响因子：
0.8
作者：
T. Dey
通讯作者：
T. Dey