Dendritic Cell Algorithm

Dendritic Cell Algorithm, DCA.

Taxonomy

The Dendritic Cell Algorithm belongs to the field of Artificial Immune Systems, and more broadly to the field of Computational Intelligence. The Dendritic Cell Algorithm is the basis for extensions such as the Deterministic Dendritic Cell Algorithm (dDCA) [Greensmith2008]. It is generally related to other Artificial Immune System algorithms such as the Clonal Selection Algorithm, and the Immune Network Algorithm.

Inspiration

The Dendritic Cell Algorithm is inspired by the Danger Theory of the mammalian immune system, and specifically the role and function of dendritic cells. The Danger Theory was proposed by Matzinger and suggests that the roles of the acquired immune system is to respond to signals of danger, rather than discriminating self from non-self [Matzinger1994] [Matzinger2002]. The theory suggests that antigen presenting cells (such as helper T-cells) activate an alarm signal providing the necessarily co-stimulation of antigen-specific cells to respond. Dendritic cells are a type of cell from the innate immune system that respond to some specific forms of danger signals. There are three main types of dendritic cells: 'immature' that collect parts of the antigen and the signals, 'semi-mature' that are immature cells that internally decide that the local signals represent safe and present the antigen to T-cells resulting in tolerance, and 'mature' cells that internally decide that the local signals represent danger and present the antigen to T-cells resulting in a reactive response.

Strategy

The information processing objective of the algorithm is to prepare a set of mature dendritic cells (prototypes) that provide context specific information about how to classify normal and anomalous input patterns. This is achieved as a system of three asynchronous processes of 1) migrating sufficiently stimulated immature cells, 2) promoting migrated cells to semi-mature (safe) or mature (danger) status depending on their accumulated response, and 3) labeling observed patterns as safe or dangerous based on the composition of the sub-population of cells that respond to each pattern.

Procedure

Algorithm (below) provides pseudocode for training a pool of cells in the Dendritic Cell Algorithm, specifically the Deterministic Dendritic Cell Algorithm. Mature migrated cells associate their collected input patterns with anomalies, whereas semi-mature migrated cells associate their collected input patterns as normal. The resulting migrated cells can then be used to classify input patterns as normal or anomalous. This can be done through sampling the cells and using a voting mechanism, or more elaborate methods such as a 'mature context antigen value' (MCAV) that uses $\frac{M}{Ag}$ (where $M$ is the number of mature cells with the antigen and $Ag$ is the sum of the exposures to the antigen by those mature cells), which gives a probability of a pattern being an anomaly.

Heuristics

• The Dendritic Cell Algorithm is not specifically a classification algorithm, it may be considered a data filtering method for use in anomaly detection problems.
• The canonical algorithm is designed to operate on a single discrete, categorical or ordinal input and two probabilistic specific signals indicating the heuristic danger or safety of the input.
• The danger and safe signals are problem specific signals of the risk that the input pattern is an anomaly or is normal, both typically $\in [0,100]$.
• The danger and safe signals do not have to be reciprocal, meaning they may provide conflicting information.
• The system was designed to be used in real-time anomaly detection problems, not just static problem.
• Each cells migration threshold is set separately, typically $\in [5,15]$

Code Listing

Listing (below) provides an example of the Dendritic Cell Algorithm implemented in the Ruby Programming Language, specifically the Deterministic Dendritic Cell Algorithm (dDCA). The problem is a contrived anomaly-detection problem with ordinal inputs $x \in [0,50)$ , where values that divide by 10 with no remainder are considered anomalies. Probabilistic safe and danger signal functions are provided, suggesting danger signals correctly with $P(danger)=0.70$, and safe signals correctly with $P(safe)=0.95$.

The algorithm is an implementation of the Deterministic Dendritic Cell Algorithm (dDCA) as described in [Stibor2009] [Greensmith2008], with verification from [Greensmith2006a]. The algorithm was designed to be executed as three asynchronous processes in a real-time or semi-real time environment. For demonstration purposes, the implementation separated out the three main processes and executed the sequentially as a training and cell promotion phase followed by a test (labeling phase).

def rand_in_bounds(min, max)
  return  min + ((max-min) * rand())
end

def random_vector(search_space)
  return Array.new(search_space.size) do |i|
    rand_in_bounds(search_space[i][0], search_space[i][1])
  end
end

def construct_pattern(class_label, domain, p_safe, p_danger)
  set = domain[class_label]
  selection = rand(set.size)
  pattern = {}
  pattern[:class_label] = class_label
  pattern[:input] = set[selection]
  pattern[:safe] = (rand() * p_safe * 100)
  pattern[:danger] = (rand() * p_danger * 100)
  return pattern
end

def generate_pattern(domain, p_anomaly, p_normal, prob_create_anom=0.5)
  pattern = nil
  if rand() < prob_create_anom
    pattern = construct_pattern("Anomaly", domain, 1.0-p_normal, p_anomaly)
    puts ">Generated Anomaly [#{pattern[:input]}]"
  else
    pattern = construct_pattern("Normal", domain, p_normal, 1.0-p_anomaly)
  end
  return pattern
end

