Machine Learning
  • Introduction
  • man
  • Linear model
    • Linear Regression
    • Generalized Linear Models
    • Nonlinear regression
  • bayes
    • bayesian network
    • Variational Bayesian inference
    • Gaussian Process Regression
  • Logistic Regression
    • L1 regularization
    • L2 regularization
    • softmax
    • Overflow and Underflow
  • SVM
    • C-SVM
    • C-SVM求解
  • EM
    • GMM
  • Maximum Entropy
    • IIS
  • HMM
    • viterbi algorithm
  • CRF
  • Random Forest
    • bagging
    • random forest
  • boosting
    • catboost
    • gradient boosting
    • Newton Boosting
    • online boosting
    • gcForest
    • Mixture models
    • XGBoost
    • lightGBM
    • SecureBoost
  • LDA
  • rank
    • RankNet
    • LambdaRank
    • SimRank
  • Factorization Machine
    • Field-aware Factorization Machine
    • xdeepFM
  • Clustering
    • BIRCH
    • Deep Embedding Clustering
  • Kalman filtering
  • word2vec
  • 关联规则挖掘
  • MATH-Mathematical Analysis
    • measure
  • MATH-probability
    • Variational Inference
    • Dirichlet分布
    • Gibbs Sampling
    • Maximum entropy probability distribution
    • Conjugate prior
    • Gaussian Process
    • Markov process
    • Poisson process
    • measure
    • Gumbel
  • MATH-Linear Algebra
    • SVD
    • SVD-推荐
    • PCA
    • Linear Discriminant Analysis
    • Nonnegative Matrix Factorization
  • MATH-Convex optimization
    • 梯度下降
    • 随机梯度下降
    • 牛顿法
    • L-BFGS
    • 最速下降法
    • 坐标下降法
    • OWL-QN
    • 对偶问题
    • 障碍函数法
    • 原对偶内点法
    • ISTA
    • ADMM
    • SAG
  • MATH-碎碎念
    • cost function
    • Learning Theory
    • sampling
    • Entropy
    • variational inference
    • basis function
    • Diffie–Hellman key exchange
    • wavelet transform
    • 图
    • Portfolio
    • 凯利公式
  • ML碎碎念
    • 特征
    • test
    • TF-IDF
    • population stability index
    • Shapley Values
  • 课件
    • xgboost算法演进
  • Time Series
  • PID
  • graph
    • SimRank
    • community detection
    • FRAUDAR
    • Anti-Trust Rank
    • Struc2Vec
    • graph theory
    • GNN
  • Anomaly Detection
    • Isolation Forest
    • Time Series
  • Dimensionality Reduction
    • Deep Embedded Clustering
  • Federated Learning
  • automl
  • Look-alike
  • KNN
  • causal inference
Powered by GitBook
On this page
  • 处理缺失属性
  • 处理连续值的属性
  • ID3与C4.5
  • CART (Classification and regression tree 分类回归树)

Was this helpful?

Random Forest

PreviousCRFNextbagging

Last updated 5 years ago

Was this helpful?

见李航的《统计学习方法》

应思考的几个问题

  • 属性值应当完全二值的还是多值的?或者节点的分支数应该是几?(CRAT和random forest是二叉树,ID3,C4.5等都是多叉树)

  • 如何确定某节点出应该测试哪个属性

  • 何时可以令某个节点成为叶子节点,即合适停止分裂。(1叶子节点很纯,2分裂后信息增益或gini系数或xgboost中的“gini”系数小于阈值)

  • 如果树生长的“过大”,如何“剪枝”使得它变小变简单(误判,以父节点“作为”叶子节点,对比子节点的预测效果,若更优,则删除子节点)

  • 如果叶子节点仍然不“纯”,那么怎么给他赋类别标签(以比较多的那类样本标签作为该节点的类别标签)

  • 缺省属性的数据如何处理(随机森林中就包含着随机选择属性)

处理缺失属性

如果有些训练样本或者待分类样本缺失了一些属性值,那么该如何处理?要解决这个问题,需要考虑3个问题:

i)当开始决定选择哪个属性用来进行分支时,如果有些训练样本缺失了某些属性值时该怎么办?

ii)一个属性已被选择,那么在决定分支的时候如果有些样本缺失了该属性该如何处理?

iii)当决策树已经生成,但待分类的样本缺失了某些属性,这些属性该如何处理?针对这三个问题,昆兰提出了一系列解决的思路和方法。

对于问题i),计算属性a的增益或者增益率时,如果有些样本没有属性a,那么可以有这么几种处理方式:

(I)忽略这些缺失属性a的样本。(这种适合于只含少量缺失值的情况)

(C)给缺失属性a的样本赋予属性a一个均值或者最常用的值。

(R)计算增益或者增益率时根据缺失属性样本个数所占的比率对增益/增益率进行相应的“打折”。

Gain(A)=属性 A 在数据集中不空的比率 × ( Entropy(S)−Entropy_A(S) )

SplitE(A)=−∑i=1k∣Si∣∣S∣log2∣Si∣∣S∣−∣Sunknow∣∣S∣log2∣Sunknow∣∣S∣SplitE(A) = -\sum_{i=1}^k \frac{|S_i|}{|S|}log_2\frac{|S_i|}{|S|} - \frac{|S_{unknow}|}{|S|}log_2\frac{|S_{unknow}|}{|S|}SplitE(A)=−∑i=1k​∣S∣∣Si​∣​log2​∣S∣∣Si​∣​−∣S∣∣Sunknow​∣​log2​∣S∣∣Sunknow​∣​

(S)根据其他未知的属性想办法把这些样本缺失的属性补全。

对于问题ii),当属性a已经被选择,该对样本进行分支的时候,如果有些样本缺失了属性a,那么:

(I)忽略这些样本。

(C)把这些样本的属性a赋予一个均值或者最常出现的值,然后再对他们进行处理。

(R)把这些属性缺失样本,按照具有属性a的样本被划分成的子集样本个数的相对比率,分配到各个子集中去。至于哪些缺失的样本被划分到子集1,哪些被划分到子集2,这个没有一定的准则,可以随机而动。

(A)把属性缺失样本分配给所有的子集,也就是说每个子集都有这些属性缺失样本。

(U)单独为属性缺失的样本划分一个分支子集。

(S)对于缺失属性a的样本,尝试着根据其他属性给他分配一个属性a的值,然后继续处理将其划分到相应的子集。

对于问题iii),对于一个缺失属性a的待分类样本,有这么几种选择:

(U)如果有单独的缺失分支,依据此分支。

(c)把待分类的样本的属性a值分配一个最常出现的a的属性值,然后进行分支预测。

(S)根据其他属性为该待分类样本填充一个属性a值,然后进行分支处理。

(F)在决策树中属性a节点的分支上,遍历属性a节点的所有分支,探索可能所有的分类结果,然后把这些分类结果结合起来一起考虑,按照概率决定一个分类。

(H)待分类样本在到达属性a节点时就终止分类,然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。

剪枝

处理连续值的属性

ID3与C4.5

C4.5算法与ID3算法相似,但:

  1. 能处理连续值的特征,对连续值进行离散化

  2. 能够处理缺失值

  3. 能剪枝

  4. 生成节点过程中使用的是信息增益比来选择特征

信息增益:特征A对训练集D的信息增益g(D,A)g(D,A)g(D,A),为集合D的经验熵H(D)H(D)H(D)与特征A给定条件下D的经验条件熵H(D∣A)H(D|A)H(D∣A)之差g(D,A)=H(D)−H(D∣A)g(D,A) = H(D) - H(D|A)g(D,A)=H(D)−H(D∣A)。

信息增益就是互信息I(X;Y)=H(X)−H(X∣Y)I(X;Y) = H(X) - H(X|Y)I(X;Y)=H(X)−H(X∣Y)

信息增益比:特征A对训练集D的信息增益gR(D,A)g_R(D,A)gR​(D,A),为其信息增益g(D,A)g(D,A)g(D,A)与经验熵H(D)H(D)H(D)之比gR(D,A)=g(D,A)H(D)g_R(D,A) = \frac {g(D,A)}{H(D)}gR​(D,A)=H(D)g(D,A)​。 C4.5选择信息增益比,是因为信息增益值的大小受训练数据集经验熵影响。

CART (Classification and regression tree 分类回归树)

ID3和C4.5只能做分类,而CART既可以处理分类,也可以处理回归。

CART算法采用一种二分递归分割的技术,与基于信息熵的算法不同,CART算法对每次样本集的划分计算GINI系数,GINI系数可以衡量纯度,与熵有类似性质,所以GINI系数越小则划分越合理。CART算法总是将当前样本集分割为两个子样本集,使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。

C4.5决策树
如何理解决策树的损失函数?
Logistic Regression Vs Decision Trees Vs SVM
Why are we growing decision trees via entropy instead of the classification error?
分类算法:决策树(C4.5)
数据挖掘十大经典算法--CART: 分类与回归树
如何解读决策树和随机森林的内部工作机制?
决策树方法小结