第12讲数据挖掘应用Chapter12ApplicationsofDataMining

《第12讲数据挖掘应用Chapter12ApplicationsofDataMining》由会员分享，可在线阅读，更多相关《第12讲数据挖掘应用Chapter12ApplicationsofDataMining（179页珍藏版）》请在装配图网上搜索。

1、第12讲 数据挖掘应用Chapter 12 Applications of Data Mining徐从富(Congfu Xu),PhD,Asso.Professor 浙江大学人工智能研究所2005年5月17日第一稿2006年10月30日第二次修改浙江大学研究生人工智能引论课件目录一关联规则挖掘二聚类分析三分类与预测四Web挖掘五流数据挖掘六隐私保护数据挖掘一关联规则挖掘1.关联规则挖掘简介2.关联规则基本模型3.关联规则价值衡量与发展1.关联规则简介n关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。

2、n典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。什么是关联规则挖掘n关联规则挖掘 首先被Agrawal,Imielinski and Swami在1993年的SIGMOD会议上提出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集 n目的:发现数据中的规律超市数据中的什么产品会一起购买？啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?频繁模式挖掘的重要性n许多重要数据挖掘任务的基础关联

3、、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析n更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等2.关联规则基本模型关联规则基本模型Apriori算法 关联规则基本模型 nIBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度关联规则基本模型（续）n设I=i1,i2,im为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识T

4、ID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。关联规则基本模型（续）n关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support(X)，规则的信任度为support(XY)support(X)。这是一个条件概率P(Y|X)。也就是：suppor

5、t(XY)=P(X Y)confidence(XY)=P(Y|X)规则度量：支持度与可信度n查找所有的规则 X&Y Z 具有最小支持度和可信度支持度,s,一次交易中包含X、Y、Z的可能性可信度,c,包含X、Y的交易中也包含Z的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为50%,最小可信度为 50%,则可得到A C (50%,66.6%)C A (50%,100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户关联规则基本模型（续）n关联规则就是支持度和信任度分别满足用户给定阈值的规则。n发现关联规则需要经

6、历如下两个步骤：找出所有频繁项集。由频繁项集生成满足最小信任度阈值的规则。Let min_support=50%,min_conf =50%:A C (50%,66.7%)C A (50%,100%)Customerbuys diaperCustomerbuys bothCustomerbuys beerTransaction-idItems bought10A,B,C20A,C30A,D40B,E,FFor rule A C:support=support(AC)=50%confidence=support(AC)/support(A)=66.6%Min.support 50%Min.con

7、fidence 50%Transaction-idItems bought10A,B,C20A,C30A,D40B,E,FFrequent patternSupportA75%B50%C50%A,C50%Apriori算法的步骤nApriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。nApriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。n挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。频繁项集n为了避免计算所有项集的支持度（实际上频繁项集

8、只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为 ，则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。kmCkmC关联规则的性质：n性质6.1 频繁项集的子集必为频繁项集。n性质6.2 非频繁项集的超集一定是非频繁的。nApriori算法运用性质6.1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在

9、一定程度上减少了计算量。Apriori算法n(1)L1=频繁1项集;n(2)for(k=2;Lk-1;k+)do begin n(3)Ck=apriori_gen(Lk-1);/新的潜在频繁项集 n(4)for all transactions tD do begin n(5)Ct=subset(Ck,t);/t中包含的潜在频繁项集 n(6)for all candidates cCt do n(7)c.count+;n(8)end;n(9)Lk=cCk|c.countminsup n(10)end;n(11)Answer=kkL实例Database TDB1st scanC1L1L2C2C2

10、2nd scanC3L33rd scanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA,BA,CA,EB,CB,EC,EItemsetsupA,B1A,C2A,E1B,C2B,E3C,E2ItemsetsupA,C2B,C2B,E3C,E2ItemsetB,C,EItemsetsupB,C,E2Visualization of Association Rules:Pane GraphVisualization of Association Rules:Rule Graph提高A

11、priori算法的方法nHash-based itemset counting（散列项集计数）nTransaction reduction（事务压缩）nPartitioning（划分）nSampling（采样）关联规则挖掘算法nAgrawal等人提出的AIS，Apriori和AprioriTidnCumulate和Stratify，Houstsma等人提出的SETMnPark等人提出的DHPnSavasere等人的PARTITIONnHan等人提出的不生成候选集直接生成频繁模式FPGrowthn其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。n用Freq

12、uent-Pattern tree(FP-tree)结构压缩数据库,高度浓缩，同时对频繁集的挖掘又完备的避免代价较高的数据库扫描n开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则:只使用部分数据库!挖掘频繁集挖掘频繁集 不用生成候选集不用生成候选集f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3最小支持度最小支持度=0.5TIDItems bought (ordered)frequent items100f,a,c,d,g,i,m,pf,c,a

13、,m,p200a,b,c,f,l,m,of,c,a,b,m300 b,f,h,j,of,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p步骤:1.扫描数据库一次，得到频繁1-项集2.把项按支持度递减排序3.再一次扫描数据库，建立FP-tree用交易数据库建立用交易数据库建立 FP-treen完备:不会打破交易中的任何模式包含了频繁模式挖掘所需的全部信息n紧密去除不相关信息不包含非频繁项支持度降序排列:支持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销)例子:对于 Connect-4 数据库,压缩率超过 100

14、FP-tree 结构的好处结构的好处n基本思想(分而治之)用FP-tree地归增长频繁集n方法 对每个项，生成它的 条件模式库,然后是它的 条件 FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的项集都是频繁集)用用 FP-tree挖掘频繁集挖掘频繁集1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tree3)递归构造条件 FP-trees 同时增长其包含的频繁集如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。挖掘挖掘 FP-tree的主要步骤的主要步骤n从FP

15、-tree的头表开始n按照每个频繁项的连接遍历 FP-treen列出能够到达此项的所有前缀路径，得到条件模式库条件模式库条件模式库itemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤步骤1:从从 FP-tree 到条件模式库到条件模式库n节点裢接任何包含ai,的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到n前缀路径要计算路径P 中包含节点ai

16、的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度FP-tree支持条件模式库构造的属性支持条件模式库构造的属性n对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库条件模式库:fca:2,fcab:1f:3c:3a:3m-conditional FP-treeAll frequent patterns concerning mm,fm,cm,am,fcm,fam,cam,fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤步骤2:建立条件

17、建立条件 FP-treeEmptyEmptyf(f:3)|c(f:3)c(f:3,c:3)|a(fc:3)aEmpty(fca:1),(f:1),(c:1)b(f:3,c:3,a:3)|m(fca:2),(fcab:1)m(c:3)|p(fcam:2),(cb:1)p条件FP-tree条件模式库项通过建立条件模式库得到频繁集通过建立条件模式库得到频繁集f:3c:3a:3m-条件 FP-tree“am”的条件模式库:(fc:3)f:3c:3am-条件 FP-tree“cm”的条件模式:(f:3)f:3cm-条件 FP-tree“cam”条件模式库:(f:3)f:3cam-条件 FP-tree第第

18、3步步:递归挖掘条件递归挖掘条件FP-tree3.关联规则价值衡量与发展关联规则价值衡量关联规则最新进展 规则价值衡量 n对关联规则的评价与价值衡量涉及两个层面：系统客观的层面用户主观的层面系统客观层面 n使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。用户主观层面 n只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。n可以采用基于约束（Consraint-based）的数据挖掘方法。具体约束的内容有：数据约束、限定数据挖掘的维和层次、规则约束。n如果把某些约束条件与算法紧密结合，既能提高数据挖掘效率，

19、又能明确数据挖掘的目标。关联规则新进展 n在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。nR.Agrawal等人提出的Apriori 是经典算法。随后的关联规则发现算法大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。nLin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。关联规则新进展（续）n数据挖掘工作是在海量数据库上进行的，数据库的规模对规则的挖掘时间有很大影响。nAgrawal首先提出事务缩减技术，Han和Park等人

20、也分别在减小数据规模上做了一些工作。n抽样的方法是由Toivonen提出的。nBrin等人采用动态项集计数方法求解频繁项集。nAggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。关联规则新进展（续）n关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。n还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。nGuralnik提出顺序时间段问题的形式描述语言，以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。n最大模式挖掘是Bayardo等人提出来的。关联

21、规则新进展（续）n随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法。nB.zden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。n贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（Calendric Association Rules）算法，用以进行市场货篮分析。nFang等人给出冰山查询数据挖掘算法。关联规则新进展（续）nT.Hannu等人把负边界引入规则发现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。nSrikant等人通过研究

22、关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。nZakia还用项集聚类技术求解最大的近似潜在频繁项集，然后用格迁移思想生成每个聚类中的频繁项集。nCAR，也叫分类关联规则，是Lin等人提出的一种新的分类方法，是分类技术与关联规则思想相结合的产物，并给出解决方案和算法。关联规则新进展（续）nCheung等人提出关联规则的增量算法。nThomas等人把负边界的概念引入其中，进一步发展了增量算法。如，基于Apriori框架的并行和分布式数据挖掘算法。nOates等人将MSDD算法改造为分布式算法。还有其他的并行算法，如利用垂直数据库探求项集聚类等。二聚类分析I.聚类分析简介II.聚类分析中的

23、数据类型III.划分方法IV.层次方法I.聚类（Clustering）分析简介n聚类（Clustering）是对物理的或抽象的对象集合分组的过程。n聚类生成的组称为簇（Cluster），簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高的相异度。相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。聚类分析简介（续）n聚类分析是数据分析中的一种重要技术，它的应用极为广泛。许多领域中都会涉及聚类分析方法的应用与研究工作，如数据挖掘、统计学、机器学习、模式识别、生物学、空间数据库技术、电子商务等。聚类分析简介（续）n从统计学的观点看，聚类

24、分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。聚类分析简介（续）n从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。聚类分析简介（续）n从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。n就数据挖掘功能而言，

25、聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。n聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。n数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类分析算法。聚类的常规应用 n模式识别n空间数据分析 在GIS中，通过聚类发现特征空间来建立主题索引；在空间数据挖掘中，检测并解释空间中的簇；n图象处理n经济学(尤其是市场研究方面)nWWW文档分类分析WEB日志数据来发现相似的访问模式应用聚类分析的例子n市场销售:帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；n土地使用:在一个陆地

26、观察数据库中标识那些土地使用相似的地区；n保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；n城市规划:根据类型、价格、地理位置等来划分不同类型的住宅；n地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类；什么是一个好的聚类方法?n一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性 n聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；n聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；II.聚类分析中的数据类型n聚类分析主要针对的数据类型包括区间标度变量、二元变量、标称变量、序数型变量，以及

27、由这些变量类型构成的复合类型。n一些基于内存的聚类算法通常采用数据矩阵和相异度矩阵两种典型的数据结构。数据矩阵（Data Matrix）n设有n个对象，可用p个变量（属性）描述每个对象，则np矩阵 称为数据矩阵。数据矩阵是对象-变量结构的数据表达方式。npnnppxxxxxxxxx 212222111211相异度矩阵（Dissimilarity Matrix）n按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）：n其中d(i,j)表示对象i与j的相异度，它是一个非负的数值。当对象i和j越相似或“接近”时，d(i,j)值越接近0；而对象i和j越不相同或相距

28、“越远”时，d(i,j)值越大。显然，d(i,j)=d(j,i)，d(i,i)=0。相异度矩阵是对象-对象结构的一种数据表达方式。0 )2 ,()1 ,(0 )2 ,3()1 ,3(0 )1 ,2(0ndndddd评价聚类质量n差异度/相似度矩阵:相似度通常用距离函数来表示；n有一个单独的质量评估函数来评判一个簇的好坏；n对不同类型的变量，距离函数的定义通常是不同的；n根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系；n很难定义“足够相似了”或者“足够好了”只能凭主观确定；聚类分析中的数据类型n区间标度变量；n二元变量；n标称型，序数型变量；n混合类型变量；对象间距离

29、的计算n设两个p维向量xi=(xi1,xi2,xi p)T和xj=(xj1,xj2,xj p)T分别表示两个对象，有多种形式的距离度量可以采用。闵可夫斯基（Minkowski）距离：曼哈坦（Manhattan）距离：欧几里得（Euclidean）距离：切比雪夫（Chebyshev）距离：马哈拉诺比斯（Mahalanobis）距离：III.划分方法简介n对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。n划分方法满足两个条件：（1）每个分组至少包含一个对象；（2）每个对象必属于且仅属于某一个分组。n常见的划分方法有k

30、-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。k-均值算法 nk-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。首先，随机选取k个对象作为初始的k个簇的质心；然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到目标函数最小化为止。k-均值算法 n输入 期望得到的簇的数目k，n个对象的数据库。n输出 使得平方误差准则函数最小化的k个簇。n方法 选择k个对象作为初始的簇的质心；repeat 计算对象与各个簇的质心的距离，将对象划分到距离其最近的簇；重新计算每个

31、新簇的均值；until簇的质心不再变化。K-均值算法 012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassig

32、nreassignIV.层次聚类n层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。n按自底向上层次分解，则称为凝聚的层次聚类。n按自顶向下层次分解，就称为分裂的层次聚类。凝聚的和分裂的层次聚类 n凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。n分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。凝聚的和分裂的层次聚类 a,b,c,d,e c,d,e d,e a,b e d c b a 第 4 步 第 3 步 第 2 步 第

33、 1 步 第 0 步 凝聚的（AGENS）第 0 步 第 1 步 第 2 步 第 3 步 第 4 步 分裂的（DIANA）层次聚类方法的优缺点n层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。n单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。n层次聚类和其他聚类方法的有效集成可以形成多阶段聚类，能够改善聚类质量。这类方法包括BIRCH、CUR

34、E、ROCK、Chameleon等。三分类与预测1.简介2.决策树1.简介分类预测 分类n分类的目的是提出一个分类函数或分类模型（即分类器），通过分类器将数据对象映射到某一个给定的类别中。n数据分类可以分为两步进行。第一步建立模型，用于描述给定的数据集合。通过分析由属性描述的数据集合来建立反映数据集合特性的模型。这一步也称作有监督的学习，导出模型是基于训练数据集的，训练数据集是已知类标记的数据对象。第二步使用模型对数据对象进行分类。首先应该评估模型的分类准确度，如果模型准确度可以接受，就可以用它来对未知类标记的对象进行分类。训练集与测试集n训练集：训练集：数据库中为建立模型而被分析的数据元组形

35、成训练集。n训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:(v1,v2,.,vn;c);其中vi表示属性值,c表示类别。n测试集：测试集：用于评估分类模型的准确率。分类的两个阶段a.模型训练阶段 训练集b.使用模型 分类阶段评估准确率（测试集）对类标号未知的新数据分类 分类模型的构造方法机器学习方法：机器学习方法：决策树法知识表示是决策树规则归纳知识表示是产生式规则神经网络方法：神经网络方法：BP算法,模型表示是前向反馈神经网络模型粗糙集粗糙集(rough set)(rough set)知识表示是产生式规则 预测n预测的目的是从历史数据记录中自动推导出对给

36、定数据的推广描述，从而能够对事先未知的数据进行预测。n分类和回归是两类主要的预测问题。分类是预测离散的值，回归是预测连续值。n用预测法预测类标号为分类n用预测法预测连续值为预测 评估分类和预测方法的五条标准n预测的准确率n计算速度n鲁棒性n可伸缩性n可解释性2.决策树决策树学习简介决策树实例决策树学习的算法 决策树学习简介n决策树（Decision Tree）学习是以样本为基础的归纳学习方法。n决策树的表现形式是类似于流程图的树结构，在决策树的内部节点进行属性值测试，并根据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。内部节点是属性或属性的集合，叶节点代表样本所属的类或类分布。n经由

37、训练样本集产生一棵决策树后，为了对未知样本集分类，需要在决策树上测试未知样本的属性值。测试路径由根节点到某个叶节点，叶节点代表的类就是该样本所属的类。决策树实例n关于PlayTennis的决策树如图所示：High Overcast Normal Strong Weak Sunny Rain Outlook Wind Humidity No Yes Yes No Yes 决策树学习的算法 n决策树学习的基本算法是贪心算法，采用自顶向下的递归方式构造决策树。nHunt等人于1966年提出的概念学习系统CLS是最早的决策树算法，以后的许多决策树算法都是对CLS算法的改进或由CLS衍生而来。nQuin

38、lan于1979年提出了著名的ID3方法。以ID3为蓝本的C4.5是一个能处理连续属性的算法。n其他决策树方法还有ID3的增量版本ID4和ID5等。n强调在数据挖掘中有伸缩性的决策树算法有SLIQ、SPRINT、RainForest算法等。四Web 挖掘KnowledgeWWW目录I.Web 挖掘简介II.Web日志挖掘I.Web Mining简介1.产生原因2.应用3.分类4.过程1.产生原因n网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。n传统数据挖掘和文本挖掘技术的不断完善和应用。2.应用n查询相关信息n从Web数据发现潜在的未知信息n了解用户的兴趣爱好n信息个

39、性化3.Web 挖掘分类Web MiningWeb Content MiningWeb Usage MiningWeb Structure Mining Web内容挖掘nWeb内容挖掘是从文档内容或其描述中抽取知识的过程。nWeb内容挖掘策略直接挖掘文档的内容在其它工具搜索的基础上进行改进Web内容挖掘（续）n提取文字、图片或者其他组成网页内容成分的信息，即通过有效的内容挖掘能告诉我们哪些页面是德文或者法文的？哪些站点卖我们喜欢的东西？哪些页面介绍了我们感兴趣的知识？搜索引擎、智能代理和一些推荐引擎都使用内容挖掘来帮助客户在浩瀚的网络空间中寻找所需的内容。Web结构挖掘nWeb结构挖掘研究的是

40、Web文档的链接结构，揭示蕴含在这些文档结构中的有用模式，处理的数据是Web结构数据。是从WWW的组织结构和链接关系中推导知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。Web结构挖掘（续）n提取网络的拓扑信息网页之间的链接信息，即通过有效的结构挖掘能告诉我们哪些页面被其他页面所链接？哪些页面指向了其他页面？哪些页面的集合构成了一个独立的整体？Web日志挖掘nWeb日志挖掘的主要目标则是从Web的访问记录中（Web服务器log日志）抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了用

41、户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。Web日志挖掘（续）n一般的访问模式跟踪通过分析日志数据来了解用户的访问模式和倾向，以改进站点的组织结构n个性化的使用记录跟踪倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。Web日志挖掘（续）n提取关于客户如何运用浏览器浏览和使用这些链接的信息，即通过有效的日志挖掘能告诉我们那些客户访问了哪些页面？在每一页上待了多长时间？下一步单击了什么？在站点中是按照怎样的访问路线通向检查计数器，又是通过怎样的路线直接退出的？Web内容挖掘Web结构挖掘Web日志挖掘处

42、理数据类型IR方法：无结构数据、半结构数据数据库方法：半结构化数据Web结构数据用户访问Web数据主要数据自由化文本、HTML标记的超文本HTML标记的超文本Web文档内及文档间的超链Serverlog,Proxy serverlog,Client log表示方法词集、段落、概念、IR的三种经典模型对象关系模型图关系表、图处理方法统计、机器学习、自然语言理解数据库技术机器学习、专有算法统计、机器学习、关联规则主要应用分类、聚类、模式发现模式发现、数据向导、多层数据库、站点创建与维护页面权重分类聚类模式发现Web站点重建，商业决策4.Web挖掘过程n资源发现：在线或离线检索Web的过程，例如用爬

43、虫（crawler）或（spider）在线收集Web页面n信息选择与预处理：对检索到的Web资源的任何变换都属于此过程。词干提取高低频词的过滤汉语词的切分n综合过程：自动发现Web站点的共有模式n分析过程：对挖掘到的模式进行验证和可视化处理II.Web日志挖掘1.Web日志挖掘数据类型2.Web日志挖掘应用3.Web日志挖掘过程服务器日志数据类型nClient IP:128.101.228.20nAuthenticated User ID:-nTime/Date:10/Nov/1999:10:16:39-0600nRequest:GET/HTTP/1.0nStatus:200nBytes:-n

44、Referrer:“-”nAgent:Mozilla/4.61 en(WinNT;I)2.Web 日志挖掘应用nApplications电子商务中发现潜在客户增强终端用户信息获取的质量提高Web服务器的性能合理放置广告提高站点设计欺诈和入侵检测预测用户行为3.Web日志挖掘过程Web日志挖掘过程预处理数据挖掘模式分析 数据预处理n数据清理n用户对话识别n页面视图识别n路径完整数据清理n根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（status code）进行检查。清理后的Samp

45、le LogIP AddressTime/DateMethod/URIReferrerAgent202.120.224.4 15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.

46、0W98)202.120.224.4 15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.phpMozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET A.htmhttp:

47、/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htmMozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)用户对话识别n1.IP Address&Agentn2.Embedded Session IDn3.Registration(User Profile)n4.Cookien5.Software Agent(

48、Applet&Scrtipt)n6.Modified Browser用户对话识别（续）方法说明隐私性保护优点缺点IP地址/代理服务器假定每个独立IP地址/代理服务器组是独立用户低通常可用，无需附加技术。无法保证唯一性，在随机或者轮换IP情况下失效嵌入式对话ID通过动态形成页面将ID加入每个链接低/中等通常可用，不需依赖于IP地址无法了解重复访问，需要完全动态站点。注册用户确切地登陆站点中等可以跟踪单个用户，而不仅仅是浏览器不是全部用户都愿意注册Cookie在客户端机器上保留标识符中等/高可以跟踪重复访问能被禁止。不为大众接收软件代理服务器程序载入浏览器从而将日志数据返回高可以得到单个Web站点

49、的确切日志数据很可能被拒绝。不为大众接收用户对话识别15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.php15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htm15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htm15:30:01/2-Jan-01 GET 1.htmh

50、ttp:/ex.edu/index.htm15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htm15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:页面视图识别1-Ahttp:/ok.edu/res.phpBA.htm1-Ahttp:/ok.edu/link.htmEC

51、.htm1-CA.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:路径补全n解决由于Cache带来的问题路径不全的问题数据挖掘n统计分析n频繁项集和关联规则n聚类分析和分类n序列模式统计分析统计分析主要用于改进系统的性能、设计等包括：1)最频繁访问的页面2)每个页面的平均访问时间3)通过一个站点的平均时间频繁项集和关联规则频繁项集和关联规则可以寻找出经常频繁访问的page组，可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。包括两方面的应用：*user 用于Market

52、 segmentation(市场分割)和个人内容定制*page(content)后者主要用于IR和冲浪辅助聚类和分类聚类和分类序列模式序列模式可用于用户的 visit pattern.包括：1.趋势分析2.拐点检测模式分析n目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。Visualization五流数据挖掘n流数据简介n流数据频繁模式挖掘简介n流数据频繁模式挖掘算法I.数据流简介n概念 一系列连续且有序的点组成的序列 x1,xi,xn,称为数据流；按照固定的次序，这些点只能被读取一次或者几次n特点大数据量，甚至无限频繁的变化和快速的响应线性扫描算法，查询次数

53、有限nrandom access is expensiveDBMS 与 DSMSn持久的关系nOne-time queriesn随机的访问n“无限”的磁盘空间n当前状态有效n相对较低的更新率n很少“实时服务”n假定数据精确无误n访问策略由查询处理器在数据库设计时确定n瞬间的流 n连续的查询n序列化的访问n有限的主存n数据的到达顺序是关键n数据传输率未知n实时响应n过时/模糊的数据n变化的数据及数据量DSMSDSMSScratch StoreDSMSInput streamsRegisterQueryStreamedResultStoredResultArchiveStoredRelations

54、目前的DSMS项目(Stanford):A general-purpose DSMS(Cornell):sensors(Brown/MIT):sensor monitoring,dataflow(AT&T):telecom streams(OGI/Wisconsin):Internet XML databases(Georgia Tech):triggers,incr.view maintenance(Xerox):pub/sub content-based filtering(Berkeley):adaptive engine for sensors():stock tickers&stre

55、ams(Bellcore):network monitoring(UIUC):new project for stream data mining应用领域n新的应用领域 以连续的、有序的“流”的形式输入数据网络监听和流量控制(Network monitoring and traffic engineering)电话通信(Telecom call records)网络安全(Network security)金融领域(Financial Application)工业生产(Manufacturing Processes)网页日志与点击流(Web logs and clickstreams)应用实例n

56、网络安全 数据包流，用户的会话信息查询:URL 过滤，异常监测，网络攻击和病毒来源n金融领域交易数据流，股票行情，消息反馈查询:套汇可能性分析，模式现有的研究方向n流数据建模(Stream data model)STanford stREam datA Manager(STREAM)Data Stream Management System(DSMS)n流检索/查询建模(Stream query model)Continuous QueriesSliding windowsn流数据挖掘(Stream data mining)Clustering&summarization(Guha,Motwa

57、ni et al.)Correlation of data streams(Gehrke et al.)Classification of stream data(Domingos et al.)II.流数据频繁模式挖掘简介静态数据静态数据流数据流数据关系特点关系特点静态稳固短暂易失查询方式查询方式一次完成连续查询存取方式存取方式随机访问序列访问存储容量存储容量无限的辅存有限的主存响应速度响应速度无要求或尽量快必须快存储特点存储特点被动存储主动存储更新速度更新速度低不可预测响应特点响应特点较少“实时服务”实时响应流数据频繁模式挖掘要求只能对数据流进行一次扫描；处理的数据项是无穷的；实时响应数据

58、处理要求。数据流管理系统的抽象体系结构 III.流数据频繁模式挖掘算法n确定区间（deterministic bounds）近似算法：计算一个近似结果，但这个近似结果能够落入由真实结果构成的区间；n概率区间（probabilistic bounds）近似算法：计算一个近似结果，但这个近似结果能够以较高的概率落入由真实结果构成的区间。算法比较滑动窗口技术n自然滑动窗口31 days24 hours4 qtrs12 monthsTimeNow24hrs4qtrs15minutes7 daysTimeNow25sec.对数滑动窗口六隐私保护数据挖掘n隐私保护数据挖掘简介n隐私保护数据挖掘n面向企业信

59、用评估的分布式隐私保护数据挖掘研究一、隐私保护数据挖掘简介nWhatnWhynWhonGoalnHownAn Example什么是数据挖掘n数据挖掘是从大量数据中提取或“挖掘”知识的过程。n数据挖掘以客观、有效的数据源为物质基础。n数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。什么是隐私n针对不同的应用环境，隐私定义不同。n在信息时代，隐私指用户隐藏个人信息的权利和控制自己的信息给其他人的能力。什么是隐私保护数据挖掘n“getting valid data mining results without learning the underlying data values”n噪声背

60、景的数据挖掘n受限制的数据挖掘数据挖掘可能会违反用户的隐私n数据挖掘以准确的数据为数据源，进行数据归纳分析。n个体隐私记录级和属性级上的隐私n组织隐私结果级上的隐私，统计分析后的结果什么人需要隐私保护数据挖掘？n政府和公用事业部门疾病控制中心保险公司n工商业组织n跨国公司每个国家的法律是不同的n军事情报分析n犯罪行为分析n反恐分析隐私的限制不会阻止数据挖掘n数据挖掘的目标是结果的总结关联规则分类聚类n结果本身不会违反隐私不包含个人身份信息反映的是整个数据的归纳统计结果，而不是针对每个单位The problem is computing the results without access to

61、 the data!隐私保护数据挖掘的目标nPPDM encompasses the dual goal of meeting privacy requirements and providing valid data mining results.n保护隐私和满足安全性要求（安全性）n产生正确的数据挖掘归纳结果（准确性）n提供高效的数据挖掘算法（高效性）AccuracyEfficiencyPrivacy如何进行隐私保护数据挖掘计算频繁项集：ABC 5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC:R+count-freq.*DBS

62、izeR=17ABC:17+5-.05*100ABC:17ABC:17+9-.05*200ABC:12ABC:12+18-.05*300ABC:19ABC:19 R?ABC:YES!计算频繁项集：ABC 5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC:R+count-freq.*DBSizeR=17ABC:17+9-.05*200ABC:12+18-.05*300ABC:19 R?ABC:YES!二、隐私保护数据挖掘n隐私保护数据挖掘分类保护个体用户隐私个体用户隐私保护组织用户隐私组织用户隐私n研究方法数据隐藏安全多方计算保护个体

63、用户隐私个体用户隐私n这是一种记录和属性级上的隐私保护。在原始数据库中，类似于标识符、姓名、地址和喜好等用户数据作为用户的隐私应该被保护。保护敏感的原始数据的隐私保护数据挖掘方法应该能够使得用户的敏感的原始数据被修改，以便数据的使用者不能对用户的原始数据进行直接存储，不能查看用户的隐私，以此保护用户的私有数据。个体隐私:保护记录n每个项都不允许泄漏n记录的一部分是可以泄漏的个人身份信息个人身份信息n删除标识符n但是我们无法保证身份不能被推断候选码一些个体特有的属性Data Mining enables such tracing!保护组织用户隐私组织用户隐私n这是一种结果级上的隐私保护，这里的目

64、标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。在数据挖掘的统计模型中，有很多挖掘出的知识也会泄漏用户的隐私。保护敏感的挖掘知识的隐私保护数据挖掘方法能够保护用户的敏感知识，以便不会被泄漏用作其他的目的，造成用户重要信息的泄密。组织隐私n保护个体隐私是不够的n保护从组织中获得的敏感知识策略模式数据挖掘的结果n目标：身份信息不能泄漏数据挖掘之后的模式和知识同样不能泄漏Database用户数据挖掘挖掘得到的知识变换后数据库隐藏敏感的知识P3Pn发布的隐私策略n协同达成的一致策略隐私

65、保护数据挖掘架构nB2B的架构中，具体的事务分布在几个不同的站点。每个站点拥有一个包含大量事务的私有数据库。这里用到的主要计算技术是安全多方计算（Secured multiparty computation）及其变种。nB2C的架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。在线调查表是这种B2C架构的一个典型的例子。其中包含一个调查表收集器和分析器以及众多的数据提供者。解决方法分类n数据隐藏(Data Obfuscation)对数据进行挖掘时，不能看到真实的数据n安全多方计算仅仅可信的结点可以看到数据数据隐藏n目标:隐藏被保护信息私有数据可用噪声较大真实值不能确定得到主要技术匿名技术

66、 随机的数据转换(random data perturbation)阻塞技术(blocking)聚集或融合技术(aggregation or merging)交换技术(swapping)采样技术(sampling)基于阻塞的技术(blocking)BlockingAlgorithm主要用于组织隐私的保护随机的数据转换(random data perturbation)ABCD11101011000111101011ABCD111010100011110101DistortionAlgorithm随机的数据转换n目标统计属性可以较精确得到个体数据不能得到n离散型变量转换布尔型变量分类型(Category)变量n连续型变量转换布尔型变量转换分类型变量转换连续型变量转换布尔型变量转换n购物篮问题n数据位以概率p 被翻转n对经过变化的数据进行挖掘1TDCM C101,1CppMCCp p分类型变量转换nSelect-a-size RandomizationnCut and Paste RandomizationSelect-a-size Randomizationn给定大小为t的事务,构造t: