Graphical Models: Methods for Data Analysis and Mining. (Book Reviews)

Article excerpt

Christian BORGELT and Rudolf KRUSE. New York: Wiley, 2002. ISBN 0-470-84337-3. viii+ 358 pp. $79.95 (H).

In their prefatory overview to the volume Applications of Uncertainty Formalisms, Parsons and Hunter (1998) distinguished the three main numerical approaches to approximate reasoning under conditions of uncertainty: probability theory (e.g., Lindley 1975), evidence theory (Dempster 1968), and possibility theory (Zadeh 1978). Graphical Models: Methods for Data Analysis and Mining is a fairly thorough overview of the theory of graphical models, with a focus on the use of possibility measures to characterize uncertainty in the building and interpretation of these models.

The first chapter provides definitions of knowledge discovery in databases (KDD) and data mining, with brief reference lists and URLs for catalogs of related tools. In the second chapter, a five-page sketch of relational algebra and conditional probability is followed by 30 pages on possibility theory and the context model. This includes several simple examples, conducted with special dice, to compare the inferences achievable using probability and possibility measures. [For readers who have not encountered possibility theory, a key characterization is [PI](A U B) = max([PI](A), [PI](B)) and [PI](A ** B) = min({PI](A), [PI](B)), where A and B are any fuzzy subsets of a fuzzy universe governed by a possibility measure [PI].] This chapter is a reasonable mix of formalism and illustrative simple examples.

Chapter 3, "Decomposition," includes a fairly formal treatment of relational algebra sufficient to define the minimal decomposition of a relation. Relational algebra concepts are then connected with binary possibility measures to construct concepts of conditional possibility and conditional relational independence that are analogous to central concepts of probability theory for graphical models. Conditional probability and factorization of probability models are defined, and general possibilistic decompositions are developed. The chapter concludes with a section titled "Possibility versus Probability" that includes the following:

In other words, a marginal probability distribution states "the probability that attribute A has value a is p." This probability is aggregated over all values of all other attributes and thus refers to a one element vector (a). A marginal possibility distribution instead states "the degree of possibility of a value vector with the highest degree of possibility of all tuples in which attribute A has value a is p." That is, it refers to a value vector over all attributes of the universe of discourse, although the values of all attributes other than A are left implicit.

This is perhaps the most focused statement on the contrast between the possibilistic and probabilistic frameworks found in the book. It is followed by discussion of a number of caveats for the possibilistic approach.

Chapter 4 provides a formal treatment of graphical representation of statistical models, including the graphoid axioms, proof (deferred to an Appendix) that conditional possibilistic independence satisfies the semigraphoid axioms, graph theory, Markov properties, evidence propagation, and join-tree propagation.

Chapter 5 is a mainly technical treatment of computing projections of relations and marginalizations of distributions The EM algorithm and some accelerations are presented. Examples are reviewed, but the authors note that they "could not get hold of any real-world dataset containing 'true' imprecise attribute values, i.e., datasets with cases in which for an attribute A a set S [member of](A) with \S\ I and S [not equal to](A) was possible." In other words, the authors had access only to datasets in which imprecision coincided with total missingoess. Public datasets with censored variables are available to remedy this gap.

Chapter 6, "Naive Classifiers," describes the naive Bayes classifier (a graphical model with star-like structure) and its application to the iris dataset. …