《数据仓库与数据挖掘》课件ppt_7_文本挖掘序列分析web 挖掘

第7章 文本挖掘、 序列分析、Web挖掘 目录 n7.1 文本挖掘 n7.2序列分析 n7.3 Web挖掘 文本挖掘概述 n文本挖掘的基本概念 n文本特征的表示 n文本特征的提取 文本挖掘的基本概念 n文本挖掘一词出现于1998年第十届欧洲 机器学习会议上。 nKodratoff认为文本挖掘的目的是从文本 集合中，试图在一定的理解水平上尽可能 多地提取知识。 概念 n文本挖掘是一个从大量文本数据中提取 以前未知的、有用的、可理解的、可操 作的知识的过程。 n文本数据包括：技术报告、文本集、新 闻、电子邮件、网页、用户手册等。 主要任务 （1）短语提取 提取文本集中所有相关的短语 。 （2）概念提取（聚类） 对这些短语之间的关系，建立一个该文 本集中的主要概念 。 （3）可视化显示和导航 从多个视角出发进行分析. 文本挖掘与数据挖掘 数据挖掘文本挖掘 研究对对象用数字表示的、结结构化的数 据 无结结构或者半结结构化的文本 对对象结结 构 关系数据库库自由开放的文本 目标标获获取知识识，预测预测 以后的状 态态 提取概念和知识识 方法归纳归纳 学习习、决策树树、神经经 网络络、 粗糙集、遗传遗传 算法等 提取短语语、形成概念、关联联分 析、 聚类类、分类类 成熟度从1994年开始得到广泛应应用从2000年开始得到广泛应应用 文本特征的表示 n文本特征指的是关于文本的元数据： （1）描述性特征，例如文本的名称、日期 、大小、类型等； （2）语义性特征，例如文本的作者、机构 、标题、内容等。 文本特征的表示 n矢量空间模型（VSM）是效果较好的表示文本 特征的方法。每个文本d表示为其中的一个规范 化特征矢量： V(d)=(t1，w1(d)；ti，wi(d)；tn，wn(d) d中出现的所有单词作为ti，或所有短语。wi(d) 一般被定义为ti在d中出现频率tfi(d)的函数。 函数wi(d)=(tfi(d) ，常用的有： （1）平方根函数 （2）对数函数 文本特征的提取 n特征提取主要是识别文本中代表 其特征的词项。 n文本特征分为一般特征和数字特征，其中 一般特征主要包括动词和名词短语，如人 名、组织名等； n数字特征主要包括日期、时间、货币以及 单纯数字信息。 特征项抽取的判断算法 （1）该特征项集合包含所有该类中出现的词。 （2）对于每个词，计算词Wi和类别Cj的互信息量 I(W,C) （3) 对于该类中所有的词，依据上面计算的互信 息量排序。 （4）抽取互信息量大的词作为特征项。 （5）根据抽取的特征项进行向量压缩，精简向量 表示。 文本挖掘 n文本挖掘功能层次 n关联分析 n文本聚类 n文本分类 文本挖掘功能层次 关键词 相似检索 词语关联分析 自然语言处理 文本聚类文本分类 文本挖掘功能层次 （1）关键词检索 关键词建立倒排文件索引，与传统的 信息检索使用的技术类似。 （2）相似检索 找到相似内容的文本。 （3）词语关联分析 聚焦在词语（包括关键词）之间的关 联信息分析上。 （4）文本聚类和文本分类 实现文本的聚类和分类。 （5）自然语言处理 揭示自然语言处理技术的语义，进 行文本语义挖掘。 关联分析 在文本数据库中，每一文本被视为一个事务，文 本中的关键词组可视为事务中的一组事务项。即文本数 据库可表示为： 文本编号， 关键词集 文本数据库中关键词关联挖掘的问题就变成事务 数据库中事务项的关联挖掘。 关联分析挖掘可以用于找出词或关键词间的 关联。 文本聚类 1层次聚类法 对于给定的文本集合D=d1，di，dn: （1）将D中的每个文本di看作是一个具有单成员的类 ci=di，这些类构成了D的一个聚类: C=c1，ci，cn； （2）计算C中每对类(ci，cj)之间的相似度sim(ci，cj)； （3）选取具有最大相似度的类对，并将ci和cj合并为一个 新的类ck=cicj，从而构成了D的一个新的聚类C=c1， ，cn-1； （4）重复上述步骤，直至C中剩下一个类为止。 该过程构造出一棵生成树，其中包含了类的层次信息，以 及所有类内和类间的相似度。 文本分类 首先，把一组预先聚类过的文本作为训练集。 然后对训练集进行分析以便得出各类的分类模式 。 对文本分类的有效方法是基于关联的分类: （1）提出关键词和词组。 （2）生成关键词和词组的概念层次，或类层 次结构。 （3）词关联挖掘方法用于发现关联词，它可 以最大化区分一类文本与另一类文本。这导致了 对每一类文本，有一组关联规则。 7.2 时间序列及其应用 n时间序列（Time Series）挖掘是数据挖掘中的一个重 要研究分支，有着广泛的应用价值 。 n近年来，时间序列挖掘在宏观的经济预测、市场营销 、客流量分析、太阳黑子数、月降水量、河流流量、 股票价格变动等众多领域得到应用。事实上，社会、 科学、经济、技术等领域中广泛存在着大量的时间序 列数据有待进一步的分析和处理。 n时间序列数据挖掘通过研究信息的时间特性，深入洞 悉事物进化的机制，是获得知识的有效途径。 时间序列有关概念 n从统计意义上来讲，所谓时间序列就是将某一指标在 不同时间上的不同数值，按照时间先后顺序排列而成 的数列。 n时间序列挖掘通过对过去历史行为的客观记录分析， 揭示其内在规律，进而完成预测未来行为等决策性工 作。 n简言之，时间序列数据挖掘就是要从大量的时间序列 数据中提取人们事先不知道的、但又是潜在有用的与 时间属性相关的信息和知识，并用于短期、中期或长 期预测，指导人们的社会、经济、军事和生活等行为 。 时间序列有关概念 n从数学意义上来讲，如果我们对某一过程中的某一变量 进行X(t)观察测量，在一系列时刻t1，t2，tn（t为自 变量，且t1对的形式。 识别用户访问事务 n在Web日志中，用户的访问事务并不是一个显然的结果，需 要专门的算法来进行识别和生成。找到相应的事务集，才能 对这个事务集进行关联规则和序列模式发现等挖掘工作。 n 时间窗C大小的界定是一个经验值（有人建议30分钟较为合 适）。 定义义7-1 设L为用户访问 日志，其中的一个项lL包括用户的IP地址l.ip，用 户的标识 符l.uid，被存取页的URI地址l.url，长度为l.length以及存取访问 的 时间 l.time，存取访问 的时长 l.timelength，访问 事务被定义为 ： 这里C是一个固定的时间 窗。 其他信息的预处理技术 1导航内容片断 在一些电子商务网站中，需要知道用户到达一个 内容页之前是经历哪些导航页的。例如，一个用户访 问事务为：N1，N2，N3，C1， N4，N5，N6，C2， N7，N8，C3，N9，N10，N11，N12，C4，其中N为 导航页，C为内容页。识别导航内容片断就是要从用 户访问事务中识别出： n片断1：N1，N2，N3，C1。 n片断2：N4，N5，N6，C2。 n片断3：N7，N8，C3。 n片断4：N9，N10，N11，N12，C4。 其他信息的预处理技术 2最大前向访问序列 所谓用户最大前向访问序列是指在用户访 问回退之前一直被访问的页面序列。每个最 大前向访问序列就构成一个访问片段。定义 该片断的优点是有利于发现用户感兴趣的事 务。显然在用户访问事务中寻找最大前向序 列必须要依据Web站点的拓扑结构。 在Web访问挖掘中的常用技 术 1路径分析 n路径分析最常用的应用是用于判定在一个Web站点 中最频繁访问的路径，这样的知识对于一个电子商务 网站或者信息安全评估是非常重要的。 2关联规则发现 n使用关联规则发现方法可以从Web访问事务集中， 找到一般性的关联知识。 3序列模式发现 n在时间戳有序的事务集中，序列模式的发现就是指找 到那些如“一些项跟随另一个项”这样的内部事务模式 。 在Web访问挖掘中的常用技 术 4分类 n发现分类规则可以给出识别一个特殊群体的 公共属性的描述。这种描述可以用于分类新 的项。 5聚类 n可以从Web Usage数据中聚集出具有相似特 性的那些客户。在Web事务日志中，聚类顾 客信息或数据项，就能够便于开发和执行未 来的市场战略。 Web访问信息挖掘的要素构 成 1数据来源 n数据的来源分为服务器，代理服务器，和客户端。 2数据类型 n数据的类型主要分为结构,内容,访问信息,用户概貌文 件。 3用户的数量 n用户的数量表现为：或者数据集只由一个用户的信息 构成，或者数据由多个用户的信息构成。 4站点的数量 n在数据集中的Web站点的个数表现为：或者在数据集 中只记录单个站点的信息，或者记录多个站点的信息 。 Web访问信息挖掘的要素构 成 5服务对象 nWeb访问信息挖掘的结果由Web服务方进行 应用。应用的结果即服务对象可以是当个单 个用户，或群体用户。单个用户即意味着个 性化。 6挖掘手段 nWeb访问信息挖掘所采用的各种数据挖掘方 法，例如关联规则发现，聚类，分类，统计 等等。 利用Web访问信息挖掘实现 用户建模 n由于Web网站的特性，对网站的经营者和设计者而言 ，无法直接了解用户的特性。然而对访问者个人特性 和群体用户特性的了解对Web网站的服务方而言显得 尤为重要。幸运的是可以通过数据挖掘的方法得到用 户的特性。 n“用户建模”（Modelling Users）是指根据访问者对一 个Web站点上Web页面的的访问情况，可以模型化用 户的自身特性。在识别出用户的特性后就可以开展针 对性的服务。用户建模主要有三种途径。 n推断匿名访问者的人口统计特性 n在不打扰用户的情况下，得到用户概貌文件 n根据用户的访问模式来聚类用户 利用Web访问信息挖掘发现 导航模式 n发现导航模式（Discovering Navigation Patterns）是Web访问信息挖掘的一个重要的研究 领域。用户的导航模式是指群体用户对Web站点内 的页面的浏览顺序模式。 n用户导航模式的主要应用在改进站点设计和个性化推 销等方面。 n1改进Web站点的结构设计 n2个性化行销（Direct Marketing）： n3利用关联规则发现算法发现导航模式 n4利用模板发现导航模式 n5利用超文本概率文法发现导航模式 利用Web访问信息挖掘改进 访问效率 1Web服务器推送技术 2自适应网站 3应用导航模式的结果改进Web站点的访问效率 4改进Web服务器的性能 利用Web访问信息挖掘改进访问效 率 表7-10改进Web站点访问效率方法的比较 方法特点 优点缺点 Web服务器推 送技术 Bin Lan相关的文档会被服务器 提前推送到Proxy上 。 存在冗余推送问 题。 自适应网站Perkowitz M.通过增加索引页来帮助 用户进 行访问 ，以 改进访问 效率。 这些索引页难 于 被用户理解 。 应用导航模式 的结果改 进改进 Web站点的 访问 效率 Myra Spiliopoulou 基于规则 的动态 Web 站点。 规则 需要人工判 定。 改进Web服务 器的性能 Cohen E. Almeida Schechter 通过对页 面的特性的 挖掘，改进服务器 的效率。 改进集中于页面 这一级，不涉及 更高级的逻辑结 构改进。 利用Web访问信息挖掘进行个 性化服务 在Web站点开展个性化（Personalization）服务的总的思路和 步骤是： n模型化页面和用户； n分类页面和用户； n在页面和对象之间进行匹配； n判断当前访问的类别以进行推荐。 而且，个性化系统一般分为两个部分：离线部分和在线部分 。 利用Web访问信息挖掘进行个 性化服务 表7-11个性化方法的比较 方法特点缺点 离线聚类和动态链 接 结合 可以实时 个性化地为用户提供 推荐。 随着用户访问长 度的增加，可 供推荐的元素会趋于零。 基于关键词 学习引入时间 特性为用户提供推荐 。 需要用户人工干预，无法做到 自动。 识别 感兴趣的链接建立代理服务器识别 用户的 访问兴 趣提供推荐。 用户兴 趣的实效性考虑不够。 自动定制不同用户访问 界面 利用用户建模技术自动定制不 同的用户访问 界面。 “推论”依赖于用户所在的领域 ，适应性不好。 利用客户端代理进行个 性化 客户端的代理，完全为个人服 务。 冗余搜索过大。 聚类推荐可以实时 个性化地为用户提供 推荐。 聚类的个数是人为事先给定的 ，不能随着每个用户的访问 特 性而动态调 整。 利用Web访问信息挖掘进行商 业智能发现 n 表7-12 商业智能方法的比较 方法特点 Buchner其贡献在于首次在Web访问 信息挖掘的基础上提出了 商业智能的发现 的框架；其不足在于发现 的知识局 限于用户确实发 生的购买 行为，而对用户潜在的购 买兴 趣无法发现 。 Yun C.优点是挖掘了迁移和购买 行为之间的内在关系。缺 点是发现 的知识局限于用户确实发 生的购买 行为， 对用户潜在购买兴 趣无法发现 。 SurfAid，Accrue， NetGenesis，Aria， Hitlist，WebTrends 优点是通过分析页面的点击率来为推断商业智能提 供Web流量分析。缺点是无法发现 高级的商业职 能。 利用Web访问信息挖掘进行 用户移动模式发现 n在移动计算环境中，一个新的挖掘方法，即用户的移 动模式挖掘被提出。挖掘的结果可以用于开发数据的 分配模式以改变移动系统的总的性能。首先，对移动 环境中的一些日志数据进行挖掘，可以得到频繁用户 移动模式。然后，根据挖掘结果和数据的特性设定个 人数据分配模式。 n根据不同层次的挖掘结果，有两种个人数据分配模式 ： n利用集合层次的用户移动模式（DS模式）； n利用路径层次的用户移动模式（DP模式）。 利用Web访问信息挖掘进行 用户移动模式发现 图7-2在一个移动计算系统中移动模式的例子 利用Web访问信息挖掘进行 用户移动模式发现 利用Web访问信息挖掘进行用户移动模式发现可以 分为如下三个主要步骤： n数据收集阶段：从各个服务器的日志集合中判断最大 的移动序列和移动对的出现次数。 n挖掘阶段：从第一步的结果集中的每w个最大移动序 列中判断大项移动序列。考虑到新近的移动模式，设 立w为一个回顾因子，一个可调整的窗口。 n产生模式阶段：根据第二步的得到的大项移动序列， 判断用户的移动模式。 利用协作推荐的方法实现实时 个性化推荐 基于协作筛方法的Web站点实时个性化系统的结构如图 7-3所示。 图7-3基于协作筛方法的Web站点实时个性化系 统 n整个处理过程分为两部分： n离线部分：包括数据准备、得到推荐池、建 立协作筛。 n在线部分：推荐引擎。 页面重要性的评价方法 n在设计搜索引擎等服务时，对Web页面的链接结构进 行挖掘以得出有用的知识是提高检索效率的重要手段 。Web页面的链接类似学术上的引用，因此一个重要 的页面可能会有很多页面的链接指向它。 n定义7-3 设u为一个Web页，Fu为所有u指向的页面 的集合，Bu为所有指向u的页面的集合。设Nu= |Fu|为 从u发出的链接的个数，c（L1，得到权威页面的权重； （7） yp=q Xq；/ L1 ，得到中心页面的权重； （8） A=p|p为具有最高xp值的页面； （9） H=p|p为具有最高yp值的页面； （10）END Web访问信息的一些概念 nW3C国际组织已经为Web访问信息定义了一些基本概念： n定义7-4 用户（User）：用户被定义为一个通过浏览器访 问一个或者多个Web服务器的访问者。一个用户可以通过几台PC 机或者使用多个浏览器来访问，因此识别用户是任务之一。 n定义7-5 页面文件（Page File）：一个页面文件是通过 HTTP请求发给用户的文件。页面文件有静态的和动态的，动态页 面文件由Web服务器动态生成响应用户的请求。 n定义7-6 页面视图（Page View）：一个页面视图由一个集 合的页面文件组成，页面视图通常与一个用户的行为相关（如一 次鼠标点击）。由框架（frame）、图片、和script等组成。 n定义7-7 客户端浏览器（Client Browser）：是指具有一个 独立IP地址的，用户通过其访问Web服务器的浏览器软件。客户 端包括代理服务器软件。 n定义7-8 Web服务器（Web Server）：是指运行在互联网 服务提供方主机上的WWW服务软件，目的是响应客户端发来的 HTTP请求。 Web访问信息的一些概念 n定义7-9 点击流（Click Stream）：亦称连续HTTP请 求序列。 n定义7-10 一次访问用户（One User at a Time）： 是指某一个通过一个客户端浏览器发出连续HTTP请求序列 的对一个Web服务器进行访问的访问者。如果一个真实的 用户每隔一段较长的时间对一个Web服务器发出一个连续 HTTP请求序列，那么对该Web服务器而言就有多个一次访 问用户进行了访问。 n定义7-11 用户访问会话（User Session）：是指由 一个用户发出的对Web世界的一次连续HTTP请求序列。 n定义7-12 服务器用户访问会话（Server Session）： 简称用户访问事务（User Transaction）是指一次访问用户 的对一个Web服务器的一次访问。由该一次访问用户所请 求的页面序列顺序组成。 n定义7-13 访问片断（Episode）：任何有意义的用户 访问会话或用户访问事务的子集，被称为访问片断。 Web站点的结构的对象描述 n一个Web站点的拓扑结构M ： n其中P为所有页面视图Page_View的集合： n一个页面