数据挖掘常用算法概述

1、关联分析关联分析关联规则挖掘的提出关联规则挖掘的提出l关联规则挖掘的典型案例：购物篮问题关联规则挖掘的典型案例：购物篮问题l在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将所购买的商品放入到自己的购物篮中。所购买的商品放入到自己的购物篮中。l通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯购买习惯l哪些物品经常被顾客购买？哪些物品经常被顾客购买？l同一次购买中，哪些商品经常会被一起购买？同一次购买中，哪些商品经常会被一起购买？l一般用户的购买过程中是否存在一定

2、的购买时间序列？一般用户的购买过程中是否存在一定的购买时间序列？l具体应用：利润最大化具体应用：利润最大化l商品货架设计：更加适合客户的购物路径商品货架设计：更加适合客户的购物路径l货存安排货存安排 ：实现超市的零库存管理：实现超市的零库存管理l用户分类用户分类 ：提供个性化的服务：提供个性化的服务其他典型应用其他典型应用l相关文献的收集相关文献的收集l购物篮购物篮 = 文档（文档（Document）l项项 目目 = 单词（单词（Word）l相关网站的收集相关网站的收集l购物篮购物篮 = 词句（词句（Sentences）l项项 目目 =链接文档（链接文档（Document）什么是关联规则挖掘什

3、么是关联规则挖掘? ?l关联规则挖掘关联规则挖掘l简单的说，关联规则挖掘发现大量数据中项集之间有简单的说，关联规则挖掘发现大量数据中项集之间有趣的关联趣的关联l在交易数据、关系数据或其他信息载体中，查找存在在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。性、或因果结构。l应用应用l购物篮分析、交叉销售、产品目录设计、购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。、聚集、分类等。关联规则挖掘形式化定义关联规则挖掘形式化定义l给定给定:l交易数据

4、库交易数据库 l每笔交易是：一个项目列表每笔交易是：一个项目列表 (消费者一次购买活动中购买的商消费者一次购买活动中购买的商品品)l查找查找: l所有描述一个项目集合与其他项目集合相关性的规则所有描述一个项目集合与其他项目集合相关性的规则l应用应用l* 护理用品护理用品 (商店应该怎样提高护理用品的销售？商店应该怎样提高护理用品的销售？)l家用电器家用电器 * (其他商品的库存有什么影响其他商品的库存有什么影响?)l在产品直销中使用附加邮寄在产品直销中使用附加邮寄其它相关概念其它相关概念l包含包含k个项目的集合，称为个项目的集合，称为k-项集项集l项集的出现频率是包含项集的事务个数，称为项集的

