数学建模教学:常用算法 --- BIRCH-层次聚类算法

发布时间:2023-03-26 09:30

0 前言

本人计算机研二,专业带队数学建模,长期更新建模教学,有需要的同学欢迎讨论~
本篇文章,本系列学长讲解一部分数学建模常用算法,会陆续更新每个算法的详细实现和使用教程

1 BIRCH算法概述

BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies)在设计之初就考虑到了大规模数据集上聚类的精确性(充分利用有限内存保证好的聚类效果)和最小化I/O代价(减少数据库的读写,保证效率)之间的均衡。BIRCH能够识别出数据集中数据分布的不均衡性,将分布在稠密区域中的点聚类,将分布在稀疏区域中的点视作异常点而移除。此外,BIRCH是一种增量聚类方法,针对每一个点的聚类决策都是基于当前已经处理过的数据点,而不是全局的数据点。

2 一些重要概念

\"数学建模教学:常用算法

\"数学建模教学:常用算法
\"数学建模教学:常用算法

3 BIRCH算法流程

整个算法的实现分为四个阶段:

  • (1)扫描所有数据,建立初始化的CF树,把稠密数据分成簇,稀疏数据作为孤立点对待

  • (2)这个阶段是可选的,阶段3的全局或半全局聚类算法有着输入范围的要求,以达到速度与质量的要求,所以此阶段在阶段1的基础上,建立一个更小的CF树

  • (3)补救由于输入顺序和页面大小带来的分裂,使用全局/半全局算法对全部叶节点进行聚类

  • (4)这个阶段也是可选的,把阶段3的中心点作为种子,将数据点重新分配到最近的种子上,保证重复数据分到同一个簇中,同时添加簇标签

4 算法实现

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_blobs
from sklearn.cluster import Birch
from sklearn import metrics
 
##############################################
#                     生成数据
##############################################
# X为样本特征,Y为样本簇类别
# 共1000个样本,每个样本2个特征
# 共4个簇,簇中心在[-1,-1], [0,0],[1,1], [2,2]
# 每个类别的方差分别为0.4, 0.3, 0.4, 0.3
X, y = make_blobs(n_samples=1000, n_features=2, 
	centers = [[-1,-1], [0,0], [1,1], [2,2]], 
	cluster_std = [0.4, 0.3, 0.4, 0.3], random_state=9)
 
##############################################
#                     开始聚类
##############################################
# 尝试多个threshold取值,和多个branching_factor取值
param_grid = {\'threshold\': [0.1, 0.3, 0.5],
\'branching_factor\': [10, 20, 50]}  
CH_all = []
X_all = []
y_all = []
paras_all = []
# 网格搜索方法
print(\"Threshold\\tBranching factor\\tMetrics\")
for threshold in param_grid[\'threshold\']:
    for branching_factor in param_grid[\'branching_factor\']:
        clf = Birch(n_clusters = 4, 
        	threshold = threshold, branching_factor = branching_factor)
        clf.fit(X)
        X_all.append(X)
        y_pred = clf.predict(X)
        y_all.append(y_pred)
        CH = metrics.calinski_harabaz_score(X, y_pred)
        CH_all.append(CH)
        paras_all.append([threshold, branching_factor])
        print(threshold, \"\\t\", branching_factor, \"\\t\", \'%.4f\'%CH)
 
##############################################
#                     择优
##############################################
CH_max = max(CH_all)
idx = CH_all.index(CH_max)
X_max = X_all[idx]
y_max = y_all[idx]
 
##############################################
#                     绘图
##############################################
plt.rcParams[\'font.sans-serif\'] = [\'Times New Roman\']
plt.rcParams[\'axes.unicode_minus\'] = False
 
plt.figure()
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1], marker = \'o\', c = y)
plt.title(\'Original Cluster Plot\')
plt.xlabel(\'(1)\')
 
plt.subplot(1, 2, 2)
plt.scatter(X_max[:, 0], X_max[:, 1], marker = \'o\', c = y_max)
plt.title(\'Result (Threshold = \' + str(paras_all[idx][0])
 + \', BF = \' + str(paras_all[idx][1]) + \')\')
plt.xlabel(\'(2)\')
 
 
plt.show()

最后

数学建模精选资料共享,研究生学长数模指导,建模比赛思路分享,关注我不迷路!

建模指导,比赛协助,有问必答,欢迎打扰

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号