机器学习中的 Find S 算法

machine learningdata sciencepython

机器学习算法彻底改变了我们从大量数据中提取有价值的见解和做出明智决策的方式，在众多算法中，Find-S 算法脱颖而出，成为该领域的基本工具。该开创性算法由 Tom Mitchell 开发，在假设空间表示和概念学习中具有重要意义。

Find-S 算法简单高效，因其从标记训练数据中发现和概括模式的能力而备受关注。在本文中，我们深入研究 Find-S 算法的内部工作原理，探索其功能和在现代机器学习范式中的潜在应用。

机器学习中的 Find-S 算法是什么?

S 算法，也称为 Find-S 算法，是一种机器学习算法，旨在根据标记训练数据找到最具体的假设。它从最具体的假设开始，通过结合正例将其概括。它在学习过程中忽略反例。

该算法的目标是通过逐步扩大假设空间直到覆盖所有正例来发现准确表示目标概念的假设。

Find-S 算法中使用的符号

在 Find-S 算法中，通常使用以下符号来表示不同的概念和操作 −

∅(空集) − 此符号表示不存在任何特定值或属性。它通常用于将假设初始化为最具体的概念。
? (不关心) − 问号符号表示属性的"不关心"或"未知"值。当假设需要概括正例中存在的不同属性值时，会使用它。
正例 (+) − 加号代表正例，即标记为正在学习的目标类或概念的实例。
负例 (-) − 减号表示反面例子，即被标记为非目标类别或概念的实例，不应被假设所涵盖。
假设 (h) − 变量 h 表示假设，即基于训练数据学习到的概念或概括。它在整个算法中不断迭代完善。

这些符号有助于表示和操纵假设空间，并在假设细化过程中区分正例和负例。它们有助于捕捉目标概念并将其准确地推广到未见过的实例。

Find-S 算法的内部工作原理

Find-S 算法在假设空间上运行，以根据标记的训练数据找到准确表示目标概念的一般假设。让我们深入研究算法的内部工作原理 −

初始化 − 算法从最具体的假设开始，表示为 h。这个初始假设是最严格的概念，通常不假设任何正面例子。它可以表示为 h = <∅, ∅, ..., ∅>，其中 ∅ 表示每个属性的"不关心"或"未知"值。
迭代过程 − 算法迭代每个训练示例，并根据示例是正面还是负面来细化假设。

对于每个正面训练示例(标记为目标类的示例)，算法通过将其概括为包含属性来更新假设示例。假设涵盖的正例越多，就越具有普遍性。
对于每个负面训练示例(标记为非目标类的示例)，算法都会忽略它，因为假设不应涵盖负面示例。对于负面示例，假设保持不变。

概括 − 处理完所有训练示例后，算法会生成一个最终假设，该假设涵盖所有正面示例，同时排除负面示例。这个最终假设代表了算法从训练数据中学习到的广义概念。

在迭代过程中，算法可能会在假设中引入"无关"符号或占位符(通常表示为"?")，表示在正例中不同的属性。这允许算法通过适应不同的属性值来概括概念。算法发现训练数据中的模式，并提供正在学习的概念的可靠表示。

让我们使用一个实际的例子来探索算法的步骤 -

假设我们有一个动物数据集，它有两个属性:"有毛"和"发出声音"。每只动物都被标记为狗或猫。这是一个示例训练数据集 −

Animal	Has Fur	Makes Sound	Label
Dog	Yes	Yes	Dog
Cat	Yes	No	Cat
Dog	No	Yes	Dog
Cat	No	No	Cat
Dog	Yes	Yes	Dog

要应用 Find-S 算法，我们从最具体的假设开始，记为 h，它最初代表最严格的概念。在我们的示例中，初始假设为 h = <∅, ∅>，表示没有特定动物符合该概念。

对于每个正训练示例(标记为目标类的示例)，我们更新假设 h 以包含该示例的属性。在我们的示例中，正训练示例是狗。因此，h 将更新为 h = <Yes, Yes>。
对于每个负训练示例(标记为非目标类的示例)，我们将其忽略，因为假设 h 不应涵盖这些示例。在我们的例子中，反面的训练样本是猫，由于 h 已经涵盖了狗，所以我们不需要更新假设。
处理完所有训练样本后，我们得到了一个广义的假设，它涵盖了所有正面的训练样本，并排除了负面样本。在我们的例子中，最终假设 h = <Yes, Yes> 准确地代表了狗的概念。

示例

这是一个 Python 程序，说明了 Find-S 算法 −

# Training dataset
training_data = [
   (['Yes', 'Yes'], 'Dog'),
   (['Yes', 'No'], 'Cat'),
   (['No', 'Yes'], 'Dog'),
   (['No', 'No'], 'Cat'),
   (['Yes', 'Yes'], 'Dog')
]

# Initial hypothesis
h = ['∅', '∅']

# Find-S algorithm
for example, label in training_data:
   if label == 'Dog':
      for i in range(len(example)):
         if h[i] == '∅':
            h[i] = example[i]
         elif h[i] != example[i]:
            h[i] = '?'

print("Final hypothesis:", h)