数据挖掘领域十大经典算法之—C4.5算法（超详细附代码）

男娘i 2022-05-30 05:52 393阅读 0赞

> **相关文章：**
> 
>  *  **[数据挖掘领域十大经典算法之—K-Means算法（超详细附代码）][K-Means]**
>  *  **[数据挖掘领域十大经典算法之—SVM算法（超详细附代码）][SVM]**
>  *  **[数据挖掘领域十大经典算法之—Apriori算法][Apriori]**
>  *  **[数据挖掘领域十大经典算法之—EM算法][EM]**
>  *  **[数据挖掘领域十大经典算法之—PageRank算法][PageRank]**
>  *  **[数据挖掘领域十大经典算法之—AdaBoost算法（超详细附代码）][AdaBoost]**
>  *  **[数据挖掘领域十大经典算法之—K-邻近算法/kNN（超详细附代码）][K-_kNN]**
>  *  **[数据挖掘领域十大经典算法之—朴素贝叶斯算法（超详细附代码）][Link 1]**
>  *  **[数据挖掘领域十大经典算法之—CART算法（超详细附代码）][CART]**

数据挖掘十大经典算法如下：  
![这里写链接内容][551d7bffg80cbb284ca7f_690]

### 简介 ###

C4.5是决策树算法的一种。决策树算法作为一种分类算法，目标就是将具有p维特征的n个样本分到c个类别中去。常见的决策树算法有ID3,C4.5,CART。

### 基本思想 ###

下面以一个例子来详细说明C4.5的基本思想  
![例子][Center]  
上述数据集有四个属性，属性集合A=\{ 天气，温度，湿度，风速\}， 类别标签有两个，类别集合L=\{进行，取消\}。

**1. 计算类别信息熵**  
类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。  
![这里写链接内容][Center 1]

**2. 计算每个属性的信息熵**  
每个属性的信息熵相当于一种条件熵。他表示的是在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越大，表示这个属性中拥有的样本类别越不“纯”。  
![这里写链接内容][Center 2]

**3. 计算信息增益**  
信息增益的 = 熵 - 条件熵，在这里就是 类别信息熵 - 属性信息熵，它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性，当然，选择该属性就可以更快更好地完成我们的分类目标。

信息增益就是ID3算法的特征选择指标。  
![这里写链接内容][Center 3]  
但是我们假设这样的情况，每个属性中每种类别都只有一个样本，那这样属性信息熵就等于零，根据信息增益就无法选择出有效分类特征。所以，C4.5选择使用信息增益率对ID3进行改进。

**4.计算属性分裂信息度量**  
用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益 / 内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它），这样算是对单纯用信息增益有所补偿。  
![这里写链接内容][Center 4]

**5. 计算信息增益率**  
（下面写错了。。应该是IGR = Gain / H ）  
![这里写链接内容][Center 5]

天气的信息增益率最高，选择天气为分裂属性。发现分裂了之后，天气是“阴”的条件下，类别是”纯“的，所以把它定义为叶子节点，选择不“纯”的结点继续分裂。  
![这里写链接内容][Center 6]

在子结点当中重复过程1~5。  
至此，这个数据集上C4.5的计算过程就算完成了，一棵树也构建出来了。

总结**算法流程**为：

while (当前节点”不纯“)  
    	(1)计算当前节点的类别信息熵Info(D) （以类别取值计算）  
    	(2)计算当前节点各个属性的信息熵Info(Ai) （以属性取值下的类别取值计算）  
    	(3)计算各个属性的信息增益Gain(Ai)=Info(D)-Info(Ai)  
    	(4)计算各个属性的分类信息度量H(Ai) （以属性取值计算）  
    	(5)计算各个属性的信息增益率IGR(Ai)=Gain(Ai)/H(Ai)  
    end while  
    当前节点设置为叶子节点

### 优缺点 ###

#### 优点 ####

产生的分类规则易于理解，准确率较高。

#### 缺点 ####

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

### 代码 ###

代码已在[github][]上实现，这里也贴出来

