等大小谱聚类

聚类是一种将具有相似特征的数据点进行分组的方法。它广泛应用于探索性数据分析,并已被证明在模式识别、市场和客户细分、推荐系统、数据压缩以及生物数据分析等许多应用中都发挥着重要作用。

尽管聚类算法种类繁多,但没有一种能够生成点数均衡的聚类。这种大小均衡的聚类在某些领域非常重要,例如在“最后一英里”配送领域,大量订单可以聚合成大小均衡的组,从而优化配送路线并最大限度地提高车辆利用率。

考虑到需要实现等大小的聚类,我和几位同事扩展了所谓的谱聚类,以生成点数均衡的聚类。这种新算法基于数据点的地理信息构建具有相似点数的聚类。

完整代码可在此GitHub 仓库中找到。它旨在为数据科学社区做出贡献。如果您需要在地图上创建相等的点簇,不妨尝试一下!

等大小谱聚类:算法

等大小聚类由三个步骤组成:聚类初始化、计算每个聚类的邻居以及平衡每个聚类中的点。让我们详细回顾一下每个步骤。

聚类初始化

第一步,我们使用Scikit-learn 的谱聚类算法实现来创建聚类。谱聚类在聚合空间数据方面非常强大,因为它可以根据连接节点的边来识别图中节点的社群。谱聚类算法在对遵循圆对称性的点进行聚类时尤其有用。如果您想了解更多关于此方法的信息,可以阅读 William Fleshman 撰写的这篇精彩文章:

谱聚类

基础与应用

towardsdatascience.com

进行聚类初始化需要两个超参数:nclusters表示 所需聚类的数量;nneighbors表示每个数据点的邻居数量。谱聚类使用最后一个参数来构建亲和度矩阵。 的良好值nneighbors 介于数据点的 7% 到 15% 之间。

步骤1:利用谱聚类算法创建聚类。这些聚类中的点数并不相等。

计算每个聚类的邻居

创建聚类后,算法的第二步是计算每个聚类的邻居。这个计算是如何进行的呢?通过估计每个数据点最近邻居的聚类标签的众数。例如,如果点x属于聚类A,而其大多数最近邻居属于聚类B,则意味着聚类B是聚类A的邻居。

每个簇的邻居的计算极其重要,因为簇的平衡是通过在相邻簇之间交换点来实现的。

步骤2:左图:估计每个聚类的邻居。在此示例中,我们可以看到聚类 A 和 B 是聚类 C 的邻居。右图:通过在相邻聚类之间交换点来实现聚类的平衡。

平衡每个聚类上的点

算法的最后一步是平衡每个聚类中的点。如上所述,我们通过在相邻聚类之间交换点来实现这一点。较大的聚类会将点转移到较小的相邻聚类。在平衡过程中,我们的目标是使聚类大小大致等于N /ncluster,其中N是数据点的总数。

为了平衡簇的大小,我们定义了超参数equity_fractionequity_fraction是一个定义在区间 (0,1] 内的数字,它限制了生成的簇必须达到的相等程度。如果equity_fraction为零,则簇将保持相同的初始大小。如果equity_fraction为一,则生成的簇的大小大致等于N /ncluster

步骤 3:最终的聚类规模取决于 equity_fraction。左图:如果 equity_fraction 为 0,聚类将保持其初始规模。右图:如果 equity_fraction 为 1,聚类的点数大致相同。

让我们用一个小括号来定义一个叫做簇离散度(cluster diffraction)的量。簇离散度定义为簇内点距离的标准差。你可以把它看作是簇内距离的稍微修改版本。

equity_fraction会影响初始聚类分散度,因为点的交换会增加聚类内点之间的距离。在这种情况下,我建议您使用优化算法来找到最小化聚类分散度的最佳聚类超参数。在下一节中,我将讨论如何从 Python 代码中去除聚类分散度。

其他功能

