数据挖掘中的词干提取

词干提取是生成词根/基本词的形态变体的过程。词干提取程序通常被称为词干提取算法或词干提取器。词干提取将单词简化为其词干，即词缀（前缀和后缀）或单词的词根，称为“词元”。词干提取在自然语言理解（NLU）和自然语言处理（NLP）中很重要。

词干提取是形态学、人工智能（AI）信息检索和抽取领域语言学研究的一部分。词干提取也是查询和互联网搜索引擎的一部分。词干提取和人工智能知识可以从大数据或互联网等海量资源中提取有意义的信息，因为为了获得最佳结果，可能需要搜索与主题相关的其他词形。

当发现新词时，它可以带来新的研究机会。通常，通过使用单词的基本形态，即词元，可以获得最佳结果。为了找到词元，词干提取由个人或算法执行，AI系统可以使用该算法。词干提取使用多种方法将单词从遇到的任何屈折形式简化为其基本形式。

开发词干提取算法可能很简单。一些简单的算法会剥离识别出的前缀和后缀。然而，这些简单的算法容易出错。例如，一个错误可能会将单词“laziness”（懒惰）简化为“lazi”，而不是“lazy”（懒惰的）。此类算法在处理屈折形式不能完美反映词元的词语时也可能遇到困难。

词干提取的历史

Julie Beth Lovins 在 1968 年撰写了第一篇已发表的词干提取文章。这篇文章在当时具有开创性，并对该领域的后续工作产生了重大影响。她的论文提到了之前在词干提取算法方面做的三个主要尝试。

• 一位是普林斯顿大学的 **John W. Tukey** 教授。
• 另一位是哈佛大学的 **Michael Lesk**，在 Gerard Salton 教授的指导下。
• 第三个算法是由加利福尼亚州洛斯加托斯 R and D Consultants 的 **James L. Dolby** 开发的。

Martin Porter 在 1980 年 7 月的《Program》杂志上发表了另一个词干提取器。这个词干提取器被广泛使用，并最终成为英语词干提取的事实标准。2000 年，Porter 博士因其在词干提取和信息检索方面的工作获得了 Tony Kent Strix 奖。

为什么词干提取很重要？

如前所述，英语中有许多单一术语的变体。在开发 NLP 或机器学习模型时，文本语料库中的这些变体会导致数据冗余。这些模型可能无效。

通过词干提取将单词标准化为基本形式，去除重复，对于构建强大的模型至关重要。

词干提取中的错误

词干提取主要有两种错误，即：

1. 过度词干提取（Over-stemming）： 当两个具有不同词干的单词被提取到同一个词根时，会发生这种情况。过度词干提取也可以视为假阳性。
2. 词干提取不足（Under-stemming）： 当两个具有相同词根但不同词干的单词被提取时，会发生这种情况。词干提取不足可以解释为假阴性。

词干提取的应用

以下是词干提取的应用，例如：

1. 词干提取用于信息检索系统，如搜索引擎、文本挖掘 SEO、网络搜索结果、索引、标记系统和单词分析。
2. 它用于确定领域分析中的领域词汇。
3. Google 搜索在 2003 年采用了词干提取来进行预测，并获得了可比的结果。以前搜索“fish”不会返回“fishing”或“fishes”。

词干提取算法分类

所有词干提取算法在性能和准确性方面都有所不同。词干提取算法可分为截断法、统计法和混合法。这些组中的每一组都有一种查找单词变体词干的典型方法。

1. 截断或词缀去除法

顾名思义，这些方法与去除单词的后缀或前缀有关。最基本的词干提取器是 Truncate (n) 词干提取器，它在第 n 个符号处截断单词，即保留 n 个字母并删除其余部分。在此方法中，长度小于 n 的单词保持不变。当单词长度很小时，过度词干提取的可能性会增加。另一种简单的方法是 S-stemmer，它是一种合并英语名词单复数形式的算法。该算法具有去除复数后缀以将其转换为单数形式的规则。

Lovins 词干提取器

Lovins 算法比 Porter 算法更大，因为它包含非常广泛的结尾列表。Lovins 在 1968 年提出，它从单词中删除最长的后缀，然后记录单词以将此词干转换为有效单词。Lovins 词干提取器的主要优点是速度快。它有效地用空间换取时间，并且由于其庞大的后缀集，它只需要两个主要步骤即可删除后缀，而 Porter 算法则需要八个步骤。

Lovins 词干提取器包含 294 个结尾、29 个条件和 35 个转换规则。每个结尾都与一个条件相关联。第一个步骤中找到最长的结尾，该结尾满足其关联条件并被删除。在第二步中，应用 35 条规则来转换结尾。第二步是执行的，无论第一个步骤是否删除了结尾。