# encoding=utf-8
    
    import cv2
    import time
    import numpy as np
    import pandas as pd
    
    
    from sklearn.cross_validation import train_test_split
    from sklearn.metrics import accuracy_score
    
    # 二值化
    def binaryzation(img):
        cv_img = img.astype(np.uint8)
        cv2.threshold(cv_img,50,1,cv2.THRESH_BINARY_INV,cv_img)
        return cv_img
    
    def binaryzation_features(trainset):
        features = []
    
        for img in trainset:
            img = np.reshape(img,(28,28))
            cv_img = img.astype(np.uint8)
    
            img_b = binaryzation(cv_img)
            # hog_feature = np.transpose(hog_feature)
            features.append(img_b)
    
        features = np.array(features)
        features = np.reshape(features,(-1,feature_len))
    
        return features
    
    
    class Tree(object):
        def __init__(self,node_type,Class = None, feature = None):
            self.node_type = node_type  # 节点类型（internal或leaf）
            self.dict = { } # dict的键表示特征Ag的可能值ai，值表示根据ai得到的子树 
            self.Class = Class  # 叶节点表示的类，若是内部节点则为none
            self.feature = feature # 表示当前的树即将由第feature个特征划分（即第feature特征是使得当前树中信息增益最大的特征）
    
        def add_tree(self,key,tree):
            self.dict[key] = tree
    
        def predict(self,features): 
            if self.node_type == 'leaf' or (features[self.feature] not in self.dict):
                return self.Class
    
            tree = self.dict.get(features[self.feature])
            return tree.predict(features)
    
    # 计算数据集x的经验熵H(x)
    def calc_ent(x):
        x_value_list = set([x[i] for i in range(x.shape[0])])
        ent = 0.0
        for x_value in x_value_list:
            p = float(x[x == x_value].shape[0]) / x.shape[0]
            logp = np.log2(p)
            ent -= p * logp
    
        return ent
    
    # 计算条件熵H(y/x)
    def calc_condition_ent(x, y):
        x_value_list = set([x[i] for i in range(x.shape[0])])
        ent = 0.0
        for x_value in x_value_list:
            sub_y = y[x == x_value]
            temp_ent = calc_ent(sub_y)
            ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_ent
    
        return ent
    
    # 计算信息增益
    def calc_ent_grap(x,y):
        base_ent = calc_ent(y)
        condition_ent = calc_condition_ent(x, y)
        ent_grap = base_ent - condition_ent
    
        return ent_grap
    
    # C4.5算法
    def recurse_train(train_set,train_label,features):
        
        LEAF = 'leaf'
        INTERNAL = 'internal'
    
        # 步骤1——如果训练集train_set中的所有实例都属于同一类Ck
        label_set = set(train_label)
        if len(label_set) == 1:
            return Tree(LEAF,Class = label_set.pop())
    
        # 步骤2——如果特征集features为空
        class_len = [(i,len(list(filter(lambda x:x==i,train_label)))) for i in range(class_num)] # 计算每一个类出现的个数
        (max_class,max_len) = max(class_len,key = lambda x:x[1])
        
        if len(features) == 0:
            return Tree(LEAF,Class = max_class)
    
        # 步骤3——计算信息增益,并选择信息增益最大的特征
        max_feature = 0
        max_gda = 0
        D = train_label
        for feature in features:
            # print(type(train_set))
            A = np.array(train_set[:,feature].flat) # 选择训练集中的第feature列（即第feature个特征）
            gda = calc_ent_grap(A,D)
            if calc_ent(A) != 0:  ####### 计算信息增益比，这是与ID3算法唯一的不同
                gda /= calc_ent(A)
            if gda > max_gda:
                max_gda,max_feature = gda,feature
    
        # 步骤4——信息增益小于阈值
        if max_gda < epsilon:
            return Tree(LEAF,Class = max_class)
    
        # 步骤5——构建非空子集
        sub_features = list(filter(lambda x:x!=max_feature,features))
        tree = Tree(INTERNAL,feature=max_feature)
    
        max_feature_col = np.array(train_set[:,max_feature].flat)
        feature_value_list = set([max_feature_col[i] for i in range(max_feature_col.shape[0])]) # 保存信息增益最大的特征可能的取值 (shape[0]表示计算行数)
        for feature_value in feature_value_list:
    
            index = []
            for i in range(len(train_label)):
                if train_set[i][max_feature] == feature_value:
                    index.append(i)
    
            sub_train_set = train_set[index]
            sub_train_label = train_label[index]
    
            sub_tree = recurse_train(sub_train_set,sub_train_label,sub_features)
            tree.add_tree(feature_value,sub_tree)
    
        return tree
    
    def train(train_set,train_label,features):
        return recurse_train(train_set,train_label,features)
    
    def predict(test_set,tree):
        result = []
        for features in test_set:
            tmp_predict = tree.predict(features)
            result.append(tmp_predict)
        return np.array(result)
    
    
    class_num = 10  # MINST数据集有10种labels，分别是“0,1,2,3,4,5,6,7,8,9”
    feature_len = 784  # MINST数据集每个image有28*28=784个特征（pixels）
    epsilon = 0.001  # 设定阈值
    
    if __name__ == '__main__':
    
        print("Start read data...")
    
        time_1 = time.time()
    
        raw_data = pd.read_csv('../data/train.csv', header=0)  # 读取csv数据
        data = raw_data.values
        
        imgs = data[::, 1::]
        features = binaryzation_features(imgs) # 图片二值化(很重要，不然预测准确率很低)
        labels = data[::, 0]
    
        # 避免过拟合，采用交叉验证，随机选取33%数据作为测试集，剩余为训练集
        train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
        time_2 = time.time()
        print('read data cost %f seconds' % (time_2 - time_1))
    
        # 通过C4.5算法生成决策树
        print('Start training...')
        tree = train(train_features,train_labels,list(range(feature_len)))
        time_3 = time.time()
        print('training cost %f seconds' % (time_3 - time_2))
    
        print('Start predicting...')
        test_predict = predict(test_features,tree)
        time_4 = time.time()
        print('predicting cost %f seconds' % (time_4 - time_3))
        
        # print("预测的结果为：")
        # print(test_predict)
        for i in range(len(test_predict)):
            if test_predict[i] == None:
                test_predict[i] = epsilon
        score = accuracy_score(test_labels, test_predict)
        print("The accruacy score is %f" % score)

