8.1 什么是聚类分析？

面试官：什么是聚类分析？聚类是如何划分的？簇的类型如何定义？

程序员大树：
        聚类分析是根据在数据中发现的描述对象及其关系的信息，将数据对象分组。达到的效果是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内相似性越大，组间差距越大，说明聚类效果越好。

        层次聚类：层次聚类是类树的结构，树中每个节点都是子女节点的并集。
        完全聚类：数据集里的每个对象都会被派到一个簇中。
        部分聚类：数据集里包含一些噪声、离群点，可以不被指派到簇中。

        划分簇可以出现不同簇的类型。
        （1）原型簇。对于连续属性的数据，簇的原型是质心，即簇里所有点坐标的平均值；对于分类属性的数据，簇的原型是中心点，即最有代表性的点。原型簇也可称为基于中心的簇，形状趋向于球形。
        （2）基于图的簇。对于图数据，可以将节点看成对象，边看成对象间的关系，那么求簇其实就是求连通分支，即内部互相连通，而不与组外的节点连通。
        （3）基于密度的簇。簇是高密度区域的聚集，簇之间被低密度区域分开。对于噪声和离群点较多的情况下，会使用这种方法。

8.2 如何使用k-means聚类分析？

面试官：如何使用k-means聚类分析？

程序员大树：
        K-means是上面说到的，基于原型、划分的聚类，它尽可能找到k个（用户指定）簇。
        K-means算法：
            （1）选取k个点作为初始质心。其中，k是用户指定的，希望簇的个数。
            （2） 将每个点指派到最近的质心，形成k个簇。
            （3）重新计算每个簇的质心。
            （4）不断重复（2），（3），直到质心不发生变化。

        聚类的目标可以用目标函数表示，用于度量聚类质量。

面试官：那么如何选取初始的质心呢？

程序员大树：
        一个暴力的技术是，多次运行，每次用一组不同的随机初始质心，然后选取目标函数最小的簇集。这样可能复杂度会比较高，效果也未必好，因为很可能选取的都是紧邻的点。我们希望初始质心的选择，可以让簇尽可能得散开。
        我们可以改善选取初始质心的方法。
        对于层次聚类，可以先划分成k个层次，然后每层计算质心，作为初始质心。或者可以使用k-means++算法，该算法的第一个质心是随机选择的。接下来的质心选取看离最近质心的距离，距离越大越可能被选为下一个质心，直到选为k个质心。

面试官：如何确定初始的K值呢？

程序员大树：
    （1）肘部法则。肘部法则的原理是，随着k值增大，误差值会越来越小（极端情况下，每个点自成一类，肯定误差最小），因此可根据不同k值下的误差曲线选择使误差平方和下降最快的k值，当大于此k值时，k值增大，但误差减少量很小。即选择曲线上的拐点最佳。
 

（2）轮廓系数。是评判聚类好坏的标准，结合类内聚合度以及类间分离度两种指标来计算得到。
计算方法：
    簇内不相似度：计算样本i到簇内其他样本的平均距离a(i)，a(i)越小，说明样本i越该被聚类到该簇中。
    b(i) 越大说明样本i越不属于其他簇。
    s(i)越接近于1，说明i聚类越合理。
    s(i)越接近-1，说明i更适合聚到其他类上。
    s(i)越接近0，说明i在两个簇之间的边界上。
    所有样本点的轮廓系数的平均值，为总的轮廓系数S，找到最接近于1的k值。
    比如轮廓系数S随k变化如下图，其轮廓系数最高点对应的k=3为最佳k取值。
 

面试官：K-Means算法有哪些优缺点？

程序员大树：
    2）可解释度较强

K-Means的主要缺点：
    1）K值很难确定
    2）局部最优
    3）对噪音和异常点敏感
    4）需样本存在均值（限定数据种类）

面试官：kmeans、凝聚层次聚类、dbscan的比较？

8.3 什么是凝聚层次聚类？

