This paper addresses the problem of predicting the k events that are most likely to occur next, over historical real-time event streams. Existing approaches to causal prediction queries have a number of limitations. First, they exhaustively search over an acyclic causal network to find the most likely k effect events; however, data from real event streams frequently reflect cyclic causality. Second, they contain conservative assumptions intended to exclude all possible non-causal links in the causal network; it leads to the omission of many less-frequent but important causal links. We overcome these limitations by proposing a novel event precedence model and a run-time causal inference mechanism. The event precedence model constructs a first order absorbing Markov chain incrementally over event streams, where an edge between two events signifies a temporal precedence relationship between them, which is a necessary condition for causality. Then, the run-time causal inference mechanism learns causal relationships dynamically during query processing. This is done by removing some of the temporal precedence relationships that do not exhibit causality in the presence of other events in the event precedence model. This paper presents two query processing algorithms -- one performs exhaustive search on the model and the other performs a more efficient reduced search with early termination. Experiments using two real datasets (cascading blackouts in power systems and web page views) verify the effectiveness of the probabilistic top-k prediction queries and the efficiency of the algorithms. Specifically, the reduced search algorithm reduced runtime, relative to exhaustive search, by 25-80 (depending on the application) with only a small reduction in accuracy.
In addition, there has been some work (e.g., @cite_40 @cite_34 @cite_19 ) to support Bayesian network which aims to handle the cyclic causality in Bayesian networks. This work, however, still carries the drawbacks inherent in the Bayesian network approach -- that is, the ambiguity of equivalence classes and the inability to meet the requirement of a causal network that the parent node in the network should always represent the direct cause -- and hence is not useful in our work.
@cite_19 @cite_40 @cite_34
1586497982 372138008 878863653
Although undirected cycles in directed graphs of Bayesian belief networks have been thoroughly studied, little attention has so far been given to a systematic analysis of directed (feedback) cycles. In this paper we propose a way of looking at those cycles; namely, we suggest that a feedback cycle represents a family of probabilistic distributions rather than a single distribution (as a regular Bayesian belief network does). A non-empty family of distributions can be explicitly represented by an ideal of conjunctions with interval estimates on the probabilities of its elements. This ideal can serve as a probabilistic model of an expert's uncertain knowledge pattern; such models are studied in the theory of algebraic Bayesian networks. The family of probabilistic distributions may also be empty; in this case, the probabilistic assignment over cycle nodes is inconsistent. We propose a simple way of explicating the probabilistic relationships an isolated directed cycle contains, give an algorithm (based on linear programming) of its consistency checking, and establish a lower bound of the complexity of this checking. The first comprehensive overview of preprocessing, mining, and postprocessing of biological dataMolecular biology is undergoing exponential growth in both the volume and complexity of biological dataand knowledge discovery offers the capacity to automate complex search and data analysis tasks. This book presents a vast overview of the most recent developments on techniques and approaches in the field of biological knowledge discovery and data mining (KDD)providing in-depth fundamental and technical field information on the most important topics encountered.Written by top experts, Biological Knowledge Discovery Handbook: Preprocessing, Mining, and Postprocessing of Biological Data covers the three main phases of knowledge discovery (data preprocessing, data processingalso known as data miningand data postprocessing) and analyzes both verification systems and discovery systems.BIOLOGICAL DATA PREPROCESSINGPart A: Biological Data ManagementPart B: Biological Data ModelingPart C: Biological Feature ExtractionPart D Biological Feature SelectionBIOLOGICAL DATA MININGPart E: Regression Analysis of Biological DataPart F Biological Data ClusteringPart G: Biological Data ClassificationPart H: Association Rules Learning from Biological DataPart I: Text Mining and Application to Biological DataPart J: High-Performance Computing for Biological Data MiningCombining sound theory with practical applications in molecular biology, Biological Knowledge Discovery Handbook is ideal for courses in bioinformatics and biological KDD as well as for practitioners and professional researchers in computer science, life science, and mathematics.