一种基于用户兴趣的个性化搜索实现方法

摘要

本发明公开了一种基于用户兴趣剖像实现个性化搜索的方法，首先，从用户的浏览器页面缓存中抽取Web页面，根据页面中包含的超链接关系进行聚类，获取的聚类代表用户的一种兴趣，聚类包含的页面数量与页面总数之比代表兴趣的浓厚程度；然后，提出一种新的用户兴趣剖像表示方法，并在用户兴趣页面聚类中，采用基于忠诚度的加权关联规则方法，挖掘聚类中的关联规则词条作为用户兴趣剖像的代表；最后，将获取的用户兴趣剖像推导用户搜索请求的兴趣，通过与用户交互确认，扩展用户的搜索请求提交给通用搜索引擎，扩展后搜索请求能够将搜索结果聚焦在用户的兴趣范围内，实现了用户的个性化搜索。该方法可以用于浏览互联网的浏览器，帮助用户改善搜索体验。

说明书

技术领域

本发明涉及一种互联网上实现个性化搜索的技术，特别是一种挖掘和表示用户的 兴趣剖像实现基于用户兴趣的个性化搜索实现方法。

背景技术

对于目前基于关键字匹配的搜索引擎，大多数的用户缺乏改善搜索结果的经验， 不能精确的表示自己想要的信息。而且搜索引擎用户往往只给出相对较少的查询词（据 统计超过70%的搜索词只有一个，90%不超过3个），通过短短的几个词，搜索引擎也 无法获知用户的具体需求，搜索引擎会返回的成千上万的结果页面，用户根本就无法 逐一浏览，通常只是查看前几页的搜索结果。大量的含有用户搜索关键字的页面可能 与用户的兴趣毫无关系。因此对于用户来说，找个适合自己的有用的信息是一件相当 费时、费力的事情。

如何能够从用户方获取更多的关于用户的兴趣信息，进而改善用户的搜索是个性 化搜索领域需要解决的课题，其中，用户兴趣数据的获取和用户兴趣剖像的表示是个 性化搜索研究领域中关键的问题。在对用户兴趣剖像建模方面主要的方法有兴趣特征 向量，本体结构化等。兴趣特征向量将用户兴趣剖像信息表达为一组带权重的术语集 合，权重大小表示用户的兴趣程度，因为采用向量空间模型表示，这种表达方式的好 处是与目前很多的信息检索系统可以很好的匹配，在实现个性搜索的过程中，二维兴 趣特征词条通常用于搜索结果的过滤和排序，并没有提高搜索的精度。

从用户兴趣数据来源方式上，主要有(1)用户浏览器的历史页面、收藏和Cache的 数据，(2)搜索引擎的日志信息，(3)用户指定的文档或兴趣，(4)用户的搜索反馈和评价。 其中，Cui和Liu等人提出从搜索引擎的搜索日志中挖掘用户的搜索信息，以获得普遍 用户的共同偏好。存在的问题是用户的搜索记录并不能完全代表个别用户的偏好信息。 通过与用户交互的方式，事先要求用户指定自己的兴趣偏好特征，或者用户指定自己 的喜好的页面，通过挖掘这些页面得到用户的偏好特征。

从用户兴趣剖像表示方面，主要有二维兴趣特征词条、决策树、兴趣生成树以及 本体表示等方法。二维兴趣特征词条将用户的剖像信息表达为一组带权重的术语，权 重大小表示用户的兴趣程度，这种表达方式的好处是与目前很多的信息检索系统可以 很好的匹配，因为它们大部分仍然是基于向量空间模型，大部分的研究都是基于这种 表示方式。本体（ontology）技术的用户剖像是最近热门研究方向的内容，本体正是描 述语义Web中语义知识的建模手段，它形式化定义了领域内共同认可的知识，是语义 Web体系中的核心。把本体直接应用到目前的检索方式上，仍然存在如果结合完全不 同的两种表达体系的问题。

基于代理的个性化搜索，建立专用的个性化代理系统，利用兴趣剖像过滤搜索结 果。基于WWW缓冲技术的实时二维兴趣模型，通过粗集理论和关联规则深入挖掘兴 趣之间的关联关系，实时二维兴趣模型充分考虑了用户兴趣之间的递推关系。

