A new density estimator based on nearest and farthest neighbor

摘要

Usually nearest-neighbor density estimator methods suffer from problems such as high time complexity of O(n2) and high memory requirement especially when indexing is used. These problems produce limitations on applying them for small datasets. In this paper a new method is proposed that calculates distances to nearest and farthest neighbor nodes to make dataset subgroups; therefore, computational time complexity becomes of O(nlogn) and space complexity becomes constant. After subgroup formation, assembling technique is used to derive correct clusters. The proposed method uses a new parameter to detect clusters which are not obviously separable. The ratio of middle point to minimum density of clusters is compared to this parameter which its value is dependent on the clustering problem. The proposed method is applied to both synthetized and real-world datasets and the results demonstrated the feasibility of the proposed method. Furthermore, the proposed method is compared to the similar algorithm - DBSCAN- on real-world datasets and the results showed significantly higher accuracy of the proposed method.