第9章Web数据挖掘文本挖掘和图像挖掘.ppt

Web 数据挖掘,Outline,Web挖掘概述web数据挖掘分类Web数据挖掘中的关键技术Web数据挖掘的应用,Why Web Mining?,随着Internet/Web技术的快速普及和迅猛发展，使各种信息可以以非常低的成本在网络上获得，由于Internet/WWW在全球互连互通，可以从中取得的数据量难以计算，而且Internet/WWW的发展趋势继续看好，特别是电子商务的蓬勃发展为网络应用提供了强大支持，如何在WWW这个全球最大的数据集合中发现有用信息无疑将成为数据挖掘研究的热点。随着Internet的发展，Web数据挖掘有着越来越广泛的应用,Web数据挖掘是数据挖掘技术在Web信息集合上的应用。,Web挖掘概述,Web上有少量的数据信息，相对于传统的数据库的完全结构化的数据，Web上的数据最大特点就是半结构化。由于Web的开放性、动态性与异构性等固有特点，要从这些分散的、异构的、没有统一管理的海量数据中快速、准确地获取信息也成为Web挖掘所要解决的一个难点，也使得用于Web的挖掘技术不能照搬用于数据库的挖掘技术。因此，开发新的Web挖掘技术以及对Web文档进行预处理以得到关于文档的特征表示，便成为Web挖掘的重点。,典型的Web挖掘的处理流程1查找资源：任务是从目标Web文档中得到数据，值得注意的是有时信息资源不仅限于在线Web文档，还包括电子邮件、电子文档、新闻组，或者网站的日志数据甚至是通过Web形成的交易数据库中的数据。2信息选择和预处理：任务是从取得的Web资源中剔除无用信息和将信息进行必要的整理。例如从Web文档中自动去除广告连接、去除多余格式标记、自动识别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。3模式发现：自动进行模式发现。可以在同一个站点内部或在多个站点之间进行。4模式分析：验证、解释上一步骤产生的模式。可以是机器自动完成，也可以是与分析人员进行交互来完成。,Web挖掘的IR和IE过程,Web挖掘作为一个完整的技术体系，在进行挖掘之前的信息获得IR（Information Retrieval）和信息抽取IE(Information Extraction)相当重要。信息获得（IR）的目的在于找到相关Web文档，它只是把文档中的数据看成未经排序的词组的集合，而信息抽取(IE)的目的在于从文档中找到需要的数据项目，它对文档的结构合表达的含义感兴趣,它得一个重要任务就是对数据进行组织整理并适当建立索引。由于Web 数据量非常大，而且可能动态变化，用原来手工方式进行信息收集早已经力不从心，目前的研究方向是用自动化、半自动化的方法在Web上进行IR和IE。,2 web数据挖掘分类,Web 数据有三种类型,：HTML 标记的Web 文档数据、Web文档内的链接的结构数据和用户访问数据。相应地Web 数据挖掘可分为三类：内容挖掘(Web content mining)、结构挖掘(Web structure mining)和用户访问模式挖掘(Web usage mining)。,2.1 Web内容挖掘,Web内容挖掘是从文档内容或其描述中抽取有用信息的过程。Web内容挖掘的对象包括文本、图象、音频、视频等多媒体和其他各种类型的数据。其中针对无结构化文本进行的Web挖掘被归类到基于文本的知识发现领域，也称文本数据挖掘或文本挖掘，是Web挖掘中比较重要的技术领域，也引起了许多研究者的关注。在Web多媒体数据挖掘方面的研究成为另一个热点，即多模态数据挖掘。,2.1.2 实现方法和策略 Web内容挖掘按实现方法分为两大类：信息检索（IR）方法和数据库方法。且有两种策略：直接挖掘文档的内容和在其他工具搜索的基础上进行改进。1.从资源查找（Information Retrival）的观点挖掘非结构化文档：非结构化文档主要指Web上的自由文本，包括小说、新闻等。,大部分研究都是建立在词汇袋（bag of words）或称向量表示法（vector representation）的基础上，这种方法将单个的词汇看成文档集合中的属性，只从统计的角度将词汇孤立地看待，而忽略该词汇出现的位置和上下文环境。属性可以是布尔型，根据词汇是否在文档中出现而定，也可以有频度，即该词汇在文档中的出现频率。这种方法可以扩展为选择终结符、标点符号、不常用词汇的属性作为考察集合。,词汇袋方法的一个弊端是自由文本中的数据丰富，词汇量非常大，处理起来很困难，为解决这个问题人们做了相应的研究，采取了不同技术，如信息增益，交叉熵、差异比等，其目的都是为了减少属性。,一个比较有意义的方法是潜在语义索引（Latent Semantic Indexing），它通过分析不同文档中相同主题的共享词汇，找到它们共同的根，用这个公共的根代替所有词汇，以此来减少维空间。例如：“informing”、“information”、“informer”、“informed”可以用他们的根“inform”来表示，这样可以减少属性集合的规模。其他的属性表示法还有词汇在文档中的出现位置、层次关系、使用短语、使用术语、命名实体等。,2.用资源查找（Information Retrival）的观点挖掘半结构化文档与非结构化数据相比，Web上的半结构化文档挖掘指在加入了HTML、超连接等附加结构的信息上进行挖掘，其应用包括超连接文本的分类、聚类、发现文档之间的关系、提出半结构化文档中的模式和规则等。,3从数据库的观点挖掘非结构化文档：数据库技术应用于Web挖掘主要是为了解决Web信息的管理和查询问题。这些问题可以分为三类：Web信息的建模和查询；信息抽取与集成；Web站点建构和重构。从数据库的观点进行Web内容挖掘主要是试图建立Web站点的数据模型并加以集成，以支持复杂查询，而不止是简单的基于关键词的搜索。这要通过找到Web文档的模式、建立Web数据仓库或Web知识库或虚拟数据库来实现。,数据库观点主要利用OEM(Object Exchange Model)模型将半结构化数据表示成标识图。OEM中的每个对象都有对象标识（OID）和值，值可以是原子类型，如整型、字符串型、gif、html等，也可以是一个复合类型，以对象引用集合的形式表示。对于在半结构化数据上的查询语言研究也得到了人们的重视,并做了专题研究。,Web图像挖掘举例,特征提取和表示+聚类+分类,算法流程,利用BOW词袋的方法生成词典,典型的视觉词典,主题和词典,视觉词典表示的图例,参考文献,文本挖掘举例,文本挖掘概述,文本挖掘的基本概念 文本特征的表示 文本特征的提取,1 文本挖掘的基本概念,文本挖掘一词出现于1998年第十届欧洲机器学习会议上。Kodratoff认为文本挖掘的目的是从文本集合中，试图在一定的理解水平上尽可能多地提取知识。,1.概念,文本挖掘是一个从大量文本数据中提取以前未知的、有用的、可理解的、可操作的知识的过程。文本数据包括：技术报告、文本集、新闻、电子邮件、网页、用户手册等。,2.主要任务,（1）短语提取 提取文本集中所有相关的短语。（2）概念提取（聚类）对这些短语之间的关系，建立一个该文本集中的主要概念。（3）可视化显示和导航 从多个视角出发进行分析.,3.文本挖掘与数据挖掘,文本特征的表示,文本特征指的是关于文本的元数据：（1）描述性特征，例如文本的名称、日期、大小、类型等；（2）语义性特征，例如文本的作者、机构、标题、内容等。,文本特征的表示,矢量空间模型（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）对数函数,文本特征的提取,特征提取主要是识别文本中代表其特征的词项。文本特征分为一般特征和数字特征，其中一般特征主要包括动词和名词短语，如人名、组织名等；数字特征主要包括日期、时间、货币以及单纯数字信息。,特征项抽取的判断算法,（1）该特征项集合包含所有该类中出现的词。（2）对于每个词，计算词Wi和类别Cj的互信息量I(W,C)（3)对于该类中所有的词，依据上面计算的互信息量排序。（4）抽取互信息量大的词作为特征项。（5）根据抽取的特征项进行向量压缩，精简向量表示。,文本挖掘,文本挖掘功能层次 关联分析 文本聚类 文本分类,11.2.1文本挖掘功能层次,文本挖掘功能层次,（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）词关联挖掘方法用于发现关联词，它可以最大化区分一类文本与另一类文本。这导致了对每一类文本，有一组关联规则。,2.2 Web结构挖掘,Web结构挖掘的基本思想是将Web 看作一个有向图,它的顶点是Web页面,页面间的超链就是图的边。然后利用图论对Web 的拓扑结构进行分析。Web结构挖掘的对象是Web本身的超连接，即对Web文档的结构进行挖掘。,对于给定的Web文档集合，应该能够通过算法发现它们之间连接情况的有用信息，文档之间的超连接反映了文档之间的包含、引用或者从属关系，引用文档对被引用文档的说明往往更客观、更概括、更准确。Web结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之间的关系分为incoming连接和outgoing连接，运用引用分析方法找到同一网站内部以及不同网站之间的连接关系。,2.2.2 算法,常见的算法有HITS(Hypertext Induced Topic Search),PageRank,发现虚拟社区的算法、发现相似页面的算法、发现地理位置的算法和页面分类算法。Web 结构挖掘的算法一般可分为查询相关算法和查询无关算法两类。查询相关算法需要为每一个查询进行一次超链分析，从而进行一次值的指派;查询独立算法则为每个文档仅进行一次值的指派,对所有的查询都使用此值。,HITS和PageRank分别是查询相关算法和查询独立算法的代表。它们的共同点是使用一定方法计算Web页面之间超连接的质量，从而得到页面的权重。著名的Clever和Google搜索引擎就采用了该类算法。,Web访问挖掘是从服务器端记录的用户访问日志或从用户的浏览信息中抽取感兴趣的知识，即Web使用记录挖掘。在新兴的电子商务领域有重要意义，它通过挖掘相关的Web日志记录，来发现用户访问Web页面的模式，通过分析日志记录中的规律，可以识别用户的忠实度、喜好、满意度，可以发现潜在用户，增强站点的服务竞争力。,2.3 web用户访问模式挖掘,Web使用记录数据除了服务器的日志记录外还包括代理服务器日志、浏览器端日志、注册信息、用户会话信息、交易信息、Cookie中的信息、用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见Web使用记录的数据量是非常巨大的，而且数据类型也相当丰富。,2.3.2 分类 根据不同的应用需求可将web用户访问挖掘分为以下五类：个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基本信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众不同的个性化服务。,系统改进：Web服务（数据库、网络等）的性能和其他服务质量是衡量用户满意度的关键指标，Web 用法挖掘可以通过用户的拥塞记录发现站点的性能瓶颈，以提示站点管理者改进Web缓存策略、网络传输策略、流量负载平衡机制和数据的分布策略。此外，可以通过分析网络的非法入侵数据找到系统弱点，提高站点安全性，这在电子商务环境下尤为重要。,站点修改：站点的结构和内容是吸引用户的关键。Web 用法挖掘通过挖掘用户的行为记录和反馈情况为站点设计者提供改进的依据，比如页面连接情况应如何组织、那些页面应能够直接访问等。智能商务：用户怎样使用Web站点的信息无疑是电子商务销售商关心的重点，用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，Web用法挖掘可以通过分析用户点击流等Web日志信息挖掘用户行为的动机，以帮助销售商合理安排销售策略。,Web特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各个用户在页面上的交互情况，对用户访问情况进行特征描述。,2 根据对数据源的不同处理方法，Web 用法挖掘可以分为两类：一类是将Web使用记录的数据转换并传递进传统的关系表里，再使用数据挖掘算法对关系表中的数据进行常规挖掘；,另一类是将Web 使用记录的数据直接预处理再进行挖掘。Web 用法挖掘中的一个有趣的问题是在多个用户使用同一个代理服务器的环境下如何标识某个用户，如何识别属于该用户的会话和使用记录，这个问题在很大程度上影响着挖掘质量。经典的数据挖掘算法都可以直接用到Web 用法挖掘上来，但为了提高挖掘质量，研究人员在扩展算法上进行了努力，包括复合关联规则算法、改进的序列发现算法等。,2.3.3 web挖掘过程及算法Web使用记录挖掘通常需要经过三个阶段:数据预处理阶段(主要包括数据清洗和事物识别两个部分)；模式识别阶段(采用统计法、机器学习等成熟技术。从Web使用记录中挖掘知识)；模式分析阶段(采用合适的成熟的技术和工具进行模式的分析，从而辅助分析人员理解。使采用各种工具挖掘出的模式得到很好利用)。对Web使用记录挖掘采用的算法有：路径分析、关联规则和有字模式的发现、聚类分类等，为了提高精度，使用记录挖掘也用到站点结构和页面内容等信息。,3 Web数据挖掘中的关键技术,Web数据挖掘中常用的技术有Web使用的特有的路径分析技术，数据挖掘领域常用的关联规则、序列模式、分类聚类技术等。1.路径分析技术用路径分析技术进行Web数据挖掘时，最常用的是图，因为Web可以用一个有向图来表示，G=(V，E)，V是页面的集合，E是页面之间的超连接集合，页面定义为图中的顶点，而页面之间的超连接定义为图中的有向边。顶点v的入边表示对v的引用，出边表示v引用了其他的页面，这样形成网站结构图，从图中确定最频繁的访问路径。,2.关联规则挖掘技术关联规则挖掘技术主要用于从用户访问序列数据库的序列项中挖掘出相关的规则，就是要挖掘出用户在一个访问期间(SESSION)，从服务器上访问的页面文件之间的联系，这些页面之间可能并不存在直接的参引(RIFERENCE)关系。最常用的是用APRIOR算法，从事务数据库中挖掘出最大频繁访问项集，这个项集就是关联规则挖掘出来的用户访问模式。,3.序列模式挖掘技术序列模式数据挖掘就是要挖掘出交易集之间的有时间序列关系的模式它与关联挖掘技术都是从用户访问下的日志中寻找用户普遍访问的规律，关联挖掘技术更注重事务内的关系，序列模式技术则注重事务间的关系。4.聚类分类技术分类规则可以挖掘出某些共同的特性，这个特性可以用来对新添到数据库里的数据项进行分类。在Web数据挖掘中，分类技术可以根据访问这些用户而得到的个人信息或共同的访问模式，得出访问某一服务器文件的特征。聚类技术则是对符合某一访问规律特征的用户进行用户特征挖掘。最后进行模式分析，挖掘出人们可理解的知识的模式解释。,4 Web数据挖掘的应用,随着中国经济的高速发展，数据挖掘将在中国形成一个产业，目前Web数据挖掘已广泛地应用于金融业、远程通讯业、政府管理、制造业、医疗服务以及体育事业中,基于Web的数据挖掘技术已经成为一个热点,下面主要介绍Web数据挖掘的三个应用前景。,1.在电子商务中的应用在电子商务中，运用Web挖掘技术从服务器和浏览器端日志记录中自动发现隐藏在数据中的模式信息，对此进行分析加工，通过对客户进行分类和聚类，从中可得到商家用于向特定消费群体或个体进行定向营销的决策信息。了解系统的访问模式以及用户的行为模式，从而做出预测性分析。同时有效地对这些Web日志进行定量分析，提示其中的关联关系、时序关系、页面类属关系、客户类属关系和频繁访问路径、频繁访问页面等，从而为企业更有效地确认目标市场、改进决策获得更大的竞争优势提供帮助。,2.在搜索引擎中的应用利用Web数据挖掘技术，通过对网页内容的挖掘，可实现对网页的聚类和分类，实现网络信息的分类浏览与检索；运用网络内容挖掘技术改进关键词加权算法，提高网络信息的标引准确度，从而改善检索效果；通过对用户所使用的提问式的历史记录的分析，可以有效地进行提问扩展，提高用户的检索效率。,3.在网站设计中的应用在网站建设中，使用Web挖掘通过对网站内容的挖掘，可有效地组织网站信息，例如采用自动归类技术实现网站信息的层次性组织;分析用户的Web访问行为，可为用户提供智能化、个性化服务。比如,可根据客户的访问兴趣、访问频度、访问时间，动态地调整页面结构,迎合每个客户的浏览兴趣,使客户在浏览时感觉自己是网站的惟一客户;另外，网站还可以根据实际用户的浏览情况，挖掘用户的兴趣点，定期为用户推送相关信息，以及调整网站中网页的链接结构和内容，为用户提供个人的定制服务。,