EAPSI: Developing Fast and Accurate Methods for Grouping Objects in a Dataset Using Inconsistent Labels

Veldt Luke N, Lafayette IN

Investigators

Abstract

In today's information-rich age, it is relatively easy to collect large amounts of data when attempting to solve problems and answer questions in almost any field. It is often very challenging, though, to analyze and extract useful information from these datasets, due to their massive size and lack of organization. This project will investigate special techniques for organizing a dataset into groups of similar objects to allow for easier analysis. This task is called clustering, and can be applied in vastly different settings, such as the study of protein interactions in biology, or the categorization of webpages in a large database. The research will be conducted at the University of Melbourne in collaboration with Professor Anthony Wirth. Dr. Wirth is an expert in data analysis and a pioneer in the study of "clustering with advice," a technique for clustering data when the only available information is a list of inconsistent labels that mark data points as "similar" or "dissimilar." In general, exactly solving this clustering problem on a large dataset is slow and computationally expensive. This research aims to explore basic assumptions on the input dataset that can lead to more efficient methods for clustering with inconsistent labels. Developing faster methods for this problem will expand current theoretical understanding of clustering with advice, as well as making this useful technique more achievable in practice. The researcher will apply techniques in integer-constrained linear programming and numerical linear algebra to obtain a solution for the clustering with advice problem when the input data can be represented as a low-rank matrix. The primary objective is to develop a polynomial time algorithm for solving the problem for rank-2 matrices and prove complexity results about this special case of the problem. Obtaining a fast solution under low-rank assumptions sheds light on when an otherwise hard problem becomes tractable in practice, and will stimulate research in showing similar results for other difficult problems. This award under the East Asia and Pacific Summer Institutes program supports summer research by a U.S. graduate student and is jointly funded by NSF and the Australia Academy of Science.