|
本文是徐梓宸同学对聚类分析的整理总结。徐同学阅读了大量文献并进行了深入思考，非常值得肯定！ 本文是我基于所学，针对聚类分析的主要思想方法进行的梳理，希望能对大家有所帮助。 我将从三个部分介绍聚类分析。第一部分，我希望使用最简单的语言，将聚类分析有趣的想法介绍给大家；第二部分，我将基于教材和文献，分别对典型的聚类分析方法进行论述；第三部分，我将基于对一些有趣问题的思考，补充前两部分通俗表述的不足，努力使这篇文章不失严谨性与一般性。 一、 聚类分析的通俗理解1.1 “聚类”的核心是一件什么事情？将观测按照某种标准分为几类。 1.2 想达到什么目标？类内更相近，类间更相异。 1.3 如何评价聚类方法的好坏？将“相近”与“相异”的程度数量化，大致可以分为： 1. 相似度视角：皮尔逊相关系数等; 2. 距离视角：闵可夫斯基距离，马氏距离等 二者本质上相同，无非是相“近”的凑为一类，“远近”的定义标准有多种。 1.4 如何实现聚类？
1.5 尝试各用一句话概括基于划分：遍历所有观测，越分越“好”直到收敛。 基于分层：由“每一个观测自成一类”到“所有观测归于一类”的全过程，“截断”去寻找理想的聚类方案。 基于密度：从密度、紧密程度中发现聚类结构, 进一步将观测聚为几类。 （'基于网格'我认为是对密度的优化，通过有限划分网格，让高维空间中的观测集在低维空间中被聚类，降低计算难度。） 基于模型：假定存在参数结构，分组或寻找映射来将“最优聚类”问题转变为参数估计求解的问题。 这些并不严谨，但我希望能提供一种对核心想法的理解思路。 二、 主要方法的介绍本部分的理论介绍主要参考周志华老师《机器学习》一书. 2.1 K-means( J. MacQueen, 1967)给定观测点集 , “均值”（k-means）算法针对聚类所得到的簇划分最小化平方误差: 其中是簇的均值向量. 直观来看，上式在一定程度上刻画了簇内观测点围绕簇均值向量的紧密程度，越小则簇内观测点的相似度越高. 最小化需要遍历观测集的所有可能簇划分, 计算量颇大, 事实上已有研究表明它是一个难的问题. 因此, 均值算法采用了贪心策略, 迭代求解最优的. 从下面的伪代码中, 我们能更加清晰地看到这一点.  受篇幅限制, 这里并不过多展开. 但是想请大家关注几个有趣的细节. 其一, 初始均值向量是从观测点集中随机选取的个观测. 其二, 每一步按照'距离最近'的策略, 更新全部观测点的簇标记. 其三, 达到设定的'最大轮数'或者'最小调整幅度'时跳出迭代. 事实上, 很多有趣的改进方法就是针对这些细节提出的, 但为保证行文的连贯性, 我将在第三部分讨论. 在学习过程中, 我认为以下几处很有趣: (1). 多次重复( 初始化) 的必要性: 许多研究表明, 不同的'初始均值向量'选取可能会产生完全不同的聚类结果. (2). 收敛与质心(k-centroid)的观点: 事实上, 均值最终在寻找的便是质心, '平均值'只是其中一种特例. 而质心的核心思想不妨理解为对'用一个点如何概括整个物体质量的分布信息'这一问题的回答, 在聚类中便是用一个点去'最优'地刻画一个簇的所有观测. 不同的划分, 其实会产生不同的'均值', 即质心. 通过迭代的算法, 我们实际上找到了最稳定的划分及对应的个均值. 这里有几个有趣的问题, 为什么最终会收敛到最优的均值? 为什么这个最优不是全局的, 还会随着初始向量的选择改变? 欧氏距离之外, 推广至任意度量空间(metric spaces)的'质心'是否还有意义? (3). 调参与k值选取: 在许多介绍聚类算法的书籍中, 都有一个很tricky的地方. 都假定了'聚类簇数为', 但并没告诉我们该怎么选这里的. 事实上, 这便是后续许多算法改进的初衷. 均值算法的思想很简单, 但存在许多缺点和改进措施, 我也将在第三部分展开介绍. 2.2 AGNES( AGglomerative NESting)层次聚类(hierarchical clustering)试图在不同层次对观测点集进行划分, 形成树形的聚类结构. 是其中一种采用'自底而上'聚合策略的典型算法. 在这种算法中, 观测集中的每个观测点看做一个初始聚类簇, 然后在算法运行的每一步中找到'距离最近'的两个聚类簇进行合并, 不断重复该过程, 直到达到预设的聚类簇个数. 这其中有一个关键问题, 如何定义并计算聚类簇之间的'距离'? 书中介绍了几种常见的距离, 列举如下: 最小距离: 最大距离: 平均距离: 豪斯多夫距离( Hausdorff distance): 其中 显然, 最小距离由两个簇的最近观测点决定, 由此类推最大距离和平均距离. 但几种距离中, 集合间距离通常采用最后一种来度量, 而它相对不好理解, 所以我将在下一部分中提供一种解释思路. 有趣的巧合是, 这里的Hausdorff也是上节结尾度量空间 (metric spaces) 最早的提出者(Set Theory, 1927). 下面给出算法的伪代码和得到的树状图.   这里给出《统计学习导论》中的一个图片, 辅助理解. 需要注意的是, 算法中是按照'最近距离'的原则合并两个簇为一个新簇, 所以虽然层次聚类会经过'单个观测成为一簇'合并至'所有观测成为一类'的过程, 但簇划分的合并存在先后顺序, 在'树'中直观表现为'分支长度'不同. 在学习过程中, 我认为这种思想同样有许多有趣的地方: (1). “两两凑为一类”再到最终节点，“所有都凑为一类”的分层处理思想, 这样应该会加大计算复杂度, 但思维方法却获得了极大简化. (2). 同样是树状结构, 决策树、系统发育树和'聚类树'都是人类能够更直观认识数据的形式, 同时对计算机而言同样易于'理解', 这一性质也很有趣. (3). 值遍历了1~n而不必由我们预设, 同时, 参数不同水平时的聚类效果可以很直观看到(截断观察). 2.3 DBSCAN( Density-Based Spatial Clustering of Application with Noise, Ester, 1996)是一种著名的密度聚类算法. 密度聚类(density-based clustering)假设聚类结构能够通过样本分布的紧密程度确定. 通常情况下, 密度聚类算法从样本密度的角度考察样本间的可连续性, 基于可连接样本不断扩展聚类簇以获得最终的聚类结果. 用平白的话说, 就是将密集区域中的某个点定为'核心对象', 把和它认定'临近'的观测都'顺藤摸瓜'地提取出来成为一类, '一提一大串'. 绕不开的是如何定义并找到'核心对象'? 我们认为'周围'观测点足够'多'的点是'核心对象'.
如何将观测集按照'核心对象'聚成类? 基于某种'传递性'.
这些概念与学习随机过程时, 对链中转移情况的讨论有许多异曲同工的地方, 所以不多展开了. 周老师书中的一幅图可以辅助理解.  基于这些概念, 将'簇'定义为: 由密度可达关系导出的最大的密度相连的观测点集合. 在实际应用中, 算法先任选数据集中的一个核心对象为'种子'(seed), 再由此出发确定相应的聚类簇, 在排除了已选出观测点的集合中, 继续确定新的聚类簇, 直到所有核心对象被访问过为止. 以下是这种算法的伪代码.  需要注意的是, 筛选出核心对象的集合后, 被排除在外的观测将被认为是噪音, 不会进入下一步的聚类. 这一点既是它的优势, 可以将噪音'干干净净'地剔除, 也是它的缺点, 受初始参数和样本密度影响, 很难在不同密度的数据中(如下图)识别并生成聚类簇.  同样地, 在学习的过程中, 我认为这些地方很有趣: (1). 作为噪声的“观测点”可以被分离出来, 不进入任何一个簇, 这一点是独特的. (2). 连“点”成“串”，探索聚类结构并“一提一大串”的想法. 事实上, 对'密度'信息的利用, 使我们并不需要对所有观测点进行相同的分析, 只要对筛选出的'核心对象'进行分析便可. (3). 这里虽然不用我们设置聚类簇数, 但对初值和的依赖性较强, 二者的选择仍然是一个很重要的问题. 此外, 在核心对象的集合中聚类时, 仍然是单个点开始, 计算效率是一个值得关注的问题. 2.4 GMM( Mixture of Gaussians, Dempster, 1977)这个算法的理解, 并不容易. 但我认为可以按这样的思路理解. 在聚类簇数给定时, 高斯混合模型(GMM)聚类假定每个簇的观测服从一种(多元)正态分布, 通过贝叶斯定理, 把'将已知观测点聚为个类'的问题, 转化为了'给定个类的高斯分布, 从中采样并混合, 使得出现观测点集这种情况的概率(似然)最大'这样的问题, 而后者只是一个参数估计和求解的问题. 由于王子涵同学已基于EM算法对GMM算法进行了阐释, 下面对GMM的介绍将相对简略. 我们可以定义高斯混合分布: 该分布共由k个混合成分组成, 每个混合成分对应一个高斯分布. 其中和是第个高斯混合成分的参数, 而为相应的'混合系数'(mixture coefficient), . 假设观测的生成过程有高斯分布给出: 首先, 根据定义的先验分布选择高斯混合成分, 其中其中为选择第个混合成分的概率; 然后, 根据被选择的混合成分的概率密度进行采样, 生成相应的样本. 若训练集为由上述过程生成, 令随机变量表示生成样本的高斯混合分布, 其取值未知. 显然, 的先验概率对应于 .根据贝叶斯定理, 的后验分布对应于: 它给出观测点由第个高斯混合成分生成的后验概率. 按照后验概率大小, 为观测点赋予最可能的簇标签. 后面只是模型参数的求解问题, 中间使用到了非常关键的算法来求解这些隐变量, 详细过程请参考王子涵同学的文章和郭老师的介绍, 这里我将直接给出这个过程的伪代码.  学习过程中, 我觉得这个算法思路吸引了我的地方主要有以下几点. (1). 巧妙的假定: 定义了一个高斯混合分布, 由个混合成分 (也即簇划分) 组成, 每个混合成分对应一个高斯分布. 于是后面的核心问题就转化为在已知的分布假定下, 求解 (估计) 参数了. (2). 算法为隐变量求解提供了很重要的理论基础. 事实上, 算法可以理解为使用坐标下降(coordinate descent)求解最大化似然下界的问题 (更具体些, 通过 Jensen 不等式得出似然函数的下界，通过极大化下界做到极大化似然函数) ,而这些想法真的很神奇. (3). 贝叶斯定理的运用使得第一点具有了可能性, 对于不确定性事件发生的可能性, 使用了可以不断更新的后验概率去刻画. 2.5 本部分小结在学习的过程中，我认为这些方法是存在层次、特点鲜明的。基于划分和基于分层的两种方法，想法相对简单而计算复杂度较大，其中均值算法的原始问题已有研究表明是难问题。事实上，如果任务是将三个观测点聚为两类，我们手动枚举也能完成。前两类方法我认为就可以理解为遍历所有样本点，以计算量的提高换取思想方法的简单、操作的便捷。 基于密度的方法利用了“密度”的辅助信息，多了一步筛选，找到邻域内观测点很多的“核心对象”并在它们中间顺藤摸瓜找到一个个“簇”，从某个核心对象“一提一大串”地实现了聚类。基于网格的方法可以理解为对密度方法的优化，划分出有限个网格，将高维空间的观测处理到低维空间中完成聚类，优化了计算复杂度。 基于模型的方法同样非常有趣，我认为可以理解为在聚类簇数给定时，假设聚类簇是确定的个，认为每个“簇”中的观测点应当服从相同的分布，在贝叶斯视角下，计算观测点属于某一类的后验概率，并使用算法逼近获得参数的最优解，即为聚类结果的局部最优。 受篇幅限制，上面并未介绍谱聚类，但它同样是常用且有趣的方法。它的主要思想是将点与点的关系整合在“图”（无向权重图）中，用“边”（不妨简单理解为连线）的权重刻画相关关系的有无和强弱，将聚类的任务简化为最优分割子图的任务。使用“图”的方法来求解的好处是可以将点与点的关系整合在矩阵中（邻接矩阵和相关矩阵，并进一步有拉普拉斯矩阵)，进而我们可以使用矩阵的手段对原问题进行简化（如进行谱分解、降维等方法简化矩阵结构）。事实上，谱聚类的三个步骤主要便是相似矩阵的生成，切图以及最后的聚类，而'聚类'步骤最常用的方法便是刚刚介绍过的均值算法。 三、 一些很有趣的问题这部分是我学习过程中的困惑以及和老师讨论后的解答, 希望能为前两部分提供更为严谨的理论支撑. 同时, 基于问题的提出与解决, 我想整理出上周和老师讨论后的一些想法, 以期有'抛砖引玉'的作用. 3.1 如何进行的选择以及模型'好坏'的评估?事实上, 仔细观察聚类方法的假定可以发现, 大部分情形中我们需要预先指定一个k值 (类个数). 以均值算法为例, 的选取主要有以下几种方法: (1). 肘部法则(elbow method): 我们知道, 均值算法的最小化目标函数是观测与质点的平方误差, 若用畸变程度(distortions)表示每个簇的质心与簇内观测点的平方误差和, 随着聚类算法簇数的提高, 我们可以从下图中直观看到它的下降, 选取下降'拐点' (即'肘部')位置的簇数便可以获得最理想的结果. 它的本质与主成分分析、因子分析中的'碎石图'并无二致, 但这种方法主观性较强, 解释性难以令人满意.  (2). 'intelligent' version of K-Means, (Mirkin, 2005): 本质是通过异常检测, 一步步确定每一个类. 异常检测是通过AP (Anomalous Pattern) algorithm来进行的, 而后者的基本原理 (初始) 是采用时的均值算法, 将最'远端' (furthest) 的观测点设为质心进行运算. 事实上, 远端取点的想法也和数据挖掘中的理念暗合, 'the farther from normal, the more interesting' (Fayyad, 1996). 此外, Chiang 等人曾提供了该算法的一个调整版本 (adjusted version of , 2010) (3). Gap Statistic (Tibshirani, 2001): 这种方法在生物信息学 (bioinformatics) 中用得较多, 其中, Gap Statistic定义如下: 不难论证均值和标准差的形式, 最终可以得到估计量为的最小值, 并满足条件: 更多的值选取方法, 请查阅Chiang等人2010年的文章, 其中有8种方法的对比; 此外, 李高荣老师多元统计的课件中也有较为深入的讨论. 3.2 很多距离并不好理解, 它们各有什么特点和价值?先介绍上文提到过的豪斯多夫距离, 形式如下: 其中 这个距离初读很难理解, 虽然结构看着简单. 在学习过程中, 我认为理解它的核心在于'两个集合之间的距离该如何表示'这个问题. 我们当然可以使用最近或最远两点, 或者使用'中心点', 但另一种思路是, 以这个'距离'画圆(欧氏距离中), 应该能够保证全体集合与另一集合中恰好有一个点相交, 也即'够得着的最短距离'. 这是单向的理解, 再从'距离'定义中的对称性不难想到可以建立这样的结构. 下面一副图可以更直观地展示这一点. 
事实上, 距离的定义有非常非常多种, 李高荣老师的'多元统计分析'中有着更细致的讨论, 此处不再展开. 3.3 许多材料中说能够收敛到局部最优(以K-means为例), 是否真的能? 中心的度量是否可以换为其它标准?均值算法的收敛性已被许多学者研究过, 但很多严格的证法会涉及测度的知识, 较难理解. 但基于王子涵同学对算法及均值关系已有讨论, 我这里只简单给出证明. 假设簇数为已确定, 使用簇内使用平方损失函数作为目标函数, 可以变形获得畸变函数(distortion function): 其中为观测集中第个观测, 是观测属于的类, 基于最短距离的判断: , 为聚类簇的中心点. 对畸变函数求偏导, 可以获得下式: 令其为0, 可以求得极值点: 可以证得收敛. 事实上, 我认为中心位置的度量还可以采用中位数等方式, 距离的计算也可以使用曼哈顿距离、马氏距离等形式, 畸变函数也可以按照观测点到的距离远近采用不同权重 (借用核函数的思想) 来计算. 但是, 在更复杂情况下求解收敛性显然是一个更加困难的工作. 3.4 从这几个'原始'而'破绽百出'的算法出发, 研究者们做了哪些改进工作?聚类算法真的数不胜数, 实非我短期学习所能穷尽, 以下仅列出一小部分. 部分主要参考'Dengbocong'同学整理的论文集和笔记, 链接附在了文章最后. 我们知道, 均值算法初始的'均值向量'是由观测集总体中随机抽取的, 在密度分布不均(见)等情况下显然存在弊端, 密集区域的观测更有可能被选为'初始向量', 这一点会使均值算法稳定性下降. David Arthur提出了++算法(2006), 在'均值向量'的选取(抽取)环节, 采用单次单点的随机抽取方式, 抽出第一个初始均值后, 计算各观测点与它的距离, 距离远则以更大的概率被选中为下一个初始均值, 这样使初始均值向量的选取更合理. 但随之而来的是采样效率的问题, 方法(Bahman, 2012)改良'单点选取'为按照概率选择多个观测点, 提高了效率. 对初始均值向量的选取还有其它改进方法, 这里不再列举. 当然, 等算法也存在大量改进, 我认为'基于网格'就是对'基于密度'方法的改进. 有学者提出CLIQUE(CLuster In Quest, Rakesh Agrawal, 1998)算法, 它不再需要对整个高维空间进行分析, 而是通过有限的网格划分, 在更低维度子空间中形成聚类簇. 我认为这个算法的核心在于'最小描述'概念的使用, 这一概念应当可以直观理解为将高维空间的'海绵', 基于寻找'共同交集'的逻辑找到最核心的部分, '挤压海绵'降维到更低维度进行聚类, 这样降低了计算复杂度. 由于能力和精力的不足, 我对很多改进方法的理解与思考暂时只是'浅尝辄止', 所以观点仅供参考, 欢迎大家去深入阅读原始文献. 3.5 EM算法总觉得有些'玄妙', 但我是被它哪里的妙吸引了?这一话题王子涵同学已有介绍, 我这里就不展开算法细节了. 其实这个算法吸引我的点, 除了简明的E和M两步, 更在于它似乎回应了对一个问题的思考, 即'我们如何发掘未知信息, 求解隐变量(latent variable)'. 事实上, 我认为最有趣的一点体现在下面的式子中. 其中是隐变量. 隐变量的信息我们并不知道, 如何才能优化求解它呢? 在全概率公式的框架下, 利用概率的归一性, 我们可以用'概率求和'的结构 (E-step求期望的想法似乎也如此) , 将隐变量真正引入分析的过程. 假设真值存在, 再逼近去求解, 这样的思路简单而有趣. 3.6 高斯混合模型中, 是否可以按照'聚类→给定个簇的条件→分类问题→参数求解'的思路理解?这个问题我认为应该慎重, 虽然变为'分类问题'会极大方便我们的理解. 学习的过程中, 我认为聚类和分类的'核心动作'都是基于已知数据(观测)去训练一个algorithm或者更广义地说, 一个'classifier'. 只不过聚类中的'类'实际是个隐变量. 通过贝叶斯定理, 我们对'因果'有了更精细的讨论, 但事实上, 这一切只是基于条件概率和全概率公式框架的计算方式, 并非真的允许逻辑改变. 所以从计算机模拟, 基于各个高斯分布采样生成混合分布, 达到对观测集更优拟合的角度去理解我认为更'安全'. 或许, 在更深入了解贝叶斯学派的思想后, 我会对这个问题的认识更加清晰. 3.7 CV方法能不能用, 该怎么使用?课后我曾与郭老师和李老师讨论过这个问题, 但并未得出明确的答案. 事实上, 在给定值下, 若将聚类出几个特定簇的整体视为训练'classifier'的工作, 从使用交叉验证(cross validation)评价分类问题的角度, 应该是可以说通的. 但我认为这里有两个核心问题, 第一, 聚类和分类的差异表面在于'是否存在已知类标签', 是有无监督的问题. 但我认为二者的差别还在于'可知'与'不可知', 若将聚类结果视为已知, 变成分类问题, 我目前认为存在上文所说的'因果'问题, 需要慎重. 第二, 在实际应用中, 我们常会使用已知数据集, 使用不含标签的数据去训练聚类算法, 再将获得的聚类结果与真实情况进行比对, 这里应当可以使用交叉验证, 在分类问题的框架下检测'classifier'的稳定性. 如果这个思路成立, 那么又会出现赵俊龙老师讲到的问题, 我们评价模型所用的大多是简单的数据集 (toy examples), 而评价其在真实数据集中的表现是很困难的. 当然, 在学习过程中我也看到了一篇文章(Wei Fu, 2017), 使用Gabriel Cross Validation去选择聚类簇数, 尚未完全理解, 谨列在附录中. 3.8 文中聚类方法的种类与原始文献中有所不同, 是否合理?在许多文献中, K均值算法、GMM和许多聚类算法一起被统称为'基于原型的聚类' (prototype-based clustering), 这类算法假设聚类结构可以通过一组原型刻画. 其通常情形分为以下两步: 1. 对原型进行初始化 2. 对原型迭代更新求解. 由于均值算法过于重要, 且'原型初始化+更新'的思想太过笼统, 所以我参考其它材料, 将它以及由它衍生的方法单独列出为'基于划分'的聚类, 从'遍历划分+迭代收敛至最优'的思路加以理解, 以期能更简明地发现不同方法尤其是均值算法上的继承与嬗变。 还有许多问题, 因篇幅和精力的限制, 暂且搁置讨论, 保留作我以后思考的主题和方向. 四、 参考资料与后记英文文献:以下文献很多我尚未开始学习或还未理解清晰, 但在学习过程中我曾多次看到它们, 均为聚类领域很重要的工作, 所以谨罗列在下面, 以便感兴趣的同学们检索.
中文材料（主要）:
|
|
|
