Rare category exploration via wavelet analysis: Theory and applications

• We propose a novel approach RCEWA for RCE which achieves a linear time complexity.
• We provide theoretical proofs for the effectiveness of using wavelet analysis for RCE.
• Experiments show that RCEWA outperforms the existing algorithms w.r.t. F-score.

Rare category exploration (in short as RCE) aims to discover all the remaining data examples of a rare category from a known data example of the rare category. A few approaches have been proposed to address this problem. Most of them, however, are on quadratic or even cubic time complexities w.r.t. data set size n. More importantly, the F-scores (harmonic mean of precision and recall) of the existing approaches are not satisfactory. Compared with the existing solutions to RCE, this paper proposes a novel approach with a linear time complexity and achieves a higher F-score of mining results. The key steps of our approach are to reduce search space by performing wavelet analysis on the data density function, and then refine the coarse mining result in the reduced search space via fine-grained metrics. A solid theoretical analysis is conducted to prove the feasibility of our solution, and extensive experiments on real data sets further verify its effectiveness and efficiency.