Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Clustering Without (Thinking About) Triangulation
Denise Draper
Abstract:
The undirected technique for evaluating belief networks [Jensen, et.al., 1990, Lauritzen and Spiegelhalter, 1988] requires clustering the nodes in the network into a junction tree. In the traditional view, the junction tree is constructed from the cliques of the moralized and triangulated belief network: triangulation is taken to be the primitive concept, the goal towards which any clustering algorithm (e.g. node elimination) is directed. In this paper, we present an alternative conception of clustering, in which clusters and the junction tree property play the role of primitives: given a graph (not a tree) of clusters which obey (a modified version of) the junction tree property, we transform this graph until we have obtained a tree. There are several advantages to this approach: it is much clearer and easier to understand, which is important for humans who are constructing belief networks; it admits a wider range of heuristics which may enable more efficient or superior clustering algorithms; and it serves as the natural basis for an incremental clustering scheme, which we describe.
Keywords: Clustering algorithms, incremental clustering algorithms, triangulation.
Pages: 125-133
PS Link: ftp://ftp.cs.washington.edu/pub/ai/cluster-uai95.ps.Z
PDF Link: /papers/95/p125-draper.pdf
BibTex:
@INPROCEEDINGS{Draper95,
AUTHOR = "Denise Draper ",
TITLE = "Clustering Without (Thinking About) Triangulation",
BOOKTITLE = "Proceedings of the Eleventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-95)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1995",
PAGES = "125--133"
}


hosted by DSL   •   site info   •   help