Cette question concerne le regroupement/regroupement de documents similaires dans la recherche d'information.grouper des documents similaires
J'ai un ensemble de documents, D1, D2, .. Dn. Pour chaque document, Di, j'ai aussi un ensemble de mots-clés, Di_k1, Di_k2, ..., Di_km. La similarité entre deux documents, Di et Dj est donnée par une fonction qui implique les mots-clés associés, c'est-à-dire la similarité (Di, Dj) = f (Di_K, Dj_K).
Maintenant, je veux placer chacun de ces documents dans un ensemble de groupes/clusters de sorte que chaque cluster contienne un type de document similaire pour une valeur seuil donnée de similarité entre les éléments présents dans un cluster.
Un moyen facile est de regarder chaque paire de pages possible que je veux évidemment éviter parce que le nombre de documents que j'ai est assez grand, en millions. Je parcourais le livre Introduction to Information Retrieval, mais je ne trouve aucun algorithme évolutif mentionné.
Ma question est de savoir quel type d'algorithme peut m'aider à regrouper les documents efficacement? Je suis particulièrement intéressé par la complexité de calcul de l'algorithme.
Merci d'avance pour les pointeurs.
s'il vous plaît préciser exactement ce que vous recherchez. trouver des sous-ensembles optimaux est NP Hard, c'est ce que vous cherchez? – amit
Oui. Je sais que c'est dur et c'est pourquoi je suis à la recherche d'une solution algorithmique efficace qui soit meilleure que l'implémentation la plus simple mais la plus lente possible. – user429113
puisqu'il est NP Hard, il n'y a pas de solution polynomique connue pour ce problème, vous devrez parcourir toutes les solutions possibles et choisir l'optimum - ce sera O (2^n) où n est le nombre de documents. il y a quelques algorithmes polynomiques pour trouver une approximation, mais ce ne sont que des heuristiques, et peuvent échouer. – amit