文本检索的聚类分布式索引

刘宇松 江苏经贸职业技术学院

一、前言

随着信息技术的发展，各种数据的可用性呈爆炸性增长。它带来了一个前所未有的机会，可以开发自动数据驱动的技术来提取有用的知识，这就产生了数据挖掘的概念。数据挖掘是知识发现过程中的一个重要步骤，它由发现知识的方法组成隐藏在数据中的有趣、非平凡和有用的模式。大量的非结构化文档在许多领域都是可用的，当我们使用网络时，可以从世界各地检索文档。为了检索到对用户有用的信息，必须移动大量文本。快速有效的聚类是无监督学习的基本工具。现在已经开发出了各种方法来支持对文本文档集合的高效搜索和检索，包括后缀数组、倒排文件或倒排索引和签名文件等。

一个粗略但得到广泛认可的框架是，根据生成的聚类的属性，将聚类技术分为层次聚类和分区聚类。距离度量必须根据数据的基本形状进行适当选择，无论是球形数据还是椭球数据。查询可以是布尔查询，也可以是排序查询。布尔查询由逻辑运算符AND、OR和NOT连接的术语组成，可用于标识包含给定术语组合的文档，类似于关系表上使用的查询类型。

另一方面，排名是一个将非正式查询与文档相匹配的过程，并根据文档与查询的相似程度为文档分配分数。主要问题是组织和存储大量数据。当对这些数据进行搜索时，搜索的质量应该非常好。搜索还应具有成本效益和时间效益，非常重要的是，搜索查询得到的结果应该与我们实际搜索的结果相同。

有相关学者开发出了用于多台计算机上数据挖掘的可伸缩并行聚类模型。他们在并行机上设计并实现了自动分类，这是一个基于贝叶斯方法的自动分类系统的并行版本，用于确定大型数据集中的最佳类。特别是顺序自动分类系统的效率和可扩展性也通过它们进行了评估和比较。

文本搜索和信息检索在现代计算中起着非常重要的作用。这可以通过谷歌、雅虎、瑞迪夫等高效搜索引擎实现。搜索引擎是在集合中查找与用户查询匹配良好的文档的工具。典型的文件收集类型包括网页、报纸文章、学术出版物、公司报告、研究资助申请、手册页、百科全书、议会议事录、参考书目、历史记录、电子邮件和法庭记录等。

一位研究人员在十年内撰写的一整套论文的纯文本可能会占用10兆字节，而同一位研究人员的（纯文本、非垃圾邮件）10年电子邮件存档可能会占用100兆字节。随着时间的推移，收藏的变化方式也有所不同。一个新闻专线档案馆或数字图书馆可能会增长缓慢，也许每天会增长几千份文档；删除很少。

相反，Web集合可以是高度动态的。许多相同的搜索和存储技术对这些集合很有用。文本并不是存储在文档集合中的唯一一种内容。研究论文和报纸文章包括图片，电子邮件包括附件，网络收藏包括音频和视频格式。

为了解决这个问题，许多研究人员在他们的论文中提出了几种方法。其中一种方法是排名。排名是将查询与文档匹配，并根据文档的相似度为文档分配分数的过程。另一种方法是聚类过程。聚类是将对象组织成组的过程，这些组的成员在某种程度上是相似的。

搜索引擎在结构上类似于数据库系统。文档存储在存储库中，并维护索引。通过处理索引来评估查询，以识别匹配项，然后将匹配项返回给用户。然而也有许多不同之处。数据库系统必须处理任意复杂的查询，而对搜索引擎的查询是术语和短语的列表。在数据库系统中，匹配是满足指定逻辑条件的记录；在搜索引擎中，匹配是根据统计启发法适合查询的文档，甚至可能不包含所有查询词。

数据库系统返回所有匹配的记录；搜索引擎返回固定数量的匹配项，这些匹配项按其统计相似性排序。数据库系统为每个记录分配一个唯一的访问密钥，并允许对该密钥进行搜索；对于在web集合上进行查询，可能会有数百万个与查询具有非零相似性的文档。因此，当搜索引擎如果没有关系连接等操作的相关成本，快速响应会有很大的障碍，也就是说，查询术语可能出现在大量文档中，并且每个文档通常包含大量术语。文本搜索带来的挑战导致了一系列算法和数据结构的发展。这些包括文本索引表示、索引构造技术和文本查询评估算法。

二、相关工作

索引对于搜索引擎提供快速响应至关重要。通过使用压缩和仔细的组织，索引所需的空间以及查询评估期间所需的时间和磁盘流量减少到以前需求的一小部分。因此，考虑到上述所有参数，我们尝试开发一种新的方法，通过使用C语言开发代码来改进聚集分布索引，这是本文的重点。

