Реализация алгоритма классификации деревьев решений на Python

В этой статье пример кода python для реализации алгоритма классификации дерева решений предоставляется для вашего рассмотрения, подробности см. ниже

1. Обзор

Дерево решений (decision tree) - это вид широко используемого алгоритма классификации.

По сравнению с алгоритмом Байеса, преимущество дерева решений заключается в том, что процесс его создания не требует никаких знаний области или настройки параметров

На практике для обнаружения знаний по запросу дерево решений более пригодно.

2. Идея алгоритма

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

　　　　　 Дочь: Сколько ему лет?

　　　　　 Мать: 26.

　　　　　 Дочь: Как он выглядит?

　　　　　 Мать: Он очень красивый.

　　　　　 Дочь: Доход высокий?

　　　　　 Мать: Не очень высокий, средний уровень.

　　　　　 Дочь: Он госслужащий?

　　　　　 Мать: Да, работает в налоговой.

　　　　　 Дочь: Ну, я встречусь.　

Процесс принятия решения этой девушки является типичным процессом принятия решения с использованием классификационного дерева.

Сущность:Через возраст, внешность, доход и является ли он государственным служащим, мужчину можно разделить на две категории: встречаться и не встречаться

Предположим, что у этой девушки требования к мужчине такие: моложе 30 лет, среднего или выше среднего внешнего вида и высокооплачиваемый работник или работник с доходом выше среднего, то это можно представить следующим образом:

Upper image fully expresses the strategy of this girl to decide whether to meet a date object, among which:

Зеленые узлы показывают условия.

Оранжевые узлы показывают результат принятия решения.

Стрелки показывают путь принятия решения при различных условиях.

Красные стрелки на изображении показывают процесс принятия решения девушки из предыдущего примера.　

Это изображение можно считать деревом решений, говорят, что это «более-менее можно считать», потому что условия в этом изображении не количественно определены, например, высокий, средний и низкий доходы, и это еще не строгое дерево решений. Если все условия количественно определить, то оно станет真正的 деревом решений.　

Ключевой алгоритм классификации дерева решений заключается в том, чтобы на основе «пriorsких данных» построить наилучшее дерево решений для предсказания категорий незнакомых данных　

Дерево решений: это структура дерева (может быть двоичным или не двоичным). Каждый нелистовой узел представляет тест на свойстве характеристики, каждая ветвь代表着这个 характеристика в определенном диапазоне значений, а каждый листовой узел хранит категорию. Процесс принятия решения с использованием дерева решений начинается с корневого узла, тестирования соответствующего свойства характеристики предмета классификации, и выбора ветви в зависимости от значения, до достижения листового узла, где хранится категория как результат принятия решения.

3. Конструкция дерева решений

Если у вас есть следующие данные样本 для определения качества яблок:

Примеры样本а　　　 Красный　　　　 Размер　　　　　 Хорошие яблоки

0　　　　　　　 　1　　　　　 1　　　　　　　　 1

1　　　　　　　 　1　　　　　 0　　　　　　　　 1

2　　　　　　　 　0　　　　　 1　　　　　　　　 0

3　　　　　　　 　0　　　　　 0　　　　　　　　 0

В данном примере样本 имеет 2 свойства, A0 означает, является ли яблоко красным. A1 означает, является ли яблоко большим. Если нужно построить дерево решений для автоматического определения качества яблок.

Поскольку в данном примере данные имеют только 2 свойства, мы можем перечислить все возможные деревья решений, которые можно построить, всего 2, как показано на рисунке ниже:

显然, дерево решений, которое сначала использует A0 (красный) в качестве критерия разбиения, лучше того, которое использует A1 (размер) в качестве критерия разбиения.

Конечно, это интуитивное понимание. А интуиция显然 не подходит для реализации в программе, поэтому необходим метод количественной оценки для оценки производительности этих двух деревьев.

Квантitative метод оценки, используемый для оценки деревьев решений:Расчет增益 энтропии для каждого случая разбиения:

Если после разбиения данных по выбранному свойству информационная энтропия снижается наиболее сильно, то это разбиение является оптимальным выбором　

Основание для выбора属性的 разбиения (т.е. строительство дерева решений):

Простыми словами, энтропия - это уровень «беспорядка» или «хаоса».

Чтобы понять это, нужно вычислить:

1. Энтропия исходных данных样本а:

Общее количество примеров: 4

Хорошие яблоки: 2

Плохие яблоки: 2

Энтропия: -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1

Информационная энтропия 1 означает, что текущее состояние является наиболее хаотичным и наиболее безорядочным.

2. Расчет增益 энтропии результатов разбиения двух деревьев решений

Дерево 1 сначала выбирает A0 в качестве критерия разбиения, расчет информационной энтропии для каждого подузла следующий:

У узлов 0 и 1 есть 2 положительных примера, нет отрицательных примеров. Информационная энтропия: e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0.

У узлов 2 и 3 нет положительных примеров, есть 2 отрицательных примера. Информационная энтропия: e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0.

Таким образом, выбирается информационная энтропия A0, которая является весовой суммой доли информационной энтропии каждого подузла: E = e1 * 2/4 + e2 * 2/4 = 0.

Информационный增益 от разделения A0 G(S, A0) = S - E = 1 - 0 = 1.

Фактически, листья дерева принятия решений представляют собой категории, к которым уже относятся все, поэтому энтропия всегда равна 0.　

Ребенок 2 сначала выбирает A1 для разделения, и расчет энтропии всех подузлов следующий:

Узлы 0 и 2 имеют по одному положительному и одному отрицательному примерам. Информационная энтропия: e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

Узлы 1 и 3 имеют по одному положительному и одному отрицательному примерам. Информационная энтропия: e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

Таким образом, энтропия после разделения A1 составляет加权 среднее информационной энтропии всех подузлов: E = e1 * 2/4 + e2 * 2/4 = 1. То есть разделение не изменило ситуацию!

Информационный增益 от разделения A1 G(S, A1) = S - E = 1 - 1 = 0.　

Таким образом, перед каждым разделением нам нужно только вычислить разделение с максимальным增益 энтропии.

Информационный增益 от разделения A0 на начальном этапе больше, чем от разделения A1, поэтому разделение A0 является оптимальным выбором!!!

4. Идеология алгоритма

После разделения по свойствам принятия решений беспорядок данных становится все меньше, то есть энтропия становится все меньше.　

5. Реализация алгоритма

Систематизируйте свойства данных

Сравните информацию о增益 энтропии для данных, разделенных по определенному свойству, и выберите свойство с максимальным增益 энтропии в качестве первого основания для разделения, затем продолжайте выбирать второе свойство и так далее.

Вот весь контент статьи, надеюсь, он поможет вам в изучении. Также просим вас активно поддерживать учебник Kaoan.

Заявление: содержимое этой статьи взято из Интернета, авторские права принадлежат соответствующему автору. Контент был предложен и загружен пользователями Интернета. Этот сайт не имеет права собственности на него, не производил ручную редактуру и не несет ответственности за соответствующие юридические последствия. Если вы обнаружите подозрительное содержимое, пожалуйста, отправьте письмо по адресу: notice#oldtoolbag.com (во время отправки письма замените # на @), чтобы сообщить о нарушении авторских прав,并提供 соответствующие доказательства. Если нарушение будет подтверждено, сайт немедленно удалит подозрительное содержимое.