Sélection de fonctionnalités de type arbre de décision de longueur fixe pour minimiser les performances de recherche moyennes

J'ai une requête complexe utilisée pour rechercher un ensemble de données pour trouver . Chaque requête prend un temps moyen donc le temps global dans la recherche linéaire est. Je peux décomposer une requête en sous-requêtes plus simples q_i et trouver H_ \ text {approx} = \ {s \ in S \ mid \ forall q_j (s) \ text {is True} \} et où H_ \ text {exact } \ subseteq H_ \ text {environ} . Chaque sous-requête q_i est beaucoup plus rapide à calculer, donc dans l'ensemble, il est plus rapide de trouver H_ \ text {approx} puis d'utiliser Q pour trouver H_ \ text {exact} .S H exact = { s ∈ S ∣ où  Q ( s )  est Vrai } t t ⋅ | S | H environ = { s ∈ S ∣ ∀ q j ( s ) est Vrai } H exact ⊆ H environ q i H environ Q H $Q$$S$$H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$$t$$t\cdot |S|$$H_\text{approx} = \{s\in S \mid \forall q_j(s) \text {is True}\}$$H_\text{exact}\subseteq H_\text{approx}$$q_i$$H_\text{approx}$$Q$$H_\text{exact}$

Chaque $Q$ a plusieurs $q_i$ . Le chevauchement entre différents $Q$ est élevé. Je cherche un moyen de déterminer un ensemble de questions fixes de type arbre de décision $q_j$ qui minimise le temps moyen pour trouver un H_exact, sur la base d'un large échantillon de requêtes de recherche.

Pour rendre cela plus concret, supposons que l'ensemble de données contienne les 7 milliards de personnes dans le monde, et les requêtes complexes sont des choses comme "la femme qui vit dans la maison rouge au coin du 5e et Lexington dans une ville commençant par B."

La solution évidente est de vérifier chaque personne dans le monde et de voir qui correspond à la requête. Il peut y avoir plusieurs personnes. Cette méthode prend beaucoup de temps.

Je pourrais pré-calculer cette requête exactement, auquel cas ce serait très rapide .. mais uniquement pour cette question. Cependant, je sais que d'autres questions concernent la femme qui vit sur la maison bleue dans le même coin, l'homme qui vit dans le même coin, la même question mais dans une ville commençant par C, ou quelque chose de totalement différent, comme `` le roi de Suède. »

Au lieu de cela, je peux décomposer la question complexe en un ensemble d'ensembles plus faciles mais plus généraux. Par exemple, toutes les questions ci-dessus ont une requête basée sur le rôle du genre, donc je peux précalculer l'ensemble de toutes les personnes dans le monde qui se considèrent comme une «femme». Cette sous-requête ne prend essentiellement pas de temps, donc le temps de recherche global diminue d'environ 1/2. (En supposant que par d'autres connaissances, nous savons qu'un «roi» suédois ne peut pas être une «femme». Hatchepsout était une femme égyptienne qui était roi.)

Cependant, il y a parfois des requêtes qui ne sont pas basées sur le sexe, comme "la personne qui vit sur la 8ème rue dans une maison rouge dans une ville commençant par A." Je peux voir que la sous-requête "vit dans une maison rouge" est courante et pré-calculer une liste de toutes les personnes qui vivent dans une maison rouge.

Cela me donne un arbre de décision. Dans le cas habituel, chaque branche de l'arbre de décision contient des questions différentes, et les méthodes pour sélectionner les termes optimaux pour l'arbre de décision sont bien connues. Cependant, je m'appuie sur un système existant qui exige que toutes les succursales doivent poser les mêmes questions.

Voici un exemple de décision finale possible: la question 1 est «la personne est-elle une femme?», La question 2 est «la personne vit-elle dans une maison rouge?», La question 3 est «la personne vit-elle dans une ville commençant par A ou la personne vit-elle dans une ville commençant par B? », Et la question 4 est« la personne vit-elle dans une rue numérotée? ».

Lorsqu'une requête entre, je vois si son correspond à l'une des questions pré-calculées que j'ai déterminées. Si oui, alors j'obtiens l'intersection de ces réponses et pose la question sur ce sous-ensemble d'intersection. Par exemple, si la question est "les gens qui vivent dans une maison rouge sur une île", alors constatez que "la personne vit dans une maison rouge" est déjà précalculée, il suffit donc de trouver le sous-ensemble de ceux qui vivent également sur une île.q i q j$Q$$q_i$$q_j$$Q$

Je peux obtenir un modèle de coût en regardant un ensemble de nombreux et vérifier la taille du . Je souhaite minimiser la taille moyenne de .$Q$$H_\text{approx}$$H_\text{approx}$

La question est, comment puis-je optimiser la sélection de possibles pour faire cet arbre de décision fixe? J'ai essayé un GA mais il a été lent à converger. Probablement parce que mon espace de fonctionnalités a quelques millions de possibles . J'ai trouvé une méthode gourmande, mais je ne suis pas satisfait du résultat. C'est aussi très lent, et je pense que j'optimise la mauvaise chose.q $q_j$$q_j$

Quelles recherches existantes dois-je rechercher pour des idées?

La solution que j'ai trouvée (j'ai posé la question) est d'utiliser un codage superposé, et plus précisément, une variante du zatocodage qui prend mieux en charge les descripteurs hiérarchiques.

La méthode que j'ai utilisée provient de «Une conception efficace pour la recherche de structures chimiques. I. The Screens ', Alfred Feldman et Louis Hodes, J. Chem. Inf. Comput. Sci., 1975, 15 (3), pp 147-152.

La solution non hiérarchique consiste à examiner la densité de l'information. Chaque descripteur se verra attribuer bits où est la fréquence dans l'ensemble de données ( f_i <= 1.0). Calculez le nombre total de bits (la taille de l'arbre de décision) en utilisant où est le facteur de compression Mooers 0,69 (à partir de ). Une fois que vous avez déterminé le nombre total de bits à utiliser, sélectionnez bits au hasard pour chaque descripteur pour l'attribution des bits.f i 0 < D D = ∑ ( s i f i ) / M c M c l o g e 2 s $s_i=-log_2(f_i)$$f_i$$0<$$D$$D=\sum(s_i f_i)/M_c$$M_c$$log_e 2$$s_i$

La solution hiérarchique de Feldman et Hodes remplace pour les descripteurs qui sont un sous-ensemble d'autres descripteurs. Dans ce cas, utilisez où est la fréquence du parent le moins fréquent. De plus, lors de l'affectation de bits, ne sélectionnez pas les bits qui sont également utilisés par l'affectation de bits du parent.s i = - l o g 2 ( f i / g i ) g $s_i=-log_2(f_i)$$s_i=-log_2(f_i/g_i)$$g_i$

Il y a toujours un problème pour trouver les bons descripteurs, mais ce sera spécifique au domaine.