16. Miscellaneous Algorithms
Society for Industrial and Applied Mathematics eBooks · 2007
This chapter introduces some miscellaneous clustering algorithms, including algorithms for clustering time series data, data streams, and transaction data. 16.1 Time Series Clustering Algorithms As an independent exploratory technique or a subroutine in more complex data mining algorithms such as indexing (Hetland, 2004; Keogh et al., 2001; Li et al., 1998), rule discovery (Das et al., 1998; Tsumoto, 1999; Caraça-Valente and López-Chavarrías, 2000; Chiu et al., 2003), and classification (Cotofrei and Stoffel, 2002), time series clustering has attracted much attention. In general, the time series data to be clustered can be classified into two categories: many individual time series and a single time series. This leads to two categories of clusterings: whole clustering and subsequence clustering (Keogh et al., 2003). The notion of whole clustering is similar to the conventional clustering discussed in previous chapters. Precisely, given a set of individual time series, the objective is to group these time series into clusters such that time series from the same cluster are more similar to each other than time series from different clusters. Subsequence clustering means clustering a single time series. Given a single time series, subsequences are extracted with a sliding window and then subsequence clustering is performed on the extracted subsequences. Subsequence clustering is commonly used as a subroutine in algorithms such as indexing, rule discovery, prediction, anomaly detection, and classification (Keogh et al., 2003). Keogh et al. (2003) and Lin et al. (2003) showed that subsequence clustering of time series is meaningless, where “meaningless” means that the clustering output is independent of the input. This invalidates the contributions of dozens of previously published papers that use subsequence clustering. The authors also gave several conditions that must be satisfied for subsequence clustering to be meaningful. Assume that a time series contains k approximately or exactly repeated patterns of length w with k and w known in advance.