即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

机器学习和进阶-决策树 ID3算法

编程语言 Snow_Me 19℃ 0评论

今天用了一晚上把决策树的ID3算法撸出来了。

首先推荐一发博客,说的感觉挺靠谱的…传送门


一、信息熵

高中化学里面有个概念讲的是分子的混乱程度(大概是这个…)。而信息熵就是香农借鉴了热力学的概念,将信息熵定义为“离散随机事件出现的概率”。

加入对于随机变量X={xi},每个xi的概率为pi,那么信息熵可以定义为:







二、信息增益

对于一个数据集S来说,其信息熵为Entropy(S)。对其中的一个特征T来说,这个特征中含有不同的特征值,那么在数据集S中的特征T的信息熵




其中,ti表示特征T的一个特征值的集合,集合仅含该特征和结果,H(ti)表示在ti数据集下的信息熵,P(ti)表示这个集合占T这个集合的大小。

所以信息增益IG(S|T) = Entropy(S)-Entropy(S|T)




三、决策树之ID3算法

ID3算法是一种很贪心的策略。每次找到信息增益最大的特征,以此建立一层。再用剩余的特征去建立剩下的树。




四、Python实现代码

# -*- encoding=utf-8 -*-

import math

from enum import Enum

Outlook = Enum('Outlook', ('sunny', 'overcast', 'rain'))
Temperature = Enum('Temperature', ('hot', 'mild', 'cool'))
Humidity = Enum('Humidity', ('high', 'normal'))

train_set = (
 (Outlook.sunny, Temperature.hot, Humidity.high, False, False),
 (Outlook.sunny, Temperature.hot, Humidity.high, True, False),
 (Outlook.overcast, Temperature.hot, Humidity.high, False, True),
 (Outlook.rain, Temperature.mild, Humidity.high, False, True),
 (Outlook.rain, Temperature.cool, Humidity.normal, False, True),
 (Outlook.rain, Temperature.cool, Humidity.normal, True, False),
 (Outlook.overcast, Temperature.cool, Humidity.normal, True, True),
 (Outlook.sunny, Temperature.mild, Humidity.high, False, False),
 (Outlook.sunny, Temperature.cool, Humidity.normal, False, True),
 (Outlook.rain, Temperature.mild, Humidity.normal, False, True),
 (Outlook.sunny, Temperature.mild, Humidity.normal, True, True),
 (Outlook.overcast, Temperature.mild, Humidity.high, True, True),
 (Outlook.overcast, Temperature.hot, Humidity.normal, False, True),
 (Outlook.rain, Temperature.mild, Humidity.high, True, False),
 )


def entropy(c):
 ans, cas, total = 0, {}, len(c)
 for x in c:
  if x not in cas:
   cas[x] = 1
  else:
   cas[x] += 1
 for x in cas:
  tmp = cas[x] / total
  ans += tmp * math.log2(tmp)
 return -ans


def cal_imformation_gain(t):
 '''
 t: 特征集合,有两列,第一列是属性,第二列是结果
 return: 在特征属性T下的条件熵
 '''
 # 将t分解成多个小集合
 st = set()
 for row in t:
  if row[0] not in st:
   st.add(row[0])
 mp = {x : [] for x in st}
 for row in t:
  mp[row[0]].append(row[1])

 # 计算每个集合单独的信息熵
 ans = 0
 for key in mp:
  ans += len(mp[key]) / len(t) * entropy(mp[key])
 return entropy([x[1] for x in t]) - ans


def build_decision_tree(train_set):
 len_train_set = len(train_set[0])
 tmp = set()
 for x in train_set:
  tmp.add(x[len_train_set-1])
 if len(tmp) == 1:
  return "Yes" if tmp.pop() == True else "No"
 if len_train_set == 1:
  tmp = set()
  for x in train_set:
   tmp.add(x[0])
  if len(tmp) == 1:
   return "Yes" if train_set[0][0] == True else "No"
  else:
   return [True, False]


 # 获取最大的信息增益
 mx, inx = 0, 0
 for i in range(len_train_set - 1):
  tmp = cal_imformation_gain([[x[i], x[len_train_set-1]] for x in train_set])
  if tmp > mx:
   mx, inx = tmp, i
 # 递归构造决策树
 tree = {}
 for x in train_set:
  tree[x[inx]] = {}
 for key in tree:
  new_train_set = []
  for x in train_set:
   if x[inx] == key:
    tmp = []
    for i in range(len_train_set):
     if i == inx:
      continue
     tmp.append(x[i])
    new_train_set.append(tmp)
  tree[key] = build_decision_tree(new_train_set)
 return tree


if __name__ == "__main__":
 tree = build_decision_tree(train_set)
 print (tree)





这篇博客写的很挫…刚入门机器学习…如有问题…还请各位dalao指出!




转载请注明:CodingBlog » 机器学习和进阶-决策树 ID3算法

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情