机器学习-决策树与基于ID3算法的python决策树实现

决策树顾名思义,就相当于我们平常所画的那种逻辑树形图,帮助我们一步步判断。举个例子:


我们已经知道6位女生对经济和长相和最终结果(约会还是回家)的态度,那么现在来了一个男生他的条件是经济rich,长相ugly。

我们可以看到数据集(1,2行)两位女生的态度都不相同,一位拜金女表示愿意约会,另一位外貌协会表示不约。那么这种情况怎么办呢?我们可以看第三行,有一位女生在经济rich的情况下选择了约会,那么也就是说虽然前两位女生引起了冲突,但第三位女生虽然没有完全对rich和ugly的态度表态,但她对rich,cool的男生表示了愿意约会,也就是说她对rich的男生表示愿意约会的可能性也是比较大的,相当于给了rich,ugly这个男生信心。但第五位女士又对ugly表示要回家,那到底这个男生能不能约到女生呢?

如何用数学度量这种情况呢?对于一个普适的情况而言,女生是先考虑经济,还是长相呢?决策树帮我们处理了这一类问题

决策树划分算法有非常多,这里我们拿ID3算法举例。


ID3算法主要从信息增益来考量:

信息增益公式如下,S代表没划分,A表示特征,等式右边第一个项表示没划分前的信息熵,第二个代表根据属性A划分后的信息熵


对于特征的信息熵的计算公式如下,我们假定特征A有k个属性,比如我们上述例子,经济有poor和rich两个属性,那么k=2

|Si|/|S|表示某个属性占多少,例如rich有3个,一共6个,那么Si=3,S=6。Entropy(Si)则是计算在这个属性的样本中信息熵的大小。


信息熵计算公式如下,pi表示某个label占比,继续拿上述例子举例,我们假定现在已经在rich的条件下了,那么p1表示home个数/date个数  p1 = 1/3,p2 = 2/3


我们拿上述例子来实际计算下第一个划分点:


最终经济的信息增益熵高于长相,因此我们第一划分点为经济。

如此循环判断直到划分完所有属性或者不必再继续划分


下面是我写的一个python的id3具体实现

实现的算法如下

'''

基于id3算法的决策树模型

def 创建决策树

    if 所有样本都是一个类别:

            创建叶节点

    elif 没有属性可以划分:

            选择样本标签多的作为节点值(如果label数量一样,随便选择)

    else:

            计算信息增益,选择分裂特征

            根据分裂特征将样本分离

            将已选特征从特征集中删除

            for 每个样本集

                    递归生成决策树

'''


项目地址:https://github.com/ccyzml/my_ml_models/blob/master/decision_tree.py

最终的运行结果如下

画成决策树就是这个样子

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

推荐阅读更多精彩内容

  • 该文章为转载文章,作者简介:汪剑,现在在出门问问负责推荐与个性化。曾在微软雅虎工作,从事过搜索和推荐相关工作。 T...
    名字真的不重要阅读 5,185评论 0 3
  • 记得早先年少时大家诚诚恳恳说一句 是一句请早上 火车站长街黑暗无行人卖豆浆的小店冒着热气从前的日色变得慢车,马,邮...
    中麦麦阅读 293评论 0 0
  • 不奋斗,你的才华如何配上你的任性; 不奋斗,你的脚步如何赶上父母老去的速度; 不奋斗,世界那么大,你靠什么去看看;...
    欣赏66阅读 203评论 0 1
  • 【原文】韩公叔有齐、魏,而太子有楚、秦以争国。郑申为楚使于韩,矫以新城、阳人予太子。楚王怒,将罪之。对曰:“臣矫予...
    眉间山川阅读 527评论 0 3
  • 望子成龙、望女成凤可以说不但是每个家庭的愿望,而且也是每个国家和民族的愿望,所以当下社会空前的重视教育,但...
    淮河里的一条小鲤鱼阅读 651评论 1 5