第12讲 数据挖掘应用Chapter 12 Applications of Data Mining.ppt

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

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

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

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

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

6、现关联规则需要经历如下两个步骤： 找出所有频繁项集。 由频繁项集生成满足最小信任度阈值的规则。,Let min_support = 50%, min_conf = 50%: A C (50%, 66.7%) C A (50%, 100%),For rule A C: support = support(AC) = 50% confidence = support(AC)/support(A) = 66.6%,Min. support 50% Min. confidence 50%,Apriori算法的步骤,Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 Aprior

7、i算法将发现关联规则的过程分为两个步骤： 通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集； 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。,频繁项集,为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck ，频繁k项集的集合记为Lk ，m个项目构成的k项集的集合为 ，则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。,关联规则的性质：,性质6.1 频繁项集的子集必为频繁项集。 性

8、质6.2 非频繁项集的超集一定是非频繁的。 Apriori算法运用性质6.1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。,Apriori算法,(1) L1=频繁1项集; (2) for(k=2;Lk-1;k+) do begin (3) Ck=apriori_gen(Lk-1); /新的潜在频繁项集 (4) for all transactions tD do begin (5) Ct=subset(Ck,t)

9、; /t中包含的潜在频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup (10) end; (11) Answer=,实例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,Visualization of Association Rules: Pane Graph,Visualization of Association Rules: Rule Graph,提高Apriori算法的方法,Hash-based

10、itemset counting（散列项集计数） Transaction reduction（事务压缩） Partitioning（划分） Sampling（采样）,关联规则挖掘算法,Agrawal等人提出的AIS，Apriori和AprioriTid Cumulate和Stratify，Houstsma等人提出的SETM Park等人提出的DHP Savasere等人的PARTITION Han等人提出的不生成候选集直接生成频繁模式FPGrowth 其中最有效和有影响的算法为Apriori，DHP和PARTITION，FPGrowth。,用Frequent-Pattern tree (FP-

11、tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘又完备的 避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法 采用分而治之的方法学：分解数据挖掘任务为小任务 避免生成关联规则: 只使用部分数据库!,挖掘频繁集 不用生成候选集,最小支持度 = 0.5,TID Items bought (ordered) frequent items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o f, c, a, b, m 300 b, f, h, j, o f, b 400 b, c, k, s

12、, p c, b, p 500 a, f, c, e, l, p, m, n f, c, a, m, p,步骤: 扫描数据库一次，得到频繁1-项集 把项按支持度递减排序 再一次扫描数据库，建立FP-tree,用交易数据库建立 FP-tree,完备: 不会打破交易中的任何模式 包含了频繁模式挖掘所需的全部信息 紧密 去除不相关信息不包含非频繁项 支持度降序排列: 支持度高的项在FP-tree中共享的机会也高 决不会比原数据库大（如果不计算树节点的额外开销) 例子: 对于 Connect-4 数据库,压缩率超过 100,FP-tree 结构的好处,基本思想 (分而治之) 用FP-tree地归增长频

13、繁集 方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree，重复这个步骤 直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的项集都是频繁集),用 FP-tree挖掘频繁集,为FP-tree中的每个节点生成条件模式库 用条件模式库构造对应的条件FP-tree 递归构造条件 FP-trees 同时增长其包含的频繁集 如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。,挖掘 FP-tree的主要步骤,从FP-tree的头表开始 按照每个频繁项的连接遍历 FP-tree 列出能够到达此项的所有前缀路径，得到

14、条件模式库,条件模式库 item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1,步骤1: 从 FP-tree 到条件模式库,节点裢接 任何包含ai, 的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到 前缀路径 要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度,FP-tree支持条件模式库构造的属性,对每个模式库 计算库中每个项的支持度 用模式库中的频繁项建立FP-tree,m-条件模式库: fca:

15、2, fcab:1,All frequent patterns concerning m m, fm, cm, am, fcm, fam, cam, fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,头表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3,步骤2: 建立条件 FP-tree,通过建立条件模式库得到频繁集,“am”的条件模式库: (fc:3),“cm”的条件模式: (f:3),f:3,cm-条件 FP-tree,“cam”条件模式库: (f:3),f:3,cam-条件 FP-tree,第3步:

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

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

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

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

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

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

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

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

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

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

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

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

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

