资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分类和预测,第六章,分类和预测是两种数据分析形式，用于提取描述重要数据类或预测未来的数据趋势 的模型,分类：,预测类对象的分类标号（或离散值）,根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据,预测：,建立连续函数值模型,比如预测空缺值，或者预测顾客在计算机设备上的花费,典型应用,欺诈检测、市场定位、性能预测、医疗诊断,分类,VS.,预测,分类,银行贷款员需要分析数据，来弄清哪些贷款申请者是安全的，哪些是有风险的（将贷款申请者分为“安全”和“有风险”两类）,我们需要构造一个分类器来预测类属编号，比如预测顾客属类,预测,银行贷款员需要预测贷给某个顾客多少钱是安全的,构造一个预测器，预测一个连续值函数或有序值，常用方法是回归分析,分类和预测,-,示例,第一步，也成为,学习步,，目标是建立描述预先定义的数据类或概念集的分类器,分类算法通过分析或从训练集“学习”来构造分类器。,训练集由数据库元组（用,n,维属性向量表示）和他们相对应的类编号组成；假定每个元组属于一个预定义的类,训练元组,：训练数据集中的单个元组,学习模型可以用分类规则、决策树或数学公式的形式提供,数据分类,一个两步过程,(1),第二步，使用模型，对将来的或未知的对象进行分类,首先评估模型的预测准确率,对每个测试样本，将已知的类标号和该样本的学习模型类预测比较,模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比,测试集要独立于训练样本集，否则会出现“过分拟合”的情况,数据分类,一个两步过程,(2),第一步,建立模型,训练数,据集,分类算法,IF rank=professor,OR years 6,THEN tenured=yes,分类规则,第二步,用模型进行分类,分类规则,测试集,未知数据,(Jeff,Professor,4),Tenured?,监督学习（用于分类）,模型的学习在被告知每个训练样本属于哪个类的“指导”下进行,新数据使用训练数据集中得到的规则进行分类,无监督学习（用于聚类）,每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的,通过一系列的度量、观察来建立数据中的类编号或进行聚类,监督学习,VS.,无监督学习,数据预测也是一个两步的过程，类似于前面描述的数据分类,对于预测，没有“类标号属性”,要预测的属性是连续值，而不是离散值，该属性可简称“预测属性”,E.g.,银行贷款员需要预测贷给某个顾客多少钱是安全的,预测器可以看作一个映射或函数,y=f(X),其中,X,是输入；,y,是输出，是一个连续或有序的值,与分类类似，准确率的预测，也要使用单独的测试集,数据预测的两步过程,通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性,数据清理,消除或减少噪声，处理空缺值，从而减少学习时的混乱,相关分析,数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确,数据变换与归约,数据可以通过规范化进行变换，将所给属性的所有值按比例进行缩放，使其落入一个较小的指定区间，例,0.0,1.0,（,ANN,和设计距离的度量方法中常用）,可以将数据概化到较高层概念,准备分类和预测的数据,使用下列标准比较分类和预测方法,预测的准确率：模型正确预测新数据的类编号的能力,速度：产生和使用模型的计算花销,健壮性：给定噪声数据或有空缺值的数据，模型正确预测的能力,可伸缩性：对大量数据，有效的构建分类器或预测器的能力,可解释性：学习模型提供的理解和洞察的层次,比较分类方法,什么是决策树？,类似于流程图的树结构,每个内部节点表示在一个属性上的测试,每个分枝代表一个测试输出,每个树叶节点存放一个类编号,用决策树归纳分类,(1),age?,student?,credit rating?,no,yes,fair,excellent,youth,senior,no,no,yes,yes,yes,Middle,aged,决策树：,Buys_computer,使用决策树分类,给定一个类标号未知的元组,X,，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。,决策树容易转换为分类规则,决策树的生成由两个阶段组成,决策树构建,使用属性选择度量来选择将元组最好的划分为不同的类的属性,递归的通过选定的属性，来划分样本（必须是离散值）,树剪枝,决策树建立时，许多分枝反映的是训练数据中的噪声和离群点点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性,用决策树归纳分类,(2),输入,数据划分,D,是训练元组和对应类标号的集合,attribute_list,候选属性的集合,Attribute_selection_method,，指定选择属性的启发性过程,算法步骤,树以代表训练样本的单个节点（,N,）开始,如果样本都在同一个类，则该节点成为树叶，并用该类标记,否则，算法调用,Attribute_selection_method,，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”。,决策树归纳策略,(1),P189,图,6-3,对测试属性每个已知的值，创建一个分支，并以此划分元组,算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现,递归划分步骤停止的条件,划分,D,（在,N,节点提供）的所有元组属于同一类,没有剩余属性可以用来进一步划分元组,使用多数表决,没有剩余的样本,给定分支没有元组，则以,D,中多数类创建一个树叶,决策树归纳策略,(2),P189,图,6-3,属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法,理想情况，每个划分都是“纯”的，即落在给定划分内的元组都属于相同的类,属性选择度量又称为分裂准则,常用的属性选择度量,信息增益,增益率,Gini,指标,属性选择度量,S,是一个,训练样本,的集合，该样本中每个集合的,类编号,已知。每个样本为一个,元组,。有个属性用来判定某个训练样本的类编号,假设,S,中有,m,个类，总共,s,个训练样本，每个类,C,i,有,s,i,个样本,(,i,1,2,3.m,),，那么任意一个样本属于类,C,i,的概率是,s,i,/s,，那么用来分类一个给定样本的,期望信息,是：,信息增益,(1),一个有,v,个值的属性,Aa,1,a,2,.,a,v,可以将,S,分成,v,个子集,S,1,S,2,.,S,v,，其中,S,j,包含,S,中属性,A,上的值为,a,j,的样本。假设,S,j,包含类,C,i,的,s,ij,个样本。根据,A,的这种划分的期望信息称为,A,的,熵,A,上该划分的获得的信息增益定义为：,具有高信息增益的属性，是给定集合中具有高区分度的属性。所以可以通过计算,S,中样本的每个属性的信息增益，来得到一个属性的相关性的排序。,信息增益,(2),age,income,student,credit_rating,buys_computer,youth,high,no,fair,no,youth,high,no,excellent,no,middle_aged,high,no,fair,yes,senior,medium,no,fair,yes,senior,low,yes,fair,yes,senior,low,yes,excellent,no,middle_aged,low,yes,excellent,yes,youth,medium,no,fair,no,youth,low,yes,fair,yes,senior,medium,yes,fair,yes,youth,medium,yes,excellent,yes,middle_aged,medium,no,excellent,yes,middle_aged,high,yes,fair,yes,senior,medium,no,excellent,no,对于上述数据，可以略过步骤,1,，,2,步骤,3,，计算基于熵的度量,信息增益，作为样本划分的根据,Gain(age)=0.246,Gain(income)=0.029,Gain(student)=0.151,Gain(credit_rating)=0.048,然后，对测试属性每个已知的值，创建一个分支，并以此划分样本，得到第一次划分,判定归纳树算法示例,(1),判定归纳树算法示例,(2),判定归纳树算法示例,(3),age?,overcast,student?,credit rating?,no,yes,fair,excellent,youth,senior,no,no,yes,yes,yes,Middle aged,产生的决策树会出现过分适应数据的问题,由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常,对新样本的判定很不精确,防止过分适应的两种方法,先剪枝：通过提前停止树的构造,如果在一个节点划分样本将导致低于预定义临界值的分裂（,e.g.,使用信息增益度量）,选择一个合适的临界值往往很困难,后剪枝：由“完全生长”的树剪去分枝,对于树中的每个非树叶节点，计算该节点上的子树被剪枝可能出现的期望错误率,使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树,防止分类中的过分适应,可以提取决策树表示的知识，并以,IF-THEN,形式的分类规则表示,对从根到树叶的每条路径创建一个规则,沿着给定路径上的每个属性,-,值对形成规则前件（,IF,部分）的一个合取项,叶节点包含类预测，形成规则后件（,THEN,部分）,IF-THEN,规则易于理解，尤其树很大时,示例：,IF age=“youth”AND student=“no”THEN buys_computer=“no”,IF age=“youth”AND student=“yes”THEN buys_computer=“yes”,IF age=“middle_aged”THEN buys_computer=“yes”,IF age=“senior”AND credit_rating=“excellent”THEN buys_computer=“yes”,IF age=“senior”AND credit_rating=“fair”THEN buys_computer=“no”,由决策树提取分类规则,分类挖掘是一个在统计学和机器学习的领域也被广为研究的问题，并提出了很多算法，但是这些算法都是内存驻留的,可伸缩性问题：,要求以合理的速度对数以百万计的样本和数以百计的属性的进行分类挖掘,由大型数据库构造决策树,首先将样本划分为子集，每个子集可以放在内存中,然后由每个自己构造一颗决策树,输出的分类法将每个子集的分类法组合在一起,（其他方法包括,SLIQ,SPRINT,RainForest,等等）,可伸缩性与决策归纳树,贝叶斯分类,贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。,朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。,后向传播是一种神经网络学习算法；神经网络是一组连接的输入,/,输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。,优点,预测精度总的来说较高,健壮性好，训练样本中包含错误时也可正常工作,输出可能是离散值、连续值或者是离散或量化属性的向量值,对目标进行分类较快,缺点,训练（学习）时间长,蕴涵在学习的权中的符号含义很难理解,很难根专业领域知识相整合,后向传播分类,使用一种非线性的映射，将原训练数据映射到较高的维,一个数据被认为是,p,维向量，数据在这个,p,维向量空间中被分为两类；,SVM,的目的是找到一个,p-1,维的超平面，来划分,p,维向量空间的数据,在新的维上，它搜索线性最佳分离超平面,(,即将一类的元组与其他类分离的“决策边界”,),。,使用一个适当的对足够高维的非线性映射，两类的数据总可以被超平面分开。,SVM,使用支持向量（“基本”训练元组）和边缘（由支持向量定义）发现该超平面。,SVM,支持向量机,特点,:,训练时间非常长，但对复杂的非线性决策边界的建模能力是高度准确的（使用最大边缘）,可以用来预测和分类,应用,:,手写数字识别，对象识别，语音识别,以及基准时间序列预测检验,SVM-,特点和应用,SVM,一般原理,支持向量,小边缘,大边缘,06 May 2026,Data Mining:Concepts and Techniques,31,SVM,当数据是线性可分的时候,m,设给定的数据集,D,为,(,X,1,y,1,),(,X,|D|,y,|D|,),其中,X,i,是训练元组，具有相关联的类标号,yi,。,可以画出无限多条分离直线（或超平面）将类,+1,的元组与类,-1,的元组分开，我们想找出“最好的”那一条,(,对先前未见到的元组具有最小分类误差的那一条）。,SVM,要搜索具有最大边缘的超平面，即,最大边缘超平面,(MMH),k-,最临近分类,给定一个未知样本，,k-,最临近分类法搜索模式空间，找出最接近未知样本的,k,个训练样本；然后使用,k,个最临近者中最公共的类来预测当前样本的类标号,基于案例的推理,样本或案例使用复杂的符号表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例,遗传算法,结合生物进化思想的算法,粗糙集方法,模糊集方法,允许在分类规则中定义“模糊的”临界值或边界,其他分类方法,预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。,预测和分类的异同,相同点,两者都需要构建模型,都用模型来估计未知值,预测当中主要的估计方法是回归分析,线性回归和多元回归,非线性回归,不同点,分类法主要是用来预测类标号（分类属性值）,预测法主要是用来估计连续值（量化属性值）,什么是预测？,线性回归：,Y=,+X,其中,和,是回归系数，可以根据给定的数据点，通过最小二乘法来求得,多元回归：,Y=,+,1,X,1,+,2,X,2,线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的,，,1,和,2,非线性回归：,Y=,+,1,X,1,+,2,X,2,2,+,3,X,3,3,对不呈线性依赖的数据建模,使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解,线性回归、多元回归和非线性回归,导出分类法后，再使用训练数据评估分类法，可能错误的导致乐观的估计,保持方法,给定数据随机划分为两个集合：训练集,(2/3),和测试集,(1/3),训练集导出分类法，测试集对其准确性进行评估,随机子选样,：保持方法的一个变形，将保持方法重复,k,次，然后取准确率的平均值,k-,折交叉确认,初始数据被划分为,k,个不相交的，大小大致相同的子集,S,1,S,2,S,k,进行,k,次训练和测试，第,i,次时，以,S,i,做测试集，其他做训练集,准确率为,k,次迭代正确分类数除以初始数据集样本总数,评估分类法的准确性,Bagging,技术和,boosting,技术都通过将,T,个学习得到的分类法,C,1,C,2,C,T,组合起来，从而创造一个改进的分类法,C*,Bagging,技术,对训练集,S,进行,T,次迭代，每次通过放回取样选取样本集,S,t,，通过学习,S,t,得到分类法,C,t,对于未知样本,X,，每个分类法返回其类预测，作为一票,C*,统计得票，并将得票最高的预测赋予,X,Boosting,技术,每个训练样本赋予一个权值,C,t,的权值取决于其错误率,提高分类法的准确性,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
