Say we have 100,000 documents tagged with 10,000 different tags (Max 5 tag per document). We wish to limit allowed tags to a list of 500 tags.

How to select 500 tags in order to cover the largest set of documents ?

Firstly, I chose the 500 most frequent tags. If we keep only these 500 tags, 70% of documents keep at least 1 tag.

I'm looking for a better method to pick the 500 most pertinents tags.

example : enter image description here

my best set of 5 tags to cover all documents is [italian, german, french, chineese, japan].

it is not [italian, spanish, indian, finnish, english] although these are the most frequent tags.

I tried a Single Value Decomposition on the matrix : [documentID, set of tags]. but after that ? is it a good idea ? how to get 500 tags from the SVD results ?

| improve this question | | | | |
  • $\begingroup$ Unless there are duplicates of tags or documents the most frequent tags should be the same as the tags that cover the largest set of documents. $\endgroup$ – Simon Larsson Nov 5 '19 at 12:20
  • $\begingroup$ Thanks Simon Larrson. I am not looking for the tags that cover the largest set of documents. I am looking for the best set of tags to cover the largest set of documents . I edited my question and added an example. $\endgroup$ – Brigitte Charpent Nov 5 '19 at 14:15
  • $\begingroup$ Ok, so it would be feasible to compound tags? Like having italian/spanish/indian/finnish/english as a single tag in your example? $\endgroup$ – Simon Larsson Nov 5 '19 at 14:35

That is a set cover problem. The documents (universe) are being covered by a set of tags (elements).

In the case of maximizing the number of documents with a limited number of tags, a greedy approach can be taken. Find the single tag that covers the most documents. Then find the next tag that covers the most documents not already covered. Continue the process until the number of tags has been reached.

| improve this answer | | | | |
  • $\begingroup$ Thanks Brian . quite simple once you have been told :) $\endgroup$ – Brigitte Charpent Nov 5 '19 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.