1、信息熵
信息论中的信息量和信息熵。
信息量：
信息量是对信息的度量，就跟温度的度量是摄氏度一样，信息的大小跟随机事件的概率有关。
例如：在哈尔滨的冬天，一条消息说：哈尔滨明天温度30摄氏度，这个事件肯定会引起轰动，因为它发生的概率很小（信息量大）。日过是夏天，“明天温度30摄氏度”可能没有人觉得是一个新闻，因为夏天温度30摄氏度太正常了，概率太大了（信息点太小了）
从这个例子中可以看出一个随机事件的信息量的大小与其发生概率是成反相关的。
香农定义的一个事件的信息信息量为：I(X) = log2(1/p)其中p为事件X发生的概率
信息熵：Entropy
一个随机变量 X可以代表n个随机事件，对应的随机变为X=xi,
那么熵的定义就是 X的加权信息量。
H(x) =p(x1)I(x1)+...+p(xn)I(x1)
=p(x1)log2(1/p(x1)) +.....+p(xn)log2(1/p(xn))
=-p(x1)log2(p(x1)) - ........-p(xn)log2(p(xn))
其中p(xi)代表xi发生的概率
例如有32个足球队比赛，每一个队的实力相当，那么每一个对胜出的概率都是1/32
那么 要猜对哪个足球队胜出 非常困难，
这个时候的熵H(x) = 32 *(1/32)log(1/(1/32)) = 5
熵也可以作为一个系统的混乱程度的标准
试想如果32个队中有一个是ac米兰，另外31个对是北邮计算机1班队，2班，...31班
那么几乎只有一个可能ac米兰胜利的概率是100%，其他的都是0%，这个系统的熵
就是 1*log(1/1) = 0. 这个系统其实是有序的，熵很小，而前面熵为5系统处于无序状态。
2、基尼不纯度
基尼不纯度的大概意思是 一个随机事件变成它的对立事件的概率
例如 一个随机事件X，P(X=0) = 0.5 ,P(X=1)=0.5
那么基尼不纯度就为 P(X=0)*(1 - P(X=0)) + P(X=1)*(1- P(X=1)) = 0.5
一个随机事件Y，P(Y=0) = 0.1 ,P(Y=1)=0.9
那么基尼不纯度就为P(Y=0)*(1 - P(Y=0)) + P(Y=1)*(1 -P(Y=1)) = 0.18
很明显 X比Y更混乱，因为两个都为0.5很难判断哪个发生。而Y就确定得多，Y=0发生的概率很大。而基尼不纯度也就越小。
所以基尼不纯度也可以作为 衡量系统混乱程度的 标准
-、什么是决策树？
决策树就是一棵树（这里用二叉树来表示）
例如下面这个图就是一个两个人是否匹配的决策树
每一个训练sample格式为(gender,age,location)
对于每一个输入例如
(男，10，北京)
（女，30，成都）
遍历这棵树 都能得到结果
二、怎么建立这棵树？
我们训练样本如下，（最后一行是结果）
(男，10，北京，match)
(女，35，成都, match）
(女，10，北京，match)
(女，60，上海, notmatch）
(男，10，北京，match)
(女，30，南京,notmatch）
(男，70，北京，match)
(女，20，成都,notmatch）
按照怎样的原则来分呢？
如图所示：
如果我用年龄来分，分成两个集合
大于30的 集合
(女，60，上海, not match）
(男，70，北京，match)
(女，35，成都, match）
小于30 的集合
..........................
大于30的集合 的结果又有（match ，match,notmatch)
小于30的结核的结果是：（match ，match,match,notmatch)
对于大于30的集合，match的概率是 2/3, not match的概率是1/3
对于小于30的集合，match的概率是 3/4, not match的概率是1/4
我们可以分别计算两个子集的熵或者基尼不纯度。
如果分开之前的集合的熵为h
例如 集合1的熵是 h1,集合2的熵是h2，
集合1的权值是3/7, 集合2是4/7
那么分为集合1和集合2之后的熵是 h_later = h1*3/7 +h2*4/7
我们可以遍历每一个 参数的每一个值 取 h-h_later最大的那个feature的那个值作为 标准 将这个set分为两个set
递归地按照这个原则来建立一个二叉树（决策树）
三、overfitting 过度拟合问题。
决策树可能变得对训练集合拟合得非常好，但是对于测试集合表现非常差，这可能就是overfitting了，我们需要对建立好的决策树进行剪枝.剪掉一些 分得太细的枝条，比如一个枝条，他分为两个分支，其实分为两个分支以后的熵并没有减小多少。这样的分支我们就可以不用再分了，将他们合并为一个叶子节点
例如Entropy（A) - (Entropy(B) +Entropy(C))/2 很小，就可以将其合并为一个叶子节点，如图
四、处理数据不全。
决策树对处理数据不全也很容易，有时候某些feature的数据我们搜集不到怎么处理呢？
例如我们 在节点A这个地方的属性没有数据，怎么办呢? 我们可以加权两个分支，也就是 B 和C的结果，然后再返回。
这是正常的分类函数
obervation就是输入的数据 ['(direct)','USA','yes',5]
result就是结果比如：（{"notmatch":2}，{"match":1})
# observation =['(direct)','USA','yes',5]
defclassify(observation,tree):
if tree.results != None:
returntree.results
else :
v =observation[tree.col]
branch =None
ifisinstance(v,int) or isinstance(v,float):
if v >tree.value: branch = tree.tb
else : branch =tree.fb
else:
if v == tree.value: branch =tree.tb
else :branch =tree.fb
returnclassify(observation,branch)
这是处理有确实数据的分类函数
# observation =['(direct)','USA','yes',5]
# deal with the missing featurewhen classifying a observation
defmdclassify(observation,tree):
if tree.results != None:
returntree.results
else :
v =observation[tree.col]
# deal with missing feature
ifv==None:
tr,fr =mdclassify(observation,tree.tb),mdclassify(observation,tree.fb)
tcount =sum(tr.values())
fcount =sum(fr.values())
# true weight,and falseweight
tw =float(tcount)/(fcount+tcount)
fw = float(fcount)/(fcount+tcount)
result = {}
for k,v in tr.items():result[k]=v*tw
for k,v in fr.items():result[k]=v*tw
return result
else:
branch = None
if isinstance(v,int) orisinstance(v,float):
if v > tree.value: branch =tree.tb
else : branch = tree.fb()
else :
if v == tree.value: branch =tree.tb
else :branch = tree.fb
returnmdclassify(observation,branch)
五、处理数值类型的输出，用方差来替代熵和基尼不纯度
上面的输出都是 那么 match，not match，等等离散的输出，如果是 1,2,3.4,100.222等数值的输出呢？使用我们的熵和基尼不纯度就不行了，我们在建立决策树的就需要使用其他的标准了。可以使用方差来代替