Time series matching: A multi-filter approach.
详细信息
文摘
Data arriving in time order (time series) arises in applications ranging from music and meteorology to finance to motion capture data, to name a few. In many cases, a natural application to investigate the data is to use existing examples as queries to find similar data (Query-by-Example). Usually the example data are naturally generated but artificially collected, thus they contain noise and/or (timing) errors. The characteristics of the errors vary, depending on the types of the applications.;Existing time-warped time series matching algorithms, such as DTW (Dynamic Time Warping), can accommodate certain timing errors in the query and have good accuracy performance on matching query to small database. However, they all have high computational complexity and the accuracy dramatically drops when the data set grows large. Another problem is that the type and amount of time warping may be different for different applications.;Here we present a general time series matching framework. It is a framework to easily explore, train, test and combine different features to do fast similarity search based on the application requirement. Basically we use multi-filter chain and Boosting algorithms to composite a ranking algorithm. Each filter is a classifier which removes bad candidates by comparing certain features on the original time series data. Some filter uses boosting algorithm to combine a few different weak classifiers into a strong classifier. The final filter will give a ranked list of candidates in the reference data which matches the query datum.;The framework is used to build query algorithms for a Query-by-Humming system. Experiments show that the algorithms scales much better when the database song number increases from 50 to 1000 than DTW algorithm. The response time is improved by orders of magnitude and the accuracy performance remains at the same level.