# RandomForest

**Repository Path**: Mr-Bugs/random-forest

## Basic Information

- **Project Name**: RandomForest
- **Description**: 算法课的大作业
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-11-08
- **Last Updated**: 2023-12-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#随机森林算法的手动实现

##信息熵
信息熵是评估平均信息量的概念  
假设在10个样本中，有3个a，3个b，4个c
则该样本的信息熵`Ent=-0.3*log0.3-0.3*log0.3-0.4*log0.4`(log通常用2为底)  
**计算连续值而非离散值的方式略有不同**
而通常情况下，一个样本中的每条数据会有多个属性，每个属性具有一个值，因此，一个样本应该是如下的结构

    dataset=[
        {
            "key1":0.1,
            "key2":0.2,
            "key3":0.3
        },
        {
            "key1":0.3,
            "key2":0.2,
            "key3":0.1
        },
        {
            "key1":0.3,
            "key2":0.1,
            "key3":0.2
        }
    ]

由于随机森林方法是用来分类的，因此输入的数据通常还具有一个被称为"Class"的属性，描述这个数据**应该**被分到哪一类（训练数据有，测试数据没有）

因此，信息熵需要对每个属性（包括Class）进行单独的计算，对于一组样本，可以得到

    Ent(Class)=xxx
    Ent(key1)=xxx
    Ent(key2)=xxx
    Ent(key3)=xxx

##决策树

***本作业中使用ID3算法生成决策树***

决策树是一种多叉树状结构，根据给出的一条数据的多个属性进行判断，返回该数据的Class

决策树的每个节点是对数据的某个属性进行的一次判断，根据这次判断，将会产生以下结果之一

- 确定数据的Class
- 根据属性值分类，前往指定的下个节点继续进行判断


使用训练数据生成决策树的流程如下：
![决策树生成流程](/tree_generate.png)

##随机森林
将训练数据随机分为几组，每组只使用部分数据属性进行训练，每组数据训练出一棵树。

对于给出的一条测试数据，每颗树对其进行评判，最后的结果以多棵树投票的总评价为准。

##数据随机
本作业使用的数据集为150条，通过fisher-Yates-shuffle进行随机打乱后，取前80%为训练数据，后20%为测试数据

##运行结果

    tree result: 0.9
    forest result: 0.9666666666666667