CONVEX HULL BASED CLUSTERING ALGORITHM

Abstract

The use of computational geometry methods in the field of data classification is a recent practice especially those based on the convex hull computation. In the literature, there are some works that address this kind of problems. Most of these studies apply the convex hull for an offline clustering which assumes dense sampling in advance and requires some
times labeled training set. In this paper, we propose a dynamic convex hull based clustering algorithm dealing with data appearing sequentially. Considering that classification is the task of assigning a test object to one among two or several possible clusters, an intuitive way to proceed is to restrict clusters to be combinations of vertices of the convex hull
containing the data set. This hull gives rather an approximation to the cluster region. The classification process is achieved by evaluating the variation of the data density of that region. An additional merge mechanism is proposed to avoid local optima drawbacks and improve performances. The developed algorithm is assessed at first on some empirical data and then it is applied for the monitoring of a complex system to illustrate its efficiency in real time applications.