正文 

当前位置： 首页 > 程序 > java教程

第二节：层次聚类算法之birch算法(代码片段)

快乐江湖 快乐江湖     2022-10-21     717

关键词：

文章目录

一：BIRCH算法概述

BIRCH算法：该算法于1996年提出，尤其适用于大型数据库。它会增量地对输入数据进行聚类，有时甚至只需对所有数据扫描一遍就可以产生结果，当然额外的扫描肯定可以提升聚类效果，而且还可以有效处理噪声。BIRCH算法需要引入以下两个概念

  • 聚类特征（CF）
  • 聚类特征数（CF树）

聚类特征数类似于平衡B+树，CF树的每个结点是由若干聚类特征CF组成的

（1）聚类特征CF

聚类特征CF：一个聚类特征由一个三元组表示，它给出了一个簇的汇总描述。在大小为 N N N的 d d d维数据集 x 1 , x 2 , . . . , x N \\x_1,x_2,...,x_N\\ x1​,x2​,...,xN​上，定义聚类特征如下

C F = ( N , L S ⃗ , S S ) CF=(N,\\vecLS,SS) CF=(N,LS ,SS)

  • N N N：数据数量
  • L S ⃗ \\vecLS LS ： N N N个数据点的线性和，也即 ∑ i = 1 N x i ⃗ \\sum\\limits_i=1^N \\vecx_i i=1∑N​xi​ ​
  • S S SS SS： N N N个数据点的平方和，也即 ∑ i = 1 N x i 2 ⃗ \\sum\\limits_i=1^N \\vecx_i^2 i=1∑N​xi2​ ​

聚类特征是可以求和的

  • C F 1 = ( N 1 , L S 1 ⃗ , S S 1 ) CF_1=(N_1,\\vecLS_1,SS_1) CF1​=(N1​,LS1​ ​,SS1​)
  • C F 2 = ( N 2 , L S 2 ⃗ , S S 2 ) CF_2=(N_2,\\vecLS_2,SS_2) CF2​=(N2​,LS2​ ​,SS2​)
  • C F 1 + C F 2 = ( N 1 + N 2 , L S 1 ⃗ + L S 2 ⃗ , S S 1 + S S 2 ) CF_1+CF_2=(N_1+N_2,\\vecLS_1+\\vecLS_2,SS_1+SS_2) CF1​+CF2​=(N1​+N2​,LS1​ ​+LS2​ ​,SS1​+SS2​)

如下图，有5个样本形成的一个簇，分别是 ( 3 , 4 ) , ( 2 , 6 ) , ( 4 , 5 ) , ( 4 , 7 ) , ( 3 , 8 ) (3, 4),(2,6),(4,5),(4,7),(3,8) (3,4),(2,6),(4,5),(4,7),(3,8)，则有

  • N N N：5
  • L S ⃗ \\vecLS LS ： ( 3 + 2 + 4 + 4 + 3 , 4 + 6 + 5 + 7 + 8 ) = ( 16 , 30 ) (3+2+4+4+3, 4+6+5+7+8)=(16, 30) (3+2+4+4+3,4+6+5+7+8)=(16,30)
  • S S SS SS： ( 3 2 + 2 2 + 4 2 + 4 2 + 3 2 + 4 2 + 6 2 + 5 2 + 7 2 + 8 2 ) = 244 (3^2+2^2+4^2+4^2+3^2 +4^2+6^2+5^2+7^2+8^2)=244 (32+22+42+42+32+42+62+52+72+82)=244

（2）聚类特征树

聚类特征树：一个CF树存储了层次聚类的聚类特征。它存储了层次聚类的聚类特征。下图是一个典型的CF树。CF树中每个非叶结点存储的CF是其孩子结点的CF总和，也即父结点存储的信息是其子结点存储信息的汇总。一个叶子结点至多包含 L L L个条目，每个条目是一个聚类特征三元组，每个叶子结点有两个指针，即prev和next，用来把所有的叶子结点连接起来

一个CF树有如下两个参数，当阈值 T T T越大时树就会越小，它们决定了树的大小

  • 分支因子 B B B：表示每个非叶结点最大的孩子数目
  • 阈值 T T T：：表示存储在树的叶子结点中的子聚类的最大半径

如下图，在CF树中，对于父结点的每个CF结点，它的 ( N , L S ⃗ , S S ) (N,\\vecLS,SS) (N,LS ,SS)三元组的值等于这个CF结点所指向的所有子结点的三元组之和

（3）聚类特征树的生成

A：生成规则

