Uplift Decision Tree With KL Divergence

Intro

Uplift model 我没找到一个合适的翻译，这方法主要应用是，探究用户在给予一定激励之后的表现，也就是说在电商领域，比如我们给一部分用户发了一些优惠券，那么这些行为是否将“转化”用户呢？是否会起一些积极作用呢？Uplift Model是模拟增量操作对个人行为的影响的。

而在决策树中，我们给一部分样本treatment，而不给另一部分样本treatment，这样相当于每个样本都多了一个属性，也就是是否被给予treatment，利用这一点，我们可以计算给予treatment和未被给予treatment的样本的KL散度，然后每次节点分裂使得KL散度最大化，这样可以使得给予treatment和未被给予treatment的样本距离最远。因此，使用KL散度来做节点分裂距离的思想就是使得分裂前后子节点的平均KL散度增加，而且相对父节点最大增加。

KL-Divergence

KL散度在学习分类问题的交叉熵的时候非常常见，从概率论角度，KL散度的本质是衡量两个分布的距离，从信息论角度，他的本质是使用p分布来编码q所需要的编码长度。

KL散度的数学定义为:
\[ KL(P:Q) = \sum_i p_i log(\frac{p_i}{q_i}) \]

Uplift Decision Tree

首先定义分裂前后treatment和没给treatment的数据的KL散度：

分裂前两者的KL散度为：(其中C表示没给treatment)
\[ KL(P^T(Y):P^C(Y)) = \sum_i p^T(y_i) log\frac{p^T(y_i)}{p^C(y_i)} \]
以A属性作为分裂属性分裂后的条件KL散度：(a代表属性取值，N代表分裂之前总样本数，N(a)是该属性取该值的样本数)
\[ KL((P^T(Y):P^C(Y))|A) = \sum_{a}\frac{N(a)}{N}D(P^T(Y|a):P^C(Y|a)) \]
则最终KL散度的增量为：
\[ KL_{gain} = KL((P^T(Y):P^C(Y))|A) - KL(P^T(Y):P^C(Y)) \]
计算每个属性分裂属性

最终求得最大的作为分裂的标准。

Example

Coding

import numpy as np
import random
class Node():
    def __init__(self):
        self.children = []
        self.value = None
        self.attr = None
        self.attr_values = []
class DecistionTree():
    def __init__(self,dataset,attrs,mode = "Entropy"):
        self.dataset = np.array(dataset)
        self.attrs = attrs
        self.root = Node()
        self.mode = mode
    def predict(self,sample,root):
        attr = root.attr # 属性名
        res = ""
        #print("****start at attribute:{}****".format(attr))
        attr_idx = self.attrs.index(attr) # 这个属性的idx
        flag = False
        if sample[0,attr_idx] in root.attr_values:
            index = root.attr_values.index(sample[0,attr_idx]) # 本节点的属性对应的第几个子节点，也就是子节点index
            value = root.children[index].value
            #print(type(value)) 
            if type(value) is np.str_:
                #print(value)
                res = value    
            else:
                res = self.predict(sample,root.children[index])
            
        return res
    def create_tree(self,dataset,attrs,root):
        label = dataset[:,-1]
        
        if len(set(list(label))) == 1:
            return label[0]
        #if dataset.shape[1] == 2: # 全部遍历完了
        #    return label[0]
        if len(attrs) == 0:
            return label[0]
        idx = self.chooseBestFeatureToSplit(dataset) # feature idx
        myTree = []
        myTree.append(self.attrs[attrs[idx]])
        root.attr = self.attrs[attrs[idx]]
        attrs.remove(attrs[idx])
        
        #root.childen.append(idx)
        values = set(list(dataset[:,idx]))
        
        for value in values:
            sub_dataset = dataset[dataset[:,idx] == value]
            new_node = Node()
            sub_dataset = np.delete(sub_dataset,idx,axis = 1)
            sub_tree = self.create_tree(sub_dataset[:],attrs,new_node)
            #print(sub_tree,type(sub_tree))
            if type(sub_tree) is np.str_:
                
                new_node.value = sub_tree
            root.children.append(new_node)
            root.attr_values.append(value)
                
            myTree.append(sub_tree)
        return root    
        #return myTree
    def train(self,attrs):
        tree = self.create_tree(self.dataset,attrs,self.root)
        #print(tree)
        #print(self.root.attr,self.root.attr_values)
        #print(['age', ['prescript', ['astigmatic', 'nolenses', ['tearRate', 'soft', 'nolenses']], 'nolenses'], 'nolenses', 'nolenses'])
    def random_chosen(self,ratio = 0.5):
        assert ratio < 1 and ratio > 0.1
        idx = np.arange(self.dataset.shape[0]) # 样本个数
        choice = random.choices(idx,k = int(len(idx) * ratio)) # 正样本idx
        converted = np.zeros(shape = (len(idx),))
        converted[choice] = 1
        self.dataset = np.insert(self.dataset,-1,converted,axis = 1)
    @staticmethod
    def KL_divergence(sub_dataset):
        dataset1 = sub_dataset[sub_dataset[:,-2] == '1.0']
        dataset2 = sub_dataset[sub_dataset[:,-2] == '0.0']
        labels = set(list(sub_dataset[:,-1]))
        num_dataset1,num_dataset2 = dataset1.shape[0],dataset2.shape[0]
        res = 0.
        for label in labels:
            
            p = np.mean(dataset1[:,-1] == label)
            q = np.mean(dataset2[:,-1] == label) + 1e-5
            if p >0:
                res += (p* np.log2(p/q))
        return res
    @staticmethod
    def Entropy(dataSet):
        dataSet = np.array(dataSet)
        labels = dataSet[:,-1]
        label_set = list(set(list(labels)))
        num_classes = len(label_set)
        def label_ratio(labels,label):
            return np.mean(labels == label)
        probablities = []
        for label in label_set:
            probablities.append(label_ratio(labels,label))
        res = 0
        for i in range(num_classes):
            p = probablities[i]
            res -= p * np.log2(p)
        return res
    @staticmethod
    def EntropyA(dataSet,idx):
        dataSet = np.array(dataSet)
        values = set(list(dataSet[:,idx]))
        e = 0
        for value in values:
            e = e + np.sum(dataSet[:,idx] == value)
        return e / dataSet.shape[0] 
    def chooseBestFeatureToSplit(self,dataset):
        dataset = np.array(dataset)
        def splitDataSet(dataSet, axis, value):
            dataSet = np.array(dataSet)
            
            dataMat = dataSet[:,:-1]
            attr = dataMat[:,axis]
            
            retDataSet = []
            for val in value:
                retDataSet.append(dataSet[attr == val])
            return retDataSet
        max_s = -1
        max_i = 0
        if self.mode == "Entropy":
            for i in range(dataset.shape[1]-2): # 特征个数
                values = set(list(dataset[:,i]))
                datasets = splitDataSet(dataset,i,values)
                s = self.Entropy(dataset)
                for ds in datasets:
                    s = s - self.Entropy(ds)
                if s > max_s:
                    max_s = s
                    max_i = i    
        elif self.mode == "c4.5":
            for i in range(dataset.shape[1]-2): # 特征个数
                values = set(list(dataset[:,i]))
                
                datasets = splitDataSet(dataset,i,values)
                
                s = self.Entropy(dataset)
                for ds in datasets:
                    s = s - ds.shape[0]/dataset.shape[0] * self.KL_divergence(ds)
                ha = self.EntropyA(dataset,i)
                s = s/ha
                if s > max_s:
                    max_s = s
                    max_i = i
        else:
            for i in range(dataset.shape[1]-2): # 特征个数
                values = set(list(dataset[:,i]))
                
                datasets = splitDataSet(dataset,i,values)
                
                s0 = self.KL_divergence(dataset)
                s1 = 0.
                for ds in datasets:
                    s1 = s1 + ds.shape[0]/dataset.shape[0] * self.KL_divergence(ds)
                if s1 - s0 > max_s:
                    max_s = s1 - s0
                    max_i = i
            
        return max_i
