【数据挖掘】决策树之CART (Classification and Regression Trees)分类与回归树

 #!/usr/bin/python

    
 my_data=[['slashdot','USA','yes',18,'None'],
    
     ['google','France','yes',23,'Premium'],
    
     ['digg','USA','yes',24,'Basic'],
    
     ['kiwitobes','France','yes',23,'Basic'],
    
     ['google','UK','no',21,'Premium'],
    
     ['(direct)','New Zealand','no',12,'None'],
    
     ['(direct)','UK','no',21,'Basic'],
    
     ['google','USA','no',24,'Premium'],
    
     ['slashdot','France','yes',19,'None'],
    
     ['digg','USA','no',18,'None'],
    
     ['google','UK','no',18,'None'],
    
     ['kiwitobes','UK','no',19,'None'],
    
     ['digg','New Zealand','yes',12,'Basic'],
    
     ['slashdot','UK','no',21,'None'],
    
     ['google','UK','yes',18,'Basic'],
    
     ['kiwitobes','France','yes',19,'Basic']]

 class decisionnode:#决策树节点结构

    
   def __init__(self,col=-1,value=None,results=None,tb=None,fb=None):
    
     self.col=col#被测试规则索引
    
     self.value=value#要被测试的值
    
     self.results=results#测试结果
    
     #tb,fb是决策树节点，tb为true时的节点，fb为false的节点
    
     self.tb=tb
    
     self.fb=fb

 #训练决策树：CART (Classification and Regression Trees)分类与回归树

    
 #1）建立根节点
    
 #2）遍历表中所有数据，选择最好的变量划分数据
    
 def devideset(rows,column,value):#column为栏位在row的索引，value为此栏位的值
    
     split_function=None
    
     if isinstance(value,int) or isinstance(value,float):
    
     split_function=lambda row:row[column]>=value
    
     else:
    
     split_function=lambda row:row[column]==value
    
     #根据split_function划分    
    
     set1=[row for row in rows if split_function(row)]
    
     set2=[row for row in rows if not split_function(row)]
    
     return (set1,set2)

 #没row中最后一个栏位的个数

    
 def uniquecount(rows):
    
     result={}
    
     for row in rows:
    
     r = row[len(row) - 1]
    
     if r not in result: result[r]=0
    
     results[r]+=1
    
     return result
    
 #整个rows随机放置item到错误category中的可能性
    
 def giniimpurity(rows):
    
     total = len(rows)
    
     counts=uniquecount(rows)
    
     imp=0
    
     for k1 in counts:
    
     #计算k1放到错误category中的可能性 
    
     p1=float(counts[k1])/total
    
     for k2 in counts:
    
         if k1==k2:continue
    
         p2=float(counts[k2])/total
    
         imp+=p1*p2
    
     return imp
    
 #sum(p(x)*log2(p(x)))  
    
 def entropy(rows):
    
     from math import log
    
     log2=lambda x:log(x)/log(2)
    
     results=uniquecounts(rows)
    
     ent=0.0
    
     for r in results.keys():
    
     p=float(results[r])/len(rows)
    
     ent+=p*log2(p)        
    
     return ent

 #递归构建决策树

    
 def buildtree(rows,scoref=entropy):
    
     if len(rows)==0:return decisionnode()
    
     current_score=scoref(rows)
    
     #设置变量，跟踪最好的规则
    
     best_gain=0
    
     best_criteria=None
    
     best_sets=None
    
     #record的栏 item数
    
     column_count=len(row[0])-1
    
     for col in range(0,column_count):
    
     #生成
    
     column_values={}
    
     for row in rows:
    
         column_values[row[col]]=1
    
     #尝试为rows中的每个记录的第col个field划分set    
    
     for value in column_values.keys():
    
          #划分后的set
    
         (set1,set2)=devideset(rows,col,value)
    
         #划分后的长度比例
    
         p=float(len(set1))/len(rows)
    
         #权重得分
    
         gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
    
         #找到了最好的规则
    
         if gain>best_gain and len(set1)>0 and len(set2)>0:
    
             best_gain=gain
    
             best_criteria=(col,value)
    
             best_sets=(set1,set2)
    
     #取最好的规则，并对划分后的子集合进行递归构建决策树            
    
     if best_gain>0:
    
     trueBranch=buildtree(best_sets[0])
    
     falseBranch=buildtree(best_sets[1])
    
     return decisionnode(col=best_criteria[0],value=best_criteria[1],
    
                         tb=trueBranch,fb=falseBranch)
    
     else:
    
     return decisionnode(results=uniquecounts(rows))

 #利用决策树来对observation进行归类

    
 def classify(observation,tree):
    
     if tree.results != None:
    
     return tree.results
    
     v = observation[tree.col]
    
     branch = None
    
     #查找分支，此处算法与划分set规则一致
    
     if isinstance(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        
    
     return classify(observation,brance)