商业智能技术

《商业智能技术》由会员分享，可在线阅读，更多相关《商业智能技术（183页珍藏版）》请在金锄头文库上搜索。

1、1 数据挖掘技术数据挖掘技术 赵卫东博士 复旦大学软件学院 2 分类和预测分类和预测 3 分类分类 对离散数据的分类称为分类，对数值数据的分类称为预 测。 分类要解决的问题是为一个事件或对象归类，即确定一个 特定的对象属于哪一类。分类函数或分类模型分类函数或分类模型(分类器分类器) 分类模型是通过那些已知历史数据训练出来的。 这里用于建立模型的数据称为训练集，通常是已经掌握的历 史数据。 在训练集中每个对象都赋予一个类别的标记，不同的类别具 有不同的标记。 分类就是通过分析训练集（决策表）中的数据，为每个类 别做出准确的描述或建立分析模型或挖掘出分类规则，然 后用这个分类规则对其它数据对象进行

2、分类。 4 决策树决策树 判定树分类算法 output 训练集 决策树 input 新数据 分类 5 使用决策树进行分类使用决策树进行分类 决策树 一个树形的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分类 决策树生成算法分成两个步骤 树的生成 开始，数据都在根节点 递归的进行数据分片 树的修剪：去掉一些可能是噪音或者异常的数据 决策树使用: 对未知数据进行分割 按照决策树上采用的分割属性逐层往下，直到叶子节点 6 决策树算法决策树算法 基本算法（贪心算法） 自上而下分而治之的方法 开始时所有的实例都在根节点 属性都是分类型 (如果是连续的，将其离散化)

3、所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如信息增 益) 停止分割的条件 一个节点上的实例都属于同一个类别； 没有属性可以再用于对数据进行分割 7 属性选择的统计度量属性选择的统计度量 信息增益Information gain (ID3/C5.0) 所有属性假设都是分类型字段 经过修改之后可以适用于数值型字段 信息增益率（C4.5) 基尼指数Gini index (IBM Intelligent Miner) 能够适用于分类和数值字段 2检验(CHAID) 其他 8 信息增益信息增益(ID3) 任意样本分类的期望信息： I(s1,s2,sm)=Pi

4、log2(pi) (i=1.m) 其中，数据集为S，m为S的分类数目， Pi Ci为某分类标号，Pi为任意样本属于Ci的概率，si为分 类Ci上的样本数 由A划分为子集的熵： E(A)= j(|s1j|+ +|smj|)/|s| * I(s1j， ，smj) A为属性，具有V个不同的取值 信息增益：Gain(A)= I(s1,s2,sm) E(A) | | S Si 9 训练集训练集 ageincome studentcredit_ratingbuys_computer =30highnofairno 40mediumnofairyes 40lowyesfairyes 40lowyesexce

