（产业经济学专业论文）基于关联规则的Web使用挖掘.pdf

摘 要 摘 要 数据挖掘就是从大量的数据中提取隐含的、未知的、具有潜在价值的有用信 息。web 使用挖掘就是运用数据挖掘的思想来对 web 服务器日志进行分析处理。 web 使用挖掘在电子商务和 web 个性化等方面有着广泛的应用。通过挖掘 web 使用挖掘可以改善网站的组织结构，监控服务器的工作情况，改善 web 应用的系 统设计，为用户提供个性化服务。 数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式、 神经网络等等。关联规则是数据挖掘领域中一个非常重要的研究课题，apriori 算 法是关联规则最经典的算法。 数据预处理是数据挖掘非常关键的环节，其好坏直接影响到后续工作是否能 得到理想的结果，同时也决定了最终挖掘出的知识的可信度。web 使用挖掘数据 预处理包括四个步骤：数据清理、用户识别、会话识别、路径补全。 本文研究了 web 使用挖掘的特点、方法和相关技术，讨论了数据预处理的过 程和有效的数据预处理方法。运用 apriori 算法、clementine 数据挖掘工具对中俄 经贸合作网 web 使用日志进行挖掘，详细给出 web 使用日志数据预处理的方法、 对挖掘结果进行分析。 关键词：web 使用挖掘、关联规则、apriori 算法、数据预处理 abstract data mining is the process that people discover extract,connotative,unknown and valuable information or mode from larger database or data warehouse.web usage mining is applying web mining in analysis of web server log.web usage mining is widely applied to e-commerce and individuating web.we can improve the structures of web sites and the system design of web application,monitor the server and provide indicidual server to the users. the main algorithm of data mining included classified mode,related rule, strategic tree,array mode,clusters mode ,nerve network and so on.the related rule is a very importment research domain in the field of data mining,apriori algorithm is the most classical algorithm. data pretreatment is the most importment step in data mining,direct impact on the result of follow-up work and the credibility of the knowledge that excavated finally. data pretreatment of web usage mining consists by four steps: data cleaning, user identification, session identification, fill the path. this thesis focus on the features,method,and related techniques of web usage mining,the process and several kinds of efficient methods of data pretreatment are discussed.we use apriori algorithm, data mining tool of clementine to excavate the web usage log of sino-russian economic and trade cooperation network, descript data pretreatment methods detailly, analysis mining results. key words:web usage mining,related rule,apriori algorithm,data pretreatment 学位论文原创性声明学位论文原创性声明 本人郑重声明： 所呈交的学位论文， 是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果。对本文所涉及的研究工作做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 本人郑重声明： 所呈交的学位论文， 是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果。对本文所涉及的研究工作做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 特此声明特此声明 学位论文版权使用授权书学位论文版权使用授权书 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 学位论文作者签名：学位论文作者签名： 年年 月月 日日 导师签名：导师签名： 年年 月月 日日 1 第一章第一章 绪绪 论论 1.1 研究背景 随着计算机技术， 特别是数据库技术在各个领域的广泛应用， 尤其是 www （world wide web）作为信息传播媒介的迅速膨胀，数据经过日积月累已经泛滥 成灾。数据过量直接导致数据丰富，但信息贫乏。快速增长的数据，如果没有强 有力的分析工具，理解他们已经远远超过人的能力。如何发挥这些数据的最大作 用，从大量的数据中找出对企业决策有用的数据，已经成为用户和服务提供商们 非常关心的问题。目前大多数的数据库系统都能提供对数据的管理和简单的事务 处理，而对通过对这些数据的分析得出隐含信息的功能明显不足。因此需要对数 据进行较高层次的分析处理，找出隐含的信息，为用户提供更好的决策支持。 数据挖掘（data mining，简称 dm）技术的产生满足了人们的需要。数据挖 掘，简单的说就是从大量的数据中挖掘或抽取出知识。数据挖掘，又称为数据库 中的知识发现（knowledge discovery from database，简称 kdd） ，它是一个从大 量数据中抽取挖掘出未知的、有价值的模式或规律的复杂过程1。整个知识挖掘过 程由数据清洗、数据集成、数据转换、数据挖掘、模式评估以及知识表示组成， 数据挖掘是整个知识挖掘过程中的一个主要步骤。数据挖掘从数据中发现的模式 有多种，在实际应用中分为 6 种：分类模式、回归模式、时间序列模式、聚类模 式、关联模式和序列模式，其中关联模式的挖掘是目前数据挖掘领域中最为广泛 的研究课题之一。 www 自 1991 年诞生以来，已经成为拥有亿万用户和上百万站点的巨大分 布式信息库， 如何从 www 这个信息的汪洋大海中寻找到有用的信息成为人们面 临的一个重要挑战。数据挖掘技术在成功应用于传统的数据库和数据仓库后，人 们开始对基于 web 的数据挖掘进行研究。web 挖掘，是数据挖掘技术在 web 环 境下的应用， 是从大量的 web 文档集合和在站点内进行浏览的相关数据中发现蕴 含的、未知的、有潜在应用价值的模式的过程。相较于传统的数据库和数据仓库， 对 web 中的数据进行挖掘显的更为困难，主要表现在：传统数据库和数据仓库处 理的数据具有完整的结构，但是 www 中的数据是无序的、非结构化或半结构化 的，并且存在大量的冗余和噪声。 1 朱明，数据挖掘，中国科学技术大学出版社，2002 年 5 月，第 5 页 2 1.2 国内外研究现状 1989 年 8 月在美国底特律召开了第 11 界国际人工智能联合会议的专题讨论 会上首次提出了 kdd 这个术语。随后 1991 年、1993 年和 1994 年都举行了 kdd 的专题讨论会，集中讨论数据统计、海量数据分析算法、知识表示、知识运用等 问题。随着参与人员的不断增多，kdd 国际会议发展成为年会2。于国外相比， 国内的数据挖掘起步的比较晚， 1993 年国家自然科学基金首次支持对数据挖掘领 域的研究项目。目前，国内的许多科研单位和高校相继开展 kdd 的基础理论及 其应用研究。1999 年在北京召开了第 3 界亚太地区知识发现和数据挖掘会议，收 到论文 158 篇。2005 年 7 月 22-24 日在武汉举行了首届 adma（advanced data mining and applications） 国际学术会议。 2006 年 8 月在西安举行了第二届 amda 会议。2007 年 5 月 22-25 日在南京召开第十一届亚太地区知识发现和数据挖掘会 议。 自 1993 年 rabesh agrawal 等人提出了关联规则，并于 1994 年提出了关联规 则的经典算法 apriori 算法 ，关联规则已经成为数据挖掘领域中一个非常重要的 课题。apriori 算法需要多次重复扫描数据库，而且可能产生大量的候选项集。为 了提高算法的效率，很多研究者进行了大量的研究，他们的工作包括对原有的算 法进行优化，如引入随机采样、并行的思想、增加衡量标准、规则约减、改变存 储结构等，提出了各种变体，如泛化的关联规则、周期关联规则等，对关联规则 的应用进行推广。当前，关联规则挖掘的研究问题主要集中在：对关联规则挖掘 理论的新探索，分布环境下大型数据系统的关联规则挖掘问题，关联规则的兴趣 度问题、关联规则挖掘算法的交互性问题、关联规则挖掘技术与其他技术的融合 问题。 除 apriori 算法外，ramakrishnan srikant 等提出的挖掘定量关联规则的算法， sergey brin 等提出的 dic 算法，这些算法都是离线的或者批处理式的。christian hidber 提出了挖掘关联规则找出数据项频集的在线算法 carma， charuc.aggarwal 提出了根据数据项频集的集合找出关联规则的在线算法，在线挖掘关联规则的算 法允许用户随时调整最小支持度，如果中间结果已经令人满意，用户也可以随时 终止算法的执行。 2 王永利，哈尔滨工程大学硕士论文，2003 年 3 1.3 内容安排 本文分为七章： 第一章绪论，介绍数据挖掘和关联规则的研究背景，分析了国内外对数据挖 掘、 关联规则算法的现状及研究中存在的问题， 指出本文的研究内容和研究意义。 第二章 web 使用挖掘，给出 web 挖掘的定义，分析 web 挖掘的特点，分别 对 web 挖掘的三个类别结构挖掘、内容挖掘、使用挖掘进行归纳总结，从 web 使用挖掘的数据源、应用的领域对 web 使用挖掘进行更详细的描述。 第三章关联规则，首先介绍了关联规则的基本思想、基本概念，然后详细介 绍了关联规则最经典的 apriori 算法， 分析了 apriori 算法的性能瓶颈， 以及 apriori 算法的改进。 第四章数据预处理， 说明 web 服务器日志格式， 给出数据预处理的四个步骤： 数据清理、用户识别、会话识别、路径补全的一般做法，强调数据预处理对数据 挖掘结果的重要性。 第五章中俄经贸合作网 web 服务器日志预处理， 首先归纳了中俄经贸的网站 结构、web 服务器日志格式，按照数据清理、用户和会话识别、事务识别三个步 骤对中俄经贸网 web 服务器日志进行预处理。 第六章中俄经贸合作网 web 服务器日志挖掘，简单介绍了数据挖掘工具 clementine，运用 clementine 对处理后的数据进行挖掘并得出结果，并对挖掘结 果进行分析。 第七章总结与展望，对本文内容的总结以及以后研究工作的展望。 1.4 研究意义 国外在数据挖掘领域、web 使用挖掘领域的研究内容已经十分广泛，研究重 点已经从发现方法逐步转向系统应用。而在国内相应的理论和算法上的研究还比 较薄弱，相关的论文资料和研究成果比较少。本文对 web 使用挖掘的概念和应用 进行了详尽的阐述，关联规则，对其概念、算法、算法瓶颈、改进算法进行分析， 含有一定的数据挖掘、web 使用挖掘的理论知识，能够提供一些理论和概念上的 信息。 本文重点给出了数据预处理各个步骤的处理方法，结合了中俄经贸合作网的 web 服务器日志的预处理，把理论知识运用到实践，为数据挖掘爱好者提供数据 4 预处理的参考。 运用数据挖掘工具 clementine 对中俄经贸合作网日志进行挖掘，得出有用户 的访问模式，为中俄经贸合作网的管理者提供决策支持。 5 第二章 web 使用挖掘 2.1 web 挖掘 www 已经成为一个巨大的分布式全球信息服务中心，提供新闻、广告、消 费信息、金融管理、教育、电子商务、电子政务等各种服务。www 不仅包含大 量的文档，而且包含了丰富的动态链接信息、存取和使用信息等。如此巨大的信 息资源为数据挖掘提供广阔的应用空间和基础。 2.1.1 web挖掘定义 web 挖掘是从数据挖掘发展而来，是将数据挖掘技术应用于大规模 web 数 据，以期发现有效的、新颖的、潜在的、有用的、最终可以被理解的模式。它是 一项综合技术，涉及 web、数据挖掘、计算机语言学、信息学等多个领域。用于 传统数据挖掘的聚类、分类、关联规则、序列模式等分析技术都可以运用到 web 挖掘上来。 web 挖掘技术从一开始就是面向应用的，它不仅仅面向特定数据源的简单检 索查询调用，而且要对这些无结构的、异源的数据进行微观、中观甚至宏观的清 洗、集成、统计、分析、综合和推理，指导实际问题的求解，企图发现用户间、 页面间的相互关联，甚至利用已有的数据对用户未来的活动进行预测。web 挖掘 被信息产业界认为是“未来三到五年内将对工业产生深远影响的五大关键技术” 之首。 2.1.2 web挖掘特点 web 挖掘是一个极具挑战性的课题，是对数据挖掘的一种新的发展和应用， 但是又不同于传统的数据挖掘。其区别在于： （1）web 挖掘的对象是无结构、半结构化的数据。web 中除了文本文档外， 还有多媒体等其他形式的半结构或者无结构数据，缺乏机器可理解的语义，这给 web 挖掘带来了新的挑战。 （2）web 中的数据量太大，无法有效的构造数据仓库和进行数据挖掘。web 中的数据量是以百 tb 来就算的，而且仍然在迅猛地增加。截止到 2000 年初，web 中可公开访问到的网页数至少已有 8 亿页，而且据估计每 4 个月这一数字就会翻 6 一番。这使得几乎不可能去构造一个数据仓库来复制、存储或集成 web 上的所有 数据。 （3）web 用户群体的多样性。2000 年 8 月为止，cnnic 调查我国上网人数已 达到 1600 万，web 上至少链接了 1.1 亿台以上的电脑，而且这数字将持续增长。 web 用户具有不同的背景、兴趣和使用目的。大多数用户都不太了解信息网络的 结构，也不会意识到一次搜索的代价，常常会在信息的海洋中迷失方向，或会被 不断点击跳跃网页所累倒。 （4）web 是一个高度动态的信息源。不仅 web 用户数量在迅速增加，而且其 中的信息也在迅速增加。新闻、股票市场、公司广告等都在不断地定期更新他们 的网页内容。信息的链接和读取也在不断的更新。 （5）web 中的信息只有一小部分是真正有用的或者相关的 3。web 中有 99%的 信息对 99%的用户而言是无用的。一个用户往往只对 web 上一个非常小的部分感 兴趣，但是 web 中充斥着大量无用或不想要的东西。 基于以上几点，使得 web 挖掘有其自身的特点和复杂性，也促使有效发现和 利用 web 信息资源的相关研究工作开展。 2.1.3 web挖掘分类 www 中有三种数据：站点结构数据、页面内容数据和记录用户如何使用站点 的使用数据。因此，web 挖掘分为 web 结构挖掘（web structure mining） 、web 内容挖掘（web content mining） 、web 使用挖掘（web usage mining）4。另外， web 挖掘也可以被认为是 web 内容挖掘的一部分， 这样， web 挖掘可以简单的分 为两类，即 web 内容挖掘和 web 使用挖掘。 3朱明，数据挖掘，中国科学技术大学出版社，2002 年 5 月，第 188 页 4欧阳利军、龚成，一种基于关联规则的 web 日志数据挖掘的实现方法，现代计算机（总第二二九期） 7 图 2.1 web 挖掘分类图 资料来源：本论文整理 （1）web 结构挖掘 web 结构包括页面内部的结构、页面之间的结构。web 的文档结构、web 组织 结构及其链接关系中隐含着大量潜在的，有价值的信息，web 结构挖掘主要是从 web 组织结构和链接关系中推导出有价值的信息。例如，通过 web 页面间的链接 信息可以识别出权威页面、安全隐患（非法链接）等。 1999年chakrabarti等人提出利用挖掘web上的链接结构来识别权威页面的 思想。web 不仅由页面组成，而且也包含指向页面的链接，这些链接中包含了大 量人类潜在的信息，有助于自动推断出权威页面。一般创建一个网页的作者，在 设置网页链接时就考虑了所指网页的内容及相关性和重要。由不同作者对同一个 网页的链接考虑就表明了该网页的重要性，从而很自然的获得有关的权威网页。 然而，web 链接结构具有如下局限性:不是每个超链接都代表对我们寻找的认可， 有些链接是为其他目的而创建的，如为了导航等；基于商业或者竞争的考虑，很 少有权威页面会指向同一竞争领域的另一个权威页面，如诺基亚可能就不会指向 其对手摩托罗拉页面。权威网页很少是描述性的，如雅虎页面几乎不包含任何自 我描述。 由于 web 链接结构存在这些局限性， 人们提出了另一种重要的 web 页面， web 挖掘挖掘 web 结构挖掘web 内容挖掘web 使用挖掘 超 链 接 挖 掘 内 部 结 构 挖 掘 文 本 挖 掘 多 媒 体 挖 掘 serv er coo kie log 8 hub。hub 是指一个或多个 web 页面，它提供了指向权威页面的链接集合。hub 页 面本身可能并不突出，或者说可能没有几个链接指向它们，但是，它却提供了指 向某个公共话题而言最为突出的站点链接，起到隐含说明某话题权威页面的作用 5。利用 hub 页，运用 hits 算法找出权威页。 （2）web 内容挖掘 web 的内容主要包含文本、声音、图象、视频以及其他类型的数据，有无结 构的自由文本，也有用 html 标记的半结构的数据和来自数据库的结构化数据。 web 内容挖掘就是从 web 上的内容中抽取有价值信息的过程。根据处理的内容， web 内容挖掘可以分为两个部分：文本挖掘和多媒体挖掘。无结构化文本进行的 web 挖掘归属于基于文本的知识发现领域，又称为文本数据挖掘或者文本挖掘， 是 web 挖掘中重要的技术领域，引起许多研究者的关注。最近，随着 www 中多媒 体数据的猛增，多媒体数据挖掘研究成为另一个热点。 web 内容挖掘使用的技术有两种类型：一种是建立在统计模型的基础上，采 用的技术有决策树、分类、聚类、关联规则等。目前主要技术包括 6：文本总结， 文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解 释，其目的是对文本信息进行浓缩，给出它的紧凑描述，这样，用户不需要浏览 全文就可以了解文档或文档集合的总体内容；文本分类，分类是在已有数据的基 础上学会一个分类函数或构造出一个分类模型， 即通常所说的分类器； 文本聚类， 文本聚类把一组文档按照相似性归成若干类别，方法大致可分为层次凝聚法和平 面划分法两种类型；关联分析，发现关联规则的算法通常要经过以下三个步骤： 连接数据、作数据准备、给定最小支持度和最小可信度，利用数据挖掘工具提供 的算法发现关联规则，可视化显示、理解、评估关联规则。另一种简历一个计息 学习为主的人工智能模型，采用的方法包括神经网络、自然法则计算方法等。 多媒体文本数据的特征表示、特征抽取以及多媒体文本数据挖掘方法是多媒 体数据挖掘研究的重要内容。web 多媒体数据挖掘通常采用的方法有关联规则法 和特征提取法。对多媒体数据进行挖掘前，首先对多媒体数据进行预处理，抽取 多媒体文本的特征（描述性特征和语意性特征） ，其中关键是多媒体内容特征的 表示和抽取。获得多媒体数据特征后，通过选定的表示法将其表示成元数据 （metadata）,对元数据进行结构化处理后存于结构化的元数据库,即多媒体文本 文档特征库。 5 （加）hanj.kamberm，数据挖掘概念与技术，机械工业出版社，2001 年，第 292 页 6 龚月瑛，web 信息挖掘现状及应用前景，科技情报开发与经济第 17 卷第 20 期，2007 年 9 （3）web 使用挖掘 web 使用挖掘就是利用数据挖掘技术对网站大量的（用户访问）使用数据及 其他相关数据所组成的数据集进行分析挖掘，并从中获得有价值的有关网站访问 使用情况的模式知识 7。web 使用挖掘过程的总体描述如下： 内容和结构数据 处理后的点击流数据元数据 预处理预处理模式发现模式发现 模式分析模式分析 有兴趣的规则模式 规格模式 图 2.2 web 使用挖掘过程 资料来源：本研究整理 根据对源数据的不同处理方法，web 使用挖掘可以分成两类：一类是将 web 使用记录的数据转换并传递进传统的关系表里，再使用数据挖掘算法对关系表中 数据进行常规挖掘，即将 web 使用挖掘转换成传统意义的数据挖掘；另一类是将 web 使用记录的数据直接预处理再进行挖掘。 web 使用挖掘是一个非常年轻的研究领域，有非常多的问题有待进一步探索 研究，例如：网页类型的自动识别判断、浏览路径的补全、记录时间与真正浏览 时间的差别，以及如何有效利用 web 使用挖掘结果等等。最终无论点击数据流来 自客户、web 服务器还是内容服务器，web 使用挖掘工具可以进行分析，并帮助 网站优化，以提供个性化服务等 8。 7朱明，数据挖掘，中国科学技术大学出版社，2002 年 5 月，第 259 页 8朱明，数据挖掘，中国科学技术大学出版社，2002 年 5 月，第 290 页 10 2.2 web 使用挖掘 2.2.1 web使用挖掘数据源 web 使用挖掘所使用的数据可以来自服务器层面、代理层面和客户层面，大 多数的研究都利用了服务器端的数据。从不同数据源搜集而来的数据反应了 web 使用过程中不同的访问模式。服务器端的数据则描述了多用户/单站点的访问行 为，代理端的数据则记载了多用户/多站点的使用情况，而客户端的数据通常反 应单用户/多用户的访问行为。如图所示： 8 u内容服务器 网络服务供应服务器 网络服务器 调制解调器 客户电脑 用户 行为 网站 内容 电话 线 因特 网 客户 层日 志 代理 层日 志 服务 器层 日志 内容 层日 志 帧探 测器 日志 图 2.3 web 使用挖掘数据源 资料来源：本研究整理 具体情况说明介绍如下： （1）服务器端数据 web 服务器日志是 web 使用挖掘中一个重要的数据源，它清楚地记录了网站 用户的访问浏览行为。这些日志通常采用了普通日志格式（clf）或扩展普通日 志格式（eclf） 。帧嗅探器（sniffer）可以检测网络（向服务器方向）传输的信 息，并从 tcp/ip 帧中直接抽取出相关的使用数据。服务器端所能提供第三个数 据源就是其内容服务器（content server）日志，它可以提供有关用户所浏览的 信息内容的有关情况。除了这些数据外，服务器端还可以提供有关网站的信息， 如：内容数据、结构信息、本地数据库、网页元数据。 （2）客户端数据 客户端数据可以利用远程 agent 来帮助收集客户端（单用户/多网站）访问 浏览情况。显然，在客户端直接收集用户访问网站的浏览行为要比在服务器端间 接记录用户行为要准确得多，但是利用远程 agent 在客户端进行（用户）浏览数 11 据的收集工作需要得到用户的首肯，否则收集工作很难进行，而取得用户的首肯 将是一个艰巨的工作。 （3）代理端数据 一个 web 代理作为用户（浏览器）与 web 服务器之间的交通要道，代理端的 缓存将有助于减少网页（在客户端）的装载时间和服务器端的工作负载。代理端 可以跟踪来自多个客户访问多个服务器的请求。代理端的缓存对服务器日志记录 内容的影响取决于（所读取）网站内容的性质。若为动态生成的网页，则不受代 理端缓存的影响，但是若为静态网页，就可能会受到较大的影响。 2.2.2 web使用挖掘运用的领域 目前，web 使用挖掘已经被运用到众多领域，主要体现在： (1) 完善系统性能 web 使用挖掘的结果有助于设计出合理的 web 缓存， 网络通讯和数据分布等， 也有助于解决网络安全问题。web 使用挖掘还可以帮助进行入侵检查等网络安全 工作，为网络安全工作提供非常有价值的参考。 (2) 完善网站设计 web 使用挖掘可以提供用户访问模式，使网站设计人员能够更合理的设计网 站的内容和组织结构。 而且， 帮助网站进行有效测试不需要有经验的的人员参加， 此外，利用 web 使用挖掘的结果可以来探讨网站内容安排的自动改进问题。 (3) 个性化服务 根据网站用户访问情况，为用户提供个性化服务信息服务，这事许多互联网 应用，尤其是互联网信息服务或电子商务所追求的目标。根据 web 使用挖掘所得 到的用户访问网站模式，并结合当前用户的访问行为，向用户提供个性化服务。 (4) 商业智能 通过定义 web 使用日志的超维数据立方，将 web 使用数据与电子商务应用 数据有机地结合在一起，可以利用数据挖掘方法与技术来为客户关系管理中的重 要环节提供技术支持。利用 web 使用挖掘技术为客户关系管理提供决策支持，这 对电子商务有着深远的影响。 12 第三章 关联规则 3.1 综述 关联规则挖掘是从大量的数据中挖掘出有价值的、描述数据项之间相互联系 的有关知识。从大量的商务交易记录中发现有价值的关联知识就可以帮助进行商 品目录的设计、交叉营销和帮助进行其他有关的商业决策。 关联规则挖掘的一个典型应用实例就是购物篮分析。作为一个商场的主管， 肯定想知道商场顾客的购物习惯，除了想知道那些商品容易被顾客购买外，尤其 想知道那些商品会一起被用户顾客所购买。通过对顾客在商场购物交易记录数据 进行分析，可以帮助商场主管制定针对性的市场营销和广告宣传计划，以及编撰 合适的商品目录。比如：分析结果将帮助商家对商场内商品应该如何摆放进行规 划设计。其中，一种策略是将常常一起购买的商品摆放在向邻近的位置，以方便 顾客同时购买这两件商品。例如：如果购买电脑的顾客同时也常购买杀毒软件， 那么将电脑硬件和软件摆放在一起有助于这两种商品的销售。另一种策略是将常 常一起购买的商品摆放在商场的两端，这样就会促使顾客在需要购买两种商品的 途中要走更多的路，从而达到诱导他们购买更多商品的目的。例如：如果购买电 脑的顾客同时也常购买杀毒软件，把电脑和杀毒软件放在商场的两端，在顾客购 买外电脑要去购买杀毒软件的时候可能看到财务软件等其他应用软件，他就有可 能购买这类产品。同时，购物分析结果也可以帮助商场主管们决定那些商品可以 进行捆绑减价销售，以期达到最佳的促销效果。 关联规则挖掘有许多不同的类型，可以根据以下的类型对这些关联规则挖掘 方法进行分类： （1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、 种类化的， 它显示了这些变量之间的关系； 而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行 处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联 规则中也可以包含种类变量。例如：性别=“女”=职业=“秘书” ，是布尔型 关联规则；性别=“女”=avg（收入）=2300，涉及的收入是数值类型，所以是 一个数值型关联规则。 （2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层 13 次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如： ibm 台式机=sony 打印机，是一个细节数据上的单层关联规则；台式机=sony 打印机，是一个较高层次和细节层次之间的多层关联规则。 （3）基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多 维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则 是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：啤酒=尿布，这条规则只涉及到用户的购买的物品；性别=“女”=职业= “秘书” ，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 （4）关联规则所涉及的关联特征。关联规则可以扩展到其他数据挖掘应用 领域，如进行分类学习，或进行相关分析。 关联规则挖掘主要包含两个步骤：步骤一，发现所有的频繁项集，根据定义， 这些项集的频度至少应等于预先设置的最小支持频度；步骤二，根据所获得的频 繁项集，产生相应的强关联规则，根据定义这些规则必须满足最小信任度阀值9。 关联规则挖掘可以产生清晰有用的结果，支持间接数据挖掘，可以处理变长的数 据，计算的消耗时间也是可以预见的。但是，当问题变大时，计算量增长厉害， 难以决定正确的数据也容易忽略稀有的数据。 3.2 基本概念 设 i 为数据项集合，d 为与任务相关的数据集合，t 为一个数据项子集，即 ti，每个数据项子集都有一个识别编号 tid。a 为一个数据项集合，当且仅当 at 时，称 t 包含 a。一个关联规则就是一个具有“ab”形式的蕴含式，其 中 ai,bi,且 ab=。规则 ab 在任务相关的数据集合中成立，且具有 s 支持度和 c 信任度。 这就意味着任务相关的数据集合 d 中有 s 比例的 t 包含 ab 数据项，在任务相关的数据集合 d 中有 c 比例的 t 满足包含 a 就包含 b。具体描 述如下 10： support（ab）=p（ab） confidence（ab）=p(b|a) 顾客购买电脑的同时也会购买杀毒软件的购物模式可以用以下的关联规则 9秦亮曦、史忠值，关联规则研究综述，关系大学学报（自然科学版）第 30 卷第 4 期，2005 年 12 期 10 （加）hanj.kamberm，数据挖掘概念与技术，机械工业出版社，2001 年 14 来描述： 电脑杀毒软件support3%confidence60%=，。 规则的支持度为 3%， 这就意味着所分析的数据中有 3%的记录同时包含购买电脑和杀毒软件，规则的 信任度为 60%，这意味着购买电脑的顾客中的 60%也购买了杀毒软件。 用户可以设置最小的支持度阀值（minimun support threshold）和最小信任度 阀值（minimun confidence threshold） ，这两个阀值都在 0%到 100%之间，只有满 足最小支持度和最小信任度的关联规则才是有意义的，也即强规则（strong） 。一 个数据项的集合成为项集（itemset） ，一个包含 k 个数据项的项集称为 k 项集。满 足最小支持度阀值的 k 项集就成为频繁 k 项集,记为 lk。 3.3 apriori 算法 agrawal 首先于 1994 年提出了 apriori 算法11，引入相当广泛的讨论，之后许 多算法的提出都是根据此方法来加以改进的，可谓是最具代表性的方法之一。 apriori 算法是挖掘产生布尔关联规则所需频繁项集的基本算法， 、其核心方法是 基于频繁理论的递推方法。 3.3.1 apriori 算法描述 apriori使用逐层搜索的迭代方法，k-项集用于探索(k+l)-项集。首先，找 出频繁1-项集的集合。该集合记作l1。l1用于找频繁2-项集的集合l2，而l2用于找 l3，如此下去，直到不能找到频繁k-项集 12。找每个l k需要一次数据库扫描。 这里在第k次循环中，过程先产生候选k-项集的集合ck,ck中的每一个项集是 对两个只有一个项不同的属于lk-1的频集做连接来产生的。ck中的项集是用来产生 频集的候选集，最后的频集lk必须是ck的一个子集。ck中的每个元素需在交易数据 库中进行验证来决定其是否加入lk。为了提高频繁项集逐层产生的效率，在这里， 该算法使用了一种重要性质用于压缩搜索空间，称为apriori性质。 性质1 若i为频繁项目集，则i的所有子集都是频繁项目集。 性质2 若i为非频繁项目集，则i的所有超集均为非频繁项目集。 证明: 根据定义，如要项集i不满足最小支持度闽值min-sup，则i不是频繁 的，即p(i)min_sup。如果将项a添加到i，则结果项集(ia)不可能比i更频繁 11杨晓平，关联规则 apriori 算法的改进，浙江海洋学院学报(自然科学版)第 25 卷第 2 期，2006 年 12王伟勤、钟敬堂，对 apriori 算法的一种改进，佛山科学技术学院学报（自然科学版） 第 25 卷第 2 期， 2007 年 15 的出现.因此，ia也不频繁，即p(ia )miu_sup。这样，就可以根据逆反公 理:即若一个集合不能通过测试，该集合所有超集也不能通过同样的测试。因此 很容易确定apriori性质成立。 为了解释apriori性质是如何应用到频繁项集的挖掘过程中的，这里就以用 lk-1来产生lk为例来说明具体应用方法。利用lk-1来获得lk主要包含两个处理步骤， 即连接步骤和剪枝步骤。 连接步骤:为发现lk，可以将lk-1中两个项集相连接以获得一个lk的候选集合 ck。设i1和i2是lk-1:中的两个项集，记号i1j表示ii的第j项;如i1k-2就表示ii中 的倒数第二项。为方便起见，假设交易数据库中各交易记录中各项均已按字典次 序存放.若lk-1的连接操作记为lk-1x lk-1，则它表示若i1和i2中的前(k-2)项是相同的 也就是说若有:（i1l= i2l)(i12= i22).（i1k-2= i2k-2) （i1k-1 i2k-1），则lk-1中i1和i2的内容就可以连接到一起.而条件（i1k-1= min-sup) return lk; procedurea priori_gen(lk-1,min-sup) for each itemset i1 lk-1 , for each itemset i2 lk-1 if（i1l= i2l)(i12= i22).（i1k-2= i2k-2) （i1k-1 i2k-1）then c= i1 x i2; /连接步:产生候选项集 if has_infrequent_subset(c, lk-1)then delete c; /剪枝步:移去那些含有不频繁子集的集合 else add c to ck; return ck; procedure has_infrequent_subset(c ,lk-1) for each(k -1)-subset s of c if slk-1 then return true ; return false; 3.3.2 apriori 算法性能瓶颈 apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。 但是随着研究的深入，它的缺点也暴露出来。apriori算法有两个致命的性能瓶 颈问题： （1）多次扫描事务数据库，需要很大的i/o负载。对每次k循环，候选集ck 中的每个元素都必须通过扫描数据库一次来验证其是否加入lk。假如一个频繁大 项目集包含10个项，那么就至少需要扫描事务数据库10遍。 （2）可能产生庞大的候选集。由lk产生候选k-项集ck是指数增长的，例如10 4 个频繁1-项集就有可能产生接近10 7个元素的候选2-项集.如此大的候选集对时间 和主存空间都是一种挑战。 17 3.4 apriori 改进算法 3.4.1 apriori 算法改进方向 1995年park等人提出了散列算法，其基本思想是:当扫描数据库中每个事务， 由cl中的候选1-项集产生频繁1-项集l1时，对每个事务产生所有的2-项集，将它 们散列到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计 数低于支持度闭值的2-项集不可能是频繁2-项集，可从候选2-项集中删除，这样 就可大大压缩了要考虑的2-项集。 同年，savasere等人提出了基于划分的算法。该算法先把数据库从逻辑上分 成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产 生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。该算法 的有点在于只需两次扫描整个数据库从而提高了算法的效率。 1996年，toivonen提出基于采样的算法。该算法对数据库进行采样，并对样 本数据库进行挖掘从中得到相应的规则，然后将这些规则带到数据库中进行验 证。该算法显著提高了算法的运行效率，但是会使产生的结果不精确。 brin 等人给出动态项集算法。动态项集计数技术将数据库划分为标记开始 点的块。不像apriori算法仅在每次完整的数据库扫描之前确定新的候选项集， 在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计 数的所有项集的支持度，如果一个项集的所有子集己被确定为频繁的，则添加它 作为新的候选。该算法需要的数据库扫描比apriori算法少。 3.4.2 apriori-tid算法 设|d|表示数据库 d 中事务的个数，minsup：minsup=min-sup*|d|，|tidl（x） |表示 tidl(x)所含元素的个数，也就是支持事务 x 的计数。 当扫描事务数据库 d，求频繁项集 l1 时，记录频繁项集 l1 每一项的 d 中所 有支持该项的事物的唯一编号 tid 的列表。 当计算候选 2-项集 c2 各项的支持记数 时，不需要在扫描事务数据库 d，而是通过计算 l1 中两个项 tid 列表的交集，求 出 c2 中某项的 tid 的列表，而这一列表元素的个数就是该项的支持记数。支持记 数大于或者等于 minsup 的项就被添加到频繁 2-项集 l2 中，从而求出频繁 2-项集 l2 ，并保留 l2 中各项的 tid 列表。同时，当计算候选 3-项集 c3 各项的支持记数 时， 也不需要在扫描事务数据库 d， 而是通过计算 l2 中两个项 tid 的列表的交集， 18 以此类推求各项的频繁项集。该算法对整个物理数据库只需扫描一次，由于内存 速度远远大于磁盘读写速度，所以在运行是减少了低速的 i/o 时间，速度打打提 高。 apriori-tid 算法描述如下： 输入：事物数据库 d；最小事物支持度阈值 min-sup； 输出：d 中的频繁项集 i 。 ll=find_tidl(d) for(k=2;lk-l;k+) for each itemset xlk-l for each itemset y lk-1 if(x1=y1x2 =y2 xk-l=yk-lx k minsup) then add i to ll return l1 ;tidl(i)(il1); 19 第四章 数据预处理 4.1 数据预处理的重要性 数据预处理是数据挖掘过程中的一个重要步骤， 尤其是对包含噪声、 不完整， 甚至是不一致数据进行数据挖掘时，更需要进行数据的预处理，以提高数据挖掘 对象的质量，并最终提高数据挖掘所获模式知识质量 14。所谓噪声数据是指数据 中存在着错误或异常的数据，不完整数据是指感兴趣的属性没有指，而不一致数 据则是指数据内涵出现不一致的情