基于查询分类的个性化检索系统研究

搜索引擎是网络用户最常用的网络服务之一。用户通过向搜索引擎提交查询（Query）的方式获取与该查询相关的信息。由于用户的背景各不相同，即使他们输入完全相同的查询语句，其需求也可能是不同的。传统的搜索引擎并没有针对用户来设计查询的相关度算法，因此难以给出令每个用户满意的结果。目前人们提出通过个性化检索技术来解决这一难题。而查询分类是个性化检索中最具挑战性的关键技术之一。 本文通过对大规模真实中文查询语句的分析，提出使用VASE特征词的方法对查询所属的主题进行分类，并采用规则的方法对用户的意图进行自动识别，实验结果表明该方法能够有效地对查询主题和用户意图进行识别。 随后本文探讨了如何使用查询分类的结果进行个性化检索。基于用户的点击信息和查询类别，分别采用对查询结果进行过滤、次级关键词的提取以及对不同的查询意图采用不同的排序算法等三种策略对检索的结果进行改进。实验结果表明这些方法都取得了良好的效果。 最后，本文设计并实现了客户端个性化检索工具，以Firefox浏览器插件的形式，对用户输入的查询进行分类，并基于百度的搜索结果并为用户提供个性化检索的功能。

增量式个性化推荐系统研究

