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 [email protected]

    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
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.