需要记住的是,等大小谱聚类可用于创建空间点的聚合。存储库附带绘图功能,可在您拥有数据点坐标的情况下使用。在下一节中,我们将看到此功能的实际应用。

用例:阿姆斯特丹的餐馆集群

假设您是荷兰一家农场的主人,您想将新鲜优质的食材配送到阿姆斯特丹的众多餐厅。您有6辆容量相同的车辆,这意味着它们能够配送到大致相同数量的餐厅。

为了充分利用车辆的容量,您可以使用等大小聚类对餐厅进行分组,以便每辆车不会从一家餐厅行驶到另一家餐厅太多。

我们先来看看餐厅的位置:

restaurants_in_amsterdam.csv文件包含阿姆斯特丹中央火车站周围 8 公里范围内餐厅位置的列表。您可以在GitHub 仓库的datasets文件夹中找到此文件。

根据数据框中列出的位置coords,可以估算出一个包含每对点之间行程距离的矩阵。该矩阵的形状为 (n_samples, n_samples),并且必须是对称的。该矩阵是等大小聚类的输入。

现在我们可以运行等大小谱聚类了。这就像调用类一样简单SpectralEqualSizeClustering

在此示例中,我们创建了 6 个聚类。我们选择邻居数量nneighbors为输入数据集中点数的 10%。由于我们希望聚类尽可能均等,因此我们将 设置 equity_fraction为 1。

您可以看到如何通过调用该方法获取每个数据点的聚类标签fit重要提示:用于预测原始数据中不存在的点的聚类标签的函数尚未实现。如果您觉得此代码对您的工作有用,我鼓励您开发此功能!

可以将上面获得的聚类标签添加到数据框中,coords以便在地图上绘制生成的聚类:

通过运行上面的代码,我们得到一个包含所有聚类的交互式图,如图所示:

使用等大小谱聚类代码创建的聚类。

在该图中,您可以选择每个集群以分别进行可视化:

 

在上述用例中,超参数优化并非必需。然而,正如我之前提到的,如果需要,可以使用优化方法。在这种情况下,您可以将属性clustering.total_cluster_dispersion(即所有聚类离散度的总和)用作优化指标。通过最小化该量, 生成的聚类将更加紧凑。

带回家的信息

在这篇博客中,我介绍了一种谱聚类代码的修改,它可以生成点数均衡的聚类。该算法可以用来生成空间点的均等聚合,并且可能有助于改进“最后一英里”配送领域的某些流程。

等大小谱聚类的重要考虑因素如下:

  • 输入数据必须是与数据点坐标相关的对称距离矩阵。
  • 聚类代码的超参数包括所需聚类的数量 ( nclusters)、每个数据点的邻居数量 ( nneighbors) 以及决定聚类大小均匀程度的分数 ( equity_fraction)。您可以使用任何优化算法来找到最小化总体聚类离散度 ( ) 的最佳参数total_cluster_dispersion
  • 等大小聚类也可用于非空间数据,但尚未针对此目的进行测试。如果您想尝试一下,请定义一个度量来创建代码所需的对称距离矩阵作为输入。请务必先对变量进行归一化或标准化。
  • 该代码还没有prediction方法,但如果您发现该代码有用,欢迎您做出贡献。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/88282.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/88282.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

〔从零搭建〕数据湖平台部署指南

🔥🔥 AllData大数据产品是可定义数据中台,以数据平台为底座,以数据中台为桥梁,以机器学习平台为中层框架,以大模型应用为上游产品,提供全链路数字化解决方案。 ✨杭州奥零数据科技官网&#xff…

Java 导出pdf 写出demo 1、需要设置自定义页眉和文字 2、可以插入表格 3、可以插入图片

以下是一个使用 iText 7 库实现 PDF 导出的 Java 示例&#xff0c;包含自定义页眉、文字、表格和图片功能&#xff1a; 添加 Maven 依赖 <dependencies><!-- iText 7 Core --><dependency><groupId>com.itextpdf</groupId><artifactId>ite…

