Chapter 8. 分类与预测-2

1、2021-6-151数据仓库与数据挖掘数据仓库与数据挖掘 第第8章章 分类分类:基本概念基本概念 (二二)李成安华南理工大学电子商务系2021-6-152主要内容主要内容n基本概念n决策树归纳n贝叶斯分类方法n基于规则的分类n支持向量机 n模型评估与选择n提高分类准确率的技术n小结2021-6-153n分类: n预测分类标号nE.g., 个人主页分类nxi = (x1, x2, x3, ), yi = +1 or 1nx1 : # of a word “homepage”nx2 : # of a word “welcome”n数学上nx X = n, y Y = +1, 1nWe want a

2、 function f: X Y 分类分类: 数学映射数学映射2021-6-154线性分类线性分类n二分类问题nThe data above the red line belongs to class xnThe data below red line belongs to class onExamples: SVM, Perceptron, Probabilistic Classifiersxxxxxxxxxxooooooooooooo2021-6-155感知器感知器 & Winnow Vector: x, w Scalar: x, y, wInput:(x1, y1), Output: c

3、lassification function f(x)f(xi) 0 for yi = +1f(xi) wx + b = 0or w1x1+w2x2+b = 0 x1x2 Perceptron: update W additively Winnow: update W multiplicatively2021-6-156用用BP分类分类n后向传播: A neural network learning algorithm n最早由心理学家和神经学家开创，旨在寻求开发和测试神经的计算模拟。n神经网络: A set of connected input/output units where each

4、 connection has a weight associated with itnDuring the learning phase, the network learns by adjusting the weights so as to be able to predict the correct class label of the input tuplesn又称为连接者学习( connectionist learning )2021-6-157用神经网络作分类器用神经网络作分类器n缺点n训练时间长n学习函数(权重)很难理解n不容易包含论域知识n优点n预测的准确率通常很高n强壮性好

