Три алгоритма дерева решений (ID3, CART, C4.5) и реализация Python

Github: github.com/yingzk/MyML
Блог:www.yingjoy.cn

1. Введение в дерево решений

1.1 Принцип дерева решений

Дерево решений — это относительно простой тип алгоритма классификации машинного обучения с учителем.Дерево решений — это модель прогнозирования, представляющая отношение сопоставления между атрибутами объекта и значениями объекта. Каждый узел в дереве представляет объект, и каждый путь бифуркации представляет возможное значение атрибута, и каждый конечный узел соответствует объекту, представленному путем от корневого узла к конечному узлу. Дерево решений имеет только один выход.Если вы хотите иметь несколько выходов, вы можете построить независимое дерево решений для обработки разных выходов. Это процесс классификации данных с помощью ряда правил.

Пример: Пример того, стоит ли выходить на выходные

Дерево решений предназначено для преобразования набора данных в древовидную структуру следующим образом:

1.2 Процесс построения дерева решений

Обычно состоит из трех частей 1. Выбор функции: выбор функции относится к выбору функции из множества функций в обучающих данных в качестве критерия разделения для текущего узла.Существует множество различных количественных критериев оценки того, как выбрать функцию, чтобы принять другое решение древовидные алгоритмы, такие как CART, ID3, C4.5 и т.д. 2. Генерация дерева решений: в соответствии с выбранными критериями оценки функций рекурсивно генерируйте дочерние узлы сверху вниз и останавливайте рост дерева решений до тех пор, пока набор данных не станет неразделимым. С точки зрения древовидной структуры рекурсивная структура является самым простым способом понимания. 3. Обрезка: деревья решений склонны к переоснащению.Как правило, обрезка требуется для уменьшения размера древовидной структуры и устранения переобучения. Технология обрезки имеетПредварительная обрезкаипосле обрезкидва вида.

Поддельный код

if 遇到终止条件:
	return 类标签
else:
	寻找一个最优特征对数据集进行分类
	创建分支点
	对每个分支节点进行划分，将分支点返回到主分支
	return 分支节点

1.3 Преимущества и недостатки деревьев решений

Деревья решений подходят для числовых и номинальных типов (дискретные данные, результаты переменных принимают значения только в ограниченном целевом наборе) и могут считывать наборы данных и извлекать правила, содержащиеся в некоторых сериях данных. Использование моделей деревьев решений в задачах классификации имеет много преимуществ.Деревья решений не требуют сложных вычислений, просты в использовании и эффективны.Деревья решений могут обрабатывать данные с нерелевантными функциями и могут легко создавать простые для понимания правила.Как правило, правила просты. объяснить и понять. У моделей дерева решений также есть некоторые недостатки, такие как сложность работы с отсутствующими данными, переобучение и игнорирование корреляций между атрибутами в наборе данных.

1.4 Введение в три алгоритма дерева решений

Основная часть алгоритма дерева решений:Как выбрать атрибут раздела?

Самый ранний алгоритм дерева решений возник из системы CLS (Concept Learning System), то есть системы концептуального обучения.

Об этом надо судить количественными методами.Количественных методов много, один из них через "Метрики теории информации Классификация информации". Алгоритмы дерева решений, основанные на теории информации, включают: ID3, CART, C4.5 и другие алгоритмы.

Алгоритм ID3 был изобретен Россом Куинланом и основан на «Бритве Оккама». Чем проще дерево решений, тем лучше дерево решений (будьте проще). Алгоритм ID3 основан на информационном приросте теории информации. Оценка и выбор характеристик, каждый выбормаксимальный информационный приростФункции используются в качестве модуля суждения. Алгоритм ID3 можно использовать для разделения номинальных наборов данных.Процесс отсечения отсутствует.Чтобы устранить проблему чрезмерного сопоставления данных, смежные листовые узлы, которые не могут генерировать большой объем информации, могут быть объединены путем отсечения (например, установка порога получения информации). Недостатком использования информационного выигрыша является то, что он смещен в сторону атрибутов с большим количеством значений — то есть в обучающей выборке, чем больше различных значений принимает атрибут, тем больше вероятность его использования в качестве split, а делать это иногда бессмысленно.Кроме того, ID3 не может обрабатывать непрерывно распределенные данные, поэтому существует алгоритм C4.5 (появилась и коммерческая версия алгоритма C5.0). Алгоритм CART также поддерживает функции непрерывно распределенных данных.

C4.5 — это улучшенный алгоритм ID3, который наследует преимущества алгоритма ID3.Алгоритм C4.5 использует скорость получения информации для выбора атрибутов раздела., который преодолевает недостаток использования прироста информации для выбора атрибутов с большим количеством значений и сокращения в процессе построения дерева, может выполнять дискретную обработку непрерывных атрибутов и может обрабатывать неполные данные. Правила классификации, сгенерированные алгоритмом C4.5, просты для понимания и обладают высокой точностью, однако эффективность невысока, так как набор данных необходимо многократно сканировать и сортировать в процессе построения дерева. Кроме того, поскольку необходимо несколько сканирований наборов данных, C4.5 подходит только для наборов данных, которые могут находиться в памяти.

Полное название алгоритма CART — Дерево классификации и регрессии, которое использует индекс Джини (выберите признаки с наименьшим индексом Джини) в качестве стандарта разделения, а также включает операции пост-обрезки. Хотя алгоритм ID3 и алгоритм C4.5 могут добывать как можно больше информации при обучении набора обучающей выборки, сгенерированное ими дерево решений имеет более крупные ветви и более крупные масштабы. С целью упрощения масштаба дерева решений и повышения эффективности формирования дерева решений появляется алгоритм дерева решений CART, выбирающий признаки теста по коэффициенту Джини.

