基于相关反馈和聚类的搜索引擎技术

摘要

本发明同时利用用户相关反馈信息和相关度排序指导检索结果的聚类，使检索结果的最终划分符合用户查询需求；在聚类过程中去除了大量与用户不相关的文档和重复网页，提高了聚类速度，同时优化了检索结果。在聚类过程中，与用户不相关的一类聚簇不修改聚类中心，确保了不会在不相关文档聚簇中因引入噪声而丢掉与用户相关的结果文档。

说明书

技术领域

本发明涉及互联网信息检索技术领域，尤其涉及一种基于相关反馈和聚类的Web检索结果优化方法。

背景技术

目前，搜索引擎大都是基于关键词来进行索引和检索的，根据用户输入的关键词列表，搜索引擎查找索引库，将匹配的文档按照与用户查询的相关度的不同排序显示。由于关键词具有一词多义现象，而且用户往往只输入很少的关键词进行检索，使得搜索引擎返回的搜索结果列表通常包含了很多主题不相关、混杂在一起的文档，用户必须逐个浏览检索结果列表以找到相关文档，其中还有许多内容重复的网页，从这样的检索结果中浏览信息会浪费用户许多时间和大量精力。

为了方便用户的浏览，一些研究人员将自动聚类技术用于Web信息检索结果的类别划分，将具有相似特征(例如同属于一个主题)的文档放在同一组，以便于用户缩小查找范围，只在自己感兴趣的少数组中查找和浏览所关心的文档。但是对检索结果的自动聚类没有考虑与用户的相关性，导致检索结果不能反映用户的特定意愿及专业领域，用户也不能根据自己的需要和兴趣选择文档聚类的方式。另外，在Web搜索引擎上其检索结果数量巨大，已有的自动聚类研究是对全部检索结果包括大量与用户不相关的结果进行聚类，聚类过程需要时间长，从而影响搜索引擎的性能。

为了使检索结果的聚类与特定用户的查询需求相关，出现了一种基于查询日志的检索结果的半指导聚类方法。该方法根据查询日志中用户点击结果的记录数据得到must-link约束，具体方法是假定用户点击了同一页的两个检索结果，则认为它们是和用户查询相关的，由此可以得出它们之间具有must-link约束关系。考虑到由于个人的原因选择的must-link约束会具有噪声，该方法首先统计查询日志中这些约束的产生频率，然后选择频率大于某个阈值的约束作为最终的must-link约束。用此方法遍历查询日志可以得到关于每个查询的must-link约束，最后根据约束进行检索结果的半指导聚类。由于查询日志中并不包括用户的所有可能的查询，对于用户输入的新的查询，并不能从查询日志中得到约束关系；此外，在聚类时保证了must-link约束的结果在同一聚簇中，can not-link约束的结果不在同一聚簇中，并没有考虑聚类过程的优化，按照该方法对Web信息检索结果聚类时对全部与用户相关的和不相关的检索结果进行聚类处理仍然会耗时长，影响搜索引擎的性能。

另一种将用户反馈信息结合到文本聚类的方法，需要用户首先指定属于一些聚簇的例子文档以指导聚类过程。然后将聚类结果呈现给用户，由用户检查聚类结果并给出一些反馈信息，例如指出文档d应该属于聚簇S或不应属于聚簇S；文档d应该从聚簇S_i换到聚簇S_j；两个文档应在同一聚簇或不应在同一聚簇。根据用户反馈信息指导下一轮聚类过程，再与用户交互，直到得到用户满意的聚类结果。对每个聚簇建模时使用了特征局部权重来反映一个聚簇的特征的重要性。通过增加更多更准确的约束来提高特征局部权重的质量，从而提高聚类效果。该方法主要考虑了文本聚类的有效性，但需要用户多次输入反馈信息，增加了用户的负担，尤其是首次聚类时需要用户指定属于一些聚簇的例子文档以指导聚类过程，给用户增加了难度；而且聚类的过程耗时长，不适用于Web信息检索结果的聚类。

发明内容

本发明针对上述方法存在的需要用户多次输入复杂的反馈信息或是查询日志对新的查询无效，以及对全部检索结果聚类耗时长、结果划分中存在无关文档类或文档聚簇中仍存在大量重复内容等弊端，提供了一种只需用户输入与查询需求相关和不相关的少部分反馈信息来指导优化Web检索结果的方法。