聚类特征树的生成规则：CF树是随数据的输入动态增长的，生成CF树的步骤如下

  • 找到要插入的叶子结点：从CF树根结点开始，通过比较结点的CF值找到距离最近的簇，然后从该簇的孩子结点中继续找到距离最近的簇，直到最后找到叶子结点
  • 修改叶子结点： 找到叶子结点中距离最近的条目，检查该叶子结点能够再加入新条目，可以的话直接加入，不可以的话分裂叶子结点并加入条目birch聚类算法的实现(代码片段)

    ...m2.BIRCH聚类算法介绍2.1BIRCH聚类算法介绍BIRCH的全称是利用层次方法的平衡迭代规约和聚类（BalancedIterativeReducingandClusteringUsingHierarchies），它是用层次方法来聚类和规约数据。BIRCH算法利用了一个树结构来帮助我们快速... 查看详情

    birch聚类算法的实现(代码片段)

    目录1.作者介绍2.BIRCH聚类算法介绍2.1BIRCH聚类算法介绍2.2聚类特征CF与聚类特征树CFTree2.3Birch聚类算法优缺点3.scikit-learn学习Birch聚类3.1Brich类参数4.实验代码与结果展示4.1完整代码4.2实现过程4.3实验结果1.作者介绍冯达，男࿰... 查看详情

    birch聚类算法原理

    ...RCH算法做一个总结。1.BIRCH概述　　　　BIRCH的全称是利用层次方法的平衡迭代规约和聚类（ 查看详情

    挑子学习笔记：birch层次聚类

      转载请标明出处：http://www.cnblogs.com/tiaozistudy/p/6129425.html    本文是“挑子”在学习BIRCH算法过程中的笔记摘录，文中不乏一些个人理解，不当之处望多加指正。本人邮箱：[email protected]  BIR... 查看详情

    挑子学习笔记：两步聚类算法（twostepclusteralgorithm）——改进的birch算法

    ...步聚类算法是在SPSSModeler中使用的一种聚类算法，是BIRCH层次聚类算法的改进版本。可以应用于混合属性数据集的聚类，同时加入了自动确定最佳簇数量的机制，使得方法更加实用。本文在学 查看详情

    第二节1：optics算法思想和算法流程(代码片段)

    文章目录一：OPTICS算法相关定义（1）相关定义（2）簇结构可视化二：算法流程OPTICS算法是从DBSCAN算法演化而来的基于层次密度的聚类算法，它可以解决DBSCAN算法中的参数敏感问题和不能很好处理数据... 查看详情

    第二节：谱聚类算法之切图聚类算法流程及其实现

    本文部分内容源自刘建平博客，在此基础上进行总结拓展原文链接文章目录一：谱聚类与图划分（1）比例割（2）规范割（常用）二：谱聚类算法流程三：Python实现四：谱聚类算法优缺点... 查看详情

    第二节4：k-means算法及其python实现（初始中心点的选择和k-means++算法）(代码片段)

    文章目录一：朴素方法二：KKK-MeansMeansMeans++算法（1）算法思想（2）算法流程（3）Python实现（4）分析三：kkk-variatesvariatesvariates++算法一：朴素方法最基本的KKK-MeansMeansMeans... 查看详情

    ml-7聚类算法-实例代码

    目录K-Means算法和MiniBatchK-Means算法比较层次聚类(BIRCH)算法参数比较DBSCAN算法一、K-Means算法和MiniBatchK-Means算法比较1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... 查看详情

    基于网格的聚类算法clique

    ...算法很多，包括基于划分的聚类算法（如：kmeans），基于层次的聚类算法（如：BIRCH），基于密度的聚类算法（如：DBScan），基于网格的聚类算法等等。基于划分和层次聚类方法都无法发现非凸面形状的簇，真正能有效发现任意... 查看详情

    层次聚类算法的实现(代码片段)

    目录1.作者介绍2．层次聚类算法介绍2.1层次聚类算法原理2.2层次聚类算法步骤2.3层次聚类算法分类3．层次聚类算法实现(代码如下)3.1相关包导入3.2生成测试数据集3.3层次聚类实现&画出树状图3.4获取聚类结果3.5完整代码... 查看详情

    层次聚类算法的实现(代码片段)

    目录1.作者介绍2．层次聚类算法介绍2.1层次聚类算法原理2.2层次聚类算法步骤2.3层次聚类算法分类3．层次聚类算法实现(代码如下)3.1相关包导入3.2生成测试数据集3.3层次聚类实现&画出树状图3.4获取聚类结果3.5完整代码... 查看详情

    机器学习实战精读--------k-均值聚类算法

    ...安置的均值计算而成。分层聚类算法①BIRCH算法：结合了层次聚类算法和迭代的重定位方法，首先用自底向上的层次算法，然后用迭代的重定位来改进效果。②DBSCAN算法：具有噪声的基于密度的聚类方法③CU 查看详情

    第二节算法中的公平——队列(代码片段)

    1、栗子学校食堂打饭、火车站买火车票、公交站等车，都要排队，先来的先上车，车满了，其余只能等下一班了。这对大多数人而言，都是相对公平的方式。在算法中，也有类似的公平——队列（queue）。队列遵循先进先出（Fir... 查看详情

    聚类算法之dbscan(代码片段)

    DBSCAN聚类算法1.DBSCAN算法基本概念DBSCAN是一种典型的基于密度的聚类算法，基于一组邻域(ϵ,MinPts)(\\epsilon,MinPts)(ϵ,MinPts)来描述样本集的紧密程度。其中ϵ\\epsilonϵ描述了某一样本的邻域距离阈值，MinPtsMinPtsMinPts描述了某一... 查看详情

    第二节2：optics算法python实现和效果展示(代码片段)

    文章目录三：Python实现四：效果展示（1）人造数据集（2）Square数据集（3）Arrevation（4）Gassian（5）Jain数据集（6）Lineblobs（7） 查看详情

    机器学习---聚类算法(代码片段)

    ...数据集3、使用模型进行分类头文件汇总亲和力传播聚合聚类BIRCH聚类DBSCAN【本人的毕业设计系统中有用到】K-均值高斯混合模型【写在最后】【写在前面】sklearn和scikit-learn：scikit-learn是下载下来的工具，sklearn是在python调... 查看详情

    网络层-第二节：路由算法与路由协议概述

    文章目录一：静态路由与动态路由（1）静态路由算法（非自适应路由算法）（2）动态路由算法（自适应路由算法）二：距离-向量路由算法三：链路状态路由算法四：层次路由一࿱... 查看详情