Advancements in computational situation assessment with dynamic graph-based procedures.

摘要

Chapter 1 of this dissertation presents a new Information Fusion reference model, termed the Decision Framed Fusion Model (DFFM) which relates computerized information fusion products to an empirically validated formalization of the cognitive Situation Assessment process. It is not the goal of the reference model to define how people should make decisions, or even how they do make decisions, but rather reference an empirically validated framework of their understanding of the environment (Endsley's Model of Situation Awareness) in a more general reference model so we can then define fusion product in those terms. By defining fusion product in these terms, we are making a claim to why given fusion processes should be considered as different "levels", and that claim is that they are providing a product of a type which addresses a different function within the cognitive situation assessment process and therefore a different utility to the overall decision making process.;Chapter 2 discusses the concept of representing data and information as graphs, and why graph-based analytical methods are important for Situation Assessment. In the most general sense, the problem addressed by the work in this dissertation is on improving cognitive Situational Assessment through improving a decision maker's understanding of current situations (DFFM level A fusion). The more specific problem definition is in finding patterns in large graphs of data. Graphs can theoretically represent any type of information, but differ in their strengths and weaknesses as a representation choice depending on the characteristics of the data being represented. Graphs can grow to sizes non-interpretable by a human so pattern detection approaches are typically used to process the large graphs for meaningful information. In this sense, the defined patterns and occurrences of those patterns in the data become the actionable information expressed by a decision maker.;Chapter 3 introduces Information Fusion Engine for Real-time Decision Making (INFERD). INFERD input patterns are modeled in a graph-based language construct called a Guidance Template. The Guidance Template language is an extension of the directed attributed relational graph (DARG) language to include special types of nodes, and a constraint language to replace the normal sense of an attribute. The novelty of INFERD is in its use of the Guidance Template to detect graph-based patterns of information in non-graph based streaming data. The construction of Guidance Templates is non-intuitive due to this syntactic representational difference between the pattern definition to detect and the data in which it may be present.;In Chapter 4, Incremental Subgraph Isomorphism System (ISIS) is introduced as an enhancement to a batched inexact subgraph isomorphism procedure called Truncated Search Trees (TruST) and shown to be a bounded incremental algorithm meaning that its runtime is a function of the size of the change in the data graph. ISIS results are shown to be equal to that of TruST with large improvements in runtime for graphs even in the size range of thousands of nodes. This new enhancement not only allows subgraph isomorphism procedures to be applied to new types of problems, but also allows graphs which were previously unable to fit within memory constraints to be decomposed into subgraphs and processed sequentially without the quality of results being affected.;Chapter 5 will introduce semantic enhancements to ISIS which helps to overcome syntactic inconsistencies between an expressed pattern and its underlying representation in the data graph, under the condition that they are semantically equivalent. Combining predicate logics and inference mechanisms with patterns expressed in a DARG language enhance the explicit expressiveness of the patterns which can be exploited by procedures to resolve the syntactic inconsistencies and not penalize match results under the condition that there is semantic consistency. Implementation and performance evaluation of ISIS semantic enhancements will be left for future work.;In conclusion it is shown that in the application of cyber network situational awareness, INFERD was successful at detecting graph based patterns in non graph-based data, outperforming Bayesian, game theoretic, and expert systems against a set of defined metrics. It is also shown that ISIS is a bounded incremental subgraph isomorphism algorithm under graph additions, successfully outperforming TruST by orders of magnitude in runtime while keeping identical results under the testing of randomly generated graphs of varying sizes. (Abstract shortened by UMI.)