本发明采用以下技术方法：

(1)确定初始聚类类别数和各类别的初始聚类中心向量，包括：

将用户从检索结果中选取的相关文档划为一类，称为相关文档类，确定相关文档类的初始聚类中心；相关文档类的初始聚类中心向量通过求取各个关键词在该类各个文档中的权重平均值得到。

将不相关文档划分为一个或若干个不相关文档类，确定每类的初始聚类中心，包括：

-选一个不相关文档作为第一个不相关文档类，该文档的特征向量即为该文档类的聚类中心向量

-计算其余不相关文档和上述类别的相似度，根据相似度值将其划分到最相近的某个不相关类别中或划分到新的不相关类，如果是划分到新的一类，则该文档的特征向量即为该类的聚类中心向量

(2)初始划分及确定最终聚类类别数；

计算检索结果列表中用户未选取的文档与相关文档类和不相关文档类的相似度，根据相似度值的大小进行以下处理：

-将其划分到最相近的某个文档类中

-或划分到新的文档类，该文档特征向量即为该类的聚类中心向量；

-或者判断出属于重复内容的文档并将其删除

(3)去掉初始划分中的每个文档类(聚簇)中内容重复的文档；

从该类中的某个文档d1开始，计算该文档的特征向量与其后各个文档向量之间的相似度，根据相似度值判断某文档是否与文档d1内容重复，如果是，则从检索结果列表和该文档类中删除与该文档d1内容重复的文档；

然后从更新了的检索结果列表中的下一个开始，计算该文档的特征向量与其后各个文档的特征向量之间的相似度，并进行是否是重复文档的判断。

重复上述过程，直到检索结果列表的最后。

(4)修改除了不相关文档类以外的其它类别的聚类中心向量；

类的初始聚类中心向量通过求取各个关键词在该类各个文档中的权重平均值得到。

(5)重新计算检索结果列表中用户未选中的其它项与每个聚类中心的相似度，重新进行划分，包括：

-计算每个文档的特征向量和每个类别聚类中心向量之间的相似度，将文档划分到最相近的类别中。

-如果某文档属于不相关文档类，而且其与查询的相关度排序靠后，则分别从不相关文档类别和检索结果列表中删除该文档。

(6)重复步骤(4)和(5)，直到满足终止条件。

本发明同时利用用户相关反馈信息和相关度排序指导检索结果的聚类，使检索结果的最终划分符合用户查询需求；在聚类过程中去除了大量与用户不相关的文档和重复网页，提高了聚类速度，同时优化了检索结果。在聚类过程中，与用户不相关的一类聚簇不修改聚类中心，确保了不会在不相关文档聚簇中因引入噪声而丢掉与用户相关的结果文档。

附图说明

下面结合附图对本发明作详细说明：

图1为本发明的流程图。

具体实施方式

步骤S101：用户从搜索引擎检索结果中选择相关的文档和不相关的文档；

步骤S102：确定初始聚类类别数和初始聚类中心；

假设检索结果列表中文档为d1，d2，..ds(s为文档数)，假设检索系统的索引库中索引的关键词不包括停用词，在检索系统的索引库中选取文档d1，d2，..ds中关键词权重，即关键词在文档中出现的频率，大于预设的阈值δk的关键词t1，t2，t3，..tn(n为关键词数)，构成向量空间模型中向量的维，则文档di的特征向量di定义为：

di＝(w_i1，w_i2，...，w_in)                    (1)

其中，w_ij＝tf_ij(i＝1，2，...s，j＝1，2，...n)，tf_ij是第j个关键词在第i个文档di中出现的频率。

1.抽取相关文档的公共特征向量：

将用户选取的相关文档作为一个相关文档类，用C1表示。假设C1文档类中的相关文档为d1，d2，..dm(m为用户选取的相关文档数)，则关键词t1，t2，t3，..tn在C1类中的权重分别为：

$a_{1j}=\frac{\underset{i=1}{\overset{m}{\Sigma }}{\mathrm{tf}}_{\mathrm{ij}}}{m},(j=\mathrm{1,2},...n)---\left(2\right)$

C1类的初始聚类中心向量定义为：