def initialize_cell(thresh, cell={})
  cell[:lifespan] = 1000.0
  cell[:k] = 0.0
  cell[:cms] = 0.0
  cell[:migration_threshold] = rand_in_bounds(thresh[0], thresh[1])
  cell[:antigen] = {}
  return cell
end

def store_antigen(cell, input)
  if cell[:antigen][input].nil?
    cell[:antigen][input] = 1
  else
    cell[:antigen][input] += 1
  end
end

def expose_cell(cell, cms, k, pattern, threshold)
  cell[:cms] += cms
  cell[:k] += k
  cell[:lifespan] -= cms
  store_antigen(cell, pattern[:input])
  initialize_cell(threshold, cell) if cell[:lifespan] <= 0
end

def can_cell_migrate?(cell)
  return (cell[:cms]>=cell[:migration_threshold] and !cell[:antigen].empty?)
end

def expose_all_cells(cells, pattern, threshold)
  migrate = []
  cms = (pattern[:safe] + pattern[:danger])
  k = pattern[:danger] - (pattern[:safe] * 2.0)
  cells.each do |cell|
    expose_cell(cell, cms, k, pattern, threshold)
    if can_cell_migrate?(cell)
      migrate << cell
      cell[:class_label] = (cell[:k]>0) ? "Anomaly" : "Normal"
    end
  end
  return migrate
end

def train_system(domain, max_iter, num_cells, p_anomaly, p_normal, thresh)
  immature_cells = Array.new(num_cells){ initialize_cell(thresh) }
  migrated = []
  max_iter.times do |iter|
    pattern = generate_pattern(domain, p_anomaly, p_normal)
    migrants = expose_all_cells(immature_cells, pattern, thresh)
    migrants.each do |cell|
      immature_cells.delete(cell)
      immature_cells << initialize_cell(thresh)
      migrated << cell
    end
    puts "> iter=#{iter} new=#{migrants.size}, migrated=#{migrated.size}"
  end
  return migrated
end

def classify_pattern(migrated, pattern)
  input = pattern[:input]
  num_cells, num_antigen = 0, 0
  migrated.each do |cell|
    if cell[:class_label] == "Anomaly" and !cell[:antigen][input].nil?
      num_cells += 1
      num_antigen += cell[:antigen][input]
    end
  end
  mcav = num_cells.to_f / num_antigen.to_f
  return (mcav>0.5) ? "Anomaly" : "Normal"
end

def test_system(migrated, domain, p_anomaly, p_normal, num_trial=100)
  correct_norm = 0
  num_trial.times do
    pattern = construct_pattern("Normal", domain, p_normal, 1.0-p_anomaly)
    class_label = classify_pattern(migrated, pattern)
    correct_norm += 1 if class_label == "Normal"
  end
  puts "Finished testing Normal inputs #{correct_norm}/#{num_trial}"
  correct_anom = 0
  num_trial.times do
    pattern = construct_pattern("Anomaly", domain, 1.0-p_normal, p_anomaly)
    class_label = classify_pattern(migrated, pattern)
    correct_anom += 1 if class_label == "Anomaly"
  end
  puts "Finished testing Anomaly inputs #{correct_anom}/#{num_trial}"
  return [correct_norm, correct_anom]
end

def execute(domain, max_iter, num_cells, p_anom, p_norm, thresh)
  migrated=train_system(domain, max_iter, num_cells, p_anom, p_norm, thresh)
  test_system(migrated, domain, p_anom, p_norm)
  return migrated
end

if __FILE__ == $0
  # problem configuration
  domain = {}
  domain["Normal"] = Array.new(50){|i| i}
  domain["Anomaly"] = Array.new(5){|i| (i+1)*10}
  domain["Normal"] = domain["Normal"] - domain["Anomaly"]
  p_anomaly = 0.70
  p_normal = 0.95
  # algorithm configuration
  iterations = 100
  num_cells = 10
  thresh = [5,15]
  # execute the algorithm
  execute(domain, iterations, num_cells, p_anomaly, p_normal, thresh)
end

References

Primary Sources

The Dendritic Cell Algorithm was proposed by Greensmith, Aickelin and Cayzer describing the inspiring biological system and providing experimental results on a classification problem [Greensmith2005]. This work was followed shortly by a second study into the algorithm by Greensmith, Twycross, and Aickelin, focusing on computer security instances of anomaly detection and classification problems [Greensmith2006].

Learn More

The Dendritic Cell Algorithm was the focus of Greensmith's thesis, which provides a detailed discussion of the methods abstraction from the inspiring biological system, and a review of the technique's limitations [Greensmith2007]. A formal presentation of the algorithm is provided by Greensmith et al. [Greensmith2006a]. Greensmith and Aickelin proposed the Deterministic Dendritic Cell Algorithm (dDCA) that seeks to remove some of the stochastic decisions from the method, and reduce the complexity and to make it more amenable to analysis [Greensmith2008]. Stibor et al. provide a theoretical analysis of the Deterministic Dendritic Cell Algorithm, considering the discrimination boundaries of single dendrite cells in the system [Stibor2009]. Greensmith and Aickelin provide a detailed overview of the Dendritic Cell Algorithm focusing on the information processing principles of the inspiring biological systems as a book chapter [Greensmith2009].

Bibliography

Please Note: This content was automatically generated from the book content and may contain minor differences.