Ntfs!LfsReadRestart函数分析得到Ntfs!LFS_RESTART_PAGE_HEADER

第一部分&#xff1a;0: kd> p Ntfs!LfsPinOrMapData0x8c: f71797f6 ff15a40016f7 call dword ptr [Ntfs!_imp__CcPinRead (f71600a4)] 0: kd> t nt!CcPinRead: 80bf9a5a 6a2c push 2Ch 0: kd> kc# 00 nt!CcPinRead 01 Ntfs!LfsPinOrMapData 02 N…

skywalking-agent-docker镜像

FROM centos:7.9.2009 USER root# 定义 Arthas 目录环境变量 ENV ARTHAS_HOME/opt/arthas# 更改 YUM 源并清理缓存 RUN mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo_bak && \rm -rf /etc/yum.repos.d/* && \curl -o /etc/yum.rep…

数据库开发运维的集成:弥合开发与运维之间的鸿沟

在传统的软件开发工作流程中&#xff0c;数据库变更往往是事后才考虑的问题。应用程序代码遵循定义明确的开发运维实践&#xff0c;包括版本控制、自动测试和持续部署&#xff0c;而数据库变更则经常是由数据库管理员手动执行的高风险操作。这种脱节造成了瓶颈&#xff0c;带来…

PiscTrace应用:从 YOLO-Pose 到深蹲与引体向上计数:实时健身动作分析与实现

随着健身行业的发展&#xff0c;越来越多的智能应用涌现&#xff0c;用于帮助健身者更好地记录和分析运动情况。特别是在体能训练中&#xff0c;俯卧撑和引体向上是两个非常常见的动作&#xff0c;它们通常用来锻炼上半身力量和耐力。为了使训练更加科学和高效&#xff0c;实时…

【unity】webCanvas.enabled = false;和webCanvas.gameObject.SetActive(false);的优缺点比较

在 Unity 中&#xff0c;webCanvas.gameObject.SetActive(false) 和 webCanvas.enabled false 是两种不同的隐藏 UI 的方式&#xff0c;它们的核心区别在于作用范围和对组件状态的影响。理解这些差异能帮助你避免初始化失败、性能问题和逻辑错误。 1核心区别 gameObject.SetAc…

深入探索 pnpm:高效磁盘利用与灵活的包管理解决方案

引言 在现代 JavaScript 开发中&#xff0c;依赖管理效率直接影响开发体验。传统工具如 npm 和 yarn 在大型项目中常面临磁盘冗余和性能瓶颈。pnpm&#xff08;Performant npm&#xff09;通过创新的硬链接和符号链接机制&#xff0c;解决了这些痛点。本文将深入解析 pnpm 的核…

Hive MetaStore的实现和优化

在大数据领域&#xff0c;数据管理与存储至关重要&#xff0c;Hive MetaStore&#xff08;HMS&#xff09;作为 Hive 数据仓库的核心组件&#xff0c;承担着元数据管理的关键职责。随着数据规模不断膨胀&#xff0c;其性能与稳定性面临挑战。本文将深入剖析 HMS 的实现机制&…

一文读懂动态规划:多种经典问题和思路

一、动态规划算法的思想与核心概念框架 1. 动态规划的基本思想 动态规划&#xff08;Dynamic Programming, DP&#xff09;是一种通过将复杂问题分解为重叠子问题&#xff0c;并利用子问题的解来高效解决原问题的方法。其核心思想是避免重复计算&#xff0c;通过存储中间结果&a…

阿幸课堂随机点名

代码功能 这个是一个HTML网页端&#xff0c;简单来说就是可以双击之后运行进行点名。 当然&#xff0c;不局限于课堂点名 代码功能 Excel 导入增强&#xff1a; 增加了列选择器&#xff0c;可以指定从哪一列读取学生姓名 增加了起始行选择器&#xff0c;可以跳过标题行或其…

