鞋印作为案件侦破的重要线索,随着时间积累,数量不断壮大。而如何实现对大规模鞋印库的自动分类管理成为刑侦人员亟待解决的一大难题。聚类的目的是将相同花纹的鞋印图像标记为一类。但鞋印库存在图像质量层次不齐,类别数目众多,类内类间密度分布不均匀,类内距离大于类间距离以及同类点被非同类点包围等问题。所以基于以上特点,本文提出了基于密度划分的自适应鞋印图像聚类算法,主要工作如下:1)基于密度划分的聚类参数自适应计算鞋印数据结构复杂,仅通过固定的距离、密度等参数并不能准确描述类别间关系,需要深入挖掘各点间的位置关系,自适应得到聚类结果。在本文中,所有数据先根据密度阈值进行划分,再进行聚类,并计算簇间同类点与非同类点的比例,作为判别簇间是否合并的条件,实现了聚类算法的参数自适应。在两类公开数据集以及鞋印数据库上进行了实验,聚类结果接近人工设置最优参数。2)基于自然邻域图的簇划分自然近邻是通过自动搜索近邻点来确定点间位置关系,根据自然近邻点构建的自然邻域图可以更加准确反映数据的复杂结构。本文利用自然邻域图对簇进行细划分,将划分到一个簇的非同类点成功分离,实现了簇的准确划分,提高了聚类算法的纯度。同时改进了算法中的代表点竞争规则。在两类公开数据集上进行了验证实验,均取得较好聚类效果。在16938幅鞋印库数据上进行实验,F-measure值为80.16%,聚类纯度大大提高。3)基于加权相似度的簇合并对于复杂数据结构,传统聚类算法中基于点间距离计算相似度的方法并不准确。经过对相邻簇的结构进行分析,本文提出基于加权相似度的簇合并算法。将跨簇点与该簇的数目比以及相邻簇间的密度均值比作为相似度计算公式的权重,改进的相似度计算方法可以准确描述簇间相似度。从而实现了簇的正确合并,提高了聚类算法的查全率。在两类公开数据集上的聚类性能均优于对比算法;在鞋印数据集上实验,聚类纯度达到 90.21%,F-measure 值为 81.96%。