AI机器学习-决策树-Python实现ID3算法

信息熵的python算法实现，本文根据网上的资料进行了如下整理：

1. 修改了一些方法的变量，使更容易理解（至少个人认为更容易理解）

2. 添加了更多的注释

3. 对代码进行本地调试，验证可行性

4. 对代码进行拆分讲解

下面我们开始做详细说明：

1. 引入依赖包

决策树算法需要用到下面的包，在文件的开头引入

frommathimportlog

importtime

importos

2. 构件数据集

通过python的二维列表创建一个简单的测试数据集。

输入参数filename是用来做外部数据导入的，如果没有传入此参数，返回代码hard code出来的数据集。

defcreateDataSet(filename=""):

dataSet = [[1, 1,'yes'],

[1, 1,'yes'],

[1, 0,'no'],

[0, 1,'no'],

[0, 1,'no']]

labels = ['长的帅','有钱','见不见']

iffilename!=""andos.path.exists(filename):

print("fileexits")

dataSet,labels = loadData(filename)

returndataSet, labels

3. 计算香农熵

下面是计算香农熵的函数，函数中做了大量注释，方便大家学习代码。

# 计算香农熵，输入数据集

defcalcShannonEnt(dataSet):

#获取数据集的长度

numEntries = len(dataSet)

#定义结果统计对象

resultCounts = {}

#遍历数据集

fordataItemindataSet:

#获取当前结果值

currentResult = dataItem[-1]

#统计结果值个数，如果没有在集合中，统计值为0，否则+1

ifcurrentResultnot inresultCounts:

resultCounts[currentResult] = 0

resultCounts[currentResult] += 1

#定义信息熵

shannonEnt = 0.0

#遍历结果统计集，计算信息熵

forkeyinresultCounts:

#计算某个结果所占的比率

prob = float(resultCounts[key]) / numEntries

#计算熵

shannonEnt -= prob * log(prob, 2)

returnshannonEnt

4. 计算条件熵

此方法用来计算基于某一列的条件熵，代码也加了注释。

#计算以某属性列为选择标准的条件熵

#输入数据集dataSet,列索引columnIndex

defcalcAttrEnt(dataSet,columnIndex):

# 获取第i列的数组信息

columnValues = [example[columnIndex]forexampleindataSet]

# 获取此列的无重复的属性特征值

distinctColumnValues = set(columnValues)

attrEntropy = 0.0

fordistinctColumnValueindistinctColumnValues:

subDataSet = splitDataSet(dataSet, columnIndex, distinctColumnValue)

prob = len(subDataSet) / float(len(dataSet))

attrEntropy += prob * calcShannonEnt(subDataSet)

returnattrEntropy

其中用到一个获取属性子集的方法：

#获取按某个特定属性的特定值划分的子集（不包含当前列）

# 输入数据集合dataSet，数据列索引index，在columIndex这一列上的不重复的某个值

defsplitDataSet(dataSet, columnIndex, distinctColumnValue):

#定义按columnIndex列上取值为distinctColumnValue的子集

subDataSet = []

foritemindataSet:

ifitem[columnIndex] == distinctColumnValue: #只筛选值为distinctValue的数据

reducedFeatVec = item[:columnIndex] #取当前列之前的所有数据

reducedFeatVec.extend(item[columnIndex + 1:]) #取当前列之后的所有数据

subDataSet.append(reducedFeatVec) #在subDataSet中追加此行数据

returnsubDataSet

5. 使用ID3算法做特征选择

下面的方法使用ID3算法选择最佳的决策分支属性

#用ID3算法，通过信息增益做特征选择

defchooseBestFeatureToSplit(dataSet):

numFeatures = len(dataSet[0]) - 1 # 获取数据集列数，因为要从0开始所以减1

shannonEntropy = calcShannonEnt(dataSet) #计算熵值

bestInfoGain = 0.0

bestFeature = -1

#从0开始遍历数据集列

forcolumnIndexinrange(numFeatures):

attrEntropy = calcAttrEnt(dataSet,columnIndex)

infoGain = shannonEntropy - attrEntropy

ifinfoGain > bestInfoGain:

bestInfoGain = infoGain

bestFeature = columnIndex

returnbestFeature

6. 构件决策树

#通过递归调用创建决策树

defcreateTree(dataSet, labels):

#获取数据集结果列的数据组成列表

resultList = [example[-1]forexampleindataSet]

ifresultList.count(resultList[0]) == len(resultList): # 列表中的结果集的值相同则直接返回结果值

returnresultList[0]

print("dataSet:"+ str(dataSet))

print("dataSet[0]:"+ str(dataSet[0]))

iflen(dataSet[0]) == 1: #遍历完所有的特征时，仍然不能将数据集划分成仅包含唯一类别的分组 dataSet

returnmajorityCnt(resultList) #由于无法简单的返回唯一的类标签，这里就返回出现次数最多的类别作为返回值

bestFeatColumnIndex = chooseBestFeatureToSplit(dataSet) #获取最佳分支属性列索引

bestFeatLabel = labels[bestFeatColumnIndex] #获取最佳分支属性列名称

myTree = } #初始化myTree树根

del(labels[bestFeatColumnIndex]) #把已分配的列名称删除,因为递归调用createTree的时候splitDataSet方法会把当前列去除

featValues = [example[bestFeatColumnIndex]forexampleindataSet] #取出最佳分支列整列的数据组成一个列表

uniqueVals = set(featValues) #把列数据去重，得到此属性的所有可能的不重复取值

forbestFeatColumnUniqueValinuniqueVals:

subLabels = labels[:] # 为了不改变原始列表的内容复制了一下

#递归调用构建决策树

myTree[bestFeatLabel][bestFeatColumnUniqueVal] = createTree(splitDataSet(dataSet,

bestFeatColumnIndex, bestFeatColumnUniqueVal), subLabels)

returnmyTree

关注微信公众号“挨踢学霸”，获取更多技术好文