Dendritic Cell AlgorithmDendritic Cell Algorithm, DCA. TaxonomyThe 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. InspirationThe 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 nonself [Matzinger1994] [Matzinger2002]. The theory suggests that antigen presenting cells (such as helper Tcells) activate an alarm signal providing the necessarily costimulation of antigenspecific 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, 'semimature' that are immature cells that internally decide that the local signals represent safe and present the antigen to Tcells resulting in tolerance, and 'mature' cells that internally decide that the local signals represent danger and present the antigen to Tcells resulting in a reactive response. StrategyThe 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 semimature (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 subpopulation of cells that respond to each pattern. ProcedureAlgorithm (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 semimature 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. Input :
InputPatterns , $iterations_{max}$, $cells_{num}$, $MigrationThresh_{bounds}$
Output :
MigratedCells
ImmatureCells $\leftarrow$ InitializeCells ($cells_{num}$, $MigrationThresh_{bounds}$)MigratedCells $\leftarrow$ $\emptyset$For ($i=1$ To $iterations_{max}$)$P_i$ $\leftarrow$ SelectInputPattern (InputPatterns )$k_i$ $\leftarrow$ ($Pi_{danger}$ – 2 $\times$ $Pi_{safe}$) $cms_i$ $\leftarrow$ ($Pi_{danger}$ + $Pi_{safe}$) For ($Cell_i$ $\in$ ImmatureCells )UpdateCellOutputSignals ($Cell_i$, $k_i$, $cms_i$)StoreAntigen ($Cell_i$, $Pi_{antigen}$)If ($Celli_{lifespan}$ $\leq$ $0$)ReInitializeCell ($Cell_i$)ElseIf ($Celli_{csm}$ $\geq$ $Celli_{thresh}$)RemoveCell (ImmatureCells , $Cell_i$)ImmatureCells $\leftarrow$ CreateNewCell ($MigrationThresh_{bounds}$)If ($Celli_{k}$ < $0$)$Celli_{type}$ $\leftarrow$ Mature Else $Celli_{type}$ $\leftarrow$ Semimature End MigratedCells $\leftarrow$ $Cell_i$End End End Return (MigratedCells )Heuristics
Code ListingListing (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 anomalydetection 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 realtime or semireal 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 + ((maxmin) * 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.0p_normal, p_anomaly) puts ">Generated Anomaly [#{pattern[:input]}]" else pattern = construct_pattern("Normal", domain, p_normal, 1.0p_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.0p_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.0p_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 Download: dendritic_cell_algorithm.rb.
ReferencesPrimary SourcesThe 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 MoreThe 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

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


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

Do you like Clever Algorithms? Buy the book now. 