一个经典的例子是猜人游戏。参与游戏的一方默想一个人名,另一方向他提问题,最终猜出这个人名。 决策树属于监督学习,可以处理上面的分类问题。这个问题的特点是:
决策树算法是找到一个优化的决策路径(决策树),使得每次分类尽可能过滤更多的数据,或者说问的问题尽量少。 决策树算法可以用来优化一些知识系统,帮助用户快速找到答案。
这里,要解决的问题是采用哪些数据属性作为分类条件,最佳次序是什么?
H(X) = \sum\limits_{i=1}^n P(x_i)I(x_i) = - \sum\limits_{i=1}^n P(x_i)\log_2 P(x_i) \\ where \\ \qquad H(X) : 数据集合X的信息熵值。 \\ \qquad X : 数据集合X。 \\ \qquad x_i : 数据集合X的标签的一个枚举值。 \\ \qquad I(x_i) :x_i的资讯量 (information self). I(x_i) = -ln(P(x_i)) \\ \qquad P(x_i) : 发生x_i的概率。x的机率质量函数(probability mass function)。 P(x_i) = count(x_i)/len(X).
H(F, X) = \sum\limits_{i=1}^n P(f_i)H(X_fi) \\ where \\ \qquad H(F, X) : 数据集合X在属性F上的信息熵值。 \\ \qquad F : Feature F。 \\ \qquad X : 数据集合X。 \\ \qquad f_i : Feature F的一个枚举值。 \\ \qquad H(X_fi) :集合X_fi的信息熵。 \\ \qquad X_fi :数据集合X中属性F为f_i的子集。 \\ \qquad P(f_i) : 发生f_i的概率。f_i的机率质量函数(probability mass function)。 P(f_i) = count(f_i)/len(X).
'no surfacing'和'flippers'是数据的属性名。 0, 1是标称数据。 'yes', 'no'是决策结果。
\text{(jsonTree) createTree(dateset)} = \\ \{ \\ \qquad \text{if (the value of the dateset labels are same)} \\ \qquad \{ \\ \qquad \qquad return\ dataset.lables[0] \\ \qquad \} \\ \qquad \\ \qquad \text{if (dataset.features.length = 1)} \\ \qquad \{ \\ \qquad \qquad return\ mostAppeard(dataset.lables) \\ \qquad \} \\ \qquad \\ \qquad feature = findBestFeature(dateset) \\ \qquad jsonTree = \{feature.label:\{\}\} \\ \qquad \textstyle {foreach}_\text{value}^\text{feature.values} \\ \qquad \{ \\ \qquad \qquad jsonTree[feature.label][value] = createTree(dateset.subset(feature, value)) \\ \qquad \} \\ \} * findBestFeature
\text{(feature) findBestFeature(dateset)} = \\ \{ \\ \qquad baseFeatureEntroy = infinite \\ \qquad \text{foreach}_\text{current_feature}^\text{dataset.features} \\ \qquad \{ \\ \qquad \qquad featureEntroy = calculateFeatureEntroy(dateset, feature) \\ \qquad \qquad \text{if (featureEntroy < baseFeatureEntroy)} \\ \qquad \qquad \{ \\ \qquad \qquad \qquad baseFeatureEntroy = featureEntroy \\ \qquad \qquad \qquad feature = current_feature \\ \qquad \qquad \} \\ \qquad \} \\ \}
见原书。
见原书。
决策树对数据质量要求比较高。那猜人名的游戏来说,需要收集大量的人名和人名对应的数据。
参考: