检索结果-内蒙古大学图书馆

Density Clustering Algorithm Based on kd-tree and Voting Rules

Computers, Materials & Continua 2024年第5期79卷 3239-3259页

作者： Hui Du Zhiyuan Hu Depeng Lu Jingrui Liu The College of Computer Science and Engineering Northwest Normal UniversityLanzhou730070China

Traditional clustering algorithms often struggle to produce satisfactory results when dealing with datasets withuneven density. Additionally, they incur substantial computational costs when applied to high-dimensional datadue to calculating similarity matrices. To alleviate these issues, we employ the kd-tree to partition the dataset andcompute the K-nearest neighbors (KNN) density for each point, thereby avoiding the computation of similaritymatrices. Moreover, we apply the rules of voting elections, treating each data point as a voter and casting a votefor the point with the highest density among its KNN. By utilizing the vote counts of each point, we develop thestrategy for classifying noise points and potential cluster centers, allowing the algorithm to identify clusters withuneven density and complex shapes. Additionally, we define the concept of “adhesive points” between two clustersto merge adjacent clusters that have similar densities. This process helps us identify the optimal number of clustersautomatically. Experimental results indicate that our algorithm not only improves the efficiency of clustering butalso increases its accuracy.

关键词： Density peaks clustering kd-tree K-nearest neighbors voting rules

来源：评论

学校读者我要写书评

暂无评论

Improved Data Stream Clustering Method: Incorporating kd-tree for Typicality and Eccentricity-Based Approach

引用

Computers, Materials & Continua 2024年第2期78卷 2557-2573页

作者： Dayu Xu Jiaming Lu Xuyao Zhang Hongtao Zhang College of Mathematics and Computer Science Zhejiang A&F UniversityHangzhou311300China College of Economics and Management Zhejiang A&F UniversityHangzhou311300China

Data stream clustering is integral to contemporary big data ***,addressing the ongoing influx of data streams efficiently and accurately remains a primary challenge in current *** paper aims to elevate the efficiency and precision of data stream clustering,leveraging the TEDA(Typicality and Eccentricity Data Analysis)algorithm as a foundation,we introduce improvements by integrating a nearest neighbor search algorithm to enhance both the efficiency and accuracy of the *** original TEDA algorithm,grounded in the concept of“Typicality and Eccentricity Data Analytics”,represents an evolving and recursive method that requires no prior *** the algorithm autonomously creates and merges clusters as new data arrives,its efficiency is significantly hindered by the need to traverse all existing clusters upon the arrival of further *** work presents the NS-TEDA(Neighbor Search Based Typicality and Eccentricity Data Analysis)algorithm by incorporating a kd-tree(K-Dimensional tree)algorithm integrated with the Scapegoat *** arrival,this ensures that new data points interact solely with clusters in very close *** significantly enhances algorithm efficiency while preventing a single data point from joining too many clusters and mitigating the merging of clusters with high overlap to some *** apply the NS-TEDA algorithm to several well-known datasets,comparing its performance with other data stream clustering algorithms and the original TEDA *** results demonstrate that the proposed algorithm achieves higher accuracy,and its runtime exhibits almost linear dependence on the volume of data,making it more suitable for large-scale data stream analysis research.

关键词： Data stream clustering TEDA kd-tree scapegoat tree

来源：评论

学校读者我要写书评

暂无评论

A model of image retrieval based on kd-tree Random Forest

引用

DATA TECHNOLOGIES AND APPLICATIONS 2023年第4期57卷 514-536页

作者： Dinh, Nguyen Thi Nhi, Nguyen Thi Uyen Le, Thanh Manh Van, Thanh The Hue Univ Univ Sci Hue Vietnam Ho Chi Minh City Univ Food Ind Ho Chi Minh City Vietnam Univ Da Nang Univ Econ Da Nang Vietnam HCMC Univ Educ Ho Chi Minh City Vietnam

Purpose - The problem of image retrieval and image description exists in various fields. In this paper, a model of content-based image retrieval and image content extraction based on the kd-tree structure was proposed. Design/methodology/approach - A Random Forest structure was built to classify the objects on each image on the basis of the balanced multibranch kd-tree structure. From that purpose, a kd-tree structure was generated by the Random Forest to retrieve a set of similar images for an input image. A kd-tree structure is applied to determine a relationship word at leaves to extract the relationship between objects on an input image. An input image content is described based on class names and relationships between objects. Findings - A model of image retrieval and image content extraction was proposed based on the proposed theoretical basis;simultaneously, the experiment was built on multi-object image datasets including Microsoft COCO and Flickr with an average image retrieval precision of 0.9028 and 0.9163, respectively. The experimental results were compared with those of other works on the same image dataset to demonstrate the effectiveness of the proposed method. Originality/value - A balanced multibranch kd-tree structure was built to apply to relationship classification on the basis of the original kd-tree structure. Then, kd-tree Random Forest was built to improve the classifier performance and retrieve a set of similar images for an input image. Concurrently, the image content was described in the process of combining class names and relationships between objects.

关键词： kd-tree Random Forest Image classification Image retrieval Similar images Image content description

来源：评论

学校读者我要写书评

暂无评论

MCMSTClustering: defining non-spherical clusters by using minimum spanning tree over kd-tree-based micro-clusters

引用

NEURAL COMPUTING & APPLICATIONS 2023年第18期35卷 13239-13259页

作者： Senol, Ali Tarsus Univ Fac Engn Dept Comp Engn TR-33400 Tarsus Mersin Turkiye

Clustering is a technique for statistical data analysis and is widely used in many areas where class labels are not available. Major problems related to clustering algorithms are handling high-dimensional, imbalanced, and/or varying-density datasets, detecting outliers, and defining arbitrary-shaped clusters. In this study, we proposed a novel clustering algorithm named as MCMSTClustering (Defining Non-Spherical Clusters by using Minimum Spanning tree over kd-tree-based Micro-Clusters) to overcome mentioned issues simultaneously. Our algorithm consists of three parts. The first part is defining micro-clusters using the kd-tree data structure with range search. The second part is constructing macro-clusters by using minimum spanning tree (MST) on defined micro-clusters, and the final part is regulating defined clusters to increase the accuracy of the algorithm. To state the efficiency of our algorithm, we performed some experimental studies on some state-of-the-art algorithms. The findings were presented in detail with tables and graphs. The success of the proposed algorithm using various performance evaluation criteria was confirmed. According to the experimental studies, MCMSTClustering outperformed competitor algorithms in aspects of clustering quality in acceptable run-time. Besides, the obtained results showed that the novel algorithm can be applied effectively in solving many different clustering problems in the literature.

关键词： Clustering kd-tree Minimum spanning tree Micro-cluster Arbitrary-shaped clusters

来源：评论

学校读者我要写书评

暂无评论

A Fast and Generalized Broad-Phase Collision Detection Method Based on kd-tree Spatial Subdivision and Sweep-and-Prune

引用

IEEE ACCESS 2023年 11卷 44696-44710页

作者： Cao, Jiaqi Wang, Monan Harbin Univ Sci & Technol Sch Mech & Power Engn Harbin 230103 Peoples R China

Various graphics applications use multibody collision detection, a critical technology in computer graphics, system simulations, and virtual reality. In these simulation environments, broad-phase collision detection, as part of collision detection, plays a critical role in ensuring that rejecting disjoint objects and collision detection is accelerated. Few existing methods implement collision detection of millions of objects in a general-purpose environment on the CPU. This paper proposes a broad-phase collision detection algorithm based on kd-tree spatial subdivision and sweep-and-prune, which optimizes and accelerates broad-phase collision detection using a pre-sorting and temporal inference solution. Our method enables broad-phase collision detection for coherent and non-coherent settings for uniformly and non-uniformly sized objects respectively. Based on our proposed solution is tested in the context of complex scenarios and compared with other solutions available in the literature and in the industry. The experimental results show that our approach has a 1X to 2X performance improvement in virtual environments with up to 1024 x 103 objects, reaching the fastest collision detection speed of 119.45 milliseconds per frame in the test environment.

