1. A recognition device comprising: a storage unit that stores information of a cluster to which a model feature point that is a feature point of model data belongs, which is determined by clustering based on a feature amount and information of a feature amount of the model feature point; an extracting unit that extracts a feature amount of a query feature point that is a feature point of data input as a query; a generating units that determines a first set of the query feature point including a reference point that is one of the query feature points, which serves as a reference and a dependent point that is one or a plurality of query feature points depending on the reference point, and generates, for each first set, geometric information that is information representing a position of each dependent point, with a position of the reference point given as a reference; a clustering unit that clusters the query feature point by the same scheme as in the clustering of the model feature point; a correcting unit that sets up the model feature point belonging to the same cluster as that of the reference point as a nearest candidate of the reference point, sets up the model feature point belonging to the same cluster as that of the dependent point as a nearest candidate of the dependent point, determines whether or not the nearest candidate of the reference point is present at a position where the reference point, which is specified by the geometric information, is regarded to be present, with a position of the nearest candidate of each dependent point given as a reference, and corrects the model feature point serving as the nearest candidate of the reference point according to a result of the determination; and a similarity degree calculating unit that calculates a similarity degree of the first set and a second set including the nearest candidate of the reference point after correcting and the nearest candidate of the dependent point based on a feature amount of each feature point and determines the second set nearest to the first set.