自动化规则挖掘（-）-基于决策树规则挖掘

嗨，周末愉快。

最近在做自动化规则挖掘的脚本，本篇文章主要介绍基于递归dfs的方式对sklearn 中决策树的规则进行提取，并生成sql脚本。

一、 决策树简单介绍

上图就是一颗决策树，决策树是具有树状结构的二叉树，它是由根节点、叶子节点、非叶子节点及分支组成。

决策树在优化过程中有3个经典算法，分别为ID3（信息增益），C4.5（增益率），CART（基尼系数）。本篇文章主要介绍对决策树规则的提取，故决策树算法不做仔细介绍。

二、 一个简单的决策树案例

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import export_text
iris = load_iris()
X = iris['data']
y = iris['target']
decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2)
decision_tree = decision_tree.fit(X, y)
r = export_text(decision_tree, feature_names=iris['feature_names'])
print(r)
out：
|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal width (cm) <= 1.75
|   |   |--- class: 1
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2

画树

dot_data = tree.export_graphviz(decision_tree,feature_names=iris['feature_names']) 
graph = graphviz.Source(dot_data )  
graph   

三、基于递归的方式对决策树生成的规则进行提取

深度优先优搜索（DFS）：是一种搜索算法。它是沿着一条路径一直找到最深的那个节点，当没有子节点的时候，返回上一级节点，寻找其另外的子节点，继续向下遍历，没有就向上返回一级，直到所有的节点都被遍历到，每个节点只能访问一次。比如对于BST（二叉搜索树）的先序遍历、中序遍历和后序遍历。

1. 一个小例子

上图中的遍历结果为[1,2,4,8,#,#,9,#,#,5,10,#,##,3,6,#,#,7,#,#]

在算法实现的过程中，我们可以采用递归和非递归两种方式进行实现。 递归：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 保存结果
        res = []
        
        def traversal(root: TreeNode):
            if root == None:
                return
            res.append(root.val) # 前序
            traversal(root.left)    # 左
            traversal(root.right)   # 右

        traversal(root)
        return res

非递归采用栈来保存

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            res.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return res

下来我们来看一下怎么将我们决策树的规则提取出来

def get_dt_rules(clf, feature_names,OverallBadrate:float):
    '''
    Author: yuqing 873237045@qq.com
    Date: 2022-11-06 15:35:15
    LastEditors: yuqing 873237045@qq.com
    LastEditTime: 2022-11-06 15:35:55
    FilePath: \规则开发\决策树规则开发.py
    Description: 
    '''
    tree_ = clf.tree_
    left = clf.tree_.children_left
    right = clf.tree_.children_right
    feature_name = [feature_names[i] if i != -2 else "undefined!" for i in tree_.feature]
    rules=dict()

    global res_df
    res_df = pd.DataFrame()
    def recurse(node, depth, parent): # 搜每个节点的规则

        if tree_.feature[node] != -2:  # 非叶子节点,搜索每个节点的规则
            name = feature_name[node]
            thd = np.round(tree_.threshold[node],3)
            s= "{} <= {} ".format( name, thd, node )
            # 左子
            if node == 0:
                rules[node]=s
            else:
                rules[node]=rules[parent]+' & ' +s
            recurse(left[node], depth + 1, node)
            s="{} > {}".format(name, thd)
            # 右子 
            if node == 0:
                rules[node]=s
            else:
                rules[node]=rules[parent]+' & ' +s
            recurse(right[node], depth + 1, node)
        else:
            df = pd.DataFrame()
            df['rule'] = rules[parent],
            df['good_cnt'] = tree_.value[node][0][0].astype(int)
            df['bad_cnt'] = tree_.value[node][0][1].astype(int)
            df['cnt'] = df['good_cnt']+ df['bad_cnt']
            df['bad_rate'] = df['bad_cnt']/df['cnt'] 
            df['Lift'] = df['bad_rate'] / OverallBadrate
        
            global res_df
            res_df = pd.concat([res_df,df],0)
    recurse(0, 1, 0)
    return res_df.reset_index().drop('index',1)

结果如下：