模式识别_10720938_赵海红.doc

研究生文献阅读课程文献阅读报告题 目: 基于用户行为的WEB内容分析研究 课程名称： 模式识别学 院：计算机科学与工程专 业：计算机科学与技术学 号： 10720938学生姓名： 赵 海 红 基于用户行为的WEB内容分析研究赵海红 10720938 计算机科学与工程摘要：互联网技术的迅猛发展把我们带进了信息爆炸的时代. 海量信息的同时呈现，同时也存在无序性，结构多样性的问题 ,使用户一方面很难从中发现自己感兴趣的部分 , 另一方面也使得大量少人问津的信息成为网络中的“暗信息”, 无法被一般用户获取. 本文力求为上述问题提出一个解决方案，提出了一种基于用户行为的WEB信息内容的分析。利用Google搜索引擎提供的结果，以及用户点击页面内容进这行分析，找到用户的一些兴趣爱好和相同兴趣爱好的群组，最后利用用户的爱好与群组，为用户提供各类服务。关键词: 协同过滤；User ConText；Query ConText；信息熵；信息检索Abstract: The rapid development of Internet technology brought us into the era of information explosion. Vast amounts of information at the same time show, there is also disorder, structural diversity, allowing users from one hard to find parts of interest to the other also makes a lot of information Shaorenwenjin network of "secret information" and can not be general user access. The paper tries to propose a solution to these problems, a WEB based on user behavior analysis of information content. Use Google search engine results, and the user clicks the page content into this line of analysis, to find the user's interests and the same number of group interests, the last use of the user's preferences and groups, to provide users with various services.Key words： collaborative filtering; User ConText; Query ConText; information entropy; information retrieval随着 Internet迅猛发展，接入Internet的服务器数量和World-Wide-Web上的网页的数目都呈现出指数增长的态势。互联网技术的迅速发展使得大量的信息同时呈现在我们面前，例如 ，Netflix 上有数万部电影，Amazon上有数百万本书，Del1icio1.us上面有超过10亿的网页收藏，如此多的信息，别说找到自己感兴趣的部分，即使是全部浏览一遍也是不可能的。传统的搜索算法只能呈现给所有的用户一样的排序结果，无法针对不同用户的兴趣爱好提供相应的服务。信息的爆炸使得信息的利用率反而降低，这种现象被称之为信息超载。个性化服务 ，包括个性化搜索、推荐等，被认为是当前解决信息超载问题最有效的工具之一。推荐问题从根本上说就是代替用户评估它从未看过的产品。这些产品包括书、电影、CD、网页、甚至可以是饭店、音乐、绘画等等，是一个从已知到未知的过程。本文力求为上述问题提出一个解决方案，提出了一种基于用户行为的WEB信息内容的分析。利用Google搜索引擎提供的结果，以及用户点击页面内容进行深入分析，找到用户的一些兴趣爱好和相同兴趣爱好的群组，最后利用用户的爱好与群组，为用户提供各类服务，也即使实现利用其他用户的喜好帮助用户找到自己所喜好的网络资源。本文第一节讨论Query ConText的基本概念，第二节讨论User ConText的基本概念，第三节我们讨论用户之间协同度计算的问题，第四节用户聚类的问题，发现具有类似兴趣爱好的用户群。第五节是我们对实验结果的分析，第六节全文总结展望。第七节是致谢。1 Query ConText1.1 前提概念记录（Record，由Ri表示）记录是搜索结果的基本单位。由标题（Title），片段（Snippet），网页地址（Url）组成。一个搜索结果页面通常包含几条到几百条记录，因此适当的选取有用的记录是十分有必要的。标题（Title，由Ti表示）标题是记录的组成部分，主要是用于鉴别一个页面的手段，标题中往往带有主题概念（Theme Concept）或者搜索关键词（Keyword）。因此很多用户使用标题来辨别他们感兴趣的内容。片段（Web_snippet，由Si表示）片段也是记录的组成之一，主要是向用户展现网页的重点内容，片段中往往也带有主题概念（Theme Concept）或者搜索关键词（Keyword），并且可能是用户感兴趣的内容，本文的片段就是搜索结果中的一条记录。概念（Concept，由C表示）概念是一条记录的最基本元素，通常由文本的关键词（Keyword）表示。但和关键词不同的是，概念是不带状态的词语。比如Contract和Contraction、foot和feet都算同一种概念。概念间权重（表示为wij，即概念对概念的权重） 表示概念 和概念 之间在某种语境下的联系。1.2 Query ConText的概念Qeury ConText(用户搜索的语境),也就是用户在向Google提交查询词的时候，Google所给出的结果，我们通过这样的结果去表示用户所搜的这样的语境，这样就可以区分出不同用户提交查询词结果的相关度，同时Query ConText是基于用户独立的，也就是说只有在查询词相同的情况下Query Qontext才是一样的，即使不同用户输入的关键词相同，其中Query ConText是相同的，也就是说只与查询关键词有关，与具体的用户无关的。现在由以下定义：定义1：(Query ConText，QC) 一个Query ConText是一个二元组QC(C,QR) 其中C=c1,c2,cn),在这里我成为非空概念结合，每个概念ci=<sci,cwi>,其中，sci表示第i个概念的语义，cwi表示这个概念的权值。QR=qr1,qr2,.,qrn是定义一个非空的关系集，其中qri表示概念cp与cq得关联度。 我们可以看到Query ConText不仅描述了各个概念，而且也描述了各个概念的关系，概念的权值表示这个概念对用户查询词的贡献度或者说关联度，各个关系度的大小表示了各个关系的强或者弱，Query ConText可以用一个概念关系图来表示。首先，让我们对Query Context有一个大概的了解，其图例如下：图1 查询词Nokia的Query ConText的图1.3 Query ConText的概念的抽取通过以上的介绍我们已经清楚了什么是概念，但是也存在以下的现实情况的问题。首先，Google给我们提供的信息是大量的，所以在下载这些信息的时候也会花费大量的时间去得到这些结果。其次，我们去把所有的结果去直接单独的去分析也是不太实际的，所以我们就提取Google提供结果的前100条信息，同时只在Web_skippet提取概念(Web_skippet搜索结果的基本单位是记录，包括搜索的题目（Title），片段（Snippet），网站地址（Url），以及一些相关的信息)。通过这样处理所得到的信息就可以实施概念的抽取。 概念抽取的方法是在数据挖掘中频繁集发现思想的启发，当用户把一个查询词提交给Google ，这样就可以给我们网页片段的集合，通过认知科学理论，如果一个概念频繁的出现在查询词的网页片段中，就说明这个概念对这个查询词是重要的，对此我们就用到支持度进行计算一个概念在网页片段中出现的频率其中n代表总共返回的记录条数， 表示一个频繁模式在所有记录中出现的频度。 表示频繁模式中出现过的词的个数，频繁模式的次数可能是1或者大于1的数字。需要说明一点的是用户的搜索词条（主题概念）是不参与此次计算的，也就是忽略了自身的支持度。通过支持度的计算我们得到了每个概念的支持度，但是这样得到的概念集合很大，有些概念意义在这里没有真正体现到，所以在这里我们给出一个支持度的阀值。如果支持度大于阀值，就保留此概念，如何支持度小于阀值就删除此概念，最后得到一个概念的集合C1.4 Query ConText的概念关系的抽取概念的关系也可以从网页片段中挖掘的，一个重要的信息论里面的一个公式pointwise mutual information(PMI)是用来计算概念ci和概念cj的关联度的其中 代表总共返回的记录条数， 表示概念1和概念2共同在一条记录中出现的频率。表示在这个概念的词频。在本文中，2个概念共同出现可能是一下情况中的一种： 1）概念1和概念2一起出现在标题（Title）中。 2）概念1和概念2一起出现在片段（Snippet）中。 3）概念1出现在标题（Title）中，概念2出现在片段（Snippet）中，反之亦然。 根据以上公式，我们将上节中的所有概念两两配对，并计算他们的相似度，如果相似度大于阀值的，则说明他们之间有这一定的联系。小于阀值的可以删除。这样概念的语境向量就生成了。其中也就是上面说到的阀值通过上面的计算我们得到了一个查询词的各个概念以及概念之间的关系，最后我们在Google里面输入Apple后得到的概念以及概念的关系图2 查询词Apple的Query ConText的图2 User ConText2.1 User ConText的概念我们知道用户输入的查询词相同，他们的Query ConText应该是相同的，但是User ConText是不同的，因为每个用户信息查找的过程是不同的，或者感兴趣的信息是不同的，对此我们在这里用Vector Space Model来建立一个User ConText, User ConText是用户点击信息当中的关键词组成的向量2.2 User ConText的表示对此我们在这里用Vector Space Model来建立一个User ConText, User ConText是用户点击信息当中的关键词组成的向量，我们用usc表示一个User ConText 其中w(i,ucs)表示第i个关键词的权值，n表示关键词的个数。3 用户之间协同度的表示3.1 Query ConText的相似性计算我们刚才也看到了Query ConText是由概念跟概念的关系两部分组成，所以计算两个用户的Query ConText的相似性可以把计算任务分为以下俩个子任务 1.计算在Query ConText中概念之间的相似性 2.计算概念之间关系的关联度 其中第一个问题可以consin函数解决，首先概念是由向量表示的，同时所有的Query ConText的维度是相同的，不同的Query ConText的相同位置是表示相同的概念，所以可以用consin函数计算俩个Query ConText概念的相似度： 在公式5中，高的consin值表示俩个Query ConText的概念相似度比较高但是第二个问题就不能简单的用consin函数解决，因为在俩个User ConText中很难发现相同的关系。我们为了解决这样的问题问题，提出了信息熵的概念 其中rwi表示对Concepti的关联度 w(ci,cj)表示概念Concepti与Conceptj的关联度.高的关联度表示这个概念Concepti在Query ConText中跟其他越多概念concepts有关联。低的关联度表示一个不活跃的关系，通过计算每个概念的关系度，我们可以得到一个关系度向量，如下：其中rwi表示概念的关联度，n表示概念的数目这样就可以consin函数计算在Query ConText中关系的相似度了，我们用rdr表示关系的关联度。 到目前为止我们已经计算出了概念的相似度rdc，以及概念之间的关系的关联度rdr.我们可以通过概念的相似度跟概念关系的相关度这个俩个概念来表示Query ConText的相似度，其中表示为as_qc如下：其中 w是一个参数,一般的情况下是0.5.不过我们可以在试验的过程中该表这个参数，观察相关的结果，尽量选取合适的参数值。3.2 User ConText的相似性计算 User ConText是由用户点击过的网络资源的关键字向量表示的，所以我们可以直接用consin公式计算俩个用户的User ConText的相似度3.3 用户之间的协同度表示到此为止，我们已经得到了俩个用户的Query ConText与User ConText的相似度，我们就可以把俩个用户的相似度表示为cd，如下： 其中 w是表示一个参数，sim_uc表示User ConText的相似度，as_qc表示Query ConText的相似度4 根据协同用户进行用户聚类4.1 K_means的聚类我们可以用协同度做距离尺度，用K_means算法去发现在兴趣爱好上有相似性的用户群。算法思想如下：1. 选择几个User ConText作为初始中心点2. 分配所有User ConText到最近的中心点3. 重新计算每个聚类的中心点4. 重复2、3知道中心点不变 通过此聚类算法，我们可以得到具有相同兴趣的用户群组，自此我们就可以把一个用户的相关信息直接推荐给他的协同用户群组、4.2 FCM的聚类FCM算法中m的选择必须与所应用的数据集相关联，没有一个通用的对任何数据都合理的m值。对每个数据集，应该根据数据集本身选择合理的全指数，下面根据上面讨论的全指数m的选择方法给FCM的算法步骤：选定将要聚类的数据集D;l 根据数据集D计算cx，并求出cx的最大特征值maxl 如果max<0.5,则取m<=1/(1-max);如果max>=0.5,则m值无法确定，有用户自己确定 l 根据选定的m用FCM算法对数据集聚类5 实验分析大部分文献只考虑了Uers Context，很少有文献提到还会考虑Query ConText。本文就是解决这样的问题的，让我们一起看看实验的效果吧!实验效果如下表1 试验过程中输入的四组查询关键词图2 试验的效果其中蓝色的方柱表示Query ConText的相关度；红色的方柱表示User ConText的相似度；黄色表示用户之间的协同度。6 结论与展望 通过以上几章的阐述，我们发现基于协同过滤的个性化搜索这个方法对于我们研究和发现用户的兴趣有着比较大的作用。除了用在搜索网页上之外，我们还可以把它用在其他的方面，比如在网上商店中向用户推荐个性化的商品，或者在文献搜索中向用户推荐与他研究有关的文献。 其实如今的网络，个性化的成分已经开始一点一点萌芽。仔细观察的话，会发现很多比较新奇的个性化方法。我们此文中只是尝试了一种全新的方法，希望对今后的网络个性化发展起到推动作用。通过以上的分析，我们可以看到此算法的最大优点是在提高用户系统度精度的提高，也存在着以下几个问题1. 计算量很大。2. User ConText表示欠佳，也就是User Context的建模有一定的问题。3. 聚类算法的改进。4. 本文提出的内容获取方式有待进一步优化，因为本文还是基于概率的内容信息提取。7 致谢 在此向叶老师这个学期的热情的传授知识和引导，使我在这个学期中学到了大量的知识，也在叶老师身上看到了做研究的执着精神，会在我今后的学习和生活中会受到很大的启发的。同时也要谢谢我的导师余洁老师的耐心而有细致的指导，不仅在学习上熏熏引导，而且在生活上也帮助和指导了很多，在此，谢谢余洁老师。References:1. Tao Zhou, Zoltan Kuscsik, Jian-Guo Liu, Matus Medo,Joseph Wakeling, Yi-Cheng Zhang,Solving the apparent diversity-accuracy dilemma of recommender systems。PNAS, 107 (2010) 4511-4515.2. Fang, Ning; Luo, Xiangfeng; Xu, Weimin,Measuring Textual Context Based on Cognitive Principles.Journal of Software Science and Computational Intelligence, Vol. 1, Issue 4. Pages: 61-893. Xinhuai Tang, Xiangfeng Luo，Jie Yu. Personalized Browsing of Topics based on Topic Map within a Domain. Accepted by Chinese Journal of Electronics.4. Jie Yu,Jie Gong,Fangfang Liu,Discovering Collaborative Users based on Query ConText for Web Information seeking附中文参考文献1.刘建国，周涛，汪秉宏，个性化推荐系统的研究进展，自然科学进展，2009年1月，第19卷，1-15页。2.刘建国，周涛，郭强，汪秉宏，个性化推荐系统评价方法综述，复杂系统与复杂性科学，2009年9月，第6卷，1-10页。3.曾春，刑春晓，基于内容过滤的个性化搜索算法，软件学报，2003，13（10）：1952-1961.