5、llentno 3140lowyesexcellentyes =30mediumnofairno 40mediumyesfairyes 40mediumnoexcellentno 10 使用信息增益进行属性选择使用信息增益进行属性选择 Class P: buys_computer = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age: Hence Similarly agepiniI(pi, ni) 40320.971 971.0)2, 3( 14 5 )0 ,4(

6、14 4 )3 ,2( 14 5 )( I IIageE 048. 0)_( 151. 0)( 029. 0)( ratingcreditGain studentGain incomeGain )(),()(ageEnpIageGain 0.694 11 分枝分枝 12 决策树决策树 age? overcast student?credit rating? noyesfairexcellent 40 nonoyesyes yes 30.40 13 决策树在犯罪分析中的应用决策树在犯罪分析中的应用 有无固定 职业 家庭经济 状 况 年龄文化程度有无特长社会关系 犯 罪 记录 违法 记录 家庭 和

7、睦 状况 犯罪 记录 次数 是否 经常 赌博 犯罪程度有无固定 职业 家庭经济 状 况 年龄文化程度有无特长社会关系 犯 罪 记录 违法 记录 家庭 和睦 状况 犯罪 记录 次数 是否 经常 赌博 犯罪程度 无差30-40初中否有差有4是严重 有中20-30中专否无差无0是较轻 有差40初中有有差无2是严重 有差20-30高中有有中有6是严重 有差20-30中专否无中有1否较轻 有差30-40大专有有差无3是严重 无中20初中有无好有5是严重 无差20-30初中否有差无0否严重 有好40小学否有中无2否严重 无差40初中否无差无0否严重 无差30-40高中否无好无4否较轻 无好20-30中专有

8、无差有2否较轻 14 犯罪潜在风险决策树犯罪潜在风险决策树 15 典型的分类树典型的分类树 (规则）规则） 典型的分类树典型的分类树 (决策树）决策树） 16 信息增益率信息增益率 C4.5算法继承了ID3算法的优点，算法基本过程与ID3算法相似， 但在选择决策树的分枝属性时用信息增益率选择属性，克服了选 择属性时信息增益偏向选择取值种类较多的属性的不足。 属性A信息增益率的定义为： 式中v为属性A的不同取值 的个数，从中可以看出，当v比较大 时， 就会降低增益率。 17 18 基尼指数（基尼指数（Gini Index） 集合T包含n个类别的记录，那么其Gini指数就是 pj类别j出现的频率

9、如果集合T分成两部分N1and N2。那么这个分割的Gini就是 提供最小Ginisplit就被选择作为分割的标准. n j p j Tgini 1 2 1)( )()()( 2 2 1 1 T gini N N T gini N N T gini split 19 过拟合问题过拟合问题 训练数据 测试数据 此处剪枝 决策树深度 错误率 剪枝剪枝 避免过拟合 决策树泛化 20 Pruning Tree 目的： 消除决策树的过拟合(Over Fitting)问题 实质：消除训练集中的异常和噪声 两种方法： 先剪枝法(Public 算法) 后剪枝法(Sprint 算法) 21 误分类率误分类率 C

10、1C2C3 C10r12r13 C2r210r23 C3r31r320 实际类别 分类类别 Cost (or loss) matrix 22 决策树算法的可伸缩性决策树算法的可伸缩性 ID3、C4.5等算法对规模较小，可以一次放入内存的训练样本集很有效， 但实际上数以百万计样本的超大型训练集是常见的，大多数情况下无法把 训练样本集全部放入内存，导致这些算法的有效性降低。因此需要增加可 伸缩的方法以节省空间。 IBM的研究人员运用一些特殊数据结构，例如属性表和类表，在1996年提 出了一种快速的、可伸缩的SLIQ算法，可以处理离散属性和连续属性。 SLIQ算法首先把训练样本集划分成若干子集，使每

11、一个子样本集都能放入 内存，然后对每个子样本集分别构造一棵决策树，再把这些决策树综合， 得到最终决策树。SLIQ 算法可以处理大规模的训练样本集，具有较好的 伸缩性。与传统决策树算法相比，减少了运行时间。SLIQ算法在执行过程 中需要随时修改类表，类表常驻内存，而类表的大小会随着训练样本集的 增大而增大，因此SLIQ算法对内存容量有一定的要求。 23 常用的决策树算法常用的决策树算法 ID3, C4.5, C5.0算法 CART （C for (k= 1; Lk!=; k+) do begin Ck+1= candidates generated from Lk; for each trans

12、action tin database do increment the count of all candidates in Ck+1 that are contained in t Lk+1= candidates in Ck+1with min_support end return kLk; 108 项集格项集格 109 如何生成候选集如何生成候选集 假定Lk-1中的项按顺序排列 第一步: 自连接Lk-1 insert intoCk select p.item1, p.item2, , p.itemk-1, q.itemk-1 fromLk-1p, Lk-1 q wherep.item1

13、=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 5 112 Apriori 算法在超市的应用Apriori 算法在超市的应用 某日超市的购物记录 交易时间购买商品交易时间购买商品 14：25i1，i2，i4 15：07i1，i2，i3 16：33i2，i3 17：05i1，i3 18：40i1，i2，i3，i5 18：55i2，i3 19：26i1，i2，i5 19：52i2，i4 20：03i1，i2，i3 20：16i1，i3 i1，i5i2 i2，i5 i1 ； i5 i1，i2 113 IBM SPSS Modeler构建关联模型IBM SPSS

14、Modeler构建关联模型 114 Apriori 性能瓶颈Apriori 性能瓶颈 Apriori算法的核心: 用频繁的(k 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成 巨大的候选集: 多次扫描数据库： 如果最长的模式是n的话，则需要 n +1次数据库扫描 115 布尔型和数值型关联规则布尔型和数值型关联规则 根据处理的项目类别，关联规则可以分为布尔型和数值型。布尔 型关联规则处理的项目都是离散的，它显示了这些变量之间的关 系。例如性别=“女”职业=“秘书”，是布尔型关联规则。而数值 型关联规则可以和多维关联或多层关联规

15、则结合起来。对数值型 属性进行处理，参考连续属性离散化方法或统计方法把其进行分 割，确定划分的区间个数和区间宽度。数值型关联规则中也可以 包含可分类型变量。例如性别=“女”平均收入2300，这里的 收入是数值类型，所以是一个数值型关联规则。又如，age(x， 30，39) income(x，42，48) buys(x，“PC”) 1%， 75%。这里的项目用谓词表示，其中x是变量，泛指顾客，表 示逻辑与。 116 多层关联规则多层关联规则 项通常具有层次。 底层的项通常支持度也 低。 某些特定层的规则可能 更有意义。 交易数据库可以按照维 或层编码。 可以进行共享的多维挖 掘。 食品 面包牛奶

16、 脱脂奶 光明统一 酸奶白黄 TID Items T1111, 121, 211, 221 T2111, 211, 222, 323 T3112, 122, 221, 411 T4111, 121 T5111, 122, 211, 221, 413 117 挖掘多层关联规则挖掘多层关联规则 自上而下，深度优先的方法： 先找高层的“强”规则： 牛奶面包 20%, 60%. 再找他们底层的“弱”规则： 酸奶黄面包 6%, 50%. 多层关联规则的变种 层次交叉的关联规则： 酸奶复旦面包房 黄面包 不同种分层方法间的关联规则： 酸奶复旦面包房面包 118 多层关联：冗余过滤多层关联：冗余过滤 由于“祖先”关系的原因，有些规则可能是多余的。 例子 牛奶白面包support = 8%, confidence = 70% 酸奶白面包 support = 2%, confidence = 72% 第一个规则是第二个规则的祖先 参考规则的祖先，如果它的支持度与“预期”的支持度近 似的