5、,当训练样本包含错误时很有效n输出可以是离散的,实数值的或几个离散或实数值属性的向量n学习目标函数的快速评估2021-6-158神经元神经元nThe n-dimensional input vector x is mapped into variable y by means of the scalar product and a nonlinear function mappingmk-fweighted sumInputvector xoutput yActivationfunctionweightvector ww0w1wnx0 x1xn)sign(yExampleFor n0ikiix

6、wm2021-6-159神经网络训练神经网络训练n训练的最终目标n获得一个权重集使得训练数据中的所有元组都能被正确的分类n步骤n用任意的值初始化权n向前传播输入n对任意单元n每个单元的净输入用它输入的线性组合计算n使用赋活函数计算输出值n计算错误n更新权和基2021-6-1510多层前向神经网络多层前向神经网络 Output layerInput layerHidden layerOutput vectorInput vector: XwijijiijjOwIjIjeO11)(1 (jjjjjOTOOErrjkkkjjjwErrOOErr)1 (ijijijOErrlww)(jjjErrl)(

7、2021-6-1511多层神经网络如何工作的多层神经网络如何工作的?n网络的输入输入对应于每个训练元组测量的属性 n输入同时提供给称为输入层输入层的单元层n然后加权提供给称为隐藏层隐藏层的类神经元的第二层n隐藏层的数量是任意的，尽管实践中通常只用一层 n最后的一个隐藏层的加权输出作为构成输出层输出层的单元的输入。输出层发布给给定元组的网络预测。n网络是前馈的( feed-forward),如果其权都不回送到输入单元，或前一层的输出单元。n从统计学的观点来讲,他们进行非线性回归 : Given enough hidden units and enough training samples, th

8、ey can closely approximate any function2021-6-1512定义网络拓扑结构定义网络拓扑结构n首先确定网络拓扑结构首先确定网络拓扑结构: 输入层的单元数、隐藏层数 (if 1), 、每个隐藏层的单元数和输出层的单元数n规范化每个属性的测量输入值，使其落在 0.01.0。n每个单元初始化为 0n对于分类，如果多于两个类，则每个类使用一个输出单元nOnce a network has been trained and its accuracy is unacceptable, repeat the training process with a differ

9、ent network topology or a different set of initial weights2021-6-1513后向传播后向传播n后向传播迭代地处理训练元组数据集，将每个元组的网络预测与实际已知的目标值比较。n对每个训练样本，修改权重使网络预测和实际目标值之间的均方误差最小。n这种修改“后向”进行，即由输出层，经由每个隐藏层，到第一个隐藏层，故称后向传播 “backpropagation”nStepsn初始化权重 (to small random #s) and biases in the networkn向前传播输入 (by applying activation

10、function) n向后传播误差 (by updating weights and biases)n终止条件 (when error is very small, etc.)2021-6-1514主要内容主要内容n基本概念n决策树归纳n贝叶斯分类方法n基于规则的分类n支持向量机 n模型评估与选择n提高分类准确率的技术n小结2021-6-1515SVM的理论基础的理论基础n传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保证。统计学习理论（STL）研究有限样本情况下的机器学习问题。SVM的理论基础就是统计学习理论。n传统的统计模式识别方法在进行机器学习时，强调经验风险最小化。而单

11、纯的经验风险最小化会产生“过学习问题”，其推广能力较差。n推广能力推广能力是指: 将学习机器(即预测函数,或称学习函数、学习模型)对未来输出进行正确预测的能力。2021-6-1516过学习问题n“过学习问题过学习问题”：某些情况下，当训练误差过小反而会导致推广能力的下降。n例如：对一组训练样本(x,y),x分布在实数范围内，y取值在0，1之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0.2021-6-1517SVMn根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最

12、小误差，没有最小化置信范围值，因此其推广能力较差。nVapnik 提出的支持向量机（Support Vector Machine, SVM）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即SVM是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。n形成时期在19921995年。 2021-6-1518SVMn由于SVM 的求解最后转化成二次规划问题的求解，因此SVM 的解是全局唯一的最优解nSVM在解决小样本、非线性及高维模式识别问题中表现在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他出许多特有的优势，

13、并能够推广应用到函数拟合等其他机器学习问题中机器学习问题中nJoachims 最近采用SVM在Reuters-21578来进行文本分类，并声称它比当前发表的其他方法都好 2021-6-1519OutlinenSVM的理论基础n线性判别函数和判别面n最优分类面n支持向量机nSVM的研究与应用2021-6-1520线性判别函数和判别面线性判别函数和判别面n一个线性判别函数(discriminant function)是指由x的各个分量的线性组合而成的函数 n两类情况:对于两类问题的决策规则为n如果g(x)0，则判定x属于C1，n如果g(x)0；当；当x点在超平面的负侧时，点在超平面的负侧时，g(x

14、) z or t -z, then t value lies in rejection region:nReject null hypothesis that mean error rates of M1 & M2 are samenConclude: statistically significant difference between M1 & M2 nOtherwise, conclude that any difference is chance47模型选择模型选择: ROC 曲线曲线nROC (Receiver Operating Characteristics) curves:

15、for visual comparison of classification modelsnOriginated from signal detection theorynShows the trade-off between the true positive rate and the false positive ratenThe area under the ROC curve is a measure of the accuracy of the modelnRank the test tuples in decreasing order: the one that is most

16、likely to belong to the positive class appears at the top of the listnThe closer to the diagonal line (i.e., the closer the area is to 0.5), the less accurate is the modelnVertical axis represents the true positive ratenHorizontal axis rep. the false positive ratenThe plot also shows a diagonal line

17、nA model with perfect accuracy will have an area of 1.048影响模型选择的问题影响模型选择的问题n准确性准确性nclassifier accuracy: predicting class labeln速度速度ntime to construct the model (training time)ntime to use the model (classification/prediction time)n鲁棒性: handling noise and missing valuesn可伸缩性: efficiency in disk-resid

18、ent databases n可解释性可解释性nunderstanding and insight provided by the modeln其他指标, e.g., goodness of rules, such as decision tree size or compactness of classification rules492021-6-1550预测器误差度量预测器误差度量nMeasure predictor accuracy: measure how far off the predicted value is from the actual known valuen损失函数损

19、失函数: measures the error betw. yi and the predicted value yin绝对误差: | yi yi| n平均误差: (yi yi)2 n检验误差 (泛化误差): the average loss over the test setnMean absolute error: Mean squared error:nRelative absolute error: Relative squared error:The mean squared-error exaggerates the presence of outliersPopularly us

20、e (square) root mean-square error, similarly, root relative squared errordyydiii1| |dyydiii12) (diidiiiyyyy11| |diidiiiyyyy1212)() (2021-6-1551分类法的准确性:评估分类法的准确率2021-6-1552主要内容主要内容n基本概念n决策树归纳n贝叶斯分类方法n基于规则的分类n支持向量机 n模型评估与选择n提高分类准确率的技术n小结2021-6-1553系综方法系综方法: 提升精度提升精度n系综方法nUse a combination of models to

21、 increase accuracynCombine a series of k learned models, M1, M2, , Mk, with the aim of creating an improved model M*n常用的系综方法n装袋: averaging the prediction over a collection of classifiersn推进: weighted vote with a collection of classifiersn集成: combining a set of heterogeneous classifiers2021-6-1554推进与

22、装袋推进与装袋2021-6-1555装袋装袋: 自助聚集自助聚集n模拟: 基于医生的多数投票的诊断nFor i=1 to k don通过对D有放回抽样,创建自助样本Di;n使用Di导出模型Mi;nEndforn对元组X使用复合模型:nIf 分类 thenn让k个模型都对X分类并返回多数表决;nIf 预测 thenn让k个模型都对X预测并返回预测值的平均值;2021-6-1556推进推进n模拟: Consult several doctors, based on a combination of weighted diagnosesweight assigned based on the pre

23、vious diagnosis accuracyn提升如何工作?nWeights are assigned to each training tuplenA series of k classifiers is iteratively learnednAfter a classifier Mi is learned, the weights are updated to allow the subsequent classifier, Mi+1, to pay more attention to the training tuples that were misclassified by Mi

24、nThe final M* combines the votes of each individual classifier, where the weight of each classifiers vote is a function of its accuracynThe boosting algorithm can be extended for the prediction of continuous valuesn与装袋比较: boosting tends to achieve greater accuracy, but it also risks overfitting the