分类技术 (或分类法) 是一种根据输入数据建立分类模型的系统方法, 分类法的例子包括决策分类法, 基于规则的分类法, 神经网络, 支持向量机和朴素贝叶斯分类法. 这些技术都使用一种学习算法 (learning algorithm) 确定分类模型, 该模型能够很好的拟合输入数据中类标号和属性集之间的联系, 学习算法得到的模型不仅要很好地拟合输入数据, 还要能够正确的预测未知样本的类标号. 因此, 训练算法的主要目标就是建立具有很好泛化能力模型, 即建立能够准确的预测未知样本类标号的模型.
那我们首先说一下分类与回归的区别.
回归(regression)
回归问题的应用场景(预测的结果是连续的, 例如预测明天的温度: 23,24,25 度等等)
所以说回归问题通常是用来预测一个值, 如预测房价, 未来的天气情况等等, 例如一个产品的实际价格为 500 元, 通过回归分析预测值为 501 元, 我们认为这是一个比较好的回归分析. 一个比较常见的回归算法是线性回归算法(LR). 另外, 回归分析用在神经网络上, 其最上层是不需要 softmax 函数的, 而是直接对前一层累加即可. 回归是对真实值的一种逼近预测.
分类(classification)
分类问题的应用场景(预测的结果是离散的, 例如预测明天天气: 阴, 晴, 雨等等)
例如判断一幅图片上的动物是一只猫还是一只狗, 分类通常是建立在回归之上, 分类的最后一层通常要使用 softmax 函数进行判断其所属类别. 分类并没有逼近的概念, 最终正确结果只有一个, 错误的就是错误的, 不会有相近的概念. 最常见的分类方法是逻辑回归, 或者叫逻辑分类.
如何选择模型呢?(我们借助别人的图来选择分类, 回归, 聚类, 降维)
决策数 (Decision Tree) 在机器学习中也是比较常见的一种算法, 属于监督学习中的一种. 看字面意思应该也比较容易理解, 相比其他算法比如支持向量机 (SVM) 或神经网络, 似乎决策树感觉 "亲切" 许多.
决策树算法思想
决策树 (decision tree) 是一个树结构(可以是二叉树或者非二叉树). 决策树分为分类树和回归树两种, 分类树对离散变量做决策树, 回归树对连续变量做决策树.
其中每个非叶节点表示一个特征属性上的测试, 每个分支代表这个特征属性在某个值域上的输出, 而每个叶节点存放在一个类别.
使用决策树进行决策的过程就是从根节点开始, 测试待分类项中相应的特征属性, 并按照其值选择输出分支, 知道到达叶子节点, 将叶子节点存放的类别作为决策结果.
决策树学习算法主要由三部分构成
特征选择
特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准, 如何选择特征有着很多不同量化评估标准, 从而衍生出不同的决策树算法.
决策树生成
根据选择的特征评估标准, 从上至下递归地生成子节点, 直到数据集不可分则停止决策树停止生长. 树结构来说, 递归结构是最容易理解的方式.
决策树的剪枝
决策树容易过拟合, 一般来需要剪枝, 缩小树结构规则, 缓解过拟合, 剪枝技术有预剪枝和后剪枝两种.
决策实例一
决策树表示如下(借用周志华老师西瓜书的图)
假如我现在告诉你, 我买了一个西瓜, 它的特点是纹理是清晰, 根蒂是硬挺的瓜, 你来给我判断一下是好瓜还是坏瓜, 恰好, 你构建了一颗决策树, 告诉他, 没问题, 我马上告诉你是好瓜, 还是坏瓜?
判断步骤如下:
根据纹理特征, 已知是清晰, 那么走下面这条路, 红色标记:
好了, 现在到了第二层, 这个时候, 由决策树的图, 我们可以看到, 我们需要知道根蒂的特征时什么了?, 对时硬挺, 于是我们继续走, 如下蓝色的图:
此时, 我们到达叶子结点了, 根据上面总结的店, 可知, 叶子结点代表一种类别, 我们从如上决策树中可以知道, 这是一个坏瓜!!
所以根据上面的例子, 非常直观容易的得到了一个实例的类别判断, 只要你告诉我各个特征的具体值, 决策树的判定过程就相当于树中从跟节点到某一个叶子节点的遍历, 每一步如何遍历是由数据各个特征的具体特征属性决定.
好了, 可能有人要问了, 说了这么多, 给你训练数据, 你的决策树是怎么构建的呢? 没有树, 谈何遍历, 谈何分类?
于是构建决策树也就成了最重要的工作!!
比如, 给我下面的训练数据, 我们如何构建出决策树?
我们可以从上面的决策树看出, 每一次子结点的产生, 是由于我在当前层数选择了不同的特征来作为我的分裂因素造成的, 比如下面红色三角形表示选择的特征:
每一层选择了指定的特征之后, 我们就可以继续由该特征的不同属性值进行划分, 依次一直到叶子节点.
看起来一切很顺利, 但是, 细心地小伙伴可能会问了, 为什么在第一次选择特征分裂的时候, 不选择触感呢? 而是选择纹理, 比如如下:
不换成抽干, 或者是其他特征呢? 为什么选择的是纹理, 这是以什么标准来选择特征的? 这个问题先留着, 让我们再看一个例子
决策实例二
一天, 老师问了个问题, 只根据头发和声音怎么判断一位同学的性别.
为了解决这个问题, 同学们马上简单的统计了 7 位同学的相关特征, 数据如下:
机智的同学 A 想了想, 先根据头发判断, 若判断不出, 再根据声音判断, 于是画了一幅图, 如下:
于是, 一个简单, 直观的决策树就这么出来了. 头发长, 声音粗就是男生; 头发长, 声音细就是女生; 头发短, 声音粗是男生; 头发短, 声音细是女生.
这时又蹦出个同学 B, 想先根据声音判断, 然后再根据头发来判断, 如是大手一挥也画了个决策树:
同学 B 的决策树: 首先判断声音, 声音细, 就是女生; 声音粗, 头发长是男生; 声音粗, 头发长是女生.
那么问题来了: 同学 A 和同学 B 谁的决策树好些? 计算机做决策树的时候, 面对多个特征, 该如何选哪个特征为最佳的划分特征? 下面我们就要说一下决策树的特征选择了.
决策树的特征选择
划分数据集的大原则是: 将无序的数据变得更加有序.
我们可以使用多种方法划分数据集, 但是每种方法都有各自的优缺点. 于是我们这么想, 如果我们能测量数据的复杂度, 对比按不同特征分类后的数据复杂度, 若按某一特征分类后复杂度减少的更多, 那么这个特征即为最佳分类特征.
Claude Shannon 定义了熵 (entropy) 和信息增益(information gain). 下面先介绍一下概念:
熵(entropy)
在信息论与概率论中, 熵 (entropy) 用于表示 "随机变量不确定性的度量"
在决策树的算法中, 熵是一个非常非常重要的概念, 一件事发生的概率越小, 我们说它蕴含的信息量越大, 比如: 我们听到女人怀孕了, 是不是不奇怪, 但是某天听到那个男人怀孕了, 是不是????
所以下面我们说一下信息量熵的定义.
设 X 是一个有限状态的离散型随机变量, 其概率分布为:
则随机变量 X 的熵定义为:
熵越大, 则随机变量的不确定性越大.
当随机变量只有 0 和 1 两种取值的时候, 假设 P(X=1)=p, 则有:
从而有:
从而可知, 当 p=0.5 时, 熵取值最大, 随机变量不确定性最大. 如图:
条件熵(conditional entropy)
随机变量 X 给定的条件下, Y 的条件概率分布的熵对 X 的数学期望, 其数学推导如下:
随机变量 Y 的条件熵 H(Y|X)定义为:
其中:
条件熵 H(Y|X)表示在已知随机变量 X 的条件下随机变量 Y 的不确定性. 注意一下, 条件熵中 X 也是一个变量, 意思是在一个变量 X 的条件下(变量 X 的每个值都会取到), 另一个变量 Y 的熵对 X 的期望.
信息增益(information gain)
信息增益表示的是: 得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度. 简单说, 就是当我们用另一个变量 X 对原变量 Y 分类后, 原变量 Y 的不确定性就会减少了(即熵值减少). 而熵就是不确定性, 不确定程度减少了多少其实就是信息增益, 这就是信息增益的由来.
所以信息增益的具体定义如下:
特征 A 对训练数据集 D 的信息增益 g(D,A)定义为集合 D 的经验熵 H(D)与特征 A 给定条件下 D 的经验条件熵 H(D/A)之差, 即:
一般地, 熵 H(Y)与条件熵 H(Y|X)之差成为互信息(mutual information).
根据信息增益准则而进行特征选择的方法是: 对训练数据集 D, 计算其每个特征的信息增益, 并比他们大小, 从而选择信息增益最大的特征.
假设训练数据集为 D, 样本容量为 | D|, 由 k 个类别 Ck,|Ck | 为类别 Ck 的样本个数, 某一特征 A 由 n 个不同的取值 a1,a2,a3,.....an. 根据特征 A 的取值可将数据集 D 划分为 n 个子集 D1,D2.....Dn,|Di | 为 Di 的样本个数, 并记子集 Di 中属于类 Ck, 的样本的集合为 Dik,|Dik | 为 Dik 的样本个数.
则信息增益的算法如下:
- 输入: 训练数据集 D 和特征 A
- 输出: 特征 A 对训练数据集 D 的信息增益 g(D,A)
(1) 计算数据集 D 的经验熵 H(D).
(2)计算特征 A 对数据集 D 的经验条件 H(D|A)
(3)计算信息增益
信息增益比(information gain ratio)
以信息增益作为特征选择准则, 会存在偏向于选择取值较多的特征的问题, 可以采用信息增益比对这个问题进行校正.
特征 A 对训练数据集 D 的信息增益比定义为其信息增益与训练集 D 关于特征 A 的值的熵之比, 即:
其中:
计算实例二的信息增益值
首先计算未分类前的熵, 总共有 8 位同学, 男生 3 位, 女生 5 位.
熵(总)=-3/8*log2(3/8)-5/8*log2(5/8)=0.9544
接着分别计算同学 A 和同学 B 分类后信息熵.
同学 A 首先按头发分类, 分类后的结果为: 长头发中有 1 男 3 女. 短头发中有 2 男 2 女.
熵(同学 A 长发)=-1/4*log2(1/4)-3/4*log2(3/4)=0.8113
熵(同学 A 短发)=-2/4*log2(2/4)-2/4*log2(2/4)=1
熵(同学 A)=4/8*0.8113+4/8*1=0.9057
信息增益(同学 A)= 熵(总)- 熵(同学 A)=0.9544-0.9057=0.0487
同理, 按同学 B 的方法, 首先按声音特征来分, 分类后的结果为: 声音粗中有 3 男 3 女. 声音细中有 0 男 2 女.
熵(同学 B 声音粗)=-3/6*log2(3/6)-3/6*log2(3/6)=1
熵(同学 B 声音粗)=-2/2*log2(2/2)=0
熵(同学 B)=6/8*1+2/8*0=0.75
信息增益(同学 B)= 熵(总)- 熵(同学 A)=0.9544-0.75=0.2087
按同学 B 的方法, 先按声音特征分类, 信息增益更大, 区分样本的能力更强, 更具有代表性.
以上就是决策树 ID3 算法的核心思想.
代码如下:
- def uniquecounts(rows):
- '''
- 对 y 的各种可能取值出现的个数进行计数
- 其他函数利用该函数来计算数据集和的混杂程序
- :param rows:
- :return:
- '''
- results = {}
- for row in rows:
- # 计算结果在最后一列
- r = rows[len(rows)-1]
- if r not in results:
- results[r] = 0
- results[r] += 1
- # 返回 一个字典
- return results
- def entropy(rows):
- # 计算熵
- from math import log
- log2 = lambda x:log(x)/log(2)
- results = uniquecounts(rows)
- # 开始计算熵的值
- ent = 0.0
- for r in results.keys():
- p = float(results[r]/len(rows))
- ent = ent - p*log2(p)
- return ent
决策树的生成算法介绍
划分数据集的最大原则是: 使无序的数据变的有序. 如果一个训练数据中有 20 个特征, 那么选取哪个做划分依据? 这就必须采用量化的方法来判断, 量化划分方法有多重, 其中一项就是 "信息论度量信息分类". 基于信息论的决策树算法有 ID3,CART 和 C4.5 等算法, 其中 C4.5 和 CART 两种算法从 ID3 算法中衍生而来.
决策树的生成算法由很多变形, 这里简单说一下几种经典的实现算法: ID3 算法, C4.5 算法和 CART 算法. 这些算法的主要区别在于分类结点熵特征选择的选取标准不同, 下面了解一下算法的具体实现过程.
一: ID3 算法
ID3 算法所采用的度量标准就是我们前面提到的 "信息增益". 当属性 a 的信息增益最大时, 则意味着用 a 属性划分, 其所获得的 "纯度" 提升最大, 我们所要做的, 就是找到信息增益最大的属性.
ID3 算法的核心是在决策树的各个节点上应用信息增益准则进行特征选择, 具体的做法是:
从根节点上开始, 对结点计算所有可能特征的信息增益, 选择信息增益最大的特征作为结点的特征, 并由该特征的不同取值构建子节点;
对于子节点递归的调用以上方法, 构建决策树;
直到所有特征的信息增益均很小或者没有特征可选择的时候为止.
ID3 算法存在的缺点:
1. ID3 算法在选择根节点和内部节点中的分支属性时, 采用信息增益作为评价标准. 信息增益的缺点是倾向于选择取值较多是属性, 在有些情况下这类属性可能不会提供太多有价值的信息.
2. ID3 算法只能对描述属性为离散型属性的数据集构造决策树 .
为了改进决策树, 又提出了 ID4.5 算法和 CART 算法.
二: C4.5 算法
C4.5 算法与 ID3 算法的区别主要是在于它在生产决策树的过程中, 使用信息增益比来进行特征选择.
实际上, 信息增益准则对于可取值数目较多的属性会有所偏好, 为了减少这种偏好可能带来的不利影响, C4.5 决策树算法不直接使用信息增益, 而是使用 "信息增益率" 来选择最优划分属性, 信息增益率定义为:
其中, 分子为信息增益, 分母为属性 X 的熵.
需要注意的是, 增益率准则对可取值数目较少的属性有所偏好.
所以一般这样选取划分属性: 先从候选属性中找到信息增益高于平均水平的属性, 再从中选择增益率最高的.
三: CART 算法
分类与回归树 (classification and regression tree,CART) 与 C4.5 算法一样, 由 ID3 算法演化而来. CART 假设决策树是一个二叉树, 它通过递归地二分每个特征, 将特征空间划分为有限个单元, 并在这些单元上确定预测的概率分布.
CART 算法中, 对于回归树, 采用的是平方误差最小化准则; 对于分类树, 采用基尼指数最小化准则.
平方误差最小化
假设已将输入空间划分为 M 个单元 R1,R2......Rm, 并且在每个单元 Rm 上有一个固定的输出值 Cm, 于是回归树可以表示为:
当输入空间的划分确定时, 可以用平方误差 来表示回归树对于训练数据的预测误差.
基尼指数
分类问题中, 假设有 K 个类别, 样本点属于第 k 类的概率为 pk, 则概率分布的基尼指数定义为:
决策树的优缺点分析
优点:
易于理解和解释, 甚至比线性回归更直观;
与人类做决策思考的思维习惯契合;
模型可以通过树的形式进行可视化展示;
可以直接处理非数值型数据, 不需要进行哑变量的转换, 甚至可以直接处理含有缺失值的数据;
缺点:
对于有大量数值型输入和输出的问题, 决策树未必是一个好的选择;
特别是当数值型变量之间存在许多错综复杂的关系, 如金融数据分析;
决策分类的因素取决于更多变量的复杂组合时;
模型不够稳健, 某一个节点的小小变化可能导致整个树会有很大的不同
接下来用 python 代码来实现 ID3 算法:
- from math import log
- import operator
- def calcShannonEnt(dataSet): # 计算数据的熵(entropy)
- numEntries=len(dataSet) # 数据条数
- labelCounts={}
- for featVec in dataSet:
- currentLabel=featVec[-1] # 每行数据的最后一个字(类别)
- if currentLabel not in labelCounts.keys():
- labelCounts[currentLabel]=0
- labelCounts[currentLabel]+=1 # 统计有多少个类以及每个类的数量
- shannonEnt=0
- for key in labelCounts:
- prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
- shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
- return shannonEnt
- def createDataSet1(): # 创造示例数据
- dataSet = [['长', '粗', '男'],
- ['短', '粗', '男'],
- ['短', '粗', '男'],
- ['长', '细', '女'],
- ['短', '细', '女'],
- ['短', '粗', '女'],
- ['长', '粗', '女'],
- ['长', '粗', '女']]
- labels = ['头发','声音'] #两个特征
- return dataSet,labels
- 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
- def chooseBestFeatureToSplit(dataSet): # 选择最优的分类特征
- numFeatures = len(dataSet[0])-1
- baseEntropy = calcShannonEnt(dataSet) # 原始的熵
- bestInfoGain = 0
- bestFeature = -1
- for i in range(numFeatures):
- featList = [example[i] for example in dataSet]
- uniqueVals = set(featList)
- newEntropy = 0
- for value in uniqueVals:
- subDataSet = splitDataSet(dataSet,i,value)
- prob =len(subDataSet)/float(len(dataSet))
- newEntropy +=prob*calcShannonEnt(subDataSet) # 按特征分类后的熵
- infoGain = baseEntropy - newEntropy # 原始熵与按特征分类后的熵的差值
- if (infoGain>bestInfoGain): # 若按某特征划分后, 熵值减少的最大, 则次特征为最优分类特征
- bestInfoGain=infoGain
- bestFeature = i
- return bestFeature
- def majorityCnt(classList): #按分类后类别数量排序, 比如: 最后分类为 2 男 1 女, 则判定为男;
- classCount={}
- for vote in classList:
- if vote not in classCount.keys():
- classCount[vote]=0
- classCount[vote]+=1
- sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
- return sortedClassCount[0][0]
- def createTree(dataSet,labels):
- 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)
- bestFeat=chooseBestFeatureToSplit(dataSet) #选择最优特征
- bestFeatLabel=labels[bestFeat]
- myTree={bestFeatLabel:{}} #分类结果以字典形式保存
- del(labels[bestFeat])
- featValues=[example[bestFeat] for example in dataSet]
- uniqueVals=set(featValues)
- for value in uniqueVals:
- subLabels=labels[:]
- myTree[bestFeatLabel][value]=createTree(splitDataSet\
- (dataSet,bestFeat,value),subLabels)
- return myTree
- if __name__=='__main__':
- dataSet, labels=createDataSet1() # 创造示列数据
- print(createTree(dataSet, labels)) # 输出决策树模型结果
输出结果为:
{'声音': {'细': '女', '粗': {'头发': {'短': '男', '长': '女'}}}}
这个结果的意思是: 首先按声音分类, 声音细为女生; 然后再按头发分类: 声音粗, 头发短为男生; 声音粗, 头发长为女生.
这个结果也正是同学 B 的结果.
补充说明: 判定分类结束的依据是, 若按某特征分类后出现了最终类(男或女), 则判定分类结束. 使用这种方法, 在数据比较大, 特征比较多的情况下, 很容易造成过拟合, 于是需进行决策树枝剪, 一般枝剪方法是当按某一特征分类后的熵小于设定值时, 停止分类.
参考:
- Machine Learning in Action https://book.douban.com/subject/6962285/
- 统计学习方法 https://book.douban.com/subject/10590856/
https://zhuanlan.zhihu.com/p/26703300
来源: https://www.cnblogs.com/wj-1314/p/9428494.html