Abstracts Category : Other

A Study on Linkage Pattern Mining in Multiple Sequential Data :

by Saerom Lee

Sequential pattern mining is a promising and effective data mining method for finding frequent patterns in large-scale sequential data. After Agrawal et al. constructed the foundations of sequential pattern mining in 1995, various new effective algorithms have been developed and applied in a wide range of fields. These research aims to detect same or similar subsequences within a single sequential data or among multiple sequential data.Linkage pattern mining is a data mining technique that finds frequent patterns that appear repeatedly across multiple sequential data. Even if frequent patterns occurring in the respective sequential data do not show similarity to each other, the set of those patterns is extracted as a linkage pattern if it appears continually within the same period. Linkage pattern mining is expected to become a useful approach in various fields such as vital data monitoring or voice analysis. However, the existing method has an issue that it can hardly extract linkage patterns in sequential data with noise/fluctuations.The aim of this study is to propose a new noise-robust linkage pattern mining method. The procedure of the proposed method is composed of the following five steps: 1) Normalization and discretization of sequential data, 2) Extracting and labeling frequent patterns from each sequence, 3) generating interval graphs depending on overlapping labels on the time axis, 4) closed itemset mining from the generated interval graphs, 5) outputting the linkage pattern. The main contribution of this study is to extract clear linkage patterns by excluding noise in Step 4). Closed itemset mining can find maximal frequent pattern that co-occurs among the interval graph, and hence pseudo patterns accidentally constructed by noise can be excluded effectively. In this study, we first conduct a grid search for the parameter values of the proposed method, maximum window width and minimum number of occurrences in frequent pattern mining and minimum support in closed itemset mining. As a result, it is shown that these parameter values should be set to small values for high extraction accuracy. Subsequently, performance comparison between the proposed method and the previous method is conducted using artificial sequential datasets. By this experiment, it is shown that the proposed method can significantly improve extraction accuracy of linkage pattern in sequential data with noise as well as those without noise. Furthermore, the proposed method is applied to real ECG (electrocardiogram) data, and the performance is evaluated. In this experiment, a discretization method based on data distribution is newly incorporated into the proposed method in order to deal with the peak in ECG data. As a result, it is shown that the proposed method can extract meaningful linkage patterns that are composed of waves crucial for diagnosis of heart disease. This suggests that the proposed method is available as a new abnormality detector for ECG data.Agrawal