Robust Division in Clustering of Streaming Time Series

• Type: Article in International Scientific Journal
• Date: 2008

Authors

Pedro Pereira Rodrigues (Author) FCUP; Joao Gama (Author) FEP

Journal

Title: Frontiers in Artificial Intelligence and Applications

Vol. 178

Pages: 172-176

ISSN: 0922-6389

Publisher: IOS PRESS

Indexing

ISI Proceedings

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Other information

Authenticus ID: P-004-331

DOI: 10.3233/978-1-58603-891-5-172

Abstract (EN): Online learning algorithms which address fast data streams should process examples at the rate they arrive, using a single scan of data and fixed memory, maintaining a decision model at any time and being able to adapt the model to the most recent data. These features yield the necessity of using approximate models. One problem that usually arises with approximate models is the definition of a minimum number of observations necessary to assure convergence, which implies a high risk since the system may have to decide based only on a small subset of the entire data. One approach is to apply techniques based on the Hoeffding bound to enforce decisions with a confidence level. In divisive clustering of time series, the goal is to find clusters of similar time series over time. In online approaches there are two decisions to make: when to split and how to assign variables to new clusters. We can define a confidence level to both the decision of splitting and the assignment of data variables to new clusters. Previous works have already addressed confident decisions on the moment of split. Our proposal is to include a confidence level to the assignment process. When a split point is reported, creating two new clusters, we can directly assign points which are confidently closer to one cluster than the other, having a different strategy for those variables which do not satisfy the confidence level. In this paper we propose to assign the unsure variables to a third cluster. Experimental evaluation is presented in the context of a recently proposed hierarchical algorithm, assessing the advantages of the proposal, revealing also advantages on memory usage reduction and processing speed. Although this proposal is evaluated under the scope of an existent method, it can be generalized to any divisive procedure.

Language: English

Type (Professor's evaluation): Scientific

Notes: 18Th European Conference on Artificial Intelligence, JUL 21-25, 2008,

No. of pages: 5