数据挖掘技术方法(P151).ppt

《数据挖掘技术方法(P151).ppt》由会员分享，可在线阅读，更多相关《数据挖掘技术方法(P151).ppt（150页珍藏版）》请在装配图网上搜索。

1、商务智能 数据挖掘技术 分类和预测 分类 对离散数据的分类称为分类，对数值数据的分类称为预测。 分类要解决的问题是为一个事件或对象归类，即确定一个 特定的对象属于哪一类。 分类函数或分类模型 (分类器 ) 分类模型是通过那些已知历史数据训练出来的。 这里用于建立模型的数据称为训练集，通常是已经掌握的历 史数据。 在训练集中每个对象都赋予一个类别的标记，不同的类别具 有不同的标记。 分类就是通过分析训练集中的数据，为每个类别做出准确 的描述或建立分析模型或挖掘出分类规则，然后用这个分 类规则对其它数据对象进行分类。 分类规则实例 低风险 收入 ￥ 40,000 工作时间 5年 高负债 高风险 高

2、风险 低风险 否 否 否 是 是 是 If 收入 ￥ 40,000 而且工作时间 5年 then低风险 分类数据 The data used to build a classification model consists of A set of records. Each record has the same number of fields. One field in these record contains indicators of classes which records belong to. This field is called target field. Other f

3、ields are called independent fields which describe the individual objects represented by the records. 决策表实例 A g e S e x BP C h o l e s t e r o l Na K D r u g 25 F H I G H H I G H 0 . 6 7 5 9 9 6 0 . 0 7 4 8 3 4 d r u g A 17 F H I G H H I G H 0 . 5 3 9 7 5 6 0 . 0 3 0 0 8 1 d r u g Y 23 M L O W N O R

4、 M A L 0 . 5 5 6 4 5 3 0 . 0 3 6 1 8 d r u g Y 24 M N O R M A L N O R M A L 0 . 8 4 5 2 3 6 0 . 0 5 5 4 9 8 d r u g Y 74 F L O W H I G H 0 . 8 4 9 6 2 4 0 . 0 7 6 9 0 2 d r u g C 40 F N O R M A L H I G H 0 . 6 7 6 8 3 0 . 0 4 9 6 3 4 d r u g X 32 F H I G H H I G H 0 . 5 8 1 6 6 4 0 . 0 2 4 8 0 3 d r

5、 u g Y 70 M L O W H I G H 0 . 7 1 6 3 5 9 0 . 0 3 6 9 3 6 d r u g Y 64 M H I G H N O R M A L 0 . 6 4 0 7 8 9 0 . 0 7 8 3 0 2 d r u g B 45 M H I G H H I G H 0 . 6 6 4 1 0 5 0 . 0 4 7 8 1 9 d r u g A 33 F L O W N O R M A L 0 . 8 2 1 8 0 5 0 . 0 2 7 6 7 4 d r u g Y 74 F L O W N O R M A L 0 . 7 7 2 2 2

6、5 0 . 0 4 7 9 4 d r u g Y 73 M H I G H N O R M A L 0 . 7 9 2 1 3 1 0 . 0 6 2 1 7 1 d r u g B 38 F L O W H I G H 0 . 7 9 4 3 1 8 0 . 0 5 1 8 2 5 d r u g Y 72 F H I G H N O R M A L 0 . 5 3 3 5 5 8 0 . 0 2 1 2 8 9 d r u g Y 27 F H I G H N O R M A L 0 . 5 5 5 0 6 4 0 . 0 4 6 6 5 d r u g A 62 M H I G H N

7、 O R M A L 0 . 5 1 0 1 5 0 . 0 7 1 4 6 3 d r u g B 72 M H I G H N O R M A L 0 . 8 1 9 4 8 3 0 . 0 7 3 8 0 2 d r u g B 19 M H I G H N O R M A L 0 . 5 5 2 7 0 1 0 . 0 3 2 5 9 8 d r u g Y 28 M H I G H H I G H 0 . 5 8 4 0 3 9 0 . 0 6 8 3 7 5 d r u g A 54 M N O R M A L N O R M A L 0 . 6 0 5 6 2 9 0 . 0 7

8、 6 5 2 7 d r u g X 决策树 are widely used in data mining. were developed in machine learning and statistics. are used to build classification and prediction models. are widely available. 判定树分类算法 output 训练集 决策树 input 新数据 分类 使用决策树进行分类 决策树 一个树形的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分类 决策树生成算法分成两个步骤 树的生

9、成 开始，数据都在根节点 递归的进行数据分片 树的修剪：去掉一些可能是噪音或者异常的数据 决策树使用 : 对未知数据进行分割 按照决策树上采用的分割属性逐层往下，直到叶子节点 决策树算法 基本算法（贪心算法） 自上而下分而治之的方法 开始时所有的实例都在根节点 属性都是分类型 (如果是连续的，将其离散化 ) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如信息增 益 ) 停止分割的条件 一个节点上的实例都属于同一个类别； 没有属性可以再用于对数据进行分割 属性选择的统计度量 信息增益 Information gain (ID3/C4.5) 所有属性假设都

10、是分类型字段 经过修改之后可以适用于数值型字段 基尼指数 Gini index (IBM Intelligent Miner) 能够适用于分类和数值字段 其他 信息增益度度量 (ID3/C4.5) 任意样本分类的期望信息： I(s1,s2,sm)= Pi 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(

11、s1,s2,sm) E(A) | | S Si 训练集 a g e i n co me st u d e n t cre d i t _ ra t i n g b u ys_ co mp u t e r =3 0 h i g h no f a i r no 4 0 me d i u m no f a i r ye s 4 0 l o w ye s f a i r ye s 4 0 l o w ye s e x ce l l e n t no 3 1 4 0 l o w ye s e x ce l l e n t ye s =3 0 me d i u m no f a i r no 4 0 me

12、 d i u m ye s f a i r ye s 4 0 me d i u m no e x ce l l e n t no 使用信息增益进行属性选择 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 age p i n i I ( p i, n i) 4 0 3 2 0 .9 7 1 971.0)2,3( 14 5 )0,4( 14 4)3,2( 14 5)( I IIageE 0 4

13、8.0)_( 1 5 1.0)( 0 2 9.0)( r a ti n gc re d itG a in s tu d e n tG a in in c o m eG a in )(),()( ageEnpIageG ai n 0.694 分枝 决策树 age? overcast student? credit rating? no yes fair excellent 40 no no yes yes yes 30.40 基尼指数（ Gini Index） 集合 T包含 n个类别的记录，那么其 Gini指数就是 pj 类别 j出现的频率 如果集合 T分成两部分 N1 and N2 。 那么这

14、个分割的 Gini就是 提供最小 Ginisplit 就被选择作为分割的标准 . nj p jTg i n i 1 21)( )()()( 2211 Tg i n iNNTg i n iNNTg i n i s p l i t Pruning Tree 目的： 消除决策树的过拟合 (Over Fitting)问题 实质：消除训练集中的异常和噪声 两种方法： 先剪枝法 (Public 算法 ) 后剪枝法 (Sprint 算法 ) 过拟合问题 训练数据 测试数据 此处剪枝 决策树深度 剪枝 避免过拟合 决策树泛化 误分类率 C1 C2 C3 C1 0 r12 r13 C2 r21 0 r23 C3

15、 r31 r32 0 实际类别 分类类别 Cost (or loss) matrix 常用的决策树算法 ID3, C4.5, C5.0 (Ross Quinlan 1986,1993) CART (Leo Briemen, et al 1984) CHAID (J. A. Hartigan, 1975) 银行信用卡市场分析员的市场促销（ 1） 确定促销最理想的顾客群体 常客们是否是银行的受益顾 客？这里的常客指每月至少使用一次信用卡的顾客，受益 顾客指为银行带来回报的顾客。 顾客分类 记录人数 常顾客 76028 给企业带来最大 收益的顾客 72051 76028 72051 5124 常顾客

16、和 给企业带来最大收益的顾客 2类顾客数量比较报告 结果表明银行所喜欢的顾客，很多不是那些使用信用卡 的常客。由于促销预算的限制，他只允许给 36000位顾 客促销袋。 促销应针对哪一部分受益顾客？哪些受益顾客将成为常 客（促销的目的是在给定时间内使顾客成倍地增加且进 行大量的消费） 决策树分析 银行信用卡市场分析员的市场促销（ 2） 银行信用卡市场分析员的市场促销（ 3） 401709个记录 帐户平衡的： 243789 60.7% 延迟超过 60天的 85869 21.4% 延迟超过 30天的 72051 17.9% 婚姻状况 =寡居 36519个记录 帐户平衡的： 7896 21.6% 延

17、迟超过 60天的 16779 45.9% 延迟超过 30天的 11844 32.4% 婚姻状况 =独身 65142个记录 帐户平衡的： 19740 30.3% 延迟超过 60天的 9870 15.2% 延迟超过 30天的 35532 54.5% 婚姻状况 =已婚 300048个记录 帐户平衡的： 216153 72.0% 延迟超过 60天的 59220 19.7% 延迟超过 30天的 24675 8.2% 居住情况 =租房 42441个记录 帐户平衡的： 987 2.3% 延迟超过 60天的 5922 14.0% 延迟超过 30天的 35532 83.7% 居住情况 =自有住房 22701个记

18、录 帐户平衡的： 18753 82.6% 延迟超过 60天的 3948 17.4% 月可支配收入 938美元 6909个记录 帐户平衡的 987 14.3% 延迟超过 60天的 5922 85.7% 月可支配收入 938美元 35532个记录 延迟超过 30天的 35532 100% Customer profiling 预测 预测是构造和使用模型评估给定的样本数据可能具有的属性 值或值区间： 离散数据的预测：可以使用分类分析的方法， 例如预 测一个移动用户是否流失。 连续数据的预测：可以使用回归分析的方法。 神经网络 Neural Networks 神经网络 神经网络通过学习待分析数据中的模

19、式来构造模型，一般可对 隐类型进行分类，用于非线性的，复杂的数据。它通过模拟人 脑神经元结构进行数据挖掘。以 MP模型和 Hebb学习规则为基础， 建立了三大类多种神经网络模型： 前馈式网络：以感知机、反向传播模型 BP、 函数型网络为 代表，可用于预测、模式识别等方面。 反馈式网络：以 Hopfield的离散模型和连续模型为代表， 分别用于联想记忆和优化计算。 自组织网络：以 ART模型、 Koholon模型为代表，用于聚类。 神经元 神经元：每个细胞处于两种状态 ，突触联接有强度。多输入单输 出，实质上传播的是脉冲信号， 信号的强弱与脉冲频率成正比。 Use neural models t

20、o approximate multiple variate functions like Y = f(X1, X2, , X n, W1, W2, , W k) Here, the form of f(.) is unknown. Xi are input variables, Wi are coefficients . 神经网络用途 分类 回归 预测 聚类 神经网络适合数值型数据 以数值型数据为输入 输出为可分类属性 神经网络模型 *Multi-layer Perceptrons (ANN) Radial Basis Function Networks (RBFN) Probabilist

21、ic Neural Networks (PNN) 前馈型神经网络 最初称之为感知器。 应用最广泛的一种 人工神经网络模型， 采用 BP学习算法。 前馈网络结构是分 层的，信息只能从 下一层单元传递到 相应的上一层单元。 上层单元与下层所 有单元相联结。激 活函数可以是线性 的。 感知器的不足 1957年 Frank Rosenblatt定义了一个神经网络结构感知 器（ perception）。 第一次把神经网络研究从纯理论的 探讨推向工程实现，在 IBM704计算机上进行了模拟， 证明了该模型有能力通过调整权的学习达到正确分类 的结果。 1969年 Minsky和 Papert发表了 Perc

22、eptions 的论著， 指出感知器仅能线性划分，对于非线性或其他分类会 遇到很大困难。 BP网的产生 1986年美国的一个并行计算研究小组提出了前 向反馈神经网络的 Back Propagation（ BP） 算 法，成为目前最广泛使用的方法之一，克服了 感知器非线性不可分类问题。 BP神经网络 输出 隐层 x1 x2 x3 x4 x5 x6 x7 y1 y2 y3 y4 y w11 w 12 w74 w1 w2 w3 w4 给定训练样本集 设计网络结构 训练网络 网络基本参数 网络结构包括隐层数和隐层节点数 学习率 ： w(t+1) = w(t) + (d - y) xi 停止条件： 训练

23、次数、精度或时间 神经网络的应用 (1) 在财务方面，神经网络可用来协助投资公司预测普通股的表 现、公司的债券等级或公司破产的可能性。 VISA国际公司用神经网络来帮助侦测信用卡欺诈，它监控所 有 VISA交易并且注意持卡人消费形态的改变。 收入 负债 年龄 付款 记录 信誉良好风 险值 信誉不良风 险值 神经网络的应用 (2) 股票拐点趋势预测 :利用历史价格数据预测中短期（从 2到 10或 15 天）的价格走势。 贝叶斯分类器 贝叶斯定理 假设 X和 Y在分类中可以分别表示样本的属性集和类别。 P(X,Y)表 示它们的联合概率， p(X|Y) 和 p(Y|X)表示条件概率，其中是后验 概率

24、，而称为 Y的先验概率。 X和 Y的联合概率和条件概率满足下 列关系： 变换后得到 ( , ) ( | ) ( ) ( | ) ( )p X Y p Y X p X p X Y p Y ( | ) ( )( | ) ()p X Y p Yp Y X pX 朴素贝叶斯分类器 对于属性集 ，如果 之间相互独立，即 ，有朴素贝叶斯分类器： 其中 是常数，先验概率 可以通过训练集中每类样本所占的 比例估计。给定 ，如果要估计测试样本 X的分类 ， 由朴素贝叶斯 分类器得到 y类的后验概率： 只要找出使最大的类别 y即可。 12 , ,., nX X X X 12, ,., nX X X 1( | )

25、( | ) n iip X Y p X Y 1 ( ) ( | ) ( | ) () n i i p Y p X Y p Y X pX ()pX ()pY Yy 1 ( ) ( | ) ( | ) () n i i p Y y p X Y y p Y y X pX 贝叶斯分类器在供电电容生产中的应用（ 1） 假设某段时期内某电脑主板制造商所用的供电电容是由三家电容 生产厂提供的。对制造商在这段时期内的业务数据进行抽样，得 到下表。 因为三家电容工厂的供电电容在电脑主板生产商的仓库中是均匀 混合的，并无明显的区别标志。现在电脑主板生产商想通过对数 据进行分析，解决下面两个问题： （ 1）随机地从

26、仓库中取一只供电电容是次品的概率。 （ 2）从仓库中随机地取一只供电电容，若已知取到的是一只次品， 想分析此次品来自哪家工厂的可能性最大。 贝叶斯分类器在供电电容生产中的应用（ 2） 贝叶斯分类器在垃圾邮件处理中的应用 贝叶斯分类器是对邮件的内容进行分析，不仅考虑关键词在 垃圾邮件中出现的概率，也考虑关键词在正常邮件中的概率。 当一封新的邮件到达时，这封邮件的内容将被分解成字串。 依据数据库中这些词的概率通过公式进行计算，用贝叶斯定 理计算出的垃圾邮件可能性高于某个阈值时就判定这封邮件 是垃圾邮件。 贝叶斯过滤防范有一定的智能性，通过一定的学习方法可以 对数据库词的概率进行更新，可以适应垃圾邮

27、件的变化情况。 K-最近邻分类 遗传算法 粗糙集理论 模糊理论 其他分类方法 聚类 Clustering 聚类 Definition of clustering Clustering is a process of partitioning a set of objects such as customers into groups in which the objects in the same group are similar to each other and the objects in different groups are dissimilar, according to so

28、me similarity measure. 聚类就是把整个数据分成不同的组，并使组与 组之间的差距尽可能大，组内数据的差异尽可 能小。 Clustering is often called unsupervised classification Clustering is used for customer segmentation Customer Segmentation Customer segmentation is a process to divide customers into groups or segments. Customers in the same segment

29、 have similar needs or behaviors so that similar marketing strategies or service policies can be applied to them. Segmentation according to some variables E.g., use customer type variable to divide customers into corporate customers and individual customers Segmentation using a data mining technique

30、s E.g., a clustering algorithm or decision tree algorithm 与分类的区别 与分类不同，在开始聚集之前用户并不知道要把数据分 成几组，也不知分组的具体标准，聚类分析时数据集合的特征是未知的。 聚类根据一定的聚类规则，将具有某种相同特征的数据 聚在一起也称为无监督学习。分类用户则知道数据可分 为几类，将要处理的数据按照分类分入不同的类别，也称为有监督学习。 聚类问题的数学描述 给定数据集合 V， 根据数据对象间的相似程度将数据集 合分成组，并满足： 则该过程称为聚类。 Ci称为簇。 1 | 1 , 2 , . , j i ij k ii C

31、j k CV CC CV 基本概念 Cluster center Cluster size Cluster density Cluster descriptions 一个好的聚类方法要能产生高质量的聚类结果 簇，这些 簇要具备以下两个特点： 高的簇内相似性 低的簇间相似性 聚类的典型应用 模式识别 空间数据分析 在 GIS中，通过聚类发现特征空间来建立主题索引； 在空间数据挖掘中，检测并解释空间中的簇； 图象处理 经济学 (尤其是市场研究方面 ) WWW 文档分类；分析 WEB日志数据来发现相似的访问模式 Cluster analysis of data Customer segmentati

32、on Fraud detection Missing value prediction 聚类需求 可伸缩性 能够处理不同类型的属性 能发现任意形状的簇 在决定输入参数的时候，尽量不需要特定的领域知识； 能够处理噪声和异常 对输入数据对象的顺序不敏感 能处理高维数据 能产生一个好的、能满足用户指定约束的聚类结果 结果是可解释的、可理解的和可用的 计算对象之间的相异度 通常使用距离来衡量两个对象之间的相异度。 常用的距离度量方法有 : 明考斯基距离 （ Minkowski distance） : 其中 i = (xi1, xi2, , xip) 和 j = (xj1, xj2, , xjp) 是两

33、个 p维的数据对 象 , q是一个正整数。 当 q = 1时 , d 称为 曼哈坦距离 （ Manhattan distance） q qppqq jxixjxixjxixjid )|. .|(|),( 2211 |. . .|),( 2211 pp jxixjxixjxixjid Similarity and Dissimilarity Between Objects (Cont.) 当 q=2时 , d 就成为 欧几里德距离 : 距离函数有如下特性： d(i,j) 0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j) d(i,k) + d(k,j) 可以根据每个变量的重要

34、性赋予一个权重 )|.|(|),( 2222211 pp jxixjxixjxixjid 二元变量 二元变量的可能性表 其中每个对象有 p个变量，且 p=a+b+c+d pdbcasum dcdc baba sum 0 1 01 Object i Object j 二元变量 对称的 如果一个二元变量的两个状态是同等价值的，具有相同的 权重。即可以任取其中一种状态编码为 1或者 0。对于对称 的二元变量，采用 简单匹配系数 来评价两个对象之间的相 异度 dcba cb jid ),( 二元变量 非对称的 如果变量的两个状态不是同样重要的，则称该变量是不对称 的。将比较重要通常也是出现概率比较小的

35、状态编码为 1，将另 一种状态编码为 0。对于非对称的二元变量，采用 Jaccard系数 来 评价两个对象之间的相异度 cba cb jid ),( 二元变量的相异度计算 gender 是一个对称的二元变量 其它的都是非对称的二元变量 将值 Y和 P 编码为 1, 值 N 编码为 0，根据 Jaccard系数计算得： Nam e Gender Fev er Cough Test-1 Test-2 Test-3 Test-4 Jack M Y N P N N N Ma ry F Y N P N P N Ji m M Y P N N N N 75.0 211 21),( 67.0 111 11),

36、( 33.0 102 10),( m a r yjimd jimj a c kd m a r yj a c kd 标称变量（ Nominal Variables） 标称变量是二元变量的推广，它可以具有多于两个的状态， 比如 变量 map_color可以有 red, yellow, blue, green四种状 态。有两种计算相异度的方法 ： 方法 1: 简单匹配方法 m是匹配的数目 , p是全部变量的数目 方法 2: 使用二元变量 为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标 称变量。 p mpjid ),( 序数型变量 一个序数型变量可以是离散的也可以是连续的 离散的序数

37、型变量类似于标称变量，除了它的 M个状态 是以有意义的序列排序的，比如职称。 连续的序数型变量类似于区间标度变量，但是它没有 单位，值的相对顺序是必要的，而其实际大小并不重 要。 聚类算法 K-means type algorithms Kohonen neural network (self-organizing map) Hierarchical clustering methods 其他 K-均值算法（ 1） Input A set of numeric records An integer k 1 (number of clusters to be found). Output A p

38、artition of records into k clusters. Each record is identified as one of the k clusters. x11, x12 x21, x22 xn1, xn2 x11, x12 1 x21, x22 2 xn1, xn2 1 K-均值算法过程 1. Select k distinct records as initial means, each representing a cluster. 2. For each record in data, calculate the squared Euclidean distan

39、ces between it and the means. Assign the record to the cluster whose mean is the nearest to the record. 3. After all records are assigned a cluster, calculate the new mean for each cluster as the average of all records in the cluster. 4. If the new means equal to the previous means, stop, otherwise,

40、 go to Step 2. K-均值算法（ 2） 1 x11, x12 2 x21, x22 3 x31, x32 4 x41, x42 5 x51, x52 6 x61, x62 C1 C2 1 x11, x12 1 2 x12, x12 1 3 x13, x12 2 4 x14, x12 1 5 x15, x12 2 6 x16, x12 2 C1 C2 1 x11, x12 1 2 x12, x12 2 3 x13, x12 2 4 x14, x12 1 5 x15, x12 1 6 x16, x12 1 C1 C2 K-均值算法性质 Efficient in clustering l

41、arge data Solution depends on initial means Sensitive to outliers Spherical clusters Numeric data K-均值算法局限 非球形的簇 发现客户的特征 客户分割（ segmentation） 是一种发现用户 特性的方法。数据驱动的分割将一个基于数 据的客户信息的自然客户分组：从而给你一 个客户信息的概况，这可以直接转化为增加 客户的经营策略。 聚类可视化 Total Population This Class 性别 F M 0 500 0 1000 0 1500 0 2000 0 2500 0 3000

42、0 3500 0 4000 0 4500 0 5000 0 0 10 20 30 percent Total Population This Class 收入 聚类结果 信用卡用户聚类 聚类结果 高花费用户 偏离（异常）检测 偏离检测 在数据库中寻找含有你不希望出现的值的记录或 记录系列。 应用实例：用它来识别欺诈行为模式或控制生产 过程的质量。 异常探测 异常探测是数据挖掘中一个重要方面，用来发 现 “ 小的模式 ” (相对于聚类 )，即数据集中显 著不同于其它数据的对象。 异常探测应用 电信和信用卡欺骗 贷款审批 药物研究 气象预报 金融领域 客户分类 网络入侵检测等 什么是异常 （ ou

43、tlier） ？ Hawkins(1980)给出了异常的本质性的定义： 异常 是 在数据集中与众不同的数据，使人怀疑这些数据并非随机 偏差，而是产生于完全不同的机制。 聚类算法对异常的定义：异常是聚类嵌于其中的背 景噪声。异常探测算法对异常的定义：异常是既不 属于聚类也不属于背景噪声的点。他们的行为与正 常的行为有很大不同。 关联分析 association analysis 关联 若两个或多个变量的取值之间存在某种规律性，就称为关联。 关联规则是寻找在同一个事件中出现的不同项的相关性，比如在一次 购买活动中所买不同商品的相关性。 关联分析即利用关联规则进行数据挖掘。 关联规则是形式如下的一种

44、规则，“在购买计算机的顾客中，有 30 的人也 同时 购买了打印机”。 从大量的商务事务记录中发现潜在的关联关系，可以帮助人们作出正 确的商务决策。 啤酒和尿布问题 反映一个事件和其他事件之间依赖或关联的知识。如果两 项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。 在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿 布，超市也因此发现了一个规律，在购买婴儿尿布的年轻 父亲们中，有 30% 40%的人同时要买一些啤酒。超市 随后调整了货架的摆放，把尿布和啤酒放在一起，明显增 加了销售额。 购物篮分析 此类关联分析在零售业，如 超市等得到广泛应用，企业 可以获得注入产

45、品间的关联， 或者产品类别和购买这些类 别的产品的顾客的统计信息 之间的关联规则。 关联分析又称购物篮分析，在 销售配货、商店商品的陈列设 计、超市购物路线设计、产品 定价和促销等方面得到广泛应 用。 Association Rule 1. The first association discovery algorithm was designed for basket analysis in retail.Try to answer How many customers who bought item X also bought Item Y?Such algorithm has been

46、found useful in other applications, e.g., associations of drugs. Association rule: Frozenmeal Head support, confidence. buys(x, diapers) buys(x, beers) 0.5%, 60% major(x, CS) takes(x, DB) grade(x, A) 1%, 75% 关联规则问题的形式化描述项目 定义 1：集合 I=i1， i2， ,im为标识符的集合，其 中 m为正整数， ik（ k=1， 2， ,m)称为项目。 项目是一个从具体问题中抽象出的一

47、个概念。在 超市的关联规则挖掘问题中，项目表示各种商品， 如旅游鞋等。由于在超市的关联规则挖掘中并不 关心顾客购买的商品数量和价格等，因此顾客的 一次购物可以用该顾客所购买的所有商品的名称 来表示，称为事务，所有事务的集合构成关联规 则挖掘的数据集，称为事务数据库。 事务 定义 2：关联规则挖掘的数据库记为 D， 事务数据 库 D中的每个元组称为事务。一条事务 T是 I中项目 的集合。一条事务仅包含其涉及到的项目，而不 包含项目的具体信息。在超级市场的关联规则挖 掘问题中事务是顾客一次购物所购买的商品，但 事务中并不包含这些商品的具体信息，如商品的 数量、价格等。 项目集 定义 3：项目集是由

48、 I中项目构成的集合。若项 目集包含的项目数为 k， 则称此项目集为 k-项目 集。 定义 4：任意的项目集 X和事务 T若满足： TX， 则称事务 T包含项目集 X。 在超市的关联规则挖掘问题中项目集可以看成 一个或多个商品的集合。若某顾客一次购买所 对应的事务 T包含项目集 X， 就说该顾客在这次 购物中购买了项目集 X中的所有商品。 频繁项目集 定义 5：对任意的项目集 X， 若事务数据库 D中 %的事务包含项目集 X， 则项目集的支持率为 ， 记为 support（ X） = ， 其中包含项目集 X的事务 数称为项目集 X的频度，记为 count（ X）。 若项 目集 X的支持率大于或

49、等于用户指定的最小支持 率（ minsupport）， 则项目集 X称为 频繁项目集 （或大项目集），否则项目集 X为非频繁项目集 （或小项目集）。如果数据库 D中的事务数记为 |D|， 频繁项目集是至少被 %x|D|条事务包含的 项目集 . 支持度和置信度 定义 6:关联规则是形如 X-Y的规则，其中 X， Y为 项目集且 XY=。 定义 7：在数据库 D中，若 s%的事务包含 XY， 则关联规则 X-Y的支持度为 s%； 在数据库 D中， 若 c%的包含项目集 X的事务也包含项目集 Y， 则 关联规则 X-Y的置信度为 c%: p（ YX） p（ XY） /p(X)。 置信度反应了关联规则

50、的可信度 购买了项目集 X中的商品的顾客同时也购买了 Y中商品的 可能性 有多大。 强关联规则 定义 8：若关联规则 X-Y的支持度和置信度分 别大于或等于用户指定的最小支持率 minsupport 和最小置信度 minconfidence， 则称关联规则 X- Y为 强关联规则 ，否则称关联规则 X-Y为弱 关联规则。 关联规则挖掘的核心就是要找出事务数据库 D 中的所有强相关规则。 关联规则挖掘问题的分解 给定数据库 D， 关联规则的挖掘就是找出所有存 在于数据库 D中的强关联规则。因此整个关联规 则挖掘过程可以分解为以下两个子问题： 找出所有的频繁项目集； 根据找到的频繁项目集导出所有的