29、,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2 Arbitrarily choose K object as initial cluster center,Assign each objects to most similar center,Update the cluster means,Update the cluster means,reassign,reassign,层次聚类,层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。 按自底向上层次分解，则称为凝聚的层次聚类。 按自顶向下层次分解，就称为分裂的层次聚类。,凝聚的和分裂的

30、层次聚类,凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。 分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。,凝聚的和分裂的层次聚类,层次聚类方法的优缺点,层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。 单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。通常考

31、虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。 层次聚类和其他聚类方法的有效集成可以形成多阶段聚类，能够改善聚类质量。这类方法包括BIRCH、CURE、ROCK、Chameleon等。,分类与预测,简介 决策树,简介,分类 预测,分类,分类的目的是提出一个分类函数或分类模型（即分类器），通过分类器将数据对象映射到某一个给定的类别中。 数据分类可以分为两步进行。 第一步建立模型，用于描述给定的数据集合。通过分析由属性描述的数据集合来建立反映数据集合特性的模型。这一步也称作有监督的学习，导出模型是基于训练数据集的，训练数据集是已知类标记的数据对象。 第二步使用模型对数据对

32、象进行分类。首先应该评估模型的分类准确度，如果模型准确度可以接受，就可以用它来对未知类标记的对象进行分类。,训练集与测试集,训练集：数据库中为建立模型而被分析的数据元组形成训练集。 训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:( v1, v2, ., vn; c );其中vi表示属性值,c表示类别。 测试集：用于评估分类模型的准确率。,分类的两个阶段,a.模型训练阶段训练集b.使用模型分类阶段 评估准确率（测试集） 对类标号未知的新 数据分类,分类模型的构造方法,机器学习方法： 决策树法知识表示是决策树 规则归纳知识表示是产生式规则神经网络方法： BP算

33、法,模型表示是前向反馈神经网络模型 粗糙集(rough set)知识表示是产生式规则,预测,预测的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而能够对事先未知的数据进行预测。 分类和回归是两类主要的预测问题。分类是预测离散的值，回归是预测连续值。 用预测法预测类标号为分类 用预测法预测连续值为预测,评估分类和预测方法的五条标准,预测的准确率 计算速度 鲁棒性 可伸缩性 可解释性,决策树,决策树学习简介 决策树实例 决策树学习的算法,决策树学习简介,决策树（Decision Tree）学习是以样本为基础的归纳学习方法。 决策树的表现形式是类似于流程图的树结构，在决策树的内部节点进行属

34、性值测试，并根据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。内部节点是属性或属性的集合，叶节点代表样本所属的类或类分布。 经由训练样本集产生一棵决策树后，为了对未知样本集分类，需要在决策树上测试未知样本的属性值。测试路径由根节点到某个叶节点，叶节点代表的类就是该样本所属的类。,决策树实例,关于PlayTennis的决策树如图所示：,决策树学习的算法,决策树学习的基本算法是贪心算法，采用自顶向下的递归方式构造决策树。 Hunt等人于1966年提出的概念学习系统CLS是最早的决策树算法，以后的许多决策树算法都是对CLS算法的改进或由CLS衍生而来。 Quinlan于1979年提出了著名

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

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

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

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

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

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

41、中的状态码（status code）进行检查。,清理后的Sample Log,用户对话识别,1.IP Address & Agent 2.Embedded Session ID 3.Registration(User Profile) 4.Cookie 5.Software Agent (Applet&Scrtipt) 6.Modified Browser,用户对话识别（续）,用户对话识别,页面视图识别,1-A,http:/ok.edu/link.htm,E,C.htm,1-C,A.htm,路径补全,解决由于Cache带来的问题路径不全的问题,数据挖掘,统计分析 频繁项集和关联规则 聚类分析和

