层次聚类算法.ppt

7.5层次聚类方法 层次聚类方法概述 层次聚类方法将数据对象组成一棵聚类树。 根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。 层次聚类方法概述 凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。 分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。 层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。 簇间距离 最小距离 簇间距离 最大距离 簇间距离 平均距离 簇间距离 均值距离 AGNES算法 AGNES(AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。 聚类的合并过程反复进行直到所有的对象最终满足簇数目。 AGNES算法 输入：n个对象，终止条件簇的数目k。 输出：k个簇，达到终止条件规定簇数目。 (1)将每个对象当成一个初始簇； (2)REPEAT (3)根据两个簇中最近的数据点找到最近的两个簇； (4)合并两个簇，生成新的簇的集合； (5)UNTIL达到定义的簇的数目； AGNES算法例题 AGNES特点 AGNES算法比较简单，但经常会遇到合并点选择的困难。假如一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤销，聚类之间也不能交换对象。如果在某一步没有很好的选择合并的决定，可能会导致低质量的聚类结果。 DIANA算法 DIANA（Divisive ANAlysis)算法是典型的分裂聚类方法。 在聚类中，用户能定义希望得到的簇数目作为一个结束条件。 DIANA算法例题 层次聚类方法的改进 层次聚类方法尽管简单，但经常会遇到合并或分裂点的选择的困难。 改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。 下面介绍3个改进的层次聚类方法BIRTH， ROCK和Chameleon。 BIRCH算法 BIRCH （Balanced Iterative Reducing and Clustering） 利用层次方法的平衡迭代归约和聚类 用聚类特征（CF）和聚类特征树来概括聚类描述。 该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。 聚类特征（CF） CF(Clustering Feature)：包含簇信息的三元组(N,LS,SS)，N：簇的数据点；LS：线性和； SS：平方和 假定在簇C1中有三个点(2,5),(3,2),(4,3) 聚类特征是： CF1=3,(2+3+4,5+2+3),(22+32+42,52+22+32) =3,(9,10),(29,38) 聚类特征树 CF树是一个具有两个参数分支因子B和阈值T的高度平衡树。 分支因子B：非叶节点可以拥有的孩子数 阈值T：叶子节点中的子聚类的最大直径 BIRCH算法 阶段一：扫描数据库，建立一个初始的CF树，它可以被看作一个数据的多层压缩，试图保留数据内在的聚类结构。当一个对象被插入到最近的叶节点（子聚类）中时，随着对象的插入，CF树被动态地构造，因此，BIRTH方法对增量或动态聚类也非常有效。 阶段二：采用某个聚类算法对CF树的叶节点进行聚类。在这个阶段可以执行任何聚类算法。 ROCK ROCK(Robust Clustering using linKs,使用连接的鲁棒聚类 大多数聚类算法在进行聚类时只估计点与点之间的相似度，即在每一步中那些最相似的几个点合并到一个簇中。这种“局部”方法很容易导致错误。例如：两个完全不同的簇可能有少数几个点的距离较近，仅仅依据点与点之间的相似度来做出聚类决定就会导致这两个簇合并。 ROCK采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。 ROCK 两个概念：近邻和链接 近邻：两个点pi和pj是近邻，如果sim(pi,pj)=θ,sim是相似度函数，θ是指定的阈值 链接：两个点pi和pj的链接数定义为这两点的共同近邻个数。 由于在确定点对之间的关系时考虑邻近的数据点，因此比只关注相似度的聚类方法更加鲁棒。 ROCK 例：购物篮数据库包含关于商品a,b,…g的事物记录。簇C1涉及商品{a,b,c,d,e},簇C2涉及商品{a,b,f,g} 假设：只考虑相似度而忽略邻域信息。 C1中{a,b,c}和{b,d,e}之间的Jaccard系数 是0.2 而C1中的{a,b,c}和C2中的{a,b,f}的Jaccard系数 是0.5 说明：仅根据Jaccard系数， 很容易导致