第六周作业报告

编程入门行业动态更新时间:2024-10-21 20:33:49

第六周作业报告

1、CART算法

GINI指数：

是一种不等性度量；
通常用来度量收入不平衡，可以用来度量任何不均匀分布；
是介于0~1之间的数，0-完全相等，1-完全不相等；
总体内包含的类别越杂乱，GINI指数就越大
对于一个数据集T，其Gini计算方式为

gini(T)=1−∑j=1np2j $gini(T) = 1-\sum_{j=1}^n p_j^2$

进而引出Ginigain
$Gini_s(T) = \sum_{i=1}^n \frac{N_i}{N}gini(T_i)$
其中i表示特征第i个取值

CART分析步骤

从根节点t=1开始，从所有可能候选S集合中搜索使不纯性降低最大的划分S*，然后，使用划分S*将节点1（t=1）划分成两个节点t=2和t=3
在t=2和t=3上分别重复划分搜索过程。

基尼不纯度指标

在CART算法中,
基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时，基尼不纯度为零。

2、ID3，C4.5

信息熵：

在概率论中，信息熵给了我们一种度量不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值。若待分类的事物可能划分在N类中，分别是x1，x2，……，xn，每一种取到的概率分别是P1，P2，……，Pn，那么X的熵就定义为：

H(X)=−∑i=1npilogpi $H(X) = - \sum_{i=1}^n p_i \log p_i$

条件熵：

假设有随机变量(X,Y)，其联合概率分布为:P(X=xi,Y=yi)=pij,i=1,2,⋯,n;j=1,2,⋯,m
则条件熵(H(Y∣X))表示在已知随机变量X的条件下随机变量Y的不确定性，其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望:

H(Y|X)=∑i=1npiH(Y|X=xi) $H(Y|X) = \sum_{i=1}^n p_i H(Y|X=x_i)$

信息增益：

表示得知特征x的信息后是的y的不确定性减少的程度，定义为：

g(D,A)=H(D)−H(D|A) $g(D,A) = H(D) - H(D|A)$

ID3
可以归纳为以下几点：
1. 使用所有没有使用的属性并计算与之相关的样本熵值
2. 选取其中熵值最小的属性
3. 生成包含该属性的节点

C4.5
ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。
C4.5首先定义了分裂信息，定义为：

SplitInfoA(D)=−∑i=1u|Dj||D|log2(|Dj||D|) $SplitInfo_A(D) = - \sum_{i=1}^u \frac{|D_j|}{|D|} \log_2(\frac{|D_j|}{|D|})$
C4.5选择具有最大增益率的属性作为分裂属性，其具体应用与ID3类似