《分类和预测教案.ppt》由会员分享，可在线阅读，更多相关《分类和预测教案.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、分类和预测 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望分类 类标签属性的确定基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据(测试集)进行分类预测:对连续性字段进行建模和预测。典型应用信用评分目标市场定位医疗诊断治疗结果分析分类和预测2分类的两个步骤模型创建:描述一组预先确定的类每一条记录都属于一个预先定义的类别，我们使用类标签属性来标识类别。用于创建模型的数据集叫:训练集模型可以用分类规则，决策树，或者数学方程的形式来表达。模型使用:用
2、创建的模型预测未来或者类别未知的记录的类别估计模型的准确率使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较准确率是测试集中被正确分类的对象的比率测试集和训练集是独立的。3分类过程(1)：模型创建训练集分类算法IF rank=professorOR years 6THEN tenured=yes 模型4分类过程(2):使用模型模型测试集未知数据(Jeff,Professor,4)Tenured?5有监督和无监督学习有监督学习(分类)训练集是带有类标签的新的数据是基于训练集进行分类的。无监督学习(聚类)训练集的类标签未知。给定一组测度(度量)或观察，然后寻找出训练集中存在类别或者聚类
3、。6分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类用Excel来演示决策树用Matlab演示决策树7关于分类和预测的一些问题(1):数据准备数据清洗对数据进行预处理，消除噪音,处理缺失值。相关性分析(属性选择)去掉不相关或者冗余的属性数据转换规范化或者对数据进行标准化8关于分类和预测的问题(2):评估分类方法预测准确率速度创建速度使用速度强壮性处理噪音和丢失值伸缩性(规模化)对磁盘驻留数据的处理能力可解释性:对模型的可理解程度。规则好坏的评价决策树的大小分类规则的简明性9分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类用Excel来演示决策
4、树用Matlab演示决策树10使用决策树归纳进行分类决策树 一个类似流程图的树结构内部节点表示在一个属性上的测试每个分枝表示测试的结果叶子节点表示类或一个类分布决策树生成算法分成两个步骤树的创建初始时，所有的训练例子都在根节点根据被选属性,递归地对例子进行划分树的修剪识别并去掉那些反映噪音或者异常的分枝决策树使用:对未知样本进行分类对照决策树测试样本的属性值11训练集例子源自Quilan的ID3算法12输出输出:关于购买电脑的一棵决策树关于购买电脑的一棵决策树age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes3
5、0.4013决策树算法基本算法（贪心算法）树的建立是自上而下递归的分而治之的方法初始时，所有的训练例子都在根节点属性都是类别字段(如果是连续的，将其离散化)所有例子根据所选属性递归地进行划分属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain,信息增益)停止划分的条件给定节点的所有样本都属于同一个类没有剩余的属性可以用于进一步划分样本分枝没有样本可划分了14属性选择的统计度量Information gain(ID3/C4.5)所有属性都假定为类别型属性经过修改之后可以适用于连续型属性Gini index(IBM IntelligentMiner)（仅供参考）所
6、有属性都假定为连续型属性对每个属性假定存在着几种可能的拆分值可能需要利用其他的工具,如聚类,获得可能的拆分值可以修改,以适用于类别型属性15信息增益信息增益是一种基于熵的测度信息增益可定义如下:已知:被分好类的一组例子E(或称样本)E的一个划分P=E1,.,En ig(E,P)=entropy(E)-i=1,.,nentropy(Ei)*|Ei|/|E|16信息理论中的Shannon熵一般不确定性问題所包含“不确定”(uncertainty)的程度可以用数学來定量地描述吗?信息理论:Shannon熵,1940年代末硬币反正面的不确定性均匀不均匀数学描述17Shannon熵的数学描述假设样本空間
7、(Sample space)X 有 n 的基本事件(events)，其基本事件 wi 的概率为 pi,i=1,2,n。我們記之為 。,i=1,2,n 表示不确定性 18不确定性函数应满足的条件(i)对于固定的n,H是(p1,p2,pn)的连续函数(ii)对于pi=1/n,H应是n的单调递增函数(iii)若某一试验分解成多个相继的试验，则原先的 H 值应为相应的各个 H 值的加权和(weighted sum)。19图示20Shannon熵定理：定理：满足条件(i)、(ii)和(iii)的函数 H 恰好具有形式其中 K 为某个固定正常数。Shannon熵:由公式 定义的数,称为对应于样本空间(X,
8、p1,p2,pn)的熵21信息增益(Information Gain)原来的不确定性知道x之后的不确定性信息增益:原来-知道x之后的22信息增益(Information Gain)选择属性的标准：选择具有最高信息增益(Information Gain)的属性假设有两个类,P 和 N假设集合S中含有p个类别为P的样本,n个类别为N的样本将S中一个已知样本进行分类所需要的期望信息定义为:23信息增益在决策树中的使用假设使用属性A将把集合S划分成 V份 S1,S2,Sv 如果 Si 中包含 pi 个类别为 P的样本,ni 个类别为 N,的样本。那么熵就是(entropy),在A上进行分枝所获得的编码
9、信息为:24使用信息增益进行属性选择gClass P:buys_computer=“yes”gClass N:buys_computer=“no”gI(p,n)=I(9,5)=0.940gCompute the entropy for age:HenceSimilarly25例子(1)26例子(2)27例子(3)28Gini Index(IBM IntelligentMiner)集合T包含N个类别的记录，那么其Gini指标就是pj 类别j出现的频率如果集合T分成两部分 N1 and N2。那么这个分割的Gini就是具有最小Ginisplit 的属性就被选择用来拆分节点(对于每个属性都要列举所有
10、可能拆分点).29生成决策树的基本算法(1)算法 Generate_decision_tree(samples,attribute_list)输入:训练样本 samples,由离散值属性表示;候选属性的集合attribute_list.输出:一棵决策树算法:(1)创建节点N;(2)如果samples都属于同一个类C那么(3)返回N作为叶节点,以类C标记;(4)如果attribute_list为空则(5)返回N作为叶节点,将该叶节点标识为samples中最普遍的类30生成决策树的基本算法(2)(6)选择attribute_list中具有最高信息增益的属性test_attribute;(7)标记节
11、点N为test_attribute;(8)对于每个test_attribute中的已知值ai(9)由节点N长出一个条件为test_attribute=ai的分枝;(10)设si是Samples中test_attribute=ai的样本集合;(11)如果si为空则(12)加上一个树叶,标记为samples中最普遍的类;(13)否则 加上一个由Generate_decision_tree(si,attribute_list-test_attribute)返回的节点;31从树中生成分类规则用 IF-THEN 这种形式来表示规则对从根到叶节点的每条路径创建一条规则沿着一条路径的每个属性值对构成“并”连
12、接叶子节点中的类别就是所预测的类规则更容易被人们理解例子IF age=“=30”AND student=“no”THEN buys_computer=“no”IF age=“40”AND credit_rating=“excellent”THEN buys_computer=“yes”IF age=“=30”AND credit_rating=“fair”THEN buys_computer=“no”32在分类中避免过度适应(Overfit)所生成的树可能会过度适应于训练数据太多的分支,有些可能反映的是训练数据中的异常或噪音在进行预测的时候准确率比较差两种方法避免过度适应 预修剪:难点：选择一
13、个域值比较困难后修剪:先生成完整的树，然后进行修剪使用另外一个的一个测试集来决定哪个树最好33分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类用Excel来演示决策树用Matlab演示决策树34分类和预测什么是分类？什么是预测关于分类和预测的一些问题使用决策树进行分类用Excel来演示决策树用Matlab演示决策树35用Matlab演示决策树数据集说明Iris plant data:(150条记录)属性信息:1.sepal length in cm:萼片的长度(厘米)2.sepal width in cm:萼片的宽度(厘米)3.petal length in cm:花
14、瓣的长度(厘米)4.petal width in cm:花瓣的宽度(厘米)5.class:-Iris Setosa:蝴蝶花(鸢尾)长有刚毛的 -Iris Versicolour:杂色 -Iris Virginica:纯色共有数据:150条,4个输入属性,都是数值型的,一个输出属性(分类属性)是标称型(类别型)36写在后面的知识介绍网络蜘蛛与搜索引擎的基本原理搜索引擎的工作原理搜集信息网络蜘蛛整理信息接受查询37网络蜘蛛原理Web spider互联网-网蜘蛛-爬抓取多少呢？容量最大的搜索引擎也不过是抓取了整个网页数量的40%左右为什么？抓取技术？还是容量？38网络蜘蛛原理Web spider抓取
15、网页策略深度优先广度优先网站与网络蜘蛛会不会引起服务器负担过重？抓那些不抓那些？如何向网站表明自己的身份？GoogleBot,BaiDuSpider,Inktomi SlurpRobots.txt User-agent:*Disallow:39网络蜘蛛内容提取搜索引擎建立网页索引，处理的对象是文本文件，而对网络蜘蛛来说，抓取下来的网页包括各种形式：html,图片、doc、pdf、多媒体、动态网页等等如何把这些文件中的文本信息提取出来呢？Doc、pdf等文档，专业厂商提供文本提取借口Html等过滤多媒体、图片等：注释信息动态网络等：困难40网络蜘蛛更新周期Online还是offline?增量更新？更新周期多长？41