决策树
决策树是常用的分类算法之一,其对于探索式的知识发现往往有较好的表现。决策树原理十分简单,可处理大维度的数据,不用预先对模型的特征有所了解,这些特性使得决策树被广泛使用。决策树采用贪心算法,其建立过程同样需要训练数据。决策树算法有ID3、在ID3基础上发展起来的C4.5,以及C4.5的商业化版本C5.0,C5.0核心与C4.5相同,只是在执行效率和内存使用方面有所改进。
决策树的核心问题是决策树分支准则的确定,以及分裂点的确定。为了直观起见,推荐大家玩一个游戏:通过20个问题来猜出你心中所想的那个人。
初次接触这个游戏的你是否觉得十分神奇,在20个不到的问题里真的就能猜出你心中所想的那个人,不论是你的女朋友、父母或者动漫人物、歌手、演员甚至是政界人物。其实仔细想想,一个20层的二叉树最后的叶子节点有多少个?1024*1024个,而我们能想到的人绝对是超不出这个数量的。这个网站的具体算法就是采用的类似决策树的算法,通过一个个问题来减少候选的数据,直至找出你所想的那个人。
多玩几次你就会发现,一般第一个或前几个问题就会问你:你描述的对象是男(女)性吗?这意味着什么,意味着第一个问题就能将候选数据减少一半左右。因为你想的那个人,除了男人就是女人了。这就是前面所说的决策树分支准则的确定。若将这个问题放在最后几个问题中,毫无疑问是个吃力不讨好的事情。那么如何才能将这些众多属性(如:性别、高矮、胖瘦、头发长短、是否是歌手、是否有money等)按照其重要程度来排个顺序,这就是ID3和C4.5算法所做的事情了。
预备知识
信息熵是信息论中的基本概念。信息论是C.E.Shannon于1948年提出并由此发展起来的,主要用于解决信息传递过程中的问题,也称为统计通信理论。信息论认为:信息是用来消除随机不确定性的,信息量的大小可由所消除的不确定大小来计量。详细了解。
信息量的数学定义为:
\(I(u_i)=-log_2P(u_i)\)
其中 \(P(u_i)\) 为信息 \(u_i\) 发生的概率。信息熵是信息量的数学期望,是信源发出信息前的平均不确定性,也成为先验熵,信息熵的数学定义为:
\(Ent(U)=-\sum_iP(u_i)log_2P(u_i)\)
当已知信号 \(U\) 的概率分布 \(P(U)\) 且收到信号 \(V=v_i\) 后,发出信号的概率分布变为 \(P(U|v_j)\) ,于是信源的平均不确定性变为(也称为条件熵):
\(Ent(U|v_i)=-\sum_iP(u_i|v_i)log_2P(u_i|v_i)\)
一般来说, \(Ent(U|v_i) < Ent(U)\) ,于是定义信息增益为:
\(Gains(U,V)=Ent(U)-Ent(U|V)\)