数据分析师笔试题1-常见聚类算法

来源：小红书笔试-牛客网

一、算法基础

1 auc与 roc

AUC：分类中一个正例，一个负例。预测为正的概率值比预测为负的概率值还要大的可能性就是auc。绘制ROC曲线，ROC曲线下面的面积就是AUC的值。

image.png

二、常见的聚类算法

(1) K-means聚类、K-中心点聚类、CLARANS算法,DIANA算法、BIRCH算法、Chameleon算法
(2) EM算法
(3) OPTICS算法、DBSCAN算法
分类
（1）基于质心
K-means聚类√、K-中心点聚类、CLARANS算法,DIANA算法、
（2）基于层次
BIRCH算法√、Chameleon算法√
（3）基于概率
EM算法√
（4）基于密度
DBSCAN算法√
OPTICS算法（Ordering points to identify the clustering structure，排序点来识别聚类结构）有效的解决了密度不同导致的聚类效果不好的问题。
（5）基于图

各算法在sklearn中的调用

image.png

1 基于质心

K-means聚类

目的：最小化平方误差

image.png

理解：
第一步选择初始质心，最基本的方法是ķ从数据集中选择样本 X。
初始化之后，K-means包括在其他两个步骤之间循环：

第一步将每个样品分配到最近的质心。
第二步通过获取分配给每个先前质心的所有样本的平均值来创建新质心。计算旧的和新的质心之间的差异，并且算法重复这最后两个步骤，直到该值小于阈值。换句话说，它重复直到质心不显着移动。

实现：

sklearn.cluster.KMeans(n_clusters=8,
    init='k-means++', 
    n_init=10, 
    max_iter=300, 
    tol=0.0001, 
    precompute_distances='auto', 
    verbose=0, 
    random_state=None, 
    copy_x=True, 
    n_jobs=1, 
    algorithm='auto'
    )
algorithm: kmeans的实现算法，有：’auto’, ‘full’, ‘elkan’, 其中 ‘full’表示用EM方式实现

优缺点：
优点：简单，可解释，速度快，主要调参只有k。
缺点：

需要事先确定分类的簇数，即k值。
采用迭代方法，得到的结果只是局部最优。
对初始值的选取比较敏感。（改进1：k-means++（sklearn已经添加该参数的取值）;改进2：二分K-means）
当数据量非常大时，算法的时间开销是非常大的（改进：Mini Batch K-Means（精确度会降低，在可接受的范围即可））；
若簇中含有异常点，将导致均值偏离严重，对噪声和孤立点数据敏感（改进1：离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响；改进2：改成求点的中位数，这种聚类方式即K-k-median聚类（K中值））；
对于不是凸的数据集比较难收敛(改进：基于密度的聚类算法更加适合，比如DESCAN算法)

2 基于概率

2.1 BIRCH算法

对于CF Tree，一般有3个重要参数:

第一个参数是每个内部节点的最大CF数B
第二个参数是每个叶子节点的最大CF数L
第三个参数是叶节点每个CF的最大样本半径阈值T，也就是说，在这个CF中的所有样本点一定要在半径小于T的一个超球体内。

步骤：
1.从根节点向下寻找和新样本距离最近的叶子节点和叶子节点里最近的CF节点。

如果新样本加入后，这个CF节点对应的超球体半径仍然满足小于阈值T，则更新路径上所有的CF三元组，插入结束。否则转入3.
如果当前叶子节点的CF节点个数小于阈值L，则创建一个新的CF节点，放入新样本，将新的CF节点放入这个叶子节点，更新路径上所有的CF三元组，插入结束。否则转入4。
4.将当前叶子节点划分为两个新叶子节点，选择旧叶子节点中所有CF元组里超球体距离最远的两个CF元组，分布作为两个新叶子节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂方式相同。
优缺点：
优点：节约内存，聚类块，可识别噪音点，可用于预分类处理
缺点：
1）由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同.
2）对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means
3）如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。

2.2 chameleon 变色龙算法

是一种两阶段聚类法

image.png

步骤：

第一阶段把点分成很多小的簇；第一个是形成小簇集的过程就是从Data Set 到k最近邻图到分裂成小聚簇
第二阶段根据相近程度合并这些小的簇。第二阶段计算任意两个簇的互连性RI和紧密性RC，当两个指标都比较大时才合并这两个簇,合并这些小聚簇形成最终的结果聚簇

image.png

优缺点：
优点：算法考虑了互连性和近似性，能发现高质量的任意形状的簇
缺点：参数复杂，时间复杂度高

3 基于密度

DESCAN算法

DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ, MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。
理解：给定一个半径长度r和一个最小点的数目m，然后以某个点为圆心，r为半径，如果在该圆内的点的数目大于m值，则把该点标记为中心点，如果数目小于m值，则被标记为噪声点。重复该步骤，如果一个噪声点存在于某个中心点的圆内，则标记该点为边缘点。直到所有点都被标记了，然后连接在一个圆内中心点以及每个中心点的边缘点组成一个簇。
实现：

class sklearn.cluster.DBSCAN(eps=0.5, 
        min_samples=5, 
        metric=’euclidean’, 
        metric_params=None, 
        algorithm=’auto’, 
        leaf_size=30, 
        p=None, 
        n_jobs=1)

eps:两个样本之间的最大距离，以便将它们视为在同一邻域中。
min_samples:对于要被视为核心点的点，邻域中的样本数（或总权重）。这包括点本身。
metric：最近邻距离度量参数。可以使用的距离度量较多，一般来说DBSCAN使用默认的欧式距离
algorithm：最近邻搜索算法参数(暴力实现，kd数，球树实现)

DBSCAN小结

和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似。

那么我们什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。

4、EM算法

最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。
步骤：
最大期望算法经过两个步骤交替进行计算：

第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

image.png

参考来源：

3 判别模型与生成式模型

判别式模型是直接对条件概率p(y|x;θ)建模。生成式模型则会对x和y的联合分布p(x,y)建模，然后通过贝叶斯公式来求得p(yi|x)，然后选取使得p(yi|x)最大的yi。

image.png

生成式模型有：
AODE（平均单依赖估计）
朴素贝叶斯Native Bayes
混合高斯型Gaussians
隐马尔科夫模型HMM
贝叶斯网络
信念网络sigmoid belief networks
马尔科夫随机场Markov random fields
深度信念网络DBN
隐含狄利克雷分布简称LDA(Latent Dirichlet allocation)
多专家模型（the mixture of experts model）
Restricted Boltzmann Machine（限制波兹曼机）

判别式模型有：
感知机(Perceptron):二分类 +1 / -1
决策树
逻辑回归logic regression
K近邻 KNN
最大熵模型
支持向量机SVM
提升方法/集成学习Boosting
神经网络NN
高斯过程Gaussian process
条件随机场CRF
CART决策树(Classification and regression tree)
Linear Regression（线性回归）
Linear Discriminant Analysis（线性判别分析）