Эвристические алгоритмы. Урок 2. Обучение решающих деревьев.
Чтобы смотреть урок полностью, подпишитесь на платный раздел.
В платном разделе статья находится здесь.
Исходники у уроку можно скачать в платном разделе
В этом уроке речь пойдет об обучении решающих деревьев. В общей сложности, алгоритм обучения дерева решения можно изобразить в таком виде:
| S0 = вычисляем энтропию исходного
множества Если S0 == 0 значит: Все объекты исходного набора, принадлежат к одному классу Сохраняем этот класс в качестве листа дерева Если S0 != 0 значит: Перебираем все элементы исходного множества: На основе каждого элемента генерируем предикат, который разбивает исходное множество на два подмножества Рассчитываем среднее значение энтропии Вычисляем ∆S Нас интересует предикат, с наибольшим значением ∆S Найденный предикат является частью дерева принятия решений, сохраняем его Разбиваем исходное множество на подмножества, согласно предикату Повторяем данную процедуру рекурсивно для каждого подмножества |
Как считаем энтропию? По формуле Шеннона:
|
|
(1.1) |
Подробнее про энтропию см. также Математическое моделирование. Урок 4. Пример решения задачи....
...
...
Ну и все, можно приступать к тестирования. Сделаем на форме кнопочку "Обучить":
|
private void btnStudy_Click(object sender, EventArgs e) { tree.node=tree.build(selection, 10); TreeNode node = new TreeNode(); view_tree(tree.node, node); tvTree.Nodes.Add(node); } |
и кнопочку "Проверка":
|
private void btnTesting_Click(object sender, EventArgs e) { foreach (SelectionItem item in selection) { if (tree.calk(tree.node, item.parameters) != item.kind) { MessageBox.Show(item.parameters.ToString()+" не сходиться!"); return; } } MessageBox.Show("Проверка успешно прошла"); } |
Для наглядности разместим на форме TreeView и парочку полей ввода NumericUpDown, для ввода координат:
...
...
... Ну и все, проверяем:
Как видим, дерево решений у нас построилось автоматический. Не так компактно, как было вручную (на прошлом уроке) , но тем не менее, это работает. Другое дело, что при большом числе точек такой алгоритм будет тормозить, но из этот есть выход. Какой? Об этом узнаем из будущих уроков, когда начнем применять деревья решений к большим выборкам.