Title: Annotating Clustering Constraints with Feature Relevance Information

Speaker: Prof. Marie desJardins, University of Maryland Baltimore County
Dept. of Computer Science and Electrical Engineering


Abstract: 

Constrained clustering uses membership constraints between pairs of
data points to improve the performance of clustering algorithms [2].
Previous work in this area has focused on two classes of binary
constraints: MUST-LINK constraints (which indicate that two data
points should be placed in the same cluster) and CANNOT-LINK
constraints (which indicate that two data points should be placed in
different clusters).  One recent constrained clustering algorithm,
MPCK-MEANS [2], integrates such constraints with a metric learning
approach, yielding very good performance in a variety of domains.

In this talk, I will describe our ongoing research to extend
MPCK-MEANS by annotating the constraints with information about
feature relevance.  Specifically, each constraint may include a
feature vector, indicating the degree to which a user (or oracle)
believes that a particular feature is important for generating the
MUST-LINK or CANNOT-LINK constraint that is associated with that pair
of data points.  I will present a method for automatically generating
feature annotations (simulating a domain expert), and will describe
our initial experimental results, which show that feature annotations
can improve clustering performance for a given number of constraints.


[1] Mikhail Bilenko, Sugato Basu, and Raymond J. Mooney, "Integrating
constraints and metric learning in semi-supervised clusetring."  In
Proceedings of the 21st International Conference on Machine Learning
(ICML-2004), pp. 81-88, Banff, Canada, July 2004.

[2]  Kiri Wagstaff, "Intelligent Clustering with Instance-Level
Constraints."  Cornell University Computer Science Ph.D. dissertation,
2002. 


- ------------------

Dr. Marie desJardins is an assistant professor in the Department
of Computer Science and Electrical Engineering at the University of
Maryland, Baltimore County.  Prior to joining the faculty in 2001,
Dr. desJardins was a senior computer scientist at SRI International in
Menlo Park, California.  Her research is in artificial intelligence, 
focusing on the areas of machine learning, multi-agent systems,
planning, interactive AI techniques, information management, reasoning
with uncertainty, and decision theory.

------------------------