Letizia系统是由MIT开发的，具有智能导航功能。它采用了一种基于行为的用户 兴趣建模方法，即通过跟踪用户的浏览行为推测用户兴趣,建立用户兴趣模型。例如该 系统可自动从用户当前页面出发，对所有超链接指向的链宿页面进行宽度优先搜索， 在分析页面内容后与用户兴趣模型比较，进而找出用户可能感兴趣的页面,在单独的窗 口中显示推荐给用户的URL列表。

LIRA系统是由Stanford开发的，具有主动服务功能的系统。在用户网络浏览过 程中选择与用户兴趣模型相似度高的页面提交给用户，并要求用户给出明确的评估值, 然后根据用户提供的相关反馈结果修改搜索和选择策略，调整用户兴趣模型。该系统 的特点在于利用了启发式搜索算法，对搜索规模进行了限制，从而兼顾了效率。

WebMate系统是一个帮助用户有效地浏览和搜索Web的代理。从Web信息检索的 多个方面改善，首先，使用了多个TFIDF向量跟踪用户的兴趣领域，这些领域都是 WebMate自动学习的。其次，WebMate使用了Trigger Pair Model自动提取关键词改善 页面搜索。再次，搜索过程中，用户可以为搜索提供多个页面作为相似/相关性的引导。

国内目前也有研究个性化搜索的专利，比如一种基于用户停留时间分析的个性化 网页搜索排序方法（申请号201110194078.8）依据用户阅读页面的时间推测出感兴趣 的概念词，进一步基于概念词来预测搜索结果中每个页面的个性化阅读兴趣。基于链 接分析的个性化搜索引擎方法（申请号200510050198.5）通过知识网络模型描述用户 兴趣，建立多态链接网络记录网络节点之间链接的不同类别，进而在此基础上展开链 接分析得到搜索结果。

发明内容

发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种基于用 户兴趣的个性化搜索实现方法，通过实时获取浏览器缓存的页面，能够动态反映用户 兴趣的变化，利用关联规则词条作为用户兴趣特征，将用户的搜索限定在特定兴趣的 页面范围，达成更加精确的搜索结果。

为了解决上述技术问题，本发明提出了一种用户兴趣剖像模型的表达方法和两阶 段策略的个性化搜索方案。

本发明所述的一种用户兴趣剖像模型由三部分组成，第一部分为一组浏览页面的 聚类，每一个聚类代表用户的一种兴趣，称为兴趣聚类，其包含的页面数量与页面总 数之比作为用户兴趣的程度，该值范围为0～1之间的实数；第二部分为每一个兴趣聚 类中心，用向量表达，每一个特征项的值为该聚类中词条特征的词频平均值，聚类中 心随着聚类中文本的变化而不断更新；第三部分为关联特征词条，从每一个兴趣聚类 中获取，代表用户的一类兴趣。

本发明所述的两阶段策略的个性化搜索方案包括用户兴趣剖像生成阶段和个性化 搜索推导阶段。

阶段一、用户兴趣剖像生成

该阶段包括两个步骤：

步骤一、对用户浏览器缓存区的浏览页面进行聚类；

通过对用户浏览器缓存区中的浏览页面实施基于图链接的聚类，获得用户兴趣聚 类。具体步骤如下所示：

步骤（11）：提取用户浏览器缓存区中的浏览页面，把每一个浏览页面p表示成一 组词条的特征向量和其包含的超链接页面集合。

步骤（12），将用户的浏览器缓存区中的浏览页面按照其包含的链接关系建立图模 型的表示方式，所述图模型表示为浏览页面图HG＝{V,E}，其中，HG是一个无向图， 节点的集合V＝{p_i|1≤i≤n}，V代表浏览页面集合，p_i表示集合V中第i个浏览页面， n表示集合V的浏览页面总数；E是边的集合，边表示V中两个浏览页面的链接关系， 若有p_i，p_j∈V,当p_j∈p_i.L时，则有<p_i,p_j>∈E∪<p_j,p_i>∈E，p_i.L表示浏览页面p_i中包 含的超链接页面集合；p_j表示集合V中第j个浏览页面，1≤j≤n。

