1

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.

  • I think you need to look at the number of differences between sets as a sort of distance, so basically the number of additions or removals from one set to become the other. If you look at it this way, worst case scenario is the size of set A and the size of set B means performing A.length + B.length operations. With this heuristic, you could probably immediately guarantee that some documents can be eliminated simply by sheer size. Then if you also knew what two sets have in common, you can make this more precise still by subtracting from A.length + B.length. Food for thought. – Neil Feb 8 at 10:20
  • @Neil: unfortunately in my concrete example (real life documents) the size and amount of words among all documents is quite stable (I chose them to be). There are some documents with a similar set of words, but finding them would have o(n²) complexity. More challenging would be finding out which group of documents have similar sets of words, but the complexity by brute force is prohibitive. – julodnik Feb 8 at 12:46
  • I would suppose the brute force approach would be implemented in a dynamic programming style: From N = 1 to (total number of unique words), Exhaustively enumerate all subsets of documents (the subset consisting of any number of documents) that has exactly N unique words when combined. This way, subsets that are the "leaders" (i.e. fewer uniques among the peers) will be enumerated earlier in the search. – rwong Apr 14 at 23:57
1

"Must be"? Hardly. This sounds like one of the many, many problems in which the optimal solution depends on the exact characteristics of every single element. Essentially, you'll probably not be able to prove that some kind of locally optimal partial solution is, in fact, part of the globally optimal solution. If that is the case, the problem is almost certainly NP-complete and hence not solvable efficiently and correctly.

  • It doesn't have to be. I just wonder if there is a better heuristic than the ones I tried already. As I pointed, I don't need the best solution, but I have the feeling that "next neighbor" is far from the optimum, very far. – julodnik Feb 8 at 10:04
1

Depending on the size of the problem you might want to model it as a Mixed Integer Programming (MIP) problem. There exists a variety of open source (see glpk, cbc) or proprietary (cplex, gurobi, xpress-mp) to solve those problem.

In your case you would associate with each document a binary variable indicating if it is part of the optimal set or not. You would add a constraint stating that the sum of the variables associated to the documents have to be equal to the number of document you want as part of your optimum group. With each word you would associate a linear variable. For every combination of document and word being part of the document you would add a constraint stating that that the variable associated with the word has to be greater or equal than the variable associated with the document. Finally you would define your objective function has being the sum of all the variables associated to words.

  • Thanks for your answer! I must confess I don't quite understand it. Could you share a link to a more detailed explanation? Or even better, if you could add a small example. – julodnik Apr 16 at 9:49
  • @julodnik if you give a look at pythonhosted.org/PuLP/CaseStudies/… you will find an example of a similar problem and how it is modèles using the pulp library in Python – Renaud M. Apr 17 at 5:22

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.