Summarizing user-item matrix by group utility maximization
A user-item utility matrix represents the utility (or preference) associated with each (user, item) pair, such as citation counts, rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summari...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2023
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/166437 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
Summary: | A user-item utility matrix represents the utility (or preference) associated with each (user, item) pair, such as citation counts, rating/vote on items or locations, and clicks on items. A high utility value indicates a strong association of the pair. In this work, we consider the problem of summarizing strong association for a large user-item matrix using a small summary size. Traditional techniques
fail to distinguish user groups associated with different items (such as top-$l$ item selection) or fail to focus on high utility (such as similarity based subspace clustering and biclustering). We formulate a new problem, called Group Utility Maximization, to summarize the entire user population through $k$ user groups and $l$ items for each group; the goal is to maximize the total utility of selected items over all groups collectively. We show this problem is NP-hard even for $l=1$. We present
two algorithms. One greedily finds the next group, called Greedy algorithm, and the other iteratively refines existing $k$ groups, called $k$-max algorithm. Greedy algorithm provides the $(1-\frac{1}{e})$ approximation guarantee for a nonnegative utility matrix, whereas $k$-max algorithm is more efficient for large datasets. We evaluate these algorithms on real-life datasets. |
---|