步骤（13）：根据页面邻居和噪声页面，计算浏览页面图HG的边集合E中任意条 边<p_i,p_j>所对应的两个浏览页面是否互为邻居，如果不互为邻居，则判定两个浏览页面 的主题不一致，从浏览页面图HG中删除该边；反之，保留该边。

所述页面邻居Neighborhood(p_i,p_j)是指两个具有直接链接关系的浏览页面，且它 们之间的页面相似度大于指定值，表示为：

$\mathrm{Neighborhood}(p_i,p_j)\iff ((p_i,p_j)\in E)\cap (\mathrm{sim}(p_i,p_j)\ge \theta ),$

其中，相似度函数sim(p_i,p_j)采用浏览页面p_i与浏览页面p_j的特征向量的夹角余弦表 示的它们之间相似度，θ是相似度阈值，根据经验取值范围为0.3～0.4之间的任意实数。

所述噪声页面是指在初始浏览页面集合中与用户兴趣无关的页面，表示为：

如果浏览页面p_i与任意一个聚类中心O_Cj的相似度sim(p_i,O_Cj)＜θ成立，则所述浏 览页面p_i为噪声页面，其中O_Cj表示第j个聚类中心，所述聚类中心是聚类代表性的特 征向量表示，计算方式为每个词条特征在该聚类中出现页面次数的平均值；

步骤（14）：采用深度优先的方式遍历浏览页面图HG，得到浏览页面图HG的所 有连通分量；

步骤（15）：将浏览页面图HG中的每一个节点数量大于阈值的连通分量都作为一 个用户的兴趣浏览页面聚类，按照聚类相似度合并具有相似主题的聚类；所述阈值设 定为浏览页面图HG中页面总数的5%～10%；

步骤（16）：将剩余的节点分配到与其相似度最大的聚类中，并重新计算每一个聚 类的中心。

步骤二、聚类的关联规则词条挖掘；

从每一个兴趣聚类包含的页面中挖掘具有关联关系的所有词条，生成用户兴趣剖 像。具体步骤如下所示：

步骤（21），对于每一个兴趣聚类，将兴趣聚类包含的页面中每一个词条作为一个 词条特征，根据词条特征在浏览页面中出现与否，如果出现将词条对应的布尔型特征 值设为1，否则为0，每一个浏览页面可表示为一个高维的布尔型特征向量；

步骤（22），确定加权关联规则中的词条特征集X的加权支持率，和规则的 加权可信率如下：

词条特征集X的加权支持率计算公式如下：

$\mathrm{WSup}(X,C)=\underset{i=1}{\overset{p}{\Sigma }}L(t_i,C)\times \mathrm{Support}(t_i,C)$

其中，p值为词条特征集X中词条特征的个数，t_i∈X,1≤i≤p，

词条特征t_i在聚类C中的权重，

词条特征t_i在聚类C中的支持率，

DF(t_i,C)表示词条特征t_i在聚类C中的文档频率，

DF(t_i)表示词条特征t_i在全部浏览页面集合中的文档频率；

|C|表示聚类C的浏览页面总数。

算法中规则的加权可信率计算公式如下：

$\mathrm{WConf}(X\Rightarrow Y)=\frac{\mathrm{WSup}(X\cup Y,C)}{\mathrm{WSup}(X,C)}$

步骤（23），设定加权支持率阈值为0.2，加权可信率阈值为0.7，计算同时满足加 权支持率和加权可信率都大于上述阈值的每一个聚类的关联规则

步骤（24），将所有关联规则转换为关联规则词条(X∪Y)。

步骤（25），保存用户兴趣聚类、兴趣聚类中心和关联规则词条，构成用户兴趣剖 像。

阶段二、基于用户兴趣剖像的个性化搜索推导

将用户输入的关键字与阶段一生成的用户兴趣剖像进行推理判断，获得用户本次 搜索的兴趣，扩展用户搜索请求，提交给通用搜索，获取搜索结果。具体步骤如下所 示：