5、频率、支持计数项集的出现频率是包含项集的事务个数，称为项集的频率、支持计数或者计数或者计数l关联规则的基本形式：前提条件关联规则的基本形式：前提条件 结论结论 支持度支持度, 置信度置信度lbuys(x, “diapers”) buys(x, “beers”) 0.5%, 60%lmajor(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%关联规则兴趣度的度量值：支持度关联规则兴趣度的度量值：支持度l推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描述采用支持度、置信度概念。述采用支

6、持度、置信度概念。l支持度（支持度（Support）：规则）：规则XY在交易数据库在交易数据库D中的支持度是交易集中的支持度是交易集中包含中包含X和和Y的交易数与所有交易数之比，记为的交易数与所有交易数之比，记为support(XY)，即，即support(XY)=|T:X Y T，T D|/ |D|，它是概率，它是概率P（ X Y ），具），具体体表示为表示为：购买商品购买商品Y的交易的交易同时购买商品同时购买商品X和和Y的交易的交易购买商品购买商品X的交易的交易关联规则兴趣度的度量值：置信度关联规则兴趣度的度量值：置信度l置信度（置信度（Confidence），规则），规则XY在交易集中的

7、置信度是指包在交易集中的置信度是指包含含X和和Y的交易数与包含的交易数与包含X的交易数之比，记为的交易数之比，记为confidence(XY)，即即confidence(XY)=|T: X Y T，T D|/|T:X T，T D|，它，它是概率是概率P（ X|Y ），具体），具体表示为表示为：l最小支持度和最小置信度最小支持度和最小置信度用户（分析员）不关心可信程度太低的规则，因而用户需要输入用户（分析员）不关心可信程度太低的规则，因而用户需要输入两个参数：最小支持度和最小置信度。两个参数：最小支持度和最小置信度。购买商品购买商品Y的交易的交易同时购买商品同时购买商品X和和Y的交易的交易购买商

8、品购买商品X的交易的交易支持度和置信度举例支持度和置信度举例l零售商场销售分析：零售商场销售分析：l数据项为商品，记录集合为交易记录集合数据项为商品，记录集合为交易记录集合l规则为：规则为：“购买商品购买商品X的顾客，同时购买商品的顾客，同时购买商品Y”，即，即X Y；l设最小支持度为设最小支持度为0 .3；最小置信度也为；最小置信度也为0.3。l分析结果：分析结果： Item1 Item2 置置信信度度C 支支持持度度S A B 1 0.33 B A 0.33 0.33 B C 0.33 0.33 B D 0.66 0.66 C B 1 0.33 C D 1 0.33 D B 1 0.66

9、D C 0.5 0.33 交交易易号号 顾顾客客号号 商商品品号号 数数量量 日日期期 1 甲甲 A 14 3/4/95 甲甲 B 3 3/4/95 2 乙乙 C 2 5/6/95 乙乙 B 3 5/6/95 乙乙 D 13 5/6/95 3 乙乙 B 10 8/6/95 乙乙 D 12 8/6/95频繁项集及其基本特征频繁项集及其基本特征l频繁项集的定义频繁项集的定义l如果项集满足最小支持度，则称之为频繁项集（高频项集）如果项集满足最小支持度，则称之为频繁项集（高频项集）l频繁项集的基本特征频繁项集的基本特征l任何频繁项集的子集均为频繁项集。例如：任何频繁项集的子集均为频繁项集。例如：ABC

10、是频繁项集，则是频繁项集，则AB、AC、BC均为频繁项集均为频繁项集l在数据库表分区的情况下，一个项集是频繁的，则至少在一个分在数据库表分区的情况下，一个项集是频繁的，则至少在一个分区内是频繁的区内是频繁的关联规则挖掘的种类关联规则挖掘的种类l布尔布尔 vs. 数值型关联数值型关联 (基于基于 处理数据的类型处理数据的类型)l性别性别“女女” 职业职业“ 秘书秘书” 1%, 75% 布尔型关联规则布尔型关联规则 l性别性别“女女” 收入收入 = 2000 1%, 75% 数值型关联规则数值型关联规则 l单维单维 vs. 多维多维 关联关联lage(x, “30.39”) income(x, “

11、42.48K”) buys(x, “PC”) 1%, 75%lbuys(x, “Book”) buys(x, “Pen”) buys(x, “Ink”) 1%, 75%l单层单层 vs. 多层多层 分析分析l那个品种牌子的啤酒与那个牌子的尿布有关系那个品种牌子的啤酒与那个牌子的尿布有关系?l各种扩展各种扩展l相关性、因果分析相关性、因果分析l关联并不一定意味着相关或因果关联并不一定意味着相关或因果l最大模式和闭合相集最大模式和闭合相集l添加约束添加约束l如如, 哪些哪些“小东西小东西”的销售促发了的销售促发了“大家伙大家伙”的买卖？的买卖？关联规则挖掘的基本过程关联规则挖掘的基本过程l找出所有

12、的找出所有的频繁项集频繁项集 F，其中对于任何的其中对于任何的 Z F，在交易集合在交易集合D中至少中至少 s%的事务包含的事务包含Zl根据置信度和频繁项集根据置信度和频繁项集F, 产生关联规则。具体方法如下：产生关联规则。具体方法如下：lconf(X Y) = supp(X)/supp(X Y)l如果如果 conf(X Y) c 成立，则产生成立，则产生 X Y 的规则的规则, 因为因为:lsupp(X Y) = supp(X Y) s 且且lconf(X Y) cl因此关联规则的挖掘可以转换为频繁项集的挖掘和频繁项集之间的关联。因此关联规则的挖掘可以转换为频繁项集的挖掘和频繁项集之间的关联

13、。关联规则挖掘：一个例子关联规则挖掘：一个例子l对于对于 A C：lsupport = support(A 、C) = 50%lconfidence = support(A 、C)/support(A) = 66.6%交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度A75%B50%C50%A,C50%l最小值尺度最小值尺度 50%l最小可信度最小可信度 50%关联规则挖掘的优缺点关联规则挖掘的优缺点l优点优点l它可以产生清晰有用的结果它可以产生清晰有用的结果l它支持间接数据挖掘它支持间接数据挖掘l可以处理变长的数据可以处理变长的数据l它的计算的消耗

14、量是可以预见的它的计算的消耗量是可以预见的 l缺点缺点l当问题变大时，计算量增长得厉害当问题变大时，计算量增长得厉害l难以决定正确的数据难以决定正确的数据l容易忽略稀有的数据容易忽略稀有的数据查找频繁项集查找频繁项集 Apriori算法算法l查找具有最小支持度的频繁项集是关联规则挖掘最为重要的步骤查找具有最小支持度的频繁项集是关联规则挖掘最为重要的步骤lApriori算法是目前最有影响力的一个算法，在算法是目前最有影响力的一个算法，在1994年，由年，由R.Agrawal, S.Srikant提出提出l该算法基于频繁项集的特征：如果项集该算法基于频繁项集的特征：如果项集l = i1,i2,in

15、 是频繁的，当且是频繁的，当且仅当项集的所有子集均为频繁项集仅当项集的所有子集均为频繁项集.也就是说，如果也就是说，如果supp(l) s，当且仅，当且仅当当 supp(l ) s, l ll因此，我们可以采用层次顺序的方法来实现频繁项集的挖掘。首先，因此，我们可以采用层次顺序的方法来实现频繁项集的挖掘。首先，挖掘一阶频繁项集挖掘一阶频繁项集L1。在此基础上，形成二阶候选项集，挖掘二阶频繁。在此基础上，形成二阶候选项集，挖掘二阶频繁项集。依此类推。项集。依此类推。AprioriApriori算法算法l连接连接: 用用 Lk-1自连接得到自连接得到Ckl剪枝剪枝: 一个一个k-项集，如果它的一个

16、项集，如果它的一个k-1项集（它的子集项集（它的子集 ）不是频繁）不是频繁的，那他本身也不可能是频繁的。的，那他本身也不可能是频繁的。l伪代码伪代码:lCk: 长度为长度为k的候选项集的候选项集lLk :长度为长度为k的频繁项集的频繁项集lL1 = frequent items; for (k = 1; Lk !=; k+) do begin Ck+1 = 从从Lk 生成候选项集生成候选项集; 对于数据库中的任一交易对于数据库中的任一交易 t do 如果如果 t 中包含中包含 Ck+1中所包含的项集，则计数加中所包含的项集，则计数加 1 Lk+1 = Ck+1 中超过最小支持度的频繁项集中超过

17、最小支持度的频繁项集 end return k Lk;AprioriApriori算法算法 例子例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库数据库 Ditemset sup.1223334153itemset sup.12233353扫描扫描 DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2扫描扫描 DC3L3itemset2 3 5扫描扫描 Ditemset sup2 3 52Apriori

18、 Apriori 够快了吗够快了吗? ? 性能瓶颈性能瓶颈lApriori算法的核心算法的核心:l用频繁的用频繁的(k 1)-项集生成候选的频繁项集生成候选的频繁 k-项集项集l用数据库扫描和模式匹配计算候选集的支持度用数据库扫描和模式匹配计算候选集的支持度lApriori 的瓶颈的瓶颈: 候选集生成候选集生成l巨大的候选集巨大的候选集:l104 个频繁个频繁1-项集要生成项集要生成 107 个候选个候选 2-项集，并且累计和检项集，并且累计和检查它们的频繁性查它们的频繁性l要找长度为要找长度为100的频繁模式，如的频繁模式，如 a1, a2, , a100, 你必须你必须先产生先产生2100

19、 1030 个候选集个候选集l重复扫描数据库：重复扫描数据库：l如果最长的模式是如果最长的模式是n的话，则需要的话，则需要 (n +1 ) 次数据库扫描次数据库扫描关联规则结果显示关联规则结果显示 (Table Form )(Table Form )关联规则可视化关联规则可视化Using Rule GraphUsing Rule Graph扩展知识：多层关联规则扩展知识：多层关联规则l项通常具有层次项通常具有层次l底层的项通常支持度也低底层的项通常支持度也低l某些特定层的规则可能更有某些特定层的规则可能更有意义意义l交易数据库可以按照维或层交易数据库可以按照维或层编码编码l可以进行共享的多维挖

20、掘可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄TID ItemsT1111, 121, 211, 221T2111, 211, 222, 323T3112, 122, 221, 411T4111, 121T5111, 122, 211, 221, 413扩展知识：多维关联规则扩展知识：多维关联规则l单维关联规则（维内关联规则）单维关联规则（维内关联规则）l关联规则中仅包含单个谓词（维）关联规则中仅包含单个谓词（维）l通常针对的是事务数据库通常针对的是事务数据库 buys(X, “milk”) buys(X, “bread”)l多维关联规则：规则内包含多维关联规则：规则内包含2 个以

21、上维个以上维/谓词谓词l维间关联规则维间关联规则 (不重复谓词不重复谓词)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)l混合维关联规则混合维关联规则 (存在重复存在重复谓词谓词) age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)分类与预测分类与预测本章内容本章内容l分类与预测的基本概念分类与预测的基本概念l决策树分类决策树分类l实例：移动通信客户流失分析系统实例：移动通信客户流失分析系统l神经网络神经网络l其他分类方法其他分类方法l预测（回归）预测（回归）建立模型过程建立模型过程历史

