Outlier detection in transactional data

Article type: Research Article

Authors: Dash, Manoranjan^{; *} | Lie, Ng Wil

Affiliations: School of Computer Engineering, Nanyang Technological University, Singapore

Correspondence: [*] Corresponding author. Tel.: +65 67906167; Fax: +65 67926559; E-mail: asmdash@ntu.edu.sg

Abstract: Outlier detection is studied in the context of supervised (with class label) and unsupervised (without class label – e.g., clustering) data. To the best of our knowledge there has been no study on outlier detection in transactional database, e.g. market basket data where each transaction has a number of items and the number of items in each transaction is not constant. Following the definition of outlier by Barnett and Lewis, 1994, we define an outlier transaction in this paper as that which appears to deviate markedly from other transactions of the database in which it occurs. This problem is important, for instance a supermarket manager would like to know the outlier transactions so as to make proper decisions. This problem is not trivial particularly when the number of items is large which is often the case in market basket data. We propose a novel and efficient solution DETACH which is different from other work in this area. The proposed method uses a unique approach of creating a representative sample, and subsequently it determines the degree to which each transaction is an outlier considering the representative sample. The proposed method, unlike its predecessors, does not require any parameter that is hard to set. We test our proposed method using benchmark market basket data from QUEST project. Results show that DETACH is very efficient and accurate.

Keywords: Outlier detection, transactional data, ε-approximation, sampling

DOI: 10.3233/IDA-2010-0422

Journal: Intelligent Data Analysis, vol. 14, no. 3, pp. 283-298, 2010