例如： sitting -> sitt -> sit

优点： 速度快，能处理不规则复数，如“teeth”和“tooth”等。

缺点： 耗时且耗数据。有时非常不可靠，并且经常无法从词干形成单词或匹配意义相似的单词的词干。此外，许多后缀在结尾表中不存在。

Porter 词干提取算法

该词干提取器以其速度和简洁性而闻名。它是 1980 年提出的最流行的词干提取方法之一。它基于英语中的后缀由更小、更简单的后缀组合而成的想法。它的主要关注点是删除单词的常见结尾，以便将它们解析为通用形式。

Porter 词干提取器的主要应用包括数据挖掘和信息检索。但是，其应用仅限于英语单词。此外，一组词干被映射到同一个词干，输出的词干不一定是可理解的单词。该算法相当冗长，并且是已知最古老的词干提取器。通常，它是一个基本的词干提取器，但不建议将其用于任何生产或复杂应用。相反，它在研究中作为基本的词干提取算法，可以保证可重现性。

例如： EED -> EE 表示“如果单词至少有一个元音和一个辅音加上 EED 结尾，则将结尾更改为 EE”，例如“agreed”变为“agree”。

优点： 与其他词干提取器相比，它产生最好的输出，并且错误率较低。

缺点： 生成的形态变体不总是真实单词。

Paice/Husk 词干提取器

Paice/Husk 词干提取器是一种迭代算法，有一个包含约 120 条规则的表，这些规则由后缀的最后一个字母索引。每条规则指定结尾的删除或替换。每次迭代时，它会尝试通过单词的最后一个字符查找适用的规则。如果没有这样的规则，则终止。如果单词以元音开头且只剩下两个字母，或者单词以辅音开头且只剩下三个字符，则也会终止。否则，应用规则，然后重复该过程。

优点： 简单，每次迭代都根据应用的规则处理删除和替换。

缺点： 这是一个非常繁重的算法，可能会过度词干提取。

Dawson 词干提取器

此词干提取器扩展了 Lovins 方法，但它包含更全面的列表，约有 1200 个后缀。与 Lovins 一样，它是一个单次遍历的词干提取器，速度相当快。后缀以反向顺序存储，并按长度和最后一个字母索引。它们被组织成一组分支字符树，以便快速访问。

优点： 执行速度快，覆盖的后缀更多，并且产生更准确的词干提取输出。

缺点： 实现非常复杂，并且缺乏标准的、可重用的实现。

2. 统计方法

这些是基于统计分析和技术的词干提取器。大多数方法在实现某些统计程序后会去除词缀。

N-Gram 词干提取器

这是一种非常有趣的方法，它与语言无关。这里使用字符串相似性方法将单词的屈折形式转换为其词干。n-gram 是从一段连续文本中提取的 n 个（通常是相邻的）字符组成的字符串。准确地说，n-gram 是从单词中提取的 n 个连续字符的集合。这种方法背后的主要思想是，相似的单词将拥有很大比例的共同 n-gram。一些词干提取技术使用 n-gram 上下文来选择单词的正确词干。当 n 等于 2 或 3 时，提取的单词是二元图或三元图。

例如： 'INTRODUCTIONS' 当 n=2 时变为：*I, IN, NT, TR, RO, OD, DU, UC, CT, TI, IO, ON, NS, S*

当 n=3 时变为：**I, *IN, INT, NTR, TRO, ROD, ODU, DUC, UCT, CTI, TIO, ION, ONS, NS*, S**

其中 '*' 表示填充空格，包含 n 个字符的单词中有 n+1 个这样的二元图和 n+2 个这样的三元图。大多数词干提取器都是语言特定的。通常，n 的值选择为 4 或 5。然后，分析文本数据或文档中的所有 n-gram。

显然，单词的词根通常比其形态变体出现的频率低。这意味着单词通常带有词缀。可以使用基于逆文档频率 (IDF) 的典型统计分析来识别它们。

优点： 基于字符串比较，且与语言无关，因此在许多应用中非常有用。

缺点： 需要大量的内存和存储空间来创建和存储 n-gram 和索引。因此，它不是时间效率高或非常实用的方法。

HMM 词干提取器

该词干提取器基于隐马尔可夫模型 (HMM) 的概念，即有限状态自动机，其中概率函数控制状态之间的转换。每个状态在每次转换时以给定概率发出一个符号。

将 HMM 应用于词干提取时，形成单词的字母序列可以被视为两个子序列的连接结果：前缀和后缀。可以计算每个路径的概率，并使用 Viterbi 编码在自动机图中找到最可能的路径。此方法基于无监督学习，不需要数据集的先验语言知识。

状态之间的转换定义了单词构建过程。

一种对该过程进行建模的方法是通过 HMM，其中状态被分成两个不相交的集合：初始状态只能是词干，而后者可以是词干或后缀。在此方法中可以做出一些假设：

1. 初始状态仅属于词干集——单词总是以词干开头。
2. 从后缀集状态到词干集状态的转换始终具有零概率——单词只能是词干和后缀的连接。
3. 最终状态属于两个集合——词干可以有许多不同的派生，但也可以没有后缀。

对于任何单词，从初始状态到最终状态的最可能路径将产生分割点（从词根到后缀的转换）。然后，该点之前的字符序列可以被认为是词干。

优点： 无监督，因此不需要了解语言。

缺点： 有点复杂，有时可能会过度词干提取单词。

YASS 词干提取器

该名称是 Yet Another Suffix Striper 的缩写。该词干提取器属于统计和基于语料库的类别。它不依赖于语言专业知识。通过对词汇表进行聚类生成的词干提取器，不包含任何语言输入，其性能可与 Porters 等标准的基于规则的词干提取器相媲美。

作者在英语、法语和孟加拉语数据集上进行的检索实验表明，该方法对于主要是后缀性的语言非常有效。聚类使用分层方法和距离度量进行创建。然后，将所得聚类视为等价类，并将其质心视为词干。

3. 屈折和派生方法

这是另一种词干提取方法，它涉及屈折和派生形态分析。在屈折法中，单词变体与特定的语言句法变体相关，如复数、性别、格等。在派生法中，单词变体与单词在句子中出现的词性 (POS) 相关。开发这些类型的词干提取器需要非常大的语料库，因此它们属于基于语料库的词干提取器。

Krovetz 词干提取器 (KSTEM)

Krovetz 词干提取器由 Robert Krovetz 于 1993 年提出，是一种语言学的词汇验证词干提取器。由于它基于单词的屈折属性和语言句法，因此在性质上并不十分简单。它通过三个步骤有效且准确地去除屈折后缀：

1. 将单词的复数转换为单数形式。
2. 将单词的过去时转换为现在时。
3. 删除后缀“ing”。

转换过程首先删除后缀，然后通过在字典中查找任何重编码，将词干返回为单词。字典查找还会执行由于拼写异常所需的任何转换，并将产生的任何词干转换为可理解的有意义的单词。

派生和屈折分析的优势在于它们能够生成形态上正确的词干，处理异常情况，并处理前缀和后缀。由于此词干提取器不查找所有单词变体的词干，因此可以在应用词干提取算法之前将其用作预词干提取器。这将提高主词干提取器的速度和效率。与 Porter 和 Paice / Husk 相比，这是一个非常轻量级的词干提取器。

基于字典的算法的主要明显缺陷是它们无法处理词典中不存在的单词。

Krovetz 词干提取器试图通过处理拼写错误和无意义的词干来提高准确性和鲁棒性。如果输入文档大小很大，此词干提取器会变弱，效果不佳。此外，词典必须预先手动创建，这需要大量工作。此词干提取器无法持续产生良好的召回率和精确率。

Xerox 屈折和派生分析器

Xerox 的语言学团队为英语开发了多种语言学工具，可用于信息检索。他们开发了一个英语词汇数据库，该数据库提供对词汇表中任何单词的形态分析，并确定基本形式。Xerox 的语言学家还为英语和其他一些语言开发了一个词汇数据库，用于分析和生成屈折和派生形态。

屈折数据库将每个表面单词缩减为可以在字典中找到的形式，如下所示：

1. 名词单数（例如，children child）
2. 动词不定式（例如，understood understand）
3. 形容词原级（例如，best good）
4. 代词主格（例如，whom who）

派生数据库将表面形式缩减为在形式和语义上与原始形式相关的词干。例如，“government”缩减为“govern”，而“department”不缩减为“depart”，因为这两种形式具有不同的含义。所有项目都是有效的英语术语，并且可以正确处理不规则形式。与大多数传统的词干提取算法不同，派生过程使用后缀和前缀的移除，仅依赖于后缀的移除。下面给出了一些被移除的后缀和前缀的示例：

后缀： ly, ness, ion, size, ant, ent, ic, al, Ic, ical, able, ance, ary, ate, ce, y, dom, ee, er, ence, ency, ery, ess, ful, hood, ible, icity, ify, ing, ish, ism, ist, istic, ity, ive, less, let, like, ment, ory, ous, ty, ship, some, ure