22、数据历史数据模型模型建模建模记录集合记录集合预测预测数学公式数学公式规则集合规则集合l分类分类 l为一个事件或对象进行归类为一个事件或对象进行归类l预测分类标签（离散值）预测分类标签（离散值）l基于训练集形成一个模型，训练集中的类标签是已知的。使用基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类该模型对新的数据进行分类l分类模型：分类器（分类函数、分类规则等）分类模型：分类器（分类函数、分类规则等）l预测预测: l对连续或者有序的值进行建模和预测（回归方法）对连续或者有序的值进行建模和预测（回归方法） l典型应用典型应用l客户客户/用户分类用户分类l信用评分信用评

23、分l目标营销目标营销l医疗诊断医疗诊断l分类和预测分类和预测分类的相关概念分类的相关概念l训练集（训练集（Training Set）：由一组数据库记录或者元组构成，每个）：由一组数据库记录或者元组构成，每个记录由有关字段值组成特征向量，这些字段称为属性。记录由有关字段值组成特征向量，这些字段称为属性。l用于分类的属性称为标签属性。标签属性也就是训练集的类别标用于分类的属性称为标签属性。标签属性也就是训练集的类别标记。记。l标签属性的类型必须是离散的，而且标签属性的可能值的数目越标签属性的类型必须是离散的，而且标签属性的可能值的数目越少越好。少越好。分类的两个步骤分类的两个步骤l模型创建模型创建

