Machine Learning in Action:Decision Tree

概述

决策树这个算法比较接地气,就算你根本不懂机器学习算法也可以很好的理解决策树,决策树之前的算法就已经解释过了。主要思想就算通过条件进行分类即可。决策树主要的优点就在于数据形式非常好理解。decision tree的算法可以读取数据集合,可以得到数据中所隐含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取一系列规则。优点很明显,计算复杂度不高,输出结果也很容易理解,就算是中间有缺失值也影响不大,特征不相关也可以处理。由于决策树是按照条件划分,如果划分的条件过多了,可能导致overfitting。
首先要做的就是要找到数据的决定性特征是什么,把它作为划分的依据。当划分完成,如果当前的叶子都是同一个类别,那么当前叶子的划分就完成了。

决策树一般的划分流程
收集数据
准备数据,不同的判别条件方法可能会导致有不同的结果
分析数据,归一化预处理等等
训练数据,最后树的结构
测试数据,做validation
使用算法解决问题,基本步骤和KNN的差不多一样。

信息增益

划分数据的原则的,划分完了,数据一定要更加有序。组织杂乱无章数据的一种方法就是使用信息熵,也就是信息论的度量方法,在划分了数据时候信息发生的变化称为信息增益,信息增益最高的特征就是最好的选择。
l(x_i) = -log_2^{p(x_i)}其中p(x_i)为是该分类的概率,为了计算熵,我们需要计算所有类别所有可能包含是信息期望值:H = - \sum_{i=1}^np(x_i)log_2^{p(x_i)}


    def calculateShan(self, dataSet):
        labelFraction = {}
        if len(dataSet) == 0:
            return 0
        for data in dataSet:
            label = data[-1]
            if label not in labelFraction.keys():
                labelFraction[label] = 1
            else:
                labelFraction[label] += 1
        Ent = 0.0
        alldata = len(dataSet)
        for key in labelFraction:
            prob = float(labelFraction[key]) / alldata
            Ent -= prob * math.log(prob, 2)
        return Ent

找到最好的区分特征:


    def choosetheBestFeature(self, dataset):
        feature_num = dataset.shape[1] - 1
        bestEntDiff = 0.0
        BestFeature = -1
        Bestvalue = -1
        baseEnt = self.calculateShan(dataset)
        aSet = None
        bSet = None
        for i in range(feature_num):
            for value in dataset[:, i]:
                A, B = self.split_data(dataset, i, value)
                proA = len(A) / len(dataset)
                proB = 1 - proA
                infoEnt = proA * self.calculateShan(A) + proB * self.calculateShan(B)
                if baseEnt - infoEnt > bestEntDiff:
                    bestEntDiff = baseEnt - infoEnt
                    BestFeature = i
                    Bestvalue = value
                    aSet = A
                    bSet = B
        return BestFeature, Bestvalue, np.array(aSet), np.array(bSet)

递归构建一颗树

    def __build_tree(self, dataSet):
        if dataSet is None:
            return None
        elif len(dataSet) < 3:
            label_class = {}
            for data in dataSet:
                label = data[-1]
                if label not in label_class:
                    label_class[label] = 1
                else:
                    label_class[label] += 1
            sorted(label_class.items(), key=lambda label_class: label_class[1], reverse=True)
            key = list(label_class)[0]
            return nodes(result=key)
        node = nodes()
        nodes.result = None
        feature, value, A, B = self.choosetheBestFeature(dataSet)
        if value != -1 and feature != -1:
            node.value = value
            node.fea = feature
            node.left = self.__build_tree(A)
            node.right = self.__build_tree(B)
        else:
            label_class = {}
            for data in dataSet:
                label = data[-1]
                if label not in label_class:
                    label_class[label] = 1
                else:
                    label_class[label] += 1
            sorted(label_class.items(), key=lambda label_class: label_class[1], reverse=True)
            key = list(label_class)[0]
            node.result = key
        return node


在构建算法中也发现了,构建一棵树是需要很长时间的,这里还好,是寻找存在的特征,如果是寻找一些连续型的特征,比如用gini系数,那么是要找到当前特征的最大最小值,然后按照步长加上去一个一个找,类似addboost一样,所以时间复杂度不低的。即使是处理很小的数据集,也是很耗时的任务。为了节省时间,可以用Python模块pickle序列化对象,序列化可以在磁盘上保存,需要就读出来,任何对象都可以序列化,字典也不例外。
开始处理数据的时候,先要测量数据的不一致性,然后用最优的方案划分数据集,直到数据集里面所有的数据都属于同一类。
这只是其中一种决策树,比较流行的还有C4.5和CART。

所有代码https://github.com/GreenArrow2017/MachineLeariningnAction/tree/master/DecisionTree

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,014评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,796评论 3 386
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,484评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,830评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,946评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,114评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,182评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,927评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,369评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,678评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,832评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,533评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,166评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,885评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,128评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,659评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,738评论 2 351

推荐阅读更多精彩内容

  •   决策树(Decision Tree)是一种基本的分类与回归方法,其模型呈树状结构,在分类问题中,表示基于特征对...
    殉道者之花火阅读 4,521评论 2 2
  • 决策树理论在决策树理论中,有这样一句话,“用较少的东西,照样可以做很好的事情。越是小的决策树,越优于大的决策树”。...
    制杖灶灶阅读 5,843评论 0 25
  • 一.朴素贝叶斯 1.分类理论 朴素贝叶斯是一种基于贝叶斯定理和特征条件独立性假设的多分类的机器学习方法,所...
    wlj1107阅读 3,078评论 0 5
  • 一、决策树应用体验 分类   从上面可以看出,决策树对分类具有线性回归无可比拟的优势, 如果对未参与训练的数据集是...
    杨强AT南京阅读 1,244评论 1 3
  • 我们经常会听到一些鸡汤,关于坚持。 成功的路上并不拥挤,因为坚持的人不多;不要因为没有没有掌声而放弃梦...
    知守先森阅读 193评论 2 1