第7卷第5期 智能系统学报 Vol.7 No.5 2012年10月 CAAI Transactions on Intelligent Systems 0ct.2012 D0I:10.3969/j.i8sn.1673-4785.201203024 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120925.1009.001.html 面向浏览推荐的网页关键词提取 闫兴龙23，刘奕群23，马少平12，张敏123，茹立云123 (1.清华大学计算机科学与技术系，北京100084；2.清华大学智能技术与系统国家重点实验室，北京100084；3.清 华大学滑华信息科学与技术国家实脸室（筹），北京100084) 摘要：在网页浏览推荐任务中，如何利用网页内容选取合适的推荐关键词是具有挑战性的研究热点，为了实现有 效的关键词推荐方法，利用大规模的真实网络用户浏览行为数据，以及相关提取算法和新词发现算法实现并比较了 基于领域关键词提取技术和基于查询词候选集合的关键词推荐方法.实验结果证明，2种方法都能够有效地表征用 户信息需求，而第1种推荐方法的准确率更高，具有更好的推荐性能， 关键词：浏览推荐：关键词推荐：关键词提取：网页关键词 中图分类号：TP391文献标志码：A文章编号：16734785(2012)05039806 Study on website keyword extraction for browsing recommendation YAN Xinglong23,LIU Yiqun23,MA Shaoping3,ZHANG Min'23,RU Liyun23 (1.Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China;2.State Key Laboratory of Intelligent Technology and Systems,Tsinghua University,Beijing 100084,China;3.Tsinghua National Laboratory for Information Science and Technolo- g双，Tsinghua University,Beijing 10(o084,China） Abstract:It is very challenging when conducting research and it is especially difficult as it pertains to website brow- sing and recommendation system task for selection of suitable keyword usage.This research study will focus on proper use of website browsing and recommendations on how to select keywords for conducting research.The chal- lenge is to leverage user behavior features,as well as develop an effective keywords recommendation content page. The implementation of a comprehensive user browsing data,relevant extraction algorithm and algorithm finding methods for new keywords were examined in the research study.The research study also proposed additional,key- word recommendation methods utilizing large-scale and related algorithm approaches for domain-specific keyword extraction technology and a query keyword candidate set were compared.The experiment results confirm both meth- ods demonstrate that they satisfy users'information demand.However,the keyword recommendation methods show a significant performance improvement in effectiveness.The keyword recommendation method has a higher accuracy and better recommendation performance. Keywords:browsing recommendation;keyword recommendation;keyword extraction;web keywords 自21世纪以来，随着互联网的不断发展，我国个百分点，达到38.3%.越来越多的人通过互联网获 网民人数稳定增加.据中国互联网信息中心测算，截 取各种信息，网络资源正逐渐成为人们获得知识的 至2011年12月，中国网民规模达到5.13亿，全年 主要渠道，截至2011年12月底，中国网页数量为 新增网民5580万，互联网普及率较2010年提升4 866亿个，比2010年同期增长44.3%.从网民数和 网页数来看，现在网民从互联网获取信息存在信息 收稿日期：2012-03-29.网络出版日期：201209-25. 基金项目：国家自然科学基金资助项目(60736044,60903107， 过载的问题.过量的信息呈现在用户面前，用户很难 61073071);高等学校博土学科点专项科研基金资助项目 (20090002120005). 快速地获取自己需要的信息，这样就降低了用户的 通信作者：闫兴龙.E-mail:yan-cinglong@163.com, 信息使用效率.现在用户提高信息使用效率，过滤无
第5期 月兴龙，等：面向浏览推荐的网页关键词提取 ·399· 用信息的主要方法是通过门户网站和搜索引擎.门 的长关键词：第2种方法并不针对网页文本，网页文 户网站和搜索引擎在一定程度上满足了用户信息过 本和书面文本存在一定的差异，并不一定能表征用 滤的需求，但是门户网站和搜索引擎都有其存在的 户的信息需求.本文对这2种方法得到的关键词候 问题，门户网站的主要问题就是网页的过滤是通过 选集进行对比实验，结果表明，基于用户行为信息的 人工的方法进行，这样会费时费力，而且并不能满足 领域关键词提取技术有更好的效果， 每个人的信息需求.搜索引擎是当前非常重要的用 2 户获取信息的途径，其主要的问题有2个方面： 基于领域关键词提取技术的关键词 1)无法提供用户的个性化需求；2)用户需要较为繁 推荐方法 琐地提供需求来获取信息.为了给用户提供更好、便 领域关键词抽取方法的流程如图1所示. 捷和个性化的服务，推荐系统应运而生.推荐系统和 搜索引擎的主要区别在于：1)搜索引擎面向的是所 W山资源 有的用户，提供主流的结果，推荐系统更重要地是研 究用户模型，利用用户的历史记录或者社交网络提 网页标 供用户的个性化服务；2)搜索引擎是用户主导的， 需要用户主动提供和修改查询词，推荐系统是由系 领域文本语料库 统主导用户浏览，能够提供更好的推荐结果.高质量 的推荐系统能够使用户更加依赖该系统，提高用户 <预处理 候选多字集合 的忠诚度 新 1 相关工作 候选多字集合 基于频 当前网页推荐系统基本上可以分为3种方法： 率过滤 基于日志挖掘的推荐方法、基于知识的推荐方法和 <新词发现算法 于左有 基于内容的推荐方法. 熵过滤 1)基于日志挖掘的推荐方法.基于日志挖掘的 候选术语集合 推荐方法26主要是根据用户的Wb访问日志信 背景语 润合度过滤 息，划分出用户的会话，通过模式匹配以及关联规则 料库 TFIDF筛选 等数据挖掘的方法，推荐出用户需要的网页.这种方 搜索引 法很好地利用了用户行为，能够更好地实现个性化 擎过滤 需求，但是由于互联网的扩散性和数据的稀疏性，这 最终领域 术语集金 种方法只能应用于小规模的封闭集合： 候选术语集合 2)基于知识的推荐方法.该方法更多的是利用 知识工程的方法对网页进行分析，在某种程度上可 以看成是一种推理技术.它主要是通过语义Wb的 图1基于Wb资源领域关键词提取方法框架 分析1，得到各个网页之间的关系，从而由系统推 Fig.1 Framework of domain-specific term extraction 荐出网页. based on Web resource 3)基于内容的推荐方法.该方法2,2]是当前网 本文主要通过4步运算，可以得到最终领域关 页推荐系统最主要的方法，它首先提取网页中用户 键词的集合 的信息需求，然后通过一系列的数据挖掘方法得到 1)网页标注.网页标注主要通过归纳总结找到 推荐的对象.所提取的用户信息需求特征主要通过 某个领域的网页的规律和特点，最终总结出基 关键词来表示，关键词的质量是影响这种方法最主 于ul的网页筛选方法.通过该方法可以得到某领 要的因素，当前基于内容的关键词提取主要通过以 域相关的Wb资源.大型新闻门户网站中某领域网 下2种方法实现：①基于已有的分词程序中的词语 页的均是在某个子域名下，而某领域专业网站 集合21；②基于已有的词语词典[91.但是上述2种 下的网页一般为该领域的相关文本。 方法同样存在各自的问题，在第1种方法中，分词程 2)预处理.预处理为新词发现算法处理语料库，对 序中的词语往往很短，无法得到更能反映用户需求 原有的网络文本进行整理，如对网页正文进行抽取，以
·400 智能系统学报 第7卷 及对原有文本不规则内容进行整理，然后对句子进行 字.计算p和01的耦合度公式为 切分，得到多字集合，用于新词发现算法处理。 3)新词发现.新词发现基于上一步得到的候选 C)=(品<A)n()< 多字集合.该方法首先统计候选多字集合中每个候 E(w1))n(E(o)<y). 选多字出现的频率，将低于某频率阈值的多字滤除 如果存在01∈T3(T3为长度为3的候选词集 出候选集合；然后分别计算每个候选多字的左右信 合)，心可分解为w1+P,p为单字.计算p和01的耦 息熵，将低于某熵值的多字滤除。 合度公式为 假设词语w属于候选集，另外，A={a1,a2,…, c）=()<A)n(a(o)< am}和B={b1,b2,…,b.}分别为该词语对应的左右 单字集合，则左右嫡的定义为： ER(w1))∩(E(o)<Y). 式中：y和入为参数阈值.在耦合度计算中，如果交 E,(w）=-1∑c(o,a4)log (0,a) n deA n 集中的每个不等式都成立，则耦合度的值等于1，否 则耦合度为0.如果耦合度的值为1，则认为w不应 n=∑C(0,a); diEA 该为词，将0滤除。 En(o)=-L∑C(0,b)og9 (w,b;) 对于参数的估计，采用最小二乘法实现，首先抽 mbeB 取已过滤候选集中的1000个样本，对样本进行标 m=∑C(o,b:). biEB 注根据抽取出样本的数据，计算出织值和 式中：C(w,a:)和C(w,b:)分别是词语w的左单字 E.(o)或者E(0)值，对已得到的数据进行组合，得 a:和右单字b:出现的次数. 到候选参数集合，通过计算每对候选参数所对应的 对于一个实际存在的词而言，如果它的出现频 样本正确率，将最高正确率的参数对作为估计出的 率较高且左右单字集的频率也很高，则可以通过其 参数.实验表明，该算法可以有效地滤除候选集合中 左信息熵和右信息熵的方法进行过滤。 的非词语，并保留实际存在的词语， 通过上一步的过滤，仍然有部分非词语无法过 以此类推，可以得到更长长度的词进行耦合度 滤，如“化股份”这个词，从语义的角度来讲，该候选 过滤之后，将得到的结果放入搜索引擎进一步过滤， 词中的“股份”应该和“化”分开，之前没有分开的原 最后得到候选关键词集合。 因是由于该词的左信息熵过大，这样依据上一步的 4)TF/DF筛选.TF/DF是一种常用的计算某 规则无法被滤除.根据已有的信息嫡和候选词的出 个词在某篇文档或部分文档集合中重要程度的方 现频率，提出基于递推的耦合度过滤算法，具体算法 法.基于TF/IDF筛选是为了更好地得到与领域相 如下. 关的关键词，通过计算每个候选关键词在文本语料 ①对于字长为3的w,如果存在01∈T2(T2为 库中的TF/DF值，得到每个候选关键词在领域文 长度为2的候选词集合)，w可分解为p+01,P为单 本语料库的重要程度.T℉/DF值的定义如下. 字.计算p和o1的耦合度为 对于文档d,候选关键词0对应的词频及文档 C.(p,0)=（C0<A)n(E(o)< 频度倒数特征的计算公式为： tfidf(d,w）=tf x idf, E(o1)n(E(o)<Y), 如果存在01∈T2(T2为长度为2的候选词集 f=f(w) ∑fo) 合)，0可分解为01+P,卫为单字.计算p和01的耦 合度公式为 11DL+0.01 idf=og∑dl c.）=(品<A0n(E.()< 式中(w)为词o在文档d中出现的次数，∑代o)为 E(0,))n(Er(0)<y). 一篇文档的总词数，ID1为语料库中的文件总数， 式中：y和入为参数阈值.如果耦合度的值等于1， 1∑f代w)1为包含词语0的文件数目.使用类别的TF/ 则认为0不应该为词. DF作为候选词的评价函数，其公式为 ②对于字长为4的0，如果存在01∈T3(T3为 tidf(w)=∑tidf(d,o) 长度为3的候选词集合)，w可分解为p+01,P为单
第5期 闫兴龙，等：面向浏览推荐的网页关键词提取 ·401· 以上述领域关键词提取技术得到的领域关键词 符号，因为一般正常的查询都不存在符号.接下来去 为候选集合，对于每个候选词，提取其在网页中的以 除查询频率过低和过高的查询词，频率过低的查询 下特征：标题中出现的次数、标题中第一次出现的位 词一般不是真实存在的词语，而频率过高的查询词 置、正文中出现的次数和在正文中第一次出现的位 又没有真正的区分度，用户往往只是为了利用搜索 置，并且结合关键词本身的一些特征，如关键词的长 引擎引导到某个网站，如“新浪”、“搜狐”等 度、其在领域关键词提取时的频率以及TF/DF值.依 2)利用领域关键词提取技术中的新词发现算 据这7个特征，利用线性拟合的方法得到各个特征的 法，主要针对查询中小于等于4个字的结果，去除查 参数，根据这些特征的特征值，得到排序较高的前3 询词中非词语，从而提高检索的速度，该算法能很好 位结果作为推荐的关键词，即用户的兴趣点所在 地滤除非词语。 3基于用户查询集合的关键词推荐方法 3)建立基于长查询词和短查询词的映射关系， 一方面，由于查询词的集合过于庞大，为了提高查询 3.1用户查询集合的候选集选取 词匹配的速度，所以采用2级索引的方法.另一方 当前用户在浏览网页时获取所需信息的重要方 面，短查询词反映的含义简单扼要，但是有部分查询 式便是通过搜索引擎提交查询词，所以用户提交的 词无法全面反映用户的意图，所以采用2级索引，能 查询词是反应用户兴趣的重要信息，以查询词为候 更加全面地反映用户的信息需求 选集合，对用户进行关键词推荐，能够很好地表征用 3.2基于用户查询集的关键词推荐方法 户的信息需求 利用上述方法得到的短查询词集合为候选集 基于用户查询词集合的关键词推荐方法，首先 合，对于每个候选词，提取其在网页中的以下特征： 需要对查询词的候选集合进行选取，采用的查询词 标题中出现的次数、标题中第一次出现的位置、正文 选取方法的步骤分为以下3步（如图2所示）. 中出现的次数和在正文中第一次出现的位置，并且 结合查询词本身的一些特征，如查询词的长度、其查 查询日志 询的频率以及T℉/DF值.根据这些特征，利用线性 拟合的方法，得到各个特征的参数值，通过计算得到 <在询问提取 排序靠前的查询候选词. 将得到的排序靠前的短查询词索引下的长查询 查询词候选集合 词作为长查询词候选集合，对于这个候选集合中的 候选词，以对应的短查询词的得分为基础，加入长查 候选多 预处理 了集合 询词的查询频率这个特征.最后根据上述2个特征 值，排序得到推荐的长查询词.从实验的结果可以看 候选多字集 现 出，长查询词往往是与文本内容相关的信息内容 率过滤 4实验 新词 现算法 基于左右 关键词的质量是影响基于内容的网页推荐系统 嫡过滤 候选查询 效果的重要因素，使用计算不同准确率的方法评价 词集合 关键词的推荐方法，准确率P的定义为 背景语 P=推荐出相关关键词的网页数 料库 TFIDF 推荐的网页数 候选术 4.1实验数据 语集合 由于领域关键词提取技术只能提取出单个领域 最终领域 术诰集合 的关键词，因此本文主要针对单个领域的网页进行 推荐，下面以财经领域的网页为例进行实验 图2用户查询词候选集合选取方法 利用用户浏览行为信息，抽取用户在浏览过程 Fig.2 Framework of selecting query candidate 中点击的锚文本信息，以该信息作为提取关键词的 1)预处理.因为查询词中有部分噪音的存在， 背景语料库.锚文本是指由网页制作者编写的，用于 比如标点符号、不成词的查询.首先去除存在的标点 描述对应的超链接网页内容的文本样式.数据是在
402 智能系统学报 第7卷 “用户体验改进计划”中抽取的，数据收集经过了用 成查询词候选集合词汇不足的主要原因有：1)用户 户的同意，并删除了用户的P、用户名等个人信息. 提交的查询词无法涵盖所有关键词；2)由于查询词 查询集合采用某商业搜索引擎18d(2010-1008 集合过大，对长尾查询词进行过滤，导致丢失了部分 10-25)的查询日志，对于锚文本，采用同一时期的用 有用的查询词数据。 户浏览日志信息 5结束语 随机选取10000个网页l,从中提取出财经领 域的网页，并且筛选出不合格的网页，共提取出134 基于领域关键词提取技术的关键词推荐方法可 个与财经相关的网页，利用领域关键词提取方法对 以更好地把握用户的信息需求，但是其有一定的局 相关网页进行推荐，然后通过人工标注，计算出该方 限性，只能在单个领域中发挥较好的作用.而基于查 法的前1位和前3位的准确率。 询词集合的关键词推荐方法可以在各个领域推荐出 基于用户查询集合的关键词推荐方法的实验则 用户需求的信息，虽然在准确率和召回率方面有一 是从10000个l中随机抽取1000个进行推荐，并 定的缺陷，但是其普适性对于推广该方法有很大的 计算相应的前1位和前3位的准确率， 帮助.接下来的工作中，将结合这2种方法的优缺 4.2实验结果及分析 点，得到更高效、准确的关键词推荐方法， 通过标注，得到基于领域关键词提取技术和基 参考文献： 于查询词集合的关键词推荐方法在不同网页下的实 验结果，如表1所示.从实验结果可以看出，这2种 [1]许海玲，吴潇，李晓东，等.互联网推荐系统比较研究 方法得到的关键词推荐都能得到较好的推荐效果， [J].软件学报，2009,20(2)：350-362， 但是基于领域关键词提取技术的关键词推荐效果更 XU Hailing,WU Xiao,LI Xiaodong,et al.Comparison 为显著，具有更高的准确率。 study of intemet recommendation system[J].Joumnal of 表12种方法的实验结果 Software,2009,20(2):350-362. Table 1 Results of two methods [2]张培颖.基于Wb内容和日志挖掘的个性化网页推荐系 统[J].计算机系统应用，2008,17(9)：9-12 方法 Pel Pe3 P ZHANG Peiying.Personalized web page recommendation 基于领域关键词 97.0 91.0 97.0 system based on web content and log mining[J].Computer 提取技术 System and Applications,2008,17(9):9-12. 基于查询集合 76.2 72.3 77.3 [3]YANG Qingyan,FAN Ju,WANG Jianyong,et al.Person- 对实验的结果进行具体的分析，造成基于领域 alizing web page recommendation via collaborative filtering 关键词提取技术推荐错误的主要原因在于不存在相 and topic-aware Markov model C]//IEEE International 对应的候选关键词.例如：网页标题为“主力研究”， Conference on Data Mining.Sydeny,Australia,2010: 1145-1150. 正文为“沪深两市依旧是小盘股全面活跃，大盘股 [4]SUMATHI C P,VALLI R P,SANTHANAM T.Automatic 不涨反跌.虽然不少投资者…”，基于领域关键词 recommendation of web pages in web usage mining[J].In- 提取技术的推荐方法得到的结果为“主力”.通过分 ternational Journal of Computer Science and Engineering, 析，候选集合中没有“主力研究”这个词，但在该网 2010,2(9):3046-3052. 页中，只有“主力研究”能够很好地反映该网页的内 [5]刘强，郭景峰.基于用户访问路径分析的页面推荐模型 容，对于基于查询集合的关键词推荐方法而言，导致 [J].计算机技术与发展，2007,17(1)：151-154. 推荐结果不对的原因主要是某些关键词在查询词中 LIU Qiang,GUO Jingfeng.A web page recommendation 并没有出现，导致候选集合中并没有这些关键词.有 model based on analyzing user access pattern[J].Computer 如下的例子：网页标题为“Q友乐园”，网页正文为 Technology and Development,2007,17(1):151-154. “Q友乐园，专注分享精品头像与个性素材的专业性 [6]WU Y H,CHEN Y C,CHEN A L P.Enabling personal- ized recommendation on the web based on user interests and 网…”，查询词候选集合中，并没有“Q友乐园”这 behaviors[C]//Proceedings of the 11th International Work- 个候选词，所以最终的推荐结果中，只推荐了“乐 shop on Research Issues in Data Engineering.Washington, 园”这个词.由于领域关键词提取技术主要针对单 DC,USA:IEEE Computer Society,2001:17-24 个领域的词进行相应的过滤和提取，所以能够更好 [7]邵华，高凤荣，邢春晓，等.基于VSM的分层网页推荐算 地获取某个领域的关键词.而基于用户查询集合的 法[J].计算机科学，2006,33(11)：85-88,105， 关键词推荐方法则主要依据用户提交的查询词，造 SHAO Hua,GAO Fengrong,XING Chunxiao,et al.A hi-
第5期 闫兴龙，等：面向浏览推荐的网页关键词提取 ·403· erarchical webpage recommendation algorithm based on vec- ZHAO Yinchun,FU Guanyou,ZHU Zhengyu.User inter- tor space model J].Computer Science,2006,33(11): est mining of combining web content and behavior analysis 85-88,105. [J].Computer Engineering,2005,31(12):93-94,198. [8]杨学明，蒋云良.基于语义的自适应个性化网页推荐 作者简介： [J].情报理论与实践，2009,32(3)：9396. 闫兴龙，男，1986年生，硕士研究生。 YANG Xueming,JIANG Yunliang.Based on semantic a- 主要研究方向为信息检索、推荐系统 daptive personalized pages recommendation[J].Information Studies:Theory and Application,2009,32(3):93-96. [9]梁邦勇，李涓子，王克宏.基于语义Wb的网页推荐模型 [J].清华大学学报：自然科学版，2004,44(9)：1272- 1276,1281. LIANG Bangyong,LI Juanzi,WANG Kehong.Web page 刘奕群，男，1981年生，助理研究员， recommendation model for the semantic web[J].Journal of 博士，中国人工智能学会知识工程专委会 Tsinghua University:Science and Technology,2004,44 副秘书长.主要研究方向为网络搜素与性 (9):1272-1276,1281. 能评价、面向搜紫引擎的用户行为分析. [10]袁数，张璟，李军怀基于网页关键词的个性化Wb推 2010年获“钱伟长中文信息处理科学技术 荐算法[J].西安理工大学学报，2007,23(1)：5961. 奖”青年创新一等奖.申请专利13项，其中 YUAN Yan,ZHANG Jing,LI Junhuai.A personal web 6项已获得授权.发表学术论文50余篇，出版教材1部。 recommendation algorithm based on web page key words [J].Joural of Xi'an University of Technology,2007,23 马少平，男，1961年生，教授，博士生 (1):5961. 导师，博土，中国人工智能学会副理事长、 [11]杨学明.基于本体学习的个性化网页推荐[J].情报杂 知识工程专业委员会主任，中国中文信息 志，2009,28(3)：171-174,198. 学会理事、信息检索与内容安全专业委员 YANG Xueming.Personalized web recommending based 会副主任.主要研究方向为智能信息处理， on ontology learning[J].Journal of Intelligence,2009,28 包括模式识别、文本信息检索、图像信息检 (3):171-174,198 索、中文古籍的数字化与检索等.作为项目负责人承担“973” [12]赵银春，付关友，朱征宇.基于Wb浏览内容和行为相 计划、“863”计划、国家自然科学基金和国际合作项目多项.发 结合的用户兴趣挖掘[J].计算机工程，2005,31(12)： 表学术论文70余篇，出版专著2部. 9394,198