+/IBCS
git clone https://git.julia.blue/+/IBCS
c6bf06e
master
1''' 2Created on Oct 12, 2010 3Decision Tree Source Code for Machine Learning in Action Ch. 3 4@author: Peter Harrington 5''' 6from math import log 7import operator 8 9 10def createDataSet (): 11dataSet = [[1 ,1 ,'yes' ], [1 ,1 ,'yes' ], [1 ,0 ,'no' ], [0 ,1 ,'no' ], 12 [0 ,1 ,'no' ]] 13labels = ['no surfacing' ,'flippers' ] 14# change to discrete values 15return dataSet ,labels 16 17 18def calcShannonEnt (dataSet ): 19numEntries = len (dataSet ) 20labelCounts = {} 21for featVec in dataSet :# the number of unique elements and their occurance 22currentLabel = featVec [- 1 ] 23if currentLabel not in labelCounts .keys (): 24labelCounts [currentLabel ]= 0 25labelCounts [currentLabel ]+= 1 26shannonEnt = 0.0 27for key in labelCounts : 28prob = float (labelCounts [key ])/ numEntries 29shannonEnt -= prob * log (prob ,2 )#log base 2 30return shannonEnt 31 32 33def splitDataSet (dataSet ,axis ,value ): 34retDataSet = [] 35for featVec in dataSet : 36if featVec [axis ]== value : 37reducedFeatVec = featVec [:axis ]#chop out axis used for splitting 38reducedFeatVec .extend (featVec [axis + 1 :]) 39retDataSet .append (reducedFeatVec ) 40return retDataSet 41 42 43def chooseBestFeatureToSplit (dataSet ): 44numFeatures = len (dataSet [0 ])- 1 #the last column is used for the labels 45baseEntropy = calcShannonEnt (dataSet ) 46bestInfoGain = 0.0 47bestFeature = - 1 48for i in range (numFeatures ):#iterate over all the features 49featList = [example [i ]for example in dataSet 50 ]#create a list of all the examples of this feature 51uniqueVals = set (featList )#get a set of unique values 52newEntropy = 0.0 53for value in uniqueVals : 54subDataSet = splitDataSet (dataSet ,i ,value ) 55prob = len (subDataSet )/ float (len (dataSet )) 56newEntropy += prob * calcShannonEnt (subDataSet ) 57infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy 58i ,newEntropy 59if (infoGain > bestInfoGain ):#compare this to the best gain so far 60bestInfoGain = infoGain #if better than current best, set to best 61bestFeature = i 62"\n\n\n" 63return bestFeature #returns an integer 64 65 66def majorityCnt (classList ): 67classCount = {} 68for vote in classList : 69if vote not in classCount .keys (): 70classCount [vote ]= 0 71classCount [vote ]+= 1 72sortedClassCount = sorted ( 73classCount .iteritems (),key = operator .itemgetter (1 ),reverse = True ) 74return sortedClassCount [0 ][0 ] 75 76 77def createTree (dataSet ,labels ): 78classList = [example [- 1 ]for example in dataSet ] 79if classList .count (classList [0 ])== len (classList ): 80return classList [0 ]#stop splitting when all of the classes are equal 81if len (dataSet [0 ] 82 )== 1 :#stop splitting when there are no more features in dataSet 83return majorityCnt (classList ) 84bestFeat = chooseBestFeatureToSplit (dataSet ) 85bestFeatLabel = labels [bestFeat ] 86myTree = {bestFeatLabel : {}} 87del (labels [bestFeat ]) 88featValues = [example [bestFeat ]for example in dataSet ] 89uniqueVals = set (featValues ) 90for value in uniqueVals : 91subLabels = labels [:]#copy all of labels, so trees don't mess up existing labels 92myTree [bestFeatLabel ][value ]= createTree ( 93splitDataSet (dataSet ,bestFeat ,value ),subLabels ) 94return myTree 95 96 97def classify (inputTree ,featLabels ,testVec ): 98firstStr = inputTree .keys ()[0 ] 99secondDict = inputTree [firstStr ] 100featIndex = featLabels .index (firstStr ) 101key = testVec [featIndex ] 102valueOfFeat = secondDict [key ] 103if isinstance (valueOfFeat ,dict ): 104classLabel = classify (valueOfFeat ,featLabels ,testVec ) 105else : 106classLabel = valueOfFeat 107return classLabel 108 109 110def storeTree (inputTree ,filename ): 111import pickle 112fw = open (filename ,'w' ) 113pickle .dump (inputTree ,fw ) 114fw .close () 115 116 117def grabTree (filename ): 118import pickle 119fr = open (filename ) 120return pickle .load (fr )