Discovering association patterns in large spatio-temporal databases

Abstract

Data mining is concerned with the discovery of hidden patterns in large databases. Among the different types of patterns that can be discovered, "association" patterns are the most important. This is because the discovery of association patterns can lead more easily to the discovery of other patterns for such data mining tasks as classification, clustering or prediction. Given a set of data collected over a certain time period and over a number of different locations, existing data mining approaches do not provide suitable tools to allow association patterns in such a data set to be easily discovered. The objective of this study is therefore to develop new approaches so that patterns that changes from time-period to time-period and from location to location can be discovered. Making use of techniques in meta-mining, probability and statistics, and such techniques as machine learning and fuzzy logic, our objective is to develop data mining techniques capable of discovering such patterns in spatio-temporal databases. Over the past few years, a considerable number of studies have been made on market basket analysis. Market basket analysis is a useful method for discovering customer purchasing patterns by extracting association from stores' transaction database. In many business of today, customer transactions can be made in many different geographical locations round the clock, especially after e-business and online shops have become prevalent. The traditional methods that consider only the association rules of an individual location or all locations as a whole are not suitable for such a multi-location environment. Understanding and adapting to changes of customer behavior from time to time and from place to place is an important aspect for a company having transactions collected from multi-locations, for example those running business-to-customer (B2C) business, to survive in continuously changing environment. If applied to B2C business, the methodology developed in this study allow companies to detect changes of customer behavior automatically from customer profiles, in which customers may come from different places over the world, and sales data may be inputted at different time snapshots. There are three main contributions in the thesis. Firstly, we design a novel and efficient algorithm for mining spatio-temporal association rules which have multi-level time and location granularities, in spatio-temporal databases. From the perspective of business strategists, the discovered rules also must be readily interpreted for easy reading and further usage, in order to be useful. However, different executive personnel will require different interpretation of the rules in different usage scenarios. And under different granularities of time-and-place, the knowledge will be different. The goal of our work is to satisfy such dynamic needs. In this study, we develop an algorithm that can find association rules under different granularities of time-and-place to satisfy the different demands of different decision makers. Unlike Apriori-like approaches, our method scans the database at most twice. By avoiding multiple scans over the target database, our method can reduce the runtime in scanning database. Secondly, we use membership functions to construct fuzzy calendar-map patterns which represent asynchronous time periods and locations. With the use of fuzzy calendar-map patterns, we can discover fuzzy spatio-temporal association rules which are defined as association rules occur in asynchronous time periods and/or locations. Thirdly, we propose to mine a set of rules from the discovered collection of spatio-temporal rule sets. These meta-rules, rules about rules, represent the kind of knowledge that few existing data mining algorithms have been developed to mine for. In this study, we define problems in discovering the underlying regularities, differences, and changes hidden in spatio-temporal rule sets and propose a new approach, meta-mining spatio-temporal patterns, which mines previous spatio-temporal association rule mining results to discover these underlying regularities, differences, and changes. Experimental results have shown that our methods are more efficient than others, and we can find fuzzy spatio-temporal association rules satisfactorily and so as meta-rules among the set of rules discovered.