Selección de características de árbol de decisión de longitud fija para minimizar el rendimiento promedio de búsqueda

Tengo una consulta compleja $Q$ utilizada para buscar un conjunto de datos $S$ para encontrar $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$ . Cada consulta toma un tiempo promedio por lo que el tiempo total en la búsqueda lineal es. Puedo dividir una consulta en subconsultas más simples q_i y encontrar y donde . Cada subconsulta es mucho más rápida de calcular, por lo que en general es más rápido encontrar$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}$ y luego use para encontrar .$Q$$H_\text{exact}$

Cada tiene muchas . La superposición entre diferentes es alta. Estoy buscando una manera de determinar un conjunto de preguntas fijas tipo árbol de decisión$Q$$q_i$$Q$$q_j$ que minimice el tiempo promedio para encontrar un H_exact, basado en una gran muestra de consultas de búsqueda.

Para hacerlo más concreto, suponga que el conjunto de datos contiene los 7 mil millones de personas en el mundo, y las consultas complejas son cosas como "la mujer que vive en la casa roja en la esquina de 5th y Lexington en una ciudad que comienza con B".

La solución obvia es verificar a cada persona en el mundo y ver quién coincide con la consulta. Puede haber más de una de esas personas. Este método lleva mucho tiempo.

Podría precalcular esta consulta exactamente, en cuyo caso sería muy rápido ... pero solo para esta pregunta. Sin embargo, sé que otras consultas son para la mujer que vive en la casa azul en la misma esquina, el hombre que vive en la misma esquina, la misma pregunta pero en una ciudad que comienza con C, o algo totalmente diferente, como 'el rey de Suecia.

En cambio, puedo dividir la compleja pregunta en un conjunto de conjuntos más fáciles pero más generales. Por ejemplo, todas las preguntas anteriores tienen una consulta basada en el rol de género, por lo que puedo calcular previamente el conjunto de todas las personas en el mundo que se consideran una 'mujer'. Esta subconsulta no requiere esencialmente tiempo, por lo que el tiempo de búsqueda general disminuye aproximadamente 1/2. (Suponiendo que por otro conocimiento sabemos que un "rey" sueco no puede ser una "mujer". Hatshepsut era una mujer egipcia que era rey).

Sin embargo, a veces hay consultas que no están basadas en el género, como "la persona que vive en la 8va calle en una casa roja en una ciudad que comienza con A". Puedo ver que la subconsulta "vive en una casa roja" es común, y precalculo una lista de todas aquellas personas que viven en una casa roja.

Esto me da un árbol de decisión. En el caso habitual, cada rama del árbol de decisión contiene diferentes preguntas, y los métodos para seleccionar los términos óptimos para el árbol de decisión son bien conocidos. Sin embargo, estoy construyendo sobre un sistema existente que requiere que todas las ramas deben hacer las mismas preguntas.

Aquí hay un ejemplo de un posible conjunto de decisiones finales: la pregunta 1 es '¿es la persona una mujer?', La pregunta 2 es '¿vive la persona en una casa roja?', La pregunta 3 es '¿vive la persona en una ciudad que comienza con A o ¿la persona vive en una ciudad que comienza con B? ', Y la pregunta 4 es' ¿vive la persona en una calle numerada? '.

Cuando entra una consulta , veo si es q coincido con alguna de las preguntas precalculadas q j que he determinado. Si es así, obtengo la intersección de esas respuestas y hago la pregunta Q en ese subconjunto de intersección. Por ejemplo, si la pregunta es "las personas que viven en una casa roja en una isla", entonces descubren que "la persona vive en una casa roja" ya está calculada previamente, por lo que solo es cuestión de encontrar el subconjunto de aquellos que también viven en una isla.$Q$$q_i$$q_j$$Q$

Puedo conseguir un modelo de costos examinado un conjunto de muchos y comprobar para ver el tamaño de la correspondiente H aprox . Quiero minimizar el tamaño promedio de H aprox .$Q$$H_\text{approx}$$H_\text{approx}$

$q_j$$q_j$

¿Qué investigación existente debería buscar para obtener ideas?

La solución que encontré (hice la pregunta) es utilizar una codificación superpuesta y, más específicamente, una variante de Zatocoding que tenga mejor soporte para descriptores jerárquicos.

El método que utilicé proviene de 'Un diseño eficiente para la búsqueda de estructuras químicas. I. The Screens ', Alfred Feldman y Louis Hodes, J. Chem. Inf. Comput Sci., 1975, 15 (3), págs. 147-152.

$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$

$s_i=-log_2(f_i)$$s_i=-log_2(f_i/g_i)$$g_i$

Todavía hay un problema sobre cómo encontrar los descriptores correctos, pero eso será específico del dominio.