聚类分析的目标是对一组数据进行分类,使得相似的数据归为同一类别,不相似的数据归到不同类别。近年来,聚类分析在生物医学,图像处理和自然语言处理等多个领域有广泛应用。由于现实生活中的数据分布复杂,存在形状不规则,密度分布不均匀等特点,现有的聚类算法无法得到满意的结果。另外,大部分的聚类算法需要预先输入聚类数目,但实际情况下无法预知该值。为解决上述问题,本文引入了稀疏因子和增广非共享近邻的概念,并在此基础上,分别提出了聚类算法和聚类有效性指标。具体来讲,本文的主要工作如下:（1）提出了一种基于稀疏因子的数据点密度定义方法。密度峰值聚类算法因其算法思想简单而被广泛应用,但该算法的性能易受截断距离影响。为解决该问题,本文首先在数据点的k近邻点基础上定义了稀疏因子,接着,根据数据点的稀疏因子动态调整其截断距离,最后,利用测地距离计算数据点的局部密度,使得聚类中心受数据点稀疏分布的影响较小。（2）提出了一种基于增广非共享近邻的密度峰值聚类算法（knn MST）。cci MST聚类算法能识别不同形状的簇,但该算法在密度相差较大的数据集上容易出错。为解决该问题,本文引入了增广非共享近邻的概念,并在此基础上,定义了数据点对的不一致因子。最后,计算聚类中心所在路径上数据点对的不一致因子,删除最大不一致因子所对应的边,得到聚类结果。（3）提出了一种基于增广非共享近邻的聚类有效性指标（ANCV）。ANCV指标基于以下原则:首先,簇内距离可以利用共享近邻数较少的数据点对之间的距离来衡量;其次,相邻簇对交界处的数据点对之间的距离可用于度量簇间距离。在此基础上,将上述点对进一步扩展到它们的增广非共享近邻,将簇内与簇间的增广非共享近邻点对视为处于稀疏区域的小簇,分别计算这些小簇内所有点对的平均距离作为簇内距离与簇间距离。最后,根据簇间分离度与簇内紧致度之差评估聚类结果,从而得到最优聚类数目。（4）实验中,我们将knn MST与K-means,cci MST,NTHC等8种聚类算法在6个二维合成数据集与8个真实数据集进行了对比。另外,我们还将ANCV与Dunn,DBI,CH和SIL等13聚类有效性指标进行了对比实验。实验结果表明,本文提出聚类算法和聚类有效性指标的性能优于对比算法。