# ID3决策树的生成算法

## ID3算法

在决策树各个结点上应该信息增益准则选择特征，递归地构建决策树

### 输入

训练数据集D\
特征集A\
阈值$$\epsilon$$

### 输出

决策树T

### 过程

1. 若D中所有实例属于同一类$$C\_k$$，则T为单结点树，并将类$$C\_k$$作为该结点的类标记，返回T  
2. 若$$A=\emptyset$$，则T为单结点，并将D中实例数最大的类$$C\_k$$作为该结点的类标记，返回T  

   *决策树的深度每增加一层，这一层结点的特征就少一个，到了第n层的结点就没有任凭特征用于分类了。但此时结点的数据的标记可能仍不属于同一类。*  
3. 否则，按[信息增益的算法](https://windmising.gitbook.io/lihang-tongjixuexifangfa/decisiontree/2)计算A中各个特征对D的信息增益，选择信息特征最大的Ag  
4. 如果Ag的信息增益小于阈值$$\epsilon$$，则置T为单结点树，并将D中实例数最大的类$$C\_k$$作为该结点的类标记，返回T

   *阈值*$$\epsilon$$*是为了防止过拟合*  
5. 否则，对Ag的每一个可能的值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类标记，构建子结点，由结点及其子结点构成树T，返回T  
6. 对第i个子结点，以Di为训练集，以A-{Ag}为特征集，递归地调用步（1）-步（5），得到子树Ti，返回Ti  

   *A-{Ag}表示两个集合相减*  

   *训练集Di中不包含特征Ag*  

## 代码

```python
def multi(y):
    ySet = set(y)
    bestCount = 0
    for yi in ySet:
        count = y.count(yi)
        if count > bestCount:
            bestCount = count
            bestyi = yi
    return bestyi

def ID3(X, y, epsilon):
    # 若D中所有实例属于同一类
    if len(set(y))==1:
        # 将类$$C_k$$作为该结点的类标记
        return y[0]
    # 若$$A=\emptyset$$
    if X.shape[1] == 0:
        # 实例数最大的类$$C_k$$作为该结点的类标记
        return multi(y)
    bestInfo = 0
    # 计算A中各个特征对D的信息增益
    for feature in range(X.shape[1]):
        info = svm(X, y, feature)
        # 选择信息特征最大的Ag
        if svm(X, y, feature) > bestInfo:
            bestInfo = info
            bestfeature = feature
    # 如果Ag的信息增益小于阈值$$\epsilon$$
    if bestInfo < epsilon:
        # 将D中实例数最大的类$$C_k$$作为该结点的类标记
        return multi(y)
    feature = bestfeature
    ret = {'feature':feature}
    # 对Ag的每一个可能的值ai
    a = set(X[:, feature])
    for ai in a:
        yai = y[X[:,feature] == ai]
        Xai = X[X[:,feature] == ai]
        ret[ai] = ID3(Xai, yai, epsilon)
    return ret
```