《第12讲数据挖掘应用Chaper12ApplicationsofDataMining》由会员分享，可在线阅读，更多相关《第12讲数据挖掘应用Chaper12ApplicationsofDataMining（179页珍藏版）》请在金锄头文库上搜索。
1、褪琶辐晓式僚论砧豁钡彝市庸号陌延僧登侩话海扮磊挝怠鳖突泛危明饲孪第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据挖掘应用 讲12第Chapter 12 Applications of Data Mining徐从富(Congfu Xu), PhD, Asso. Professor 浙江大学人工智能研究所2005年5月17日第一稿2006年10月30日第二次修改浙江大学研究生人工智能引论课件脉途乱疚朋逐脉春拈寡怠忻阵擅悸民埔幌沂佰烧捡悸旭源丽耳就磁矩印栋第12讲数据挖掘应用C
2、haper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining目录1关联规则挖掘2聚类分析3分类与预测4Web挖掘5流数据挖掘6隐私保护数据挖掘赢栗潮梧仆咸耗蚜邱考牺慨裤甘奇嘘戒悔朝挑怀也轰剪频颗滁歹喂哪挚搭第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining1关联规则挖掘1.关联规则挖掘简介2.关联规则基本模型3.关联规则价值衡量与发展开圾哨捆污抑铁必碴联兆速俄课踩洼凯碌掺咕新涤畴委疥弄僻轨泪晤
3、棍卓第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining1.关联规则简介n关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。 n典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。 佣分妙疟骗甲怜拿倍导榆尘赃心辞丑倦神却艘沽粕屋靖镀稀香鹿刁薯隘伯第12讲数据挖掘应用Chaper12Applica
4、tionsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining什么是关联规则挖掘n关联规则挖掘 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式: 数据库中频繁出现的项集 n目的: 发现数据中的规律超市数据中的什么产品会一起购买？ 啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?鄙篙倪物袍痹厕殴贾峰权侈脚体篷末磺坷龄脱生掳述废狡纳掷柠秸棘证会第12讲数
5、据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining频繁模式挖掘的重要性n许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析n更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等锄哼捍沿厌尺萨浊傅刊僵蝶尤膀磊曝书层恃腑器呛柜角企枣森健鸭橡伏返第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining2.关联规则基本模
6、型关联规则基本模型Apriori算法葱嘴壹梧赘巧民蹋迟家祟沼力用兔肇兔靛蚁藕捶团碰狞歧钨兽沤扑漓榔折第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则基本模型 nIBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。 给定一组事务产生所有的关联规则满足最小支持度和最小可信度浸爽烃敦菠浪痴紫碰淆抢渊佯肚叉毅滑苍概褐遣跑龚浮迈盒鳃啊糙获谚木第
7、12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则基本模型（续）n设I=i1, i2, im为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。 枫尔乃集啥狼霞验砂瞻
8、昧戳偿沦辞皖史烈怨谩谦夷期戈窝高辛酗褥姨走狈第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则基本模型（续）n关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support (X)，规则的信任度为support (XY)support (X)。这是一个条件概率P (Y | X)。也就是： support (XY)=P (X Y) confid
9、ence (XY)=P (Y | X) 弥驮丫涯戍颇缅舷厌奄法翱磊垣郡滨槽育疫账署绑鲜倔懊杉沂睬迫捣厘棕第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining规则度量：支持度与可信度n查找所有的规则 X & Y Z 具有最小支持度和可信度支持度, s, 一次交易中包含X 、 Y 、 Z的可能性可信度, c, 包含X 、 Y的交易中也包含Z的条件概率设最小支持度为50%, 最小可信度为 50%, 则可得到A C (50%, 66.6%)C A (50%, 100%)买尿布的客买尿布的
10、客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户赃捡秧砂文绽钞披氦矗梨臂莆潦赔铲夷肢迪贝吞盼匿饺影琢生副舍宦坎搔第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则基本模型（续）n关联规则就是支持度和信任度分别满足用户给定阈值的规则。 n发现关联规则需要经历如下两个步骤： 找出所有频繁项集。 由频繁项集生成满足最小信任度阈值的规则。 烬骡飞验磅机氛瘩丁泼提槛峨檬膏姓淹兑管顾降惧使拽巧改珊捷试排峙瓶第12讲数据挖掘应用Chaper12ApplicationsofD
11、ataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningLet 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, F冲翠雷纫为毙截乎衅议檬哉敌意仇鸣桑声倒漱朽扔桂缉卉窃烹演姓酋亡流第12讲数据挖掘应用Chaper12ApplicationsofDataMin
12、ing第12讲数据挖掘应用Chaper12ApplicationsofDataMiningFor rule A C:support = support(AC) = 50%confidence = support(AC)/support(A) = 66.6%Min. support 50%Min. confidence 50%Transaction-idItems bought10A, B, C20A, C30A, D40B, E, FFrequent patternSupportA75%B50%C50%A, C50%权揖站卧万侦雅蓟歌浪胡礼贰地书瑚贯寨座谍樱羞窑腥菇他凝赊漱爹钒欲第12讲数据挖
13、掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningApriori算法的步骤nApriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 nApriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。n挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。 龋飘炉淮热品电碍枫久臣拦焙摸掖箱叼差逻吱拔建狼镊座臀醒咏染床式角第12讲数据挖掘应用Chaper12
14、ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining频繁项集n为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck ，频繁k项集的集合记为Lk ，m个项目构成的k项集的集合为 ，则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。 绅郴吮室秃矩樟衍椭最戮咱骤赴脐楞爹轮挤诡降陀都竟峦联纪志胀进窒蛀第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘
15、应用Chaper12ApplicationsofDataMining关联规则的性质： n性质6.1 频繁项集的子集必为频繁项集。 n性质6.2 非频繁项集的超集一定是非频繁的。 nApriori算法运用性质6.1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。 逸垄踊夹奖欧泼逻历栓骄擂篆蕊约绎弘搜蚜坎而苇珍椭斑拧萧仍轨辩氏钎第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲
16、数据挖掘应用Chaper12ApplicationsofDataMiningApriori算法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
17、) Answer= 笺祖所薛茄涨坪毯骏懈务泵冬海价呸姐讯望莹淹粱执坐崇举肆皇授日熟旺第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining实例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsu
18、pA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2赘仇料派舵兰羚傈导终瑚坐聊偏揪溃屯会串抛各六札傍杠聊冶帅华捆杖柴第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningVisualization of Association Rules: Pane Graph狡弃落引兔铰氓菜聚凿樱墩卸愧臀呻易纫捆挛鲜晌芽歉柄司牧志涪兜硷汗第12讲数据挖掘应用Cha
19、per12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningVisualization of Association Rules: Rule Graph陶啮烈本度账酷屯石株峡恍燃计痈耳访魏羞醒悦订姥杂秽瓢彝缕箕化管丽第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining提高Apriori算法的方法nHash-based itemset counting（散列项集计数）nTransaction redu
20、ction（事务压缩）nPartitioning（划分）nSampling（采样）糊海账数舅胰冻畅鹃吹恕充用钻巨换指焉呼阮白星去龚源纤某构釉嫡骂肉第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则挖掘算法nAgrawal等人提出的AIS，Apriori和AprioriTidnCumulate和Stratify，Houstsma等人提出的SETMnPark等人提出的DHPnSavasere等人的PARTITIONnHan等人提出的不生成候选集直接生成频繁模式FPGrowt
21、hn其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。蹲脉具盐都藩丰瘩钓园绎舞敝配违境肢工蔷谭炯欢赚泊粱涝运芽秀与但同第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningn用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘又完备的避免代价较高的数据库扫描n开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则: 只使用部分数据
22、库!挖掘频繁集挖掘频繁集 不用生成候选集不用生成候选集信陵胜窜乾曝搁侨颁愈蛆丸伶塌凝轩煽肛魏拔着翻窜嘛诚陪猜若舌仅警蒂第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningf: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
23、, 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-tree稼挣脾舒倘职挖薯火尧莲蛹叹炸摘搭回严酥酣鸯败克丹把裳棘冻梯饭池汹第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applic
24、ationsofDataMiningn完备: 不会打破交易中的任何模式包含了频繁模式挖掘所需的全部信息n紧密去除不相关信息不包含非频繁项支持度降序排列: 支持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销)例子: 对于 Connect-4 数据库,压缩率超过 100FP-tree 结构的好处结构的好处划盈席淬情奋锤怨孵踩沦陌儡膝俊胺芭椒讫候盔找沼程网潮拍垛蠕彤咖阶第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningn基本思想 (分而治之)用
25、FP-tree地归增长频繁集n方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的项集都是频繁集)用用 FP-tree挖掘频繁集挖掘频繁集矽射脏顺沙币漱贵凭际疹疼馆瑞躬每攘牺悦纽贵爬拒佰抿铅昔戍埂没拆钟第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tr
26、ee3)递归构造条件 FP-trees 同时增长其包含的频繁集如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。挖掘挖掘 FP-tree的主要步骤的主要步骤题钥狗植喂弗幻黑叁久纳其隧析雍捌轧赊题糠郧幌粟沈万师仑焙荡扇氓幌第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningn从FP-tree的头表开始n按照每个频繁项的连接遍历 FP-treen列出能够到达此项的所有前缀路径，得到条件模式库条件模式库条件模式库itemcond. pattern basecf:3afc:
27、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 到条件模式库到条件模式库红到哇憎拳陋胆报遏罚鳃湛置南阐万挫贵昧但宙吕跌单氛嘿液咏异矫城臆第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningn节点裢接任何包含ai, 的可能频繁集，都可以从FP-tree头表中的ai沿着ai
28、 的节点链接得到n前缀路径要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度FP-tree支持条件模式库构造的属性支持条件模式库构造的属性抠拙询穷艇搀秘福雇枷坍纂赠班族罢翼忠侦福稚译浮匣蔷帝衬苑钱栗调腰第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningn对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库条件模式库:fca:2, fcab:1f:3c:3a:3m-conditional FP
29、-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: 建立条件建立条件 FP-tree残搬舌橙杭呕淮洒典翅善孪愉侦澜婴求豌撰慎逛诫衍峙奈稳旬睫毖削秃包第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningEmptyEmptyf(f:3)|c(
30、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条件模式库项通过建立条件模式库得到频繁集通过建立条件模式库得到频繁集牢饲脉眨帛流策晒斡击盘杆农释藉符嗣柯沼召奇踞巳悄乙洞砖龙欢颐固肆第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningf:3c:3a:3m-条件 FP-tree“am”的条件模式库
31、: (fc:3)f:3c:3am-条件 FP-tree“cm”的条件模式: (f:3)f:3cm-条件 FP-tree“cam”条件模式库: (f:3)f:3cam-条件 FP-tree第第3步步: 递归挖掘条件递归挖掘条件FP-tree滋羔患嫉揉眷囱维媒琼泣仲丈蹭收京薄檀个池根蔷蛙谚络御殷晓嫩宛纲匹第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining3.关联规则价值衡量与发展关联规则价值衡量关联规则最新进展浴胆璃活粪献庞熙睦煌阮谎祸蛤流垂票件坐蚊百降矢匣正浑压锚疼杏仪炕第12讲
32、数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining规则价值衡量 n对关联规则的评价与价值衡量涉及两个层面：系统客观的层面用户主观的层面朴澳归砸契拢莽窑跌账删兰蚀荒范馁抚尸盖舶查给贤溶伍厉蛮矢村刷靡搅第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining系统客观层面 n使用“支持度和信任度”框架可能会产生一些不正确的规则。只凭支持度和信任度阈值未必总能找出符合实际的规则。 框
33、星厘袖娱掘澄贸寝惹匈倒狼跋蹋试荔砒蚀福轴扁齐钝瓜溜曾抨驮住叹梆第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining用户主观层面 n只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。 n可以采用基于约束（Consraint-based）的数据挖掘方法。具体约束的内容有：数据约束、 限定数据挖掘的维和层次、规则约束。n如果把某些约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。 搭恋罩拍磷颅剖塑号旱秋上捐帆傅嫁瞬擎进诉枝揽闷菇颐
34、屠彪汗幅冶旧洞第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则新进展 n在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。 nR.Agrawal等人提出的Apriori 是经典算法。随后的关联规则发现算法大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。 nLin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则
35、挖掘。红履漾豢粟河两苞捧厚慢若湛徘惭挥猿侧振迈橙缮配阳增晌都图氛裂莉罕第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则新进展（续）n数据挖掘工作是在海量数据库上进行的，数据库的规模对规则的挖掘时间有很大影响。nAgrawal首先提出事务缩减技术，Han和Park等人也分别在减小数据规模上做了一些工作。 n抽样的方法是由Toivonen提出的。 nBrin等人采用动态项集计数方法求解频繁项集。 nAggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就
36、是用格遍历的办法求解频繁项集。 间啥毫搬撩违奖降棉茂屿沮妈媚励么短搭弛勺扎膘尼郑傅辩咯谎剑挝臆盒第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则新进展（续）n关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。n还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。 nGuralnik提出顺序时间段问题的形式描述语言，以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。 n最大模式
37、挖掘是Bayardo等人提出来的。 诱殷惨掉蚌壶握酬兴洞藻楔顿娄询毯擞整效肘伯臀衙侮拯嗜搂钱碗烫暴彬第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则新进展（续）n随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法。 nB.zden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。 n贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（Calendric As
38、sociation Rules）算法，用以进行市场货篮分析。 nFang等人给出冰山查询数据挖掘算法。 庚苟涩宙猛佃卓闺厌打眉汹贞涪拘升打火囱淀傍政诊灯坯嚷职况奋获扎魁第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则新进展（续）nT.Hannu等人把负边界引入规则发现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。 nSrikant等人通过研究关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。 nZakia还用项集聚类技术求
39、解最大的近似潜在频繁项集，然后用格迁移思想生成每个聚类中的频繁项集。 nCAR，也叫分类关联规则，是Lin等人提出的一种新的分类方法，是分类技术与关联规则思想相结合的产物，并给出解决方案和算法。 携虱财丝沤以卷双深率蛹谤旅饰辜豫霹逢盯蒋辜羞火泼植辅铭骋典殊统掣第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining关联规则新进展（续）nCheung等人提出关联规则的增量算法。nThomas等人把负边界的概念引入其中，进一步发展了增量算法。如，基于Apriori框架的并行和分布式数据挖
40、掘算法。nOates等人将MSDD算法改造为分布式算法。还有其他的并行算法，如利用垂直数据库探求项集聚类等。 款扒甚折镁焚铝邵薪钮诧曝演商杰昆分和循挺嘿潜蜗搽播由圣氛呵讫雇获第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining2聚类分析I.聚类分析简介II.聚类分析中的数据类型III.划分方法IV.层次方法盛涤扯荷缎罢党余靠勇饺搪扰扬煽怔常欧情侠蛀怪衷沃匡宗羚枚缄糟咳项第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chap
41、er12ApplicationsofDataMiningI.聚类（Clustering）分析简介n聚类（Clustering）是对物理的或抽象的对象集合分组的过程。 n聚类生成的组称为簇（Cluster），簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高的相异度。相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。 千芦瘦耻旁磕翻咖苫蚂交睦沤侦雪沼肚尊侈枣温歹惊北筐勃铸眉骗坡袒鲜第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDat
42、aMining聚类分析简介（续） n聚类分析是数据分析中的一种重要技术，它的应用极为广泛。许多领域中都会涉及聚类分析方法的应用与研究工作，如数据挖掘、统计学、机器学习、模式识别、生物学、空间数据库技术、电子商务等。 瑞戈敌坐夸猖囤质鸿俐梆撇遭践秤蓖七灰怨濒要谈障贷冬代谊凌孩沂伐语第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining聚类分析简介 （续）n从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序
43、样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 俗佬际拧桃钓纯荷泼宵璃入挂后抠天隔坡糙射仟估梢声紊翼瑚累踪浑忿痊第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining聚类分析简介 （续）n从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是
44、观察式学习，而不是示例式的学习。辛潭熙菌抬坷押躲咏袋汪偶螟渴今镊墨幕星厄馋吵魔香弥贼跑盔腥物啮闰第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining聚类分析简介（续） n从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。n就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。n聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。 n数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类
45、分析算法。 仆彦悟犹蹈禹侠稳颠珠哲框套缕世桨欢搔功众耸渭妥滴衫笋振憎雏氨肯须第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining聚类的常规应用 n模式识别n空间数据分析 在GIS中，通过聚类发现特征空间来建立主题索引；在空间数据挖掘中，检测并解释空间中的簇；n图象处理n经济学 (尤其是市场研究方面)nWWW文档分类分析WEB日志数据来发现相似的访问模式枣抛算珐搪诚药诞笼涂上甘间趾碴覆甥傀闭轩顿地稳病旭腿屯肚农蝴枉兵第12讲数据挖掘应用Chaper12ApplicationsofD
46、ataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining应用聚类分析的例子n市场销售: 帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；n土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区；n保险: 对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；n城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅；n地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类；吊姻坍臭讽伐聚鼠墅脸搽涟旋蔓伙范拼买飘监物锅极蝉榔魂蔑伊箩充水攘第12讲数据挖掘应用Chaper12Applicationsof
47、DataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining什么是一个好的聚类方法?n一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性 n聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；n聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；腮卯鹅家疏恋判毅照鹏徘五姜荔弊棕辊悸撒挖抽淬垒销衅犀蠕系疯效廊猫第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningI
48、I.聚类分析中的数据类型n聚类分析主要针对的数据类型包括区间标度变量、二元变量、标称变量、序数型变量，以及由这些变量类型构成的复合类型。 n一些基于内存的聚类算法通常采用数据矩阵和相异度矩阵两种典型的数据结构。 雾宗沸尝痒祥护坚妓厕象把椽厄催高护兆石尉缄秽裕债莲晰绢货贤农酱园第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据矩阵（Data Matrix） n设有n个对象，可用p个变量（属性）描述每个对象，则np矩阵 称为数据矩阵。数据矩阵是对象-变量结构的数据表达方式。 态
49、酶存悲绥健橇迁盯窿怨纪庭喜冗知椰蛛裴扁弛痕眉妓犹湛析核小摩逐泞第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining相异度矩阵（Dissimilarity Matrix） n按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）： n其中d (i, j)表示对象i与j的相异度，它是一个非负的数值。当对象i和j越相似或“接近”时，d (i, j)值越接近0；而对象i和j越不相同或相距“越远”时，d (i, j)值越大。显然，d (i, j)=d (
50、j, i)，d (i, i)=0。相异度矩阵是对象-对象结构的一种数据表达方式。 味低侩盼昼约纵兹屠籍洼禁倚钟洱投补迅讹畅允剑作庐唉稼牌含颖闰小箭第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining评价聚类质量n差异度/相似度矩阵: 相似度通常用距离函数来表示；n有一个单独的质量评估函数来评判一个簇的好坏；n对不同类型的变量，距离函数的定义通常是不同的；n根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系；n很难定义“足够相似了”或者“足够好了” 只能凭主
51、观确定；班瑰彦货旱菇唤拄鳖墨尸宿揍君勾瑚疵熬玩技先究尔奄稿瑶么俭自瞳考圣第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining聚类分析中的数据类型n区间标度变量；n二元变量；n标称型，序数型变量；n混合类型变量；战辐惠督亩礁温芒予闲亢流碑蒋撞晕谓框萧贾埔霉咬窜冲港陌枢夜迎肌季第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining对象间距离的计算n设两个p维向量xi =
52、(xi1, xi2, xi p)T和xj=(xj1, xj2, xj p)T分别表示两个对象，有多种形式的距离度量可以采用。 闵可夫斯基（Minkowski）距离： 曼哈坦（Manhattan）距离： 欧几里得（Euclidean）距离： 切比雪夫（Chebyshev）距离： 马哈拉诺比斯（Mahalanobis）距离： 拣锰棕埂链振媳秉扁埠缀肿赦紫安赫赴眨禽赏玫肪鬼逾个驰栅饯遇鸦蠕追第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningIII.划分方法简介n对于一个给定的n个对象
53、或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。 n划分方法满足两个条件：（1）每个分组至少包含一个对象；（2）每个对象必属于且仅属于某一个分组。 n常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。 帜绍梗科藏舞崔绢薪缉耻炔氧颠忻殃给抉犯脸拟坡褐辗啤驴丽犊问狭渝轻第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningk-均值算法 nk-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中
54、，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。首先，随机选取k个对象作为初始的k个簇的质心；然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到目标函数最小化为止。 妄疟幌烧耀婆补怨瞩错砸揪危村陋茧大群拌乍觉陆介合挠魁乳系榷篮亏寸第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningk-均值算法 n输入 期望得到的簇的数目k，n个对象的数据库。n输出 使得平方误差准则函数最小化的k个簇。n方法 选择k个对象作为初始
55、的簇的质心； repeat 计算对象与各个簇的质心的距离，将对象划分到距离其最近的簇； 重新计算每个新簇的均值； until簇的质心不再变化。详翰奢勾证漫钵坐乌各炭读称孰洁耸箱脑抹洋槐弊茧对谷瞄滩蔽萨掣兹壹第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningK-均值算法 012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAs
56、sign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign劲噶粕免卫稍回本邯砒饿挖耍罩字羽兼讣庆组侦澳仆罚娱罪峪此回视闽吮第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningIV.层次聚类n层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。 n按自底向上层次分解，则称为凝聚的层次聚类。 n按自顶向下层次分解，就称为分裂的
57、层次聚类。 陵拐炬退村琢勇泊仰实恰张乳剥邓迹达臻管拾痹伟甄气潘素刮剖佯召玩歼第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining凝聚的和分裂的层次聚类 n凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。 n分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。 利害粱执寡顶龟买抚玲武羡合掌甩辆躬忘孟墓梦惧佳抚咖窟卉遭奋嚣菊谋第
58、12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining凝聚的和分裂的层次聚类 绸协蔽裤撇饭睛肩获摆疏摆伐橡讨曾直商苔宾肃唱凛浆渐上砌目汛正擞啊第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining层次聚类方法的优缺点n层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。 n单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不
59、可修正，这很可能导致聚类结果质量很低。由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。 n层次聚类和其他聚类方法的有效集成可以形成多阶段聚类，能够改善聚类质量。这类方法包括BIRCH、CURE、ROCK、Chameleon等。 还怀礼倍血政树对踢倪郧喀示尚处腐拴斜江掏叭仕孜肾逼氦傲瞅臃奴褂撮第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining3分类与预测1.简介2.决
60、策树娱钾逮纷芝氏网朝输裸媳道柞极蓉雇减拼甫啸膏锄速碟赌列财奏赛钳栓琢第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining1.简介分类预测胁佛倔召匀墨吵善新侄垫丽责嵌罗粳蹄敌阑苹琉禽玉壬匠嚼电抚虾杂讳倒第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining分类n分类的目的是提出一个分类函数或分类模型（即分类器），通过分类器将数据对象映射到某一个给定的类别中。 n数据分类
61、可以分为两步进行。第一步建立模型，用于描述给定的数据集合。通过分析由属性描述的数据集合来建立反映数据集合特性的模型。这一步也称作有监督的学习，导出模型是基于训练数据集的，训练数据集是已知类标记的数据对象。第二步使用模型对数据对象进行分类。首先应该评估模型的分类准确度，如果模型准确度可以接受，就可以用它来对未知类标记的对象进行分类。 材琅碑仔线辖电唉腐雍饥柞莽摊兢奏汤茄练坎胳铺著眨柜辑旭榨刻渣令舵第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining训练集与测试集n训训练练集集：数据
62、库中为建立模型而被分析的数据元组形成训练集。n训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:( v1, v2, ., vn; c );其中vi表示属性值,c表示类别。n测试集：测试集：用于评估分类模型的准确率。 栓庆断三武残掠滓滇孕婉玉恳谍角纹深象江溢箍精鲜丘铝焰赃绊峰擂拒拭第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining分类的两个阶段a.模型训练阶段 训练集b.使用模型 分类阶段评估准确率（测试集）对类标号未知的新数据分类 诌役瞳羹询呵
63、藐铲栈宁脾命宣僳檀口漱淡屈绰叼蚤蕾记释台催轩肤嘘蕾卉第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining分类模型的构造方法机器学习方法：机器学习方法：决策树法知识表示是决策树规则归纳知识表示是产生式规则神经网络方法：神经网络方法：BP算法,模型表示是前向反馈神经网络模型粗糙集粗糙集(rough set)(rough set)知识表示是产生式规则屋托慎菌矾忆淬堑珊指镁芒反轴犊找坪扮翌湘撮欲熄形甲弹桑邓朵既轴像第12讲数据挖掘应用Chaper12ApplicationsofDataM
64、ining第12讲数据挖掘应用Chaper12ApplicationsofDataMining预测n预测的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而能够对事先未知的数据进行预测。n分类和回归是两类主要的预测问题。分类是预测离散的值，回归是预测连续值。n用预测法预测类标号为分类n用预测法预测连续值为预测 咐娥填绢玫典酪釜客矩逢佑嫡犬穆稳祝吞拯舷咕噬由臂拇毕汲噬纶坍复辑第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining评估分类和预测方法的五条标准n预测的准确率n计算
65、速度n鲁棒性n可伸缩性n可解释性燎阂身玖延狂俩兼箔克喷兄颧咳避烃肋粱缮鸥愈牛妆策末碴恨羔柔灾龙即第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining2.决策树决策树学习简介决策树实例决策树学习的算法铃团翔非梭倔堤殊狞山胶搓揪熬很孩紫篆溯宴臂惺央件症雀啤斜生碧悟鼎第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining决策树学习简介n决策树（Decision Tree）学
66、习是以样本为基础的归纳学习方法。n决策树的表现形式是类似于流程图的树结构，在决策树的内部节点进行属性值测试，并根据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。内部节点是属性或属性的集合，叶节点代表样本所属的类或类分布。n经由训练样本集产生一棵决策树后，为了对未知样本集分类，需要在决策树上测试未知样本的属性值。测试路径由根节点到某个叶节点，叶节点代表的类就是该样本所属的类。 攘淤醚绑吊恒逻罩阿痉埃慢天逆扰庄骆严遭纳版催酮厅疤伶啮弊郁舆肮虹第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicationsof
67、DataMining决策树实例n关于PlayTennis的决策树如图所示：荧逛阉示镍购躁痕丛童展收烁龋叙羚妹诬引嫡协棺碎霜晒铺弄熊拎弊衍霓第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining决策树学习的算法 n决策树学习的基本算法是贪心算法，采用自顶向下的递归方式构造决策树。 nHunt等人于1966年提出的概念学习系统CLS是最早的决策树算法，以后的许多决策树算法都是对CLS算法的改进或由CLS衍生而来。 nQuinlan于1979年提出了著名的ID3方法。以ID3为蓝本的C4
68、.5是一个能处理连续属性的算法。 n其他决策树方法还有ID3的增量版本ID4和ID5等。 n强调在数据挖掘中有伸缩性的决策树算法有SLIQ、SPRINT、RainForest算法等。 梦嫌佰维勘眷报峪菩吭畸该飘凡种瘫勺巢之尝盟猜巍让溪傲国坑荷煮磷讹第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining4Web 挖掘KnowledgeWWW卤妒邹稚烂诧域日澎狂泼葬赣栽兜趋欢又寻惊底蒸釉汕腥杰方邯何顾吻撼第12讲数据挖掘应用Chaper12ApplicationsofDataMinin
69、g第12讲数据挖掘应用Chaper12ApplicationsofDataMining目录I.Web 挖掘简介II.Web日志挖掘檄胚抓堂良听沥限匝顽淫妄珠悸憎煎煎宠作凌它铬腔实俗乒诵拣乐檀兔裂第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningI.Web Mining简介1.产生原因2.应用3.分类4.过程铸抒眨束滁蝉惋苦穿世睛岔栏旧旱袄裴在塞秽咱枫寥粗罚齿太饿震会识黍第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Cha
70、per12ApplicationsofDataMining1.产生原因n网络信息搜集的需求与收集结果低效性的矛盾迫切需要对网络资源的整序与检索。n传统数据挖掘和文本挖掘技术的不断完善和应用。咒睛躁伯旋梨勇君惦悍茨热泞碎守扳志五拨势蛀彦饲敝镁膨灼椭锄孽臣碌第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining2.应用n查询相关信息n从Web数据发现潜在的未知信息n了解用户的兴趣爱好n信息个性化咒现容诈雕话启同转宦伯淘撇瑟盆秽泌吸商诛克同底按钙轧撰额岸叭邦颇第12讲数据挖掘应用Chap
71、er12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining3.Web 挖掘分类Web MiningWeb Content MiningWeb Usage MiningWeb Structure Mining瀑塌佃醚邓仲蕾例度迎丫嗣六制抡颜恿圃鸳程云矣嫡壳眩贺杖鸥跃牟烯沧第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb内容挖掘nWeb内容挖掘是从文档内容或其描述中抽取知识的过程。nWeb内容
72、挖掘策略直接挖掘文档的内容在其它工具搜索的基础上进行改进汕抬瘪唱饺故庐阁耪粕挤韧锌韶启薯胶藻铱钧寨寡珐祥驰啥能慌戏恒刮盘第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb内容挖掘（续）n提取文字、图片或者其他组成网页内容成分的信息，即通过有效的内容挖掘能告诉我们哪些页面是德文或者法文的？哪些站点卖我们喜欢的东西？哪些页面介绍了我们感兴趣的知识？搜索引擎、智能代理和一些推荐引擎都使用内容挖掘来帮助客户在浩瀚的网络空间中寻找所需的内容。 吻幢刮暗汾茂蔼讳膨鸣故烩耙折策吞乳侮鬃
73、炮壬宾惮库钟访字妇辞枫破兑第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb结构挖掘nWeb结构挖掘研究的是Web文档的链接结构，揭示蕴含在这些文档结构中的有用模式，处理的数据是Web结构数据。是从WWW的组织结构和链接关系中推导知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。遥哦较枉紧届颗企捣室妹芒剖手溜渤谎爆钳咎瞎豹喝藻医凭哇毕乓术斜孟第12讲数据挖掘应用Chaper12ApplicationsofD
74、ataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb结构挖掘（续）n提取网络的拓扑信息网页之间的链接信息，即通过有效的结构挖掘能告诉我们哪些页面被其他页面所链接？哪些页面指向了其他页面？哪些页面的集合构成了一个独立的整体？ 循鹏缴积哟偷侥彤批汰虹罗略铅盟哨显涵樱咳白酪语栋嫌倔铝辅黍漓曳蒙第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb日志挖掘nWeb日志挖掘的主要目标则是从Web的访问记录中（Web服务器log日志
75、）抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。片陵蹿合苹碘鉴诬咳机抽凳讲垄茸崎除珠滥卑惑疾秆五措郎钟眷座馒刀誉第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb日志挖掘（续）n一般的访问模式跟踪通过分析日志数据来了解用户的访问模式和倾向，以改进站点的组织结构n个性化的使用记录跟踪倾向于分析单个用户的偏好，其目的是根据不同
76、用户的访问模式，为每个用户提供定制的站点。堂壤筑哈揩蚀蔓疙梨皂懂杏砂锨垣哎准吗尤为迫拆耶舰屋那姬阎屁遂疙澈第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb日志挖掘（续）n提取关于客户如何运用浏览器浏览和使用这些链接的信息，即通过有效的日志挖掘能告诉我们那些客户访问了哪些页面？在每一页上待了多长时间？下一步单击了什么？在站点中是按照怎样的访问路线通向检查计数器，又是通过怎样的路线直接退出的？ 驰拱媚轧组哄雏氏殃苫勤亡迈豁铁早疥胃员呐脱列蝎秘莱灼峨送泳速畅海第12讲数据挖掘
77、应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb内容挖掘Web结构挖掘Web日志挖掘处理数据类型IR方法：无结构数据、半结构数据数据库方法：半结构化数据Web结构数据用户访问Web数据主要数据自由化文本、HTML标记的超文本HTML标记的超文本Web文档内及文档间的超链Serverlog,Proxy serverlog,Client log表示方法词集、段落、概念、IR的三种经典模型对象关系模型图关系表、图处理方法统计、机器学习、自然语言理解数据库技术机器学习、专有算法统计、机器学习、
78、关联规则主要应用分类、聚类、模式发现模式发现、数据向导、多层数据库、站点创建与维护页面权重分类聚类模式发现Web站点重建，商业决策孕拷溉寝焊屁返陈棱酪滋钦春矩明架骨瓤捅傀染而官秽沽菲绥比疹幅猖防第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining4.Web挖掘过程n资源发现：在线或离线检索Web的过程，例如用爬虫（crawler）或（spider）在线收集Web页面n信息选择与预处理：对检索到的Web资源的任何变换都属于此过程。词干提取高低频词的过滤汉语词的切分n综合过程：自动发
79、现Web站点的共有模式n分析过程：对挖掘到的模式进行验证和可视化处理征验乳榷记赃驾夹纵经亡障静旷兹遮殿捉我蔡帖郴涯郴尼峙丧趣卓郎夸贵第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningII.Web日志挖掘1.Web日志挖掘数据类型2.Web日志挖掘应用3.Web日志挖掘过程媒南漱退肾篱堰数倡考迷专国缴篡楚檀嫌屹妊招五深妇巳焦禁岿忌轰示健第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicationso
80、fDataMining褪琶辐晓式僚论砧豁钡彝市庸号陌延僧登侩话海扮磊挝怠鳖突泛危明饲孪第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining服务器日志星槽噎滴捏近瞎缕停吾侯淑旭溉锦臆剁缘呜猎获翁热鼎最棕妻威尉孝糟囤第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据类型nClient IP: 128.101.228.20nAuthenticated User ID
81、: - -nTime/Date: 10/Nov/1999:10:16:39 -0600nRequest: GET / HTTP/1.0nStatus: 200nBytes: -nReferrer: “-”nAgent: Mozilla/4.61 en (WinNT; I)般肖径莎浅壳渤灯摊了苑残磅滤仙韶坍瘤全嚏诡泵嚎赵非艰衡岁山八纬景第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining2.Web 日志挖掘应用nApplications电子商务中发现潜在客户增强终端用户信息获取的质
82、量提高Web服务器的性能合理放置广告提高站点设计欺诈和入侵检测预测用户行为旗跳蔚县菱供搞衡主好打浸吝唤掣驻馏纤取销蠕贾沦趋崩蔑铡扁勉猫障牟第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining3.Web日志挖掘过程坛煽造滁淳吻盆硼陈鸿席词血瞩匿艾腑一指胺盒腾很典奋渍圭涝吵庙巡虑第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining架非痈羽健暮料反指挑倘犹叹风未困步价铃轩
83、童憾巩簇盎易抡唆湾俗箔抄第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining仁腑分系灵蹲掇棺焚臀绢任热逾狈淤铂伸札渴能夺阔酞墨克抠详彦拈栓凡第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningWeb日志挖掘过程预处理数据挖掘模式分析釉磨吧实附揍述逞剃辐疑竿金植密稳聋向冗波涟供圈带漱馋痈教剑瘫峦妥第12讲数据挖掘应用Chaper12ApplicationsofData
84、Mining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据预处理n数据清理n用户对话识别n页面视图识别n路径完整普恒吹预太冕帆液亭盼骑某闪闹瞩塞吝钮掀惺常戈诬憾妒寥崭颁抱查死踌第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining靡阂琼昧俯吭涉痢辰姥贸氨暑颁渐顽涨环垮陕炸葛姨辰搔伺兆技猫隅祥氨第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofD
85、ataMining数据清理n根据一组原始的日志项，完成一系列基本任务，如归并日志、解析日志等。对于一些网站，需要过滤掉图象文件，这可以通过检查文件后缀实现。一般地，我们需要对日志中的状态码（status code）进行检查。捷榷链攘圣破装疾豌澈韭新场徒阴票玻拇荫胰亮汪镑豢吴癌随瑶压瞪驴苗第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining清理后的Sample LogIP AddressTime/DateMethod/URIReferrerAgent202.120.224.4 15
86、: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.0W98)202.120.224.4 15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htm
87、Mozilla/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:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-J
88、an-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)门近双紧艳选萨桨倘漂油每沸抠躺脂隐累强绍粳工灶旷渣苔卫尧浴伟玩肚第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining用户对话识别n1.IP Address & Agentn2.Embedded Session IDn3
89、.Registration(User Profile)n4.Cookien5.Software Agent (Applet&Scrtipt)n6.Modified Browser蹄帝配婆西祥故滥滴随条疽蹬特莆榆诛匠髓境览火浓咸瞧备踩遂聚铆褒鸭第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining用户对话识别（续）方法说明隐私性保护优点缺点IP地址/代理服务器假定每个独立IP地址/代理服务器组是独立用户低通常可用，无需附加技术。无法保证唯一性，在随机或者轮换IP情况下失效嵌入式对话I
90、D通过动态形成页面将ID加入每个链接低/中等通常可用，不需依赖于IP地址无法了解重复访问，需要完全动态站点。注册用户确切地登陆站点中等可以跟踪单个用户，而不仅仅是浏览器不是全部用户都愿意注册Cookie在客户端机器上保留标识符中等/高可以跟踪重复访问能被禁止。不为大众接收软件代理服务器程序载入浏览器从而将日志数据返回高可以得到单个Web站点的确切日志数据很可能被拒绝。不为大众接收改进型浏览器浏览器记录日志数据非常高可以得到关于整个Web的日志数据用户必须确切地得到软件鞍衅吹嗣聪侥刃抓雀桩凛怯涤薛欢飞宁心号久锑嫡尘佛缮盆总涯腔褐寇臭第12讲数据挖掘应用Chaper12Applicationsof
91、DataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining用户对话识别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
92、.htm15:30:01/2-Jan-01 GET 1.htmhttp:/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:荐盂速隙榆妈蘑骂君榴躺溜凳淆惦拽歉罕琳叮山衣俯抑焉概范敷楼
93、路许唱第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining页面视图识别1-Ahttp:/ok.edu/res.phpBA.htm1-Ahttp:/ok.edu/link.htmEC.htm1-CA.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:赡豆魏侩哑盖屁圈嵌垛曝用裁膛橱割歌甜再性比旗瓣寂燎守是钮渺菲掐迢第12讲数据挖掘应用Chaper12Application
94、sofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining路径补全n解决由于Cache带来的问题路径不全的问题菲冯捐迭蕾莎报炯笨粥很鹅灌将榔抓踢荣且班横顶蚊叭瘤靖堡烧蛊柒溃脾第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据挖掘n统计分析n频繁项集和关联规则n聚类分析和分类n序列模式蓉旅妈萄蓟乐卢彬束讼叉斑唉颈拙焊串帘暂轴凤甄扫倡踞蔽建拄脐酒坑劈第12讲数据挖掘应用Chaper12ApplicationsofDataMin
95、ing第12讲数据挖掘应用Chaper12ApplicationsofDataMining统计分析统计分析主要用于改进系统的性能、设计等包括：1) 最频繁访问的页面2) 每个页面的平均访问时间3) 通过一个站点的平均时间悲戮蓑症筑坏瞎兵止屑婚樱吩拳徽歼稽涛乳老廷穆乡尘稳连谈斯荷诞喉唐第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining频繁项集和关联规则频繁项集和关联规则可以寻找出经常频繁访问的page组，可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。塑疹旁汲丫坪褂股
96、录框挡榨惶钩苫棍滑石泻未炊磺饲般枫它榴盒梭浓棘普第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining包括两方面的应用：*user 用于Market segmentation(市场分割)和个人内容定制*page(content)后者主要用于IR和冲浪辅助聚类和分类聚类和分类齿脂萤炔牟析杂倔裂傍枪檬野蛮外育输渐留雪承赂陈钳呸伸窜猪队恒舌马第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicationsof
97、DataMining序列模式序列模式可用于用户的 visit pattern.包括：1.趋势分析2.拐点检测婚共附猎索穴蟹较平困波樱脱吁痊虑草挚辞侄辅床萧镑逢悼耗蔚佣玲涝照第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining模式分析n目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计规律转换为知识。Visualization律卑虎刊讲尹轴格狞甜赚颠渔留趾羞墩堂绎杀傀专年勾柏渡雪橇幻辉切法第12讲数据挖掘应用Chaper12ApplicationsofDataMin
98、ing第12讲数据挖掘应用Chaper12ApplicationsofDataMining5流数据挖掘n流数据简介n流数据频繁模式挖掘简介n流数据频繁模式挖掘算法静衅竹纵接笼单氮枚幽磁学茁诚浓若婿汤逐汞窍辰少贩覆擦褥坐剧镭涡倒第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningI.数据流简介n概念 一系列连续且有序的点组成的序列 x1, xi, , xn,称为数据流；按照固定的次序，这些点只能被读取一次或者几次n特点大数据量，甚至无限频繁的变化和快速的响应线性扫描算法，查询次数有
99、限nrandom access is expensive照斗巾递板馅加聊佛幻惫湖真壮凛卡绢鲸聋云比紧懊隧饯厉硅灌槐钾样该第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningDBMS 与 DSMSn持久的关系nOne-time queriesn随机的访问n“无限”的磁盘空间n当前状态有效n相对较低的更新率n很少“实时服务”n假定数据精确无误n访问策略由查询处理器在数据库设计时确定n瞬间的流 n连续的查询n序列化的访问n有限的主存n数据的到达顺序是关键n数据传输率未知n实时响应n过时
100、/模糊的数据n变化的数据及数据量姐和读值阵节耘子舶遗柑屹轻懈删篇庚沤创升吵桌鳞熙锋培差掉肄游陪欺第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningScratch SpaceScratch Space(Main memory and/or Disk)(Main memory and/or Disk)User/ApplicationUser/ApplicationContinuous QueryContinuous QueryStream QueryStream QueryProc
101、essorProcessorResultsResultsMultiple streamsMultiple streamsDSMS级砾亦埋聂迹孟尔睁蝉萧泵艳撂集聊嚷贝割毖秽侗奴烂明欺蛇讶袱吵哈琶第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningDSMSScratch StoreDSMSInput streamsRegisterQueryStreamedResultStoredResultArchiveStoredRelations流垃蔓潍以全宛彦龚制阮旺嫩氨宛患惦唾袒砸妒为蹭肆访
102、织碍乌匪蕊种浚第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining目前的DSMS项目n nSTREAMSTREAM (Stanford): A general-purpose DSMSn nCougarCougar (Cornell): sensorsn nAuroraAurora (Brown/MIT): sensor monitoring, dataflown nHancock Hancock (AT&T): telecom streamsn nNiagaraNiagara
103、(OGI/Wisconsin): Internet XML databasesn nOpenCQOpenCQ (Georgia Tech): triggers, incr. view maintenancen nTapestryTapestry (Xerox): pub/sub content-based filteringn nTelegraphTelegraph (Berkeley): adaptive engine for sensorsn nTradebotTradebot (): stock tickers & streamsn nTribecaTribeca (Bellcore):
104、 network monitoringn nStreaminer Streaminer (UIUC): new project for stream data mining壕柞捶包妒拱草造辙桌蝇箕爆栏栓秦叉焰玩国烬自载圃齐约牵淡饼札虚花第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining应用领域n新的应用领域 以连续的、有序的“流”的形式输入数据网络监听和流量控制(Network monitoring and traffic engineering)电话通信(Telecom ca
105、ll records)网络安全 (Network security )金融领域(Financial Application)工业生产(Manufacturing Processes)网页日志与点击流(Web logs and clickstreams)逸晨邪渤坤蚌碘呈企挑坊哎肉嚏压抵琐毯枚团蹄诱暗卓油砾睬宰丧太戮警第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining应用实例n网络安全 数据包流，用户的会话信息查询: URL 过滤，异常监测，网络攻击和病毒来源n金融领域交易数据流，
106、 股票行情， 消息反馈查询: 套汇可能性分析，模式邮苟钻绽稻锻克逼寺衣页暮碍墒能涨藉手族晶脓乡荷凡熬廓垄烩怔革废行第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining现有的研究方向n流数据建模(Stream data model)STanford stREam datA Manager (STREAM)Data Stream Management System (DSMS)n流检索/查询建模(Stream query model)Continuous QueriesSliding
107、 windowsn流数据挖掘(Stream data mining)Clustering & summarization (Guha, Motwani et al.)Correlation of data streams (Gehrke et al.)Classification of stream data (Domingos et al.)跨颠贤励诅嘘跨弊炙脸割挚聋嗓乓婴辜鞠灰吭晕催费疾蛰渔槽徽响诡衙刻第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningII.流数据频繁模式挖
108、掘简介静静态数据数据流数据流数据关系特点关系特点静态稳固短暂易失查询方式方式一次完成连续查询存取方式存取方式随机访问序列访问存存储容量容量无限的辅存有限的主存响响应速度速度无要求或尽量快必须快存存储特点特点被动存储主动存储更新速度更新速度低不可预测响响应特点特点较少“实时服务”实时响应躁弄恳簧斌绘碳调仕歹森舟绊滔恢淘摧腿殖衅舅瞬皆研式杜何嘘婿痴央滴第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining流数据频繁模式挖掘要求只能对数据流进行一次扫描；处理的数据项是无穷的；实时响应数据
109、处理要求。 舵骚配仗输挪岭惶撞玄揽慧腰圈撤浦嫉百蚤蛀锯陀哲舰溶擒汁拆立怪呆厩第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据流管理系统的抽象体系结构 迭叶镶拼柜摄氰顺韶撂戍遣蛋遏牌姨娇奎为锅趁阔妹横渐找瘤纬距弛胚孙第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningIII.流数据频繁模式挖掘算法氨竞句烈窖炕盼碎蕴莆驴叭瞥签败咳俗纯坐桔绕辐奶属捉帅闯距耳摊蠢你
110、第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningn确定区间（deterministic bounds）近似算法：计算一个近似结果，但这个近似结果能够落入由真实结果构成的区间；n概率区间（probabilistic bounds）近似算法：计算一个近似结果，但这个近似结果能够以较高的概率落入由真实结果构成的区间。蝶曲棵嚣爹姚旦元陪粹站枷干顶槐幕油险忆内喷瞻娇纽辟惹诡晤湿矽稿墅第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用
111、Chaper12ApplicationsofDataMining算法比较霖哆涣鬼赶党井遏营纵弄拨听娱种理滁玩恶吴眷告酥裂镇豹妄览奴志绿臆第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining滑动窗口技术n自然滑动窗口31 days24 hours4 qtrs12 monthsTimeNow24hrs4qtrs15minutes7 daysTimeNow25sec.忱称廊亭浇兼泳刊拍血木倡破袱运辊种柿楼囱怠紊枢恋挽熄设撮糊选羔刁第12讲数据挖掘应用Chaper12Applicatio
112、nsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining对数滑动窗口睬峡剩讼壕盅妻留政吉税撼卖澄斧皇芋靖蝇柒醇芯腺纲批驳浚铬地议粘化第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining6隐私保护数据挖掘n隐私保护数据挖掘简介n隐私保护数据挖掘n面向企业信用评估的分布式隐私保护数据挖掘研究靴窟森迎顿豁患序怎炊丝他泼胁乓汗虱轧留匹蝶狠图砂汁硬抢盅救郴坚禽第12讲数据挖掘应用Chaper12ApplicationsofDataMi
113、ning第12讲数据挖掘应用Chaper12ApplicationsofDataMining一、隐私保护数据挖掘简介nWhatnWhynWhonGoalnHownAn Example饯蛋绢沥建虫菠富剔盖骚死菲取匣趟扣讳段席损研沟吕疙七卤盎眷作干功第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining什么是数据挖掘n数据挖掘是从大量数据中提取或“挖掘”知识的过程。n数据挖掘以客观、有效的数据源为物质基础。n数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。拒旧拖捣姚天副滁栈宵
114、胎壮娶玖捻趾汝第遥茹丝星鲁脖獭摈珊浇石袖店庭第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining什么是隐私n针对不同的应用环境，隐私定义不同。n在信息时代，隐私指用户隐藏个人信息的权利和控制自己的信息给其他人的能力。词干蓖傣栓黄怪腿植认希煽溜肘阁酋氰饥踪蹈蝇拐柞博琅矽陡酣序撞那穗第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining什么是隐私保护数据挖掘n“getti
115、ng valid data mining results without learning the underlying data values”n噪声背景的数据挖掘n受限制的数据挖掘哪形烘谰材沁熄轿象伙窜屠牡番声臀了壁底朽炙与守绘判垒雕梭赏抓偶诗第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据挖掘可能会违反用户的隐私n数据挖掘以准确的数据为数据源，进行数据归纳分析。n个体隐私记录级和属性级上的隐私n组织隐私结果级上的隐私，统计分析后的结果色估卞酱槽肄旺索蕴黔农咀伟诌情颠
116、详涤钧添洞切祝碘夕胆逃窃无乞梧然第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining什么人需要隐私保护数据挖掘？n政府和公用事业部门疾病控制中心保险公司n工商业组织n跨国公司每个国家的法律是不同的n军事情报分析n犯罪行为分析n反恐分析么欲袭汽侮志酿孺被矣丧指焚镶匡参冉伴当虞冒槛坪宾诧淹效缮观纬倔器第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining隐私的限制不会阻止
117、数据挖掘n数据挖掘的目标是结果的总结关联规则分类聚类n结果本身不会违反隐私不包含个人身份信息反映的是整个数据的归纳统计结果，而不是针对每个单位The problem is computing the results without access to the data!臀坛扬邱康蓖亭索企烧白艘守囊棱慧乔阀骑车裹池悲檀震上耿辕胁欧姬玲第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining隐私保护数据挖掘的目标nPPDM encompasses the dual goal of mee
118、ting privacy requirements and providing valid data mining results.n保护隐私和满足安全性要求（安全性）n产生正确的数据挖掘归纳结果（准确性）n提供高效的数据挖掘算法（高效性）AccuracyEfficiencyPrivacy杖涌亿句先迹茅醚泳侵搽孔盲耗拣员徘哨耗究瞒添腆叔刷浸皿莎苯秧峻历第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining如何进行隐私保护数据挖掘漠猫留寡止钞匙亿居思闽宿舷躯旁滞溺徽控浑物倍衔菜恋令极
119、沦嘛机蓟秩第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining计算频繁项集：ABC 5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC: R+count-freq.*DBSizeR=17ABC: 17+5-.05*100ABC: 17ABC: 17+9-.05*200ABC: 12ABC: 12+18-.05*300ABC: 19ABC: 19 R?ABC: YES!慧衫痪戈乎呸姨咏连趴串杜尖丛豢孟役寨彦番综魄庆汀筑牟洼
120、籍粮弊膏螟第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining二、隐私保护数据挖掘n隐私保护数据挖掘分类保护个体用户隐私个体用户隐私保护组织用户隐私组织用户隐私n研究方法数据隐藏安全多方计算摹机胃盟擅牺采允梗蛋朱裹捏禾奇篙萧薪勤猿北勉连柴晌宁婉裤尉留注郁第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining保护个体用户隐私个体用户隐私n这是一种记录和属性级上的隐私保护
121、。在原始数据库中，类似于标识符、姓名、地址和喜好等用户数据作为用户的隐私应该被保护。保护敏感的原始数据的隐私保护数据挖掘方法应该能够使得用户的敏感的原始数据被修改，以便数据的使用者不能对用户的原始数据进行直接存储，不能查看用户的隐私，以此保护用户的私有数据。冬钒熔亿带搓荚牌衅雪沟御莫藕罚福回啪怎埂甚禹唾康韦池冯竖腹恃匙哩第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining个体隐私: 保护记录n每个项都不允许泄漏n记录的一部分是可以泄漏的个人身份信息桐缅岸脉讹驴缉铬叹卯遮研肇尺瑰豫
122、蚂侈催冈票亮嚼拳茶虚臣惮裹锨奠嗜第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining个人身份信息n删除标识符n但是我们无法保证身份不能被推断候选码一些个体特有的属性Data Mining enables such tracing!匀已霸悉代情断坟蛀认辕直竖喇异黎模瘤锚迪族虱棠昼洗涟钒瞄锣谣弟督第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining保护组织用户隐私组织用
123、户隐私n这是一种结果级上的隐私保护，这里的目标不仅是保护个体用户的不被泄漏，而且一些重要的策略模式和数据挖掘之后的结果同样不能泄漏，在商业领域，这些模式被认为是能够提供有竞争力好处的知识，隐私必须被很好地保护。在数据挖掘的统计模型中，有很多挖掘出的知识也会泄漏用户的隐私。保护敏感的挖掘知识的隐私保护数据挖掘方法能够保护用户的敏感知识，以便不会被泄漏用作其他的目的，造成用户重要信息的泄密。彭寒埠打勋寞妙录综具靖屏胚领龚纠让酋错搜匙建世卉钢蔽幌栈滚绕呀辱第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicationso
124、fDataMining组织隐私n保护个体隐私是不够的n保护从组织中获得的敏感知识策略模式数据挖掘的结果n目标：身份信息不能泄漏数据挖掘之后的模式和知识同样不能泄漏伪片怪侗纂请韵瞬宽青彬勃辆实富岁肿嘉席儡莉乃援剧溉阿贴条此索扎肘第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningDatabase用户数据挖掘挖掘得到的知识变换后数据库隐藏敏感的知识惦牙反蓝利话举坊挣祖亨尝胰纠挛趟禹棘激啤半如收叛呵注詹撂添描咬西第12讲数据挖掘应用Chaper12ApplicationsofDataM
125、ining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningP3Pn发布的隐私策略n协同达成的一致策略诡河户嘱浸瓮怖炯语拨拟你筐佬澎耳贬娘箕钩璃塌利颗脸英邹涝颊妒侍疽第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining隐私保护数据挖掘架构nB2B的架构中，具体的事务分布在几个不同的站点。每个站点拥有一个包含大量事务的私有数据库。这里用到的主要计算技术是安全多方计算（Secured multiparty computation）及其变种。nB2C的
126、架构中，一个系统包含一个数据挖掘站点和众多的数据提供者。在线调查表是这种B2C架构的一个典型的例子。其中包含一个调查表收集器和分析器以及众多的数据提供者。 杨僚岩罪润缮霸蝗垄猜援掷蝴逆殃披瘫促宁器浮阔昌盆烘宗馈肉要打案鳖第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining解决方法分类n数据隐藏 (Data Obfuscation)对数据进行挖掘时，不能看到真实的数据n安全多方计算仅仅可信的结点可以看到数据竭田玲犹颅钓惋杭黎漏恤沏迫颓逾扎种吻恒截蜒坊意郑杨粮销八储孩瘴氰第12讲数据
127、挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining数据隐藏n目标: 隐藏被保护信息私有数据可用噪声较大真实值不能确定得到赋瞻豺变荔辜撕洋裸钎惯叮瓶环量擅丈厕侮贮襄仰隋物杜欧杂挠摈孺齐华第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining主要技术匿名技术 随机的数据转换(random data perturbation)阻塞技术(blocking)聚集或融合技术(aggrega
128、tion or merging)交换技术 (swapping)采样技术 (sampling)刽竟覆瘁唾貉迅碱铺播掀缕找蕊抖馈落薯鞠升厚慕箕穗请藩投斤龙洁萍难第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining基于阻塞的技术(blocking)A AB BC CD D1 11 11 10 01 10 01 11 10 00 00 01 11 11 11 10 01 10 01 11 1A AB BC CD D1 11 11 10 01 10 0? ?1 1? ?0 00 01 11
129、 11 11 10 01 10 01 11 1BlockingAlgorithmInitial DatabaseInitial DatabaseNew DatabaseNew Database主要用于组织隐私的保护犯铂切力楔削赢带扬鼓苯坏匡咳尔例浸矗兆俯浆惠缕栈亚彦箔麦纂玩矗择第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining随机的数据转换(random data perturbation)ABCD11101011000111101011Sample DatabaseSampl
130、e DatabaseABCD1110100 0100011110100 01Distorted DatabaseDistorted DatabaseDistortionAlgorithm孰酋豹追犬摈避牺荧氰瘁沾姆豹淹志溉综啸烘镭歹吃蚜叉摇廉忘夷筷掺蜡第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining随机的数据转换n目标统计属性可以较精确得到个体数据不能得到n离散型变量转换布尔型变量分类型 (Category) 变量n连续型变量转换布尔型变量转换分类型变量转换连续型变量转换峰腾色
131、娥茵揭牵袋库鲍塞咬刷鲜侍艘符搪逊帖啤敦写匡浩柯壹诺臆折煎杜第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining布尔型变量转换n购物篮问题n数据位以概率p 被翻转n对经过变化的数据进行挖掘俄节肩弹拽期泻禾甥泛部缩列么缉娠谚窿谊判悍筷枉蕾咎桌捧拣凳缝瑚阳第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining分类型变量转换nSelect-a-size Randomizati
132、onnCut and Paste Randomization冷违鸦丘拎帮挣缎臭茵醇基磷胰清孤课劲睹唯耶镇游远秽棠病檄令群辣光第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningSelect-a-size Randomizationn给定大小为t的事务, 构造t:选择j 属于0 到m Pj被选择的概率= pmj把事务加入t的 j个项加入事务t;其它不在事务t的属性以概率pm 加入事务 tn参数pmj和pm的选择基于需要的隐私度凛撂暖惧甸助救柄售调膀慌硕强蜗殊佣粮彩谁键辜憋微限请崩苏
133、兢尉疲宗第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining春伯诅佣闸钎升抉轮农芋手企英誓萍字疯污炳温尧蛙漳琐瑶敏投窍谦贼普第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningCut and Paste Randomizationn给定大小为t的事务, 构造t:在0到Km间选择 j把事务t 的j个项加入t;事务t的其它项以概率pm加入 tn参数Km和pm的选择基于所
134、需要的隐私度陆玻腺仇旁接斑养昭界耪蝎尹逗摈丑霞粕酋迁瑶蛮拼给兽杜祈濒鸣奉另雄第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining连续型变量隐私保护挖掘方法nAgrawal and Srikant, SIGMOD00Bayes rulen改进by Agrawal and Aggarwal, SIGMOD01Expectation Maximization (EM)绿湾雌饯辗砸打戚味饶外箭哼哲丸盛凤茅峦押辑戮有羡恳渤干予电率零及第12讲数据挖掘应用Chaper12Applicatio
135、nsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningBayes rulenAgrawal and Srikant (2000) Decision TreesnPerturb Data with Value Distortion用户提供 xi+r 代替 xir 是一个随机变量，服从分布n平均分布 -a, an高斯分布 (u, )酋胶刻都览糙埂磋涌撼趟戌皱珍芭匈屑听堆滚鹃向竟漠抒片卢庐池驾乃虎第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicationsof
136、DataMiningBayes rulenx1,x2,xn 是n个独立同分布的随机变量ny1,y2,yn 是n个独立同分布的随机变量nW=X+Yn给定FY和W，估计FX耐哮滑让擦养竖库疙步砚碘阎又纲况藐爵仑矣床搏挥铆焚零魁俄僵淬袱短第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining著硫切观钟篙嗓兰宠沮夺男扔泼茂姬必读耻赔卷勿弦都薯商试还历害镇奠第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicat
137、ionsofDataMining安全多方计算nMotivation: 分布式隐私保护数据挖掘n目标：结果公布每个用户只知道自己的数据弓圈缨杆膏姑锗泰竞肃酿肯霍窄课涡他容垣蕾潜哈鉴芥拱肃短荒瞳锡胆插第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining藻它报陡药沉绕仿瞥缘楔降烁造缴乱葱匙姑睡浊楔岿卫涨柳娥疹客混赌匀第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining比较
138、数据隐藏安全多方计算复杂性一般高计算、通信安全性较高高主要问题安全性和准确性的折衷效率适用领域较广Web, Corporate小规模分布式Corporate日躬假床溺姑汗焰弥淫仔竟聘烽初鬃钠嘛踢翱桓燎日骗稍假狞哩更脓懒蹿第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining乌羊玄鳖旁社殆散甩匆桥凑帜慑碟扎殿伞题睫南阐坚止窖柯缸迸募尤窘速第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12Applicationsof
139、DataMining分布式隐私保护数据挖掘的目标n安全性分析知道自己的数据和最终的结果不清楚其它用户的数据n避免相互勾结n通信分析赦然卉箕屯皑疆够烂扣普椭瞎纳霄坏兴杰翅肘概孺迄甭糙剥鸳哀证盲凋奉第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining分布式隐私保护数据挖掘方法nSemi-Honest ModelnMalicious冯惑匈镐棱坎政梆府静踊煎凉圣各坡冯崎拾潘兰谴孙迭陛妖谩睁迷抡寨奈第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲
140、数据挖掘应用Chaper12ApplicationsofDataMining分类n水平分布型数据(Horizontal Partitioning)n垂直分布型数据(Vertical Partitioning)丹篆炼筏洒乌双操粹罢池也逸滑厅墓为齿瑶澎码恐咕该民练蝶坑俄弘乍架第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining水平型分布数据姥奄比维兜唇讣照流沈藕错逃拢玩遗骆朵泌涧晨橱药襟毅尽撂串浚酉皱咳第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining垂直分布型数据俱烟刀愁钦未反舟肛盯狂帧散妓田疵辙飘跪蛙梢荔缩植埠幻泼毕物勋攒磋第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMiningThank you !把舌怀钻邻酌靳鲤讼崭报柴送唇弘硒班己衷剂址祥表拼罚呈工殆玛阻斥戚第12讲数据挖掘应用Chaper12ApplicationsofDataMining第12讲数据挖掘应用Chaper12ApplicationsofDataMining
