利用不同相似度度量的元搜索方法查找网页相似度

### 利用不同相似度度量的元搜索方法查找网页相似度 #### 1. 引言 万维网的规模因大量网页的快速创建而显著增长，目前已约有 600 亿个网页。为了从这些网页中检索信息，搜索引擎应运而生。搜索引擎允许用户以查询的形式提出请求，返回网页列表，通常评分高的网页排在结果顶部。其中，Page Rank 是一种流行的网页评分计算方法。搜索引擎的主要组件包括网络爬虫和索引器，爬虫负责收集网页，索引器对这些网页进行排序，查询处理器处理用户查询并按排名算法返回匹配结果。 传统的网页搜索引擎以查询词为输入，返回相关页面。而本文旨在寻找与原页面主题相同且信息相关的“相似”页面。传统搜索引擎存在用户查询易出错的缺点，因此本文采用不同的查询方式，即输入特定页面的 URL，搜索引擎返回相关页面集合。同时，本文应用元搜索引擎方法进行信息检索，这种方法也称为混合搜索引擎，用户只需进行一次搜索，它会搜索不同搜索引擎数据库并在单页给出最佳结果，能有效利用不同搜索引擎资源，产生综合结果。之后，利用向量空间模型的不同相似度度量来处理这些结果，以确定哪些网页与查询页面更相似。 #### 2. 问题陈述 随着网络的快速发展，相似文档或页面不断增多。在不同网页上呈现相同内容虽能提高信息可用性和可访问性、减少繁忙网站流量，但也存在诸多缺点，如爬取、计算时间、存储和索引成本高，重复页面会影响真实页面排名，网页可能存在抄袭现象，相似页面易形成大集群。因此，需要一个能有效确定网页相似度的系统。此外，不同搜索引擎采用不同技术检索网页，且其方法通常是专有的，人们不清楚它们如何检索相似网页，已知方法通常分析页面间的链接结构或内容。 #### 3. 相关工作 查找网页相似度的方法主要有以下几种： - **分析网页内容**：包括文本内容、锚文本、元标签（标题、描述、关键词）。 - **分析网页链接结构**：分析页面的内部和外部链接分布。 - **同时考虑内容和链接**：综合考虑内容信息和网页间的链接关系。 为确定网页的结构相似度，可使用标签频率分布分析（TFDA）方法，该方法利用 HTML 标签频率计算相似度。向量空间模型（VSM）将一组文档表示为公共向量空间中的向量，可用于通过各种相似度度量（如余弦相似度、Jaccard 系数和 Dice 系数）来计算文档间的相似度。 向量空间模型将文本信息转换为数值向量进行分析，n 个文档的集合可通过词 - 文档矩阵在向量空间模型中表示。Tf - idf 加权用于为每个文档生成综合得分，计算公式如下： \[Tf - idf_{t,d}=Tf_{t,d}\times idf_{t}\] \[Score(q,d)=\sum_{t\in q}Tf - idf_{t,d}\] 相似度度量是计算两个向量相似度的函数，常见的相似度度量及其计算公式如下： - **余弦相似度**： \[Sim(d_1,d_2)=\frac{V(d_1)\cdot V(d_2)}{\vert V(d_1)\vert\vert V(d_2)\vert}\] 当余弦值为 1 时，向量方向相同；为 0 时，向量垂直，表明文档不相似。 - **Jaccard 系数**： \[Sim_{Jaccard}(d_1,d_2)=\frac{d_1\cap d_2}{d_1\cup d_2}\] - **Dice 系数**： \[Sim_{Dice}(d_1,d_2)=\frac{2N_{Common}}{N_1 + N_2}\] 网络中的重复或近似重复页面会增加搜索引擎的存储和处理开销。检测重复页面的简单方法是为每个网页计算指纹，当两个网页的指纹相同时，判定其中一个为另一个的重复页面。Charikar 的 SimHash 是查找近似重复页面的实用方法，通过计算两个指纹的汉明距离来确定近似重复页面。此外，还有共引算法、同伴算法、文献耦合和 Amsler 提出的结合共引算法和文献耦合的相似度度量方法。 #### 4. 提出的工作 本文采用元搜索方法从万维网检索网页，利用不同搜索引擎的能力收集相关网页。对于网页的相似度评估和表示，应用向量空间方法，并计算初始网页与提取页面的相似度得分。具体步骤如下： 1. 创建初始集合，包含要查找相似网页的 URL。 2. 从初始集合中选择一个 URL，提取该页面的关键词并计算 Tf - IDF 值，这些值是关键词的权重，代表文档的综合得分。 3. 将关键词以逗号分隔格式发送到 Google 和 Yahoo 进行查询。 4. 分别提取每个搜索引擎结果集中的链接，存储为 Result_Set1（Google）和 Result_Set2（Yahoo）。 5. 合并两个结果集，消除重复链接，得到 Final_Result_Set。 6. 对 Final_Result_Set 中的每个链接，重复步骤 2。 7. 计算余弦相似度并存储结果。 8. 计算 Jaccards 系数并存储结果。 9. 计算 Dice 系数并存储结果。 10. 进行比较分析。 下面是该算法的 mermaid 流程图： ```mermaid graph TD; A[选择初始 URL 集合中的 URL i] --> B[提取关键词并计算 Tf - idf 值]; B --> C[将关键词以 CSV 格式发送到 Google 和 Y ```