数据挖掘毕业论文

基于点击数据的事件检测算法研究 摘 要 近年来，针对点击数据的潜在事件挖掘吸引了众多科研人员的目光。本文研究的重点是对Web搜索引擎收集的用户搜索记录进行潜在事件挖掘。目前已有事件检测算法对查询内关键词间的相互联系不够重视，往往通过将查询与页面关联的方式将不同的查询聚类成事件。此外，现有算法还存在算法复杂度较高、可视化程度较低、不易扩展为增量计算等问题。 针对上述问题，本文提出了一种新型的基于点击数据的事件检测算法：通过建立关键词间的联系，并根据联系模式之间的相似性挖掘出潜在事件的核心关键词和扩展关键词，最后形成事件的拓扑结构图。首先，建立包含了关键词（结点）和关键词联系（边）的图 ，并通过频数统计和突发性测度将每个关键词和每个联系分为三类：孤立、突发和非突发；接着，从突发关键词或联系出发,通过深度或者广度搜索 的方法(根据模式相似度),将含有一个事件 的子图 分割出来；最后，对 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 提取出核心和扩展关键词。最后，为了提高事件的可视化程度，算法生成了事件的拓扑结构图。 实验结果显示，针对某商业搜索引擎的搜索记录进行分析，本文提出的算法得到了较好的结果。 关键词：事件挖掘；点击数据；关键词关联 ABSTRACT（需要修改） In the past few years, underlying event detecting from click-through data has attracted attention of many researchers. The research focus in this paper is to detect underlying events from the click-through data generated by Web search engines. Existing event detecting algorithms usually cluster different queries into a event by connecting queries with pages, ignoring the relationship between keywords in the same query. For this reason, there is the problem of high time and space complexity existing in current algorithms, so that it’s hard to detecting events from large-scale search log. This paper introduces a new event detecting algorithm from click-through data specific to the problem above: detecting core and noncore keywords of the underlying events by building the relationship of keywords and then computing the similarity of the relation pattern. First, the algorithm build a graph whose each vertex contains a keyword and each edge contains a relationship of two keywords, and then each vertex and each edge is classified to be: isolated, burst or non-burst by frequency statistics and entropy measure. Second, it search depth-firstly according to burst keywords and burst relations, and a subgraph which contains a event is cut by similary of relation pattern. Finally we get both core keywords and non-core keywords of a event by analyzing . The experiment shows that the algorithm produces high quality results by applying it to the click-through data collected by a commercial search engine. Keywords: event detection; click-through data; keywords relationship 目 录 TOC \f \t "标题 1,2,标题 2,3,标题 3,4,标题,1" 1 引言 1 1.1 研究问题的背景和意义 1 1.2 国内外研究现状 2 1.3 当前研究存在的问题 4 1.4 本文的工作 4 1.5 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 的组织 5 2 算法框架介绍 6 2.1 概述 6 2.2 数据准备 7 2.3 数据表示 8 2.4 关键词关联 9 2.5 突发性侦听 12 2.6 模式相似度度量 14 2.7 模式切割与事件提取 15 2.8 算法总结 16 3 实验结果分析 18 3.1 数据集 18 3.2 实验 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 18 3.3 事件举例 18 3.4 结果分析 19 4 论文总结 21 4.1 论文 工作总结 关于社区教育工作总结关于年中工作总结关于校园安全工作总结关于校园安全工作总结关于意识形态工作总结 21 4.2 进一步工作 21 附 录 22 1​ 引言 1.1​ 研究问题的背景和意义 随着计算机网络和通信技术的飞速发展，互联网（Internet）在人们生活中扮演了越来越重要的角色，网络信息已经渗透到了现实社会中的每一个角落。World Wide Web(WWW)作为Internet上最流行的应用，它所蕴含的信息量在日新月异地增长。 在给予人们方便的同时，由于Web页面的过于复杂庞大，以及无结构的、动态的特性，人们难以迅速便捷地在Web上找到所需要的数据和信息。用户关心的只是Web信息中的很小的一个子集，然而大量不相关的、重复的甚至错误的信息可能会淹没用户感兴趣的话题。 搜索引擎的出现在一定程度上解决了人们对信息的需求。以Google为代表的搜索引擎使得用户可以在海量的信息资源里迅速检索出自己感兴趣的话题。毫无疑问，搜索引擎中记录用户和网络搜索引擎殷勤交互的日志，即点击记录，在整个网络数据中占有着重要位置。 传统的Web数据挖掘着重于Web文档的数据挖掘，从而发展了许多基于文本(Text-stream)分析的数据挖掘方法。与此同时，用户在使用搜索引擎过程中产生的海量点击（Click-through）记录信息往往被忽视。 在图 1中，Google中国记录了2008年5月19日14时30分左右的搜索流量分析[1]。在图中可以看出，14时30分的搜索流量急速下滑后急速上升，图片的背后是全体国人暂停手中的工作默哀三分钟，沉重悼念在汶川大地震中遇难的同胞。 图 1：谷歌搜索流量分析图 对点击记录进行事件挖掘得到的事件检测结果，普遍应用于事件预警，基于事件的广告投放等等。 1.2​ 国内外研究现状 Web数据挖掘可以广泛地分成三大类：Web内容挖掘、Web结构挖掘和Web使用记录的挖掘[2]。而在事件挖掘中往往只涉及Web内容挖掘和Web使用记录挖掘。Web内容挖掘是指对Web页面中含有的内容(也称文本流)进行挖掘，而Web使用记录挖掘是指对用户在进行网络浏览过程中产生的过程记录（Web log，也被称为点击记录）进行挖掘。在2006年以前，基本上所有的事件检测方法都是Web内容挖掘的，如文献[3]使用了统计的方法来研究在文本流中挖掘热门事件。 事实上，文本流和点击记录的数据挖掘方法具有很大的不同，基于文本流的方法并不能很好地应用于点击记录数据上。这主要是因为它们的结构差异甚大：首先，在文本流中，蕴含的信息量丰富但同时也有太多无用的信息，如需要使用TF-IDF法[4]以提取文本中的主要词语；而在点击记录中，蕴含的信息量较少但同时查询中的每一个词语都是至关重要的，每个关键词都尽职描述了用户的兴趣。其次，在文本流中，信息是无序无结构的，需要抽取出文本中暗藏的时间信息才能进行事件检测；而在点击记录中，信息是具有良好结构的，可以很轻松从记录中获取时间等信息。 在2006年，文献[5]首次提出从点击记录的观点进行事件检测，并提出了两段聚类（Two-phase-clustering）算法，简称2P方法，取得了较好的效果。文献[5]将点击记录定义为<查询词，页面>（query-page）序偶的集合，根据预先定义的时间间隔尺度，将集合划分为几个互不相交的子集。然后每个子集构建一个二分图，其中二分图中的顶点是查询词或者页面。如果某查询词和某页面之间存在序偶关系，则二分图中的代表该查询词和该页面的顶点间有一条边，边的权值定义为子集中序偶出现的次数。接着，将这些二分图合并成一个大的二分图，并转换成其的对偶图。最后，对这个对偶图先后进行语义切割和模式切割，从而得到现实世界的事件子图。缺点有二，一则其没有进行突发性检测，二则其在对图进行切割时必须指定切割数目，这需要用户需要有事件数目的先验知识。文献[5]的算法框架如图 2所示。 图 2：文献[5]的算法框架 文献[6]在分析用户搜索记录的基础上，从搜索引擎中获取对应的文本流，从而可以将以前的文本流数据挖掘方法应用到事件检测上，其亮点在于无缝地将Web内容挖掘和Web使用挖掘的两类挖掘方法结合起来以得到更好的挖掘效果。 文献[7]与文献[5]不同的是将点击记录定义为<查询词，会话>(query-session)的序偶关系。文献[7]根据查询的语义和发生时间将点击记录映射到二维极坐标空间上，然后应用GPCA(Generalized Principal Component Analysis)方法[8]估计子空间，其中每个子空间包含了语义相近的查询。接着删减去不代表突发事件的子空间，最后得到用户感兴趣的事件。文献[7]将其命名为DECK方法，缺点是算法复杂度太高，且当噪音很大的时候，效果并不很好。文献[7]的算法框架如图 3所示： 图 3：文献[7]的算法框架 文献[9]运用小波空间分析，对Flickr（一个在国外很流行的图片分享站点）的用户数据进行事件检测。 1.3​ 当前研究存在的问题 近年来对点击记录的事件挖掘方法有了不少进步，不过还存在着相当一些问题留待解决： (1)​ 缺乏算法复杂度分析、算法复杂度较高 在对点击记录进行事件挖掘中，算法面对的点击记录条目通常在几千万到上亿之间，数据库大小往往是GB级甚至是TB级，这特别要求算法需要有良好的空间复杂度和事件复杂度。 例如，在文献[5]中，构建后的图非常庞大，且图中的每个结点都可能存在相互关系，空间复杂度非常高。而在文献[7]中提出的DECK方法，进行语义相似性就已经需要 的时间，另外还需要PCA进行主成分分析、非线性约束优化问题等复杂度较高的操作。因此在文献[7]中的实验设计中，实验只能通过抽样10万个点击数据来进行。 此外，基本上所有的文献都没有对其算法进行算法复杂度分析，这不得不说是一种遗憾。 (2)​ 可视化程度较弱 基本上所有现有研究算法中对事件监测返回的结果不外乎以下三种情况：查询词的集合，点击URL的集合，查询词及其对应URL的集合。其中以最后一种情况为最多，文献[7]以及文献[5]均为这种情况。这样，用户仍需要根据实验结果进一步提取事件的主要内容。 (3)​ 不易扩展为增量式挖掘 无论文献[7]或文献[5]，都是对静态数据进行挖掘。而在现实中往往有对动态的数据进行事件挖掘的需求，这就对算法提出了增量式计算的要求。然而，在算法结构上，2P方法和DECK方法都很难扩展为增量式算法。 1.4​ 本文的工作 针对上述提出的现有算法的三个缺点，本文通过分析某商业搜索引擎的搜索日志记录，提出了一种简单的但是更为快速的算法以对点击记录数据进行事件挖掘，其算法复杂度较低，返回的结果简单明晰，以及从算法结构上易于扩展为增量式挖掘。经实验证明，这个算法可以较好地提取出点击记录中的事件。 1.5​ 论文的组织 全文共分为4章： 第一章：阐述问题的提出与研究背景，对现有国内外研究中的Web点击记录事件挖掘算法进行了简要阐述。 第二章：对现有算法的不足提出了基于关键词以及关键词联系的一种新型算法，对算法的细节进行了描述，并进行了算法复杂度分析。 第三章：将提出的新型算法应用于某商业搜索引擎的点击数据记录，并分析实验结果。 第四章：对全文进行研究总结以及展望，并指出今后的研究方向和需要做的工作。 2​ 算法框架介绍 2.1​ 概述 与之前研究不同的是，本文中研究的最小单位是关键词。表格 1展示了点击记录的样例，表格中每一行包括了用户匿名ID、查询（包含一个以上的关键词）、查询时间和点击的页面（当用户不产生点击时，此项为空）。 首先阐述一下查询（query）和关键词（keyword）在定义上的不同。查询是指用户和搜索引擎进行交互所需要的输入部分，其一般包括一个或一个以上的关键词。而关键词是查询的一部分，它是一个单词，在查询中一般被空格或其他空白字符隔开。 在以往文献的研究中，研究的是查询和点击页面之间联系（文献[5, 7]），一次查询会话甚至一次查询被作为研究的最小单位，这会导致一个缺点：搜索引擎面对的是一个庞大的人群，用户的需求总是多样的，一次查询中包含的不仅仅有公共事件，还有一些用户个性的需求。因此，关键词间联系没有得到足够的重视。事实上，一个查询中包含的关键词间联系同时也蕴含了许多可用于挖掘的信息。 根据观察，查询中除去一些高频词外，每一个关键词对于用户而言都是至关重要的，但是对于某个事件而言，却不是同等重要的。从表格 1中的第一项关键词可以看出用户是想查询母亲节礼物，这里面包含了两个主要成分：母亲节（mothers1 day）和礼物（gifts）。对于该用户而言，它们是缺一不可的。在本文的研究中认为每个查询是由公共成分和私有成分组成，其中公共成分描述了公共事件，私有成分描述了用户需求。上例中，公共成分是“mothers day”，私有成分是“gifts”。在一个事件中，公共成分往往是高度聚集的，如“mothers day”会在母亲节附近几天高频出现，而私有成分则较之在整个时间区间里分布得更为均匀，例如“gifts”也有可能出现在其他事件（如父亲节）中。 本文的研究就是根据这一特性，对关键词间联系进行研究，从而将公共成分从用户查询中剥离出来，使之成为被检测出事件的核心关键词。此外，具有较高频数出现的私有成分被认为是事件的扩展关键词。 尽管可以挖掘的内容越多，得到的结果就会越准确，但在本文的研究中，只关心前三项内容，最后一项点击页面并没有被考虑进去。理由是在实验中发现：数据集中的URL只有顶级域名部分，覆盖的信息不仅很少，而且容易干扰到结果的准确性。在没有更好的办法以前，暂时不考虑点击URL这一项，这也是进一步需要做的的工作。 匿名ID 查询关键词 时间 点击URL 1771959 mothers day gifts 2006-04-29 07:04:21 http://www.gourmetgiftbaskets.com 1771959 mothers day gifts 2006-04-29 07:04:21 http://shop.store.yahoo.com 1821893 mothers day craft 2006-05-10 15:23:43 http://www.enchantedlearning.com 1955618 mothers day poems 2006-05-09 08:36:07 http://www.poemsforfree.com 表格 1：点击记录样例 2.2​ 数据准备 一般来说，用户与搜索引擎交互的过程中产生的日志会包含一些无法被处理或者对挖掘方法无用的信息： (1)​ 搜索词为空（用户不输入任何文字就进行查询） 这里采用的方法是将搜索词为空的查询记录删去。 (2)​ 点击URL为空（即用户没有点击任何页面） 这说明搜索引擎返回的页面并不匹配用户的需求，也就是说所输入搜索词并不精确匹配用户的需求，这时候也将此查询记录删去。 (3)​ 搜索词含有高频词 在大多数搜索引擎中，高频词默认是被忽略的，因为其并不含有实质意义，如for，to，from，www等[10]。因此，在清洗的过程中本文也将这些高频词在搜索关键词中去掉。 同时，为了防止单一用户短时间内对同一关键词提交大量请求而导致检测出错误的事件，同时也为了降低处理数据的规模，将处理的最小单元设置为查询会话。一个查询会话（Session）被定义为用户与搜索引擎一次交互过程中的所有关键词以及该过程的开始发生时间。一般来说，一个查询会话包括一个或者一个以上的查询。 查询会话有两个特点：一是在短时间内进行，二是各个查询之间的关键词具有重叠。根据这两个特点，可以将查询聚类成查询会话。聚类问题往往比较复杂，算法 1中将较为复杂的聚类问题转换为较为简单的分类问题。 整个数据准备过程如算法 1所示。 算法 1：数据准备 输入：原始查询日志的集合 输出： 个会话 1.​ 将 按用户的匿名ID进行分类，每个子集中查询都属于同一个匿名ID，得到 。 2.​ 对于任意一个子集 ，将元素按查询时间从小到大进行排序，得到 ，其中 。 3.​ 对 到 ，依次扫描 ： a)​ 若 为空或者 为空，则将 从 中删除。 b)​ 否则， 或者是属于上一个会话，或者是新的会话：如果距离上一次查询的时间小于某个预设的时间尺度，或者和上一个会话具有相同的关键词，则认为是新的会话，否则是新的会话。 4.​ 转到第2步，处理其他子集，直至所有子集被处理完毕，并返回会话的集合。 算法复杂度分析：为简单描述起见，每一步处理的数据规模均为 。 第一步只需扫描一遍所有数据，算法复杂度为 。第二步中，只对子集 内元素进行排序，平均需要 的复杂度进行排序，而事实上由于搜索引擎是按时间顺序记录日志的，在第一步操作后子集 里的元素往往是已经按时间排序了的，所以这一步往往可以省略。第三第四步中，使用决策树方法对查询分类，算法复杂度也是 。综上，在数据准备阶段中的算法复杂度为 。 2.3​ 数据表示 给定查询会话数据和一个设定的时间窗口长度（如一天、三天甚至一周），数据可以根据窗口长度划分为一组数据序列，其中序列中的每个元素包含了在相应时间窗口内的所有查询会话。注意，时间窗口长度是人为设定的，不同的事件具有不同的事件生命周期，需要针对不同类型的事件采用不同的窗口长度。设 为时间窗口数目，则会话序列 可以表示为： 例如，如果窗口长度被设定为1小时，则一天可以被平均划分为24个时间窗口，每个窗口包含一组查询会话，表示为序列 。 为了描述关键词 出现频数的演变模式，在每个时间窗口里查找关键词 的出现频数：若某个查询会话中关键词出现了 ，则频数增一。根据在每个窗口里关键词 出现频数，可以得到 的出现频数序列，以及 的总出现频数 。然而，由于不同的关键词之间的频数可能相差甚远，不方便做比较分析，故将其转换为频率序列，表示为： 至此，每个关键词可以被表示为三元组的形式 ，其中 ， ， 的定义如上文所述，参见图 4（暂时忽略图中high entropy）。 将每一个关键词 都作为图的一个结点 ，得到一个有向图 。此时 中只含有出度和入度都为0的孤立结点。至于为何 采用有向图结构，将在下文叙述。 图 4：关键词的表示形式示例 2.4​ 关键词关联 通常来说，一个事件包含的关键词往往不止一个。作为例子，与“母亲节”相关的关键词就有：mothers、day、gifts（礼物）、card（贺卡）、poem（诗）等，为了描述“母亲节”事件，仅仅靠mothers这个关键词是不行的。 为了描述关键词之间的联系，在图 上加上边来连接两个具有相互联系的关键词。然而在实践中发现以无向边作为联系具有很大的局限性。还是以母亲节为例，相关的关键词中其中有mothers和day，一般来说在查询中，day总是会出现在mothers的后面以构成一个专有名词mothers day以描述“母亲节”。如果使用无向边来描述两个关键词的联系，最后在输出事件关键词列表的时候，得到的只是一堆无序的关键词集合，还需要依靠人工挑出主要关键词来找出事件。若事件中含有了某些专有词组，这点显得尤为困难。 有向边相对于无向边的意义在于：有向边可以描述关键词的先后次序，从而可以根据边的方向来描述关键词之间更强的联系。对于上面的例子，可以建立由mothers指向day的有向边，从而描述了一个专有名词mothers day。 对于一些先后次序不是很明显的关键词，如mothers和gifts，也可以通过有向边来联系，如何区分这两组关键词（day和gifts）将在下文中的模式切割中提到。简单地说，为表示无明显前后次序关系，连接相同结点的两条异向边可以合并成一条边。 建立了关键词之间的联系后，和关键词侦听一样，也需要知道关键词之间联系的演变模式。类似地，为了描述边 的演变模式，计算它在时间窗口 中的出现频数：若某查询会话中同时出现关键词 和 ，且 出现在 之前，则出现频数增一。类似关键词频率序列一样，定义关键词联系的频率序列为： 那么，每条边（关键词联系）可以类似地被表示为三元组的形式。至此，整个数据模型被建立为一个有向完全图 ，其中 和 分别描述了关键词和关键词间联系的演变模式，如图 5所示。接下来，可以根据模式切割将属于同一个事件的子图在图 中划分出来，其中每个子图代表一个事件。 图 5：关键词关联 以下对全图 的空间复杂度进行讨论。在实验中发现，和某关键词联系的关键词会有非常多，如与mothers联系的关键词有近3000个，这同时也体现了搜索引擎用户目的的多样性。假设每条边（联系）中的窗口数目为 个，每个关键词平均有 个相互联系的关键词，则空间复杂度为 ，其中n为关键词数目。 按 计算，显然不能将整幅图放在主存储器中。这个问题可以通过虚拟存储器等技术解决，亦可以通过下文提到的删减技术来降低其空间复杂度。 实际上，许多关键词或者关键词联系的总出现频数很低，甚至是一两次。由于其的频数太低以至于不可能作为事件的关键词，这些出现频数非常低的结点或者边在事件监测算法中不体现任何作用。因此，在本文的实验中，将其从图中删减去，具体的删减步骤是： 1.​ 将出现频数少于某常数 （在本文实验中设定 ）的关键词从图中删去，如果有边与之连接，则连同与之相连的边一齐删去； 2.​ 对于某边 ，如果其出现频数均少于与之连接的两个结点的 ，则将其从图中删去。 2.5​ 突发性侦听 作为例子，图 6展示了在在92天中关键词mothers和google的搜索频率的演变模式（以下简称模式）。可以看出，mothers和google的模式是截然不同的：mothers在第73天附近陡然增大，又陡然减小，而google的模式基本上是一直维持在一个波动比较小的范围之内。根据文献[11]中对“事件”的描述，事件的出现的标志是某些与该事件相关的特征词在出现频率上迅速上升，亦即“爆发” （burst）。 可以简单将搜索日志中的关键词分为三种：孤立关键词、突发关键词和普通关键词。孤立关键词是指不常见的关键词，通常包含了用户的某些不常见的请求，一般来说在任意一个时间窗口内频数都比较低（ ）。突发关键词是指该关键词在某段时间内高频出现，如图 6中的mothers，一般来说对应了某个周期事件或非周期事件。普通关键词通常也具有较高的频数，但是在整个时间段里并没有显现突发出现的状况，趋向于均匀分布，如图 6中的google。 根据这个想法，某关键词在单位时间内频率的陡然增大，意味着有可能发生了相关的事件。因此，在算法中进行对关键词的侦听可能会找到与之联系的事件。值得注意的是，根据图 6，很容易会想到用方差来描述事件的突发性，当方差大的时候说明关键词搜索频率波动较大，即出现突发性，即事件。然而，一个关键词中可能包含了多个事件（如周期性事件），如果用方差来描述，则周期性事件也会被认为是一个事件。然而，周期性事件并不是我们所关注的。所以本文没有简单使用方差来描述事件的突发，而是采用熵来描述事件的突发性[12]。某个关键词 的突发度定义如下： 其中 为时间窗口数目， 为第 个时间窗口内关键词的频率。易知， 的取值范围为 。根据熵的定义可以看出，当关键词的分布愈趋于稳定（亦即非事件或者周期事件）， 的取值愈趋于0，而当关键词的分布愈趋于不确定（亦即事件）， 的取值愈趋于1。 根据这个想法，本文通过实验确定一个阈值 ，当 时，认为 是一个潜在的事件关联词。具有高 的关键词A和C在图 4中被标示了出来。 类似地，可以定义关键词联系（边）的突发度。在某些情况下，边的突发性相较于结点更容易被捕获。在实际应用中可以根据实际情况，对结点或者边进行侦听。在本文的实验中使用了侦听边的方法。 在此步骤中，对每一结点或边计算突发度 ，算法复杂度为 ，其中 为图 中结点或边的规模， 为窗口数目大小。可以通过窗口合并的方法将相邻几个窗口合并为一个窗口从而降低算法复杂度。 图 6：点击记录的动态变化 2.6​ 模式相似度度量 在模式切割之前，需要先进行模式（pattern）相似度的度量。模式是指关键词或者关键词间联系的演变规律，是序列 或者 。所谓模式相似度 ，是指两个模式的演化规律的相似程度，当完全相似时， ，当完全不相似时， 。越相似的模式说明这两个模式越可能属于同一个事件。 使用简单的欧氏距离是一种可能的办法：若两个序列分别为 和 ，则其欧式距离为 ，定义 。 越大，则相似度越小。同时使用欧氏距离衡量的算法复杂度相当低。然而在实践中发现使用欧氏距离来衡量相似度并不是最好的方法。举个简单的例子，有两组序列，第一组序列 和 ，第二组序列 和 ，两组序列在欧氏距离度量下相似度都为0，亦即完全不同，但是显然第二组序列的两个序列相似度应该比第一组的要大，理由是第二组中的两个 的距离相距更近，它们更可能属于同一个事件。 因此，在本文的研究中模式相似度的衡量采用了动态时间规整法（Dynamic Time Warping, DTW）[13]。 给定两个序列 和 ，长度均为m： 使用DTW法，构建一个 的矩阵，其元素 为 和 的欧氏距离，亦即 。每个元素 意味着 对 的规整。翘曲路径 是矩阵中连续元素的集合，其定义了 和 之间的映射。 中第 个元素 ，则有： 翘曲路径 必须满足下面三个约束： (1)​ 边界条件： 应从 开始，于 结束。 (2)​ 连续性：给定 和 ，则 (3)​ 单调性：给定 和 ，则 此外，为了防止模式偏移量过大，本文约束翘曲路径须在矩阵的五对角线上（从而模式左移或者右移两个时间单位后仍和原模式完全相似）。 显然，满足以上约束的路径有许多，但我们只需要找到“花费”最小的那条： 由上述定义可知，欧氏距离测度实际上是约束在主对角线上的翘曲路径。寻找该路径可以使用动态 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 ，在此不再赘述，详见文献[13]，其算法复杂度为 ，相较于欧氏距离的复杂度 要大上一些。 据此定义两个模式 和 的相似度： 显然， 的取值范围为 。 2.7​ 模式切割与事件提取 可以观察到，在一个事件中关键词具有两类（不妨设为核心关键词和扩展关键词），核心关键词跟其他关键词都具有较强联系，而扩展关键词只和核心关键词有联系。因此含有事件 的子图 的结构大体上可以看作是星形的拓扑结构，如图 7所示。 模式切割的任务是将含有事件的子图 从整个图 中分离开来，并区分出核心关键词和扩展关键词。事件的爆发通常以某关键词或者某两个关键词联系的爆发为标志。通过遍历全图 中所有的结点和边，使用关键词（或关键词联系）侦听技术将潜在可能的结点（关键词）或边（关键词联系）加入到处理队列 中，最后得到包含了所有潜在可能事件的处理队列 。 接着，根据模式相似度进行聚类。依次对队列 中元素出列，其可能是结点，也可能是边。从该元素出发开始进行遍历相邻的边（深度搜索或广度搜索均可），若遍历到的结点或边的模式和初始元素的模式相似度较高（ ），则将该邻接边纳入子图 中。 实验中发现，对于给定一个事件，其结点和结点的模式相似度较低，而边与边的模式相似度较高，从而容易根据边的模式相似度进行模式切割。 最后根据以下两条准则对边进行合并： 1.​ 若子图中存在连接相同一对结点，但方向相反的两条有向边，将其合并为一条边，方向以两条边中种频数较大的为准。 2.​ 若子图中存在某结点 连通结点 （ 指向 ），存在第三个结点 ， 指向 且 也指向 ，则将 指向 的边合并到 指向 的边。 在上述第一条准则中，规定了相邻两个结点之间具有确定的前后次序；而第二条准则中规定了任意两个结点之间若有通路，则该通路是惟一的。这两条准则的目的都在于使得子图 更为易于理解。 得到子图 后，根据上文的分析，核心关键词结点位于星形拓扑结构的中心，而扩展关键词结点位于拓扑结构的外围。根据这点观察，可以根据 的结构将子图中的结点分成两类，从而提取出易于理解的事件。 对结点个数较多的 ，有必要区分核心关键词和扩展关键词。设 的结点个数记为 ，结点 的出度和入度分别记为 和 ，根据定义有： MACROBUTTON MTPlaceRef \* MERGEFORMAT (1) 若结点 的度数 ，也就是说结点 位于星形拓扑结构的外围，则其为扩展关键关键词，否则为核心关键词。 事件的发生时间可由核心关键词间联系的条形图峰值处的时间戳表示。 2.8​ 算法总结 综上所述，算法的整个流程如算法 2所示： 算法 2：模式切割与事件提取算法 输入：全图G 输出：代表事件的拓扑图 ，其中 为事件数目 1.​ 在全图 中进行关键词侦听，寻找事件潜在的元素（结点或边），对每一个找到的元素添加到处理队列 中。初始子图 为空。 2.​ 将 中元素出列，并将其添加到 中，并作为 的初始元素，记为 ： a)​ 若该元素为结点，则直接加入 。 b)​ 若该元素为边，则将该边以及该边连接的两个结点一并加入到 中。 3.​ 从初始元素 出发进行深度或广度搜索对全图中的边进行遍历： a)​ 若遍历到的边 和初始元素 的模式相似度 ，则将该边以及与该边相联系的新结点 一并加入到 ，并继续进行遍历。 b)​ 否则将 和其异向边 合并起来得到 ，若 ，则将 ， 和 一并加入到 并继续遍历。 c)​ 若在前两步中的模式相似度都较小，则终止在该方向上的遍历，返回到其他方向继续遍历 4.​ 对得到的图 进行边合并。 5.​ 对得到的图 ，根据 GOTOBUTTON ZEqnNum213664 \* MERGEFORMAT (1)式计算每个结点 的度数 。 6.​ 若 则 代表的关键词为扩展关键词，否则为核心关键词。 7.​ 转到第2步继续分割子图，直至 为空 3​ 实验结果分析 3.1​ 数据集 在本章实验所使用的数据集来源于AOL搜索引擎[14]。该数据集收集了从2006年3月1日到2006年5月31日共92天时间的点击记录数据。数据集包含了65万个匿名用户产生的3639万次的查询，以及点击的1944万次页面。数据集总共包含了10个文件，总的文件大小为2.12 GB。 整个数据集按时间窗口大小为1天分割成92个子集，平均每个子集包含了39.55万个查询记录。 然而，AOL数据集并不是基准数据集，实际上在点击记录检测事件上也并不存在检验准确性的基准数据集（因为数据量太大以至于无法人工识别事件）。文献[7]在AOL数据集上手工剔出35个事件，包括了可预见的事件（例如阵亡烈士纪念日，5月29日）和不可预见的事件（例如Dana Reeve去世，3月6日）。 本文将基于文献[7]的事件列表对本文提出的算法进行评价。 3.2​ 实验设计 由于数据集的数据规模巨大，本文的实验中采取了2.4节中提出的删减技术：对一些出现次数的关键词或关键词联系从图中删去以节省内存和加快处理速度。删减的合理性将在结果分析3.4节中阐述。 最后，将检测出来的事件通过搜索引擎用手工检查，并根据对比的情况说明本文提出算法的精度。 3.3​ 事件举例 根据上述实验设计，本文通过编写程序对AOL数据集进行了分析，以下通过一个典型的事件“母亲节”举例： 在图 6中可以看到关键词mothers的查询频数在第73天突然升高，在第76天又急剧下降，符合事件骤起骤灭的特性。通过对边的侦听，可以将mothers-day这一关键词联系捕获到。 对该边附近的子图进行切割，得到含有19条与之相关联的边的子图。再对边进行合并后得到了含有12条边以及13个结点的子图 ，子图如图 7所示（除关键字外的信息已略去）： 图 7：母亲节事件子图 如下关键词：free，card(s)，crafts，day，poem(s)，gift(s)等扩展关键词是与核心关键词（mothers和day）联系的。注意其中某些关键词具有单数和复数两种形式，作为可选的选项，可以在数据清洗阶段使用NLP（自然语言处理器）[15]对名词的单复数进行合并处理，这样还可以得到更好的切割效果。 根据2.7节中的定义，事件的核心关键词为mothers，以及与之紧密相关的是day，它们组合成mothers day，与该事件相关的card(s)，gift(s)，crafts均被准确找到。 一个比较奇怪的关键词是free：为什么它也是事件关键词，而且放在mothers的前面呢？在网上，人们习惯搜索免费的事物（free），实验中发现，在整个时间段中，free的搜索次数也是最多的，达到了五万多次。在这个事件中，它和mothers的相似度也非常高，达到了0.970914，主要原因还是因为出现了大量的搜索关于“免费母亲节贺卡”，“免费母亲节礼物”，因此该关键词也被列入了事件关键词。printable出现的原因和free的类似。 从子图可以看出，即便在2.7节中不严格定义核心关键词和扩展关键词，对于切割出来的含有事件 的子图 ，也可轻易从中找到事件的核心与扩展关键词。 3.4​ 结果分析 经对数据集分析，共有86万个不同的关键词，其中出现次数超过20次以上的只有50,534个。而这5万多个关键词的相互联系最多可达25亿个（50000^2），然而联系是稀疏的，只有11,184,811个。这一千多万条边中，只有3,113,095条边的出现频数大于1，只有1,656,250条边的出现频数大于2。 根据上述数据得知，进行2.4节中的删减是有效的：它将原来的数据规模缩减到10%以下，并且保证了不会丢失任何感兴趣的数据。从而，经过删减技术的处理，算法面对的规模大大缩小，从而可以将整个数据结构放在内存中进行处理，而不再需要额外的转储技术。 算法的效率与结果分析如下： (1)​ 算法效率分析 在实验中，除去数据清洗的时间，总共时间花费为255.15秒，其中构建图 就耗用了244.21秒的时间。得益于删减技术的应用，内存最高峰只占用1G左右，更为可观的是使得后续算法面对的数据规模大大减小（变为原规模的10%以下），在后续的突发性侦听和模式切割，总共只花费10.94秒的时间。其中执行实验的平台为：AMD Athlon 3600+ 2.0G Dual Core，2G内存。 (2)​ 算法结果分析 在165万条联系中，突发性侦听得到398条边属于潜在的事件。进行模式切割后，共得到166个事件。对关键词个数多于两个的38个事件一一进行了手工检查。由于在算法并没有考虑URL的因素，返回的结果只是一个具有拓扑结构的关键词集合。对每一个事件，使用Google 搜索引擎输入其关键词集合，检验关键词集合准确性的同时，本文的研究还检验了拓扑结构的正确性。 手工检查中发现：除了有2个不同的事件被认为是同一个事件，其他均一一对应了现实中的事件。其中37个事件生成的拓扑结构图均易于阅读且易于还原为原事件，在搜索引擎中显示的关键词次序和拓扑结构次序基本吻合。这38个事件附在了附录的表格 2中。 同时，在人工检查的过程中发现，由于事件关键词具有良好的拓扑结构，其更容易和搜索引擎结合得到事件的真实URL，从而获取得到更详尽的事件内容。在手工检查中发现，搜索引擎的第一页就已含有对应事件的真实网址。回顾到文献[6]是以事件挖掘结果和搜索引擎结合以得到更详尽的事件信息，根据这个特性，若本文的算法与文献[6]中与搜索引擎交互算法相结合，相信会得到更好的结果。 4​ 论文总结 4.1​ 论文工作总结 本文对现有点击记录事件挖掘算法进行了研究，并针对现有点击记录事件挖掘算法中的不足，对以下几个方面做了创新改进： (1)​ 现有挖掘算法对查询内关键词的联系不够重视，本文通过在关键词与关键词之间建立联系，并根据关键词联系之间的相似关系挖掘出事件，这也是本论文的主要贡献。 (2)​ 现有挖掘算法往往忽视了聚合用户的查询会话，本文通过聚类算法将用户的查询会话作为一个处理单元，防止了单用户短期内高频率发起大量请求导致的错误事件检测。 (3)​ 使用了删减技术，使得算法面对的数据规模大大降低（变为原规模的10%以下），加快了程序的处理速度。 (4)​ 现有挖掘算法的返回结果往往难以清晰描述事件，本文通过建立事件内关键词的拓扑结构，对事件的关键词两两间建立先后次序，使得返回结果明晰可用，对用户更为友好。 4.2​ 进一步工作 Web点击记录的事件挖掘涉及多方面的理论、方法和技术，本文就其中一些关键问题进行了有益的研究和探讨，但还有很多问题需要进行更进一步研究。 首先，在搜索引擎中需要对收集来的大量点击数据进行分析，由于数据规模极大，往往不能把整个数据集储存在主存储器中。在本文的实验设计中亦是基于这个原因不得不使用删减技术，其准确性还有待实验证明。同时，搜索引擎面对的是时间性质非常强的数据，对事件的挖掘往往需要有时效性，当天发生的事件在第二天就必须挖掘出来。这也对事件挖掘算法提出了增量式处理的要求。基于这两个约束，可以继续进行增量式或者分布式方面的算法研究。 其次，由于数据集的具体限制，在本文的算法体系中未能将URL考虑进入。如果实验面对的是其他数据集，引入对点击URL的考虑可能会带来意想不到的用处。如何将URL并入本文的算法体系中，也是未来工作的一部分。 附 录 表格 2：部分检测出来的事件列表 事件 备注 Imette st Guillen被谋杀 The World's Hardest Riddle 世上最难的谜语 NCAA 全美大学体育联盟篮球联赛 《An American Haunting》上映 World Figure Skating Championships 世界花样滑冰锦标赛 Grand Prix Of Long Beach 长滩汽车大奖赛 Atlanta Motor Speedway 亚特兰大汽车赛车场 Daytime Emmy Awards 第33届艾美奖 Corned beef and cabbage 爱尔兰后裔在St. Patrick's Day的传统食物 April fools 愚人节 St. Patrick's Day 圣帕特里克节 Dana Reeves逝世 Christopher Reeves 超人演员 2006 Oscar 2006年奥斯卡奖 Easter 复活节 Mother’s Day 母亲节 Travis Stork和Sarah Stone分手 Hot greyhounds tips Memorial Day 阵亡将士纪念日 Border patrol game 2006 Kentucky Derby 肯塔基赛马会 First fuel banks 某绿色银行 De La Hoya 世界知名拳击高手 Cinco de Mayo 五月五日节 Masters Golf 高尔夫名人赛 Tax deadline Pacific Life Open Tennis 印第安维尔斯大师赛 Big East Mens Basketball Tournament Sharon Stone 莎朗·斯通 David Blain 街头魔术 Nasdaq 100 纳斯达克100指数 Daylight Saving Time 夏时制 Academy of Country Music Awards 美国乡村音乐学院奖 Daly Fan Club Philadelphia Flower Show 最负盛名的世界室内花展 Hairspray Movie 电影《发胶明星梦》 Daytona Bike Week World Baseball Classic 世界棒球经典赛 参考文献 [1] 谷歌. 哀悼与团结的曲线[Z]. 2008. [2] 涂承胜，鲁明羽. Web 挖掘研究综述[J]. 计算机工程与应用. 2003, 39(010): 90-93. [3] Fung G P C, Yu J X, Yu P S, et al. Parameter free bursty events detection in text streams [C]. In: Proceedings of the 31st international conference on Very large data bases.Trondheim, Norway : VLDB Endowment, 2005. 181-192. [4] Salton G, Mcgill M J. Introduction to modern information retrieval[M]. McGraw-Hill New York, 1983. [5] Zhao Q, Liu T, Bhowmick S S, et al. Event detection from evolution of click-through data [C]. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining.Philadelphia, PA, USA : ACM, 2006. 484-493. [6] Hu M, Sun A, Lim E. Event detection with common user interests [C]. In: Proceeding of the 10th ACM workshop on Web information and data management.Napa Valley, California, USA : ACM, 2008. 1-8. [7] Chen L, Hu Y, Nejdl W. DECK: Detecting Events from Web Click-Through Data [C]. In: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining.IEEE Computer Society, 2008. 123-132. [8] Vidal R, Ma Y, Sastry S. Generalized principal component analysis (GPCA)[C]. In: 2003. [9] Chen L, Roy A. Event detection from Flickr data through wavelet-based spatial analysis[C]. In: ACM, 2009. 523-532.[10] Fox C. A stop list for general text [J]. SIGIR Forum. 90, 24 (1-2): 19-21.[11] Kleinberg J. Bursty and hierarchical structure in streams[J]. Data Mining and Knowledge Discovery. 2003, 7(4): 373-397.[12] 曹雪虹，张宗橙. 信息论与编码[M]. 清华大学出版社, 2004.[13] Keogh E, Ratanamahatana C A. Exact indexing of dynamic time warping[J]. Knowledge and Information Systems. 2005, 7(3): 358-386.[14] Pass G, Chowdhury A, Torgeson C. A picture of search[C]. In: Citeseer, 2006.[15] Bharati A, Chaitanya V, Sangal R, et al. Natural Language Processing[M]. PHI, 2000. 参考文献 [1] 谷歌. 哀悼与团结的曲线[Z]. 2008. [2] 涂承胜，鲁明羽. Web 挖掘研究综述[J]. 计算机工程与应用. 2003, 39(010): 90-93. [3] Fung G P C, Yu J X, Yu P S, et al. Parameter free bursty events detection in text streams [C]. In: Proceedings of the 31st international conference on Very large data bases.Trondheim, Norway : VLDB Endowment, 2005. 181-192. [4] Salton G, Mcgill M J. Introduction to modern information retrieval[M]. McGraw-Hill New York, 1983. [5] Zhao Q, Liu T, Bhowmick S S, et al. Event detection from evolution of click-through data [C]. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining.Philadelphia, PA, USA : ACM, 2006. 484-493. [6] Hu M, Sun A, Lim E. Event detection with common user interests [C]. In: Proceeding of the 10th ACM workshop on Web information and data management.Napa Valley, California, USA : ACM, 2008. 1-8. [7] Chen L, Hu Y, Nejdl W. DECK: Detecting Events from Web Click-Through Data [C]. In: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining.IEEE Computer Society, 2008. 123-132. [8] Vidal R, Ma Y, Sastry S. Generalized principal component analysis (GPCA)[C]. In: 2003. [9] Chen L, R