文章最后更新于 1564 天前,其中的信息可能已经过时。
决策树算法基础原理分析
信息的不纯度(决定决策树分支的指标)
不纯度是在决策树中衡量特征分裂优异性的最主要的指标,用于衡量样本在根据某一特征的分类标准分裂后,样本是否被正确分类的准确程度。
主要有 3 种计算方式,分别对应了 3 类决策树:
| 决策树类别 | 不纯度计算方式 |
|---|---|
| ID3 | 信息增益(Information Gain) |
| C4.5 | 信息增益率(Information Gain Ratio) |
| CART | 基尼系数(Gini index) |
-
信息熵的计算 信息熵的计算公式为:
$ H(D)=-\displaystyle\sum_{i=1}^n p_i log_2 p_i $ 其中$ n $为样本D的类别数,$ p_i $为该样本所占样本总数的比例 -
信息增益的计算 信息增益的计算公式:
$ g(D,A)=H(D)-H(D|A) $ 其中,$ H(D|A) $代表在以$ A $为标准分类后的所有样本的信息熵之和 -
信息增益率 信息增益率的计算公式:
$$ IGR=\frac{g(D,A)}{H(A)} $$ 其中 $ H(A) $代表 $ A $ -
基尼系数 基尼系数的计算公式:
$ Gini(p)=\displaystyle\sum_{i=1}^n p_i (1-p_i) = 1 - \displaystyle\sum_{i=1}^n p_i ^2 $ 其中$ n $为样本D的类别数,$ p_i $为该样本所占样本总数的比例 基尼系数值越小,表示该分类方法贡献的信息度越高,即不纯度越小
特征的最佳切分点
特征的类型分为两种情况:
- 离散型变量
- 连续性变量
- 对于离散型变量: 可分为二叉树与多叉树
- 对于连续性变量
- 首先将样本的某一连续变量的值去重后按照升序进行排列
- 计算两两相邻的平均值
- 遍历,将的每一个点都作为该连续变量的切分点,并计算其分裂的不纯度,获得长度为 n − 1 的不纯度集
- 其中最大的不纯度,其切分点即为最佳切分点
- 特征在决策树中决策的先后顺序 决策的先后顺序,即为根据不同变量进行分裂的顺序。在找出每个变量的最佳分裂点后,可以计算出以该点分裂所能获得的信息度(信息增益/信息增益率/基尼系数…等),以最大信息度的变量放在最前面进行分裂,最小的放在最后面分裂。这样就确定了在对样本进行区分的时候,越早分裂的样本能以最佳的区分方法进行划分。
ID3, C4.5, CART 对比说明
| 类型 | 特点 | 劣势 |
|---|---|---|
| ID3 | 多叉树;特征只用一次;健壮性较好,能训练属性值有缺失的情况 | 1.当特征取值类型较多时,信息增益会越大,容易造成过拟合;2. 只能用于分类;3. 只能处理离散变量;4. 对缺失值敏感 |
| C4.5 | 多叉树;特征只用一次;使用信息增益比对特征值多的特征进行惩罚,减少过拟合;可以处理连续变量;可以处理缺失值 | 处理连续值只是将其离散化,形成多个离散值 |
| CART | 二叉树;特征使用多次;可以用于回归任务 | - |
决策树算法 python 代码实现
创建数据集
def createDataSet(): dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] labels = ['no surfaceing', 'flippers'] return dataSet, labels计算香农熵
# 计算香农熵,分两步,第一步计算频率,第二部根据公式计算香农熵def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} for feaVec in dataSet: currentLabel = feaVec[-1] if currentLabel not in labelCounts: labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key]) / numEntries shannonEnt -= prob * log(prob, 2) return shannonEnt划分数据集
# 划分数据集,将满足X[aixs]==value的值都划分到一起,返回一个划分好的集合(不包括用来划分的aixs属性,因为不需要)def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis + 1:]) retDataSet.append(reducedFeatVec) return retDataSet选择划分的最佳属性
采用多数表决的方式计算结点分类
# 因为我们递归构建决策树是根据属性的消耗进行计算的,所以可能会存在最后属性用完了,但是分类# 还是没有算完,这时候就会采用多数表决的方式计算节点分类def majorityCnt(classList): classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 return max(classCount)基于递归构造决策树
# 基于递归构建决策树。这里的label更多是对于分类特征的名字,为了更好看和后面的理解。def createTree(dataSet, labels): classList = [example[-1] for example in dataSet] if classList.count(classList[0]) == len(classList): # 类别相同则停止划分 return classList[0] if len(dataSet[0]) == 1: # 所有特征已经用完 return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel: {}} del (labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: subLabels = labels[:] # 为了不改变原始列表的内容复制了一下 myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) return myTree调用函数 构造主函数
def main(): data, label = createDataSet() # t1 = time.clock() myTree = createTree(data, label) # t2 = time.clock() print(myTree) # print('execute for ',t2-t1)
if __name__ == '__main__': main()完整源代码
本文源代码参考自 机器学习----决策树 (Decision Tree)算法原理及 python 实现与python 决策树算法原理及基于 numpy 的代码实现
评论
评论加载中…
