基于向量空间模型的个性化网页搜索算法研究

卢 洋，石元博

（辽宁石油化工大学 计算机与通信工程学院，辽宁 抚顺 113001）

据 国 际 数 据 公 司 (International Data Corporation, IDC)估计，到2020 年，所有创建、复制和消费的数字数据将达到40 Zb[1]。信息量爆炸式的增长使人们对在海量数据中查找更加符合自己要求的信息更为渴望。完成个性化搜索、提高用户对搜索结果的满意度，是信息检索的主要任务。

在信息检索过程中，网页排序算法尤为重要。作为谷歌的重要网页排序算法，PageRank 算法是由Google 创 始 人B.Sergey 和P.Lawrence 于1998 年 提出的一种网页排名算法[2]。但是，PageRank 算法在其提出过程中并没有考虑用户的个性化需要[3]。因此，对PageRank 算法进行改进，使其能完成个性化搜索成为许多研究者所关注的问题。王冲等[4]构建用户兴趣度因子，同时结合主题相关度因子对网页PageRank 值进行修正。黄贤英等[5]利用用户搜索历史记录网页浏览时间以及同类用户协同过滤这些基于用户兴趣度的主观特性来改进PageRank 算法。Y.Tang 等[6]设计了一种通过用户点击率修正参数的个性化PageRank 算法，从而提高检索结果的排序质量。其他许多研究者也做了类似改进，不过此种改进方法大多偏重用户的网页停留时间、点击率等浏览信息，并不能全面系统地描述用户的兴趣。

本文引入用户画像（User profile）这一在个性化推荐领域常用的方法来建立一个相对完整的用户兴趣度描述模型，提高用户对搜索结果的满意程度。用户画像是基于大数据开展精准营销的核心，王硕慜等[7]提出了一种基于节目标签和用户标签的个性化推荐算法，此算法以电视节目与电视用户具有的特点为基础来建立用户画像。针对本文提出的问题，根据网页与用户兴趣信息、用户搜索内容多为文字的特点，采用向量空间模型(Vector Space Model, VSM)建立用户画像。袁仁进等[8]提出了一种基于VSM 和Bisecting K‐means 聚类的新闻推荐方法，但其仅以用户浏览过的新闻为基础建立用户兴趣模型，并未考虑个人背景等用户信息。为了更加全面地刻画用户兴趣，本文以用户个人信息、网页浏览历史、搜索历史、下载历史等为基础，通过VSM 建立用户画像。王东[9]将用户画像应用于个性化书籍推荐，进一步证明了用户画像可以有效地提升用户满意度，其优点可以弥补其他研究者对个性化PageRank 算法改进的不足，根据这一特点，本文提出了基于VSM 的个性化网页搜索算法。

1 向量空间模型

VSM 是信息检索领域最为经典的计算模型,在该模型中,用特征向量来表示文档中的多维信息,然后通过计算特征向量计算之间相似程度对文档内容进行划分[10]。为了使搜索结果更加准确地贴近用户兴趣，采用K 最近邻(K‐Nearest Neighbors,KNN)算法进一步得出网页与用户兴趣的相关性。

1.1 特征词权重计算

最常用的计算特征词权重的方法为TF‐IDF 算法，TF‐IDF 由两部分组成：词频（TF）指的是某一个特定的词语在该文本中出现的频率；逆文档频率（IDF）,即文本数量与某一个特定的词语在文本集中出现的次数的比值[11]。TF‐IDF 实际上是TF×IDF[12]。

对某文档中的词语，其TF 公式为：

某文档dj中的词语ti，其IDF 公式为：

式中，D 为文件的总数目；mti为包含词语ti的文档数目；f (ti,dj) 为特征词ti在文档里出现的频次；为文档dj中所有字词出现的频次总和。

1.2 相关性计算

KNN 算法是一种主要用于分类以及回归的非参数统计方法[13]。在文本分类中，采用KNN 算法将文档用经过特征加权后的特征项表示成空间向量后，根据相应的方法计算待分类文本的空间向量与已知类别的文本向量间相似程度，得到相似程度最高 的K 个 文 本[10]。

通过上述特征词权重计算方法可以得到用户画像向量空间，根据此向量空间采用常用的余弦相似度计算方法得到K 个最近邻用户画像向量，并通过该K 个用户画像向量得出网页和用户兴趣的相关度[14]。其中ai、bi两个文本余弦相似度计算公式为：

2 算法流程

算法整体过程如图1 所示。首先通过向量空间模型建立用户画像模型U，其次使用KNN 方法计算出网页与用户画像向量之间的关联概率，最后结合PageRank 算 法 得 出 最 终 的PageRank 值PR( p)，根据PageRank 值得出最终网页排序结果。

图1 算法整体过程

步骤1 通过TF‐IDF 算法计算用户兴趣特征词权重wi及网页特征词权重wi'，wi的计算公式为：

对于某个网页，计算其特征词权重时并未涉及到文档总数这一概念，只计算某特征词ti'在该网页文档中的出现的频率，所以用TF 值来表示其特征词权重值wi',即：

步骤2 通过步骤1 可得到用户画像向量空间U 及网页向量p，用户画像向量空间U={u1,u2,…,un}，由用户的各个用户兴趣向量ui组成，ui及网页向量p 表示为：

步骤3 根据向量空间，通过KNN 算法计算网页与用户兴趣的相关性。

首先，通过式（6）计算网页向量和用户画像向量之间的余弦值。

根据余弦值可以得到网页的K 最近邻用户画像向量U'。

