基本概念

t-SNE(t-distributed stochastic neighbor embedding)是用于降维的一种机器学习算法，由 Laurens van der Maaten 等在08年提出。

t-SNE 是一种非线性降维算法，非常适用于高维数据降维到2维或者3维，进行可视化。该算法可以将对于较大相似度的点，t分布在低维空间中的距离需要稍小一点；而对于低相似度的点，t分布在低维空间中的距离需要更远。

tips1:TSNE将数据点之间的相似性转换为联合概率，并试图最小化低维嵌入和高维数据的联合概率之间的Kullback-Leibler差异。t-SNE的成本函数不是凸的，即使用不同的初始化，我们可以获得不同的结果。

tips2:如果特征数量非常多，强烈建议使用另一种降维方法（例如，对于密集数据使用PCA或对于稀疏数据使用TruncatedSVD）将尺寸数量减少到合理的数量（例如50个）。这将抑制一些噪声并加快样本之间成对距离的计算。

tips3:sklearn TSNE 源码

tips4:t-SNE 原理及Python实例 - 知乎 (zhihu.com)

优缺点

优点：

• 对于不相似的点，用一个较小的距离产生较大的梯度来排斥区分。
• 这种排斥不会无限大(梯度中分母)，避免不相似的点距离太远。

缺点：

• 主要用于可视化，很难用于其他目的。比如测试集合降维，因为他没有显式的预估部分，不能在测试集合直接降维；比如降维到10维，因为t分布偏重长尾，1个自由度的t分布很难保存好局部特征，可能需要设置成更高的自由度。
• t-SNE倾向于保存局部特征，对于本征维数(intrinsic dimensionality)本身就很高的数据集，是不可能完整的映射到2-3维的空间（映射存在信息损失）
• t-SNE没有唯一最优解，且没有预估部分。如果想要做预估，可以考虑降维之后，再构建一个回归方程之类的模型去做。但是要注意，t-sne中距离本身是没有意义，都是概率分布问题。
• 训练太慢。有很多基于树的算法在t-sne上做一些改进

算法流程

• 首先在高维空间,将样本之间的距离转换成概率分布.

$$ P_{j|i}=\frac {exp(-||x_i-x_j||^2/2\sigma^2)}{\sum_{k \neq i} exp(-||x_i-x_k||^2/2\sigma^2)} $$

• 在低维空间寻找类似的概率分布,并使用KL散度衡量高维空间/低维空间两概率分布的相似度.

• 使用梯度下降最小化所有数据点上的KL散度总和

  $$ C = \sum_i KL(P_i||Q_i)=\sum_i \sum_j p_{j|i} \log {\frac {p_{j|i}}{q_{j|i}} } $$

• 对 C 求偏导数(每个样本)获得每次更新的方向

sklearn

• n_components : tsne最终降维的维度
• init : 初始化方法,可以使用pca or random

from sklearn.manifold import TSNE
tsne=TSNE(n_components=1,init='pca', random_state=501)
down_X = tsne.fit_transform(X) # train and get embadding

基本概念

• DBSCAN:Density-Based Spatial Clustering of Applications with Noise (具有噪声的基于密度的聚类方法）
• 核心对象：若某个点内的密度达到算法设定的阈值则为核心点
• ∈-邻域的距离阈值：设定的半径r
• 直接密度可达：若点p在点q的r邻域内，且q是核心点则p-q直接密度可达
• 密度可达：若有一个点的序列$q_0,q_1,...,q_k$，对任意$q_i,q_{i-1}$直接密度可达,那么称$q_0,q_k$密度可达。即直接密度可达的‘传播’。
• 密度相连：若从核心点p出发，点q和点k都是密度可达的。那么点q和点k是密度相连的。(不要求q/k必须是核心点)
• 边界点：属于某个类的非核心点
• 噪声点：不属于任何一个类簇的点，从任何一个核心点出发都是密度不可达的。

参数选择

• 半径∈：可以根据K距离设定，即寻找突变点。

• K距离：给定数据集P = {p(i);i=0,1,...,n},计算点p(i)到集合D的子集S中所有点之间的距离d，按照距离从小到大排序,d(k)即K距离

  例如点s到其他点的距离数组$d_k$={0.1,0.11,0.12,0.3,0.5....}(已排序)，发现前三个距离相差不大，第四个距离0.3发生突变，那么半径取d(3)=0.12,MinPts取3

• MinPts：K-距离中的K值，一般从小开始取

优缺点

优点：

• 可以处理任意形状的簇
• 不需要指定簇的个数
• 擅长找到离群点，用于异常检测任务

缺点：

• 高维数据处理困难(可以寻找降维方法)
• 半径r和MinPts难以确定
• 算法效率慢

算法流程

伪代码如下,类似宽度优先搜索进行簇的传播:

bool visited[n];
memset(visited,false,sizeof visited);
while(some point is unvisited){
    choose p randomly which is unvisited;
    if(p ∈-field has more that MinPts points){
        create a new cluster C;
        N = {q in p ∈-field};
        for(auto &q:N){
            if(visited[q]==false){
                visited[q] = true;
                if(q ∈-field has more that MinPts points){
                    add {k in q ∈-field} to N;
                }
                add q to cluster C;
            }
        }
    }else{
        add p to noise;
    }
}

可视化

Visualizing DBSCAN Clustering (naftaliharris.com)

sklearn

from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.5,min_sample=5)
dbscan.fit(X)    # train
dbscan.label_   # label label=-1 means noise
descan.core_sample_indices_ # 核心样本在原始训练集中的位置