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

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180428A1SDCS00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券