I need help with a problem which I have been working for the last month.
I have a group of documents, each document has a set of unique words (if the word appears more than once in the document, I count it only once). I want to find for a particular amount of documents the optimum group which contains the least amount of different words.
For example, if I have a set of five documents, each of them containing a set of words:
d1 = [ a , b, c, d, e ] d2 = [ b , c, f ] d3 = [ c , e, g ] d4 = [ a , c, d ] d5 = [ c , d, e ]
The set of three documents with the least amount of words would be (d1,d4,d5). This group of three documents would contain only a, b, c, d and e.
So far what I have tried is the "nearest neighbor" approach. Take the document with the least amount of new words. I extended it with a recursive limited brute force: take the next n documents with the least amount of new words.
Is there any better algorithm for finding a good set? I know the optimum set can only be solved by brute force, but that is obviously not doable here.
EDIT: Why I have the impression that "nearest neighbor" is a poor solution: By extending the set of documents I sometimes get a solution which is much worse than with less documents. Theoretically, the same set of documents could always be choosen independently of how many more new documents I add.