关键词： Collision avoidance Computational modeling Solid modeling Object recognition Inference algorithms Cognition Three-dimensional displays Collision detection kd-tree spatial subdivision sweep and prune

来源：评论

学校读者我要写书评

暂无评论

Boosting interclass boundary preservation (BIBP): a kd-tree enhanced data reduction algorithm

引用

International Journal of Information Technology (Singapore) 2024年第7期16卷 4069-4088页

作者： Fuangkhon, Piyabute Department of Digital Business Management Assumption University of Thailand

Interclass boundary preservation (IBP) is a data reduction technique that maintains only the instances (referred to as “prototypes”) at the decision boundary between consecutive classes of data to reduce the dataset’s size. It augments the original distance-based instance selection (DIS) to support a minimum class size using Naïve random over-sampling, preventing a particular class from being underrepresented in kNN classification. Both techniques suffer from prolonged instance selection execution due to using the Euclidean distance function in a one-versus-rest approach. This paper proposes Boosting Interclass Boundary Preservation (BIBP) and Boosting Distance-Based Instance Selection (BDIS) algorithms that replace the Euclidean distance function with a K-dimensional tree (kd-tree) in their original algorithms to significantly reduce their runtimes, enhancing applicability to real-world datasets. Through hyperplane partitioning in the kd-tree, searching for prototypes becomes much faster than a brute-force approach using Euclidean distance. The evaluation was conducted on real-world datasets from the UCI machine learning repository. The results demonstrate that the proposed BIBP and BDIS algorithms achieve significant runtime reductions while maintaining data reduction and classification performance comparable to their original counterparts. © Bharati Vidyapeeth's Institute of Computer Applications and Management 2024.

关键词： Data reduction Instance selection kd-tree Naïve random over-sampling Neural network

来源：评论

学校读者我要写书评

暂无评论

An adaptive coverage aware data gathering scheme using kd-tree and ACO for WSNs with mobile sink

引用

JOURNAL OF SUPERCOMPUTING 2022年第11期78卷 13530-13553页

作者： Al Aghbari, Zaher Khedr, Ahmed M. Khalifa, Banafsj Raj, Pravija P., V Univ Sharjah Dept Comp Sci Sharjah 27272 U Arab Emirates

While several Mobile Sink (MS)-based data gathering methods have been proposed for Wireless Sensor Networks, most of them are less adaptive to changes in network topology, and the planned MS trajectory cannot be refined to accommodate node failures. Hence, a kd-tree-based scheme (kdT) is proposed, which is an adaptive and robust algorithm that reduces network energy consumption and data gathering delay. In contrast to many existing algorithms, the number of Rendezvous Points (RPs) are assigned dynamically by prioritizing the nodes' coverage. Overlapping coverage of RPs is minimized, while guaranteeing 100% coverage of nodes. kdT is adaptive to network topology changes, and the planned MS trajectory can be refined to accommodate node failures. The shortest MS path is found using Ant Colony Optimization. Simulation results show that kdT requires approximately half the number of RPs and about 13% reduction in MS travel time compared to existing schemes.

关键词： Wireless sensor networks kd-tree Travel route planning Trajectory design Data gathering Mobile sink Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

基于自动终止准则改进的kd-tree粒子近邻搜索研究

引用

工程科学与技术 2024年第6期56卷 217-229页

作者：张挺王宗锴林震寰郑相涵福州大学土木工程学院福建福州350116 福州大学计算机与大数据学院福建福州350116

