A non-parametric heuristic algorithm for convex and non-convex data clustering based on equipotential surfaces

摘要

In this paper, using the concepts of field theory and potential functions a sub-optimal non-parametric algorithm for clustering of convex and non-convex data is proposed. For this purpose, equipotential surfaces, created by interaction of the potential functions, are applied. Equipotential surfaces are the geometric location of the points in the space on which the potential is constant. It means all points in each surface were affected the same by the field. Regarding this concept and other characteristics of equipotential surfaces, the outcome of this method will be an optimal solution for the clustering problem. But with regard to the existence of several parameters requiring to be set in the algorithm, finding the global optimal solution leads to a high computational complexity and therefore is not practical. Thus by applying some considerations and approximations, the resulting outcome will be a sub-optimal solution, while appropriate setting of the parameters causes the result to be closer to the global optimal solution. The advantage of this method is that it does not need any external parameter setting, such as number of clusters. To this end, an automatic parameter setting algorithm is suggested based on an optimal clustering index. Simulation results for a number of standard datasets, illustrate the superb performance of this method, especially for non-convexly scattered data. All mentioned characteristics of this method are widely demanded in different scientific areas. In this case it has been utilized in the well-known Point Location Problem (PLP) to reduce computational complexity.