+/IBCS

git clone https://git.julia.blue/+/IBCS

Joseph Ryanadd final projectc6bf06e

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