对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n_(0... 详细信息

对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n_(0)对近邻搜索效率的影响。试验表明,ATC-kd-tree具有更高的近邻搜索效率,相较于不使用自动终止准则的kd-tree搜索效率最高提升46%,且适用性更强,可求解不同N值的近邻搜索问题,解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时,本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过2维阿米巴虫形状的参数优化试验发现,GSCD法可更为快速地率定ATC-kd-tree的可变参数,其优化效率比网格搜索法最高提升了205%,相较于改进网格搜索法最高提升了90%。研究结果表明,ATC-kd-tree和GSCD法不仅提高了近邻搜索的效率,也为复杂运动中近邻粒子搜索问题提供了一种更为高效的解决方案,能够显著降低计算资源的消耗,进一步提升模拟的精度和效率。

关键词： kd-tree 粒子近邻搜索自适应网格搜索法坐标下降法

来源：评论

学校读者我要写书评

暂无评论

KMiST: A kd-tree Based Fast Minimum Spanning tree Algorithm 15

KMiST: A KD-Tree Based Fast Minimum Spanning Tree Algorithm

引用

15th International Conference on Computing Communication and Networking Technologies, ICCCNT 2024

作者： Ghosh, Pulak Mishra, Gaurav Visvesvaraya National institute of Technology Nagpur India

ISBN: (纸本)9798350370249

Minimum Spanning trees (MSTs) are crucial in graph theory and computer science for understanding complex networks. Their ability to efficiently connect nodes while minimizing total edge weight makes them indispensable tools in various domains. However, the quadratic time complexity of standard MST algorithms, renders them impractical for large-scale graphs, motivating the development of more efficient approaches for MST construction. A critical aspect is how to efficiently generate a intermediary graph that sufficiently encapsulates local neighborhood information with sub-quadratic time. We propose a method utilizing k-dimensional trees (kd trees) for efficient construction and connection of similarity graphs. By harnessing the spatial indexing properties of k-d trees, this approach seeks to mitigate computational challenges often encountered in graph construction. Our algorithm achieves a time complexity of O (n log2 n), significantly improving upon the O(n2) complexity of standard MST algorithms. Experimental analyses show that intermediary graph collects shorter edges and disregards the longer edges. The proposed method's performance was also justified through its application on several synthetic and real datasets with various characteristics, showcasing its potential to handle large-scale graphs efficiently. © 2024 IEEE.

关键词： Graph Theory kd-tree Large-Scale Graphs Minimum Spanning tree

来源：评论

学校读者我要写书评

暂无评论

Developing a model semantic-based image retrieval by combining kd-tree structure with ontology

引用

EXPERT SYSTEMS 2025年第1期42卷

作者： Le, Thanh Manh Dinh, Nguyen Thi Van, Thanh The Hue Univ Univ Sci Hue Vietnam HCMC Univ Food Ind HoChiMinh City Vietnam HCMC Univ Educ HoChiMinh City Vietnam

The paper proposes an alternative approach to improve the performance of image retrieval. In this work, a framework for image retrieval based on machine learning and semantic retrieval is proposed. In the preprocessing phase, the image is segmented objects by using Graph-cut, and the feature vectors of objects presented in the image and their visual relationships are extracted using R-CNN. The feature vectors, visual relationships, and their symbolic labels are stored in kd-tree data structures which can be used to predict the label of objects and visual relationships later. To facilitate semantic query, the images use the RDF data model and create an ontology for the symbolic labels annotated. For each query image, after extracting their feature vectors, the kd-tree is used to classify the objects and predict their relationship. After that, a SPARQL query is built to extract a set of similar images. The SPARQL query consists of triple statements describing the objects and their relationship which were previously predicted. The evaluation of the framework with the MS-COCO dataset and Flickr showed that the precision achieved scores of 0.9218 and 0.9370, respectively.

关键词： image retrieval kd-tree ontology relationship kd-tree similar images

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：