(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210794065.2 (22)申请日 2022.07.05 (71)申请人 合肥黎曼信息科技有限公司 地址 230031 安徽省合肥市高新区创新大 道2800号创新产业园二期J1栋A座 1027室 (72)发明人 宋艳枝　杨路　 (74)专利代理 机构 合肥汇融专利代理有限公司 34141 专利代理师 王秀芳 (51)Int.Cl. G06K 9/62(2022.01) G06Q 10/04(2012.01) G06Q 10/08(2012.01) (54)发明名称 一种指定 类别容量的聚类方法及其系统 (57)摘要 本发明涉及人工智能与算法开 发技术领域， 解决了传统的聚类方法无法识别空间中障碍区 域的技术问题， 涉及一种指定类别容量的聚类方 法， 包括以下过程： 根据待聚类离散点集的空间 坐标信息建立连通图； 确定连通图中任意两个离 散点集之间的连通关系并计算 成本； 根据两点选 择算法选取2 ‑类别指定容量聚类中与虚拟源点 连接的两个节 点的初始点； 还涉及一种应用于指 定类别容量的聚类方法的系统， 包括： 连通图建 立模块用于根据待聚类离散点集的空间坐标信 息建立连通图。 本发明将指定容量的聚类问题转 化为网络流模 型并求最优解， 模 型求解的方案能 够完美处理指定类别容量的聚类问题， 并有效避 免了类别间空间交错、 包 含等问题。 权利要求书2页 说明书9页 附图7页 CN 115018008 A 2022.09.06 CN 115018008 A 1.一种指定类别容 量的聚类方法， 其特 征在于， 包括以下 过程： 根据待聚类离 散点集的空间坐标信息建立连通图； 确定连通图中任意两个离 散点集之间的连通关系并计算成本； 根据两点选择算法选取2 ‑类别指定容 量聚类中与虚拟源点连接的两个节点的初始点； 根据连通图和初始点建立2 ‑类别指定容 量聚类的网络流模型； 由2‑类别指定容 量聚类的网络流模型迭代求 解k‑类别指定容 量聚类问题。 2.根据权利要求1所述的聚类方法， 其特征在于： 所述离散点集为具有容量属性的离散 点集合， 离散点集合由若干个包 含坐标信息和其对应的容 量大小的离 散点构成。 3.根据权利要求1所述的聚类方法， 其特征在于： 所述在连通图中引入用于保证离散点 集合流量守恒的虚拟源点。 4.根据权利要求1所述的聚类方法， 其特征在于： 所述连通图包括节点集、 边集、 边集上 的成本； 所述节点 集由采掘场或排土场的块体质心的坐标点构成； 所述边集由以节点 为端点的线段中存在邻接关系构成； 所述边集上的成本由两端点间的欧式距离计算给 出。 5.根据权利要求1所述的聚类方法， 其特征在于： 所述根据待聚类离散点集的空间坐标 信息建立连通图这一步骤之后还包括， 逐一访问连通图中的各离散点间的连通分支， 单独 构建离散点与其 他连通分支间的边。 6.根据权利要求1所述的聚类方法， 其特征在于： 所述确定连通图中任意两个离散点集 之间的连通关系并计算成本， 其中包括： 确立离散点集合中任意两个离 散点之间连接所构成的边； 计算离散点集合中任意两个离 散点之间所构成的边的成本函数。 7.根据权利要求1所述的聚类方法， 其特征在于： 所述两点选择算法为： 基于离散点的 欧氏距离 选取距离最大的两点。 8.根据权利要求1所述的聚类方法， 其特征在于： 所述两点选择算法为： 基于连通图上 的距离选取最大的两点。 9.一种应用于上述权利要求1 ‑8任一项的指定类别容量的聚类方法的系统， 其特征在 于， 包括： 连通图建立模块(100)， 所述连通图建立模块(100)用于根据待聚类离散点集的空间坐 标信息建立连通图； 连通关系确定模块(200)， 所述连通关系确定模块(200)用于确定连通图中任意两个离 散点集之间的连通关系并计算成本； 初始点选取模块(300)， 所述初始点选取模块(300)用于根据两点选择算法选取2 ‑类别 指定容量聚类中与虚拟源点连接的两个节点的初始点； 网络流模型建立模块(400)， 所述网络流模型建立模块(400)用于根据连通图和初始点 建立2‑类别指定容 量聚类的网络流模型； 迭代求解模块(500)， 所述迭代求解模块(500)用于由2 ‑类别指定容量聚类的网络流模 型迭代求 解k‑类别指定容 量聚类问题。 10.根据权利要求9所述的聚类系统， 其特 征在于， 所述聚类系统还 包括：权　利　要　求　书 1/2 页 2 CN 115018008 A 2访问、 构建模块(101)， 所述访问、 构建模块(101)用于逐一访问连通图中的各离散点间 的连通分支， 单独构建离 散点与其 他连通分支间的边。权　利　要　求　书 2/2 页 3 CN 115018008 A 3