В этом блоге мы сначала коснемся истории дерева решений, и я дам вам полное руководство, чтобы понять концепцию, лежащую в основе дерева решений, и то, как оно работает, на интуитивно понятном примере.
Начало моделей дерева решений
Первоначальная модель для выполнения анализа дерева решений была создана J. Росс Куинлан из Сиднейского университета и представленный в его книге Машинное обучение, vol.1, no. 1, в 1975 году. Его первый алгоритм построения дерева решений назывался Итеративный дихотомайзер 3 (ID3). Этот алгоритм был создан на основе принципов бритвы Оккама с идеей создания наименьшего и наиболее эффективного дерева решений. Куинлан продолжил дальнейшее развитие этой модели, создав алгоритм C4.5 и, наконец, алгоритм C5.0.
Что такое дерево решений?
Дерево решений - это алгоритм обучения с учителем. Деревья решений генерируются путем разделения генеральной совокупности и выборочных данных на основе условий и порогового значения таким образом, чтобы одни и те же группы были похожи друг на друга, а группы существенно отличались друг от друга. Дерево решений в основном используется в задачах классификации. Но он работает как для категориальных, так и для числовых данных.
Математическая концепция:
Энтропия:
Информационная энтропия - это средняя скорость, с которой информация производится стохастическим источником данных. Он измеряет важность информации относительно ее размера. Энтропия - это мера непредсказуемости состояния или, что эквивалентно, его среднего информационного содержания.
А в контексте дерева решений энтропия показывает, насколько данные имеют дисперсию.
Энтропия максимальна, когда данные неоднородны (нечисты). И минимум, когда данные однородны (чистые).
Например:
Если мы подбрасываем монету и вероятность выпадения орла такая же, как и вероятность выпадения решки, то энтропия подбрасывания монеты настолько высока, насколько это могло бы быть для испытания с двумя исходами. А если монета смещена и всегда дает орел, и у нее нет хвоста, энтропия равна нулю, так как монета всегда будет выпадать орлом, и результат можно точно предсказать.
Для дерева решений мы должны вычислить 2 типа энтропии:
- Энтропия E (S) одного атрибута, где S - текущее состояние (существующие результаты), а P (x) - вероятность события x этого состояния S:
2. Энтропия E (S, A) двух атрибутов - S и A, где S - текущий состояние с атрибутом A, A - это выбранный атрибут, а P (x) - вероятность события x атрибута A.
Получение информации:
Он представляет собой изменение энтропии или уменьшение энтропии. Он измеряет качество разделения и количество информации о классе, которую дает нам функция. Максимум информации будет для объекта, который разбит на разделы идеально.
Это также называется дивергенцией Кульбака-Лейблера. Он измеряет относительное изменение энтропии относительно независимых переменных. Обозначается IG (S, A).
ID3 (Итерационный дихотомизатор)
Это наиболее распространенный и старый алгоритм дерева решений. Дерево решений работает по правилу «разделяй и властвуй». Здесь дихотомизатор означает разделение на две противоположные части. Этот алгоритм делит объекты в интерактивном режиме на две группы, которые полностью независимы друг от друга и строят дерево на основе правила разделения.
Критерий разделения
ID3 использует жадный поиск сверху вниз для построения дерева с помощью энтропии и сбора информации. Атрибут, имеющий наибольшее количество информации, будет считаться лучшим атрибутом для разделения.
Правило классификации
Если энтропия для отдельного объекта равна 0, это означает, что это однородный узел и нет необходимости в дальнейшей классификации. Если энтропия равна 1, это неоднородный узел и требуется дальнейшая классификация.
Пример
Используя данные двухнедельных тренировок, нам нужно решить, подходит ли погода для игры в крикет с использованием алгоритма ID3.
Здесь выходная или целевая переменная - это решение.
Энтропия для переменной решения:
Здесь:
«Да» = 9
‘No’ = 5
Итого = 14
Теперь у нас есть 4 входных атрибута: Outlook, Температура, Влажность, Ветер.
Мы рассчитаем информационный выигрыш для каждой переменной, и переменная с наибольшим информационным выигрышем будет корневым узлом.
Начнем с атрибута outlook:
Атрибут Outlook имеет 3 переменных: солнечно, пасмурно и дождливо.
У Санни:
2 да и 3 нет
пасмурно имеет 4 да 0 нет
дождливый уже 3 да 2 нет.
Расчетная энтропия для каждого человека составляет:
Теперь мы рассчитаем взвешенную энтропию после разделения данных:
Наконец, получение информации для атрибута внешнего вида:
Таким же образом мы можем рассчитать IG для температуры, влажности и ветра.
IG для соответствующих атрибутов:
IG (S, температура): 0,029
IG (S, влажность): 0,151
IG (Ю, ветрено): 0,048
Из вышеизложенного наблюдения IG (S, Outlook) имеет самый высокий информационный прирост 0,246, поэтому атрибут Outlook будет корневым узлом:
Из представленного выше обзора дерева - - ›пасмурность всегда да (энтропия для пасмурности равна 0).
Теперь у нас есть 3 оставшихся атрибута.
Сначала мы рассчитаем энтропию принятия решения при благоприятных погодных условиях.
E (Решение | прогноз = солнечно) = 0,96
E (Decision | outlook = sunny) можно представить как E (S | outlook = sunny).
Теперь таким же образом мы рассчитаем получение информации при солнечной погоде по температуре, влажности и признаку ветра:
IG (прогноз = солнечно, температура) = 0,570
IG (внешний вид = солнечно, влажность) = 0,970
IG (перспектива = солнечно, ветрено) = 0,019
Из вышеприведенных выходных данных влажность дает самый высокий информационный выигрыш, точно так же, как ветер дает нам самый высокий информационный выигрыш для (S | outlook = дождь).
Итак, окончательное дерево решений будет:
Заключение
В ID3, если переменная числовая, мы должны преобразовать ее в номинальную переменную. Данные могут быть переоборудованы или классифицированы. Эти проблемы были выявлены и преодолены в C4.5 и C5.0 Дж. Россом Куинланом. Это мы увидим в следующей части.
