论文部分内容阅读
谱聚类算法是基于谱图划分理论的一种聚类算法,由于其对非凸数据集具有优越的性能而广受欢迎。因为谱聚类算法中的相似图构造的好坏往往会直接关系到数据集内数据点之间的相似度是否符合真实情况,从而进一步影响到谱聚类算法的聚类性能,所以本文针对这一问题进行了研究。本文内容紧紧围绕谱聚类算法中的相似图构造,提出了两种基于不同相似图的谱聚类算法,其中一种为半监督算法。最后本文还将这两种算法进行了融合,得到一种新的算法,并将其应用到了实际的文本聚类当中。以下是本文的主要研究工作及成果:首先,提出了基于密度自适应邻域相似图的半监督谱聚类算法(DAN-SSC)。该算法先是将半监督信息的一种——成对约束先验信息扩散到整个聚类空间,然后再合理地利用这些信息来指导DAN算法当中的相似度矩阵的构造过程,接着才继续完成规范化谱聚类的流程。最后还需检验之前的聚类结果是否满足先验信息的约束条件,若不满足则需对其进行调整,调整之后才能得到最终的聚类结果。通过对比实验及分析,证明了DAN-SSC算法充分利用了有标签数据且避免了少量有标签数据可能会对聚类过程进行错误指导的情况,该算法在实验数据集上获得了比传统无监督谱聚类算法和其它半监督谱聚类算法更好的聚类结果。其次,提出了第二种算法:基于自然最近邻相似图的谱聚类算法(NSG-SC)。自然最近邻是一种较为新颖的最近邻概念,它有着诸多优点。本文创新性地将其融入到谱聚类算法的关键步骤相似图构造当中,主要是利用自然最近邻的思想来指导相似图的构造过程。最后的实验结果表明:对比传统的近邻关系图,本文提出的自然最近邻相似图能够更加准确地反映出样本间的相似性关系,NSG-SC算法同时也改善了传统谱聚类算法中不易识别形状不规则和密度可变的簇类的缺点。最后,将本文之前提出的两种算法进行融合,得到了基于自然最近邻相似图的半监督谱聚类算法(NSG-SSC),并将该算法并行化然后应用到真实的文本聚类当中。这是由于文本数据集通常维度高、分布复杂,而谱聚类正擅长处理这种数据集,将算法并行化更是能大大加快算法的运行速度。NSG-SSC算法的并行化平台是基于MapReduce编程思想的第二代分布式平台Spark,该平台采用了一种名为内存计算的技术,通过该技术能够极大地提高大数据集的运算速度。最后经过实验分析表明,NSG-SSC算法并行化后,可以成功地应用到文本聚类当中,并且取得了不错的效果。