## 方式二 # # 统计标签出现的次数 # label_count = Counter(data[-1] for data in dataSet) # # 计算概率 # probs = [p[1] / len(dataSet) for p in label_count.items()] # # 计算香农熵 # shannonEnt = sum([-p * log(p, 2) for p in probs]) # #
return shannonEnt
def majorityCnt(classList): # 选择出现次数最多的一个结果 classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] +=1 # 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # print('sortedClassCount:', sortedClassCount) return sortedClassCount[0][0]
# 选择切分数据集的最佳特征 def chooseBestFeatureToSplit(dataSet): # 求第一行有多少列的 Feature, 最后一列是label列嘛 numFeatures = len(dataSet[0]) - 1 # label的信息熵 baseEntropy = calcShannonEnt(dataSet) # 最优的信息增益值, 和最优的Featurn编号 bestInfoGain, bestFeature = 0.0, -1 # iterate over all the features for i in range(numFeatures): # create a list of all the examples of this feature # 获取每一个实例的第i+1个feature，组成list集合 featList = [example[i] for example in dataSet] # get a set of unique values # 获取剔重后的集合，使用set对list数据进行去重 uniqueVals = set(featList) # 创建一个临时的信息熵 newEntropy = 0.0 # 遍历某一列的value集合，计算该列的信息熵 # 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet)/float(len(dataSet)) newEntropy += prob * calcShannonEnt(subDataSet) # gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值 # 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。 infoGain = baseEntropy - newEntropy print('infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy) if (infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature
# 创建决策树 def createTree(dataset, lables): classList = [example[-1] for example in dataset] # 如果数据集只有一种则直接返回 # if classList.count(classList[0]) == len(classList): return classList[0] # ?使用完了所有特征 依旧还有未包含的数据集 if len(dataset[0]) == 1: return majorityCnt(classList)
# 选择最优的列，得到最优列对应的label含义 bestFeat = chooseBestFeatureToSplit(dataSet) # 获取label的名称 bestFeatLabel = labels[bestFeat] # 初始化myTree myTree = {bestFeatLabel: {\}\} # hexo的bug 双大括号 会异常 需转义 # 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改 # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list del(labels[bestFeat]) # 取出最优列，然后它的branch做分类 featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: # 求出剩余的标签label subLabels = labels[:] # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree() myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) # print('myTree', value, myTree) return myTree
