Scaling up the DBSCAN Algorithm for Clustering Large Spatial Databases Based on Sampling Technique

Clustering, in data mining, is a useful technique for discovering interesting data distributions and patterns in the underlying data, and has many application fields, such as statistical data analysis, pattern recognition, image processing, and etc. We combine sampling technique with DBSCAN algorithm to cluster large spatial databases, and two sampling based DBSCAN (SDBSCAN) algorithms are developed. One algorithm introduces sampling technique inside DBSCAN, and the other uses sampling procedure outside DBSCAN. Experimental results demonstrate that our algorithms are effective and efficient in clustering large scale spatial databases.

Spatial quality evaluation for drinking water based on GIS and ant colony clustering algorithm

To develop a better approach for spatial evaluation of drinking water quality, an intelligent evaluation method integrating a geographical information system(GIS) and an ant colony clustering algorithm(ACCA) was used. Drinking water samples from 29 wells in Zhenping County, China, were collected and analyzed. 35 parameters on water quality were selected, such as chloride concentration, sulphate concentration, total hardness, nitrate concentration, fluoride concentration, turbidity, pH, chromium concentration, COD, bacterium amount, total coliforms and color. The best spatial interpolation methods for the 35 parameters were found and selected from all types of interpolation methods in GIS environment according to the minimum cross-validation errors. The ACCA was improved through three strategies, namely mixed distance function, average similitude degree and probability conversion functions. Then, the ACCA was carried out to obtain different water quality grades in the GIS environment. In the end, the result from the ACCA was compared with those from the competitive Hopfield neural network(CHNN) to validate the feasibility and effectiveness of the ACCA according to three evaluation indexes, which are stochastic sampling method, pixel amount and convergence speed. It is shown that the spatial water quality grades obtained from the ACCA were more effective, accurate and intelligent than those obtained from the CHNN.

Background dominant colors extraction method based on color image quick fuzzy c-means clustering algorithm

A quick and accurate extraction of dominant colors of background images is the basis of adaptive camouflage design.This paper proposes a Color Image Quick Fuzzy C-Means(CIQFCM)clustering algorithm based on clustering spatial mapping.First,the clustering sample space was mapped from the image pixels to the quantized color space,and several methods were adopted to compress the amount of clustering samples.Then,an improved pedigree clustering algorithm was applied to obtain the initial class centers.Finally,CIQFCM clustering algorithm was used for quick extraction of dominant colors of background image.After theoretical analysis of the effect and efficiency of the CIQFCM algorithm,several experiments were carried out to discuss the selection of proper quantization intervals and to verify the effect and efficiency of the CIQFCM algorithm.The results indicated that the value of quantization intervals should be set to 4,and the proposed algorithm could improve the clustering efficiency while maintaining the clustering effect.In addition,as the image size increased from 128×128 to 1024×1024,the efficiency improvement of CIQFCM algorithm was increased from 6.44 times to 36.42 times,which demonstrated the significant advantage of CIQFCM algorithm in dominant colors extraction of large-size images.

Mining Knowledge from Result Comparison Between Spatial Clustering Themes

This paper introduces some definitions and defines a set of calculating indexes to facilitate the research, and then presents an algorithm to complete the spatial clustering result comparison between different clustering themes. The research shows that some valuable spatial correlation patterns can be further found from the clustering result comparison with multi-themes, based on traditional spatial clustering as the first step. Those patterns can tell us what relations those themes have, and thus will help us have a deeper understanding of the studied spatial entities. An example is also given to demonstrate the principle and process of the method.

Realization of R-tree for GIS on hybrid clustering algorithm

The characteristic of geographic information system(GIS) spatial data operation is that query is much more frequent than insertion and deletion, and a new hybrid spatial clustering method used to build R-tree for GIS spatial data was proposed in this paper. According to the aggregation of clustering method, R-tree was used to construct rules and specialty of spatial data. HCR-tree was the R-tree built with HCR algorithm. To test the efficiency of HCR algorithm, it was applied not only to the data organization of static R-tree but also to the nodes splitting of dynamic R-tree. The results show that R-tree with HCR has some advantages such as higher searching efficiency, less disk accesses and so on.

