Density Partition Based Adaptive Shoeprint Clustering Algorithm

Shoeprints are important clues to criminal investigations.As the time going by,the number of shoeprints collected has grown up.How to realize the automatic classification of large-scale shoeprints has become a major problem for criminal investigators to be solved.The purpose of shoeprint clustering is to classify shoeprint images of the same pattern into the same class.In practiee,the characteristics of the shoeprint images are as follows:(ⅰ)shoeprint image quality levels are different;(ⅱ)the number of shoeprint classes is large;(ⅲ)the shoeprint distribution density is non-uniform;(ⅳ)the distance between intra class points is greater than that of inter-class points;(ⅴ)points form one class could be surrounded by points from different clusters.Existing cluster algorithm cannot be directly used for shoeprint clustering;therefore,we propose an adaptive density partition based shoeprint clustering algorithm.The main works are as follows:1)An adaptive clustering parameters calculation method based on density partitioning is proposed.As described above,the shoeprint data structure is complex.Therefore,the parameters such as fixed distance and density,cannot accurately describe the spatial relationship between classes.It is necessary to accurately describe the spatial relationship between points,and adaptively complete clustering.In this thesis,all points are first divided into high density points and low density points according to a density threshold and then these two kinds of points are separately clustered.The ratio of the number of points in the same class to the number of points in different classes is calculated and used as a condition for merging.The experimental results on two kinds of public datasets and one kind of real shoeprint database show that the results of the manual tuning parameters and the results of the adaptive clustering algorithm are almost the same.2)A cluster partition algorithm based on natural neighborhood graph is proposed.Natural neighbors determine the spatial relationship by automatically searching for its neighbors.The natural neighborhood graph constructed by the natural neighbors can more accurately reflect the complex structure of the data.Therefore,we use natural neighborhood graph to split clusters containing points from more than one classes.The purity of the clustering algorithm has been improved.At the same time,a new representative point competition rule is proposed.Performances on two kinds of public datasets have been greatly improved.The experimental results of 16938 shoeprint data show that the F-measure value is 80.16%,and the purity is greatly improved.3)A cluster merging algorithm based on weighted similarity is proposed.For complex data structures,some traditional clustering algorithms calculate the similarity based on the distance between points.In fact,these methods are not accurate.After analyzing the structure of the clusters,we propose a clustering algorithm based on weighted similarity.The weight of the similarity formula includes as follows:(i)the ratio of the number of edge points to the total number of clusters;(ii)the ratio of density mean value loetween adjacent clusters.The improved similarity calculation method can accurately describe the similarity between clusters.So the clusters can be merged correctly,and improving the recall ratio of the clustering algorithm.Performances on two kinds of public datasets are better than these of the comparison algorithm.Meanwhile,we do experiments on real shoeprint database and the purity reaches 90.21%.the F-measure value is 81.96%.