Segmented Nestedness in Binary Data

Lecturer : 
Esa Junttila
Event type: 
HIIT seminar
Event time: 
2011-03-25 10:15 to 11:00
Kumpula Exactum C222

Talk announcement:
HIIT Seminar Kumpula, Friday March 25 10:15, Exactum C222

Esa Junttila
University of Helsinki

Segmented Nestedness in Binary Data

Given a data matrix, we can reveal its hidden structure
by permuting the rows and columns. A binary dataset is
nested if every row is a subset or superset of every other row.
Our goal is to develop automatic methods for finding whether
a dataset can be described as a combination of k nested patterns,
even if the data contains noise and errors.
Recognizing k-nestedness takes polynomial time in noise-free case,
but finding a closest k-nested matrix is NP-hard.
We propose heuristic algorithms for k-nestedness
and an MDL-based model for selecting k. Experimental
results show that k-nestedness exists in real-world
datasets, such as in occurrences of mammals in Europe.

--Matti Järvisalo

Last updated on 16 Mar 2011 by Matti Järvisalo - Page created on 16 Mar 2011 by Matti Järvisalo