Genetic-Based Keyword Matching DBSCAN in IoT for Discovering Adjacent Clusters

As location information of numerous Internet of Thing(IoT)devices can be recognized through IoT sensor technology,the need for technology to efficiently analyze spatial data is increasing.One of the famous algorithms for classifying dense data into one cluster is Density-Based Spatial Clustering of Applications with Noise(DBSCAN).Existing DBSCAN research focuses on efficiently finding clusters in numeric data or categorical data.In this paper,we propose the novel problem of discovering a set of adjacent clusters among the cluster results derived for each keyword in the keyword-based DBSCAN algorithm.The existing DBSCAN algorithm has a problem in that it is necessary to calculate the number of all cases in order to find adjacent clusters among clusters derived as a result of the algorithm.To solve this problem,we developed the Genetic algorithm-based Keyword Matching DBSCAN(GKM-DBSCAN)algorithm to which the genetic algorithm was applied to discover the set of adjacent clusters among the cluster results derived for each keyword.In order to improve the performance of GKM-DBSCAN,we improved the general genetic algorithm by performing a genetic operation in groups.We conducted extensive experiments on both real and synthetic datasets to show the effectiveness of GKM-DBSCAN than the brute-force method.The experimental results show that GKM-DBSCAN outperforms the brute-force method by up to 21 times.GKM-DBSCAN with the index number binarization(INB)is 1.8 times faster than GKM-DBSCAN with the cluster number binarization(CNB).

基于混合优化算法的电磁监测裂缝参数识别

压裂实时监测是水力压裂效果评价和工程参数优化的重要保障措施之一。传统电磁监测裂缝参数识别方法的准确性和精度难以保证,影响了监测效果。为了提高裂缝参数识别能力,提出了一种基于海洋捕食者密度聚类混合优化算法的电磁监测裂缝参数识别方法。利用海洋捕食者算法(MPA)进行多次寻优,以每次寻优结果作为初始数据集,然后,利用密度聚类算法(DBSCAN)进行聚类,构建中间样本数据集,最后,抽取该样本数据中值作为最终输出结果。采用Rastrigin函数进行测试,分析混合优化算法寻优能力。测试结果表明,相对粒子群优化算法(PSO),MPA算法单次寻优效果较佳。但两种算法寻优结果均具有较强随机性,其中,PSO和MPA算法50次寻优精度分别为10^(-7)~10^(2)和10^(-10)~10^(-2),而改进的混合优化算法寻优效果更稳定,寻优精度达10^(-7)。构建缝长、方位压裂模型并进行了数值模拟实验,结果表明,在噪声低于15%时,缝长和方位识别平均绝对误差分别小于1 m和1°。利用改进的算法对四川盆地某井页岩气压裂电磁监测实测数据进行分析,确定了裂缝改造的长度(缝长)与方位。实例分析结果验证了改进算法的可行性和有效性。

城市休闲产业聚类模式APM算法模型开发与校验

城市休闲相关产业的高质量发展对当前我国城市消费升级以及人居环境质量提升具有重要现实意义。但是,现有研究未能精准地捕捉海量广域分布的城市休闲产业的基本空间分布规律与结构,而已有的空间聚类算法较多适用于城市用地分析,未能很好地适用于离散分布的城市休闲产业研究。为此,文章基于空间兴趣点数据,开发距离通达值及空间集群中心点等算法,构建城市休闲旅游产业聚类模式空间算法模型(APM)。在以广州为例的研究中,APM模型捕捉出3170个以500 m步行生活圈为范围的城市休闲产业集群,校验了APM模型的科学性与应用价值。整体上,APM算法可以较好地捕捉城市休闲业态集群的空间结构,清晰识别城市休闲产业空间冷、热点分布的基本结构,由其捕捉行程的聚类边界与实际道路和建筑走向、水系边界、区域范围等重合度高,聚类集群符合实际情况,具备可信度与有效性。该研究是休闲产业集聚机制研究的一次方法创新,在算法精度、实际应用、可视化效率上均做出了创新性推进。与Fishnet方法相比,可以更科学精准地识别城市内部多个休闲消费商圈的边界,实现了高效率的城市休闲产业集群捕捉;与同位模型相比,可以呈现多类别的城市休闲业态结构,突破了现有研究只能捕捉两类业态组团的局限。