51、强关联规则。 强关联规则的产生 第一个子问题的求解，需要多次扫描数据库 D， 这意味着 关联规则挖掘算法的效率将主要取决于数据库扫描、 I/O操 作和频繁项目集的计算上。因此如何迅速、高效地找出所 有的频繁项目集是关联规则挖掘的中心问题 第二个子问题的求解比较容易， R. Agrawal等人已提出了 有效的解决办法，具体过程如下： 对每个频繁项目集 I， 产生所有的非空真子集：对 I的任意 非空真真子集 m， 若 support（ I） /Support（ m） minconfidence， 则产生强关联规则 m-(l-m)。 规则度量：支持度与可信度 查找所有的规则 X for (k = 1

52、; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return k Lk; 如何生成候选集 假定 Lk-1 中的项按顺序排列 第一步 : 自连接 Lk-1 insert into Ck select p.item1, p.

53、item2, , p.item k-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, , p.item k-2=q.itemk-2, p.itemk-1 5 Apriori 够快了吗 ? 性能瓶颈 Apriori算法的核心 : 用频繁的 (k 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈 : 候选集生成 巨大的候选集 : 多次扫描数据库 ： 如果最长的模式是 n的话，则需要 n +1次数据库扫描 多层关联规则 项通常具有层次。 底层的项通常支持度也 低。 某些特定层的规则可能

54、更有意义。 交易数据库可以按照维 或层编码。 可以进行共享的多维挖 掘。 食品 面包 牛奶 脱脂奶 光明 统一 酸奶 白 黄 T I D I t e ms T1 1 1 1 , 1 2 1 , 2 1 1 , 2 2 1 T2 1 1 1 , 2 1 1 , 2 2 2 , 3 2 3 T3 1 1 2 , 1 2 2 , 2 2 1 , 4 1 1 T4 1 1 1 , 1 2 1 T5 1 1 1 , 1 2 2 , 2 1 1 , 2 2 1 , 4 1 3 挖掘多层关联规则 自上而下，深度优先的方法： 先找高层的“强”规则： 牛奶 面包 20%, 60%. 再找他们底层的“弱”规则：

55、酸奶 黄面包 6%, 50%. 多层关联规则的变种 层次交叉的关联规则 ： 酸奶 复旦面包房 黄面包 不同种分层方法间的关联规则 ： 酸奶 复旦面包房面包 多层关联：冗余过滤 由于“祖先”关系的原因，有些规则可能是多余的。 例子 牛奶 白面包 support = 8%, confidence = 70% 酸奶 白面包 support = 2%, confidence = 72% 第一个规则是第二个规则的祖先 参考规则的祖先，如果它的支持度与“预期”的支持度 近似的话，则这条规则是冗余的。 多层挖掘：深度优先 自顶向下，深度优先的方法： 先挖掘高层频繁项： 牛奶 (15%), 面包 (10%)

56、再挖掘它们底层的相对较弱的频繁项：酸奶 (5%), 白面包 (4%) 跨层时对支持度的不同处理方法，对应了不同的算法 : 层之间支持度不变：如果 t的祖先是非频繁的，则不用考虑 t 支持度随层递减 ： 则只考虑那些其祖先是频繁的 /不可忽略的项 多维关联规则概念 单维规则： buys(X, milk) buys(X, bread) 多维规则： 2个以上维 /谓词 维间关联规则 (谓 词 不重复 ) age(X,19-25) occupation(X,student) buys(X,coke) 混合维关联规则 (谓 词重复 ) age(X,19-25) buys(X, popcorn) buys

57、(X, coke) 类别属性 有限个值 , 值之间无顺序关系 数量属性 数字的，值之间隐含了顺序关系 序列模式发现 Sequential Patterns Discovery 序列模式分析（趋势分析） 序列模式的发现是由 R Agrawal于 1995年首先 提出的。序列模式寻找的是事件之间在顺序上 的相关性。 例如，“凡是买了喷墨打印机的顾客中， 80% 的人在三个月之后又买了墨盒”，就是一个 序 列关联规则 。 序列模式挖掘在交易数据库分析、 Web访问日 志分析以及通信网络分析等领域具有广泛的应 用前景。 序列模式 Identifies time-dependent sequences

58、among transaction sets where each transaction includes a set of items. Example Given a set of ordered customer transactions. Each transaction contains a set of items. Find sequences: if a customer buys item A then the customer will buy item X afterwards 实例（ 1） Transaction Time Customer Items Bought

59、June 20, 1994 10:13 am J. Brown Juice, Coke June 20, 1994 11:02 am F. Zappa Brandy June 20, 1994 11:47 am J. Brown Beer June 20, 1994 2:32 pm B. Moore Beer June 21, 1994 9:22 am J. Brown Wine, Water, Cider June 21, 1994 3:19 pm J. Mitchell Beer, Gin, Cider June 21, 1994 5:27 pm B. Adams Beer (Diaper

60、s?) June 21, 1994 6:17 pm B. Moore Wine, Cider June 22, 1994 10:34 am B. Adams Brandy June 22, 1994 5:03 pm B. Moore Brandy 实例（ 2） Database Sorted by Customer and Date Customer Transaction Time Items Bought B. Adams June 21, 1994 5:27 pm Beer B. Adams June 22, 1994 10:34 am Brandy J. Brown June 20,

61、1994 10:13 am Juice, Coke J. Brown June 20, 1994 11:47 am Beer J. Brown June 21, 1994 9:22 am Wine, Water, Cider J. Mitchell June 21, 1994 3:19 pm Beer, Gin, Cider B. Moore June 20, 1994 2:32 pm Beer B. Moore June 21, 1994 6:17 pm Wine, Cider B. Moore June 22, 1994 5:03 pm Brandy F. Zappa June 20, 1

62、994 11:02 am Brandy 实例（ 3） Customer Sequence Database Customer Customer Sequence B. Adams (Beer) (Brandy) J. Brown (Juice, Coke) (Beer) (Wine, Water, Cider) J. Mitchell (Beer, Gin, Cider) B. Moore (Beer) (Wine, Cider) (Brandy) F. Zappa (Brandy) Sequential Patterns in the Database Sequential Patterns

63、 with Support 40% Customers Supporting it (Beer) (Brandy) B. Adams, B. Moore (Beer) (Wine, Cider) J. Brown, B. Moore Sequential Rule with Support40% Customers Supporting the Rule Body Confidence Value (Beer) = (Brandy) B. Adams, B. Moore 50% (Beer) = (Wine, Cider) J. Brown, B. Moore 50% Derived Sequential Rules 序列模式 序列模式的概念最早是由 Agrawal和 Srikant 提出的。 序列模式定义：给定一个由不同序列组成的集合，其中 每个序列由不同的元素按顺序有序排列，每个元素由不 同项目组成，同时给定一个用户指定的最小支持度阈值， 序列模式挖掘就是找出所有的频繁子序列，即该子序列 在序列集中的出现频率不低