步骤（31），推导用户的搜索兴趣：取用户输入的搜索关键词与每一个用户兴趣聚 类中心进行相似度计算，获得最佳匹配兴趣聚类，将用户的搜索关键词映射到该兴趣 聚类上，计算公式如下：

$F\left(q\right)=\underset{1\le i\le \left|C\right|}{\arg \max }\mathrm{sim}(q,O_{\mathrm{Ci}})*w\left(C_i\right)$

其中，|C|表示用户兴趣聚类的个数，sim(q,O_Ci)是用户搜索关键字q与用户的第i 个兴趣聚类中心O_Ci的相似度，w(C_i)是第i个兴趣聚类的兴趣程度，其值为：C_i兴趣聚 类中页面数/总页面数；

步骤（32），获取兴趣聚类关联规则词条并由用户确认：将最佳匹配兴趣聚类对应 的关联规则词条显示出来，并由用户确认兴趣聚类；

步骤（33），扩展用户搜索请求：如果步骤（32）确定了兴趣聚类，那么将该兴趣 聚类的关联规则词条作为用户搜索请求的扩展，提交给搜索引擎；否则，不扩展用户 的搜索关键词，直接提交给搜索引擎；

步骤（34），结果返回显示：把搜索引擎返回的结果显示给用户。

本发明能够自动聚类浏览器缓冲区中的用户浏览页面，从用户兴趣页面聚类中挖 掘出用户兴趣剖像，并将兴趣剖像用于实现用户个性化搜索的推导。

本发明由于是从用户最近浏览页面中获取信息，随着用户浏览页面的变化，本发 明实时跟踪用户兴趣的变化，所以能够动态反映用户最新的兴趣。而采用关联规则挖 掘算法，从用户的兴趣聚类中获取用户兴趣的代表性词条特征，当用户搜索时，代表 用户兴趣的词条特征能够将搜索范围限制在特定兴趣页面内，相当于在一个用户感兴 趣的页面集合中进行选择。从而，返回的搜索结果既满足了用户的要求，又很自然地 表示出用户的个性化特点。

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/ 或其他方面的优点将会变得更加清楚。

图1是本发明实现的个性化搜索系统结构图

图2是用户兴趣剖像描述示意图。

图3是基于图链接的浏览器缓存区页面聚类流程图。

图4是浏览器缓存区页面在特征空间的分布示意图。

图5是将浏览器缓存区页面建模成图并删除噪声页面的示意图。

图6是获取图的连通分量示意图。

图7是合并相同主题的聚类并分配没有被连通分量包含的浏览页面节点示意图。

图8是个性化搜索技术实现的框架示意图。

具体实施方式：

参照图1，本发明的实施过程主要有两个阶段，一个阶段是用户兴趣剖像的生成， 另一阶段是利用用户兴趣剖像进行个性化搜索推导。两个阶段的实施过程相对独立， 可以分开阐述说明，而用户兴趣剖像是将两个阶段联系起来的关键。

下面首先说明用户兴趣剖像，然后分别说明两个阶段的实施过程。

用户兴趣剖像是用户兴趣的描述模型，参照图2，本发明提出的用户兴趣剖像说明 如下：用户兴趣剖像采用一种树状结构描述，从根结点出发，一个分支代表用户的一 类兴趣，与分支边上对应的数值作为该类兴趣的程度；而每一个分支下面都由3层结 构组成，下面一层是浏览页面聚类集合；中间一层是每个浏览页面聚类的中心表示， 以实现用户搜索兴趣的推导；上面一层是关联词条特征，从兴趣聚类中选择，代表用 户的一类兴趣。

阶段一、用户兴趣剖像生成

该阶段的主要实施步骤如下：

步骤一，对用户浏览器缓存区的浏览页面进行兴趣聚类。

从浏览器的缓存中获取web页面，通过对web页面进行超链接分析、文本处理和 聚类后，获得用户的兴趣聚类，保存到用户兴趣剖像模型库中。具体步骤结合图3所 示：

