数据挖掘分类和预测讲述

《数据挖掘分类和预测讲述》由会员分享，可在线阅读，更多相关《数据挖掘分类和预测讲述（37页珍藏版）》请在金锄头文库上搜索。

1、分类和预测 分类 VS. 预测 n分类和预测是两种数据分析形式，用于提取描 述重要数据类或预测未来的数据趋势 的模型 q分类： n预测类对象的分类标号（或离散值） n根据训练数据集和类标号属性，构建模型来分类现有数据 ，并用来分类新数据 q预测： n建立连续函数值模型 n比如预测空缺值，或者预测顾客在计算机设备上的花费 n典型应用 q欺诈检测、市场定位、性能预测、医疗诊断 分类和预测-示例 n分类 q银行贷款员需要分析数据，来弄清哪些贷款申请者 是安全的，哪些是有风险的（将贷款申请者分为“安 全”和“有风险”两类） n我们需要构造一个分类器来预测类属编号，比如预测顾客 属类 n预测 q银行贷款

2、员需要预测贷给某个顾客多少钱是安全的 n构造一个预测器，预测一个连续值函数或有序值，常用方 法是回归分析 数据分类一个两步过程 (1) n第一步，也成为学习步，目标是建立描述预先定义的 数据类或概念集的分类器 q分类算法通过分析或从训练集“学习”来构造分类器。 q训练集由数据库元组（用n维属性向量表示）和他们相 对应的类编号组成；假定每个元组属于一个预定义的类 n训练元组：训练数据集中的单个元组 q学习模型可以用分类规则、决策树或数学公式的形式提 供 数据分类一个两步过程 (2) n第二步，使用模型，对将来的或未知的对象进行分类 q首先评估模型的预测准确率 n对每个测试样本，将已知的类标号和该

3、样本的学习模型类预测 比较 n模型在给定测试集上的准确率是正确被模型分类的测试样本的 百分比 n测试集要独立于训练样本集，否则会出现“过分拟合”的情况 第一步建立模型 训练数 据集 分类算法 IF rank = professor OR years 6 THEN tenured = yes 分类规则 第二步用模型进行分类 分类规则 测试集 未知数据 (Jeff, Professor, 4) Tenured? 监督学习 VS. 无监督学习 n监督学习（用于分类） q模型的学习在被告知每个训练样本属于哪个类的“指 导”下进行 q新数据使用训练数据集中得到的规则进行分类 n无监督学习（用于聚类） q

4、每个训练样本的类编号是未知的，要学习的类集合 或数量也可能是事先未知的 q通过一系列的度量、观察来建立数据中的类编号或 进行聚类 数据预测的两步过程 n数据预测也是一个两步的过程，类似于前面描 述的数据分类 q对于预测，没有“类标号属性” q要预测的属性是连续值，而不是离散值，该属性可 简称“预测属性” nE.g. 银行贷款员需要预测贷给某个顾客多少钱是安全的 n预测器可以看作一个映射或函数y=f(X) q其中X是输入；y是输出，是一个连续或有序的值 q与分类类似，准确率的预测，也要使用单独的测试 集 准备分类和预测的数据 n通过对数据进行预处理，可以提高分类和预测过 程的准确性、有效性和可伸

5、缩性 q数据清理 n消除或减少噪声，处理空缺值，从而减少学习时的混乱 q相关分析 n数据中的有些属性可能与当前任务不相关；也有些属性可能是 冗余的；删除这些属性可以加快学习步骤，使学习结果更精确 q数据变换与归约 n数据可以通过规范化进行变换，将所给属性的所有值按比例进 行缩放，使其落入一个较小的指定区间，例 0.0, 1.0（ANN和 设计距离的度量方法中常用） n可以将数据概化到较高层概念 比较分类方法 n使用下列标准比较分类和预测方法 q预测的准确率：模型正确预测新数据的类编号的能 力 q速度：产生和使用模型的计算花销 q健壮性：给定噪声数据或有空缺值的数据，模型正 确预测的能力 q可伸

6、缩性：对大量数据，有效的构建分类器或预测 器的能力 q可解释性：学习模型提供的理解和洞察的层次 用决策树归纳分类 (1) n什么是决策树？ q类似于流程图的树结构 q每个内部节点表示在一个属性上的测试 q每个分枝代表一个测试输出 q每个树叶节点存放一个类编号 age? student? credit rating? noyes fairexcellent youth senior no no yes yes yes Middle aged 决策树： Buys_computer 用决策树归纳分类 (2) n使用决策树分类 q给定一个类标号未知的元组X，在决策树上测试元组的 属性值，跟踪一条由根到

7、叶节点的路径，叶节点存放该 元组的类预测。 q决策树容易转换为分类规则 n决策树的生成由两个阶段组成 q决策树构建 n使用属性选择度量来选择将元组最好的划分为不同的类的属性 n递归的通过选定的属性，来划分样本 （必须是离散值） q树剪枝 n决策树建立时，许多分枝反映的是训练数据中的噪声和离群点 点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类 的准确性 ageincomestudentcredit_ratingbuys_computer youthhighnofairno youthhighnoexcellentno middle_agedhighnofairyes seniormedi

8、umnofairyes seniorlowyesfairyes seniorlowyesexcellentno middle_agedlowyesexcellentyes youthmediumnofairno youthlowyesfairyes seniormediumyesfairyes youthmediumyesexcellentyes middle_agedmediumnoexcellentyes middle_agedhighyesfairyes seniormediumnoexcellentno 决策树归纳策略 (1) n输入 q数据划分D是训练元组和对应类标号的集合 qatt

