Fast approximate K neighbor method based on tree strategy and balanced K-means clustering

Abstract

The invention provides a fast approximate K neighbor method based on a tree strategy and balanced K-means clustering, so as to improve the performance and speed of approximate K neighbor retrieval. The method comprises the following steps: firstly, constructing a balanced K-means tree through a balanced K-means clustering method, enabling data to be organized in a tree-shaped structure efficientlyand orderly, and realizing rapid positioning of any new sample data; then, utilizing an anchor positioning method and a neighbor cluster idea, and quickly finding a plurality of approximate neighborpoints, namely K neighbor points, of the new data sample through a balance tree. According to the method, the advantages of a tree-based K-nearest neighbor algorithm and a balanced K-means algorithm are taken into account at the same time, and the method can be applied to the fields of image recognition, data compression, mode recognition and classification, machine learning, document retrieval systems, statistics, data analysis and the like.

Description

technical field [0001] The invention belongs to the technical field of machine learning and data mining, and in particular relates to a fast approximate K nearest neighbor method based on tree strategy and balanced K-means clustering. Background technique [0002] In the era of mobile Internet, people's daily life is faced with the impact of massive data every day, such as personal information, video records, image collection, geographic information, log files, etc., in the face of such a large and growing data information, how to process all The effective storage, indexing and querying of the required information is a hot research topic both at home and abroad. [0003] Approximate K-nearest neighbor retrieval was initially applied to document retrieval systems as a method for finding similar document information, and then in geographic information systems, K-nearest neighbor retrieval was also widely used in location information, query, analysis and statistics of spatial d...

AI Technical Summary

Problems solved by technology

For example, K-nearest neighbor retrieval in large-scale high-dimensional data has always been one of the hot issues that are difficult to overcome. In the tree structure method, KD tree, KD random forest, etc. have good results, but in the KD tree algorithm, The retrieval process needs to go back to the previous node continuously. The higher the dimension, the more backtracking times are required, and the efficiency of the algorithm will be lower. In KD random forest, although the backtracking problem can be alleviated to a certain extent, due to KD Random forest uses multiple KD trees to search together. How to balance memory usage and algorithm efficiency has become a new problem

Images