Совершенная классификация дерева решений

Question

Представьте себе, что все известные отображения между значениями набора переменных V и набора имен тегов T (классификационные метки) были известны. Далее предположим, что общее пространство уникальных комбинаций переменных значений велико (> 100B точек), размер набора тегов относительно невелик (тысячи элементов), а число переменных очень мало (4-10).

Что такое алгоритм для построения функции классификатора, который обеспечивает идеальное отображение (соответствие априорного знания без ложных срабатываний или ложных негативов) от значений переменных меток со следующим пространством и сложность времени цели:

• Временная сложность меньше, чем O (| V | * войти | T |)
• Пространство сложности меньше, чем O (| V | ^к), к ≤ е

Или перефразировать как проблема дерева решений:

1. Как алгоритм дерева решения быть настроен, чтобы создать совершенное отображение?
2. Каким образом данные обучения могут быть представлены эффективно, чтобы гарантировать это?

Answer 1

То, что вы пытаетесь достичь, должно быть возможным с помощью любого классификатора дерева решений, который позволяет вам каким-то образом определить уровень обрезки. Идея состоит в том, чтобы сделать это вообще не обрезкой. Дерево решений, в котором вы попадете, будет иметь (потенциально) один лист на учебный экземпляр (т. Е. Очень большой), но даст вам «совершенную» точность с временем предсказания O (| V | * log | T |).

Это абсолютно не зависит от того, как данные обучения представлены (и должны быть). Единственное, что имеет значение, это то, что индуктор дерева решений может читать и обрабатывать его. Один простой способ построения такого дерева состоит в том, чтобы добавить путь для первого примера, затем объединить в один для второго и так далее.

Независимо от того, полезен ли такой классификатор на практике, это совершенно другой вопрос, конечно, в большинстве случаев этого не будет.