我们使用Leader算法对我们获得的海量数据进行聚类。在搜索时，我们不必搜索整个数据，而只需搜索集群。这是使用集群的最大优势。通过聚类，搜索变得既经济又省时。因此，我们在搜索技术中使用了聚类。我们搜索引擎的输入是从几本书中收集的数据。我们收集了不同地区几本书的目录。我们首先压缩通过使用词干和停止等方法获得的原始数据。

停止将各种内容表作为输入，对其进行处理，并给出不包含停止字的输出。停止词包括重复词或功能词，在数据库中存储时不太重要，但可能只会占用内存。因此，在进一步处理这些单词以供后续阶段使用之前，这些单词将被删除或清除。

将输入语句送入停止模块，我们获得的输出没有标点符号，并且删除了常见的单词。下一个阶段采用无停止词列表作为输入。基本单词被存储，该单词的其他形式被清除，从而节省了内存空间，同时也提高了搜索技术的效率。这些停止、阻塞和案例折叠的步骤都是预处理阶段的一部分，在预处理阶段中，初始数据在实际处理之前被清理。

为了有效处理高流量的用户查询，我们使用分布式反向索引。倒排文件由一个词汇表和一组发布列表组成。词汇表包含测试集合中的一组相关术语，这些术语按字母顺序排列。这些术语中的每一个都与包含文档标识符以及用于排名目的的附加数据的发布列表相关联。要解决查询，需要获取与查询条件相关联的文档集，然后对这些文档进行排序，以便选择排名前“K”的文档作为查询答案。

根据词汇表中单词之间的距离，相似的单词会聚集在一起。根据词汇表的大小和文档的类型，存在几个集群。线程（轻量级进程）应用于单个集群。令人惊讶的是，我们的结果显示，通过使用集群和并行的概念，搜索变得更具成本效益、时间效益，并且搜索质量变得更准确。我们的结果表明，该策略能够在大规模和小型搜索引擎中产生有效的性能。

三、索引

为了避免每次查询对文本语料库进行线性扫描，我们提前对文档进行索引。为了获得索引的速度优势，我们还需要提前执行文档索引。进行此操作所需的主要步骤如下：收集要编制索引的文档；将文本标记化，将文档拆分为标记；生成索引术语的列表；创建由列表和词汇表组成的倒排索引。

矩阵表示法：这是术语相对于各种文档的表示法。我们可以使用一些距离度量来计算两个单词之间的距离，如欧几里德距离。

术语文档关联矩阵：索引总是从术语映射回文档中出现术语的部分。我们有一本术语词典，通常按字母顺序排序。对于每个术语，我们都有一个列表，记录该术语出现的文档。列表中的每一项都记录了文档中出现的术语称为“邮件列表”，该列表称为“发布列表”。

字典通常保存在内存中，而发帖列表通常保存在磁盘上。对于内存中的发布列表，我们使用了单链接列表。邮件列表包含以下字段：第一个字段表示该术语在文档中出现的频率。第二个字段表示文档标识（文档id），第三个字段指向下一个列表。

四、聚类

聚类是将对象组织成员在某种程度上相似的组的过程。簇是相互“相似”且与属于其他簇的对象“不同”的对象的集合。一个粗略但得到广泛认可的框架是根据生成的聚类的属性将聚类技术分为层次聚类和分区聚类。

该技术使用了4种不同的方法，即搜索、聚类、反向索引和预处理（停止和词干分析）。聚类算法将数据项分为若干组，以便相似的项归入同一组。这是在没有任何外部主管建议的情况下完成的，课程和培训示例不适用先验的。大多数早期的聚类分析算法来自统计领域，最初是为相对较小的数据集设计的。

近年来，聚类算法得到了扩展，能够有效地在大型数据库中进行知识发现，其中一些算法能够处理高维特征项。当用于对大型数据集进行分类时，聚类算法的计算要求很高，需要高性能的机器在合理的时间内得到结果。

五、结论

本文提出了一种利用线程获取聚类分布式索引的新方法。使用集群上的线程进行搜索比顺序搜索更快。此外，这是有道理的结果表明，与顺序搜索或线程搜索相比，使用集群进行搜索所需的时间更少。当然，线程有助于提高文本检索的性能，因为搜索查询所需的时间更少。但是，使用线程的基于集群的搜索进一步改进了搜索结果，因为相关的术语可以一起找到。我们的结果还表明，提出的聚类和并行搜索的概念更具成本效益、时间效益和搜索质量的准确性。用于确定搜索索引的leader算法的优点是，一次数据库扫描，效率高和访问时间非常快。对于数据大小，使用基于群集的搜索这种方法对于不同的单词大小产生了很好的索引结果，从而减少了搜索时间。在实际场景中，万维网（www）正在使用非常大的数据集。因此，我们可以推断，基于聚类的线程搜索花费的时间最少，效率最高。