Abstract
Constructing information granules (IGs) has been of significant interest to the discipline of granular computing. The principle of justifiable granularity has been proposed to guide the design of IGs, opening an avenue of pursuits of building IGs carried out on a basis of well-defined and intuitively appealing principles. However, how to improve the efficiency and accuracy of the resulting constructs is an open issue. In this paper, we present a local-density-based optimal granulation model (LoDOG), exhibiting evident advantages: 1) it can detect arbitrarily-shaped IGs and 2) it finds the optimal granulation solutions with {O}({N}) complexity, once the leading tree structure has been constructed. We describe IGs of arbitrary shapes using a small collection of landmark points positioned on the skeleton of the underlying manifold, which contribute to approximate reconstruction capabilities of the original dataset. A dissimilarity metric is developed to evaluate the quality of the obtained reconstruction. The interpretability of LoDOG IGs is discussed. Theoretical analysis and empirical evaluations are covered to demonstrate the effectiveness of LoDOG and the manifold description.