http://npc-news.ru/

Алгоритм TDIDT

Алгоритм TDIDT представля­ет собой классический вариант top-down индукции и основан на методе «разделяй и властвуй». Результатом работы алгоритма, т. е. описанием пространства примеров, является дерево реше­ний. Дерево решений разделяет области пространства примеров на подобласти таким образом, что каждая вершина дерева соот­ветствует при этом подобласти пространства примеров. Корень дерева соответствует всему пространству примеров. Его потом­ки делят пространство примеров на непересекающиеся области. Этот процесс применяется к каждому листу дерева. Каждый такой лист (т. е. вершина дерева) помечается меткой, которая обозначает множество примеров, принадлежащих соответствую­щей области. Каждая внутренняя вершина класса (т. е. верши­на, не обозначающая ничего, кроме самой себя) соответствует какому-либо атрибуту.

TDIDT обычно включает два шага — построение новых вет­вей и редукцию, т. е. удаление ветвей. На первом шаге дерево ре­шений строится так, чтобы в максимальной степени соответство­вать обучающей выборке. На втором шаге этот «изоморфизм» превращается в «гомоморфизм», так как редукция дерева при­водит к уменьшению числа его вершин.

Алгоритм построения новых ветвей. Пусть S — полное множество примеров (экземпляров) из некоторого класса эквивалентности. Далее операторы о из множества О будем называть элементами (примеров).

Шаг 1. Выполнить поиск «лучшего» элемента о^.

Шаг 2. Произвести расщепление множества S на подмноже­ства S\, So, • •., Snj так чтобы все примеры из подмножества Sj имели одинаковые элементы Oj.

Шаг 3. Для каждого множества Sj, если все примеры в Sj принадлежат одному и тому же классу (имеющему ту же метку класса), создать лист дерева решений и пометить меткой этого класса. Иначе перейти к 1, положив S = Sj. Алгоритм заканчивает работу, когда все подмножества по­мечены, либо отсутствуют элементы, разделяющие непо­меченные множества.


Комментарии закрыты.