否定选择算法（NSA）

名称

否定选择算法（Negative Selection Algorithm, NSA）

分类

查看分类思维导图

否定选择算法是人工免疫系统（Artificial Immune Systems, AIS）领域中的一种方法，而人工免疫系统又隶属于计算智能（Computational Intelligence）和生物启发计算（Biologically Inspired Computation）范畴。它与其他人工免疫系统算法关系密切，例如克隆选择算法（Clonal Selection Algorithm）和免疫网络算法（Immune Network Algorithm）。

• 计算智能
  • 生物启发计算
    • 人工免疫系统
      • 否定选择算法

策略

否定选择算法受生物免疫系统中 T 细胞成熟过程的启发。该算法生成一组检测器（detectors），用于区分给定数据集中的自体（正常）模式与非自体（异常）模式。

检测器生成

否定选择算法的第一步是生成一组候选检测器。这些检测器通常表示为二进制字符串或实值向量。生成过程可以是随机的，也可以借助启发式策略进行引导，以确保检测器集合具有良好的多样性和分布性。

自体耐受

在生成候选检测器后，算法进入自体耐受阶段。在这一阶段中，每个检测器都要与一组自体样本进行比较，而这些自体样本代表数据集中的正常模式。如果某个检测器与任一自体样本匹配，则将其丢弃。通过这一过程，可以保证保留下来的检测器不会对正常模式产生反应。

异常检测

获得具备自体耐受性的检测器后，就可以将其用于异常检测。对于一个新的模式，每个检测器都会借助匹配函数（例如欧氏距离、汉明距离）与其进行比较。如果任一检测器与该模式匹配，则将其判定为异常（非自体）；否则，将其视为正常（自体）。

过程

1. 初始化算法参数：
   • 定义检测器的表示方式（例如二进制字符串、实值向量）
   • 设定检测器生成机制（例如随机生成、基于启发式的生成）
   • 确定匹配函数所使用的匹配阈值
2. 生成一组候选检测器：
   • 根据选定的表示方式和生成机制创建检测器池
   • 确保检测器能够较充分地覆盖非自体空间
3. 执行自体耐受：
   • 对每个候选检测器：
     • 使用匹配函数将该检测器与每个自体样本进行比较
     • 若该检测器与任一自体样本匹配，则将其丢弃
   • 保留所有不与任何自体样本匹配的检测器
4. 使用具备自体耐受性的检测器进行异常检测：
   • 对每个新模式：
     • 使用匹配函数将该模式与每个检测器进行比较
     • 若任一检测器与该模式匹配，则将其判定为异常（非自体）
     • 否则，将该模式判定为正常（自体）

数据结构

• 检测器（Detectors）：由二进制字符串或实值向量组成的集合，用于表示检测器
• 自体样本（Self Samples）：表示正常（自体）类别的一组模式
• 匹配函数（Matching Function）：用于判定检测器与模式之间相似性的函数（例如欧氏距离、汉明距离）

参数

• 检测器表示方式（Detector Representation）：检测器的编码形式（例如二进制字符串、实值向量）
• 检测器生成机制（Detector Generation Mechanism）：生成候选检测器的方法（例如随机生成、基于启发式的生成）
• 匹配阈值（Matching Threshold）：匹配函数中用于判断检测器是否与某模式匹配的阈值

注意事项

优点

• 能够检测此前未见过的异常：否定选择算法可以识别训练数据中未出现的异常，因此适用于异常稀少或未知的场景。
• 具有适应性：该算法可以通过更新自体样本并重新生成检测器，来适应系统正常行为的变化。
• 具有生物学启发基础：否定选择算法来源于免疫系统机理，这为异常检测提供了较强的理论依据和启发。

缺点

• 可扩展性不足：在处理高维数据或大量自体样本时，算法可能面临可扩展性问题，因为覆盖非自体空间所需的检测器数量可能呈指数增长。
• 参数敏感性较强：算法性能对检测器表示方式、生成机制以及匹配阈值等参数较为敏感，因此需要仔细调参才能获得较优效果。
• 难以处理演化中的异常：如果异常特征会随时间变化，则算法可能需要借助更新后的自体样本重新训练，才能维持其有效性。

启发式建议

检测器生成

• 应使用具有良好多样性的检测器集合，以更有效地覆盖非自体空间。这可以通过随机生成，或引入启发式策略来保证多样性。
• 在生成检测器时，可以考虑引入领域知识。将系统正常行为的先验知识融入生成过程，有助于得到更具针对性的检测器。
• 可尝试不同的检测器表示方式（例如二进制字符串、实值向量），以找到最适合具体问题的表示形式。

匹配函数

• 应根据数据类型和问题领域选择合适的匹配函数。例如，欧氏距离常用于实值数据，而汉明距离更适合二进制数据。
• 可根据灵敏度与特异性的权衡关系调整匹配阈值。较低的阈值会使更多检测器与模式匹配，从而提高灵敏度，但也可能带来更多误报。

自体耐受

• 应确保自体样本能够充分代表系统的正常行为。引入多样且具有代表性的自体样本，有助于算法更有效地学习正常模式。
• 可考虑随时间更新自体样本，以适应系统正常行为的变化。这可以通过定期加入新的自体样本并移除过时样本来实现。

异常检测

• 应对算法检测出的异常进行分析，以获得关于系统行为的更多认识。研究这些异常的特征，有助于发现潜在问题并提升系统整体性能。
• 可考虑将否定选择算法与其他异常检测方法结合使用，以提升整体检测精度。采用集成方法或混合方法，能够借助多种算法实现更稳健的异常检测。