步骤（11），提取用户的浏览器缓存区中的浏览页面，把每一个浏览页面表示成一 组词条的特征向量和其包含的超链接页面集合，初始情况下，页面在特征空间中的表 示如图4所示，图中圆圈表示浏览页面，圈中的数字表示浏览页面的兴趣类别（类别1 和类别2是类标签），x表示页面为噪声页面。

步骤（12），将用户的浏览器缓存区中的浏览页面按照其固有的链接关系建立图模 型（HG），如图5所示，如果两个浏览页面之间有链接关系，那么它们之间存在一条 相连的边。

步骤（13），判定页面邻居和噪声页面，计算浏览页面图HG的边集合E中任意条 边<p_i,p_j>所对应的两个浏览页面是否互为邻居，如果不互为邻居，则判定两个页面的主 题不一致，从浏览页面图HG中删除该边；反之，保留该边。如图5所示，图中噪声 页面是因为用户浏览过程中存在兴趣主题偏移或链接主题漂移。图中连线上的叉表示 两个页面虽然具有链接关系，但是页面相似度太小，不能构成页面邻居。

步骤（14），采用深度优先的方式遍历浏览页面图HG，得到浏览页面图HG的所 有连通分量，不同的连通分量可能具有相似的兴趣主题，如图6所示，深度优先遍历 页面图后，共获得4个连通分量（用虚线包围），类别1和类别2的聚类各由两个连通 分量组成。

步骤（15），将浏览页面图HG中的每一个浏览页面节点数量大于给定值的连通分 量，都可以看作是用户一类兴趣页面聚类，并按照聚类相似度合并具有相似主题的聚 类，如图7所示。

步骤（16），将剩余的页面节点分配到与其相似度最大的聚类中，并重新计算每一 个聚类中心。

步骤二，获取关联规则词条，生成用户兴趣剖像

在步骤一生成的用户兴趣聚类基础上，挖掘聚类的关联规则，形成关联规则词条， 保存到用户兴趣剖像模型中。具体步骤如下：

步骤（21），对于每一个兴趣聚类，将兴趣聚类包含的页面中每一个词条作为一个 词条特征，根据词条特征在浏览页面中出现与否，如果出现将词条对应的布尔型特征 值设为1，否则为0，每一个浏览页面可表示为一个高维的布尔型特征向量；

步骤（22），确定加权关联规则中的词条特征集X的加权支持率，和规则的 加权可信率如下：

词条特征集X的加权支持率计算公式如下：

$\mathrm{WSup}(X,C)=\underset{i=1}{\overset{p}{\Sigma }}L(t_i,C)\times \mathrm{Support}(t_i,C)$

其中，p值为词条特征集X中词条特征的个数，t_i∈X,1≤i≤p，

词条特征t_i在聚类C中的权重，

词条特征t_i在聚类C中的支持率，

DF(t_i,C)表示词条特征t_i在聚类C中的文档频率，

DF(t_i)表示词条特征t_i在全部浏览页面集合中的文档频率；

|C|表示聚类C的浏览页面总数。

算法中规则的加权可信率计算公式如下：

$\mathrm{WConf}(X\Rightarrow Y)=\frac{\mathrm{WSup}(X\cup Y,C)}{\mathrm{WSup}(X,C)},$

步骤（23），设定加权支持率阈值为0.2，加权可信率阈值为0.7，计算同时满足加 权支持率和加权可信率都大于上述阈值的每一个聚类的关联规则

步骤（24），将所有关联规则转换为关联规则词条(X∪Y)。

步骤（25），保存用户兴趣聚类、兴趣聚类中心和关联规则词条，构成用户兴趣剖 像。

阶段二、利用用户兴趣剖像进行个性化搜索推导

参照图8，在用户发起搜索时，获取用户的搜索关键字q，根据用户搜索关键字将 其映射到用户的某类兴趣，并以人机交互的方式让用户确认，获得相应兴趣聚类的关 联规则词条F(q)；之后，将用户搜索请求与兴趣特征代表(q∪F(q))一起提交给通用搜 索引擎，比如百度或者google，这一步的作用是将用户的搜索限制在特定的兴趣范围 里，最后接收通用搜索引擎的结果给用户，完成一次用户的搜索请求。具体步骤如下：

步骤（31），获取用户输入的搜索关键字q；

