RRR: Rank-Regret Representative
RRR: Rank-Regret Representative
复制标题
DOI：
10.1145/3299869.3300080
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Abolfazl Asudeh;Azade Nazi;Nan Zhang;Gautam Das;H. V. Jagadish
中科院分区：
文献类型：
--
作者：
Abolfazl Asudeh;Azade Nazi;Nan Zhang;Gautam Das;H. V. Jagadish
在数据浏览中选择数据集中的最佳项是一项常见的任务。然而，“最佳”的概念取决于观察者的眼睛：不同的用户可能会认为不同的属性更重要，从而得出不同的排名。然而，人们可以去掉“占主导地位的”条目，创建一个“有代表性的”数据子集，包括其中的“最佳条目”。帕累托最优代表保证包含每个可能排名的最佳项目，但它可以是很大一部分数据。如果我们放松要求，为每个用户提供最好的商品，而只限制用户的“遗憾”，那么就可以找到一个小得多的代表。现有的工作将后悔定义为得分的损失，对于任何选择的排名函数，通过限制对代表而不是整个数据集的考虑。然而，分数往往不是一个有意义的数字，用户可能不了解其绝对值。有时分数的小范围可能包括数据集的大部分。相比之下，用户确实理解排名排序的概念。因此，我们考虑项目在排序列表中的位置来定义后悔，并提出将排名-后悔代表作为包含任何可能的排序函数的前k个中的至少一个的数据的最小子集。这个问题是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 to include 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 data set, 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 data set. In contrast, users do understand the notion of rank ordering. Therefore, we consider the position of the items in the ranked list for defining the regret and propose the \em rank-regret representative as the minimal subset of the data containing at least one of the top-k of any possible ranking function. This problem is NP-complete. We use a geometric interpretation of items to bound their ranks on ranges of functions and to utilize combinatorial geometry notions for developing effective and efficient approximation algorithms for the problem. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.