LeetCode 560: 和为K的子数组

题目描述给定一个整数数组 nums 和一个整数 k&#xff0c;请统计并返回该数组中和为 k 的连续子数组的个数。示例 1&#xff1a;输入&#xff1a;nums [1,1,1], k 2 输出&#xff1a;2示例 2&#xff1a;输入&#xff1a;nums [1,2,3], k 3 输出&#xff1a;2提示&#xff…

微软官方C++构建工具:历史演变、核心组件与现代实践指南

引言&#xff1a;C构建工具的战略意义 在Windows生态系统中&#xff0c;​​微软C构建工具​​&#xff08;Microsoft C Build Tools&#xff09;构成了数百万开发者和应用程序的技术基石。从早期的MS-DOS命令行工具到如今支持​​跨平台开发​​的现代化工具链&#xff0c;微…

探索Cocos_CoilTheRope:一款创新的游戏引擎扩展项目

探索Cocos_CoilTheRope&#xff1a;一款创新的游戏引擎扩展项目 去发现同类优质开源项目:https://gitcode.com/ 是一个基于Cocos2d-x游戏引擎的扩展库&#xff0c;旨在为开发者提供一种简便的方法来实现绳子缠绕和物理交互效果。该项目由DreamLXW开发并维护&#xff0c;为游戏…

爬虫-正则表达式

在线正则表达式测试OSCHINA.NET在线工具,ostools为开发设计人员提供在线工具&#xff0c;提供jsbin在线 CSS、JS 调试&#xff0c;在线 Java API文档,在线 PHP API文档,在线 Node.js API文档,Less CSS编译器&#xff0c;MarkDown编译器等其他在线工具https://tool.oschina.net/…

【BTC】数据结构

目录 那比特币区块链的组织形式到底是以链表的形式&#xff0c;还是树的形式呢&#xff1f; 区块头和区块体与默克尔树的关系 默克尔证明详解 区块链和链表最大的区别就是区块链用哈希指针代替了普通指针。 链表的指针就是指向一个结构体在内存中的地址&#xff0c;而哈希指…

飞算 JavaAI:让 Java 开发效率飙升的智能助手,日常开发全场景应用指南

飞算 JavaAI&#xff1a;让 Java 开发效率飙升的智能助手 &#xff0c;日常开发全场景应用指南 在 Java 开发的日常工作中&#xff0c;开发者常常面临各类重复性劳动与逻辑复杂度挑战。飞算 JavaAI 作为专注于 Java 领域的智能开发助手&#xff0c;能够覆盖从代码生成到项目维护…

8.2 文档预处理模块(二)

一、从0开始&#xff1a;简易RAG实现 在构建更复杂的 RAG 架构之前&#xff0c;我们先从最基础的版本入手。整个流程可以分为以下几个关键步骤&#xff1a; 1.数据导入&#xff1a;加载并预处理原始文本数据&#xff0c;为后续处理做好准备。 2.文本分块&#xff1a;将长文本…

【系统与工具】Linux——Linux简介、安装、简单使用

计算机概论与Linux简介 计算机概论Linux介绍与版本 Linux的规划与安装 Linux与硬件平台密切相关规划硬件与Linux安装 主机规划与磁盘分区安装CentOS、多重引导 简单使用 帮助手册文本编辑器关机 0. Linux介绍与版本 操作系统&#xff08;Linux&#xff09;&#xff1a;高效…

从视频数据到数字孪生:如何构建虚拟与现实的桥梁?

概述 视频数据与三维场景融合渲染技术通过将动态视频与静态三维模型结合&#xff0c;利用GPU加速、WebGL渲染、数字孪生等技术&#xff0c;实现虚拟与现实的交互式融合。该技术广泛应用于智慧城市、工业监控、虚拟现实、游戏特效等领域&#xff0c;能够提升场景的直观性和用户沉…