前缀： anti, bi, co, contra, counter, de, di, dis, en, extra, in, inter, intra, micro, mid, mini, multi, non, over, para, poly, post, pre, pre, re, semi, sub, super, supra, sur, trans, tn, ultra, un

基于语料库的词干提取器

基于语料库的词干提取使用词变体共现。他们提出了一种方法，试图克服 Porter 词干提取器的一些缺点。例如，“policy”和“police”这两个单词被合并，尽管它们的含义不同；而“index”和“indices”这两个单词未被合并，尽管它们具有相同的词根。Porter 词干提取器还会生成不是真实单词的词干，例如“iteration”变成“iter”，而“general”变成“gener”。另一个问题是，虽然某些词干提取算法可能适用于一个语料库，但在另一个语料库上会产生过多的错误。

基于语料库的词干提取是指使用统计方法，根据给定文本语料库的特征自动修改合并类（已产生共同词干的单词）。基本假设是，对于给定的语料库，应合并的词形将在该语料库的文档中共同出现。利用这一概念，可以解决一些过度词干提取或词干提取不足的缺点，例如，“policy”和“police”将不再被合并。

为了确定词形共现的显着性，使用的统计度量是 Em(a, b) = nab / (na + nb)，其中 a 和 b 是单词对，na 和 nb 是 a 和 b 在语料库中的出现次数，nab 是 a 和 b 在大小为 win 的文本窗口中共同出现的次数（它们共现）。

此词干提取器的工作方式是，首先使用 Porter 词干提取器识别合并单词的词干，然后下一步是使用语料库统计来重新定义合并。有时，Krovetz 词干提取器 (KSTEM) 和 Porter 词干提取器会用于初始步骤，以确保不会遗漏单词合并。

优点： 它可以潜在地避免对给定语料库进行不当的合并，结果是真实单词而不是不完整的词干。

缺点： 需要为每个语料库单独开发统计度量。处理时间会增加，因为在第一个步骤中，在使用此方法之前，会先使用两种词干提取算法。

上下文敏感的词干提取器

在此方法中，在索引文档之前进行词干提取。在这里，对于网络搜索，使用查询端的统计建模进行上下文敏感分析。基本上，对于输入查询中的单词，在提交查询给搜索引擎之前，会预测对搜索有用的形态变体。这大大减少了错误扩展的数量，从而降低了额外计算的成本，同时提高了精确度。

在从查询中派生出预测的单词变体后，会对这些变体进行上下文敏感的文档匹配。这种保守的策略可以防止虚假词干提取，并且对于提高精确度非常重要。此词干提取过程在查询被触发后分为四个步骤：

1. 候选生成： 这里使用 Porter 词干提取器从查询词生成词干。这与单词的语义无关。使用基于分布相似性的语料库分析以获得更好的输出。使用分布词相似性意味着真实的变体倾向于在相似的上下文中被使用。
   在分布词相似性计算中，每个单词都用从该单词的上下文派生的特征向量表示。我们使用单词的左侧和右侧的二元图作为其上下文特征，方法是挖掘一个巨大的网络语料库。两个单词之间的相似性是两个相应特征向量之间的余弦相似性。
2. 查询分段和词头检测： 当查询很长时，检测查询的主要概念很重要。查询被分成通常是名词短语的片段。每个名词短语中最重要的单词是词头。词头的查找是通过使用句法分析器完成的。有时会拆分单词以了解上下文。找到两个相邻单词的互信息，如果它超过阈值，则将它们保留在同一段中。
3. 上下文敏感的词扩展： 现在已经获得了词头，就决定使用概率度量哪些词变体最有用的。这是通过语言建模最简单也是最成功的方法完成的，该方法基于 n-gram 模型，该模型使用概率的链式法则。它们是单词的复数形式。
   在此步骤中，将获得所有重要的词头变体。用于网络搜索的词干提取的传统方法是朴素模型。这是将查询中的每个单词变体视为对所有可能单词的等价。查询“book store”将被转换为“(book OR books)(store OR stores)”，如果词干提取仅限于复数处理，其中 OR 是一个运算符，表示左侧和右侧参数的等价性。
   
4. 上下文敏感的文档匹配： 现在我们有了单词变体，只有当变体在文档中的上下文与查询中的原始单词在同一上下文中出现时，才认为变体匹配有效。上下文是原始单词的左侧或右侧非停用词片段。

由于查询和文档可能不以相同的方式表示意图，因此这种邻近约束允许在固定大小的窗口内出现变体。窗口大小越小，匹配的限制性越强。

优点： 它改进了查询端的选择性词扩展和文档端的保守词出现匹配。

缺点： 处理时间和词干提取器的复杂性。在查找查询中的名词短语和邻近单词时可能会出错。