（计算机应用技术专业论文）个性化信息分发及概念检索的研究.pdf

巴 摘要 ( 寺+ j 迅遮发展岢敛了信息的爆炸增长，刈海肇的信息，翻l 例他j ( j j t 能。f ，h m 止j 拽j ：j j ： 的信，曾、( w h a ty o l lg e ti sw h a ly 叭l 、v a l l l ) j j e 为 个迫 j ；j 篮m ￥? 儿i 门，叫 ，l 丝一，、 提问校验- 提问加工一 检索) 。 标引建序 图12 信息检索系统逻辑构成示意图 j 统的信息检索模型中，一般是从文档中抽取出特征词向量，然后用向量的，：j 余弦作为文档j 查询的相关度，检索结果按相关度进行排序。为了避免因为选择了小“7 j f | q 金i f 0 关键f i 造成的杏全率降低，有人提出了用同义词对查询进行扩展，比如用户舟 咖算机时，系统会同时查找包含电脑的文档。但是这种做法依然未能从语义 的角度分析用户的查询需求，只有引入知识和自然语言理解技术才能从根本上解决这个 缺陷。l l e w i s9 8 1 向量空间模型并不适合处理短查询，一方面因为短查询提供的信息啦 少，一力胜凶为相l 刷的查i 甸需求常常可以采用不同的表达形式。j a c e k9 8 1 赞从文本，一p 识别出概念，就需要后台知识库的支持。知识的表达和推理一直是几i 斜能例究“m q 重要课题，不同的知识有不同的表示方法，研究知识的表示方法，小r p 址 解决们将以存储在计算机中的问题，更重要的是应该能够方便正确地使用知识。知 u 河以有如下表示方式：单元表示、语义网络、概念从属、框架、脚本和过程表j i 钟。 刈能鬯、榆索处理，目的可行的方法是从关键词检索提升到概念检索的层次，为此人们 义挺了概念蚓络和本体论等知识表示方法。 w o o d s9 7 斯坦福大学的g r u b e r 对本体旧 定义利剑许多同行的认可，目9 本体论是对概念化的精确描述。本体论的最终目标是精确 地表小那些隐含( 或不明确的) 信息，使得它们可以被软件系统重用和共享。 1 2 研究个性化信息分发及概念检索的意义 小史综合j 7 信息检索、知以表示、数据挖掘等多方面的技术，应用于个性化信，融r 及及栅念枪糸、h 具柏妯h l 个方面的意义。 招一帝- j ji ( 1 ) 个性化技术是高质量信息服务的前提 ，恍代的f j ，魁j _ 会甲，训算机科学和技本的进步使得各种形态的数字化信息的数艟 = 刎批以微帙的速度增k 。越来越多的数2 i 采集设备和科学观测仪器每天都在产f 二高j 、 ：目拍j 数删储 j 、，即使人们所面对的各种日常信息，诸如，电影、电视、广播、音乐、报 j j 志等也越来越多地以数字化形式提供，信息高速公路的兴起和【习特网( 1 1 1 t e m e l ) 的普遍使用也划电子信息的快速增长起到了重要的推动作用。信息的多元化、复杂化为 能目、榆索、分类和相关技术领域的研究和发展提出了新的挑战。文本作为信息资源的 1 、j 盟肜式，扼统计在联机存储的信息中，8 0 以 的信息以文本的形式存在。人们迫 剀需嘤能够从人量文本集合中快速、有效地发现知识的工具。 r d ， | ；i 埘i n t e m e i 上如此浩瀚纷繁的信息海洋，人们常常会陷入两种窘迫的境地： 是收剑太多的信息无从选择和消化，即淹没在繁杂的信息中；另一方面是信息迷久， j 、仃jz 二找剑自己真正所需的信息。因此，能够快速高效地获得所需要的信息是每个 4 m ：迫切要求，而个性化技术则是实现高质量信息服务的前提。只有真币识别卅川p 的义膨，能够准确地反映出用户的兴趣变化，并从海量的信息中抽取深层次的知识t 0 之 匹配，4 能真正做到用户所得即所需( w h a ty o ug e ti sw h a ty o uw a n t ) ，让互联| x ) | | 卜 的信息更好地为用户服务。 ( 2j 概念检索将提高信息检索的可用性 亿，窟、榆索址指从火超的文档集合中找剑与查询晴求相关的、恰当数i j 的文档r = c l 信息检索技术产生和发展的推动因素来自于人们划文档资源发现的需求。信息检索系统 | 1 f j 般流程包括：对文档集合建立倒排索引、分析用户查询请求、匹配文档与查询请二r 、 刈垒嘲结果进行排序以及用户相关度反馈。在上述卅i 节中，各检索系统的实现机制各小 棚州，从而产，l 了多种检索模型，例如：仰尔模型、向量空1 t 白j 模型、概率模型等。 “7 il j 鼬q 剐j 二信息检索主要通过搜索引擎来实现，其效果远远不能令人满意。其原 足当l j 勺检索着重于检索文档中显式存储的字诃。检索系统一般返回太多的结果以下j 刖户尤法逐个浏览，而目检索的准确率很低，不能满足用户的需要。 s a l t o n8 3 】传统榆 索方浊中存在如f 问题：( 1 ) 传统的信息检索是基于关键词的匹配，面临着。词多义再 义多洲的问题。( 2 ) 出j i n t e m e t 上包含了半结构化和结构化信息，在检索过程中如们拍 它们父联集成起来也是非常必要的。本文对半( 无) 结构化信息进行了分缴表达，从j 囊 始价，、删z i 司、l i 7 谓和概念，并引入领域本体以支持文本与数据库的信息关联，从 | 典剧1 慨念榆索。 1 3 研究目标及技术路线 4 。啦题的叭7 t n 一允分利h 我们已有的研究成粜的堪础上，吸收当i u 最新的思楚 k 术，奴挥我们亿知以发现、机器学刊、自然语言处理特别中文信息处理等方1 ：i | 的优势川 经验，采用如i 、技术路线。 f 】j 攮十语义的文本主题概念选取 札征选耿是信息检索中的重要步骤，只有选取j 7 真 哺反映文本主题的犏训j i 扎j 一 f 朱m l ：协索的粕j 逆。我们舀一现有语义资源( 知嘲、w o l _ d n e t ) 的基础卜，以多视倒概，2 叫 络模刈( c ( 川n 1 、卧w ( 1 r k v i e w sm o d e ) 作为文档表达和用户兴趣模型，利刚栅0 ，j 1 j i i 、系水捌“- f ，j 息检索的精度。 叫( - 儿迂私称为i _ i o w n e t ) 足个以汉语利蜒滑旧i - 日语所代表n 0 概念为州i j 尘刈缘， 以搦小慨念1 慨念之州以及概念所具有的j 域性之m 的关系为旗本内容的常u 蝴ju _ 1 j | | 旧作为个钏以系统，名剐其实是个网而不是利。它所着力要反 映的足概念的”1 个一n 。仃知例一| l i ! i 述了下列各种关系：| f 位关系、1 i 日义关系、反义火系、刘义火尔、 删”q ：o 体父系、j 禹性拼1 i 关系、材料成品) ：系、施j 经验者笑系1 ：体一”r l ：父系、j j 川qi ：j 坞m 她：助等事十l ：关系、l 其一事中 火系、场所一批仲父系、州川j 计l ：天系、似一j ， 火系、其体恤哭系、事件角色关系、4 | | j | 关关系。 、l9 8 5 印 f = i ，w 0 1 d n e t 作为个知可门：程个j 丌。它利川了个f u 捉似砹：，rj j r f 驯女i = 1 2 、帧式似改和厂泛盹假设。w o l d n e t 的扪述列织包含c o n l p o u n dl 复f h 1 、 曲1 _ a 划、，e l _ b 语动澜) 、c o l l o c a t i o n ( 搭| _ 】己州) 、j ( 1 i o m a 【i c 口1 1 l a s e ( 成语) 、w ( ) r c l l j ) ! 、t ) i d 足坡，i 本的t 、p 位。w o r d n e t 跟剐义闻洲林相似的地方是：它也足以| 州义州q 、 介( s 、m s e t ) 作为基本建构单位进行组织的。同义i l q 集合之m 是以定数 c | 1 勺足系琵“，_ 川火暇的。这螳关系包括上下位关系、整体部分关系、继承关系等。 一：点包榆索应用中，无论是传统的概率统计方法还是综合了向然语i 处圳、人m y 能等坎术，胎船要能抽取出文档的# 题特j i t ，它是进行文本分类等处理的响捉。r f 0 统的 疗浊j 撤拟一“u 堋统计术判别特征硎，使用t f i d f 公为洞l 目加权，剥 二过，步叫繁f ：j l ( “l 【f 妯nm lr 1 譬一) 则用停用洲表滤除。j 二这利- 处理根本不涉及剑语义呲州的。! 一 所以必然遗一k 坡终抽墩n q 特征向量兀法h l 确反映文梢的：t 题内容。 小迁川如r 力法永选取文档的j i 题特征： lt 文分洲和词性标注 2i t m l 文件的1 a g 分析 3 通过奇i 1 | j ，：| j 网来对词日进行概念标t j ? 4 掬造彩视j 割概念删络 5 瞅捌概念嘲络中的能量分却束确定文档的特j _ 1 j 了网络 ( ! j j 彩眦概念例络晌用户兴趣建模 拟念刚络模型闭以用来描述用，o 兴趣利文档的1 ：题，它将兴趣或文档小n q 个郝慨2 【地，义资游建矗：起联系，形成一个网状结构，每个节点表示一个独弋7 = 的撒念，i j f | q 连线衷j 、栅念m j | 内4 ；刷关系。我们赋，每个概念个初始能最，当一个新概念进入l 仃的川铡巾，它将对这个知网产生定的冲击，我们称之为能量传递：能用：传j 凸址；j l t i 。眦in | j 的连线向外传播并不断衰减，连线的阻抗则是因其对应关系的类刑丽j 件。”7 l 能州 f 0 逊剑个1 t 点吲，该节点的能量将得到增强，并将剩下的能罱继续传逊，“令能；l ；个 i 川j j j 。、i j f 个洲慨念 | 以进入网络后，我们就得到了个以概念为一饥量的概念刚络， ：，、慨念所t 柯n 勺能量是不同的，这时我们可以找到哪些概念足鼓酬h 的。 h * 纳：f = j 一带掘衙杂乱无章，为了更清晰地展小菜螳有意义1 1 勺关系模式，刈慨念h 络坝“o 边 r 进步的扩展，构造h i 多视矧概念网络模型( c n v ，c ( c 【 n e l m “k v ic 、v s m o d e l ) 。从概念网络模型中抽取出常用的重要关系，如概念层次火系( 结构) 、同义川链表( 链表结构) 等等。 川j 。必越的获取。般包括两利，方式：用户主动扪述和从用户行为圯求t 7 爿。一 j - z “述是川用些关键词列表或自然语言来拙述他所感兴趣的内霖。用户行为，j 则址从jj 、以胁访问过的文档集合以及防问路行r 爿用户的兴趣特：j j ! ，也称为岑输八 个h 化技术。水史采用的方法是二：者的融合，酋先i 刖、，用自然语高扪述兴趣，住此j 。l 圳l 处、训j j 。f | 0 兴趣模型( 多视图概念网络模型) ，然后列用户行为进行! 冀刊术州j ；# 必 出犊 驰毕j _ ( 笨j 二聚类分析的兴趣发现 c h 挖川、特别灶个性化的w e b 挖掘1 i 撇数训挖拥j 有所小i j ，目曲w e b 挖捌j 、 ：4 孵休t1 i 、，而个忭化w e b 挖掘更多地要求天1 ：用户个体信息的规则。如伺行 1 、i1 ，；彩个川一坊问信息的数掘库中获得每个用户的模式是一个研究问题，显然，将数 圳库 列 j 户分成多个子库再对子库进行挖掘并非可耿之策。r o b e r t9 7 】因此考虑改进j 虬 何的算法，增加定义，在具有多个用户访问信息的数据库中通过一次挖掘获得每个用、 | 0 个体信息，这将涉及改进大多数规则的挖掘算法。 所何客广，行为的电子化( c l i c ks t r e a m ) 使得大量收集每个用户的每一个行为数捌、 ，入，丸错pjj ：为成为j 能。如f | _ j 利用这个机会，从这些“无意义”的繁琐数据中得刊 人家挪行得尚的、有价值的信息和知识是我们厦l 临的问题。用户访问w e b 的模式就是 他浏电删页时的操作模式，包括他的i p 地址、访问时间、停留时倒、浏览的u r l 序例 等。问模式分析包括如下几个处理步骤：数掘收集、数据预处理、模式发现和模式分 w i 。我们主要对用户访问过的文档进行聚类，并利用聚类的结果来重新调整用户兴趣模 j 洲为用厂在丌始时提供的兴趣描述常常是粗略而1 i 完备的，通过对用户访问文档的 做一叫h i 挖 ) l | ，呵以7 f 效地解决这个问题，降低用，、捕述自身兴趣的工作量。 ( 4 ) 兴趣小组的发现 司式信息推荐是根据同一兴趣小组中其他人的浏览行为，将大家都比较有兴趣f j q 史档推荐给用户。协同过滤解决了纯粹基于内容的过滤的一些缺点，它所产生的推荐足 牲，川组的i i 妲，而不仅限于简单的简档匹配。那么，如何找到与当前用户兴趣柏投的 兴趣小组呲? 传统的做法是由发起人对小组进行描述，给出小组的兴趣主题，然后刚 通过浏览选择，决定自己要加入的兴趣小组。这种方法的缺点是用户浏览的工作营太入、 人为的l 刖素川能会造成负面影响。 花个性化信息分发系统中，已经对用户兴趣建模并记录了用户的反馈信息，那么存 这姥数据的基础上，利用一些成熟的聚类算法对用户进行聚类，自动为用户找到合适的 兴趣小组，舀- 进彳信息分发时，我们会划每篇新文档计算它和兴趣小组的相关度，将川 火度i ，0 i 1 时没有被分发给当前用j o 的文档作为该月】户潜在感兴趣的文档推荐给用j ， 从i m 仃效斛决单纯基于内容的信息分发技术中的缺点。 ( 、j 有效的文档表达 义档的表达是信息榆索中的核心问题，往常用的信息检索系统中般采刖向量1 j 恢，p f 为文档的表达方式，缺乏语义上的理解。向量中的每个维是单词或词根，而要也 何效地表达文档的主题，需要将其上升到短语乃至概念的层次。同州为了更快地返川枪 岽纷粜，逊w i 要建立高性能的索引。 迂档表达包括如下处理步骡：文件格式分析、分词和词性标注、扩展短语的发现川 川义钏歧。( i ) 通过分d jh t m l 文件的格式来改善网页内容表达的有效性；( 2 ) 暴九tr j0 q 、训枢刈一j ，t 分【- _ ， ：的杯汁则采用统计_ 方法干舰则方法相结合，给出l - d 性切、 f “j _ 【! | t 、：二j 贷7 、：( 3 ) 扩腱l i n ； 的挖扼 ：( 4 ) 基j ：w o 【d n e 【语义词典进行词义排歧；( 5 ， j j j 懊访川和倒排文件索引方法。 ，本分类是信息检索中的重要基础，我们提出綦r 概念及概念洲联系的文本分炎山 i ；修【f 向葑窄问模型中关于单词m 交性的错误6 u 捉。 p 1 日利学院博j j 学位论文个h 化竹息分发发概念榆索的研究 f ) 栅念拎索模型 “1 人们和网上查找信息时，常常会发现因为使用了不恰当的检索词而导致无法找到 所需| j 信息。琏于关键词匹配的方法只是对查询和文档中的关键词进行了简单的匹配 f m 翠j 慨念的榆索系统则试图改善这利，? 状况。 2 坦实现栅念级的检索，就要解决传统检索方法中的如f 问题：( 1 ) 传统的信息榆索 足尽j 哭键。内匹配，i 曲临着一词多义和一义多词的问题。( 2 ) 由于i n t e m e t 上包含卜i 7 结构化和结构化信息，在检索过程中如何将它们关联集成起来也是非常必要的。 列于笫 个问题，我们对半( 无) 结构化信息进行了分级表达，从原始信息中抽墩 l m 短语和概念，利用了概念以及它们之间的关系，来实现用户查询和文档之拘概 念匹配，从而提高检索系统的易用性和效率。 ( j 。讹i 个问题，l 小丁二知刚和w o r d n e l 都是面向通用领域的，而且常常只提供厂 川纨 佝概念天联，剥二r 特定领域内的大量术语概念无法识别出来，这些专业术语又伟 讹更能反映艾档的主题，为此我们引入领域本体以支持文本与数据库的信息关联。 概念检索模型的处理步骤包括：收集用户的个性化信息并进行兴趣建模，生成用j 、r 特征阼：建立领域本体并提供有效的信息关联机制，利用通用的语义资源和领域本体来 从! r 构化数掘( 文本、网页等) 中抽取出概念，通过关联集成机制将结构化数扼( 数 川j 中- - q 数据j 之刘应关联起来；用户- 的信息需求被转换为多视图概念网络，最后将 乐统一酬7 j 化成信息返旧给j | j | 。 1 4 论文的内容安排 小炙分为旧个部分：个性化信息分发及概念检索总论、个性化信息分发、概念榆索 以及- 、l 验和结论。第一部分( 个性化信息分发及概念检索总论) 中介绍研究背景，引 。要解7 圳q 问题及相应的技术路线，并给出系统原型的概括介绍；第二部分( 个性化信屉j 、 分发) p 重点阐述多视图概念网络模型，同时研究个性化信息分发的两个主要方面：川 必a j e 模型和史档表达。第三部分( 概念检索) 将传统的信息检索提高到概念级的检索， 抛陆：i l 二本体的信息关联技术；第口9 部分( 实验和结论) 中用实验来验证多视图概念例 讲帧“。，旧柏效忆，最 i 给出结论和腱望。 第一章系统婊型 第二章系统原型 随着互联l 删的发展，信息自动分发显得目益重要起来。用户可以通过提交描述个人 兴趣的特征文件来订阅信息分发服务。现在有些简单的分发系统例如邮件列表等，但它 们突的问题是对用户兴趣的描述粒度太粗，用户要么是收不到所需的信息，要么是收 到大量的无关信息。本章提出基于语义资源( 知网、w o r d n e t ) 的个性化信息分发系统 f a i r y 系统，它的核心是多视图概念网络( c o n c e p t n e t w o f k 一e w s ，c n v ) ，用于 支持信息过滤、用户兴趣建模和信息推荐。 z h a j l g0 1 】根据用户特征文件和文档内容来 构造概念网络，描述其中的概念和概念问的联系，并对概念赋以不同权重。通常这些概 念网络都是庞大而繁杂的，为了更清晰地找出那些重要联系，需要从中抽取出若干不刊 的视图。除此之外，通过对用户访问模式的分析和兴趣小组的发现来找出用户的潜在兴 趣，并将协同过滤技术结合到分发模型之中。 2 1 个性化信息分发系统架构 f a i r y 系统架构如图所示。整个系统包括三大部分：用户兴趣建模、文档表达和二： 者的相关度计算。假定用户订阅了信息分发服务，他向服务器发送订阅请求，提供个人 特征信息，包括背景信息和兴趣描述( 用自然语言描述) 。这些原始特征信息被处理后 q 二成刘应的多视图概念网络，从中选耿出主题概念，然后储存到用户特征数据库中。同 时跟踪用户的浏览行为，将用户的所有操作记录到用户操作日志库中，通过访问模式分 析对刚户访问过的文档进行聚类，利用聚类的结果来调整用户特征，从而发现用户的潜 在兴趣。用户的反馈信息也同样被记录下来，通过对这些反馈信息对用户进行聚类，i j 以发现具有相同兴趣的用户小组，从而利用协同信息过滤技术来增强整个信息分发系统 的有效性。 9 新文档进入系统时，首先对这些义档进行h t m l 文件格式分析( 包括u r l 分析、 l i n k 分析和r a g 分析) ，调整这些格式对相应内容的权重影响。然后生成对应的多视 i 纠概念蚓络，从中选取出主题概念，储存到文档特征库中。同时，对所有的文档进行壤 j ：概念的文本分类，对于那些还无法明确表达信息需求的用户来说，通过浏览文档的分 类目慕有助于他们找到自己感兴趣的信息。 。1 用户的特征和文档的特征都被建立起来之后，计算用户特征和文档特征之间的梢 划鼗，然后就呵以将与用户特征最相关的文档分发给用户。我们提出两种基于多视图枞 念网络的相关度计算方法：能量消减算法和基于概念向量的余弦距离方法。前者通过两 个概念网络中的能量传播来实现相关概念的能量消减，并用被消减掉的总能量作为二者 的相关度。后者则是从多视图概念网络中选取出主题概念，表示为概念向量，然后计算 月j 户特征向量和文档特征向量的夹角余弦作为二者的相关度。 多视图概念网络的生成是整个系统的核心，对于任意段文本( 用户兴趣描述或文 档) 篮进行两个阶段的处理：( 1 ) 从词空问到概念空问的变换；( 2 ) 从概念到多视图概念 嘲络的扩展。n “者包括分词及词性标注、词义排歧和扩展短语挖掘，将文本中的词语变 换为刈应的概念：后者则是利用从语义资源中得到的概念间的联系来进行能量传播并以 圳j 纽概念，从而最终生成多视图概念网络。 中国科学院博f ：学位论文个性化信息分发发概念榆索的研究 j x l l e 7 趔1 、h 【旅尖 h j 1 jl n 基本信息 i11卜 1 关粪逮磊蘧1 多视图概念网络生成卜主题概念选取j- 用户特征库 l j 、 r ， 7 1 为日志库广j 户操l 切问模式分析j 。1 ： l * 趣建模 i 、_ l = i 户特征 计算相关度 i 】 浏览 i 一+ 、 文档特征 义档 乒豸- l h t m l 格式分析 削排文仆索引i 一 基丁概念的文本分类 ，f ，一 、 多视幽概念网络生成卜主题概念选取j叫王磊特征鬲 、7 文档表达 图2 1f a i r y 系统架构 图2 2 多视图概念网络的生成 1 0 塑= 雯墨篁堡型一 2 2 系统处理的对象 划j 二个性化信息分发系统来说，处理的主要对象包括两个：用户和文档，同时还要 处理与这二者相关的信息。对于用户对象来说，要记录他的基本信息和兴趣描述，以及 防问系统时的操作序列和向系统返回的反馈。对于文档对象来说，则要将文档的内容和 求源( u r l 地址) 记录下来。因为是面向i n t e m e t 网络环境的研究，所以不仅要识别出 用户本身，还要识别出他的每次会话。实体联系图如下所示： 图23f a i r y 系统的实体联系图 系统的数捌库中共涉及到六张表，现依次介绍如下： 用户基本信息表 表2 1 用户基本信息表 中困利学院博十学位论文个性化信息分发发概念枪索的铆究 7 j ：这张表中，u s e r i d 是主码，是数据库系统自动产生的；l o g i n i d 则是每次用，! l 建 z 会话连接后随机生成的会话标识。 第一章系统原掣 f r o m v a l u et i n y t e x t 兴趣描述初值 t o v a l u et r n y t e x t 兴趣描述终值 表2 6 兴趣变动表 扫这张表中，u s e r i d 和c h a n g e t i m e 共同作主码。 2 。3 系统的功能模块描述 系统主要包括三大部分：用户兴趣建模、文档表达和二者的相关度计算，下面我们 刈子部分的处理进行简要描述。出于前两部分中包含了公共的子模块：多视图概念网络 _ ：成和主题概念选取，为了避免内容重复，将这两个子模块提取出来单独描述。 ( 1 ) 多视图概念网络生成和主题概念选取 多视图概念网络的生成可以划分为两个阶段：( i ) 从词空间到概念空间的变换：( 2 ) 从概念到多视图概念网络的扩展。前者包括三个模块：分词及词性标注、词义排歧和扩 展短语挖掘；后者包括两个模块：能量传播和枢纽概念识别。 分词及词性标注：汉语自动分词是对汉语文本进行自动分析的第一个步骤。现有的 分词算法分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的 分词方法。我们采用的是基于词典的最大双向匹配算法，并应用规则来进行歧义消解和 未登录词识别。词性标注则是将统计方法和规则方法相结合，对于兼类词的标注，先看 能否用规则处理。若能则直接标注词性，否则再利用概率统计方法标注。 词义排歧：词义排歧就是对多义词根据所属上下文确定它在上下文中的意义代码， 我们利用w o r d n e t 来对英文进行词义排歧，排歧后的单词将被赋予唯一的s v n s e t 编号。 将语义空i 训影射为个向量空间，采用聚类方法验证语义空间的语义类中词的分布与用 空问向量表示的词在向量空间中分布的一致性，并给出了基于此空间的词义排歧模型。 扩展短语挖掘：词是表征文本语义的基本单位，为了克服传统信息检索中关于词语 之间无关性的错误前提假设以及基于词典的分词方法中无法识别短语的问题，我们提出 r 扩展短语的一系列定义，利用序列模板挖掘算法来挖掘出扩展短语。 能量传播：在多视图概念网络模型中，我们可以利用现有的语义资源确定概念的数 l | 和彼此的联系，但如何确定每个概念节点的能量值( 权重) 则是一个难题。在借鉴了 参考文献的引用排序和p a g e r a n k 算法以后，我们给出能量传播( e n e r g yt r a n s f e r ) 的前 提假设：概念网络中如果某个概念通过其链入传入的能量总和越大，则该概念节点的能 量僮就越高。这样的假设对如下两种情况都是公平的：某个概念具有很多链入：某个概 念的链入数目少，但这些链入却传递了很高的能量。在能量传播过程中，通过 c o n c e p t r a n k 的多次迭代计算，概念网络的总能量值将收敛到一个稳定值。 椒纽概念识别：在实验中我们发现，某些c o n c e p t r a f l k 很高的概念未必就是我们真 j j ：关注的主题概念，而是用于隐含说明关联概念的重要性，称之为枢纽概念。为了识剐 枢纽概念，我们借鉴了k l e i n b e 唱的h u b a u t i l o r i t y 方法，通过对概念网络进行i 操作和 o 操作的叠代计算，最终会得到收敛的计算结果，从而评价出权威概念和枢纽概念。 卜题概念选取：在生成了多视图概念网络之后，我们将网络中的概念分为原始概念 和派生概念，对它们的能量值乘以不同的系数，然后选取出能量值最高的若干概念作为 l 翘概念向量( 其中过滤掉枢纽概念) 。主题概念向量之问的余弦距离将被用作计算两 个多视j 雪概念网络相关度的方法之。 ( 2 ) 用户兴趣建模 川j 兴趣建模包含二二个主要模块：多视图概念网络生成和主题概念选取、访问模。 分机、兴趣小组聚类。由于第一个模块已经在前面予以阐述，这里主要描述后两个模块。 中困科学院博卜学位论文个州- 化f 齐息分发发概念榆索的研究 多视图概念网络生成和主题概念选取：用户的个人信息包括基本信息和兴趣描述。 摹本信息包括姓名、性别、年龄、地区、专业、电子邮件地址等：兴趣描述分为多条， 每条兴趣描述用户某方面的兴趣如“中国男子足球队的比赛情况”。当用户要修改原 来的个人信息时，会触发对其兴趣模型的自动重建： 访问模式分析：用户的访问模式就是他浏览网页时的操作模式，包括他的i p 地址、 访问时唰、停留时间、浏览的u r l 序列等。访问模式分析包括如下几个处理步骤：数 据收集、数抒 预处理、模式发现和模式分析。用户的所有操作都会被记录下来生成操作 h 卷，在进行预处理后识别出用户和会话，然后对用户访问过的文档进行聚类，并利用 聚类的结果来重新调整用户特征。因为用户在开始时提供的兴趣描述常常是粗略而不完 备的，通过对用户访问文档的模式进行挖掘，可以有效地解决这个问题，降低用户拙述 自身兴趣的工作量。 * 趣小绷聚类：当系统向用户分发了文档摘要列表( 包括标题、摘要及链接) 后， 刷户第一步的动作是点击他感兴趣的文档链接，此时要将这些点击操作记录下来反馈到 服务器，称为点击反馈；然后用户看到原文后会给相关度打分，这些反馈称为评分反馈。 我们利用用户的评分反馈来对用户进行聚类，发现具有相同兴趣的用户小组，从而利用 协同过滤技术作为信息分发的辅助，对每篇新文档计算它和兴趣小组的相关度，将相关 度商而同时没有被分发给当前用户的文档作为该用户潜在感兴趣的文档推荐给用户。 ( 3 ) 文档表达 文档处理包括四个主要模块：h t m l 格式分析、倒排文件索引、多视图概念网络生 成和主题概念选取、基于概念的文本分类。 h t m l 格式分析：包括u r l 分析，链接分析，1 a g 分析。u r l 分析用于分析u r l 1 1 一的描述，例如对于域名删t s i n 曲u ae d u c n ，能够抽取出它属于中国的教育网；进一 步的，对于w w t s i n g h u a e “c “c s x x xh t m l ，能够将它与其它直接链接在清华大学计算 机系h 拘其它蚓页聚类起来。链接分析利用网页内部的各个链接生成网站结构模式，从 斯得到网站的树状层次视图，用于计算网页的权威度和枢纽度。t a g 分析利用网页内的 r a g 文本生成网页结构树，对于某些1 a g 文本( 包括 ， ， ， ， ) 将在后续的内容分析中修改它的权重( 即其在网页中的重要程度) 。 倒排文件索引：信息检索系统般采用倒排文件作为索引机制，在倒排文件中保存 嗣禺对应的文档编号的列表。为了降低索引的空间_ 丌销，并通过减少磁盘访问次数来减 少检索系统的响应时间，就需要对倒排文件进行有效的压缩，我们比较了几种常用的倒 排文件压缩算法，最终选择g o l o m b 编码的b e r n o u l l i 模型来建立倒排文件索引。 基于概念的文本分类：用户有时并没有明确的信息需求，需要提供分类目录供他们 浏览，在浏览的过程中找到感兴趣的信息。基于概念的文本分类通过将文本从词空间变 换到概念空削并最终生成多视图概念网络，提高了分类的精度。在“实验分析”一章中 给出r 基于概念的文本分类系统框架，包括七个阶段：预处理、索引、统计、特征选取、 分类器训练和测试。 ( 4 ) 二者的相关度计算 一一者相关度计算的核心是对多视图概念网络的匹配，可以采用两种方法：是概念 网络的能量消减算法；二是从概念网络中抽取主题概念后用向量空间模型表示，然后叫 算特抓向量的央角余弦。 能遗消减算法：在对两个概念网络进行匹配时，通过能量传播，用源概念网络来消 减目杯概念剐络的能量，并用被消减掉的总能量作为二者的相关度。 概念向量的余弦距离：从多视图概念网络中选取出主题概念，表示为概念向量，然 后计算用户特征向量和文档特征向量的夹角余弦作为二者的相关度。 第二章多视幽_ i l 【念刚络模型 第二部分个性化信息分发 第三章多视图概念网络模型 多视图枞念网络( c o n c e p tn e t w o r k v i e w s ，c n v ) 模型可用于描述用户兴趣或者文 档i 题，概念网络中的节点是独立的概念，边表示两端节点之间的联系，然后根据不同 的联系类型从网络中抽取出不同的视图。每个概念节点会被赋予一个初始的能量值( 通 常是归一化后的项频) 。当新概念要加入到概念网络中时，它会影响原有的网络，称为 能量传播新概念上的能量会沿着边传递到邻近的节点，并在传播的过程中逐渐衰 减。各个边依据其联系类型来决定衰减系数。收到传播过来的能量之后，节点上的能量 值会增加，同时会将剩余的能量进步向下传播。当所有概念都加入到网络中后，就得 到了个概念网络，其中每个节点是具有不同能量值的概念，这样就可以方便地找到高 能量的节点，即主题概念。这些高能量节点和相应的边可用来描述用户兴趣或文档主题。 但一般来说，概念网络常常是繁杂无序的，很难直接发现有用的联系、重要的概念 层次等等，例如上下位关系、同义词集、部分整体关系等等。因此，我们在概念网络 的基础上抽取若干视图，用来显式反映这些联系。这些视图一般是树状结构，包括、卜下 位关系、同义词集和部分整体关系等，如下图所示： 概念网络 视图 图3 1 多视图概念网络模型 例如给定。段文本“如何治疗糖尿病”，其中可以获取两个概念：治疗和糖尿病。 通过金咖知l 列得知：糖尿病是一种疾病，患者是治疗的受事者，同时糖尿病是治疗的内 容，从而派生出疾病和患者两个概念。这些概念和联系构成了概念网络的初始状态，通 过多次能量传播( 参见32 节中的c o n c 叩t r a n k 算法) ，各个节点的能量趋于稳定，将那 些高能节点选取出来作为这段文本的主题概念，即糖尿病、疾病和治疗。 f j 始状态 第_ ：久能肇传播 终1 r 状态 图3 ，2 概念网络示例 1 5 赫姗下丽盟堍莲 p 牛 匮一一 掰劂互簋鬻赫川下丽上鬻 作掬造了慨念网络之后就可以方便地生成多种视图，就象人们从不f 0 视f n 上观察 物从虹清晰地表达那些藿要的概念问联系。 f l 塑f 1 一1 。一 图3 3 视图示例 小j 声包扦两个部分：从词空问到概念空间的变换，从概念到多视陶概念刚络 3 1 从词空间到概念空间 3 1 1 分词和词性标注 汉语i ! 动分词是对汉语文本进行自动分析的第一个步骤。词是最小的、能独 ：巩 n q 、亿盘义的语苦成分。计算机的所有语言知i 识都来自机器词典( 给啦词的各项信，n 1 、 浊j 、 则( 以词性的各种组合方式来摧i 述词的聚合现象) 以及有关训和f u 了n 勺语义一j ： 境、川= ! i 知洲乍。现有的分词算法分为j 大类：挺t 。# 符串匹配的分词力法、o 走j 川t 懈 n j 分i4 ，j 浊刖坫j j 统计的分词方法。 黄昌宁9 7 搦乔谢8 9 一栓虎g j 骆i h fc 7 我们的疗浊址坫丁- 喇嘲1 勺分词方法，涉及到两方而的内容：词典的访问和) 、w 则的处川 ( 1 ) 词典的访问 划r 分洲来说，词典的访问常常是性能的瓶颈之。目6 u 常用的词9 u 访问绱陶“，” i n 甚存储空问丌销 定kj 二： 0 。fb ( f i x e d - l e n g t hs t r i n g s ) 2 8m 熄t l ：手符懈( 1 e r m i n a t e ds t r i n g s ) 2 0m 川叫h 分块( f o u p e n t r yb l o c k i n g ) 18m f胁缀编( n o n tc o d i l l g ) l5 5 m 址小完哭| | f ! 希法( m j l l j m a lp e r f e c th a s h i n g ) 1 3m 农3 1 采用不同数据结构的词典的存储需求( 包含阿力条训1 1 ) i j k 寸：符串 蛾简币的词媳数据结构是用记录数组来存储，包含个字符串字段和两个整数。j 吖女 l 经州序后就可以采用二分法来查找。优点足结构简单，峦找迅迷，缺点悬审问7 f 销人， i ij e z e b e l 2 0 i e z e r 1 e z e i l t1 i e z i a h1 j e z i e l l 。j e z l i a j l l 笫三母多税幽概念例络模型 lj e z o a r 1 【j e z r a l l i a h 1 ij e z r e e l 3 9 l 词目t i 。的磁盘偏移 表32 基于定长字符串的词典 2 终结字符串 将字符串统一存储到一块连续区域内可以减少空间开销，但要另外增加访问指钊字 段。此方法是列定长字符串方法的改进，但依然存在空间丌销大的缺点。 j e z e b 铷e z 蜘e z 砸t i e z i a h j e z i e l | -ji j i2 0 | 3 | 1 h 1 l 1 tj 的磁盘偏移词目t 的偏移 表33 基于终结字符串的词典 3 * q 词目分块 为了减少定长字符串方法中的指针数目，可以对字符串分块存储( 四个词目为一块) 每个词目前增加一个字节的长度字段。同时用块指针表代替原来的字符串指针。 缺点：增加了查找处理的复杂度( 但对查找性能影响不大) 。 k k + 】 同 ft = 4 k 的地址 2 0 3 1 l 1 l 4 k 4 k + l 4 k + 2 4 k + 3 4 f k + 1 1 i 。的磁盘偏移 表34 基于四词且分块的词典 中闺科学院博 j 学位论义个h 化信息分发发j 【念榆索的f 】| 究 4b u 缀编忙j 订缀编码是一种很有效的数掘结构，主要思想是基于“词典中的词目与前序词目。瞄 常鼠_ 昨帅u 缀”。在每个词目中包含了两个整数字段：第一个字段表明它与前序洲li 州州f j 0 缀的长度，第：二个字段表明其剩余部分( 后缀) 的长度。然后包含后缀字符斗 。 洲项完全前缀编码部分“3 i n 4 ”的缀编码 7 i e z e b e j ) j e z e r 7 j e z e r i t 6 j e z i a l l 6 e z i e l 7 。j e z i a h o 1 e z o a r 9 j e z r a 1 i a h 3 4 e b e i 4 1 r 5 2 i t 3 ，3 ，i a h 4 ，2 ，e i 3 ，4 ，l i a h 3 ，3 ，o a r 3 ，6 ，r a l l i a l l 7 j e z e b e i 4 1 r 5 2 i t 3 ，i a l l ，6 j e z i e l 3 ，4 ，l i a h 3 3 o a r 3 3 oa 1 7 、l e z r e e l4 ，3 ，e e j，7 j e z r e e l 1 1j e z l e e l i t e s 7 ，4 ，i t e s7 ，4 ，i t e s 6 j i b s a ml ，5 ，i b s a m1 ，5 ，i b s a m ! ji i ! 箜皇! ：! ! ! ! 塑!；! ! ! ! 业垒 表3 5 基于前缀编码的词典 存宠令前缀编码数据结构中无法使用二分法进行查找，改进方法是部分“3 一i n 4 ”f m 缀编码，对酬典分块存储，每块包含四个词目，块中第一个词目的存储不采用6 口缀编码 乃。法，这样就可以采用二分法查找。 5 最小完炎哈希法 吩希函数h 的定义：定义域l = 。f f l i n 专值域( o h ( x ，) m 一1 。 完炎哈希函数：h ( x ，) = h ( x ) 的充分必要条件是一。( 即一对映射关系) 最小完荚哈希函数( m p h f ) ：m = n 。 仙j 芋哈希函数( 0 p m p h f ) ：如果x i x l ，贝0h ( x i ) h ( x i ) 。 最小完美哈希函数图例：( a ) 词目和哈希函数，( b ) 函数g a )词 jth i ( t )h 2 ( t )h ( t )b )( x g ( x ) i e z c b e l59o0 i e z c r571】 i e z e m1o 1 22 2 i e z i a h6l o33 i e z 【e i13744 i e z “a hi3 1 15 5 j e z o a r 426 6 i e z r a l l i a ho377 j e z l e e l 638 8 j e z r e e l i t e s8499 i e b s a n l 91 41 0 l o j i d l a l ) h 311 1 1 1 1 2 13 1 4 表3 6 基于最小完美哈希法的词典 ”算公式： a ( f ) = g ( h 1 ( r ) ) + 。g ( 2 ( f ) ) 1 8 o 4 o 7 6 o ，3 o 2 2 o 3 塑三! 墨丝型塑垒型堑堡型一一 向( z ) ，1 f 、 姒d 3 隆【f 】州m o 阳 其中t 【i 是词目t 中的第i 个字符。 先奖哈乔函数的生成算法： 】选择m 的值 2 对j 1l i 1 n a x 。il ，随机选取权重i ( i 】和u2 i 】，其中l 是被哈希的字符串集合 1 t 1 足字符串t 的长度。 3 _ 二成匿lg = ( v ，e ) ，其l 斗 v = 】，m ) e = ( h 【( t ) ，h 2 ( t ) ) t l ) 4 使川下面的无环检查和映射赋值算法来计算g 。 5 如果算法返回一个错误，则返回到步骤2 。 6 返旧。i ，( 。2 和g 。 尤j 4 、检金和映射赋值算法： 为了标记一个无环图， 1 f o r v v ， s el g 【v 一u n k n o w n 2f o rv ev ，g v = u n k n o w nt h e n l a b e l f r ( ) m ( v ，o ) 其- pl 。n ) 。仆r o m ( v ，c ) 定义如卜： i fg 【v u n k n ( ) w nt h e n i f g 【v c t h e n r e t u r nw i t hf a “u r e 图中存在环 c 1 】e r e t u r n 此节点己被访问过。 2s e tg v 一c 3f o ru a d j a c e n o ( y ) ， 6 基刁磁型：的词典存储 将词典划分为4 k 大小的块，仅在内存中驻留各块的首词目指针，当需要块内，i 哟 川j 侧入相应的块。剥于不超过5 0 个词目的查询来说，响应时间小于1 秒( 假设每次 f f i ：盘访问需要1 0 毫秒) 。但在创建倒排索引时必须将闫典驻留内存( 例如使用完美哈币 r _ 数) ，否则刈u 5 g 人小的文本将需要数月的利涮j 一j 以创建索引，显然不n r 忍，曼。 磊、合比较j 7 以 力法之后，可以发现部分前缀编弼方法的存储丌销小( 比传统 人约销省4 0 的空恻 销) ，时间丌销也很，j 、( 允询二分法查找) ，在实现e 最小，i ：笑 哈希浪简单得多，倒此我们选择了1 j 缀编码作为词典的存储和访问结构。 mdm 、，l， l【 l j ，0l 中旧利学院博l 学位论史个性化信息分发成概念榆索的