然后，根据式(2)计算得出网页向量p 和用户画像向量空间U 之间的关联概率PU( p)，即网页与用户兴趣之间的相关性。

式中，yi为ui所归属的用户画像空间。

步骤4 改进传统PageRank 算法，通过本文算法得到网页最终的PageRank 值PR( p)及最终网页排名。

PageRank 算法的核心思想是通过研究网络的拓扑结构和计算页面的入度，进而确定该页面的排名顺序[15]，其计算公式为：

式中，PR(Ti) 为指向该页面的其他页面Ti的PageRank 值；C(Ti)为页面Ti指向其他页面的链接数；d 为阻尼系数，表示用户随机到达一个页面的概率，通常d=0.85。

综上，网页最终的PageRank 值PR( p)计算公式为：

最后，根据PR( p)值对网页进行排序得到最终网页排序结果。伪代码描述算法过程为：

输入：网页指向关系文档file，网页pi，用户兴趣文档dj

输出：网页排名

（1）计算网页初始排名PR ←PageRank(file)；

（2）计 算 网 页 pi特 征 词 ti' 及 权 重

（5）计算p 和ui的相似度cos( p,ui)，选取k 值；

（6）得出pi与dj的关联概率PU( p)；

（7）输出网页排名PR( p)←PR×PU( p)。

3 实验及结果分析

3.1 实验描述

经由网络爬虫获取的网站初始数据, 存在大量冗余的、有噪音的、不精确的、不完整的或者不一致的数据[16]。为了减少网页噪声对实验结果的影响，采用从中国知网(http://www.cnki.net/)下载的文献作为网页数据源。为了验证本文方法，采用“病毒”这一具有歧义性的词语作为查询关键词，实体名称的歧义性是指一个实体名字可能代表不同的事物或者意义[17]。下载计算机、生物学、医学相关文献30 篇，其中包括“计算机病毒”“生物病毒”“医学病毒”相关文献各10 篇，并根据论文引用关系等信息模拟网页链接关系。以计算机、生物、临床医学3 个专业的3 名学生作为用户，根据其浏览历史、搜索历史、下载历史、个人信息等来建立其用户画像，并通过本文提出的算法得出不同专业学生对“病毒”的搜索结果。

3.2 评价标准

采用的评价标准为P@K[18]，该指标衡量的是用户对整体检索结果的满意度，它反映检索的前K 个结果中被认为是相关的文档比例[19],其表达式为：

式中，Ks为前K 个查询结果中相关网页的个数。

3.3 实验结果

首先，通过传统PageRank 网页排序算法计算出网页排名情况。然后，通过基于向量空间模型的个性化网页搜索算法得出3 个不同专业学生对“病毒”的搜索结果。通过传统算法得出排名前15 位的网页在不同专业学生的搜索结果中排名变化情况。传统PageRank 算法及本文算法搜索结果如图2 所示。为使实验结果更加清晰，根据网页内容对网页进行编码。折线图为通过传统PageRank 算法得出的前15 位网页的排名情况，柱状图为采用本文算法得出的3 个专业学生的搜索结果中这15 个网页的排名情况。

图2 传统PageRank 算法及本文算法的搜索结果

从图2 可以看出，与传统PageRank 算法排名相比，生物专业学生搜索结果中网页编码为生4、生7、生9、生10 的“生物病毒”相关网页排名有所上升，医学专业学生搜索结果中网页编码为医1、医2、医4、医5、医7、医10 的“医学病毒”相关网页排名也有所上升；因为生物、医学学科有较高的相关性，两个专业关于“病毒”研究有很多相似点，所以在生物学专业学生搜索医1、医2、医4、医5、医7、医10，医学专业学生搜索生4、生7、生9、生10 时也会出现排名上升的情况；因为生物学与医学专业与计算机专业相差较远，所以两专业学生搜索“计算机病毒”相关网页排名明显下降。

从图2 还可以看出，在计算机专业学生搜索结果中网页编码为计1、计4、计7、计9、计10 的“计算机病毒”相关网页的排名相较于其在传统网页排序算法结果中的排名有了明显上升，而“生物病毒”与“医学病毒”相关网页排名都有所下降。

本文采用P@5、P@10、P@15、P@20 来衡量网页排序结果前K 个网页中相关文档的比例。表1 列出了以传统PageRank 算法得出的PR 值作为网页排序标准的前K 个网页中各专业相关网页占比，以及针对不同用户以本文算法得出的PR( p)值作为网页排序标准的前K 个网页中相关专业网页占比。

表1 实验结果评价

从表1 可以看出，采用本文算法得到的搜索结果的P@K 值有了明显的提高，即符合用户兴趣的相关网页排名有所上升。这说明在本文的改进算法下，某一网页在具有较高PageRank 值的同时也应与用户画像模型的相关性更高，该网页排名才能靠前，即排名靠前的网页更加符合不同用户的需求。

4 结束语

提出一种基于向量空间模型的个性化网页搜索算法，通过向量空间模型建立用户画像，更加全面地描述用户兴趣信息，再结合传统的PageRank 网页排序算法，完成用户的个性化搜索。实验证明，与传统的PageRank 算法相比，个性化网页搜索算法能够解决传统PageRank 算法没有考虑的用户个性化需要的问题，提高了用户对搜索结果的满意度。另外，由于实验条件限制，实验采用的数据集较小，无法给出更加精确的算法提升效率值，下一步研究过程中应更加贴近实际网络环境，完善实验结果。