42、分类 序列模式,统计分析,主要用于改进系统的性能、设计等 包括：1) 最频繁访问的页面2) 每个页面的平均访问时间3) 通过一个站点的平均时间,频繁项集和关联规则,可以寻找出经常频繁访问的page组， 可用于修改Web 站点的设计或提前缓冲页面，改进系统的性能。,包括两方面的应用： *user 用于Market segmentation(市场分割)和个人内容定制 *page(content) 后者主要用于IR和冲浪辅助,聚类和分类,序列模式,可用于用户的 visit pattern.包括： 1.趋势分析 2.拐点检测,模式分析,目的是根据实际应用，通过用户的选择和观察，把发现的规则、模式和统计

43、规律转换为知识。 Visualization,流数据挖掘,流数据简介 流数据频繁模式挖掘简介 流数据频繁模式挖掘算法,数据流简介,概念 一系列连续且有序的点组成的序列 x1, xi, , xn,称为数据流；按照固定的次序，这些点只能被读取一次或者几次 特点 大数据量，甚至无限 频繁的变化和快速的响应 线性扫描算法，查询次数有限 random access is expensive,DBMS 与 DSMS,持久的关系 One-time queries 随机的访问 “无限”的磁盘空间 当前状态有效 相对较低的更新率 很少“实时服务” 假定数据精确无误 访问策略由查询处理器在数据库设计时确定,瞬间的

44、流 连续的查询 序列化的访问 有限的主存 数据的到达顺序是关键 数据传输率未知 实时响应 过时/模糊的数据 变化的数据及数据量,Scratch Space (Main memory and/or Disk),User/Application,Stream Query Processor,Results,Multiple streams,DSMS,DSMS,Scratch Store,DSMS,Input streams,Stored Result,Archive,Stored Relations,目前的DSMS项目,STREAM (Stanford): A general-purpose DS

45、MS Cougar (Cornell): sensors Aurora (Brown/MIT): sensor monitoring, dataflow Hancock (AT&T): telecom streams Niagara (OGI/Wisconsin): Internet XML databases OpenCQ (Georgia Tech): triggers, incr. view maintenance Tapestry (Xerox): pub/sub content-based filtering Telegraph (Berkeley): adaptive engine

46、 for sensors Tradebot (): stock tickers & streams Tribeca (Bellcore): network monitoring Streaminer (UIUC): new project for stream data mining,应用领域,新的应用领域 以连续的、有序的“流”的形式输入数据 网络监听和流量控制(Network monitoring and traffic engineering) 电话通信(Telecom call records) 网络安全 (Network security ) 金融领域(Financial Appli

47、cation) 工业生产(Manufacturing Processes) 网页日志与点击流(Web logs and clickstreams),应用实例,网络安全 数据包流，用户的会话信息 查询: URL 过滤，异常监测，网络攻击和病毒来源 金融领域 交易数据流， 股票行情， 消息反馈 查询: 套汇可能性分析，模式,现有的研究方向,流数据建模(Stream data model) STanford stREam datA Manager (STREAM) Data Stream Management System (DSMS) 流检索/查询建模(Stream query model) Co

48、ntinuous Queries Sliding windows 流数据挖掘(Stream data mining) Clustering & summarization (Guha, Motwani et al.) Correlation of data streams (Gehrke et al.) Classification of stream data (Domingos et al.),流数据频繁模式挖掘简介,流数据频繁模式挖掘要求,只能对数据流进行一次扫描； 处理的数据项是无穷的； 实时响应数据处理要求。,数据流管理系统的抽象体系结构,流数据频繁模式挖掘算法,确定区间（deter

49、ministic bounds）近似算法：计算一个近似结果，但这个近似结果能够落入由真实结果构成的区间； 概率区间（probabilistic bounds）近似算法：计算一个近似结果，但这个近似结果能够以较高的概率落入由真实结果构成的区间。,算法比较,滑动窗口技术,自然滑动窗口,对数滑动窗口,隐私保护数据挖掘,隐私保护数据挖掘简介 隐私保护数据挖掘 面向企业信用评估的分布式隐私保护数据挖掘研究,一、隐私保护数据挖掘简介,What Why Who Goal How An Example,什么是数据挖掘,数据挖掘是从大量数据中提取或“挖掘”知识的过程。 数据挖掘以客观、有效的数据源为物质基础。 数据挖掘得到的知识是一种数据归纳的结果，是一种统计的知识。,