Выбор функции в виде дерева решений фиксированной длины для минимизации средней производительности поиска

У меня сложный запрос используемый для поиска в наборе данных чтобы найти . Каждый запрос занимает в среднем время поэтому общее время в линейном поиске равно, Я могу разбить запрос на более простые подзапросы q_i и найти и где . Каждый подзапрос вычисляется намного быстрее, поэтому в целом он быстрее находит И затем использует для поиска .S H точное = { s ∈ S ∣, где  Q ( s )  истинно } t t ⋅ | S | Н ок = { s ∈ S | ∀ д J ( ы ) верно } Н точное ⊆ Н около д я H около Q Н $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}$

Каждый имеет много . Перекрытие между различными является высоким. Я ищу способ определения набора фиксированных вопросов в дерева решений которые минимизируют среднее время нахождения H_exact, на основе большой выборки поисковых запросов.q i Q q $Q$$q_i$$Q$$q_j$

Чтобы сделать это более конкретным, предположим, что набор данных содержит 7 миллиардов человек в мире, а сложные запросы - это такие вещи, как «женщина, которая живет в красном доме на углу 5-го дома, и Лексингтон в городе, начинающемся с B.»

Очевидное решение - проверить каждого человека в мире и посмотреть, кто соответствует запросу. Таких людей может быть несколько. Этот метод занимает много времени.

Я мог бы точно рассчитать этот запрос, в этом случае он будет очень быстрым ... но только для этого вопроса. Тем не менее, я знаю, что другие вопросы касаются женщины, которая живет в синем доме в том же углу, мужчины, который живет в том же углу, того же вопроса, но в городе, начинающемся с буквы С, или чего-то совершенно другого, такого как король Швеции.

Вместо этого я могу разбить сложный вопрос на набор более простых, но более общих наборов. Например, все вышеперечисленные вопросы имеют запрос на основе гендерных ролей, поэтому я могу предварительно рассчитать набор всех людей в мире, которые считают себя «женщиной». Этот подзапрос по сути не занимает много времени, поэтому общее время поиска уменьшается примерно на 1/2. (Предполагая, что из других знаний мы знаем, что шведский «король» не может быть «женщиной». Хатшепсут была египетской женщиной, которая была королем.)

Тем не менее, иногда есть вопросы, которые не основаны на гендерном вопросе, например, «человек, который живет на 8-й улице в красном доме в городе, начинающемся с А.» Я вижу, что подзапрос «живет в красном доме» является обычным делом, и предварительно вычисляю список всех тех людей, которые живут в красном доме.

Это дает мне дерево решений. В обычном случае каждая ветвь дерева решений содержит разные вопросы, и методы выбора оптимальных условий для дерева решений хорошо известны. Однако я строю существующую систему, которая требует, чтобы все ветви задавали одинаковые вопросы.

Вот пример возможного окончательного набора решений: вопрос 1 - «человек ли женщина?», Вопрос 2 - «живет ли человек в красном доме?», Вопрос 3 - «живет ли человек в городе, начиная с A или человек живет в городе, начинающемся с буквы B? », А вопрос 4« живет ли человек на пронумерованной улице? ».

Когда приходит запрос , я вижу, соответствует ли его любому из предварительно вычисленных вопросов которые я определил. Если так, то я получаю пересечение этих ответов и задаю вопрос в этом подмножестве пересечений. Например, если вопрос «люди, которые живут в красном доме на острове», то обнаружите, что «человек живет в красном доме» уже вычислен заранее, поэтому вопрос лишь в том, чтобы найти подмножество тех, кто также живет на острове.q i q j$Q$$q_i$$q_j$$Q$

Я могу получить модель стоимости, посмотрев на множество множеств и проверив, чтобы увидеть размер соответствующего . Я хочу минимизировать средний размер .H прибл. H $Q$$H_\text{approx}$$H_\text{approx}$

Вопрос в том, как оптимизировать выбор возможного чтобы сделать это фиксированное дерево решений? Я попробовал GA, но он не спешил сходиться. Вероятно, потому что у моего пространства возможностей есть несколько миллионов возможных . Я придумал жадный метод, но я не доволен результатом. Это тоже очень медленно, и я думаю, что оптимизирую не то.q $q_j$$q_j$

На какие существующие исследования мне следует обратить внимание на идеи?

Решение, которое я нашел (я задал вопрос), заключается в использовании наложенного кодирования и, более конкретно, варианта Zatocoding, который имеет лучшую поддержку иерархических дескрипторов.

Метод, который я использовал, взят из «Эффективного дизайна для поиска химической структуры. I. Экраны », Альфред Фельдман и Луи Ходс, J. Chem. Inf. Вычи. Sci., 1975, 15 (3), с. 147–152.

Неиерархическое решение состоит в том, чтобы смотреть на плотность информации. Каждому дескриптору будут назначены биты, где - частота в наборе данных ( f_i <= 1.0). Вычислить общее количество битов (размер дерева решений), используя где - коэффициент сжатия 0,69 (из ). После того, как вы определили общее количество битов для использования, выберите биты случайным образом для каждого дескриптора для назначения битов.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$

Иерархическое решение от Фельдмана и Ходса заменяет для дескрипторов, которые являются подмножеством других дескрипторов. В этом случае используйте где - частота наименее частого родителя. Кроме того, при выполнении назначения битов не выбирайте биты, которые также используются назначением битов родителя.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$

Есть еще проблема, как найти правильные дескрипторы, но это будет зависеть от предметной области.