基于Web挖掘的个性化推荐服务研究.doc

分类号分类号 密级密级 u d c 硕硕士士学学位位论论文文 基基于于web挖挖掘掘的的个个性性化化推推荐荐服服务务研研究究 学位申请人学位申请人 ：丁丁 一一 学科专业学科专业：计算机应用技术计算机应用技术 指导教师指导教师：卢正鼎卢正鼎 教授教授 论文答辩日期论文答辩日期 2004.5.10 学位授予日期学位授予日期 答辩委员会主席答辩委员会主席 胡和平胡和平 评评阅阅人人 王天江王天江 李李玉玉华华 a thesis submitted in partial fulfillment of the requirementsfor the degree of the master of engineering the research of personalized recommendation based on web mining candidate : ding yi major : computer application technology supervisor : prof. lu zhengding huazhong university of science & technology wuhan 430074, p.r.china april, 2004 i 摘摘 要要 随着网络技术的不断发展，如何利用数据挖掘技术从大量的网络信息中挖掘出 对人们有用的资源，已经成为研究的热点问题。信息推荐技术需要解决的三个问题 是：首先，要理解用户的需求；其次，是能高效、准确地执行查询任务；最后，能 把结果很好地组织起来交给用户。目前比较成熟的信息推荐技术是采用面向网络信 息来解决以上问题的。但是，这种方式很难执行好用户个性化的检索需求，因此提 出了面向用户的个性化推荐模型。 通过对通用搜索引擎和元搜索引擎的研究，提出了个性化推荐模型，该模型分 为离线部分和在线部分。离线部分由数据预处理和特定的访问挖掘任务组成，数据 预处理将网络服务器的访问日志文件以及站点的相关文件生成用户文件和事务文件； 特定的访问挖掘是利用聚类算法来生成网页聚类。模型的在线部分主要是利用离线 部分生成的网页聚类，再根据用户的当前访问操作行为，动态地为用户推荐下一步 访问操作。在线部分主要是由：用户接口、兴趣学习器、个性化分析器、推理器、 网络数据连接管理器、个性化过滤器和网络服务器等组成。在线部分涉及到的关键 算法有：兴趣学习算法、个性化分析算法、个性化过滤算法和推理算法，此外还对 模型的一些简单的语法规则进行了定义，通过实验环境实现了一个界面简单的推荐 模型。 关键词：关键词：数据挖掘，个性化，信息检索，推荐服务，聚类分析 ii abstract with the development of network technology, how to use the data mining technologies to search on web has come to be a hot research area in the information search field. three problems need to be solved through information discovery technology on web. firstly, it must understand the users need correctly. secondly, it can execute query tasks efficiently and accurately. lastly, it is able to organize the results before showing them to user. now the popular and mature ir technologies settle these problems in a network information objected method. however, the network information oriented ir technologies cannot understand and execute users personal need. in this dissertation, we bring forward a new model for information recommendation in web, user-oriented information recommendation model. after combining advantages and disadvantages of the normal search model and the meta search model, this paper raises another new model of personal information recommendation based on web mining. the model can depart offline-model and online- model. introduces the data preprocessing of the offline-model, and then discusses the special task of accessing mining. data preprocessing is the step that brings users documents and events documents through accessing log documents of web server and some documents of sites. special task of access mining brings out web url clustering using the clustering algorithm. online-model mainly uses the web url clustering based on current accessing operation of users, recommendation the following accessing operation dynamically. online- model mainly consists of user interface, interest learner, personality analysis, case-based reasoning, internet database connecter, personality re-sorting and web server. and the key algorithm of online-model such as, interest learning algorithm, personal analysis algorithm, personal re-sorting algorithm and case-based reasoning algorithm were discussed. besides these, some simple syntax rules of the model were defined. the whole structure of the model was displayed through experiments, which verify the capability of it. key words: data mining, personalization, information search, recommendation server, clustering iii 目目 录录 摘摘 要要 i abstractii 1 绪论绪论 1.1 数据挖掘(1) 1.2 web 数据挖掘 .(2) 1.3 个性化推荐服务的现状(3) 1.4 论文研究内容及其组织(5) 2 个性化个性化 web 挖掘挖掘 2.1 web 数据挖掘 .(7) 2.2 几个重要的研究方向(11) 2.3 web 挖掘的个性化 .(13) 2.4 个性化推荐解决的问题和目标(16) 2.5 小结(17) 3 基于基于 web 挖掘的个性化推荐挖掘的个性化推荐 3.1 个性化服务中用户研究(18) 3.2 个性化推荐(20) 3.3 个性化推荐服务技术(23) 3.4 个性化推荐模型(29) 3.5 小结(32) 4 个性化推荐模型设计与实现个性化推荐模型设计与实现 4.1 推荐模型描述(33) 4.2 模型离线预处理(34) iv 4.3 离线挖掘算法(37) 4.4 模型在线推荐(38) 4.5 模型测试结果(48) 4.6 小结(50) 5 论文总结论文总结 5.1 主要工作总结(51) 5.2 进一步的研究方向(51) 致致 谢谢.(53) 参考文献参考文献.(54) 附录附录 1 攻读学位期间发表的论文目录攻读学位期间发表的论文目录(57) 1 1 绪论绪论 近年来，随着大规模的工业生产过程的自动化、商务贸易电子化及企业和政府 事务电子化的迅速普及以及科学计算的日益增长，产生了大规模的数据源。计算机 网络技术的长足进步也为数据的传输和远程交互提供了技术手段，特别是互联网的 迅速发展更是将全球的信息源纳入了一个共同的数据环境中1。日益成熟的数据库系 统和数据库管理系统都为这些海量数据的存储和管理提供了技术保证，为步入信息 时代奠定了基础，这些庞大的数据库及其中的海量数据是极其丰富的信息源。 在这些信息源中隐含了许多有潜在价值的知识，如何发现这些有用的知识是人 工智能、数据库等领域的研究焦点。但是仅仅依靠传统的数据检索机制和统计分析 方法已经远远不能满足需要了。因此，近年来出现了一门新兴的知识获取提取技术 数据挖掘。数据挖掘旨在从数据库中提取正确的、非平凡的、未知的、有潜在 应用价值的并最终可为用户理解的模式。它的出现为自动和智能地把海量的数据转 化成有用的信息和知识提供了手段1。数据挖掘涉及到诸如机器学习、模式识别、统 计学、数据库和人工智能等众多学科，是数据库理论和机器学习的交叉学科。 1.1 数据挖掘数据挖掘 数据挖掘和知识发现kdd（knowledge discovery in database）有密切的联系。 知识发现（kdd）2是指从数据库中发现有用知识的整个过程，数据挖掘是这一过 程中的一个特定步骤，知识发现包括数据选择、预处理、数据转换、数据挖掘、模 式解释和知识评价等多个步骤，是应用特定数据挖掘算法和评价解释模式的一个循 环反复过程，并要对发现的知识不断求精深化，使其易于理解；数据挖掘是知识发 现过程中的一个关键步骤。数据挖掘（data mining）是从大量的、不完全的、有噪 声的、模糊的、随机的数据中提取潜在的、不为人知的有用信息、模式和趋势。数 据挖掘的目的是提高市场决策能力；检测异常模式；在过去的经验基础上预言未来 趋势等3。这些知识和规则是隐含的、先前未知的、对决策有潜在价值的有用信息。 通过数据挖掘，有价值的知识、规则或高层次的信息就能从数据库的相关数据集合 中抽取出来，为决策提供依据，从而使数据库作为一个丰富可靠的资源，为知识归 纳服务。 2 与传统的数据库查询系统相比较，数据挖掘技术有以下不同4： （1）传统的数据库查询一般都具有严格的查询表达式，可以用 sql语句描述，而 数据挖掘则不一定具有严格的要求，常常表现出即时、随机的特点 ，查询要求也不确定。 （2）整个挖掘过程也无法仅用sql语言就能完整表达，实际上，数据挖掘常常 用一种类似sql语言来描述。 （3）传统的数据库查询一般生成严格的结果集，但数据挖掘可能并不生成严格 的结果集。挖掘过程往往基于统计规律，产生的规则并不要求对所有的数据项总是 成立，而是只要达到一定的事先给定的阈值就可以了。 （4）通常情况下，数据库查询只对数据库的原始字段进行，而数据挖掘则可能 在数据库的不同层次上发掘知识规则。 从广义上讲，数据挖掘分为三种类型：全自动、半自动和全交互式。对于全自 动技术，一旦系统被创建，无需人的任何干预，它能在后台自动进行操作；对于半 自动技术，系统或者在后台操作，或者采用全交互方式；对于全交互式技术，是一 种简单的数据挖掘，它由用户设置每次操作的参数，然后等待相应结果。 数据挖掘在解决实际问题时，经常要同时使用多种模式。一个数据挖掘系统或 仅仅一个数据挖掘查询就可能生成成千上万的模式，但是并非所有的模式都是令人 感兴趣。这里有一个重要的概念，兴趣度（interestingness） ，通常是用来衡量模式的 总体价值，它包括正确性（validity） 、新奇性（novelty） 、可用性（usefulness）和 简洁性（simplicity） 。数据挖掘工具还要求具有开放性，它的开放性体现在两个方面： 能与各种数据源集成；分析的结果是通用的或易于转化的。数据挖掘工具相互差别 很大，这不仅体现在关键技术上，还体现在运行平台、数据存取和价格等方面。从 运行平台来看，简单的工具可运行在 pc 的 dos 或 windows 上，复杂的工具要求运 行在 unix 工作站或并行处理平台上；从数据存取来看，简单工具处理的数据以文件 形式输入，复杂工具要求大型的数据库环境。 目前，数据挖掘已成为计算机科学研究中的一个十分活跃的前沿领域，并在市 场分析、金融投资、欺诈甑别、医疗卫生、环境保护、产品制造和科学研究等许多 领域获得了广泛的应用，取得了十分可观的社会效益和经济效益。同时，知识发现 和数据挖掘的研究和应用，对于人工智能这门前沿学科的发展注入了新的活力，有 力地促进了计算机科学朝着纵深方向顺利发展。 3 1.2 web 数据挖掘数据挖掘 internet提供了一个海量的信息源泉，它涉及新闻、广告、消费信息、金融管理、 教育、政府、电子商务和许多其它信息服务。web还包含了丰富和动态的超链接信 息，以及web页面的访问和使用信息，这为数据挖掘提供了丰富的资源。人们希望 有一个工具能够自动从internet上提取知识。传统的数据挖掘基于关系数据库或数据 仓库，所处理数据具有完整的结构。但是internet上的数据却是无序的、非结构的， 并且存在着大量的冗余与噪声。 对有效的数据仓库和数据挖掘而言，web似乎太大了。web的数据量目前以几百 兆字节计算，而且仍然在迅速地增长。web数据具有以下的一些特征： （1）数据源具有很强的动态性，internet本身就是一个时刻在动态更新和变化的 系统，这就需要借鉴数据仓库的某些技术，以此保存web上动态更新的数据。 （2）数据的多样性，web数据经过过滤后，既有数值型(整型、实型)、布尔型， 又有分类数据、性质描述数据以及web特有的数据类型(如url地址、e-mail地址等)。 新的数据类型必然带来新的特色，需要对原有挖掘方法进行改进和扩充。 （3）用户目标的模糊性，基于internet的数据挖掘用户往往只对要挖掘的主题有 一个粗浅的认识，提不出很明确的目标来。这就需要数据挖掘系统具有一定的智能 性和学习机制，不断地跟踪用户的兴趣，清晰明白地阐述挖掘结果。 web上的信息只有很小的一部分是相关的或有用的。据统计，99%的web信息对 于99%的用户是无用的，这些无用的信息会淹没用户所希望得到的推荐结果。基于以 上的分析可知，web对有效的资源和知识发现具有极大的挑战性。这些挑战推动了 如何高效且实际地发现和利用因特网上资源的研究工作。 目前有许多基于索引的web推荐引擎，利用推荐引擎，有经验的用户可以快速 定位到所需的文档。但是目前基于查询串的推荐引擎存在一些问题。首先，推荐引 擎返回的文档数过于庞大，其中很多与话题相关性并不大；其次，很多与话题相关 的文档可能并不包含相应的查询串。因此，对web资源查找还不够充分的web推荐引 擎不能等同于web 挖掘。 1.3 个性化推荐服务的现状个性化推荐服务的现状 随着信息科技的进步和互联网的日益普及，如何在浩瀚如海的信息空间里，快 4 速查找并获取所需的信息已成为信息时代最根本的问题之一。网络个性化推荐在网 络信息资源查找中起到了重要的作用，它可以帮助人们从数以亿计的网络信息中找 到自己想要的信息。 信息检索技术经历了三个发展阶段：顺序检索、顺序与倒排检索相结合、全文 检索。全文检索早期的发展，一是源于手工标引已不适应信息增长的需要，二是人 们采用自然语言直接进行检索的原理5,6。 据研究者统计，目前互联网上的搜索引擎已达数千种，仅中文搜索引擎就达70 余种。在庞大的搜索引擎家族中，有囊括各学科、各种主题网络信息的综合性搜索 引擎，有以特定学科或专业领域的网络信息为收录对象的专业性搜索引擎，还有专 门列举搜索引擎的搜索引擎指南。搜索引擎作为一个整体，存在着质量参差不齐、 信息的分类加工欠规范、搜索速度慢、死链接过多，以及提供的检索结果中重复信 息及不相关的无效信息过多等弊端，对检索效果形成负面影响。网络信息的急剧增 加，令以覆盖所有学科、所有类型信息为宗旨的综合性搜索引擎亦越来越难以应对， 就是号称功能最为强大的搜索引擎，在网络信息搜索与加工软件的升级开发上，亦 无法跟上网络信息的增长速度。 搜索引擎在网络信息的组织、加工等环节上缺乏可供操作的、统一的技术标准， 处于各自为政的无序状态，这主要体现在网络信息的分类上。统一的网络信息分类 标准的缺位令网络用户无所适从，他们被迫接受各搜索引擎的分类体系无法兼容的 事实，每使用一种新的搜索引擎，就意味着他们必须接受该搜索引擎与其他搜索引 擎在分类体系上的差异。搜索引擎之间的检索体系存在一定的差异性，难于相互兼 容，给网络用户掌握通用的信息检索技巧与方法带来不必要的操作障碍。每一种搜 索引擎的开发者在设计该搜索引擎的核心检索技术时，都以突出自身特色而各显千 秋，故不同的搜索引擎均有着相对独立的检索方法与技巧。各个搜索引擎都有一个 特色化的检索体系等待网络用户去适应，这些检索体系在推向用户之前较少通过试 运行从网络用户中搜集反馈信息，因此在适用性上存在先天的不足。 网络搜索引擎一般由信息采集器(spider 或 crawler)、索引数据库(index 或 catalog database)以及用于检索索引库的检索软件(search engine software)三部分组成。 信息采集器主要负责访问各种站点，取回 web 主页的信息。运行 spider 时，只要提 供少量的起始网页，spider 除了会将网页上的信息读回以外，还将沿着网页上的超 文本链接，自动访问网页链接的其它网页，直至遍历整个网站。spider 对网站的访 5 问是周期的，一般为每月一次或数次，访问次数视网页的更新频率而定。索引器负 责索引库的建立。spider 收回的信息很多，直接用于查询，其效率将非常低。索引 器的主要工作是建立一个包含关键信息的索引库以备查询。索引器的策略很大程度 上影响了搜索引擎的效率与准确性。目前，比较常用的方法是对网页的标题(title)和 评语(comment)进行索引。检索软件负责提供用户使用搜索引擎的接口。检索软件通 常是一个 web 应用程序，其主要工作包括：接收、解释用户的搜索请求；查询索引 库；计算网页与搜索请求的关联度；提供排序后的搜索结果返回。简而言之，信息 采集软件是从一个已知的文档集中读取信息，并检查这些文档的链接指针，指出新 的信息空间，然后取出这些新空间中的文档，将它们加入到索引数据库，检索软件 通过索引数据库为用户的查询请求提供服务，但现有的搜索引擎在信息维护、信息 重复、网络及站点负载方面还存在很大的不足，索引数据库往往很大，检索的查准 率不高。 1.4 论文研究论文研究内容及其组织内容及其组织 1.4.1 课题提出的现实意义与目标课题提出的现实意义与目标 随着经济的不断发展，我国经济的开放度不断提高，因而遭受各种外部冲击的 可能性和受影响的程度也将日益增大，各种国际规则和惯例对我国经济运行的制度 约束越来越强烈，这些制度约束将产生强制性的制度变迁效应，加快我国外汇管理 制度和模式变革的进程，在转化过程中，如何维护和提高管理效率，尽可能地减少 制度变迁成本，将成为外汇局所面临的一大挑战。为此，迫切需要建立一个功能强 大、数据完整的信息管理系统去统驭其他业务管理系统的运行。 本课题来源于与国家外汇局合作的国家外汇信息管理决策系统的项目，简称 safemidss，是根据我国外汇管理的需要，按照外汇局“说得清，管得住，服务 好”的指导思想建立的集业务管理与辅助决策于一身的综合信息服务平台。它将是 外汇局完成真实性审核、统计预警和政研立法三大职能的支撑系统，也将成为我国 外汇管理电子化的核心平台。它将以采集基础数据取代报表数据；以电子数据的直 接提取或交换取代业务数据的二次录入与加工传递；以接近实时取代定期、不定期； 以系统灵活的、即插即用的应用程序取代独立、固定的应用程序；借助报表生成工 具以灵活组合、自定义方式的查询方法取代固定的查询、报表生成程序；以系统的 指标体系、科学的分析方法、灵敏的决策机制取代静态的、孤立的、缺乏全面信息 6 支持的决策方式。这一课题属国家十五攻关课题（2001ba102a06-11） ，并由本课题 组承担，一期工程于 2003 年 12 月通过国家验收。 本课题的目标是以建立国家外汇管理局决策支持系统为实践背景，利用数据挖 掘理论技术，改进并实现基于 web 挖掘的个性化推荐服务技术，从而对国家外汇管 理局网站的 web 信息文件进行挖掘，得出用户的访问模式，从而可以进一步分析和 研究日志记录的规律，来改进国家外汇管理局网站的组织结构及其性能，改造自适 应网站；还可以通过统计和关联分析，了解使用用户的爱好，增加个性化推荐服务， 使用户足不出户就可以了解和关注到自己感兴趣的信息和资源，更好的为用户服务； 也可以是外部数据采集员用来在 internet 上面采集相关数据、资料的工具。 1.4.2 论文组织论文组织 论文比较系统完整的分析和论述了数据挖掘技术的热点难点、web 挖掘的体系 结构、个性化服务的定义、基于 web 挖掘的个性化推荐服务。各章节内容安排如下： 第 1 章 绪论：简要介绍了本文要描述的数据挖掘的基本概况和 web 挖掘的基本 定义，本文的课题背景、目的和意义，以及论文的主要工作。 第 2 章 个性化 web 挖掘：简要介绍了 web 挖掘的定义、分类、过程、任务， 还介绍了个性化服务的定义，个性化推荐解决的主要问题以及 web 挖掘的个性化， 最后还介绍了目前比较流行和重要的几个研究方向。 第 3 章 基于 web 挖掘的个性化推荐模式：首先对个性化服务中的用户服务研究 做出了描述，接着介绍了个性化推荐模型的工作机理、分类以及目前个性化推荐存 在的问题；然后对个性化推荐服务的具体技术问题、实现方法进行了介绍，最后对 目前比较流行的通用模型和元搜索引擎进行了分析。 第 4 章 个性化推荐模型设计与实现：首先对模型进行了具体描述，然后就个性 化推荐模型的离线部分预处理、离线算法和在线部分的定义、数据流程、算法的分 析以及具体实现技术进行了具体的阐述。模型的在线部分主要是利用离线部分生成 的网页聚类，再根据用户的当前访问操作行为，动态地为用户推荐下一步访问操作。 通过实验环境实现了一个界面简单的推荐模型。 第 5 章 论文总结：总结了本论文的特色和创新，以及提出了今后工作的发展方 向。 7 2 个性化个性化 web 挖掘挖掘 本章将从 web 挖掘的定义开始，介绍了 web 挖掘的分类、web 挖掘的过程、 web 挖掘技术以及 web 信息检索，还介绍了几个最重要的挖掘技术，最后将介绍一 下 web 挖掘的个性化。 2.1 web 数据挖掘数据挖掘 数据挖掘是一个逐渐演变的过程，电子数据处理的初期，人们就试图通过某些方 法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习的过程就是将 一些已知的并已被成功解决的问题作为范例输入计算机，机器通过学习这些范例总结 并生成相应的规则，这些规则具有通用性，使用它们可以解决某一类的问题。随后， 随着神经网络技术的形成和发展，人们的注意力转向知识工程，知识工程不同于机器 学习那样给计算机输入范例，让它生成规则，而是直接给计算机输入已被代码化的规 则，而计算机是通过使用这些规则来解决某些问题6,7。 web挖掘从数据挖掘发展而来，是数据挖掘技术应用于web信息的一个崭新领域。 web是一个巨大的、广泛分布的、高度异构的、半结构化的、相互联系并且不断进 化的信息仓库；是一个巨大的文档累积的集合，包括超链接信息，访问及使用信息。 大量的非结构化数据无法使用现有的数据库管理系统来操纵和管理，其用户群体也 表现出多样性的特点，这些都对信息系统的研究人员提出新的挑战7。因为web信息 的特殊性，它与传统的数据挖掘相比又有新的特质。首先，web挖掘的对象是大量 异质分布的web文档，每个数据源都是异构的；其次，web文档本身是半结构化或无 结构的且缺乏机器可理解的语义。所谓半结构化，是指web上的数据具有一定的结 构性，但是它没有特定的模型描述，每一站点的数据都有各自独立设计，并且数据 本身具有自述性和动态可变性，是一种非完全结构化的数据。而传统的数据挖掘的 对象局限于数据库中的结构化数据并利用关系表格等存储结构来发现知识，因此有 些数据挖掘技术并不适用于web挖掘，即使可用也需要建立在对web文档进行预处理 的基础之上2。 8 2.1.1 web 挖掘的分类挖掘的分类 通过数据挖掘，个人、企业、网站从internet提供的信息资源中，根据各自不同 的目的和特点，抽取有关数据并且从中发现数据中隐含的规则和知识，从而更进一 步地获取数据。internet数据挖掘总的来讲，有3个目标：精确度，即返回数据符合用 户需求的程度；覆盖率，即有多少符合用户需求的数据被返回；效率，即响应速度。 现今最流行的web数据挖掘的分类，是根据挖掘的对象将其分为：基于内容的挖掘 和基于用户使用记录的挖掘。 （1）web内容挖掘：web内容挖掘是从web文档内容及其描述中获取有用知识， 是对网页上真正的数据进行挖掘，包括网页内容挖掘和推荐结果挖掘。web文档通 常包含以下几种数据类型：文本、图像、音频、视频、元数据和超链接，也有些如 html文档所含的半结构化数据，但大多还是无结构的文本数据。文本、超文本内容 的挖掘是web内容挖掘的重点，但作为内容挖掘一份子的多媒体数据挖掘近年来受 到许多研究人员的关注，对于统一表示模型、问题解决及从多媒体数据中学习这些 问题的研究非常迫切，也将是巨大的挑战7。随着www上的信息的迅猛增长，许多 只支持由关键词和超链接所构成推荐引擎返回的结果中有许多无用及无关的信息， 因此，要推荐某一给定话题的web页面，不仅希望得到与之相关的页面，还希望所 检索的页面具有高质量，即针对该话题具有权威性。web页面中的超链接包含了人 类潜在的注释，权威性就隐藏在web页面链接中。当一个web页面的作者建立指向另 一个页面的指针时，这可以看作是作者对另一页面的认可。把一个页面的来自不同 作者的注解搜集起来，就可以用来反映该页面的重要性。因此，大量的web链接信 息提供了丰富的关于web内容相关性、质量和结构方面的信息，这对web挖掘是可以 利用的一个重要资源。 （2）web使用记录的挖掘：web使用记录的挖掘的目的是预测用户在网上的行 为，比较网站的实际使用与期望的差别，根据用户的兴趣调整网站结构7。web使用 记录的挖掘是从用户存取模式中获取有价值的信息，是对web上第二类数据即web日 志数据及相关数据的挖掘8，如图2.1所示。 这些数据包括：客户端数据、服务器端数据和代理端数据。web使用记录挖掘 可分为一般存取路径追踪和专业化追踪。前者是用kdd技术理解一般访问模式和趋 势，如web日志挖掘；后者是分析某一时刻每一个用户的访问模式，网站根据这些 模式自动重建结构，如自适应站点。web服务器通常保存了对web页面的每一次访问 9 的web日志项，或叫web log项。它包括了所请求的url 、发出请求的ip地址和时间 戳。基于web的电子商务服务器中保存了大量的web访问日志记录，热点的web站点 每天可以记录下数以百兆字节的web log记录。web log数据库提供了有关web日志记 录，来发现用户访问web页面的模式。通过分析和探究web日志记录中的规律，可以 识别电子商务的潜在客户，增强对最终用户的因特网信息服务的质量，并改进web 服务器系统的性能，甚至建立针对个体用户的定制web服务。 站点文件 用户会话文件感兴趣的规则模式规则汇总 预处理 挖掘算法 模式分析 原始日志 图2.1 web日志挖掘过程 2.1.2 web 挖掘的步骤挖掘的步骤 目前，根据数据挖掘的通用方法，结合web数据的特点，可以将web数据挖掘划 分为以下5个步骤2，如图2.2所示： 网站结构、内容 目标数据经过预处理的数据知识表述 模式、规则、 统计结果 预处理数据挖掘 模式分析 图2.2 web挖掘的步骤 （1）数据的取样：web环境目前能提供的数据源包括web页面数据，超链接数 据和记录用户访问情况的log数据等。按照主题相关的原则，数据取样从大量数据中 取出一个与探索目标相关的数据子集，为后面的数据挖掘提供素材和资源。 10 （2）数据的预处理：数据的预处理是对数据源进行加工处理和组织重构，构建 相关主题的数据仓库，为下一步的数据挖掘过程提供基础平台，做好前期准备。它 主要包括：数据清理，数据集成，数据转换和数据简约。 （3）数据的挖掘：这是数据挖掘系统的核心部分。它的主要功能是运用各种数 据挖掘技术，从经过预处理的数据中提取出潜在的、有效的且能被人理解的知识模 式。数据挖掘的目标是描述和预测，描述型模式是对数据中存在的规则作一种描述， 或者根据数据的相似性把数据分组；而预测则是指根据属性的现有数据值找出其规 律性，进而推测出其在未来可能出现的属性值。 （4）分析与评估：数据挖掘所得到的知识模式需进行可信度和有效性分析，并 对其做出评估结论，为用户的经营决策提供信息支持。如何检验得到的分析结果是 否有用，一个简单的办法是直接使用原来建立模型的样板数据进行检验；另一种办 法是另外找一些反映客观实际的规律性数据来检验；再一种办法是在实际运行的环 境中取出新数据进行检验。 （5）知识表述：知识表述是指用适当的形式将利用数据挖掘工具从web数据中 挖掘出来的知识模式表现出来，以利于用户接受和相互交流。数据挖掘的任务是多 方面的，主要包括：总结（summarization）规则挖掘、关联（association）规则挖掘、 分类（classification）规则挖掘、聚类（clustering）规则挖掘、预测（prediction）分 析、趋势（trend）分析、偏差（deviation）分析等。 2.1.3 web 数据挖掘任务数据挖掘任务 （1）特征抽取：通过对数据源的分析 ，提取出关于该数据集的一些总体特征表达式 。 （2）关联分析：找出相互独立的不同事物之间的关联规则，经过关联分析处理， 得到结论。 （3）属性分类：利用分类器，能够把数据集中的数据项映射到某个分类。例如： 可建立一个分类模型，对银行贷款的安全或风险进行分类。 （4）聚类分析：在没有给定主题类别的情况下，通过对数据集的分析和比较， 把数据划分到不同的组中，组之间的差别尽可能小。 （5）时序预测：时序预测和关联分析相仿，是把数据之间的关联性与时间联系 起来。为得到时序预测，不仅需要知道事件是否发生，而且需要确定事件发生的时 11 间。例如：情人节前巧克力和鲜花的销量会突然上升。 在实际应用中，数据挖掘必须借助一定的工具，这些工具主要包括代理、查询 报表、统计分析、数据发现(神经网络/ 决策树模型分析) 以及olap(多维分析)和可 视化表现等4。 2.1.4 web 挖掘与挖掘与 web 推荐推荐 web 信息挖掘与 web 信息推荐在实现的技术上有很多相似之处，人们往往将 web 信息挖掘与 web 上的信息推荐等同起来，但实际上它们之间是有区别的9,10， 主要体现在： （1）web 上的信息推荐主要是通过查询串来进行推荐，而 web 信息挖掘则能 对用户给的复杂目标进行特征抽取，然后根据所提取的特征在网络中进行搜寻。 （2）所有的 web 信息挖掘基本上都要用到信息推荐技术，而并非所有的 web 信息推荐都要用到挖掘技术。 web信息推荐技术不能发现信息背后隐藏的联系和规律，而web信息挖掘的功 能之一就是找出大量看似无关的信息之间的联系和规律，供决策使用。由于web的 异构数据环境、半结构化的数据结构、开放动态的数据存取等特点，使得web上的 信息挖掘实现起来十分困难。必须对挖掘对象进行适当处理，以获得被挖掘对象的 有关特征信息。web上的信息挖掘技术可以借鉴信息推荐技术，因此如何对web文档 进行推荐、预处理而得到关于文档的特征表示，便成为web信息挖掘研究的一个重 点。当前各种信息检索工具的研制是internet/www信息检索与数据挖掘研究的重点。 网络信息检索工具的核心是其检索功能。检索功能已经从基本的布尔检索、截词检 索、邻近检索、短语检索、字段检索发展为高级的加权检索、自然语言检索、相关 信息反馈检索、模糊检索和概念检索，其中的大多数检索都与数据挖掘的算法相关。 其逼近能力的研究与实现体现了数据挖掘结果的质量，要实现多路数据的数据挖掘， 开发具有较高挖掘质量的检索工具，必须探索一些知识信息处理的方法。目前，支 撑矢量机、粗集、进化算法的研究方兴未艾，某些技术已经成功地运用到 internet/www上的数据挖掘。 12 2.2 几个重要的研究方向几个重要的研究方向 2.2.1 挖掘挖掘 web 推荐引擎所发现的资源推荐引擎所发现的资源 web推荐引擎对web资源的查找还不够充分，web上的数据大多是html格式的， 有关某个主题的信息杂乱地散布在web站点的多个目录下，这样就需要有一个强大 的推荐引擎，定位超文本的位置。现有的web推荐引擎多是基于查询串的，返回的 文档过于庞大，所包含的内容质量却不高。而且由于很多与话题相关的文档可能不 包含相应的查询串，导致结果很可能也不全面，对文档进行先扩大后缩小的方法来 推荐7。 2.2.2 权威页面的识别权威页面的识别 web不仅由页面组成，而且还包含了一个页面指向另一个页面的超链接。超链 接包含了大量人类潜在的注释，权威性就隐藏在这些超链接中。当一个web页面的 作者建立指向另一个页面的指针时，可看作是作者对另一页面的认可。把一个页面 来自不同作者的注释收集起来，就可以用来反映该页面的重要性，即用于权威的 web页面的发现。这样可以进行页面等级的划分，事实上，web链接结构存在局限性： （1）每一个超链接都代表一个认可，例如广告； （2）由于商业或竞争的考虑，很少有web页面会指向其竞争领域的权威页面， 也就是说显著权威web上通常不能直接互相认可。 权威页面很少具有特别描述之类的自描述信息，这就需要使用 hub权威方法。 一个hub是指一个或多个web页面，它提供了指向权威页面的链接集合。 hub页面 本身可能并不突出，或者说可能没有几个链接指向它们 ，但是，hub却提供了指向 就某个公共话题而言最为突出的站点链接，此类页面可以是主页上的推荐链接列表。 hub页面起到了隐含说明某话题权威页面的作用 ，好的hub是指向许多好的的权威 页面。这种hub与权威页面之间的相互作用 ，可用于权威页面的挖掘和高质量 web 结构和资源的自动发现。算法 hits（hyperlink induced top is search） ，是利用 hub的推荐算法，基于hits算法的系统有clever，google也基于同样的原理。这 些系统由于纳入web链接和文本内容信息，查询效果明显优于基于词类索引引擎产 生的结果。 13 2.2.3 web 信息过滤系统信息过滤系统 web信息过滤系统-website是一个web使用记录挖掘模型，它从站点中利用内容 和结构信息挖掘算法。预处理算法包括识别用户、服务器会话和推断缓存网页。除 了创造一个服务器会话文件，website系统进行内容和结构的预处理，把服务器会话 转换为事件。对服务器会话或事件文件可以进行序列模式分析、关联规则发现、聚 类等，其结果通过简单的知识查询机制、可视化工具或信息过滤器进行分析，形成 需要的模式。图2.3详细显示了在特定web站点上要怎样进行使用记录的挖掘。 挖掘预处理的输入包括三个服务器日志、站点文件、注册文件及远程代理日志。 预处理阶段利用这些输入形成用户会话文件 ，经过事务识别形成用于模式发现的 事务文件。模式发现利用现有的数据挖掘方法 （关联挖掘、聚类、序列模式挖掘、 统计学方法等）产生规则和模式，再经过各种模式分析工具得出最终有效知识 7。 14 站点文件 存取日志、参考日志、agent 日志、注册信息及远程代理 spider 数据清理、路径补充、会话 识别、用户识别 网站拓扑结构 用户会话文件 网页分类 事件识别 事务文件 标准统计信息包 聚类、序列模式挖 掘、关联规则挖掘 序列模式、用户聚 类、关联规则 使用记录统计 信息过滤 知识查询机制olap/可视化 图2.3 website的体系结构 2.3 web 挖掘的个性化挖掘的个性化 随着网络技术的发展及机器学习、模式识别等知识发现新技术的出现，电子商 务竞争已使得信息服务方式从传统的“一对多”发展到“一对一”的个性化用户服 务方式，即为恰当的用户在恰当的时间方便快捷的提供恰当的信息。随着电子商务 中引入个性化用户服务方式，企业需要对 web 环境下的客户资料数据进行深入的统 计与分析，找出不同用户兴趣所在，透视隐藏在这些数据之后的更重要的用户兴趣 模式信息以及关于这些数据的整体特征的描述并预测其发展趋势等。了解用户在 15 web 环境中的访问模式将不仅改善 web 站点设计，而且对企业市场决策过程具有重 要的意义。本章介绍的基于 web 挖掘的个性化推荐服务即是利用个性化技术将传统 的数据挖掘（data mining）对象同 web 访问信息结合起来，利用 web 挖掘的方法 抽取用户感兴趣的潜在有用模式与信息，然后基于这些模式和信息为用户提供“一 对一”的具备自适应性的个性化推荐服务。这些个性化推荐服务可大大缩短用户在 网络上的访问延迟，使得提供给用户的网络信息服务质量得到最大程度的提高。 web 已成为人们获取信息的一个重要途径，由于 web 信息的日益增长，人们不 得不花费大量的时间去推荐。浏览自己需要的信息，推荐引擎（search engine）是最 普遍的辅助人们检索信息的工具，比如传统的推荐引擎 altavista，yahoo 和新一代 的推荐引擎 google 等。信息检索技术由于其通用的性质，虽然满足了人们一定的 需要，但仍不能满足不同背景、不同目的和不同时期的查询请求。个性化服务技术 就是针对这个问题而提出的，它为不同用户提供不同的服务，以满足不同的需求。 个性化服务通过收集和分析用户信息来学习用户的兴趣和行为，从而实现主动推荐 的目的，如图 2.4 所示。 个性化推荐服务即是利用个性化技术将传统的数据挖掘对象同 web 访问信息结 合起来，利用 web 挖掘的方法抽取用户感兴趣的潜在有用模式与信息，然后基于这 些模式和信息为用户提供“一对一”的具备自适应性的个性化推荐服务。个性化服 务技术能充分提高站点的服务质量和访问效率，从而吸引更多的访问者。 1. 识别访问用户 2. 查询用户资料 3. 选择用户感兴趣的内容 4. 查询内容、重新组织网页 4.1 推荐的超链接列表 4.2 推荐的广告列表 4.3 推荐的商品列表 4.4 经裁减的文本或图象列表 用户文件： 用户代码、密码、兴趣 内容： 文本、图片、连接等 个性化网页 图 2.4 个性化模型的基本组成 16 为实现基于 web 的个性化推荐服务，首先需要对相应主题下各用户的信息需求 内容，以及各专业信息网站的内容，进行归纳总结，以便构造出该主题范围内的信 息模型层次树（ooh） ；然后根据所获得的 ooh 内容，对该主题中各信息网站的主 要内容和组织结构进行分析，提出获取相应的信息模型层次描述内容的网页推荐知 识和网页信息抽取知识；这时开始进行信息网页推荐和网页信息抽取工作并逐步建 立起一个基于信息层次模型的完整信息库；之后就可以根据各用户具体信息需求描 述，从信息库中筛选出满足相应用户需求的信息内容并提供给用户。 综上所述，web 个性化尤其 web 个性化推荐模型是帮助人们快速获取信息的有 效手段。然而，现有模型仍然存在如下一些缺陷或不足： （1）非个性化方式适应用户兴趣变化的能力较差：现有的大部分信息检索模型 采用关键词输入方式进行检索，对任何用户都是一种模式，很容易让用户感到迷茫， 使得用户无法准确地表述自己的兴趣。尽管有些模型为此进行了改进，确实改善了 检索效率。但是，由于没有不同个性化模式之间的相互学习和信息共享机制，因而 不能很好地适应用户兴趣变化。 （2）没有综合利用个性化检索和集中浏览的各自优点：现有信息检索模型不是 注重发展大范围信息检索模型，就是注重解决特定需求信息检索问题，没有综合地 考虑这两种检索方式的优点。 （3）用户与检索模型的交互方式比较单调：现有模型普遍采用相关反馈技术作 为用户和模型进行交互的主要手段，针对不同需求的用户，提供不同的输入方式是 目前现有模型所缺少的，缺少分布式智能信息检索和适应信息源信息变化的能力。 现有模型（如 web watcher，info finder）主要通过学习用户的历史关联信息，在线 引导用户检索感兴趣的信息。这种为用户导航的方式每次只能浏览一个站点，效益 比较低，而且无法避免用户浏览以前已经浏览过而现在不需再看的文档或链接。此 外，由于没有有效地适应信息源信息变化的机制，不能及时为用户提供新的信息， 因而无法为用户快速定位感兴趣的主题。 2.3.1 个性化推荐中的数据源个性化推荐中的数据源 web 日志文件中包含 ip、时间戳、返回码、传送的字节数、方法、 url、http、引用页 url 等。由于用户访问 web 页面时先从客户端缓存中调用已 存信息，从而导致服务器端日志文件记录数据不完备，同时由于代理服务器和防火 墙的应用，用户的 id 是不可用的，这些都给日志信息的收集和预处理造成了很大的 17 困难。同时在对日志信息的收集和预处理时必须确认用户与服务器端的对话，通过 web server 提供 cookies；若无 cookies，则需要浏览器注册 i