基于改进YOLOv5s算法的禁捕期长江渔船识别及应用研究

长江实行十年禁渔是长江生态环境修复的关键环节,针对禁渔期间长江非法捕捞渔船目标小、背景复杂、流动大等问题,提出了一种基于改进YOLOv5s的目标检测算法。该算法优化多尺度自适应锚框模块,采用改进的K-means++聚类算法,重新匹配适合长江船舶尺寸的锚框;使用轻量高效的坐标注意力(coordinate attention,CA)机制,提升模型关注目标通道信息特征的能力;采用SPPCSPPC(spatial pyramid pooling and context-aware spatial pyramid pooling combination)对特征图进行池化,提高小目标检测能力;通过构建长江船舶数据集训练得到最优权值模型。结果显示,改进后的模型在准确率、召回率、mAP0.5、mAP0.5∶0.9和原模型相比分别提高了1.5%、3.0%、2.4%、7.7%,且训练过程损失收敛更快,收敛值更低,能够准确快速识别出长江上的渔船目标。研究结果可为长江十年禁渔提供技术支持。

结合载客热点和POI的出租车停车位划定方法

针对出租车随意停靠造成城市交通拥堵甚至交通事故的问题,利用成都实际区域的出租车GPS(Global Position System)数据和爬取的POI(Point of Interest)数据,使用DBSCAN(Density-Based Spatial Clustering of Application with Noise)聚类算法对上下客点进行聚类,得到出租车的载客热点,根据POI的类型划定载客热点区域的类型,对出租车不同时间的出行需求进行分析,进而划分出出租车的固定停车区域。研究结果表明,出租车固定停车区域的设定与出行者的出行需求有关,即将固定停车区域设置在出行者出行需求多的区域,可以满足出行者的不同出行需求。结合出租车载客热点和爬取POI数据划定固定停车区域的方法具有较高的实用性,可为城市交通安全方面提供理论和现实意义。

中空铜纳米线的拉伸断裂分布与初始滑移分布的关系

构建了系列球形中空结构的纳米线(NW),采用分子动力学(MD)对每个模型300个不同初始态的样本开展拉伸形变模拟。并利用基于密度的噪声应用空间聚类(density-based spatial clustering of applications with noise,DBSCAN)机器学习算法,获得了初始滑移面的位置。基于大数据统计,分析了初始滑移位置分布以及断裂位置分布两者之间的相关性。研究结果表明:当内部中空半径较小时,断裂位置分布形成于塑性形变阶段,初始滑移分布与断裂位置分布之间无显著的相关性;但是对于脆性特征明显的大中空半径的NW,高能内表面诱导产生的滑移面迅速积累,产生颈缩并导致最终的断裂。因此当内部中空结构达到一定尺寸时初始滑移位置的分布与最终断裂位置的分布之间有明确的因果关系。

改进YOLOv5s的无人机视角下小目标检测算法

无人机视角的小目标图像具有目标分布密集、类别不均衡以及特征不明显的特点,导致目标检测任务中出现漏检、误检的问题。针对这些问题,提出一种改进YOLOv5s小目标检测方法,以达到提高目标检测准确率与精确度的目的。重新聚类锚框,更精确地锁定检测区域。更改骨干网络结构,在空间金字塔池化层增加卷积,保证充分获取检测目标特征。同时,将网络结构中的C3模块替换成融合通道注意力机制的轻量级SEC2f模块,以提升网络对于小目标检测的局部特征捕获能力。融合解耦检测头,结合自适应锚框计算,有效提取目标区域的特征。在相同参数、相同环境条件下,在DOTA数据集上和VisDrone数据集上检测精度分别提升6.1%、5.2%,表明改进方法在小目标检测任务上的有效性;在公开数据集voc2007+2012上做通用性对比实验,结果表明改进算法具有通用性。