24、: 对一个已经事先确定的类别创建模型对一个已经事先确定的类别创建模型l每个元组属于一个事先确定的类别，使用分类标签属性予以确定每个元组属于一个事先确定的类别，使用分类标签属性予以确定l用于创建模型的数据集叫用于创建模型的数据集叫: 训练集。单个元组称为训练样本训练集。单个元组称为训练样本l模型可以用分类规则，决策树，或者数学方程的形式来表达。模型可以用分类规则，决策树，或者数学方程的形式来表达。l模型使用模型使用: 用创建的模型预测未来或者类别未知的记录用创建的模型预测未来或者类别未知的记录l估计模型的准确率估计模型的准确率l使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较使用创

25、建的模型在一个测试集上进行预测，并将结果和实际值进行比较l准确率：准确率：l测试集和训练集是独立的。测试集和训练集是独立的。分类过程：模型创建（学习过分类过程：模型创建（学习过程）程）训练集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no分类算法IF rank = professorOR years 6THEN tenured = yes 模型分类过程分

26、类过程 : 使用模型使用模型模型测试集NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知数据(Jeff, Professor, 4)Tenured?本章内容本章内容l分类与预测的基本概念分类与预测的基本概念l决策树分类决策树分类l实例：移动通信客户流失分析系统实例：移动通信客户流失分析系统l神经网络神经网络l其他分类方法其他分类方法l预测预测（回归）（回归）使用决策树进行分类使用决策树进行分类l决策树决策树 l一个树型的

27、结构一个树型的结构l内部节点上选用一个属性进行分裂内部节点上选用一个属性进行分裂 （决策节点）（决策节点）l每个分叉都是分裂的一个部分每个分叉都是分裂的一个部分l叶子节点表示一个分布叶子节点表示一个分布l节点的子节点个数跟算法相关节点的子节点个数跟算法相关age?student?credit rating?noyesfairexcellent40nonoyesyesyes30.40决策树分类的特点决策树分类的特点l优点优点l容易生成可以理解的规则容易生成可以理解的规则l计算量相对来说不大计算量相对来说不大l可以处理离散和连续字段可以处理离散和连续字段l可以清晰显示哪些字段比较重要可以清晰显示哪

28、些字段比较重要l缺点缺点l对连续性的字段难以预测对连续性的字段难以预测l类别太多的时候，错误的可能性会加大类别太多的时候，错误的可能性会加大l一般情况下，标签属性的个数有限一般情况下，标签属性的个数有限决策树的生成与使用决策树的生成与使用l决策树生成算法分成两个步骤决策树生成算法分成两个步骤l树的生成树的生成l开始，数据都在根节点开始，数据都在根节点l递归的进行数据分割递归的进行数据分割l树的修剪树的修剪l去掉一些可能是噪音或者异常的数据去掉一些可能是噪音或者异常的数据l决策树使用决策树使用: 对未知数据进行分割对未知数据进行分割l按照决策树上采用的分割属性逐层往下，直到一个叶子节点按照决策树

