【机器学习-决策树模块-基础算法-1)ID3算法】

简介: 【机器学习-决策树模块-基础算法-1)ID3算法】

决策树最最最基础的三个算法:

对于什么是决策树,决策树的基本概念网上已经多的不能再多了这里不再赘述,直接切入正题,决策树的算法以及实现。

至于遇到的必须要掌握的信息论相关知识,我会在这篇文章里根据自己遇到的知识来持续更新:

点击打开链接:(http://blog.csdn.net/qq_36396104/article/details/79275836)

-------------------------------------------------------------------------------------------------------------------------

一.ID3

· ID3算法是由Quinlan首先提出的,该算法以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。首先,ID3算法需要解决的问题是如何选择特征作为划分数据集的标准。在ID3算法中,选择信息增益最大的属性作为当前的特征对数据集分类。就是对各个feature信息计算信息增益,然后选择信息增益最大的feature作为决策点将数据分成两部分然后再对这两部分分别生成决策树。

 ·通过迭代的方式,我们可以得到决策树模型。

网络异常,图片无法展示
|
   
网络异常,图片无法展示
|
 

 

·至于什么是ID3决策树的终止条件以及其它的问题,还是放到例子里进行理解:(最近数学建模需要,用matlab代码,   python代码需要的可以看这篇博客:机器学习实战_初识决策树算法_理解其python代码(一)

----------------------------------------------------------------------------------------------------------------------------

·实例:

  实例:通过这几个指标(age,income,等等)来判断是否买电脑。

网络异常,图片无法展示
|

共14条记录,目标属性是,是否买电脑,共有两个情况,yes或者no。

首先需要对数据处理,例如age属性,我们用0表示youth,1表示middle_aged,2表示senior等。


网络异常,图片无法展示
|

·实例的MATLAB代码:

%% Decision Tree
% ID3

·1、导入数据

%data = [1,1,1;1,1,1;1,0,0;0,1,0;0,1,0]; 
data = [0,2,0,0,0;
    0,2,0,1,0;
    1,2,0,0,1;
    2,1,0,0,1;
    2,0,1,0,1;
    2,0,1,1,0;
    1,0,1,1,1;
    0,1,0,0,0;
    0,0,1,0,1;
    2,1,1,0,1;
    0,1,1,1,1;
    1,1,0,1,1;
    1,2,1,0,1;
    2,1,0,1,0];
% 生成决策树createTree(data);

·2、开始创建决策树

%CREATTREE 此处显示有关此函数的摘要
%   此处显示详细说明
function [ output_args ] = createTree( data )
    [m,n] = size(data);%m行n列
    disp('original data:');
    disp(data);%显示导入的数据
    classList = data(:,n);
    %记录第一个类的个数:
    classOne = 1;
    for i = 2:m
        if classList(i,:) == classList(1,:)
            classOne = classOne+1;
        end
    end
    % 类别全相同
    if classOne == m
        disp('final data: ');
        disp(data);
        return;
    end
    % 特征全部用完
    if n == 1
        disp('final data: ');
        disp(data);
        return;
    end
    bestFeat = chooseBestFeature(data);%% 选择信息增益最大的特征
    disp(['bestFeat: ', num2str(bestFeat)]);
    featValues = unique(data(:,bestFeat));
    numOfFeatValue = length(featValues);
    for i = 1:numOfFeatValue
        createTree(splitData(data, bestFeat, featValues(i,:)));
        disp('-------------------------');
    end
end

·3、选择信息增益最大的特征

%% 选择信息增益最大的特征
function [ bestFeature ] = chooseBestFeature( data )
    [m,n] = size(data);% 得到数据集的大小
    % 统计特征的个数
    numOfFeatures = n-1;%最后一列是类别
    % 得到原始的熵
    baseEntropy = calEntropy(data);
    bestInfoGain = 0;%初始化信息增益
    bestFeature = 0;% 初始化最佳的特征位
    % 挑选最佳的特征位
    for j = 1:numOfFeatures
        featureTemp = unique(data(:,j));%得到每个feature的属性
        numF = length(featureTemp);%属性的个数
        newEntropy = 0;%划分之后的熵
        for i = 1:numF
            subSet = splitData(data, j, featureTemp(i,:));
            [m_1, n_1] = size(subSet);
            prob = m_1./m;
            newEntropy = newEntropy + prob * calEntropy(subSet);%计算划分之后的熵,此时的subSet里的变量只有一个值(这样复用函数对计算的效率会有点影响)
        end
        %计算信息增益(熵 - 条件熵)
        infoGain = baseEntropy - newEntropy;
        if infoGain > bestInfoGain
            bestInfoGain = infoGain;
            bestFeature = j;
        end
    end
end
4、一些基础的计算函数


function [ entropy ] = calEntropy( data )
    [m,n] = size(data);
    % 得到类别的项
    label = data(:,n);
    % 处理label
    label_deal = unique(label);%得到所有的类别
    numLabel = length(label_deal);
    prob = zeros(numLabel,2);%存储每个标签的个数
    % 统计每个标签的个数
    for i = 1:numLabel
        prob(i,1) = label_deal(i,:);
        for j = 1:m
            if label(j,:) == label_deal(i,:)
                prob(i,2) = prob(i,2)+1;
            end
        end
    end
    % 计算熵
    prob(:,2) = prob(:,2)./m;%存储每个标签的概率
    entropy = 0;
    for i = 1:numLabel
        entropy = entropy - prob(i,2) * log2(prob(i,2));
    end
end
function [ subSet ] = splitData( data, axis, value )  
    [m,n] = size(data);%得到待划分数据的大小  
    subSet = data;  
    %除去第axis个feature,得到剩下的满足第axis列值为value的data 
    subSet(:,axis) = []; 
    k = 0;  
    for i = 1:m  
        if data(i,axis) ~= value  
            subSet(i-k,:) = [];  
            k = k+1;  
        end  
    end

从这个例子来看,ID3决策树还是很简单的,就是通过计算信息增益来得到最有价值的那个feature,这样不断迭代,直到遍历完所有的features,从而得到决策树。

决策树ID3算法的不足:

    ID3算法虽然提出了新思路,但是还是有很多值得改进的地方。  

    a)ID3没有考虑连续特征,比如长度,密度都是连续值,无法在ID3运用。这大大限制了ID3的用途。

    b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现,在相同条件下,取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值,各为1/2,另一个变量为3个值,各为1/3,其实他们都是完全不确定的变量,但是取3个值的比取2个值的信息增益大。如果校正这个问题呢?

    c) ID3算法对于缺失值的情况没有做考虑

    d) 没有考虑过拟合的问题

