Генерация дерева отпечатков пальцев

Question

В мире есть группа людей [скажем, 1874 из них], представляющих разные компании [скажем, 236 из них].Моя задача - лучше определить, в какой компании работает каждый человек.Хитрость в том, что я не могу просто спросить человека «Где ты работаешь» и получить ответ, но у меня есть анкета с несколькими вопросами [скажем, 290 вопросов] и точными ответами, которых я должен ожидать от сотрудниковкаждой компании.У некоторых компаний могут быть одинаковые ответы, поэтому, в конце концов, даже если я не смогу точно определить, в какой компании работает человек, я смогу сузить ее и сказать, что он / она должен работать в одной из этих компаний.

Используя многозначные карты и некоторые другие структуры данных, я дошел до определения всех компаний, которые я могу идентифицировать с помощью одного вопроса [запроса].Используя эти запросы для представления корня древовидной структуры данных, мне нужно построить остальную часть дерева, используя другие запросы / вопросы в качестве ветвей для идентификации остальных.

Любой совет / помощь / предложение?

Answer 1

Построить дерево рекурсивно, начиная с корня. На каждом этапе у вас будет активный набор анкет, который изначально будет представлять собой все анкеты. Из активных вопросников выберите вопрос, в котором примерно столько ответов да, сколько ответов нет. Сделайте узел дерева для этого вопроса. Создайте поддерево «да» (рекурсивно), используя подгруппы вопросников, которые ответили «да» на вопрос, выбранный на этом узле. Также создайте поддерево без использования поднабора анкет, ответивших «нет» на выбранный вами вопрос.

Простой пример:

Предположим, мы пытаемся угадать животное, и у нас есть анкеты от медведя, зебры, лосося и крокодила.

Мы смотрим на вопросники и видим, что около половины из них сказали «да» «Вы млекопитающее?», Поэтому мы сделаем это корнем дерева.

Теперь мы возьмем только вопросники, на которые ответили «да» на этот вопрос. В нашем примере это медведь и зебра. Мы выбираем вопрос «У вас есть полоски?», Так как примерно половина из них говорит «да», а половина - «нет». Поскольку для каждого из этих ответов есть только одна анкета, вы создаете листовые узлы, которые угадывают зебру и несут соответственно.

Теперь вернемся к корневому узлу и повторим процесс для ветви «нет». То есть мы смотрим на вопросники для лосося и крокодила и выбираем вопрос, который отличает этот набор на отдельные группы. "Ты любишь улыбаться?" отвечает всем требованиям.

Окончательное дерево выглядит так:

Ask: "Are you a mammal?"
 |
 +- yes -> Ask: "Do you have stripes?"
 |          |
 |          +- yes -> Guess: Zebra
 |          |
 |          +- no --> Guess: Bear
 |
 +- no --> Ask: "Do you like to smile?"
            |
            +- yes -> Guess: Crocodile
            |
            +- no --> Guess: Salmon

Answer 2

Исходя из вашего ответа в комментариях, я чувствую, что вы также можете просто иметь каждый уровень своего дерева, представляющий вопрос, и ветви / подузлы узлов на этом уровне, представляющие ответы.Технически это будет три, как упомянуто btilly.

Более эффективное (хотя и не обязательно пространственное) решение может включать использование хеш-таблицы и хеш-функции, которая воздействует на выбор ответа для создания своего хэша., но я думаю, что trie - это лучший путь, учитывая ваши требования и все равно.

О, верно: в зависимости от того, как выложены варианты ответов, возможно, у вас может быть серияответов по конкретным веткам, в которых нет нескольких ветвей / деревьев на нескольких уровнях;в таком случае вы могли бы потенциально свести эти отдельные разделы ветвей в отдельные узлы.http://en.wikipedia.org/wiki/Trie#Compressing_tries также может дать несколько советов.

Исходя из вашего ответа на мой первоначальный ответ, вот моя идея:

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

Когда вы впервые проверяете ответ на конкретный вопрос, и с этим выбором ответа связано несколько компаний, сделайте временныйкопия данных в хэш-таблице этого первого ответа в виде связанного списка или чего-то еще.По мере получения ответов на другие вопросы проверяйте элементы списка по хеш-таблице каждого нового ответа и удаляйте компании, которых нет в хеш-таблице каждого нового ответа, из списка.Повторяйте процесс вопросов и ответов, пока 1) в списке не останется только одна компания, 2) в списке не останется ни одной компании, или 3) вы задали все вопросы.

Если 1), тоявляется работодателем, отвечающим на вопросы.
Если 2), сотрудник не нанят ни в одной из компаний для проверки, и / или где-то есть ошибка.
Если 3), компании, оставшиеся в связанномсписок возможных компаний, в которых работает отвечающий на вопросы.

Вероятно, существует более эффективный способ сделать это, так как моя реализация потребовала бы минимум 580 хеш-таблиц (по одной на каждый ответ, с минимумом2 ответа на вопрос), но сейчас я не могу придумать ничего.

Answer 3

Построение Экспертной системы с использованием Пролог является одним из возможных решений. Вы рассматривали этот вариант?

Таким образом, вы даже можете добавить некоторые возможности обработки естественного языка , облегчающие взаимодействие с пользователями.