论文部分内容阅读
细胞类型研究是生命学科领域中的一个重要课题。近些年,随着检测技术的发展,研究人员可以在单细胞尺度对大量细胞的多个特征进行检测,这为细胞类型研究提供了充足的数据支撑。由于单细胞数据集通常是高维且无标签的,聚类方法逐渐成为细胞类型研究中的主要数据分析方法。但是,现有的聚类方法往往在效率、有效性或鲁棒性方面存在一定的不足。为了更好地解决规模较大、维度较高的单细胞数据集的聚类问题,本文提出了四个在效率、有效性和鲁棒性方面达到较好平衡的密度聚类方法。方法一:基于层次最近邻上升的聚类（Hierarchical Nearest Neighbor Ascent based Clustering,HNNA-C）。该方法是本文作者提出的最近上升聚类（Nearest Ascent Clustering,NAC）的一个改进方法。尽管NAC具有一定程度的非球状簇检测能力和较低的噪声及参数敏感性,但NAC具有较高的时间复杂度（为O（N~2）,其中N为样本数）。由于NAC在构建一棵入树（in-tree）的过程中涉及核密度估计和父节点搜索这两个耗时的步骤,HNNA-C借助于快速近邻算法使得这两步都能在邻域范围内快速完成,并通过层次策略保证构建的图仍是一棵入树。理论分析表明,HNNA-C的时间复杂度为O（N log N）。实验结果表明,HNNA-C继承了NAC在有效性和鲁棒性方面的优点,并且在处理规模较大、维度较高的单细胞数据集时,HNNA-C的整体性能优于NAC和一些其它最新的高效聚类方法。方法二:基于h HNNA的核多树融合聚类（h HNNA-based Kernelized Multiple Tree-merging-based clustering,h HNNA-KMT）,其中h HNNA为HNNA的一个变体。h HNNA-KMT也是NAC的一个改进方法。和HNNA-C不同的是,h HNNA-KMT旨在同时提升NAC在鲁棒性、有效性和效率这三方面的性能。为此,h HNNA-KMT先使用h HNNA得到一个包含h个分支的森林,然后使用基于核技巧和多树融合的聚类方法对该森林的根节点聚类,最后基于根节点的聚类结果融合森林中的分支。理论分析表明,h HNNA-KMT的时间复杂度为O（N log N）。实验结果表明,h HNNA-KMT比NAC的有效性和鲁棒性更高,并且在处理规模较大、维度较高的单细胞数据集时,h HNNA-KMT的整体性能优于NAC,且和一些其它最新的高效聚类方法具有可比性。方法三:基于局部密度峰值及最小生成树（clustering with Local Density Peaks-based Minimum Spanning Tree,LDP-MST）的改进聚类方法,称为快速LDP-MST（Fast LDP-MST）。虽然LDP-MST在有效性和鲁棒性方面具备了较好的性能,但它在效率方面存在一定的不足。具体而言,LDP-MST的时间复杂度为O（N log N+M~2）,其中M是一个中间变量。本文的实验揭示,当处理大规模数据集时,M的值可能会很大;在这种情况下,LDP-MST中包含O（M~2）时间项的步骤会非常耗时。本文设计了更高效的算法来实现LDP-MST中包含O（M~2）时间项的三个步骤（即LDP-MST的5、6和7步）。具体而言,本文通过快速确定M×M稀疏权重矩阵的所有非零元素以实现对LDP-MST的第5步的加速,通过从稀疏权重矩阵中快速构建最小生成森林的方式实现对LDP-MST的第6步的加速,以及通过在动态边检测过程中快速计算簇的大小的方式实现对LDP-MST的第7步的加速。理论分析表明,Fast LDP-MST在M≈N时仍有O（N log N）的较低时间复杂度。实验结果表明,Fast LDP-MST不仅比LDP-MST更高效,同时也继承了LDP-MST在有效性和鲁棒性方面的优点。在处理规模较大、维度较高的单细胞数据集时,Fast LDP-MST的整体性能优于LDP-MST和一些其它最新的高效聚类方法。方法四:水平集森林（Level Set Forest,LSF）聚类。LSF是一种基于多尺度水平集的密度聚类方法。该方法先为每个样本找到离它最近的k个点,并基于此估计每个节点密度;紧接着基于多尺度水平集密度聚类的思想构建一棵森林;随后剪除这棵森林中权重最大的几条边;最后确定由剪边后生成的图的各个连通分支,并将属于同一个连通分支的所有节点视为一个簇。LSF的关键一步为构建一棵森林。和已有方法相比,LSF在这一步有以下两点不同:1)LSF得到的层次结构为一棵森林,而非密度聚类树（density cluster tree）或水平集树（level set tree）;2)在构建森林的过程中,LSF基于两个簇的峰值密度和谷点密度的相对关系来度量每一层合并的两个簇之间的距离,并将这个距离视为森林中边的权重。理论分析表明,LSF的时间复杂度为O（N log N）。实验结果表明,LSF在有效性、效率和鲁棒性这三个方面同时具备较好的性能,并且适用于簇个数已知或未知的场合。此外,在处理规模较大、维度较高的单细胞数据集时,LSF和一些最新聚类方法表现出相当的性能。总体而言,本文为解决规模较大、维度较高的单细胞聚类问题提供了新的技术支撑,也进一步丰富了密度聚类方法的研究。此外,本文提出的聚类方法都没有使用单细胞聚类领域的先验知识,这使得这些方法可能具有普适性的应用价值。