Kiri Wagstaff <wkiri@CS.Cornell.EDU>
http://www.cs.cornell.edu/home/wkiri

Title: Constrained Clustering with Background Knowledge

Abstract:

Unsupervised machine learning algorithms have had some impressive
successes.  For example, the Autoclass program analyzed a large body
of infrared spectral data and discovered a sub-class of stars
previously unknown to astronomers.  Data mining algorithms are
regularly used in the corporate world to extract useful information
from large customer data bases.  However, the majority of these
algorithms are limited in what they can achieve.  They can detect
general trends and patterns in data, but they cannot make use of
additional knowledge specific to the problem at hand, as a human
expert would.

Our work focuses on enhancing clustering algorithms so that they can
take advantage of background knowledge to improve accuracy.  In
particular, we have developed two modified clustering algorithms which
can take as input a set of instance-level constraints about the
relationships between items in the data set.  These constraints are
preserved in the final output clusters.

In this talk, I will present an overview of these algorithms and
results obtained from applying them to two challenging real-world
problems.  The first deals with analyzing text to determine which noun
phrases are coreferent (for example, in the first sentence of this
paragraph, "them" is coreferent with "these algorithms").  The second
problem involves processing vehicle GPS data to automatically
determine where road lane boundaries are.  This enables greatly
improved road maps and computer-generated driving directions; it also
represents a step towards the future goal of computers that are
sophisticated enough to drive cars themselves.