©2020-2024 ioDraw All rights reserved
决策树ID3算法实现
问题背景：
天气逐渐炎热，有一天你家邻居买了个西瓜回来邀请你一起吃，但是在吃之前他想知道这个瓜到底甜不甜。恰巧你学习了决策树模型，可以利用网上的数据来建立决策树模型，再来帮他预测一下这个瓜到底甜不甜。已知他买的瓜如下（乌黑，蜷缩，沉闷，清晰，凹陷，硬滑）
网上的数据如下：
编号色泽根蒂敲声纹理脐部触感好瓜
1青绿蜷缩浊响清晰凹陷硬滑是
2乌黑蜷缩沉闷清晰凹陷硬滑是
3乌黑蜷缩浊响清晰凹陷硬滑是
4青绿蜷缩沉闷清晰凹陷硬滑是
5浅白蜷缩浊响清晰凹陷硬滑是
6青绿稍蜷浊响清晰稍凹软粘是
7乌黑稍蜷浊响稍糊稍凹软粘是
8乌黑稍蜷浊响清晰稍凹硬滑是
9乌黑稍蜷沉闷稍糊稍凹硬滑否
10青绿硬挺清脆清晰平坦软粘否
11浅白硬挺清脆模糊平坦硬滑否
12浅白蜷缩浊响模糊平坦软粘否
13青绿稍蜷浊响稍糊凹陷硬滑否
14浅白稍蜷沉闷稍糊凹陷硬滑否
15乌黑稍蜷浊响清晰稍凹软粘否
16浅白蜷缩浊响模糊平坦硬滑否
17青绿蜷缩沉闷稍糊稍凹硬滑否
解题过程：
知识回顾：
在生成决策树模型之前，我们需要先理解好什么是决策树？决策树是用来干什么的？怎样生成决策树？
* 决策树：一种类似于流程图的树结构，其中每个内部节点（非叶节点）表示在一个属性上的测试。，每个分支代表该测试的一个输出，每个叶节点存放一个类标号。
*
用途：决策树通过把实例从根节点排列到某个叶子节点来对实例分类，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。
* 生成：采用自顶向下的增长树的贪婪算法（ID3算法）来生成决策树。
而ID3算法的构造过程也就是围绕“哪一个属性作为根节点”展开的，将分类能力最好的属性挑选出来被作为根节点，然后产生其他支，并把训练样例排列到适当的分支，一直向下，不考虑之前的选择。此外我们需要了解如下几个概念：
信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量成为信息熵，是指每个符号所含信息量的统计平均值。
* 信息熵（Entropy）：
* 属性剩余价值（Remainder）：
* 信息熵（Gain）：
我们先来理解一下这几个概念，信息熵也就是对信源所含的信息求和，类似于化学中的熵，信息论中熵也体现着熵越大越不确定性，所以说对于我们来说是跟希望熵越小越好，这样我们的准确性会越高。然后我们需要对每个属性对信息的价值进行评估，因此我们定义出了属性剩余价值（也是一种熵）。属性剩余价值是挑选A属性之后剩下的熵，因此我们想知道这个A属性到底帮助我们消除了多少熵（也就是不确定性），也就是信息增益，也就是信息熵与属性剩余价值的差值。显然越大越好，我们选取最大的作为根节点，紧接着我们在子集上继续划分，直至分配完所有属性到适当的分支。
详细实现：
决策树构造伪代码：
# ==============================================
# 输入：
# 数据集
# 输出：
# 构造好的决策树(也即训练集)
# ==============================================
def 创建决策树:
'创建决策树'
if (数据集中所有样本分类一致):
创建携带类标签的叶子节点
else:
寻找划分数据集的最好特征
根据最好特征划分数据集
for 每个划分的数据集:
创建决策子树(递归方式)
数据集获取：
采用手动输入的方式将西瓜特征写进数据集dataSet，和标签lables，封装成函数，返回数据集和标签这两个列表。
def createDataSet():
"""
创建测试的数据集
:return:
"""
dataSet = [
# 1
['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
# 2
['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
# 3
['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
# 4
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
# 5
['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
# 6
['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
# 7
['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
# 8
['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
# ----------------------------------------------------
# 9
['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
# 10
['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
# 11
['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
# 12
['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
# 13
['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
# 14
['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
# 15
['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
# 16
['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
# 17
['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
]
# 特征值列表
labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']
return dataSet, labels
数据集划分：
数据有了，但是我们根据属性来分类的时候会有不同的属性值，也就产生了不同的子集（新的分支）。新的分支是按照前一步的属性值分类汇总的，且要除去上一步的属性。也就是：我们假设纹理是根节点，但是按照纹理划分有清晰、稍糊、模糊三种属性值，也就产生了向下的三个分支，按照清晰、稍糊、模糊分别汇总，但是新的分支数据集中不应再包含纹理这个属性。
def splitDataSet(dataSet, axis, value):
"""
按照给定的特征值，将数据集划分
:param dataSet: 数据集
:param axis: 给定特征值的坐标
:param value: 给定特征值满足的条件，只有给定特征值等于这个value的时候才会返回
:return:
"""
# 创建一个新的列表，防止对原来的列表进行修改
retDataSet = []
# 遍历整个数据集
for featVec in dataSet:
# 如果给定特征值等于想要的特征值
if featVec[axis] == value:
# 将该特征值前面的内容保存起来
reducedFeatVec = featVec[:axis]
# 将该特征值后面的内容保存起来，所以将给定特征值给去掉了
reducedFeatVec.extend(featVec[axis + 1:])
# 添加到返回列表中
retDataSet.append(reducedFeatVec)
return retDataSet
类别处理：
当将所有属性值划分完后，也就是到头了不会再分支了。只需要对当前属性下的数据集进行类别处理，分成好瓜还是坏瓜。而分类的依据就是看看样本集中哪个类别的样本多，那这条分支就对应着哪个类别。只需要统计标签数量，遍历完所有的标签，找出最多的标签。
def majorityCnt(classList):
"""
找到次数最多的类别标签
:param classList:
:return:
"""
# 用来统计标签的票数
classCount = collections.defaultdict(int)
# 遍历所有的标签类别
for vote in classList:
classCount[vote] += 1
# 从大到小排序
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1),
reverse=True)
# 返回次数最多的标签
return sortedClassCount[0][0]
信息熵：
按照给的公式定义出信息熵计算函数。先求出数据集的长度，统计好标签数量，遍历数据集得到分类标签，以2为底求对数求出信息熵。
def calcShannonEnt(dataSet):
"""
计算给定数据集的信息熵(香农熵)
:param dataSet:
:return:
"""
# 计算出数据集的总数
numEntries = len(dataSet)
# 用来统计标签
labelCounts = collections.defaultdict(int)
# 循环整个数据集，得到数据的分类标签
for featVec in dataSet:
# 得到当前的标签
currentLabel = featVec[-1]
# 如果当前的标签不再标签集中，就添加进去
labelCounts[currentLabel] += 1
# 默认的信息熵
shannonEnt = 0.0
for key in labelCounts:
# 计算出当前分类标签占总标签的比例数
prob = float(labelCounts[key]) / numEntries
# 以2为底求对数
shannonEnt -= prob * log(prob, 2)
return shannonEnt
信息增益：
计算出信息增益，也就是决策树的划分依据，用到了信息熵的函数。并且我们要返回最大信息增益的那个属性的下标。我们需要先求出总的信息熵，然后对每个特征值求信息熵，作差求解出对应特征值的信息增益。
def chooseBestFeatureToSplit(dataSet, labels):
"""
选择最好的数据集划分特征，根据信息增益值来计算
:param dataSet:
:return:
"""
# 得到数据的特征值总数
numFeatures = len(dataSet[0]) - 1
# 计算出基础信息熵
baseEntropy = calcShannonEnt(dataSet)
# 基础信息增益为0.0
bestInfoGain = 0.0
# 最好的特征值
bestFeature = -1
# 对每个特征值进行求信息熵
for i in range(numFeatures):
# 得到数据集中所有的当前特征值列表
featList = [example[i] for example in dataSet]
# 将当前特征唯一化，也就是说当前特征值中共有多少种
uniqueVals = set(featList)
# 新的熵，代表当前特征值的熵
newEntropy = 0.0
# 遍历现在有的特征的可能性
for value in uniqueVals:
# 在全部数据集的当前特征位置上，找到该特征值等于当前值的集合
subDataSet = splitDataSet(dataSet=dataSet, axis=i, value=value)
# 计算出权重
prob = len(subDataSet) / float(len(dataSet))
# 计算出当前特征值的熵
newEntropy += prob * calcShannonEnt(subDataSet)
# 计算出“信息增益”
infoGain = baseEntropy - newEntropy
print('当前特征值为：' + labels[i] + '，对应的信息增益值为：' + str(infoGain))
# 如果当前的信息增益比原来的大
if infoGain > bestInfoGain:
# 最好的信息增益
bestInfoGain = infoGain
# 新的最好的用来划分的特征值
bestFeature = i
print('信息增益最大的特征为：' + labels[bestFeature])
return bestFeature
结束划分：
当样本集样本在属性集合中的各个取值相同，此时可结束划分。我们需要计算出共有多少个属性，多少个数据，遍历全部属性，与样本集数据进行对比，返回对比值（True或是False）
def judgeEqualLabels(dataSet):
"""
判断数据集的各个属性集是否完全一致
:param dataSet:
:return:
"""
# 计算出样本集中共有多少个属性，最后一个为类别
feature_leng = len(dataSet[0]) - 1
# 计算出共有多少个数据
data_leng = len(dataSet)
# 标记每个属性中第一个属性值是什么
first_feature = ''
# 各个属性集是否完全一致
is_equal = True
# 遍历全部属性
for i in range(feature_leng):
# 得到第一个样本的第i个属性
first_feature = dataSet[0][i]
# 与样本集中所有的数据进行对比，看看在该属性上是否都一致
for _ in range(1, data_leng):
# 如果发现不相等的，则直接返回False
if first_feature != dataSet[_][i]:
return False
return is_equal
生成决策树：
首先要循环拿到所有的数据集分类标签，统计标签数量，用来判断是否满足结束条件，得到最好的特征属性。用字典来存储决策树，然后要除去当前的属性，也就是向下继续生成树，递归调用直至结束，此时结果就是最终的字典，也就是最终的决策树。以字典的形式生成决策树，翻译成图如下：
def createTree(dataSet, labels):
"""
创建决策树
:param dataSet: 数据集
:param labels: 特征标签
:return:
"""
# 拿到所有数据集的分类标签
classList = [example[-1] for example in dataSet]
# 统计第一个标签出现的次数，与总标签个数比较，如果相等则说明当前列表中全部都是一种标签，此时停止划分
if classList.count(classList[0]) == len(classList):
return classList[0]
# 计算第一行有多少个数据，如果只有一个的话说明所有的特征属性都遍历完了，剩下的一个就是类别标签，或者所有的样本在全部属性上都一致
if len(dataSet[0]) == 1 or judgeEqualLabels(dataSet):
# 返回剩下标签中出现次数较多的那个
return majorityCnt(classList)
# 选择最好的划分特征，得到该特征的下标
bestFeat = chooseBestFeatureToSplit(dataSet=dataSet, labels=labels)
# 得到最好特征的名称
bestFeatLabel = labels[bestFeat]
# 使用一个字典来存储树结构，分叉处为划分的特征名称
myTree = {bestFeatLabel: {}}
# 将本次划分的特征值从列表中删除掉
del(labels[bestFeat])
# 得到当前特征标签的所有可能值
featValues = [example[bestFeat] for example in dataSet]
# 唯一化，去掉重复的特征值
uniqueVals = set(featValues)
# 遍历所有的特征值
for value in uniqueVals:
# 得到剩下的特征标签
subLabels = labels[:]
subTree = createTree(splitDataSet(dataSet=dataSet, axis=bestFeat,
value=value), subLabels)
# 递归调用，将数据集中该特征等于当前特征值的所有数据划分到当前节点下，递归调用时需要先将当前的特征去除掉
myTree[bestFeatLabel][value] = subTree
return myTree
解题结果：
当前特征值为：色泽，对应的信息增益值为：0.10812516526536531
当前特征值为：根蒂，对应的信息增益值为：0.14267495956679288
当前特征值为：敲击，对应的信息增益值为：0.14078143361499584
当前特征值为：纹理，对应的信息增益值为：0.3805918973682686
当前特征值为：脐部，对应的信息增益值为：0.28915878284167895
当前特征值为：触感，对应的信息增益值为：0.006046489176565584
信息增益最大的特征为：纹理
当前特征值为：色泽，对应的信息增益值为：0.04306839587828004
当前特征值为：根蒂，对应的信息增益值为：0.45810589515712374
当前特征值为：敲击，对应的信息增益值为：0.33085622540971754
当前特征值为：脐部，对应的信息增益值为：0.45810589515712374
当前特征值为：触感，对应的信息增益值为：0.45810589515712374
信息增益最大的特征为：根蒂
当前特征值为：色泽，对应的信息增益值为：0.2516291673878229
当前特征值为：敲击，对应的信息增益值为：0.0
当前特征值为：脐部，对应的信息增益值为：0.0
当前特征值为：触感，对应的信息增益值为：0.2516291673878229
信息增益最大的特征为：色泽
当前特征值为：敲击，对应的信息增益值为：0.0
当前特征值为：脐部，对应的信息增益值为：0.0
当前特征值为：触感，对应的信息增益值为：1.0
信息增益最大的特征为：触感
当前特征值为：色泽，对应的信息增益值为：0.3219280948873623
当前特征值为：根蒂，对应的信息增益值为：0.07290559532005603
当前特征值为：敲击，对应的信息增益值为：0.3219280948873623
当前特征值为：脐部，对应的信息增益值为：0.17095059445466865
当前特征值为：触感，对应的信息增益值为：0.7219280948873623
信息增益最大的特征为：触感
根节点信息熵： 0.9975025463691153
{'纹理': {'清晰': {'根蒂': {'硬挺': '坏瓜', '稍蜷': {'色泽': {'乌黑': {'触感': {'硬滑': '好瓜',
'软粘': '坏瓜'}}, '青绿': '好瓜'}}, '蜷缩': '好瓜'}}, '稍糊': {'触感': {'硬滑': '坏瓜', '软粘':
'好瓜'}}, '模糊': '坏瓜'}}
k-means聚类分析算法实现
问题背景：
夏天就要到了，就要到吃西瓜的季节了。所以说西瓜甜不甜是我们非常在意的一个问题。但是西瓜甜不甜与什么有关呢？有人假想了一下西瓜甜不甜是否与密度有关呢？也就是西瓜含糖率与密度的关系。上面我们分析了给定特征来区分好坏瓜，下面我们就根据已知瓜的密度和含糖率的数据表来进行无监督的聚类分析。
首先我们需要知道无监督学习和有监督的区别在于输入数据的标签有无，无监督学习的样本是没有标签的，我们的目的就是通过对这些无标签样本的训练学习来揭示数据的内在规律。其中聚类分析试图将样本划分为若干个不相交的子集，每个子集称为一个“簇”，子集的质心被称为“簇心”，通过不断地迭代来实现对数据分类，分成几类也就是我们的初始k值是定义者一开始就定义好的，也就是簇心的含义是由定义者来一开始就定义的。这也是k-means算法比较缺陷的一点。
解题过程：
数据集：
我们拿到的是一个关于西瓜密度和含糖率的二维矩阵，总共30行，每行两列数据。第一列为密度x1，第二列为含糖率x2。为处理数据，我们要从sklearn.cluster库中导入KMeans函数。
from sklearn.cluster import KMeans # 从sklearn.cluster机器学习聚类包中导入KMeans方法
X=[
[0.697,0.460],[0.774,0.376],[0.634,0.264],[0.608,0.318],[0.556,0.215],
[0.403,0.237],[0.481,0.149],[0.437,0.211],[0.666,0.091],[0.243,0.267],
[0.245,0.057],[0.343,0.099],[0.639,0.161],[0.657,0.198],[0.360,0.370],
[0.593,0.042],[0.719,0.103],[0.359,0.188],[0.339,0.241],[0.282,0.257],
[0.748,0.232],[0.714,0.346],[0.483,0.312],[0.478,0.437],[0.525,0.369],
[0.751,0.489],[0.532,0.472],[0.473,0.376],[0.725,0.445],[0.446,0.459]
]
聚类分析：
先将初始k值设为2，代表分为两类。调用KMeans方法，赋值给clf，再对数据进行聚类，将结果赋值给y_pred，代表着每个西瓜，不需要预测。直接打印k-means模型和聚类最后的结果，以列表形式输出。
clf = KMeans(n_clusters=2) # 聚类算法，参数n_clusters=2，聚成2类
y_pred = clf.fit_predict(X) # 直接对数据进行聚类，聚类不需要进行预测
print('k均值模型:\n',clf) # 输出完整Kmeans函数，包括很多省略参数
print('聚类结果:\n',y_pred) # 输出聚类预测结果，30行数据，每个y_pred对应X一行或一个西瓜，聚成2类
数据可视化：
首先导入matplotlib中的pyplot方法，采用for循环获取每行的第一列和第二列。再绘制散点图和横轴纵轴标签，标题这种小细节，最后show出来即可。
import numpy as np
import matplotlib.pyplot as plt
# 获取第一列和第二列数据 使用for循环获取 n[0]表示X第一列
x1 = [n[0] for n in X]
x2 = [n[1] for n in X]
# 绘制散点图 参数：x横轴 y纵轴
plt.scatter(x1, x2, c=y_pred, marker='*')
# 绘制标题
plt.title("k-means Data")
# 绘制x轴和y轴坐标
plt.xlabel("x1")
plt.ylabel("x2")
# 显示图形
plt.show()
解题结果：
为提高精确性，我们分别给k取值2,3,4看看最终的效果。
k=2:
k均值模型:
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
n_clusters=2, n_init=10, n_jobs=None, precompute_distances='auto',
random_state=None, tol=0.0001, verbose=0)
聚类结果:
[0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1] k=3:
k均值模型:
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
n_clusters=3, n_init=10, n_jobs=None, precompute_distances='auto',
random_state=None, tol=0.0001, verbose=0)
聚类结果:
[2 2 0 2 0 1 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 2 2 2 2 2 2 2 2 2] k=4:
k均值模型:
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
n_clusters=4, n_init=10, n_jobs=None, precompute_distances='auto',
random_state=None, tol=0.0001, verbose=0)
聚类结果:
[3 3 1 3 1 2 2 2 1 2 2 2 1 1 0 1 1 2 2 2 1 3 0 0 0 3 0 0 3 0]