基于html和js实现的ID3决策树算法

柔光的暖阳◎ 2024-04-06 13:57 56阅读 0赞

一、实验内容  
利用ID3实现决策树

二、实验设计（原理分析及流程）  
1.决策树介绍  
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。  
决策树是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。  
2 ID3算法介绍  
ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法，即Iterative Dichotomiser 3，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。本文转载自http://www.biyezuopin.vip/onews.asp?id=14789该算法采用自顶向下的贪婪搜索遍历可能的决策空间。  
3信息熵与信息增益  
在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。在认识信息增益之前，先来看看信息熵的定义熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。  
信息增益是针对一个一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。

数据结构：  
存储表对象，具体为一个数组对象，内包含若干数组

var examples = [
    {
        day:'D1',outlook:'Sunny', temp:'Hot', humidity:'High', wind: 'Weak',play:'No'},
    {
        day:'D2',outlook:'Sunny', temp:'Hot', humidity:'High', wind: 'Strong',play:'No'},
    {
        day:'D3',outlook:'Overcast', temp:'Hot', humidity:'High', wind: 'Weak',play:'Yes'},
    {
        day:'D4',outlook:'Rain', temp:'Mild', humidity:'High', wind: 'Weak',play:'Yes'},
    {
        day:'D5',outlook:'Rain', temp:'Cool', humidity:'Normal', wind: 'Weak',play:'Yes'},
    {
        day:'D6',outlook:'Rain', temp:'Cool', humidity:'Normal', wind: 'Strong',play:'No'},
    {
        day:'D7',outlook:'Overcast', temp:'Cool', humidity:'Normal', wind: 'Strong',play:'Yes'},
    {
        day:'D8',outlook:'Sunny', temp:'Mild', humidity:'High', wind: 'Weak',play:'No'},
    {
        day:'D9',outlook:'Sunny', temp:'Cool', humidity:'Normal', wind: 'Weak',play:'Yes'},
    {
        day:'D10',outlook:'Rain', temp:'Mild', humidity:'Normal', wind: 'Weak',play:'Yes'},
    {
        day:'D11',outlook:'Sunny', temp:'Mild', humidity:'Normal', wind: 'Strong',play:'Yes'},
    {
        day:'D12',outlook:'Overcast', temp:'Mild', humidity:'High', wind: 'Strong',play:'Yes'},
    {
        day:'D13',outlook:'Overcast', temp:'Hot', humidity:'Normal', wind: 'Weak',play:'Yes'},
    {
        day:'D14',outlook:'Rain', temp:'Mild', humidity:'High', wind: 'Strong',play:'No'}
    ];
    
    存储属性的数组
    var features = ['outlook', 'temp', 'humidity', 'wind'];
    
    决策树存储示例
    var samples = [{
        outlook:'Overcast', temp:'Mild', humidity:'High', wind: 'Strong',play: 'Yes'},
    	       {
        outlook:'Rain', temp:'Mild', humidity:'High', wind: 'Strong', play: 'No'},
    	       {
        outlook:'Sunny', temp:'Cool', humidity:'Normal', wind: 'Weak', play: 'Yes'}]

![在这里插入图片描述][b920ddede54e4f89b555aefcc1140636.png_pic_center]  
![在这里插入图片描述][455043266b874289b5a17db40ef76b9a.png_pic_center]  
![在这里插入图片描述][9a485a9c29614f1aadc56871b4eae5bb.png_pic_center]  
![在这里插入图片描述][64f272168220472fbb15edc59d21e2e3.png_pic_center]  
![在这里插入图片描述][45b307751f12474a8122cc7d0d8e412f.png_pic_center]  
![在这里插入图片描述][3acaad0610e04a868e04a9a9a194286d.png_pic_center]

[b920ddede54e4f89b555aefcc1140636.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a6d7f8b354bf4e4e853c71b24dfd5aab.png
[455043266b874289b5a17db40ef76b9a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/26483f568fd84aaf80bcdfdb0a5360e2.png
[9a485a9c29614f1aadc56871b4eae5bb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2285323a397a49e5a88c4b9af07c7d97.png
[64f272168220472fbb15edc59d21e2e3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8ae96be2d6914454915a29f68a4df0e6.png
[45b307751f12474a8122cc7d0d8e412f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/beda0df2fefe46f8b2c7690be201a511.png
[3acaad0610e04a868e04a9a9a194286d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/867eedbacd6342e9bd37316efa0e1e05.png