29、上采用的分割属性逐层往下，直到一个叶子节点训练集训练集ageincome studentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnoID3算法决策树结果：决策树结果： “buys_computer”age?overcaststudent?credit rating?noyesfairexcellent

30、40nonoyesyesyes30.40决策树算法决策树算法l基本算法（贪心算法）基本算法（贪心算法）l自上而下分而治之的方法自上而下分而治之的方法l开始时，所有的数据都在根节点开始时，所有的数据都在根节点l属性都是种类字段属性都是种类字段 (如果是连续的，将其离散化如果是连续的，将其离散化)l所有记录用所选属性递归的进行分割所有记录用所选属性递归的进行分割l属性的选择是基于一个启发式规则或者一个统计的度量属性的选择是基于一个启发式规则或者一个统计的度量 (如如, information gain)l停止分割的条件停止分割的条件l一个节点上的数据都是属于同一个类别一个节点上的数据都是属于同一个

31、类别l没有属性可以再用于对数据进行分割没有属性可以再用于对数据进行分割几种经典算法介绍几种经典算法介绍lCARTl min(P(c1),P(c2)l 2P(c1)P(c2)l P(c1)logP(c1)+P(c2)logP(c2) C4.5(ID3)lC4.5(ID3)l对种类字段处理时，缺省是对每个值作为一个分割对种类字段处理时，缺省是对每个值作为一个分割lGain和和Gain RatiolCHAIDl在在Overfitting前停止树的生成前停止树的生成l必须都是分类属性必须都是分类属性l选择分割。选择分割。X2检验检验 从树中生成分类规则从树中生成分类规则l用用 IF-THEN 这种形式

32、来表现规则这种形式来表现规则l每个叶子节点都创建一条规则每个叶子节点都创建一条规则l每个分割都成为一个规则中的一个条件每个分割都成为一个规则中的一个条件l叶子节点中的类别就是叶子节点中的类别就是Then的内容的内容l规则对于人来说更容易理解规则对于人来说更容易理解l例子例子lIF age = “=30” AND student = “no” THEN buys_computer = “no”lIF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes”lIF age = “=30” AND credit_rat

33、ing = “fair” THEN buys_computer = “no”本章内容本章内容l分类与预测的基本概念分类与预测的基本概念l决策树分类决策树分类l实例：移动通信客户流失分析系统实例：移动通信客户流失分析系统l神经网络神经网络l其他分类方法其他分类方法l预测（回归）预测（回归）应用背景与问题定义应用背景与问题定义l背景背景l在移动通信领域，客户流失成为通信运营企业关注的焦点在移动通信领域，客户流失成为通信运营企业关注的焦点l通信业务产生的海量、珍贵数据为数据挖掘的研究提供了坚实通信业务产生的海量、珍贵数据为数据挖掘的研究提供了坚实的基础的基础l把数据挖掘理论应用于移动通信领域的客户流

34、失分析，进而为把数据挖掘理论应用于移动通信领域的客户流失分析，进而为通信企业的实际业务提供指导是一项具有挑战性的工作通信企业的实际业务提供指导是一项具有挑战性的工作l定义定义l客户流失分析，就是利用数据挖掘等分析方法，对已流失客户客户流失分析，就是利用数据挖掘等分析方法，对已流失客户过去一段时间的通话、缴费等信息进行分析，提炼出流失客户过去一段时间的通话、缴费等信息进行分析，提炼出流失客户的行为特征，利用这些特征预测在网客户的流失倾向的行为特征，利用这些特征预测在网客户的流失倾向 按真实比例抽取，可能掩盖流失用户的特征 解决方法：“样本放大”数据预处理数据预处理抽样抽样原始数据（流失概率3.2

35、%）采样后（流失概率25%）10,000310,000300,00050%20:15,00015,00020,000流失非流失数据预处理数据预处理时间相关属性时间相关属性属性序列S1用用户户标标识识性性别别年年龄龄入入网网品品牌牌 1 1月月份份通通话话时时长长2 2月月份份通通话话时时长长6 6月月份份通通话话时时长长 1 1月月份份话话费费 6 6月月份份话话费费是是否否流流失失属性序列Sn“静态”属性流失标志解决方法：生成汇总属性（求和、取均值等）生成“趋势属性”，如由属性序列S1生成属性“通话时长趋势”问题： 决策树算法缺乏处理时间相关属性的能力，致使效率下降数据预处理数据预处理生成趋

36、势属性生成趋势属性0200400600800100012001400160018002000123456月份通话时长用户1用户2把每个月通话时长Y视为月份X（取值从1到6）的线性函数，即Y = + X ，系数作为属性“通话时长趋势”的取值，从而把求趋势属性的问题转化为简单的线形回归问题，siisiiixxyyxx121)()(数据预处理数据预处理生成趋势属性（续）生成趋势属性（续）siiisiiiixxwyyxxw121)()(实际应用中，发现各个月份的数值对趋势属性的影响不同，可以对各个月份指定不同的权重w作为新生成的趋势属性，可以进一步转换成离散值，如，显著上升、小幅上升、持平、小幅下降、

37、显著下降例如：1到6月份权重分别取1、1、1、2、3、4决策树示例决策树示例通话次数=20品牌话费金额神州行全球通 流失=25 流失 非流失 非流失用户用户ID通话次数通话次数品牌品牌话费金额话费金额流失标志流失标志139*88423全球通全球通23品牌 非流失神州行全球通第一步：建立决策树第二步：预测流失流失20,80 0.2通话次数=20品牌消费金额神州行10,30 0.2510,50 0.167全球通2,23 0.088,7 0.53=254,36 0.1品牌6,14 0.3神州行全球通1,8 0.115,6 0.45Cx,y k%x:流失用户数y:未流失用户数k:流失概率 k = x/

38、(x+y)A决策树算法决策树算法数据结构数据结构主要内容主要内容l分类与预测的基本概念分类与预测的基本概念l决策树分类决策树分类l实例：移动通信客户流失分析系统实例：移动通信客户流失分析系统l神经网络神经网络l其他分类方法其他分类方法l预测预测（回归）（回归）神经网络技术神经网络技术l生物神经系统的计算模拟生物神经系统的计算模拟 (实际上是一个很好的学习系统的例子实际上是一个很好的学习系统的例子)l海量并行计算技术使得性能大大提高海量并行计算技术使得性能大大提高l最早的神经网络算法为最早的神经网络算法为 1959由由Rosenblatt提出提出l基本结构基本结构神经元结构神经元结构 k-f加权

39、和加权和输入输入向量向量X输出输出 y激活函数激活函数权重权重向量向量 ww0w1wnx0 x1xn)sign(yExampleFor n0ikiixw多层感知系统多层感知系统Output nodesInput nodesHidden nodesOutput vectorInput vector: xiwijijiijjOwIjIjeO11)(1 (jjjjjOTOOErrjkkkjjjwErrOOErr)1 (ijijijOErrlww)(jjjErrl)(计算实例计算实例l一个训练样本一个训练样本X=1,0,1,输出为输出为1lX1=1,x2=0,x3=1,w14=0.2,w15=-0.3

40、,w24=0.4,w25=0.1,w34=-.5,w35=0.2,w46=-0.3,w56=-0.2,l偏置值偏置值:节点节点4:-0.4,节点节点5:0.2,节点节点6:0.1l学习率设为学习率设为0.9l节点节点4:输入值输入值:w14*x1+w24*x2+w34*x3+节点节点4的偏置的偏置=1*0.2+0.4*0-0.5*1-0.4=-0.7输出值输出值: 可得可得0.332l同理同理: 节点节点5输入值输入值0.1,输出值输出值0.525l节点节点6: 输入值输入值:w46*o4+w56*o5+节点节点6的偏置的偏置=-0.3*0.332-0.2*0.525+0.1=-0.105输出

41、值输出值:0.474计算实例计算实例误差计算误差计算l节点节点6:0.474*(1-0.474)*(1-0.474)=0.1311l节点节点5:0.525*(1-0.525)*0.1311*(-0.2)=-0.0065l同理节点同理节点4误差为误差为:-0.0087)(1 (jjjjjOTOOErrjkkkjjjwErrOOErr)1(更新权值和偏置值更新权值和偏置值lW46:-0.3+(0.9)(0.1311)(0.332)=-0.261l其他其他Wij同理同理l节点节点6的偏置的偏置:0.1+(0.9)*(0.1311)=0.218l其他偏置同理其他偏置同理ijijijOErrlww)(j

42、jjErrl)(终止条件终止条件l对所有样本作一次扫描称为一个周期对所有样本作一次扫描称为一个周期l终止条件终止条件:对前一周期所有对前一周期所有Wij的修改值都小于某个指的修改值都小于某个指定的阈值定的阈值;或超过预先指定的周期数或超过预先指定的周期数.l防止训练过度防止训练过度前馈神经网络前馈神经网络l前馈网络的表达能力l布尔函数。任何布尔函数可以被具有两层单元的网络准确表示，尽管对于最坏的情况，所需隐藏单元的数量随着网络输入数量的增加指数级增长。 l连续函数。任何有界的连续函数可以由一个两层的网络以任意小的误差逼近。这个理论适用于隐藏层使用sigmoid单元、输出层使用（非阈值的）线性单

43、元的网络。所需的隐藏单元数量依赖于要逼近的函数。l任意函数。任意函数可以被一个有三层单元的网络以任意精度逼近。与前面相同，输出层使用线性单元，两个隐藏层使用sigmoid单元，每一层所需的单元数量一般不确定。神经网络特点神经网络特点l优点优点l有很强的非线性拟合能力，可映射任意复杂的非线性关系。有很强的非线性拟合能力，可映射任意复杂的非线性关系。l学习规则简单，便于计算机实现。学习规则简单，便于计算机实现。l具有很强的鲁棒性、记忆能力以及强大的自学习能力。具有很强的鲁棒性、记忆能力以及强大的自学习能力。 l缺点缺点l最严重的问题是没能力来解释自己的推理过程和推理依据。最严重的问题是没能力来解释

44、自己的推理过程和推理依据。l不能向用户提出必要的询问，而且当数据不充分的时候，不能向用户提出必要的询问，而且当数据不充分的时候，神经网络就无法进行工作。神经网络就无法进行工作。 l把一切问题的特征都变为数字，把一切推理都变为数值计把一切问题的特征都变为数字，把一切推理都变为数值计算，其结果势必是丢失信息。算，其结果势必是丢失信息。l理论和学习算法还有待于进一步完善和提高。理论和学习算法还有待于进一步完善和提高。 应用应用l适合神经网络学习的问题适合神经网络学习的问题 l实例是用很多实例是用很多“属性属性-值值”对表示的。对表示的。 l目标函数的输出可能是离散值、实数值或者由若干目标函数的输出可

45、能是离散值、实数值或者由若干实数属性或离散属性组成的向量。实数属性或离散属性组成的向量。 l训练数据可能包含错误。训练数据可能包含错误。 l可容忍长时间的训练。可容忍长时间的训练。 l可能需要快速求出目标函数值。可能需要快速求出目标函数值。 l人类能否理解学到的目标函数是不重要的。人类能否理解学到的目标函数是不重要的。实验实验l使用使用Clementine进行神经网络分类挖掘进行神经网络分类挖掘（工具使用参见补充教材）（工具使用参见补充教材）主要内容主要内容l分类与预测的基本概念分类与预测的基本概念l决策树分类决策树分类l实例：移动通信客户流失分析系统实例：移动通信客户流失分析系统l神经网络神

46、经网络l其他分类方法其他分类方法l预测预测（回归）（回归）其它分类方法其它分类方法l贝叶斯（贝叶斯（Bayesian）分类）分类lk-临近分类临近分类l基于案例的推理基于案例的推理l遗传算法遗传算法l粗糙集理论粗糙集理论l模糊集方法模糊集方法分类的准确性：评估错误率分类的准确性：评估错误率l数据分区数据分区:训练训练-测试数据测试数据l将一个数据集合分成两个独立的数据集。例如：将一个数据集合分成两个独立的数据集。例如：训练数据训练数据 (2/3), 测试数据测试数据(1/3)l通常应用于大量数据样本的数据集通常应用于大量数据样本的数据集l交叉验证交叉验证l将一个数据集合分成若干个子样本集将一个

47、数据集合分成若干个子样本集l用用k-1个子样本作为训练数据，个子样本作为训练数据，1个子样本作为个子样本作为测试数据测试数据l每一个数据集合具有合适的宽度每一个数据集合具有合适的宽度分类的准确性：混淆矩阵分类的准确性：混淆矩阵l混淆矩阵（混淆矩阵（confusion matrix ）用来作为分类规则特征）用来作为分类规则特征的表示，它包括了每一类的样本个数，包括正确的和错误的表示，它包括了每一类的样本个数，包括正确的和错误的分类。的分类。l主对角线给出了每一类正确分类的样本的个数，非对角线主对角线给出了每一类正确分类的样本的个数，非对角线上的元素则表示未被正确分类的样本个数上的元素则表示未被正

48、确分类的样本个数实际的类实际的类预预测测的的类类A A类类B B类类C C类类总计总计A A类类4545235050B B类类10383825050C C类类4640405050总计总计5959464645451501503个类的混淆矩阵个类的混淆矩阵分类的准确性：收益图分类的准确性：收益图查全率分析图：X轴：按离网倾向评分从大到小排序后的客户占目标客户人数的百分比；Y轴：前x%的客户中被准确预测为离网的客户占目标客户中离网总人数的百分比，即查全率。 Lift分析图：X轴：按离网倾向评分从大到小排序后的客户占目标客户人数的百分比；Y轴：命中率的提升倍数。 聚类分析聚类分析聚类分析聚类分析l什么

49、是聚类分析什么是聚类分析?l划分方法（划分方法（Partitioning Methods）l分层方法分层方法l基于密度的方法基于密度的方法l异常分析异常分析什么是聚类分析什么是聚类分析? ?l簇（簇（Cluster）:一个数据对象的集合一个数据对象的集合l在同一个簇中，对象之间具有尽可能大的相似性；在同一个簇中，对象之间具有尽可能大的相似性；l不同簇的对象之间具有尽可能大的相异性。不同簇的对象之间具有尽可能大的相异性。l聚类分析聚类分析l把一个给定的数据对象集合分成不同的簇，即把一个给定的数据对象集合分成不同的簇，即“ 物以类聚物以类聚 ”；l聚类是一种无监督分类法聚类是一种无监督分类法: 没

50、有预先指定的类别标识；没有预先指定的类别标识；l典型的应用典型的应用l作为一个独立的分析工具，用于了解数据的分布；作为一个独立的分析工具，用于了解数据的分布； l作为其它算法的一个数据预处理步骤；作为其它算法的一个数据预处理步骤；应用聚类分析的例子应用聚类分析的例子l市场销售市场销售: 帮助市场人员发现客户数据库中不同群体，然后利用这些知识帮助市场人员发现客户数据库中不同群体，然后利用这些知识来开展一个目标明确的市场计划；来开展一个目标明确的市场计划；l土地使用土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区；在一个陆地观察数据库中标识那些土地使用相似的地区；l保险保险: 对购买了

51、汽车保险的客户，标识那些有较高平均赔偿成本的客户；对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；l城市规划城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅；根据类型、价格、地理位置等来划分不同类型的住宅；l地震研究地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类；根据地质断层的特点把已观察到的地震中心分成不同的类；如何评价一个好的聚类方法如何评价一个好的聚类方法? ?l一个好的聚类方法要能产生高质量的聚类结一个好的聚类方法要能产生高质量的聚类结果果簇，这些簇具备以下两个特征：簇，这些簇具备以下两个特征：l簇内极大相似性簇内极大相似性l簇间极小相似性簇间极小相

52、似性 l聚类结果的好坏取决于该聚类方法采用的相似聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；性评估方法以及该方法的具体实现；l聚类方法的好坏还取决与该方法是能发现某些聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；还是所有的隐含模式；聚类分析中的数据类型聚类分析中的数据类型l如何度量对象间的距离？如何度量对象间的距离？l欧几里德距离 l曼哈顿距离 l明考斯基距离聚类分析聚类分析l什么是聚类分析什么是聚类分析?l划分方法（划分方法（Partitioning Methods）l分层方法分层方法l基于密度的方法基于密度的方法l异常分析异常分析 划分方法划分方法

53、: 基本概念基本概念l划分方法划分方法: 将一个包含将一个包含n个数据对象的数据库组织成个数据对象的数据库组织成k个个划分（划分（k=n），其中每个划分代表一个簇（），其中每个划分代表一个簇（Cluster）。）。l给定一个给定一个k，要构造出，要构造出k个簇，并满足采用的划分准则：个簇，并满足采用的划分准则：l全局最优全局最优:尽可能的列举所有的划分；尽可能的列举所有的划分；l启发式方法启发式方法: k-均值和均值和k-中心点算法中心点算法lk-均值均值 (MacQueen67):由簇的中心来代表簇；由簇的中心来代表簇；lk-中心点或中心点或 PAM (Partition around me

54、doids) (Kaufman & Rousseeuw87): 每个簇由簇中的某个每个簇由簇中的某个数据对象来代表。数据对象来代表。 K-均值算法均值算法l给定给定k，算法的处理流程如下，算法的处理流程如下:1.随机的把所有对象分配到随机的把所有对象分配到k个非空的簇中；个非空的簇中；2.计算每个簇的平均值，并用该平均值代表相应的计算每个簇的平均值，并用该平均值代表相应的簇；簇；3.将每个对象根据其与各个簇中心的距离，重新分将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；配到与它最近的簇中； 4.回到第二步，直到不再有新的分配发生。回到第二步，直到不再有新的分配发生。K-均值算法图示均值算法图示0123456789100123456789100123456789100123456789100123456789100123456