互联网个性化推荐系统(Internet personal recommender systems)是根据用户的兴趣推荐最相关的互联网信息给用户的系统。在网上信息过载矛盾越来越严重、用户信息检索的个性化需求日益增强的现状下，推荐系统已经在搜索引擎、电子商务、网上社区等互联网关键应用中起到了关键性的作用，并且越来越受到重视。 然而，在大型网站上部署一个成熟推荐系统的代价依然很大，需要大量的计算和存储资源，推荐的准确性也依然有很大提升空间和需求，这就为推荐系统的研究提供了很多挑战。在这些挑战中推荐算法的准确性和可扩展性一直是该领域最为关注的两个问题，所谓推荐的准确性是指推荐的信息中用户真正感兴趣的比例，而可扩展性指的是系统能否在可容忍的时间和空间复杂度内处理海量的数据。如何在提高算法推荐准确性的同时增强算法的可扩展性是推荐系统改进的主要研究目标。然而，目前学术界的研究更多侧重于提高推荐算法的准确性，而对于可扩展性，很多准确性很高的算法由于需要比较复杂的计算，处理大规模动态数据的能力往往比较有限，并且它们的评测实验中并没有将可扩展性纳入到评价范畴，导致这些算法目前还很难在工业界大规模应用。 本论文的研究试图解决这一问题。通过在推荐算法中借鉴增量学习(Incremental learning)的思想，即考虑最新的训练数据来更新原有的机器学习模型，不需要或仅需要参考部分旧的训练数据，相对于使用全部数据也即批量的处理方式，增量式改进可以大大降低模型更新的复杂度，从而可以大幅度提高推荐算法在遇到新的训练数据时推荐模型更新的效率，降低计算代价，使得推荐模型的更新可以更加及时，进而提高推荐结果的准确性。具体来说，我们在提出了两种新的增量式协同过滤算法的同时，采用增量式学习的方法对目前准确性最好的若干推荐算法进行加速，特别是提高这些算法面对新的训练数据的更新模型的速度和效率，从而为这些算法的大规模的应用提供了可能。另一方面，新的训练数据包含了最新的用户兴趣，因此相对于旧的训练数据，算法在做更新时应给予更高的权重，这样才能做到推荐的结果在考虑到用户长期兴趣的同时，特别考虑用户近期的兴趣，从而使得推荐结果更加准确。这两方面归纳起来，我们旨在通过增量式学习使得推荐算法在更新时更加高效和精确，真正适用于互联网上海量数据的推荐，同时对其他增量式推荐系统方面的研究也具有借鉴意义。我们的改进工作主要包括以下几个方面： 基于主题模型的增量式推荐算法。主题模型，特别是概率隐含主题模型(PLSA)是一种广泛应用于推荐系统的主流方法，在文本推荐、图像推荐以及协同过滤推荐领域都有着很好的推荐效果。目前制约PLSA算法取得更大成功的重要因素就是PLSA算法更新的复杂度过高，使得学习模型的更新只能做批量式处理，这样就导致推荐的时效性不高，也没有办法体现用户的最新的兴趣和整体的最新动态。我们提出了一种增量式学习方法，可以应用于文本分析领域和协同过滤领域，当有新的训练数据到来时，对于基于文本的推荐，增量式更新方法仅寻找最相关的用户和文本以及涉及到的单词进行主题分布的更新，并给予新的文本以更高权重；对于协同过滤，我们的方法仅对当前用户所评分过得物品以及当前物品所涉及的用户进行更新，大大降低了更新的运算复杂度，提高了新数据在推荐算法中所占的权重，使得推荐更加准确、及时。我们的算法在天涯问答文本数据集上和MovieLens电影推荐数据集、Last.FM歌曲推荐数据集、豆瓣图书推荐数据集等协同过滤数据集上取得了很好的效果。 基于蚁群算法(Ant colony algorithm)的协同过滤推荐方法。受到群体智能(Swarm intelligence)算法的启发，我们提出了一种类似于蚁群算法的协同过滤推荐方法——Ant Collaborative Filtering，初始化阶段该方法给予每个用户或一组用户以全局唯一的单位数量的信息素，当用户对物品评分或者用户表示对该物品感兴趣时，用户所携带的信息素相应的传播到该物品上，同时该物品上已有的信息素（初始化为0）也会相应的传播给该用户；此外，用户和物品所携带的信息素会随着时间的推移有一定速率的挥发，通过挥发机制，可以在推荐时更重视用户近期的兴趣；推荐阶段，按照用户和物品所携带的信息素的种类和数量，我们可以得到相应的相似度，进而通过经典的相似度比较的方法来进行推荐。基于蚁群的协同过滤方法的优势在于可以有效的降低训练数据中的稀疏性，并且推荐算法可以实时的进行更新和推荐，同时考虑了用户兴趣随着时间的变化。我们在MovieLens电影评分、豆瓣书籍推荐、Last.FM音乐推荐数据集上验证了我们的方法。最后，我们建立了一个互联网新闻推荐系统，该系统以Firefox插件形式实现，自动采集用户浏览兴趣和偏好，后端使用不同的推荐算法推荐用户感兴趣的新闻给用户。 基于联合聚类(Co-clustering)的两阶段协同过滤方法。聚类(Clustering)是一种缩小数据规模、降低数据稀疏性的有效方法。对于庞大而稀疏的协同过滤训练数据来说，聚类是一种很自然事实上也的确很有效的预处理方法。因此我们提出了一种两阶段协同过滤框架：首先通过我们提出的一种联合聚类的方法，将原始评分矩阵分解成很多维度很小的块，每一块里面包含相似的用户对相似的物品的评分，然后通过矩阵拟合的方法（我们使用了非负矩阵分解NMF和主题模型PLSA）来对这些小块中的未知评分进行预测。当用户新增了对于某物品的一条评分，我们仅需要更新该用户或该物品所处的数据块进行重新评分预估，大大加快了评分预估的速度。我们在MovieLens电影评分数据集上验证了该算法的效果。 本文的研究成果不仅可以直接应用于大型推荐系统中，而且对于增量式推荐系统的后续研究也具有一定的指导意义。首先基于PLSA的增量式推荐算法对于其他基于图模型的推荐系统具有借鉴价值，其次蚁群推荐算法为一类新的、基于群体智能(Swarm intellignece)的协同过滤算法做出了有价值的探索，最后我们提出的两阶段协同过滤框架对于提高推荐算法的可扩展性和更新效率提出了一个通用的有效解决方案。 推荐系统是一个无止尽的优化的过程，除了推荐精度的不断提高之外，推荐算法的性能随着互联网上数据量的增加也需要进一步提高，增量式学习无疑是提高推荐算法更新速度最重要的方法，本文的研究为这一方向提供了参考。

Web服务器端藏文字符串长度的近似算法

藏文属于拼音文字,她的书写规则与英语书写规则一样是从左向右,从上到下,但每个单词之间没有空格,只用音节符把每个单词给分隔开。根据藏文文法,藏文的换行只能发生在音节符、单垂符,双垂符与空格的后面。目前主流浏览器(如Firefox,Netscape等)都不能处理藏文的这一断行特性,所以这些浏览器无法正常显示藏文文本,如Firefox将整个一段没有空格文本当作一个单词,造成在屏幕的右边无法换行。结果是用户必须拖动鼠标来浏览整篇文章,给用户带来了很大的麻烦。又由于藏文中大部分的拼音字母的宽度是不同的,在编写HTML文档时候也无法根据藏文字符串的多少来决定字符串的长度。该算法将采用了一个粗略的方法得到一个字符串长度的近似值,再根据行宽的限制在字符串的适当的位置找到一个可断行点进行断行。虽然得到的是近似值,但是基本上解决了主流浏览器无法处理藏文排版的问题。