A parameter-free approach for one-class classification using binary decision diagrams

Abstract

Parameter tuning is essential in classification problems to achieve a high performance, but it is very hard when it comes to the one-class classification problem. In this paper, we propose a novel one-class classifier whose parameter can be tuned automatically. The proposed classifier can deal with non-linearly distributed data and is robust to noise in training data sets. Moreover, the proposed classifier can be learnt efficiently in the case that a training data set is large, because the computational complexity is approximately linear with respect to the number of training data. In the proposed method, the region of a training data set is expressed as a Boolean formula that is constructed by using a binary decision diagram. Then the region is efficiently over-approximated through the direct manipulation of the binary decision diagram. The parameter of the over-approximation can be tuned automatically based on the minimum description length principle. Experimental results show that the proposed method works very well with synthetic data and some realistic data.