东北暖季冷涡降水日变化的聚类分析

使用2017~2022年5~9月逐小时三源融合实况格点降水(CMPAS)资料,采用K-均值聚类算法对东北暖季冷涡降水日变化分类,分析其特征及空间分布,结果显示:1)东北暖季冷涡降水多年平均降水量空间分布从西北到东南增加,降水频次的空间分布与其相似,降水强度大值区集中在辽东半岛附近。2)东北地区冷涡背景下降水量、降水频次和降水强度暖季平均日变化均呈双峰型,降水量的下午主峰值主要源于降水频次,而夜间次峰值与降水频次和降水强度均关系密切。3)聚类后冷涡降水量、降水频次的日变化表现为单峰型和双峰型特征,且单峰型格点占比较大,降水强度的日变化表现为单峰型。依据峰值出现时间及日变化形态间差异,降水量、频次与强度均可划分为4类不同的日变化类型。4)各类日变化空间占比统计结果显示,冷涡降水量、降水频次日变化存在下午峰值的格点均占比最大,夜间峰值次之,两者聚类后区域特征明显,与地形关系密切且分布相对规整;冷涡降水强度日变化下午单峰型格点占比最大,聚类后空间分布较为零散。

嘉陵江流域骤发干旱时空演变特征分析

为探究嘉陵江流域骤发干旱可识别特性与时空演变特征,基于标准化蒸发胁迫比研究了1980—2020年嘉陵江流域骤发干旱的时空分布特征,通过密度聚类算法提取骤发干旱斑块分析了斑块质心的轨迹变化,并探讨了骤发干旱暴发初期气象要素的异常情况。结果表明:流域西北部骤发干旱强度更高且发展速度更快,流域南部骤发干旱持续时间更长;流域骤发干旱事件主要发生在4—11月,且骤发干旱事件的质心主要沿东北和西北方向迁移;嘉陵江流域的骤发干旱主要由高温和降水共同主导。

基于改进Prim算法的路径规划研究

文中提出一种基于聚类分析改进Prim(普里姆)最小生成树的路径规划算法,采用二分法将站网中的站点先聚类,分成多个微小的站点聚类中心,再以各聚类中心进行Prim最小生成树的路径规划,量化站网空间分布特征,通过聚类增强最小生成树,达到路径优化的目的。实践结果证明,改进的Prim算法适用于大型稠密的站网,在稠密的连通图中,只要调整指数进而控制聚类中心的数量,就能简化站网布局,降低算法的空间复杂度,达到更好的实际应用。

基于机器学习空间聚类的出租车停靠站点布局规划

针对出租车随意停靠给城市交通带来的负面影响,为规范出租车营运秩序、改善出租车营运环境和居民乘车条件,提出一种将出租车出行空间信息与机器学习算法相结合的出租车停靠站点布局规划方法。首先利用出租车GPS轨迹数据提取出租车出行起点,然后采用HDBSCAN聚类算法对起点进行空间密度聚类,形成聚类簇后以其中心点作为出租车停靠站点布局的备选点。最后,为验证所提方法的可行性和有效性,选取重庆市中心城区一土地利用类型丰富、人口密度高的典型区域进行案例分析。结果显示,107个备选点主要分布于商业中心区和居住集中区,与出租车出行高需求区域的空间分布基本吻合;布局的出租车停靠站点在300 m范围内的覆盖率达到76.0%,未覆盖区域主要为城市绿地和水体。研究表明,机器学习算法可实现出租车停靠站点的高效布局规划,但在规划和实施阶段,停靠站点的设置还应结合邻近区域的建成环境特点综合考虑。

基于K-modes聚类算法的山东省传统村落空间风貌类型及区划研究

传统村落的类型解析及空间区划是开展传统村落整体性保护和区域性发展的基础前提,本文在对山东省传统村落调查的基础上,基于空间基因理论视角,从地景、聚落、建筑、文化4个层次构建起13个指标的传统村落空间风貌分类指标体系,并采用K-modes聚类算法对山东省177个传统村落进行聚类分析,得到八大空间风貌类型,进一步结合区域文化、地理特点及行政区划,划分出山东省5个传统村落风貌区,从宏观视角分析了山东省传统村落空间风貌特征及其形成与发展的内在逻辑和地理分布规律,为更加整体全面地认识山东省传统村落特点、开展区域性传统村落集中连片保护利用等工作提供科学参考。