9、ribute_list,候选属性的集合 qAttribute_selection_method，指定选择属性的启发性 过程 算法步骤 1.树以代表训练样本的单个节点（N）开始 2.如果样本都在同一个类，则该节点成为树叶，并用该 类标记 3.否则，算法调用Attribute_selection_method，选择能 够最好的将样本分类的属性；确定“分裂准则”，指出“ 分裂点”或“分裂子集”。 决策树归纳策略 (2) 4.对测试属性每个已知的值，创建一个分支， 并以此划分元组 5.算法使用同样的过程，递归的形成每个划分 上的元组决策树。一旦一个属性出现在一个 节点上，就不在该节点的任何子节点上出现

10、 6.递归划分步骤停止的条件 划分D（在N节点提供）的所有元组属于同一类 没有剩余属性可以用来进一步划分元组使用多数表决 没有剩余的样本 给定分支没有元组，则以D中多数类创建一个树叶 属性选择度量 n属性选择度量是一种选择分裂准则，将给定类 标号的训练元组最好的进行划分的方法 q理想情况，每个划分都是“纯”的，即落在给定划分 内的元组都属于相同的类 q属性选择度量又称为分裂准则 n常用的属性选择度量 q信息增益 q增益率 qGini指标 信息增益 (1) nS是一个训练样本的集合，该样本中每个集合 的类编号已知。每个样本为一个元组。有个属 性用来判定某个训练样本的类编号 n假设S中有m个类，总

11、共s个训练样本，每个类 Ci有si个样本(i1,2,3.m)，那么任意一个样 本属于类Ci的概率是si / s，那么用来分类一个 给定样本的期望信息是： 信息增益 (2) n一个有v个值的属性Aa1,a2,.,av可以将S分成v个子 集S1,S2,.,Sv，其中Sj包含S中属性A上的值为aj的样 本。假设Sj包含类Ci的sij个样本。根据A的这种划分的 期望信息称为A的熵 nA上该划分的获得的信息增益定义为： n具有高信息增益的属性，是给定集合中具有高区分度 的属性。所以可以通过计算S中样本的每个属性的信 息增益，来得到一个属性的相关性的排序。 ageincomestudentcredit_r

12、atingbuys_computer youthhighnofairno youthhighnoexcellentno middle_agedhighnofairyes seniormediumnofairyes seniorlowyesfairyes seniorlowyesexcellentno middle_agedlowyesexcellentyes youthmediumnofairno youthlowyesfairyes seniormediumyesfairyes youthmediumyesexcellentyes middle_agedmediumnoexcellentye

13、s middle_agedhighyesfairyes seniormediumnoexcellentno 判定归纳树算法示例 (1) n对于上述数据，可以略过步骤1，2 n步骤3，计算基于熵的度量信息增益，作 为样本划分的根据 qGain(age)=0.246 qGain(income)=0.029 qGain(student)=0.151 qGain(credit_rating)=0.048 n然后，对测试属性每个已知的值，创建一个分 支，并以此划分样本，得到第一次划分 判定归纳树算法示例 (2) 判定归纳树算法示例 (3) age? overcast student?credit rat

14、ing? noyesfairexcellent 40 nonoyesyes yes 30-40 防止分类中的过分适应 n产生的决策树会出现过分适应数据的问题 q由于数据中的噪声和孤立点，许多分枝反应的是训练数据中 的异常 q对新样本的判定很不精确 n防止过分适应的两种方法 q先剪枝：通过提前停止树的构造如果在一个节点划分样 本将导致低于预定义临界值的分裂（e.g. 使用信息增益度量 ） n选择一个合适的临界值往往很困难 q后剪枝：由“完全生长”的树剪去分枝对于树中的每个非 树叶节点，计算该节点上的子树被剪枝可能出现的期望错误 率 n使用一个独立的测试集来评估每颗树的准确率，就能得到具有 最小期

15、望错误率的决策树 由决策树提取分类规则 n可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示 n对从根到树叶的每条路径创建一个规则 n沿着给定路径上的每个属性-值对形成规则前件（“IF“部分）的一 个合取项 n叶节点包含类预测，形成规则后件（“THEN“部分） nIF-THEN规则易于理解，尤其树很大时 n示例： nIF age = “youth” AND student = “no” THEN buys_computer = “no” nIF age = “youth” AND student = “yes” THEN buys_computer = “yes” nIF age

16、= “middle_aged” THEN buys_computer = “yes” nIF age = “senior” AND credit_rating = “excellent” THEN buys_computer = “yes” nIF age = “senior” AND credit_rating = “fair” THEN buys_computer = “no” 可伸缩性与决策归纳树 n分类挖掘是一个在统计学和机器学习的领域也 被广为研究的问题，并提出了很多算法，但是 这些算法都是内存驻留的 n可伸缩性问题：要求以合理的速度对数以百万 计的样本和数以百计的属性的进行分类挖掘 n由大型数据库构造决策树 q首先将样本划分为子集，每个子集可以放在内存中 q然后由每个自己构造一颗决策树 q输出的分类法将每个子集的分类法组合在一起 q（其他方法包括SLIQ, SPRINT,RainForest等等） 贝叶斯分类 n贝叶斯分类利用统计学中的 贝叶斯定理，来预测类成员 的概率，即给定一个样本， 计算该样本属于一个特定