AbstractsComputer Science

A Semi-Supervised Approach for Kernel-Based Temporal Clustering

by Rodrigo Araujo




Institution: University of Waterloo
Department:
Year: 2015
Keywords: Semi-supervised clustering; Temporal clustering; Kernel k-means; Temporal segmentation; Semi-supervised kernel k-means
Record ID: 2057931
Full text PDF: http://hdl.handle.net/10012/9265


Abstract

Temporal clustering refers to the partitioning of a time series into multiple non-overlapping segments that belong to k temporal clusters, in such a way that segments in the same cluster are more similar to each other than to those in other clusters. Temporal clustering is a fundamental task in many fields, such as computer animation, computer vision, health care, and robotics. The applications of temporal clustering in those areas are diverse, and include human-motion imitation and recognition, emotion analysis, human activity segmentation, automated rehabilitation exercise analysis, and human-computer interaction. However, temporal clustering using a completely unsupervised method may not produce satisfactory results. Similar to regular clustering, temporal clustering also benefits from some expert knowledge that may be available. The type of approach that utilizes a small amount of knowledge to “guide” the clustering process is known as “semi-supervised clustering.” Semi-supervised temporal clustering is a strategy in which extra knowledge, in the form of pairwise constraints, is incorporated into the temporal data to help with the partitioning problem. This thesis proposes a process to adapt and transform two kernel-based methods into semi-supervised temporal clustering methods. The proposed process is exclusive to kernel-based clustering methods, and is based on two concepts. First, it uses the idea of instance-level constraints, in the form of must-link and cannot-link, to supervise the clustering methods. Second, it uses a dynamic-programming method to search for the optimal temporal clusters. The proposed process is applied to two algorithms, aligned cluster analysis (ACA) and spectral clustering. To validate the advantages of the proposed temporal semi-supervised clustering methods, a comparative analysis was performed, using the original versions of the algorithm and another semi-supervised temporal cluster. This evaluation was conducted with both synthetic data and two real-world applications. The first application includes two naturalistic audio-visual human emotion datasets, and the second application focuses on human-motion segmentation. Results show substantial improvements in accuracy, with minimal supervision, compared to unsupervised and other temporal semi-supervised approaches, without compromising time performance.