Incremental Maintenance on the Border of the Space of Emerging Patterns

    loading  Checking for direct PDF access through Ovid

Abstract

Emerging patterns (EPs) are useful knowledge patterns with many applications. In recent studies on bio-medical profiling data, we have successfully used such patterns to solve difficult cancer diagnosis problems and produced higher classification accuracy when compared to alternative methods. However, the discovery of EPs is a challenging and computationally expensive problem.

In this paper, we study how to incrementally modify and maintain the concise boundary descriptions of the space of all emerging patterns when small changes occur to the data. As EP spaces are convex, the maintenance on the bounds guarantees that no desired patterns are lost. We introduce algorithms to handle four types of changes: insertion of new data, deletion of old data, addition of new attributes, and deletion of old attributes. We compare these incremental algorithms, on six benchmark data sets, against an efficient algorithm that computes from scratch. The results show that the incremental algorithms are much faster than the From-Scratch method, often with tremendous speed-up rates.

Related Topics

    loading  Loading Related Articles