随着信息技术的飞速发展，模式识别受到越来越多的关注，并在不同的领域得到广泛应用。聚类是模式识别的重要组成部分，其依据给定的相似性度量将数据划分成若干个类，使得同一类内的数据相似度较高，而不同类之间的数据相似度较低，从而发现隐藏在数据中的规律与关联信息。尽管聚类算法的研究已经取得了丰硕的成果，但是在处理大数据时，仍然受到时间、空间和CPU等资源的限制，面临聚类效率低下的境况。如何研究设计出新的聚类算法使其可以对大数据进行高效聚类，得到很多研究者的关注，也已成为模式识别领域的研究热点之一。
　　针对现有的聚类算法难以对大数据高效聚类的问题，本文结合抽样技术、特征约减方法与经典聚类算法提出一系列高效率的聚类算法；同时还在经典领域算法研究的基础之上，尝试在算法设计的理念中嵌入量子计算思维、在问题解决的方案中融入量子计算的方法和技巧，开展基于量子计算的聚类算法研究。本文的贡献和研究内容如下：
　　（1）为提高大数据的聚类效率，开展基于特征约减与量子计算的划分聚类研究，提出两种算法。第一种是基于特征约减和加权的k-means++聚类算法（FRW-KC）。K-means++算法改善了k-means对初始聚类中心敏感的问题；但是其时间复杂度与数据集的特征数量成线性关系，聚类速度受到大数据应用场景的限制。FRW-KC算法采用基于近似Markov blanket的无监督特征约减方法移除数据集中的冗余特征，然后通过信息熵评价保留特征的权重，最后使用k-means++算法进行聚类。第二种是量子k-means算法。将量子计算引入k-means算法，借助量子计算的并行性、叠加性等特性以提高k-means算法的聚类效率。量子k-means算法首先将聚类数据和k个聚类中心制备为量子态，然后并行计算其相似度，接着通过相位估计算法将相似度信息保存到量子比特中，最后使用最小值查找量子算法查找最相似的聚类中心点。比较量子与经典k-means算法的复杂度得到：量子k-means算法的时间复杂度相对经典算法得到有效降低，空间复杂度可以达到指数级的降低。
　　（2）基于密度和delta距离的聚类算法（DDC）是一种较理想的聚类算法，但是它的计算复杂度很高，且需要手动识别聚类中心，费时费力，提出两种高效的DDC算法。前者是高效自适应的密度和delta距离聚类算法（EADDC），它将位置敏感哈希函数抽样方法嵌入DDC算法中对数据集进行规模约减，进而降低计算复杂度，并将一种基于密度的聚类算法（DBSCAN）作为离群点检测技术来自适应识别聚类中心。实验结果表明：与DDC算法相比较，EADDC算法具备高效、自适应聚类的性能。后者是基于量子计算加速的DDC算法，它利用量子计算在一些经典问题求解中的高效计算优势，引入相关的量子算法：即利用量子计数算法加速DDC算法中密度的求解，利用最小值查找量子算法来加速算法中delta距离的求解。理论分析得出：相比DDC算法，基于量子计算加速的DDC算法可以达到二次加速的效果。
　　（3）提出一种基于最优K相异性抽样的谱聚类算法（SOKS）。谱聚类算法是目前热门的聚类算法，它对任意分布的数据集都具有良好的聚类效果，且收敛于全局最优解，然而其所需要的计算复杂度很高。提出将最优K相异性抽样（OptiSim）算法用于数据集的抽样以得到有代表性的样本集，然后采用Nystr?m扩展方法对抽样样本集进行近似计算来降低聚类的时间复杂度。实验结果表明：与谱聚类算法相比，SOKS算法可以达到高效聚类的效果。