Clementine-第七讲

聚类分析主要内容聚类分析方法概述两步聚类方法基于聚类分析的离群点探索聚类分析方法概述聚类分析是对数据进行描述建模型的方法，目的探索数据中是否存在“自然的子类”聚类算法的种类从聚类结果角度划分从聚类变量类型角度划分从聚类原理角度划分聚类算法种类从聚类结果角度划分：覆盖聚类与非覆盖聚类：每个数据点都至少属于一个类，为覆盖聚类，否则为非覆盖聚类层次聚类和非层次聚类：存在两个类，其中一个类是另一个类的子集，为层次聚类，否则为非层次聚类确定聚类和模糊聚类：任意两个类的交集为空，一个数据点最多只属于一个类，为确定聚类（或硬聚类）。否则，如果至少一个数据点属于一个以上的类，为模糊聚类聚类算法种类从聚类变量类型角度划分数值型聚类算法、分类型聚类算法、混合型聚类算法从聚类的原理角度划分划分聚类（Partitionalclustering）层次聚类（Hierarchicalclustering）基于密度的聚类（Density-basedclustering）网格聚类（Ridclustering）两步聚类算法两步聚类：Chiu，2001年在BIRCH（BalancedIterativeReducingandClusteringusingHierarchies）算法基础上提出的一种改进算法特点：算法尤其适合于大型数据集的聚类研究通过两步实现数据聚类同时处理数值型聚类变量和分类型聚类变量根据一定准则确定聚类数目诊断样本中的离群点和噪声数据两步聚类算法第一步，预聚类采用“贯序”方式将样本粗略划分成L个子类预聚类过程聚类数目不断增加第二步，聚类在预聚类的基础上，再根据“亲疏程度”决定哪些子类可以合并，或者哪些子类可以在拆分为更小的子类，最终形成L’类聚类变量均为数值型（标准化后），采用欧氏距离，否则，采用对数似然距离通过对数似然函数的形式描述全部样本的聚类分布特征:混合分布,总体分布描述为有限个子分布的加权线性组合如果数据矩阵的各行独立，则：JjjjjXfxf1);()(JjJjjIijilXplj11)|(log“亲疏程度”的测度“亲疏程度”的测度K个聚类变量x1，x2，…xk，KA个数值型聚类变量和KB个分类型聚类变量。对数似然距离定义为：反应了类内部变量取值的总体差异性（定距变量以方差测度，分类型变量以熵测度）sjsjsjsjnewlllllsjd,,ˆˆˆˆˆ),(合并之前的对数似然合并之后的对数似然)ˆ)ˆˆlog(21(1212BAKkvkvkKkkvvEN)log(ˆ1vvklLlvvklvkNNNNEk两步聚类算法：预聚类算法是Zhang等，1996，BIRCH算法的改进算法，CF树（ClusteringFeatureTree）CF树是一种描述树结构的数据存储方式叶结点为子类，具有同一父结点的若干子类合并为一个大类形成树的中间结点。若干大类合并成更大的类形成更高层的中间结点，直到根结点表示所有数据形成一类CF树是一种数据压缩存储方式(充分统计量)},,,{2BjAjAjjjNSSNCF},,,{22,BsBjAsAjAsAjsjsjNNSSSSNNCF数值型变量值的总和及平方和两步聚类算法：预聚类预聚类过程:建立CF树视所有数据为大类，汇总统计量存在根结点中读入一个样本点，从CF树的根结点开始，利用结点的汇总统计量，计算数据与中间结点的对数似然距离。沿对数似然距离最小的中间结点依次向下选择路径直到叶结点计算与子树中所有叶结点（子类）的对数似然距离，找到距离最近的叶结点两步聚类算法：预聚类预聚类过程如果最近距离小于一定阈值，则该数据被相应的叶结点“吸收”；否则，该数据将“开辟”一个新的叶结点。重新计算叶结点和相应所有父结点的汇总统计量叶结点足够大时应再分裂成两个叶结点叶结点个数达到允许的最大聚类数目时，应适当增加阈值重新建树，以得到一棵较小的CF树重复上述过程，直到所有数据均被分配到某个叶结点（子类）为止两步聚类算法：预聚类离群点的甄别离群点，即那些合并到任何一个类中都不恰当的数据点两步聚类的处理策略：找到包含样本量较少的“小”叶结点，如果其中的样本量仅是“最大”叶结点所含样本量的很小比例，则视这些叶结点中的数据点为离群点(Clementine默认为25%)两步聚类算法：聚类聚类过程：分析对象是预聚类所形成的稠密区域方法：层次聚类法逐步将较多的小类合并为较少的大类，再将较少的大类合并成更少的更大类，最终将更大类的合并成一个大类，是一个类不断“凝聚”的过程问题：第一，内存容量问题第二，怎样的聚类数目是合适的问题聚类数目的确定第一阶段：依据BIC，确定粗略的聚类数依据类内部差异性并兼顾模型复杂度所有类合并成一个大类，BIC的第一项最大，第二项最小。当聚类数目增加时，第一项逐渐减少，第二项逐渐增大，但BIC总体上减少；当聚类数目增加到J时，第二项的增大幅度开始大于第一项的减少幅度，BIC总体上开始增大，此刻的J即为所求JjJjNmJBIC1)log(2)())1(2(1BKkkAJLKJm聚类数目的确定第一阶段：依据BIC，确定粗略的聚类数)1()()(JBICJBICJdBIC)1()()(1dBICJdBICJR•计算“定基”负增长率•找到R1(J)取最小值（Clementine规定R1(J)应小于0.04）的J为聚类数目的“粗略”估计第二阶段：对“粗略”估计值J的修正2,3,4,…,J中选择。仅依据类间对数似然距离，不考虑模型复杂度)()()(1minmin2JJCdCdJRJ类时的最小对数似然距离d(4)d(3)d(2)d(5)•计算R2(J-1)、R2(J-2)到R2(2)的值，分别反映将J-1类拆成J类后类间距离的比率。越大表明拆开后类间距离的增大越不显著，越不应拆•Clementine找到最大值和次大值。若最大值是次大值的1.15倍以上，则最大值对应的J为最终聚类数；否则为最大值对应的聚类数目和次大值对应的聚类数目中的较大值聚类算法应用以Telephon.sav为例。目标：保留客户的细分服务套餐选择分布存在差异是否选择无线服务的分布存在差异受教育水平和收入等方面的分布也存在差异Clementine无法设置最近距离阈值;无法设置离群点的甄别标准基于聚类分析的离群点探索离群点的检测：描述为一个从n个样本中选k个与其他数据显著不同、例外或不相一致的样本的过程包括：有指导学习和无指导学习两类方法多维空间基于聚类的诊断方法通过聚类和计算样本点与数据组群之间的距离，以及距离远近的判断，实现离群点的诊断以及离群点成因的分析基于聚类分析的离群点探索离群点的检测基于聚类分析的离群点探索离群点分析的三个阶段：第一，聚类，即根据“亲疏程度”将样本点聚成若干类；第二，计算，即在第一阶段聚类的基础上，依据距离，计算所有样本点的异常性测度指标第三，诊断，即在第二阶段异常性测度指标的基础上，确定最终的离群点，并分析导致样本点异常的原因，即分析离群点在哪个变量方向上呈现异常基于聚类分析的离群点探索离群点分析的三个阶段：第一，聚类，即根据“亲疏程度”将样本点聚成若干类；第二，计算，即在第一阶段聚类的基础上，依据距离，计算所有样本点的异常性测度指标第三，诊断，即在第二阶段异常性测度指标的基础上，确定最终的离群点，并分析导致样本点异常的原因，即分析离群点在哪个变量方向上呈现异常基于聚类分析的离群点探索第二阶段：计算样本的离群测度指标对于样本点S，找到样本点S所属的类v计算样本点S与类别v的对数似然距离，称之为组差异指标GDI(GroupDeviationIndex)vvklLlvvklvkKkvkvkKkkvvsvvsvsvSNNNNEENsvdGDIkBAlogˆ)ˆ)ˆˆlog(21(),(11212,,GDI反映了样本点S加入类v引起的类v内部差异的增大量基于聚类分析的离群点探索第二阶段：计算样本的离群测度指标对于样本点S，计算聚类变量k的变量差异指标VDI（VariableDeviationIndex）对于数值型聚类变量k：对于分类型聚类变量k：VDI是样本点S加入类v所引起的类v内部差异增大量中，各聚类变量的“贡献”大小)ˆˆlog(2122vkkkVDI)log(1vvklLlvvklkNNNNVDIk基于聚类分析的离群点探索第二阶段：计算样本的离群测度指标对于样本点S，计算异常指标AI（AnomalyIndex）样本点S所引起的类内差异与类v内其他样本点所引起差异的平均值的比。该值越大，认为样本点S是离群点的把握程度就越大vNiivSSGDINGDIAI11基于聚类分析的离群点探索第二阶段：计算样本的离群测度指标对于样本点S，计算变量贡献指标VCM（VariableContributionMeasures）VCM是各聚类变量对差异“贡献”的比例。该值越大，则相应变量是导致样本点S离群原因的可能性越大skSGDIVDIVCM基于聚类分析的离群点探索第三阶段：依据指标的排序结果，确定离群点并分析导致异常的原因将AI按降序排，排在前m位的样本点可能为离群点m位置的AI就是离群点的判断标准。大于该值的为离群点，小于为非离群点对于离群点，将VDI按照降序排序，排在前n位的变量是导致该点可能异常的主要原因基于聚类分析的离群点探索应用示例：以Telephone.sav为例，找到保留客户中可能的异常客户0.5-NoiseLevel是两步聚类中异常类的判定标准，NoiseLevel取值范围：[0,0.5]。Noiselevel越小接近于0，意味着聚类过程越可能找到异常类；增大该值越接近0.5，意味着算法越可能视异常类为正常类平均VDI，AI值基于聚类分析的离群点探索说明：Anomaly节点总能找到离群点，只能视为“疑似异常点”无指导的学习方法，可首先找到与输出变量相关的几个重要输入变量，然后再利用Anomaly节点诊断异常