数值型变量值的 总和及平方和
2 CFj {N j , S Aj , S Aj , N Bj }
2 2 CF j ,s {N j N s , S Aj S As , S Aj S As , N Bj N Bs }
两步聚类算法：预聚类

预聚类过程:建立CF树 视所有数据为大类，汇总统计量存在根结点中 读入一个样本点，从CF树的根结点开始，利用 结点的汇总统计量，计算数据与中间结点的对 数似然距离。沿对数似然距离最小的中间结点 依次向下选择路径直到叶结点 计算与子树中所有叶结点（子类）的对数似然 距离，找到距离最近的叶结点
聚类算法种类


从聚类变量类型角度划分 数值型聚类算法、分类型聚类算法、混合型聚 类算法 从聚类的原理角度划分 划分聚类（Partitional clustering） 层次聚类（Hierarchical clustering） 基于密度的聚类（Density-based clustering ） 网格聚类（Rid clustering ）
两步聚类算法：预聚类

预聚类过程 如果最近距离小于一定阈值，则该数据被相应 的叶结点“吸收”；否则，该数据将“开辟” 一个新的叶结点。重新计算叶结点和相应所有 父结点的汇总统计量 叶结点足够大时应再分裂成两个叶结点 叶结点个数达到允许的最大聚类数目时，应适 当增加阈值重新建树，以得到一棵较小的CF树 重复上述过程，直到所有数据均被分配到某个 叶结点（子类）为止
两步聚类算法

两步聚类：Chiu，2001年在BIRCH（Balanced
Iterative Reducing and Clustering using Hierarchies）算法基础上提出的一种改进算法

特点： 算法尤其适合于大型数据集的聚类研究 通过两步实现数据聚类 同时处理数值型聚类变量和分类型聚类变量 根据一定准则确定聚类数目 诊断样本中的离群点和噪声数据
f ( x) j f j ( X ; j )
j 1

如果数据矩阵的各行独立，则：
l iI log p( X i | j ) l j
j 1
j
J
J
j 1
“亲疏程度”的测度

K个聚类变量x1，x2，…xk，KA个数值型聚类变量 和KB个分类型聚类变量。对数似然距离定义为：
两步聚类算法：预聚类

离群点的甄别 离群点，即那些合并到任何一个类中都不恰当 的数据点 两步聚类的处理策略： 找到包含样本量较少的“小”叶结点，如 果其中的样本量仅是“最大”叶结点所含 样本量的很小比例，则视这些叶结点中的 数据点为离群点(Modeler默认为25%)
两步聚类算法：聚类
两步聚类算法


第一步，预聚类 采用“贯序”方式将样本粗略划分成 L个子类 预聚类过程聚类数目不断增加 第二步，聚类 在预聚类的基础上，再根据“亲疏程度”决定 哪些子类可以合并，或者哪些子类可以在拆分 为更小的子类，最终形成L’类
“亲疏程度”的测度


聚类变量均为数值型（标准化后），采用欧氏距 离，否则，采用对数似然距离 通过对数似然函数的形式描述全部样本的聚类分 布特征:混合分布,总体分布描述为有限个子分布 J 的加权线性组合


聚类过程：分析对象是预聚类所形成的稠密区域 方法：层次聚类法 逐步将较多的小类合并为较少的大类，再将较 少的大类合并成更少的更大类，最终将更大类 的合并成一个大类，是一个类不断“凝聚”的 过程 问题： 第一，内存容量问题 第二，怎样的聚类数目是合适的问题
聚类数目的确定

第一阶段：依据BIC，确定粗略的聚类数 依据类内部差异性并兼顾模型复杂度
聚类分析
主要内容

聚类分析方法概述 两步聚类方法 基于聚类分析的离群点探索
聚类分析方法概述


聚类分析是对数据进行描述建模型的方法，目的 探索数据中是否存在“自然的子类” 聚类算法的种类 从聚类结果角度划分 从聚类变量类型角度划分 从聚类原理角度划分
聚类算法种类

从聚类结果角度划分： 覆盖聚类与非覆盖聚类：每个数据点都至少属 于一个类，为覆盖聚类，否则为非覆盖聚类 层次聚类和非层次聚类：存在两个类，其中一 个类是另一个类的子集，为层次聚类，否则为 非层次聚类 确定聚类和模糊聚类：任意两个类的交集为空 ，一个数据点最多只属于一个类，为确定聚类 （或硬聚类）。否则，如果至少一个数据点属 于一个以上的类，为模糊聚类

反应了类内部变量取值的总体差异性（定距变量 以方差测度，分类型变量以熵测度）
两步聚类算法：预聚类

算法是Zhang等，1996，BIRCH算法的改进算法， CF树（Clustering Feature Tree ） CF树是一种描述树结构的数据存储方式 叶结点为子类，具有同一父结点的若干子 类合并为一个大类形成树的中间结点。若 干大类合并成更大的类形成更高层的中间 结点，直到根结点表示所有数据形成一类 CF树是一种数据压缩存储方式 (充分统计量)
d ( j, s) lˆ lˆnew lˆj lˆs lˆ j ,s j s j ,s
合并之前的 对数似然
KA KBຫໍສະໝຸດ 合并之后的 对数似然k
L N vkl N vkl 1 2 2 ˆ ˆ log( ) ˆ k ˆ vk ) Evk ) Evk v N v ( log( Nv l 1 N v k 1 2 k 1
BIC( J ) 2 j mJ log(N )
j 1 J
mJ J (2 K A ( Lk 1))
k 1
KB

所有类合并成一个大类，BIC的第一项最大， 第二项最小。当聚类数目增加时，第一项逐渐 减少，第二项逐渐增大，但BIC总体上减少； 当聚类数目增加到J时，第二项的增大幅度开 始大于第一项的减少幅度，BIC总体上开始增 大，此刻的J即为所求