from math import log #海洋生物数据,x1为不浮出水面是否可以生存,x2为是否有脚蹼,y为是否属于鱼类 def createDataSet(): dataSet = [[1, 1, ‘yes‘], [1, 1, ‘yes‘], [1, 0, ‘no‘], [0, 1, ‘no‘], [0, 1, ‘no‘]] labels = [‘no surfacing‘,‘flippers‘] return dataSet, labels #计算给定数据集的熵 def calcShannonEnt(dataSet): #计算数据集中实例的总数 numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: #将y取出 currentLabel = featVec[-1] #创建一个数据字典,它的键值是最后一列的数值,如果当前键值不存在,则将当前键值加入字典 if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 #每个键值都记录了当前类别出现的次数 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: #计算所有类标签发生的概率,本例:yes:2/5,no:3/5 prob = float(labelCounts[key])/numEntries #计算信息熵 shannonEnt -= prob * log(prob,2) #log base 2 return shannonEnt #调用 #调用函数createDataSet() myDat,labels = createDataSet() print(‘构建的数组:‘,myDat) print(‘x的名称分别为:‘,labels) #调用函数calcShannonEnt(dataSet) p = calcShannonEnt(myDat) print(‘构建的数组中y的熵:‘,p) #p为熵,y中混合的数据种类越多,熵越大,下面测试这一论断 myDat[0][-1] = ‘maybe‘ print(‘对y增加一个种类,修改第一个y:‘,myDat) p = calcShannonEnt(myDat) print(‘对y增加一个种类,发现y的熵变大了:‘,p) #恢复原样 myDat[0][-1] = ‘yes‘ print(‘将数组恢复原样:‘,myDat) print(‘………………‘) #划分数据集,使用了三个参数:待划分的数据集,划分数据集的特征,需要返回的特征的值 def splitDataSet(dataSet, axis, value): #创建新的列表 retDataSet = [] #遍历待划分的数据集 for featVec in dataSet: #如果满足待划分数据集中的某个值等于需要返回的值的条件 if featVec[axis] == value: #将待划分的数据集分成两部分 reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet #调用,取第0个位置等于1的元素,不包括1本身 s1 = splitDataSet(myDat, 0, 1) print(‘取第0个位置等于1的元素,不包括1本身:‘,s1) #调用,取第0个位置等于0的元素,不包括0本身 s2 = splitDataSet(myDat, 0, 0) print(‘取第0个位置等于0的元素,不包括0本身‘,s2) print(‘………………‘) #选择最好的数据集划分方式 def chooseBestFeatureToSplit(dataSet): #取x的种类数(columns数量) numFeatures = len(dataSet[0]) - 1 #计算整个数据集的原始熵 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1 #迭代所有x的column for i in range(numFeatures): #将当前列取出 featList = [example[i] for example in dataSet] #将当前列去重 uniqueVals = set(featList) newEntropy = 0.0 #迭代去重后的当前列 for value in uniqueVals: #取当前列等于value的值的元素,不包括value值本身 subDataSet = splitDataSet(dataSet, i, value) #当前列等于value的值的概率 prob = len(subDataSet)/float(len(dataSet)) #计算所有特征值的熵之和 newEntropy += prob * calcShannonEnt(subDataSet) #判断信息增益,取信息增益最大的那个索引值 infoGain = baseEntropy - newEntropy if (infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature #调用 #返回信息增益最大的那个索引值 best_x_index = chooseBestFeatureToSplit(myDat) print(‘信息增益最大的那个索引值为:‘,best_x_index) print(‘………………‘) #返回出现次数最多的分类名称 import operator def majorityCnt(classList): classCount={} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 #每个键值都记录了当前类别出现的次数 classCount[vote] += 1 #表示为对classCount中第1维的元素进行降序排序 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] #创建树,两个输入参数:数据集合标签列表 def createTree(dataSet,labels): #取y值 classList = [example[-1] for example in dataSet] #代码第一个停止条件是类标签完全相同,count()函数是统计某元素出现的次数,该例为统计y中第一个数出现的次数 if classList.count(classList[0]) == len(classList): return classList[0] #如果只有一个y的column,则返回y中出现次数最多的类别 if len(dataSet[0]) == 1: return majorityCnt(classList) #开始创建树 #返回信息增益最大的那个索引值 bestFeat = chooseBestFeatureToSplit(dataSet) #返回信息增益最大的列名称 bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel:{}} del(labels[bestFeat]) #将信息增益最大的那列放到featValues中 featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: #复制所有标签,使树不会弄乱所有标签 subLabels = labels[:] #运用递归,直到类标签完全相同或只有一个y的column为止 myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) return myTree #调用 myTree = createTree(myDat,labels) print(‘将递归过程展现出来:‘,myTree)
结果:
构建的数组: [[1, 1, ‘yes‘], [1, 1, ‘yes‘], [1, 0, ‘no‘], [0, 1, ‘no‘], [0, 1, ‘no‘]] x的名称分别为: [‘no surfacing‘, ‘flippers‘] 构建的数组中y的熵: 0.9709505944546686 对y增加一个种类,修改第一个y: [[1, 1, ‘maybe‘], [1, 1, ‘yes‘], [1, 0, ‘no‘], [0, 1, ‘no‘], [0, 1, ‘no‘]] 对y增加一个种类,发现y的熵变大了: 1.3709505944546687 将数组恢复原样: [[1, 1, ‘yes‘], [1, 1, ‘yes‘], [1, 0, ‘no‘], [0, 1, ‘no‘], [0, 1, ‘no‘]] ……………… 取第0个位置等于1的元素,不包括1本身: [[1, ‘yes‘], [1, ‘yes‘], [0, ‘no‘]] 取第0个位置等于0的元素,不包括0本身 [[1, ‘no‘], [1, ‘no‘]] ……………… 信息增益最大的那个索引值为: 0 ……………… 将递归过程展现出来: {‘no surfacing‘: {0: ‘no‘, 1: {‘flippers‘: {0: ‘no‘, 1: ‘yes‘}}}}
原文:https://www.cnblogs.com/xiao02fang/p/12680537.html