end

-------------------------------------------------------------------------------------------------------------------------

ID3 算法的作者昆兰基于上述不足,对ID3算法做了改进,这就是C4.5算法:

http://blog.csdn.net/qq_36396104/article/details/79291740


AIEarth是一个由众多领域内专家博主共同打造的学术平台,旨在建设一个拥抱智慧未来的学术殿堂!【平台地址:https://devpress.csdn.net/aiearth】 很高兴认识你!加入我们共同进步!

目录
相关文章
|
3月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
196 6
|
1月前
|
机器学习/深度学习 人工智能 算法
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
276 13
机器学习算法的优化与改进:提升模型性能的策略与方法
|
1天前
|
机器学习/深度学习 人工智能 自然语言处理
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
1月前
|
机器学习/深度学习 算法 网络安全
CCS 2024:如何严格衡量机器学习算法的隐私泄露? ETH有了新发现
在2024年CCS会议上,苏黎世联邦理工学院的研究人员提出,当前对机器学习隐私保护措施的评估可能存在严重误导。研究通过LiRA攻击评估了五种经验性隐私保护措施(HAMP、RelaxLoss、SELENA、DFKD和SSL),发现现有方法忽视最脆弱数据点、使用较弱攻击且未与实际差分隐私基线比较。结果表明这些措施在更强攻击下表现不佳,而强大的差分隐私基线则提供了更好的隐私-效用权衡。
53 14
|
2月前
|
算法
PAI下面的gbdt、xgboost、ps-smart 算法如何优化?
设置gbdt 、xgboost等算法的样本和特征的采样率
95 2
|
3月前
|
机器学习/深度学习 算法 Python
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。本文详细介绍了随机森林的工作原理、性能优势、影响因素及调优方法,并提供了Python实现示例。适用于分类、回归及特征选择等多种应用场景。
117 7
|
3月前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
78 1
|
3月前
|
机器学习/深度学习 自然语言处理 算法
深入理解机器学习算法:从线性回归到神经网络
深入理解机器学习算法:从线性回归到神经网络
|
3月前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
179 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
3月前
|
机器学习/深度学习 算法
深入探索机器学习中的决策树算法
深入探索机器学习中的决策树算法
60 0

热门文章

最新文章