1、第6章大数据分析中的四种常见分类算法6.1 分类算法概述6.2 KNN算法6.3 决策树与随机森林算法6.4 朴素贝叶斯分类算法6.5 支持向量机6.1 分类算法概述6.1.1 有关分类算法的基本概念常用的分类算法包括：决策树(Decision Tree)分类算法、贝叶斯分类算法、K-最近邻(K-Nearest Neighbor，KNN)算法、支持向量机(Support Vector Machine，SVM)算法等。1.决策树分类算法 决策树分类算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决
2、策树是通过一系列规则对数据进行分类的过程。2.贝叶斯分类算法贝叶斯分类算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯(Naive Bayesian)算法，该算法能运用到大型数据库中，而且方法简单、分类准确率高、速度快。第6章大数据分析中的四种常见分类算法6.1 分类算法概述6.1.1 有关分类算法的基本概念3.KNN算法KNN算法是一种基于实例的分类方法，它是数据挖掘分类技术中最简单的方法之一。4.SVM算法 SVM是由Corinna Cortes和Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问
3、题中。第6章大数据分析中的四种常见分类算法6.1 分类算法概述6.1.2 分类算法的常见应用场景1.O2O优惠券使用预测在O2O中使用优惠券的形式来刺激老用户吸引新用户是一种常见的营销方式。2.市民出行选乘公交预测分析挖掘出固定人群在公共交通中的行为模式，分析推测乘客的出行习惯和偏好，建立模型预测人们在未来一周内将会搭乘哪些公交线路。3.待测微生物种类判别通过把DNA序列片段与已知的微生物DNA序列进行比较，可以确定DNA片段的来源微生物，进而确定待测微生物种类。4.基于运营商数据的个人征信评估利用运营商用户数据，可以提供完善的个人征信评估。第6章大数据分析中的四种常见分类算法6.1 分类算法
4、概述6.1.2 分类算法的常见应用场景5.商品图片分类提取商品图像特征，可以提供给推荐、广告等系统，提高推荐/广告的效果。6.广告点击行为预测让广告主进行定向广告投放和优化，使广告投入产生较大回报。7.基于文本内容的垃圾短信识别基于短信文本内容，并结合机器学习算法、大数据分析挖掘来智能地识别垃圾短信及其变种。8.中文句子类别精准分析分类算法就可以对中文句子、微博等文本数据，进行类别分析。第6章大数据分析中的四种常见分类算法6.1 分类算法概述6.1.2 分类算法的常见应用场景9.P2P网络借贷平台的经营风险量化分析通过互联网数据，构建出P2P网贷平台的经营风险模型，能够比较准确地预测P2P网贷
5、平台的经营风险，促进我国P2P行业向正规化方向发展。10.国家电网客户用电异常行为分析可以利用大数据分析算法与技术，发现窃电用户的行为特征，以帮助系统更快速、准确地识别窃电用户，提高窃电监测效率，降低窃电损失。11.自动驾驶场景中的交通标志检测把完全真实场景下的图片数据用于训练和测试，训练能够实际应用在自动驾驶中的识别模型。第6章大数据分析中的四种常见分类算法6.1 分类算法概述6.1.2 分类算法的常见应用场景12.大数据精准营销中搜狗用户画像挖掘把用户历时一个月的查询词与用户的人口属性标签(性别、年龄、学历)作为训练数据，通过机器学习、数据挖掘技术构建分类算法来对新增用户的人口属性进行判定
6、。13.基于视角的领域情感分析情感分析是网络舆情分析中必不可少的技术，基于视角的领域情感分析更是情感分析应用于特定领域的关键技术。14.监控场景下的行人精细化识别行人作为视频监控中的重要目标之一，若能对其进行有效的外观识别，不仅能提高视频监控工作人员的工作效率，对检索视频、解析行人行为也具有重要意义。第6章大数据分析中的四种常见分类算法6.1 分类算法概述6.1.2 分类算法的常见应用场景15.用户评分预测通过训练带有时间标记的用户打分行为，准确地预测这些用户对其他商品的打分。16.猫狗识别大战可以从训练集里建立一个模型去识别测试集里的小狗。17.微额借款用户人品预测通过数据挖掘来分析“小额微
7、贷”申请借款用户的信用状况，以分析其是否逾期。第6章大数据分析中的四种常见分类算法6.2 KNN算法6.2.1 KNN算法的工作原理与特点1.KNN算法的工作原理训练数据中每个数据都存在标记(分类信息)，当输入新样本后，将新样本的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类信息。一般来说，我们只选择样本集数据中前k个最相似的数据。最后，选择k个最相似数据出现次数最多的分类。2.代码实现思路代码实现思路具体如下。(1)计算新样本点与训练数据点的距离。(2)将距离按照递增的顺序排序。(3)选取距离最小的k个点。(4)确定前k个点所在类别出现的频率。(5)将距离
8、按照递增的顺序排序。第6章大数据分析中的四种常见分类算法6.2 KNN算法6.2.1 KNN算法的工作原理与特点3.KNN算法的优缺点1)优点(1)理论成熟，思想简单，既可以用来做分类也可以用来做回归。(2)可用于非线性分类。(3)训练时间复杂度比支持向量机之类的算法低，仅为O(n)。(4)和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感。(5)由于KNN算法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。(6)该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域
9、采用这种算法比较容易产生误分。第6章大数据分析中的四种常见分类算法6.2 KNN算法6.2.1 KNN算法的工作原理与特点3.KNN算法的优缺点2)缺点(1)计算量大，尤其是特征数非常多的时候。(2)样本不平衡的时候，对稀有类别的预测准确率低。(3)对于KD树、球树之类的模型建立需要大量的内存。(4)使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。(5)相比决策树模型，KNN模型可解释性不强。第6章大数据分析中的四种常见分类算法6.2 KNN算法6.2.2 快速找到最优k值的实用策略KNN算法中关于k值的选取应遵循以下几个原则。(1)k值较小，则模型复杂度较高，容易发生
10、过拟合，学习的估计误差会增大，预测结果对近邻的实例点非常敏感。(2)k值较大，可以减少学习的估计误差，但是学习的近似误差会增大，与输入实例较远的训练实例也会对预测起作用，使预测发生错误，k值增大，模型的复杂度会下降。(3)在应用中，k值一般取一个比较小的值，通常采用交叉验证法来选取最优的k值。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.1 决策树算法决策树是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率。决策树是一种用于对实例进行分类的树形结构，一种依托于策略抉择而建立起来的树。决策树分类算法构造决策树来发现数据中蕴含的分类规则，
11、如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步，具体如下。(1)决策树的生成：由训练样本集生成决策树的过程。(2)决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正等的过程，第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.1 决策树算法1构建决策树模型从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点(也就是选择适当的分支)；沿着该分支可能达到叶子节点或者到达另一个内部节点时，就使用新的测试条件递归执行下去，直到抵达一个叶子节点。当到达叶子节点时，我们便得到了最终的分类结果。决策树学习也是资料探勘中一个普通
12、的方法。第6章大数据分析中的四种常见分类算法决策树模型6.3 决策树与随机森林算法6.3.1 决策树算法2剪枝剪枝是决策树停止分支的方法之一。剪枝分预先剪枝和后剪枝两种。(1)预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。(2)后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.1 决策树算法3决策树的优缺点1)优点(1)计算复杂度不高，易于理解和解释
13、，可以理解决策树所表达的意义。(2)数据预处理阶段比较简单，且可以处理缺失数据。(3)能够同时处理数据型和分类型属性，且可对有许多属性的数据集构造决策树。(4)是一个白盒模型，给定一个观察模型，则根据所产生的决策树很容易推断出相应的逻辑表达式。(5)在相对短的时间内能够对大数据集合做出可行且效果良好的分类结果。(6)可以对有许多属性的数据集构造决策树。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.1 决策树算法3决策树的优缺点2)缺点(1)对于那些各类别样本数目不一致的数据，信息增益的结果偏向于那些具有更多数值的属性。(2)对噪声数据较为敏感。(3)容易出现过拟合问题
14、。(4)忽略了数据集中属性之间的相关性。(5)处理缺失数据时比较困难。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.1 决策树算法4.决策树ID3算法ID3(Iterative Dichotomiser 3)算法，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树形结构，而是一个启发式算法。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。1)信息熵 1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率。一个
15、系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。2)信息增益 信息增益是针对一个一个特征而言的，就是看一个特征t，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.1 决策树算法5.决策树C4.5算法ID3算法有一些缺陷，在计算的时候，倾向于选择取值多的属性，因此，C4.5算法采用信息增益率的方式来选择属性，这样就避免了上述问题。1)计算类别信息熵 类别信息熵表示的是所有样本中各种类别出现的不确定性之和。2)计算每个
16、属性的信息熵 每个属性的信息熵相当于一种条件熵，它表示的是在某种属性的条件下，各种类别出现的不确定性之和。3)计算信息增益 信息增益=熵-条件熵，这里即是类别信息熵-属性信息熵，它表示的是信息不确定性减少的程度。4)计算属性分裂信息度量 信息增益率=信息增益/内在信息。5)计算信息增益率第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.2 Bagging与Boosting的区别1Bagging算法Bagging算法是一种用来提高学习算法准确度的方法，这种方法通过构造一个预测函数系列，然后以一定的方式将它们组合成一个预测函数。Bagging算法过程如下：(1)从原始样本集中
17、抽取训练集(2)每次使用一个训练集得到一个模型(3)对分类问题第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.2 Bagging与Boosting的区别2Boosting算法Boosting算法，即提升法，它的主要思想是将弱分类器组装成一个强分类器，在概率近似正确(Probably Approximately Correct，PAC)学习框架下，则一定可以将弱分类器组装成一个强分类器。Boosting是一种框架算法，主要是通过对样本集的操作获得样本子集，然后用弱分类算法在样本子集上训练生成一系列的基分类器。Boosting两个核心问题如下：(1)在每一轮如何改变训练数据
18、的权值或概率分布？(2)通过什么方式来组合弱分类器？第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.2 Bagging与Boosting的区别3Bagging与Boosting的区别Bagging与Boosting的区别如下。1)样本选择Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。第6章大数据分析中的四种常见分类算法2)样例权重Bagging：使用均匀取样，每个样例的权重相等。Boosting：根据错误率不
19、断调整样例的权值，错误率越大则权重越大。3)预测函数Bagging：所有预测函数的权重相等。Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。4)并行计算Bagging：各个预测函数可以并行生成。Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.3 随机森林分类算法的优势与应用场景1.随机森林分类算法在机器学习中，随机森林(Random Forest，RF)是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。随机森林分类算法是基于
20、Bagging框架下的决策树模型。随机森林包含了很多树，每棵树给出分类结果，每棵树的生成规则如下：(1)如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中抽取N个训练样本，作为该树的训练集，重复K次，生成K组训练样本集。(2)如果每个特征的样本维度为M，指定一个常数m，随机地从M个特征中选取m个特征。(3)利用m个特征对每棵树尽最大程度地生长，并且没有剪枝过程。第6章大数据分析中的四种常见分类算法6.3 决策树与随机森林算法6.3.3 随机森林分类算法的优势与应用场景2.随机森林分类算法的优点(1)它可以产生高准确度的分类器；(2)随机性的引入，使得随机森林不容易过拟合；(3)随机性
21、的引入，使得随机森林有很好的抗噪声能力；(4)能处理很高维度的数据，并且不用做特征选择；(5)既能处理离散型数据，也能处理连续型数据，数据集无须规范化；(6)训练速度快，可以得到变量重要性排序；(7)容易实现并行化；(8)它计算各例中的亲近度，对于数据挖掘、侦测离群点(outlier)和将资料视觉化非常有用。3.随机森林算法的应用场景随机森林的主要作用是降低模型的复杂度，解决模型的过拟合问题。第6章大数据分析中的四种常见分类算法6.4 朴素贝叶斯分类算法6.4.1 朴素贝叶斯分类算法运行原理分析1.与决策树的比较相比于决策树，贝叶斯分类器是一种在概率框架下实施决策的基本方法，它也与我们人类的经
22、验思维很符合，第6章大数据分析中的四种常见分类算法决策树的划分贝叶斯分类器6.4 朴素贝叶斯分类算法6.4.1 朴素贝叶斯分类算法运行原理分析2.贝叶斯公式第6章大数据分析中的四种常见分类算法1)优点(1)数学基础坚实，分类效率稳定，容易解释。(2)所需估计的参数很少，对缺失数据不太敏感。(3)无须复杂的迭代求解框架，适用于规模巨大的数据集。2)缺点(1)属性之间的独立性假设往往不成立(可考虑用聚类算法先将相关性较大的属性进行聚类)。(2)需要知道先验概率，分类决策存在错误率。6.4 朴素贝叶斯分类算法6.4.1 朴素贝叶斯分类算法运行原理分析3朴素贝叶斯分类算法拉普拉斯曾经说过，“概率论就是
23、将人们的常识使用数学公式表达”。接下来我们来看看最完整的朴素贝叶斯分类算法的数学表达。朴素的含义指的是对条件概率分布作了条件独立性的假设。朴素贝叶斯算法实际上学习到生成数据的机制，属于生成模型。条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的。第6章大数据分析中的四种常见分类算法6.4 朴素贝叶斯分类算法6.4.2 贝叶斯网络1.贝叶斯网络的定义贝叶斯网络(Bayesian Network)，又称信度网络，是Bayes方法的扩展，是目前不确定知识表达和推理领域最有效的理论模型之一。第6章大数据分析中的四种常见分类算法节点E影响到H的有向图表示简单的贝叶斯网络6.4 朴素贝叶斯分
24、类算法6.4.2 贝叶斯网络2.贝叶斯网络的3种结构形式第6章大数据分析中的四种常见分类算法贝叶斯网络图head-to-head结构形式图 tail-to-tail结构形式图head-to-tail结构形式图链式网络结构形式图6.4 朴素贝叶斯分类算法6.4.3 贝叶斯决策理论1.贝叶斯决策理论定义贝叶斯决策理论(Bayesian Decision Theory)就是在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。2.贝叶斯决策理论分析对贝叶斯决策理论的分析具体如下。(1)如果我们已知被分类类别概率分布的形式和已经标记
25、类别的训练样本集合，那我们就需要从训练样本集合中来估计概率分布的参数。(2)如果我们不知道任何有关被分类类别概率分布的知识，已知已经标记类别的训练样本集合和判别式函数的形式，那我们就需要从训练样本集合中来估计判别式函数的参数。第6章大数据分析中的四种常见分类算法(3)如果我们既不知道任何有关被分类类别概率分布的知识，也不知道判别式函数的形式，只有已经标记类别的训练样本集合，那我们就需要从训练样本集合中来估计概率分布函数的参数。(4)只有没有标记类别的训练样本集合，这是经常发生的情形。我们需要对训练样本集合进行聚类，从而估计它们概率分布的参数。(5)如果我们已知被分类类别的概率分布，那么，我们不
26、需要训练样本集合，利用贝叶斯决策理论就可以设计最优分类器。第6章大数据分析中的四种常见分类算法6.4 朴素贝叶斯分类算法6.4.3 贝叶斯决策理论3.贝叶斯决策理论决策判据贝叶斯决策判据既考虑了各类参考总体出现的概率大小，又考虑了因误判造成的损失大小，判别能力强。4.最小错误率贝叶斯决策与最小风险贝叶斯决策考虑决策风险，加入了损失函数，称为最小风险贝叶斯决策。1)最小错误率贝叶斯决策2)最小风险贝叶斯决策最小风险贝叶斯决策就转化成最小错误率贝叶斯决策。最小错误率贝叶斯决策可以看成是最小风险贝叶斯决策的一个特例。第6章大数据分析中的四种常见分类算法6.5 支持向量机6.5.1 支持向量机的基本思
27、想与特点1.支持向量机的基本思想支持向量机的基本思想具体如下。(1)在线性可分情况下，在原空间寻找两类样本的最优分类超平面；在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输入空间的样本映射到高维属性空间，使其变为线性情况，从而使得在高维属性空间采用线性算法对样本的非线性进行分析成为可能，并在该特征空间中寻找最优分类超平面。(2)它通过使用结构风险最小化原理在属性空间构建最优分类超平面，使得分类器得到全局最优，并在整个样本空间的期望风险以某个概率满足一定上界。第6章大数据分析中的四种常见分类算法6.5 支持向量机6.5.1 支持向量机的基本思想与特点2.支持向量机的特点1
28、)优点(1)由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的误差。同时由于SVM引入了核函数，因此对于高维的样本，SVM也能轻松应对。(2)成功应用核函数，使得非线性问题转化为线性问题求解。(3)由于SVM的求解问题对应的是一个凸优化问题，因此局部最优解一定是全局最优解。(4)分类间隔的最大化，使得SVM算法具有较好的鲁棒性。第6章大数据分析中的四种常见分类算法6.5 支持向量机6.5.1 支持向量机的基本思想与特点2.支持向量机的特点2)缺点(1)SVM算法对大规模训练样本难以实施，由于它是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算(m为样本的个数)，当m数
29、目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。(2)用SVM算法解决多分类问题存在困难，经典的SVM算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。第6章大数据分析中的四种常见分类算法6.5 支持向量机6.5.2 最优分类面和广义最优分类面最优分类面要求分类面不但能将两类正确分开，而且要使分类间隔最大。最优分类面的权系数向量是训练样本向量的线性组合。最优分类面是在线性可分的前提下讨论的。第6章大数据分析中的四种常见分类算法最优分类面示意图6.5 支持向量机6.5.3 非线性支持向量机与核函数1.支持向量机的非线性映射SVM就是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间，在这个特征空间中构造最优分类超平面。在形式上SVM分类函数类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应于一个支持向量，第6章大数据分析中的四种常见分类算法SVM示意图6.5 支持向量机6.5.3 非线性支持向量机与核函数2.核函数选择满足Mercer条件的不同内积核函数，就构造了不同的SVM，这样也就形成了不同的算法。目前研究最多的核函数主要有以下三类。1)多项式核函数2)径向基核函数3)S形核函数第6章大数据分析中的四种常见分类算法感谢观看
