基于标记点的谱聚类算法降低了谱聚类算法的计算复杂度,避免了传统谱聚类算法计算时间长的应用局限。但是,使用聚类准确性和标准化互信息衡量聚类有效性,基于标记点的谱聚类算法的聚类有效性较低。如何平衡聚类有效性和聚类时间成为了基于标记点的谱聚类算法面对的难题。针对此问题,提出了一种基于KD标记点的谱聚类算法。首先,提出一种KD标记点选取方法,该方法使用超平面将样本空间不均等划分为p个子块,超平面垂直于样本空间中方差最大的前i个维度,划分后的每个子块中数据点的数量基本相等,计算各子块中数据点的平均值作为中心点,中心点的集合即为选取的标记点;然后,在KD标记点的基础上使用一种近邻点有效分配法计算标记点与样本点之间的相似矩阵,将结果推广到样本点中构造相似图;最后,使用奇异值分解代替了传统的特征分解过程以加快算法的速度,并在右奇异向量上进行k-means聚类得到最终结果,提高了聚类有效性。在仿真实验中采用MNIST、Seismic、LetterRec和USPS四个不同规模的大数据集,将本文算法与经典谱聚类算法和四种有代表性的基于标记点的谱聚类算法进行对比,结果表明本文算法在聚类有效性和聚类时间两方面优于现有的基于标记点的谱聚类算法,在处理大规模数据时,平衡了聚类有效性和聚类时间。该论文有图23幅,表7个,参考文献51篇。