《基于领域知识库的信息推荐系统智能文本篇章分析.doc》由会员分享，可在线阅读，更多相关《基于领域知识库的信息推荐系统智能文本篇章分析.doc（33页珍藏版）》请在三一办公上搜索。
1、2013届毕业论文-智能文本篇章分析题目：基于领域知识库的文本信息推荐系统 姓 名： 谷 林 学 号: 0921121010 学 院： 数学科学学院 专 业：信息与计算科学 级 别： 2009 级本科 指导老师： 林 荣 德 时 间： 2013 年5月 摘要推荐系统是为解决Internet上成千上万的信息过载而设计的一种智能的代理系统，它能从Internet上大量的信息中向特定用户自动推荐符合其个人兴趣偏好或需求的信息，从而实现个性化的推荐服务。基于领域知识库的信息推荐即是根据知识点之间的相关性和用户的兴趣来向其推荐用户感兴趣的信息，推荐信息包括个人热点推荐和公共热点推荐。本项目需要解决的主要
2、问题有如下三个方面：第一、建立用户兴趣模型并进行动态更新。建立用户兴趣模型，首先，要收集用户的行为数据，其方式主要有显式和隐式两种；其次，用基于向量空间模型（VSM）来表示用户的个人兴趣；最后，处理用户浏览记录挖掘用户感兴趣的知识点的关键词，通过回溯用户所有关键词的生成算法动态建立用户兴趣知识库。第二、对文本篇章进行智能分析。首先，需要建立领域的知识库，并且人为设定每两个个知识点之间的相似包含关系；其次，从网页HTML源文件中提取文章的标题和正文，用正则表达式匹配的方法获取标题，用分块提取汉字的思路分析提取出文章正文，剔除图片、贴吧、广告等；最后，将提取出的文章进行分词和评分。第三、依据用户个
3、人的兴趣知识库产生推荐信息。产生推荐信息，首先，系统通过搜索引擎自动搜索用户关键词，从搜索结果中提取有效的网页地址；其次，二次访问获得的有效网页，进行文本篇章智能分析，通过评分情况判断是否推荐。测试结果表明，本项目已经能够很好地依据用户的个人兴趣实现个性化的文章信息的推荐，并且通过处理用户浏览过推荐网页来挖掘用户潜在的兴趣，从而实现用户兴趣知识库的动态更新。至此，推荐系统核心功能的框架已经基本搭建完成，为以后扩展至更多的领域的研究打下了坚实的基础。关键词：推荐系统 用户兴趣模型 智能文本篇章分析 推荐信息AbstractRecommendation system is an intellige
4、nt agent system solving thousands of overloading information from the Internet. It can offer plenty of special information automatically to individuals with different demands and interests, and thus making the personalized recommendation service accomplished. Based on domain knowledge, the informati
5、on recommendation could offer users interested messages according to the connection of knowledge points and personal appetites. Recommendation system has two aspects, including the recommendation of personal hotspot and common hotspot. This project will solved three primary problems.Q.1 Users intere
6、sts model and dynamic renovation. To build users interests model, firstly data of users behaviors including explicit aspects and implicit aspects should be collected. And secondly, use vector space model to express the users personal interests. Finally, by exploring the browsing history and searchin
7、g keywords of users interests and backtracking all the keywords of user by generating algorithm Knowledge-base of users interests are dynamically setup.Q.2 Text intelligent analysis. Firstly, building domain knowledge base, and setting up the relationship between two points artificially. Secondly, t
8、he title and text should be extracted from HTML code by using regular expressions, and removing pictures, post bar and advertisements. Lastly, segmenting and scoring the text. Q.3 Providing recommendation information according to Knowledge-base of users interests. First of all, depending on searchin
9、g engines, the system could search users keywords automatically and extract valid web address from the searching results. Additionally, visiting the effective webpages continually and analyze the text intelligently. Finally, it should determine whether the article is worth to recommend to the users
10、by the marking condition.The test results show that the project has been able to make characteristic information recommendation accomplished which depends on individuals interests, and furthermore, users potential interests through the records of browsing history can be found. Therefore, it can real
11、ize dynamically update of users interest knowledge-base. Hereto, the main functions framework of recommendation system has been basically accomplished. It lays a solid foundation for more expansive research fields. Keywords: Recommendation System, User Interest Model , Intelligent Analysis of Text,
12、Recommendation Information目录摘要2Abstract3目录5第一章 概述6第二章 系统框架72.1 基于领域知识库的信息推荐系统的框架72.2 后台分析程序数据处理流程7第三章 用户兴趣模型93.1 用户行为的数据收集93.2 基于向量空间用户兴趣模型的表示93.3 用户兴趣知识库的建立及算法实现10第四章 智能文本篇章分析和信息推荐124.1 领域知识库124.1.1 公共知识库实例124.1.2 个人知识库实例134.2 自动搜索关键词提取有效网页地址算法134.2.1 正则表达式的概念144.2.2 提取有效网页地址算法144.3 网页文本提取思路及算法154.
13、4 文章自动分词技术174.5 计算子概念对某关键词贡献度算法174.6 文章评分和信息推荐184.7 推荐信息的动态更新194.8 用户个人知识点兴趣度变化的勒夏特列原理19第五章 系统测试结果215.1 自动搜索关键词提取有效网页地址及文章评分的结果测试215.1.1 百度搜索“体育”的结果215.1.2 搜索结果的网页源代码225.1.3 分析提取有意义网页地址的结果225.1.4 网页文本提取结果235.1.5 文章分词结果235.1.6 文章最终评分结果以及产生的推荐信息245.2 用户兴趣的挖掘和个人知识库的动态生成245.2.1 读取用户浏览信息245.2.2 挖掘用户兴趣255
14、.2.3 动态生成用户个人关键词之间的包含关系27第六章 总结与展望30致谢32参考文献33第一章 概述网络信息高度发达的今天，推荐系统在网络购物、电影、音乐和新闻等方面得到越来越广泛的研究与应用。推荐系统是为解决Internet上成千上万的信息过载而设计的一种智能的代理系统，它能从Internet上大量的信息中向特定用户自动推荐符合其个人兴趣偏好或需求的信息。推荐系统有非个性化系统和个性化系统之分。由于个性化推荐系统的信息过滤效果及推荐被用户接受的程度远胜于非个性化推荐系统，故本文研究的重点是基于特定知识领域的个性化推荐系统。本文将以目前最受欢迎的体育、读书、游戏、娱乐和汽车五个基本领域为研
15、究对象，设计基于上述五个领域知识库的文章推荐系统，以此为注册用户提供个性化的信息推荐服务。为叙述的方便，以下将基于领域知识库的信息推荐系统简称为推荐系统。主流推荐系统1一般需要经过收集用户行为、建立用户兴趣模型、产生推荐信息三个阶段来实现个性化推荐。其中关键是用户兴趣模型的建立，用户兴趣模型建立的过程是获取和维护与用户兴趣、需求或习惯相关知识的过程，其结果将产生一个表示用户特有背景知识和需求的用户模型。本项目采用人工智能常用的专家系统的思维方式来分析、识别和建立用户兴趣模型。用户兴趣模型是推荐系统产生个性化推荐的主要知识源，由于用户的兴趣是时刻刻变化的，其捕捉用户真实偏好的能力在很大程度上决定
16、了推荐的成功与否。由此可见，动态更新重组用户的兴趣模型是推荐系统一项非常重要的功能模块。此外，为用户推荐的信息是包括个性化信息和公共热点信息。个性化信息是基于已建立的用户兴趣库由系统自动搜索互联网，通过一系列处理评分产生的。公共热点信息是将所用用户的推荐信息汇总筛选出评分靠前的文章进行推荐。本文主要包括三个部分的内容。第一，通过处理用户的点击信息，分析文章，挖掘出用户感兴趣的知识点，然后重新构建用户的兴趣，丰富用户的兴趣以便系统能够更好地提供个性化服务。第二，通过搜索引擎搜索用户个人兴趣所有的关键词，并对搜索结果进行合理的评分，然后存储起来。第三，通过对测试结果分析与比较，对系统不合理和不完善
17、的地方进行改进。第二章 系统框架2.1 基于领域知识库的信息推荐系统的框架如图2-1所示，本系统的框架包括Web推荐系统、数据库和后台分析程序三个部分。Web推荐系统与数据库之间的关系在吕泽水同学的毕业论文中有详细论述，此处不再赘述。本系统的数据库、数据表的设计本以及表之间的逻辑关系在江伟华同学的毕业论文中已有详细说明，此处不再赘述。本文研究的重点在后台分析程序和数据库之间的数据处理流程：首先，后台分析程序读取所有用户的浏览记录，分析后反馈给数据库动态更新每个用户的兴趣。然后，后台分析程序开始读取每个用户的所有关键词进行遍历搜索，分析后将产生的推荐信息存入数据库。数据库后台分析程序Web 推荐
18、系统读取用户个人信息以及推荐信息反馈用户的浏览记录读取所有用户的浏览记录和每个用户的所有关键词存储推荐信息以及动态更新的用户兴趣返回搜索结果搜索用户关键词访问推荐的网页Internet图2-1 基于领域知识库的信息推荐系统的框架图2.2 后台分析程序数据处理流程后台分析程序处理过程分为两个功能模块：从用户浏览记录中挖掘用户兴趣（如图2-2所示）和搜索用户关键词产生推荐信息（如图2-3所示）NY开始读取所有用户信息结束搜索每个用户知识库的关键词提取搜索结果的有效网页地址二次访问网页，提取网页文本文章分词加载个人被关键词下所有的子概念集对整篇文章进行评分计算，并存储统计该子概念在文章中出现的次数，
19、并寻找出该子概念与搜索关键字的路径，计算它的贡献度子概念集中的关键词是否在文章中出现开始读取用户浏览记录结束访问用户浏览过的网页提取网页文本内容文章分词加载公共知识库比对找出文章中出现的公共知识点重新构建个人知识库关键词之间的关系值并存储删除个人知识库关键词原有关键词之间的关系NY个人知识库中是否存在图2-2 从用户浏览记录中挖掘用户兴趣图2-3 搜索用户关键词产生推荐信息第三章 用户兴趣模型3.1 用户行为的数据收集用户行为的数据收集是一个获取与用户特征、偏好或活动相关的信息的过程。这一过程为用户模型的建立提供了必要的数据源，可采用显性和隐性两种方式实现。显性的收集方式要求用户人工提供表示其
20、兴趣偏好的各种数据，这种收集的方式简单、直接，有助于系统准确构建用户的兴趣，但它要求用户确切地知道其个人兴趣并花费相应的时间和精力积极参与，对用户的个人文化水平有较高的要求，不适合低端普通用户，因而不具有广泛性。而且，由于个人隐私原因，这种方式收集到的数据不一定真实和完整。相对于显性的收集方式，隐性的收集方式不需要用户的人工参与，而是由系统在不打扰用户正常活动的情况下自动完成的，如本系统建立用户兴趣模型的数据就源于系统记录了用户浏览Web网页的记录就是有系统隐性获取的，通过对这些信息的挖掘来发现用户可能的兴趣知识。但是由于隐性的收集方式涉及到用户的个人隐私，用户在使用时会有所顾虑，系统的推广使
21、用也不是很全面。因此，为避免上述两种数据收集方式各自的缺点，吸收两种方式的有点，本系统所使用的数据收集方式是显性和隐性两种方式的混合方式。一方面，初次注册的用户可以通过系统提供的定制功能实现初步兴趣树的建立，此处系统的功能介绍在吕泽水同学的毕业论文中有详细论述，此处不再赘述。另一方面，正常使用的用户，系统在充分保障用户隐私的基础通过记录用户的浏览记录来收集用户的行为数据。3.2 基于向量空间用户兴趣模型的表示向量空间模型2是将用户兴趣模型表示成一个n维特征向量（T1,W1）,（T2,W2）（Tn,Wn）。向量的每一维由一组关键词及他们之间的关系值组成，两个关键词之间的关系值是人为设定的相似或包
22、含的程度。在本系统中，数据库对上述模型的表示方式如图3-1所示：fatherchildp图3-1 数据库中用户兴趣模型的表示方式3.3 用户兴趣知识库的建立及算法实现本系统建立用户兴趣知识库的方法有两种。第一种是针对初次注册的用户，当此类用户第一次登陆系统时，系统还未有其兴趣的任何信息，系统给他们推荐的只有公共热点，为实现个性化推荐，用户可以根据系统提供的定制功能来初始化自己的兴趣，也就是上文所说的显性方式。第二种是通过对用户浏览记录的分析，对用户感兴趣的文章进行分词分析，提取该文章中出现在相关领域知识库的敏感词，反馈到用户个人的兴趣知识库，如果用户提取到某些关键词还未出现在个人兴趣知识库中，
23、即认为该关键词也是用户隐性的兴趣，就把该关键词增加到用户的知识库中，并动态更新用户个人知识点之间的包含关系。具体的算法实现将如下伪代码算法3-1：算法3-1 用户所有关键词包含关系的回溯生成算法String Uid;/存放用户编号ArrayList NewPersonalWords;/该动态数组用于存放用户个人所有的关键词编号string father;/父节点关键词编号string child;/子节点关键词编号float p;/存放词之间的包含关系if (NewPersonalWords.Counts1)/只有当关键词条数大于1时才能建立词与词之间的包含关系 foreach (string
24、 a1 in Class)/遍历所有关键词 p = 1; if (a1 != 顶层关键词编号) child = a1; Temp_child =a1; do 以Temp_child为孩子节点查找公共知识库中它的父节点； p = p * 上条关键词之间的p值 Temp_child = Temp_father;while(father!=顶层关键词编号 & father不包含在个人关键词中); InsertPersonalWord_Relation(father,child,p);/插入新的词条之间的关系 此算法能够很好地建立用户个人每个词之间的包含关系，用户个人知识点之间的包含关系虽然是动态生成
25、的，但其依然是基于静态的公共知识库知识点之间的关系生成的。在此，我们默认公共知识库是具有专家级别的涉及所有知识点的根本来源，它收集包含了目前所有词能产生的包含相似关系。第四章 智能文本篇章分析和信息推荐4.1 领域知识库本系统所涉及体育、读书、游戏、娱乐和汽车五个基本领域。领域知识库的建立是一项非常重要而艰巨的任务，我们需要把所有现实世界中隶属于上述领域的事物具体化为一个词条，由于每个领域包罗万象，因此工作量相当大，对建立者的知识面也有非常高的要求，而且建立的结果难免有些疏漏，需要长时间地更新维护，最终走向全面化。系统领域知识库的建立方案在江伟华同学的毕业论文中有详细的介绍，此处只作简要公共知
26、识库和个人知识库的一些实例，方便本文论述的需要。4.1.1 公共知识库实例本文简单地以体育领域作为研究对象，并列举出如图4-1所示的树形结构层次关系，其中箭头的方向表示主概念包含子概念，箭头上的数值表示人为设定的词条之间具体的包含度，椭圆框图表示该词没有子概念。体育篮球网球NBA专题中国足球德甲足球CBA专题国际足球法甲西甲意甲英超巴塞罗那梅西0.80.70.50.50.50.50.70.40.60.50.70.70.50.6图4-1 公共知识库实例4.1.2 个人知识库实例体育NBA专题网球足球国际足球英超梅西0.40.70.50.50.70.15正如第三章中讲，公共知识库是静态的，个人知识
27、库是动态的，个人知识库是建立在公共知识库之上的。形象地说，个人知识库可以看成公共知识库树形结构中抽取出来的一棵子树。在此，如图4-2所示，列举一个简单地用户知识库实例。图4-2 个人知识库实例将图4-2与图4-1作比较，我们可以看出用户知识库是公共知识库的一棵子树。而且个人知识库中体育和NBA专题产生了直接的联系，其关系值的计算方法为：0.8*0.5=0.4。同理，国际足球和梅西产生直接关系值得计算方法为：0.5*0.5*0.6=0.15。这就是第三章3.1节用户兴趣知识库的建立及算法实现的核心思路。4.2 自动搜索关键词提取有效网页地址算法自动搜索关键词产生推荐信息要解决的首要问题就是如何从
28、搜索引擎提供的搜索结果中提取有效的网页链接。常规的思路是首先获取搜索结果页面的网页源文件即HTML代码，然后对一些无效的网页标签，如、等，最后提取出herf=”*”格式的网页地址。该方法虽然简单易行，但是提取出来的效果很不好，得到的网页地址比较粗糙，无法识别那些图片、论坛、视频等网页的地址特征。在此，本系统的后台分析程序采用的方法是正则表达式匹配算法。4.2.1 正则表达式的概念正则表达式3是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。给定一个正则表达式和另一个字符串，我们可以达到如
29、下的目的：1）给定的字符串是否符合正则表达式的过滤逻辑（称作“匹配”）；2） 可以通过正则表达式，从字符串中获取我们想要的特定部分。正则表达式的特点是：1） 灵活性、逻辑性和功能性非常的强；2） 可以迅速地用极简单的方式达到字符串的复杂控制；3） 对于刚接触的人来说，比较晦涩难懂。 4.2.2 提取有效网页地址算法后台分析程序获取网页HTML源文件后，通过给定的正则表达式来匹配获取有效网页地址的算法7如算法4-1所示：算法4-1 提取有效网页地址算法 string htmlCode;/搜索结果的网页HTML代码 ArrayList arrayList;/存放有效的网页地址的动态数组 Strin
30、g strRegex = http:/(w-+.)+w-+(/w- ./?%&=*)?; /匹配有效网页地址特征的正则表达式 Regex regex = new Regex(strRegex, RegexOptions.IgnoreCase); MatchCollection matchCollection = regex.Matches(htmlCode); for (int i = 0; i = matchCollection.Count - 1; i+) bool rep = false; string strNew = matchCollectioni.ToString(); fore
31、ach (string str in arrayList) if (strNew = str) rep = true; break; if (!rep & strNew != & strNew != if (strNew.Contains(.htm) | strNew.Contains(.html) | strNew.Contains(.shtml) arrayList.Add(strNew); return arrayList;4.3 网页文本提取思路及算法网页文本提取的主要思路：后台分析程序自动访问上一节中提取出来的有效的网页地址，抓取网页HTML源码，这里要实现自动判断网页编码的问题，否
32、则有可能发生乱码现象。一般应答的 http头的charset都有声明网页的编码，常见的编码有“GB2312”、“GBK”、“UTF-8”和“ISO-8859-1”，为方便处理和存储，本系统将编码统一转为“GB2312”。但由于Internet上的网页数以亿记，网页的格式未严格达到统一的标准，比如有些http应答的头里的charset和网页的meta里声明的 charset就不一致，这就导致程序无法识别而产生乱码现象。由于此类不符合标准的网也只占少数，故处理过程中会当作无意义的网页而剔除掉。编码问题解决后，首先，从HTML文件中提取文章的标题，此处利用正则表达式4-18实现精确匹配。strReg
33、 = (?*) （式4-1）文章标题提取完后，把网页分割成几大块，取出网页里的div块，td块文字块儿，对取出的文字块排序之前把超链接文字数量和汉字数量比例超过百分之50的div去掉，因为这些都是相关链接或者文字广告，再把汉字少于200的文本块去除，因为一般少于200字的文本块不会是正文，而且即便是正文，一般来说也不会有太多的价值。由于div支持嵌套，所以剩下的文本块，有可能是重复的，一个是另一个的父节点，所以要把最里层的文本块找出来，最里层的文本块是汉字最多的，而其它文本较少的，所以要计算出剩余文本块中汉字占所有字符比例最高的文本块，基本上它就是正文的文本块。当然有的网页正文里也可能还有di
34、v的文本块，这时候可能会判断错误，但只要正文嵌套的div文本块的汉字少于200字，本系统的算法还是能准确提取正文文本块的。紧接着是细节问题的处理，把等标签替换成特殊占位符pbr等，因为最终的正文需要保留段落和回车换行等格式，这一步用正则表达式实现。把最后剩下的文本块的html标签去掉，用正则表达式过滤9。至此，正文提取完毕。具体的实现算法见算法4-2：算法4-2 网页文本提取string input;/网页HTML源文件string reg1 = (p|br);string reg2 = (=*)(=*)?sS*?/1)|(?(?=u4E00-u9FA5uFE30-uFFA0,.);)*2,(
35、?=u4E00-u9FA5uFE30-uFFA0,.);)|(?)|(?)|(?)|(?)|(?+)?sS*?/li)|(? +(s*=+?=?+?)*?)|(?&a-zA-Z+;)|(?#a-z0-96)|(?s+)|(&#d+;);/1、获取网页的所有div标签List list = GetTags(input, div);/2、去除汉字少于200字的divList needToRemove = new List();foreach (string s in list) Regex r = new Regex(u4e00-u9fa5); if (r.Matches(s).Count 200
36、) needToRemove.Add(s); foreach (string s in needToRemove) list.Remove(s); /3、把剩下的div按汉字比例多少倒序排列,list.Sort(CompareDinosByChineseLength);if (list.Count 1) return ;input = listlist.Count - 1;/4、把p和br替换成特殊的占位符pbrinput = new Regex(reg1, RegexOptions.Multiline | RegexOptions.IgnoreCase).Replace(input, $1)
37、;/5、去掉HTML标签，保留汉字input = new Regex(reg2, RegexOptions.Multiline | RegexOptions.IgnoreCase).Replace(input, );/6、把特殊占维护替换成回车和换行input = new Regex(p, RegexOptions.Multiline | RegexOptions.IgnoreCase).Replace(input, rn );input = new Regex(br, RegexOptions.Multiline | RegexOptions.IgnoreCase).Replace(inpu
38、t, rn);return input;4.4 文章自动分词技术对提取出来的文章进行高效地分词是文本篇章分析很重要的一块功能，它的基本思想是采最大匹配分词4，也称作贪心算法。分词过程需要去掉无意词和噪声词。鉴于汉字分词技术已经相当完善，本系统直接调用了一个ShootSeg的C#分词组件5，本系统对该组件的改进之处就在于更新了其基本的分词词典，比原来的分词词典增加了几万条新的网络词汇，以便于更好的对现代文章进行分词。4.5 计算子概念对某关键词贡献度算法如4.1节所讲，知识库中的某关键词下包含了许许多多的子概念10，文章分词完毕后，后台分析程序自动遍历某关键词下所有的子概念，此处称被搜索的关键词
39、为主概念，寻找子概念和主概念之间的一条路径，计算每个子概念对主概念的贡献度，也可形象地理解为通过某一算法计算出子概念和主概念之间直接的包含关系值。数据库词条包含关系存储形式（如表4-1所示）在一定程度上实现了4.1.1节公共知识的树形结构的表达。表4-1 数据库中概念间的存储形式wID2wID1puID主概念子概念关联值用户编号由于知识库不是简单的二叉树，而是n叉树，所以没有现成的算法来实现知识树节点的遍历。但是，受到数据结构中二叉树遍历算法6的启发，本系统设计了一个类似于二叉树前序遍历的算法，见算法4-3：算法4-3 主概念下所有子概念的遍历ArrayList wID;/wID是一个动态数组
40、，并且支持索引，可以随时添加、修改和删除数组元素for (int i = 0; i wID.Count; i+) sqlConn(wIDi.ToString();/查找相邻一层的所有子概念wID.add( 查询到的所有子概念); 上述算法的遍历过程可用以下例子来形象说明，假设图4-3是某用户的一个兴趣树的一部分，1表示主概念，那么遍历算法依次访问的顺序为：123456798101112131415图4-3 假想兴趣树子概念查找的过程也是路径的选择过程，每当查找到最底层的子概念后即可依据4.1.2中个人知识库实例的原理一样计算该子概念与主概念的关系值，这里我们称之为子概念对主概念的贡献度。4.6
41、 文章评分和信息推荐至此，给文章评分前的准备工作还缺少的环节就是统计每个子概念是否出现在文章中，如果出则统计该子概念出现的次数，最后在结合子概念对主概念的贡献度11按照式4-2进行计算，从而的出文章的最终评分。当文章评分大于零时，则该文章对用户来说是有意义的，应该向用户进行推荐。文章最终得分= （式 4-2）后台分析程序中具体算法设计如算法4-4所示：算法4-4 文章评分算法ArrayList TList;/存放每个子概念出现的次数的动态数组ArrayList PList;/存放每个子概念的贡献度的动态数组for (int i = 0; i TList.Count; i+)Convert.ToInt32(TListi);score += Convert.ToInt32(TListi) * Convert.ToSingle(PListi);4.7 推荐信息的动态更新推荐信息产生后，系统将记录下推荐信息产生的时间，当该信息超过3天后，默认为此文章已经失去时