C1_center＝(a₁₁，a₁₂，..a_1n)

此时聚类类别数k＝1。

2.对不相关文档进行类别划分：

用户选取的不相关文档可能属于同一文档类，也可能属于不同的文档类。对于t个不相关文档按照以下步骤进行划分：

-任选一个不相关文档记为di(i＝1，2，...t)，聚类类别数k＝k+1，将文档di划分到Ck文档类，文档di的特征向量di作为Ck文档类的聚类中心向量Ck_center。

-对其余的t-1个不相关文档重复以下过程：

计算文档di的特征向量di和每个不相关文档类的聚类中心向量之间的相似度，相似度计算公式采用向量夹角余弦公式：

$\mathrm{sim}(\mathrm{di},{\mathrm{Cj}}_{\mathrm{center}})=\frac{\underset{v=1}{\overset{n}{\Sigma }}{w}_{\mathrm{iv}}\times a_{\mathrm{jv}}}{\sqrt{\left(\underset{v=1}{\overset{n}{\Sigma }}{w}_{\mathrm{iv}}^2\right)\times \left(\underset{v=1}{\overset{n}{\Sigma }}{a}_{\mathrm{jv}}^2\right)}}---\left(3\right)$

其中，Cj_center为第j个文档类的聚类中心向量，w_iv是第v个关键词在第i个文档di中的权重，其定义见式(1)；a_jv是第v个关键词在第j个聚类Cj中的权重。

如果di与某个已有的不相关文档类Cg(g＝2，3，...k)的聚类中心向量Cg_center相似度值最大且超过设定阈值δ1时，则将文档di归为Cg文档类；

如果di与当前所有不相关类别的聚类中心向量的相似度值都小于设定阈值δ1，则令k＝k+1，将文档di划分到新的文档类Ck，文档di的特征向量di作为Ck文档类的聚类中心向量Ck_center。

上述过程结束，将不相关文档划分为d＝k-1个类别。初始的聚类类别数为k。

步骤S103：确定初始划分及最终聚类类别数k；

对用户未选中的结果列表中每个文档di，重复以下过程：

1.计算文档di的特征向量di和每个文档类的聚类中心向量之间的相似度，计算采用式(3)。

2.如果特征向量di与第r个文档类Cr的聚类中心向量Cr_center相似度值最大且超过设定阈值δ1时：

-如果相似度值小于设定阈值δ2(δ2＞δ1)，则将文档di归为Cr类；

-否则认为文档di为重复页，从检索结果列表中删除文档di。

3.如果特征向量di与当前k个文档类的聚类中心向量的相似度值都小于设定阈值δ1，则令k＝k+1，将文档di划分到新的文档类Ck，文档di的特征向量di作为Ck的聚类中心向量Ck_center。

上述过程结束，初始划分形成，最终聚类类别个数为k。

步骤S104：去掉被划分到k个文档类中的网页的重复内容；

设某一文档类中有p个文档组成文档列表d1，d2，..dp。

从文档d1开始，计算该文档向量与其后p-1个文档向量之间的相似度，如果与文档dx的特征向量之间的相似度值大于设定阈值δ2，则认为两者是重复网页，分别从检索结果列表和该文档类中删除文档dx，修改p＝p-1；

然后从更新了的检索结果列表中的d2开始，计算该文档向量与其后p-2个文档向量之间的相似度，如果与文档dy的特征向量之间的相似度值大于设定阈值δ2，则认为两者是重复网页，分别从检索结果列表和该聚类中删除文档dy，修改p＝p-1；

重复上述过程，直到检索结果列表的最后。

步骤S105：修改除d个不相关类别外的其它文档类的聚类中心向量；

步骤S106：重新计算检索结果列表中用户未选中的其它文档与这k类的相似度，并进行划分；

对更新后的检索结果列表中用户未选中的每个文档di，重复以下过程：

1.根据公式(3)计算文档di的特征向量di和每个文档类的聚类中心向量之间的相似度，将文档di划分到最相近的文档类中。

2.如果文档di属于不相关文档类，而且其与查询的相关度排序靠后，则分别从不相关文档类和检索结果列表中删除该文档。

步骤S107：重复105和106，直到满足终止条件。

设定终止条件为目标函数值最小或小于设定的迭代次数。