单细胞聚类方法大比拼（I）
单细胞转录组测序可是近年生物信息学最热门的话题，20分以上的文章更是层出不穷。小编纵观多篇文献（其实也只是看了看简介和配图），发现了几乎所有的文献都会有单细胞的聚类图，就是酱紫，是不是很熟悉~今天我们在这里探讨一下这种美观又实用的图是怎么做出来的吧。
说到聚类，首先不得不提到他的好兄弟–降维，就是降维打击的降维。因为单细胞数据的维度实在是太高了，在质控后一个细胞一般都是3000维以上，如果在这么高的一个空间中直接进行聚类，电脑的CPU和内存分分钟爆炸。所以，我们要尽量把维度压缩到可以计算的范围，但是对于不同性能的服务器是不一样的，高分的文献会降到50维左右。需要注意的是，降维不可避免的会损失一些信息，就好比你把3D的几何体投影到二维的平面一样，这时候降维方法的选择就比较重要了，好的降维方法可以尽可能多的保存数据原始信息。PCA（主成分分析）和t-SNE是目前最受青睐的两种方法，改日有空详细说一下。
好啦，现在我们有了低维度的数据，假定每个细胞50维吧。现在可以开始聚类了，是不是很激动。聚类说简单一点就是“物以类聚”，也就是度量不同样本之间的相似性，把相似的归为一类。对于我们的单细胞数据，就是用降维后的50维的向量衡量细胞之间的相似性。别慌，我们该选择什么聚类方法呢？有选择困难症的我必须一个一个都试一遍~
最简单的方法首推层次聚类。它先计算样本之间的距离，一般都是欧几里得距离，每次将距离最近的点合并到同一个类，并用类中的所有样本的平均值代表这个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。就像下图一样，你想把你的细胞分成几类，在这颗树合适的位置切断就可以了。这个方法是不是比较low，所以在文献中出现的很少，大家当然愿意用高大上的方法嘛。
可惜接下来这个还不是那么的高大上，他就是经典的聚类算法–K-means，又称K-均值聚类。他的原理也非常简单，首先人工设定k的值，也就是你想把样本分成多少类。第一步是随机（没错，就是随机！）在所有细胞中选择k个作为起始的类中心点，其他各个样本点距离哪个类中心点最近就划为哪一类。第二步，计算每个类中的平均值，作为新的样本中心点。第三步，每个样本计算它到新的样本中心的距离，并重新分类。反复重复第二、三步骤，直到每次迭代每个点所属的类不变（k-means一定会收敛），也许你等不急算法收敛，迭代一定的次数就停也是可以滴。通俗来说k-means就像是大学生选课，一开始大家都随便选，这就是第一步。然后过了一段时间，选了这门课的同学给这门课一个评价，相当于第二步求平均值。又过了一段时间，有的同学通过其他人对不同课程评价和自己的兴趣换了课，这对应第三步重新分类。然后大家就陷入选课->换课的循环，一直到学习结束（算法收敛）。诸位再看的大学生们，是不是很形象~。k-means还衍生出一些改进算法如K-means++，它可以避免随机起始对k-means结果的影响。
以上两种都是基于距离度量的聚类方法，在凸数据集中是很有效的，凸数据集就是类内任意两点的连线上所有的点都在类中，可以参考凸多边形的定义。但他们对非凸数据集就力不从心了，具体可以看文末的例子。对非凸数据集，常用DBSCAN算法。DBSCAN是一种基于密度的聚类算法，它的原理比较复杂，我这就不多说了，好学的小盆友自己百度。我们只需要知道：
1. DBSCAN聚类的时候不需要预先指定簇的个数（是不是很高级）
授人以鱼还要受人以渔嘛，我用python简单实现一下三种方法。惯用R语言的同学只有一行函数就更简单了，我就偷懒了。
嘻嘻，自己写源码是不可能的，偷偷的调用一下sklearn吧。源代码有点长，这里直接上结果图片了，源码可以从我的GitHub(https://github.com/huhansan666666/singleCell/blob/master/cluster.py)直接下载和运行哦，顺便可以给我点一个小星星。
为了突出算法之间的差异性，我特意使用了非凸数据集，从左到右依次是DBSCAN，k-means（k=4），层次聚类（分成4类）的结果。DBSCAN自己把数据分成了四类，效果还可以；可以看到后两个算法全部翻车了，说明他们对非凸数据集真的无能为力。而真实的单细胞数据的分布往往是奇形怪状的，以非凸的数据居多，这就是为啥有那么多专门为单细胞数据开发的聚类方法。所以在聚类的时候大家一定要依据自己数据集的特性仔细选择聚类方法哦！
好啦，今天将的都是比较基础的方法，下次将介绍文献中常用的SC3聚类、图聚类，它们在更复杂的真实单细胞数据集中有着更好的效果。
