Availability of affordable and widely applicable interatomic potentials is the key needed to unlock the riches of modern materials modelling. Artificial neural network based approaches for generating potentials are promising; however neural network training requires large amounts of data, sampled adequately from an often unknown potential energy surface. Here we propose a self-consistent approach that is based on crystal structure prediction formalism and is guided by unsupervised data analysis, to construct an accurate, inexpensive and transferable artificial neural network potential. Using this approach, we construct an interatomic potential for Carbon and demonstrate its ability to reproduce first principles results on elastic and vibrational properties for diamond, graphite and graphene, as well as energy ordering and structural properties of a wide range of crystalline and amorphous phases.