Non-derivable itemsets for fast outlier detection in large high-dimensional categorical data

    Authors

    A. Koufakou; J. Secretan;M. Georgiopoulos

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Knowl. Inf. Syst.

    Keywords

    Outlier detection; Anomaly detection; Frequent itemset mining; Non-Derivable itemsets; Categorical datasets; DATA SETS; ALGORITHMS; Computer Science, Artificial Intelligence; Computer Science, Information; Systems

    Abstract

    Detecting outliers in a dataset is an important data mining task with many applications, such as detection of credit card fraud or network intrusions. Traditional methods assume numerical data and compute pair-wise distances among points. Recently, outlier detection methods were proposed for categorical and mixed-attribute data using the concept of Frequent Itemsets (FIs). These methods face challenges when dealing with large high-dimensional data, where the number of generated FIs can be extremely large. To address this issue, we propose several outlier detection schemes inspired by the well-known condensed representation of FIs, Non-Derivable Itemsets (NDIs). Specifically, we contrast a method based on frequent NDIs, FNDI-OD, and a method based on the negative border of NDIs, NBNDI-OD, with their previously proposed FI-based counterparts. We also explore outlier detection based on Non-Almost Derivable Itemsets (NADIs), which approximate the NDIs in the data given a delta parameter. Our proposed methods use a far smaller collection of sets than the FI collection in order to compute an anomaly score for each data point. Experiments on real-life data show that, as expected, methods based on NDIs and NADIs offer substantial advantages in terms of speed and scalability over FI-based Outlier Detection method. What is significant is that NDI-based methods exhibit similar or better detection accuracy compared to the FI-based methods, which supports our claim that the NDI representation is especially well-suited for the task of detecting outliers. At the same time, the NDI approximation scheme, NADIs is shown to exhibit similar accuracy to the NDI-based method for various delta values and further runtime performance gains. Finally, we offer an in-depth discussion and experimentation regarding the trade-offs of the proposed algorithms and the choice of parameter values.

    Journal Title

    Knowledge and Information Systems

    Volume

    29

    Issue/Number

    3

    Publication Date

    1-1-2011

    Document Type

    Article

    Language

    English

    First Page

    697

    Last Page

    725

    WOS Identifier

    WOS:000297131000007

    ISSN

    0219-1377

    Share

    COinS