Энтропия: мера неопределенности случайной величины. (чистота)

(1) Информационная энтропия

В теории вероятностей информационная энтропия дает нам способ измерения неопределенности, которая используется для измерения неопределенности случайных величин, а энтропия — это ожидаемое значение информации. Если классифицируемые вещи можно разделить на N категорий, то они $x_1,x_2,\cdots,x_n$ , вероятность каждого взятия равна $p_1,p_2,\cdots,p_n$ , то энтропия набора данных D определяется как:

$H(D)=-\sum^{|n|}_{i=1}p_ilogp_i$

Из определения мы знаем: 0≤H(D)≤log(n)

Когда случайная величина принимает только два значения, распределение D равно P(D=1)=p, P(D=0)=1-p, 0≤p≤1 Тогда энтропия равна: H(D)=−plog_2p−(1−p)log_2(1−p) .

Чем выше значение энтропии, тем выше тип смешивания данных, а значит, тем больше возможных изменений переменной (вместо этого это не имеет ничего общего с конкретным значением переменной, только тип значения и вероятность появления ) Чем больше объем передаваемой информации.

(2) Условная энтропия

Предположим, что есть случайные величины (X,Y) , а его совместное распределение вероятностей:

$P(X=x_i,Y=y_i)=p_{ij}, i=1,2,⋯,n;j=1,2,⋯,m$ тогда условная энтропия H(Y∣X) Представляет неопределенность случайной величины Y при известной случайной величине X, которая определяется как математическое ожидание энтропии условного распределения вероятностей Y для X при данных условиях:

$H(Y|X)=\sum^{n}_{i=1}p_iH(Y|X=x_i)$

(3) Получение информации

Прирост информации относится к степени, в которой неопределенность Y уменьшается после того, как информация о признаке X известна. определяется как:

Gain(D,A)=H(D)-H(D|A)

(4) Индекс Джини

Индекс Джини (примесь Джини): Указывает вероятность того, что случайно выбранная выборка будет неправильно классифицирована в наборе выборок.

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

которыйИндекс Джини (примесь Джини) = вероятность того, что образец будет выбран * вероятность того, что образец будет неправильно классифицирован

$Gini(p)=\sum^{|y|}_{k=1}\sum_{k'}p_kp^{'}_k = 1- \sum^{|y|}_{k=1}p^2_k$

2. Реализация ID3 на Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
import pandas as pd
import operator

def loadDataSet():
    """
    导入数据
    @ return dataSet: 读取的数据集
    """
    # 对数据进行处理
    dataSet = pd.read_csv('isFish.csv', delimiter=',')
    # dataSet = dataSet.replace('yes', 1).replace('no', 0)
    labelSet = list(dataSet.columns.values)
    dataSet = dataSet.values
    return dataSet, labelSet

def calcShannonEnt(dataSet):
    """
    计算给定数据集的信息熵（香农熵）
    @ param dataSet: 数据集
    @ return shannonEnt: 香农熵
    """
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        # 当前样本类型
        currentLabel = featVec[-1]
        # 如果当前类别不在labelCounts里面，则创建
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob*np.log2(prob)
    return shannonEnt

def splitDataSet(dataSet, axis, value):
    """
    划分数据集, 提取所有满足一个特征的值
    @ param dataSet: 数据集
    @ param axis: 划分数据集的特征
    @ param value: 提取出来满足某特征的list
    """
    retDataSet = []
    for featVec in dataSet:
        # 将相同数据特征的提取出来
        if featVec[axis] == value:
            reducedFeatVec = list(featVec[:axis])
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeature(dataSet):
    """
    选择最优的划分属性
    @ param dataSet: 数据集
    @ return bestFeature: 最佳划分属性
    """
    # 属性的个数
    numFeature = len(dataSet[0])-1
    baseEntroy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeature):
        # 获取第i个特征所有可能的取值
        featureList = [example[i] for example in dataSet]
        # 去除重复值
        uniqueVals = set(featureList)
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # 特征为i的数据集占总数的比例
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * np.log2(prob)
        inforGain = baseEntroy - newEntropy
        
        if inforGain > bestInfoGain:
            bestInfoGain = inforGain
            bestFeature = i
    return bestFeature

def majorityCnt(classList):
    """
    递归构建决策树
    @ param classList: 类别列表
    @ return sortedClassCount[0][0]: 出现次数最多的类别
    """
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount += 1
    # 排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 返回出现次数最多的
    return sortedClassCount[0][0]

def createTree(dataSet, labels):
    """
    构造决策树
    @ param dataSet: 数据集
    @ param labels: 标签集
    @ return myTree: 决策树
    """
    classList = [example[-1] for example in dataSet]
    # 当类别与属性完全相同时停止
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 遍历完所有特征值时，返回数量最多的
    if (len(dataSet[0]) == 1):
        return majorityCnt(classList)
    
    # 获取最佳划分属性
    bestFeat = chooseBestFeature(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    # 清空labels[bestFeat]
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        # 递归调用创建决策树
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree
    

if __name__ == '__main__':
    dataSet, labelSet = loadDataSet()
    shannonEnt = calcShannonEnt(dataSet)
    tree= createTree(dataSet, labelSet)
    print (tree)

Другие алгоритмы, которые будут добавлены...