步骤（32），推导用户的搜索兴趣；

将用户输入的搜索关键词与每一个用户兴趣聚类中心进行相似度计算，获得最佳匹 配兴趣聚类，将用户的搜索关键词映射到该兴趣聚类上，计算公式如下：

$F\left(q\right)=\underset{1\le i\le \left|C\right|}{\arg \max }\mathrm{sim}(q,O_{\mathrm{Ci}})*w\left(C_i\right)$

其中，|C|表示用户兴趣聚类的个数，sim(q,O_Ci)是用户请求q与用户的第i个兴趣 聚类中心的相似度，w(C_i)是第i个兴趣聚类的兴趣程度，其值为C_i兴趣聚类中页面数 /总页面数；

步骤（33），用户交互确认

将最佳匹配兴趣聚类对应的关联规则词条显示出来，并由用户确认兴趣聚类；

步骤（34），扩展用户搜索请求

如果步骤（33）确认了兴趣聚类，那么将该兴趣聚类的关联规则词条作为用户的扩 展搜索请求，提交给搜索引擎；否则，不扩展用户的搜索关键词，直接提交给搜索引 擎；

步骤（35），搜索结果返回显示

实施例

本发明的效果通过以下仿真实例予以说明：

1、抽取用户web缓存文档，计算用户兴趣聚类

在一个利用本发明实现的个性化搜索系统中，预置用户缓存的有效文档总数为319 个，词条总数为1813。该系统中的用户兴趣聚类子系统从用户使用过的浏览器中，抽 取缓存在硬盘上的web文档，执行文档聚类算法。本实例系统聚类后的结果如下表所 示，得到用户的5个相关兴趣类，以及每个兴趣类的文档数、词条特征数和聚类比例。 其中，每个聚类的词条特征数只记录该类中包含的词条，不同聚类会有相同的词条， 比如“火箭”词条在第1和2类中都存在。由于，聚类中心是词条的向量表达，用于 计算和关键字的相似度，在此就不再给出示例。

聚类序号 聚类文档数 聚类词条特征数 聚类比例 1 100 890 100/319 2 83 787 83/319 3 50 540 50/319 4 46 455 46/319 5 40 408 40/319 总数 319 1813 1

2、利用关联规则方法，计算用户剖像信息

上述用户的兴趣聚类文档，即可作为用户的兴趣样本，通过布尔型关联规则挖掘 算法获取代表某兴趣类的特征词条作为兴趣剖像信息。

聚类序号 兴趣浓度 兴趣聚类关联特征词条 1 0.313 球员∪NBA∪得分 2 0.26 军事∪战机 3 0.158 电影∪明星∪票房 4 0.144 房产∪调控 5 0.125 数码相机∪拍摄∪色彩 总数 1 13

3、用户兴趣匹配推荐和搜索扩展

用户在进行搜索时，用户输入关键词“火箭”时，实例系统将捕获用户输入，与 兴趣聚类进行匹配，获得第1和2两个聚类中都有“火箭”一词，但是，实例系统通 过计算得出：“火箭”与第1个聚类的相似度为0.68，“火箭”与第2个聚类的相似度 为0.23，而且，用户对第1个兴趣类浓度为0.313，第2个兴趣类浓度为0.26。因此， 可以计算出两个兴趣类的匹配度分别为：0.213和0.0598。实例系统获得最佳匹配类并 提示用户本次搜索选择兴趣类进行扩展搜索。显然，如果用户兴趣与第一个兴趣类匹 配，那么用户关注在篮球的火箭队，实例系统会将“火箭”and“球员or NBA or得分” 进行组合，通过搜索引擎获取结果；如果用户兴趣与第二个兴趣类匹配，那么用户关 注在军事的航天火箭发射方面，实例系统会将“火箭”and“军事or战机”进行组合 发送给搜索引擎，通过搜索引擎获取结果，由此比用户单独输入“火箭”相比，获得 与用户兴趣关联度更高的更加准确的搜索结果。

本发明提供了一种基于用户兴趣的个性化搜索实现方法的思路及方法，具体实现 该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对 于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干 改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组 成部分均可用现有技术加以实现。