文档介绍：Last revised by LE LE in 2021
金融数据挖掘
金融数据挖掘论文
院系：理学院
专业班级：信息与计算科学132班
学号：
姓名：施得结果中选择一个较大的簇，继续使用K-均值算法进行分裂操作，直到得到K个簇，算法终止。
二分K-均值算法步骤如下：
输入：训练数据集D，二分次数m，目标簇数k。
输出：簇集N={N1，N2……,Nk}。
（1）初始化簇集S，它只含一个包含所有样本的簇N，将簇数K’初始化为1；
（2）从S中取出一个最大的簇Ni；
（3）使用K-均值聚类算法对簇Ni进行m次二分聚类操作；
（4）分别计算这m对子簇的总SSE的大小，将具有最小总SSE的一对子簇添加到S中，执行K’++操作；
（5）如果K’=K，算法结束。否则重复（2）到（5）步骤。
算法使用误差平方和SSE最为聚类的评价函数，对于二分K-均值聚类算法是各个步骤都是只有2个簇中心，因此相对于基本K-均值算法而言，更不易受到簇中心初始化问题的影响。二分K-均值算法中各步找出SSE之和最小的一对子簇N1和N2：
J=xi∈N1xi-m1*2+xi∈N2xi-m2*2
在二分K-均值算法中，使用误差平方和和度量聚类的质量的好坏，具体的操作是对各个样本点的误差采取欧几里德距离进行计算，然后计算误差平方和。二分K-均值算法没有初始化的问题，每一步操作实际上就是从m对子簇中找到误差平方和最小的一对子簇，然后再进行基本的K-均值操作。
BIRCH算法
Zhang 等人提出了Birch（Blanced Iterative Reducing and Clustering）[1] 算法来对大规模数据集进行聚类。Birch 算法是一种非常有效的、传统的层次聚类算法，该算法能够用一遍扫描有效地进行聚类，并能够有效地处理离群点。Birch 算法是基于距离的层次聚类，综合了层次凝聚和迭代的重定位方法，首先用自底向上的层次算法，然后用迭代的重定位来改进结果。[2]层次凝聚是采用自底向上策略，首先将每个对象作为一个原子簇，然后合并这些原子簇形成更大的簇，减少簇的数目，直到所有的对象都在一个簇中，或某个终结条件被满足。
Birch 算法的主要思想是：通过扫描数据库，建立一个初始存放于内存中的聚类特征树，然后对聚类特征树的叶结点进行聚类。它的核心是聚类特征（CF）和聚类特征树（CF Tree）。
CF 是指三元组CF=（N，LS，SS），用来概括子簇信息，而不是存储所有的数据点。其中：N：簇中d 维点的数目； LS：N 个点的线性和；SS：N 个点的平方和。比如给定一个由二维点组成的集合{(3,4),(2,6),(4,5)}，那么CF 结构概括了簇的基本信息，并且是高度压缩的，它存储了小于实际数据点的聚类信息。同时CF 的三元结构设置使得计算簇的半径、簇的直径、簇与簇之间的距离等非常容易。
Birch 算法主要分为以下两个阶段：
(1) 扫描数据库，动态的建立一棵存放在内存的CF 树。若内存不够，则增大阈值，在原树基础上构造一棵较小的树。
(2) 对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。由于 CF 树的叶节点代表的聚类可能不是自然的聚类结果，原因是给定的阈值限制了簇的大小，并且数据的输入顺序也会影响到聚类结果。因此，需要对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。
基于密度的聚类算法
DBSCAN（Density-based Spatial Clustering of Applications with Noise）
是一种基于高密度联通区域的聚类算法，它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感，并且能发现任意形状的类簇。
DBSCAN中的的几个定义：
Ε领域：给定对象半径为Ε内的区域称为该对象的Ε领域
核心对象：如果给定对象Ε领域内的样本点数大于等于MinPts，则称该对象为核心对象。
直接密度可达：对于样本集合D，如果样本点q在p的Ε领域内，并且p为核心对象，那么对象q从对象p直接密度可达。
密度可达：对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。
密度相连：对于样本集合D中的任意一点O，如果存在对象p到对象o密度可达，并且对象q到对象o密度可达，那么对象q到对象p密度相连。
可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。
Eg: 假设半径Ε=3，MinPts=3，点