测试数据集为MNIST数据集，获取地址为[train.csv][]

### 运行结果 ###

![这里写链接内容][C45_result.png]

[K-Means]: http://blog.csdn.net/fuqiuai/article/details/79458331
[SVM]: http://blog.csdn.net/fuqiuai/article/details/79483057
[Apriori]: http://blog.csdn.net/fuqiuai/article/details/79484998
[EM]: http://blog.csdn.net/fuqiuai/article/details/79484421
[PageRank]: http://blog.csdn.net/fuqiuai/article/details/79484929
[AdaBoost]: http://blog.csdn.net/fuqiuai/article/details/79482487
[K-_kNN]: http://blog.csdn.net/fuqiuai/article/details/79458648
[Link 1]: http://blog.csdn.net/fuqiuai/article/details/79458943
[CART]: http://blog.csdn.net/fuqiuai/article/details/79469412
[551d7bffg80cbb284ca7f_690]: /images/20220530/9cce014b08244223b6b03cc33f68b3ca.png
[Center]: /images/20220530/ffcd5a9ac6d146aca0ba3f93aff49145.png
[Center 1]: /images/20220530/3fec90a57fdd4108b159e7c574666647.png
[Center 2]: /images/20220530/388d5301770e4b9ea17c916d72c81850.png
[Center 3]: /images/20220530/e0f5b6cdf090426db1cc448425630b3b.png
[Center 4]: /images/20220530/94ee322c5148437a95d8cc24ce205f4f.png
[Center 5]: /images/20220530/4de3d09879f44e1cb3e843e887a764fe.png
[Center 6]: /images/20220530/9f11a2ee6e1043c6811137cdc41423ef.png
[github]: https://github.com/fuqiuai/lihang_algorithms/blob/master/decision_tree/C45.py
[train.csv]: https://github.com/fuqiuai/lihang_algorithms/blob/master/data/train.csv
[C45_result.png]: /images/20220530/d151b7170d6b490784b12cd05c1447a5.png