Axioms to characterize efficient incremental clustering

Abstract

Although clustering is one of the central tasks in machine learning for the last few decades, analysis of clustering irrespective of any particular algorithm was not undertaken for a long time. In the recent literature, axiomatic frameworks have been proposed for clustering and its quality. But none of the proposed frameworks has concentrated on the computational aspects of clustering, which is essential in current big data analytics. In this paper, we propose an axiomatic framework for clustering which considers both the quality and the computational complexity of clustering algorithms. The axioms proposed by us necessarily associate the problem of clustering with the important concept of incremental learning and divide and conquer learning. We also propose an order independent incremental clustering algorithm which satisfies all of these axioms in some constrained manner.