def get_dataset():
    dataSet = []
    with open("/home/xueaoru/下载/decision_tree_glass/lenses.txt","r") as f:
        for line in f:
            l = line.split()
            if len(l) == 6:
                temp = l[:4]
                temp.append(l[4] + l[5])
                dataSet.append(temp)
            else:
                dataSet.append(l)
    return dataSet
def get_random_dataset(n = 100):
    labels = [["young","pre","presbyopic"], 
                ["myope","hyper"],
                ["no","yes"],
                ["reduced","normal"],
                ["nolenses","soft","hard"]
            ]
    #gts = 
    dataSet = []
    for i in range(n):
        dataSet.append([random.choice(labels[i]) for i in range(5)])
    return dataSet
if __name__ == "__main__":
    #dataSet = get_random_dataset(50)
    #dataSet = np.loadtxt("/home/xueaoru/下载/dataset.txt",dtype = np.str)
    
    dataSet = get_dataset()
    #dataSet = np.array(dataSet)
    #print(dataSet)
    #dataSet = np.array(dataSet,dtype = np.str)
    #print(get_dataset())
    #print(dataSet.shape)
    gt_set = list(set(list(np.array(dataSet)[:,-1])))
    attrs = ['s' + str(i) for i in range(4)]
    #attrs = ['age','prescript','astigmatic','tearRate']
    ds = DecistionTree(dataSet,attrs,mode = "KL")
    ds.random_chosen()
    ds.train(list(range(len(attrs))))
    
    ds2 = DecistionTree(dataSet,attrs,mode = "Entropy")
    ds2.random_chosen()
    ds2.train(list(range(len(attrs))))
    ds3 = DecistionTree(dataSet,attrs,mode = "C4.5")
    ds3.random_chosen()
    ds3.train(list(range(len(attrs))))
    correct = 0
    id3_correct = 0
    c45_correct = 0
    random_correct = 0
    for i in range(len(dataSet)):
        gt = np.array(dataSet)[i,-1]
        sample = np.array(dataSet)[i,:-1]
        sample = np.reshape(sample,(1,-1))
        if gt == ds2.predict(sample,ds.root):
            id3_correct += 1
        if gt == ds3.predict(sample,ds.root):
            c45_correct += 1
        if gt == ds.predict(sample,ds.root):
            correct += 1
        r = random.choice(gt_set)
        if gt == r:
            random_correct += 1
        #print(gt,ds.predict(sample,ds.root))
    print("random_choice: {}, ID3: {} ,C4.5: {}, KL_divergence: {}".format(random_correct*1.0/len(dataSet),
                                                                            id3_correct*1.0/len(dataSet),
                                                                            c45_correct*1.0/len(dataSet),
                                                                            correct*1.0/len(dataSet)))
    #tree = createTree(dataSet,list(range(len(labels))))