基于可信工人路径规划的声望检验算法

针对工人自选择任务模式下无法确定路径规划算法工人可信度的问题,提出了基于可信工人路径规划的声望检验算法。首先,根据欧氏距离与区域限制对任务进行k均值聚类,缩小可信工人候选任务集,从而降低路径规划算法的时间复杂度;其次,提出了利用权值k对可信工人路径优化的算法,该算法综合考虑可检验工人数量、距离成本和截止时间计算任务权值,基于任务权值最大化寻找最佳插入位置来建立和更新可信工人的执行路径;最后,通过采用抽查检验的方式对可信工人与普通工人提交数据对比的结果来建立工人声望模型,该模型使用了可信性、不可信性和不确定性三个参数的期望值来描述工人的可靠性。在模拟数据集和gMission真实数据集上对声望检验算法进行实验,结果表明提出的声望校验算法数据采集质量提升13%,路径规划算法在保证抽查质量的基础上,可信工人的旅行成本降低11%。

Three-dimensional(3D)parametric measurements of individual gravels in the Gobi region using point cloud technique

Gobi spans a large area of China,surpassing the combined expanse of mobile dunes and semi-fixed dunes.Its presence significantly influences the movement of sand and dust.However,the complex origins and diverse materials constituting the Gobi result in notable differences in saltation processes across various Gobi surfaces.It is challenging to describe these processes according to a uniform morphology.Therefore,it becomes imperative to articulate surface characteristics through parameters such as the three-dimensional(3D)size and shape of gravel.Collecting morphology information for Gobi gravels is essential for studying its genesis and sand saltation.To enhance the efficiency and information yield of gravel parameter measurements,this study conducted field experiments in the Gobi region across Dunhuang City,Guazhou County,and Yumen City(administrated by Jiuquan City),Gansu Province,China in March 2023.A research framework and methodology for measuring 3D parameters of gravel using point cloud were developed,alongside improved calculation formulas for 3D parameters including gravel grain size,volume,flatness,roundness,sphericity,and equivalent grain size.Leveraging multi-view geometry technology for 3D reconstruction allowed for establishing an optimal data acquisition scheme characterized by high point cloud reconstruction efficiency and clear quality.Additionally,the proposed methodology incorporated point cloud clustering,segmentation,and filtering techniques to isolate individual gravel point clouds.Advanced point cloud algorithms,including the Oriented Bounding Box(OBB),point cloud slicing method,and point cloud triangulation,were then deployed to calculate the 3D parameters of individual gravels.These systematic processes allow precise and detailed characterization of individual gravels.For gravel grain size and volume,the correlation coefficients between point cloud and manual measurements all exceeded 0.9000,confirming the feasibility of the proposed methodology for measuring 3D parameters of individual gravels.The proposed workflow yields accurate calculations of relevant parameters for Gobi gravels,providing essential data support for subsequent studies on Gobi environments.

基于航迹匹配与SSA-GRU的多目标轨迹预测

针对空战环境下多目标轨迹预测问题,提出了基于航迹匹配与麻雀搜索算法(SSA:Sparrow Search Algorithm)-门控循环单元(GRU:Gate Recurrent Unit)的多目标轨迹预测方法。首先基于归属未知的多目标航迹点时序数据,采用基于密度的带噪声空间聚类算法(DBSCAN:Density-Based Spatial Clustering of Applications with Noise)实现在目标个数未知的情况下多目标-航迹匹配;在此基础上,构建目标轨迹预测GRU模型,并采用SSA对GRU网络参数进行优化,确定最优神经元个数,提升轨迹预测模型性能。仿真结果表明,基于航迹匹配与SSA-GRU的多目标轨迹预测方法能够有效识别匹配多个目标航迹,并实现各目标轨迹预测。