Алгоритм TDIDT представляет собой классический вариант top-down индукции и основан на методе «разделяй и властвуй». Результатом работы алгоритма, т. е. описанием пространства примеров, является дерево решений. Дерево решений разделяет области пространства примеров на подобласти таким образом, что каждая вершина дерева соответствует при этом подобласти пространства примеров. Корень дерева соответствует всему пространству примеров. Его потомки делят пространство примеров на непересекающиеся области. Этот процесс применяется к каждому листу дерева. Каждый такой лист (т. е. вершина дерева) помечается меткой, которая обозначает множество примеров, принадлежащих соответствующей области. Каждая внутренняя вершина класса (т. е. вершина, не обозначающая ничего, кроме самой себя) соответствует какому-либо атрибуту.
TDIDT обычно включает два шага — построение новых ветвей и редукцию, т. е. удаление ветвей. На первом шаге дерево решений строится так, чтобы в максимальной степени соответствовать обучающей выборке. На втором шаге этот «изоморфизм» превращается в «гомоморфизм», так как редукция дерева приводит к уменьшению числа его вершин.
Алгоритм построения новых ветвей. Пусть S — полное множество примеров (экземпляров) из некоторого класса эквивалентности. Далее операторы о из множества О будем называть элементами (примеров).
Шаг 1. Выполнить поиск «лучшего» элемента о^.
Шаг 2. Произвести расщепление множества S на подмножества S, So, • •., Snj так чтобы все примеры из подмножества Sj имели одинаковые элементы Oj.
Шаг 3. Для каждого множества Sj, если все примеры в Sj принадлежат одному и тому же классу (имеющему ту же метку класса), создать лист дерева решений и пометить меткой этого класса. Иначе перейти к 1, положив S = Sj. Алгоритм заканчивает работу, когда все подмножества помечены, либо отсутствуют элементы, разделяющие непомеченные множества.