近年来，伴随着互联网时代的数据大爆炸，面向大规模、高噪声数据的快速聚类分析技术逐渐发展成为了数据挖掘和机器学习领域的热点研究方向。聚类分析技术有着非常广阔的应用前景，被普遍应用于模式识别、机器学习、图像检索、计算机视觉、数据可视化、知识发现，以及数据统计分析等多个领域。各个不同领域中的多样化的应用需求催生了种类繁多的聚类分析算法。其中，基于密集子图的聚类分析方法通过检测由分析对象构成的相似度图中的密集子图，来实现聚类分析目标。经过多年研究发现，基于密集子图的聚类分析方法通常具有较高的抗噪声性能，但其大规模数据处理能力有限。本文在深入研究基于密集子图的聚类分析方法的基础上，提出了一种基于密集子图的快速抗噪声聚类分析方法。该算法在充分继承密集子图优良抗噪声性能的同时，有效提升了大规模数据处理能力。同时，本文还将基于密集子图的聚类分析算法有效应用于大规模相似图像检索任务中，有效提升了大规模相似图像的检索性能。本文主要研究工作包括:　　(1)提出了一种面向大规模、高噪声数据的“近似局部化感染免疫动态聚类分析算法”(Approximate Localized Infection Immunization Dynamics，ALID)。该算法通过检测相似度图中的密集子图结构，在具有高噪声背景的大量数据中快速准确的检测聚类团簇。ALID算法在不损失聚类分析精度的前提下，将原始的“感染免疫动态算法”的计算范围从覆盖整个相似度图的全局范围缩小到仅覆盖一个密集子图的局部范围，从而有效提升了其大规模数据处理能力。理论分析和实验结果充分证明了ALID算法具有很高的运算效率和聚类精度。　　(2)提出了一套基于MapReduce框架的“并行局部化感染免疫动态聚类算法”(Parallel ALID，PALID)。该算法充分利用ALID算法的局部化运算特性，将ALID算法与MapReduce并行框架相结合，进一步提升其大规模数据处理能力。PALID算法在时下较为热门的Spark并行处理平台(https://spark.apache.org/)上使用Java语言实现。实验结果表明，PALID算法利用8个工作实例处理5千万SIFT特征数据仅需2.29个小时，相对于单个工作实例实现了7.5倍的并行加速比。　　(3)提出了一种新的“基于密集子图的抗噪声视觉单词词典生成方法”，用于解决视觉单词生成过程中面临的“数据规模大”和“数据噪声高”的两大实际问题。该方法利用密集子图的良好抗噪声性能有效提升了视觉单词的视觉描述能力。同时，该方法还利用K叉树索引结构有效提升了聚类分析效率，从而满足了视觉单词词典生成过程的数据规模要求。大量实验结果证明，基于密集子图的抗噪声视觉单词词典具有很高的视觉描述能力，能够有效提升相似图像检索系统的精度和效率。　　(4)提出了一种“基于密集子图的局部相似图像检索算法”。该算法首先将视觉单词之间的空间分布一致性构建到精心设计的“空间分布一致性图”中。然后，利用基于密集子图的聚类分析算法实现了视觉单词匹配对的空间验证，从而有效提升了局部相似图像的检索性能。我们以此算法为原型，实现了一套完整的大规模相似图像检索系统，并顺利上线（http://vipl.ict.ac.cn/isia）。在多个图像检索标准数据集上的大量实验结果表明，该算法在检索局部相似图像方面的性能十分出众。　　综上所述，本文针对基于密集子图的聚类分析算法展开了深入研究，提出了一种新的面向大规模、高噪声数据的聚类分析检测算法，及其并行化实现。同时，将基于密集子图的聚类分析算法成功应用到大规模相似图像检索任务中，有效提升了图像检索性能。