面试官：什么是凝聚层次聚类？

程序员大树：
        层次聚类，是一层层地把小的簇合并聚集，当然也可以将大的簇进行分割。从下向上不断聚集，叫做凝聚式层次聚类。自上而下聚类称为分裂式层次聚类。
凝聚层次聚类算法步骤：
    （1）计算临近矩阵。
    （2）合并最近两个簇
    （3）更新临近矩阵，以反映新簇与原来簇的邻近性。
    （4）不断循环（2），（3），直到只剩下一个簇时，终止循环。

度量邻近度的方法：有单链（MIN准则），全链（MAX准则），组平均技术。
单链（MIN）：簇的邻近度为不同簇最近点之间的临近度。
 
全链（MAX）：簇的邻近度为不同簇最远点之间的临近度。
 

组平均：簇的邻近度为不同簇所有点对邻近度的平均值。
 
层次聚类适用类型：擅长处理非椭圆的簇，但对噪声和离群点敏感。适用于层次结构、少量噪声的结构，不适用于高维数据。

8.4 如何使用DBSCAN？

面试官：什么是DBSCAN？

程序员大树：
        DBSCAN是一种基于密度的聚类算法。
        一些定义：
        核心点：在基于密度的簇内部。如果该点的给定半径Eps内的点个数超过阈值MinPts，则该点是核心点。
        边界点：边界点不是核心点，它落在核心点的邻域内。
        DBSCAN的核心思想是，从某个核心点出发，不断向密度可达的区域扩张，从而得到一个包含核心点和边界最大化的区域，区域中任意两点是密度相连的。

DBSCAN算法的步骤：
    （1）将所有点标记为核心点、边界点或者噪声点。
    （2）删除噪声点。
    （3）为距离在Eps内的所有核心点直接赋予一条边。
    （4）每组连通的核心点形成一个簇。
    （5）将每个边界点指派到一个与之关联的核心点的簇中。

DBSCAN优缺点：
DBSCAN的主要优点有：
    1）可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
    2）可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
    3）聚类结果没有偏倚，而相反，K-Means聚类算法初始值对聚类结果有很大影响。
DBSCAN的主要缺点有：
    1）如果样本集的密度不均匀、聚类间距差相差很大时，用DBSCAN聚类质量较差。
    2） 如果样本集较大时，用DBSCSAN聚类收敛时间较长。

面试官：如何选取参数Eps和MinPts？Eps阈值对簇密度的影响？

8.5 如何使用簇评估？

面试官：如何进行簇评估？

程序员大树：
    簇评估也叫簇确认，是用来评估簇划分质量的。
    簇评估指标可以分成三类：非监督的、监督的以及相对的。
    （I）非监督簇确认（内部指标）：聚类结构的优良性度量，不考虑外部信息。
        （1）可以使用凝聚性和分离性度量：
                1. 簇的凝聚性：确定簇中对象如何密切相关
                2. 簇的分离性：确定某个簇不同于其他簇的方面
                效果好的簇应该是凝聚性高，分离性低。
        （2）使用临近矩阵度量。最理想的临近矩阵是，簇内所有点相似度为1，与其他簇相似度为0。越接近理想矩阵，效果越好。
    （II）监督的（外部指标）：聚类算法发现的聚类结构与某种外部结构的匹配程度。
        可以用熵、纯度、精度、召回率、F度量来评估分类模型性能。
    （III）相对的：比较不同的聚类或簇，用于比较监督或非监督评估度量。

簇确认任务的流程：
    （1）确定数据集的聚类趋势，识别数据中是否存在非随机结构
    （2）确定正确簇个数
    （3）评估聚类分析结果对数据拟合情况。评估拟合指标可以用非监督簇确认指标（内部指标），比较凝聚性和分离性。
    （4）将聚类分析结果和已知的客观结果比较。可以用监督类的指标，看聚类结构与客观外部结构的匹配程度。