Positive region preserved random sampling: an efficient feature selection method for massive data
Hexiang Bai, Deyu Li, Jiye Liang, Yanhui Zhai · 2025
Read Positive region preserved random sampling: an efficient feature selection method for massive data by Hexiang Bai, Deyu Li, Jiye Liang, Yanhui Zhai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01998.txt.
Introduction
Picking the few useful features out of a mountain of data can overwhelm an ordinary computer. Hexiang Bai and three co-authors propose a sampling method in a 2025 paper, grounded in rough set theory, that finds a near-best feature set fast. Their key measure counts how many pairs of records a feature set can tell apart, out of all pairs that need telling apart.
The method builds small samples that keep the so-called positive region of the data, then searches those. Before searching, it can already promise a floor for how well the chosen set will do. Tests on eleven datasets showed fast results that beat the promised floor.
Catalog record
| CREATOR | Hexiang Bai, Deyu Li, Jiye Liang, Yanhui Zhai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01998
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Positive region preserved random sampling: an efficient feature selection method for massive data Hexiang Bai, Deyu Li, Jiye Liang, Yanhui Zhai Abstract Selecting relevant features is an important and necessary step for intelligent machines to maximize their chances of success. However, intelligent machines generally have no enough computing resources when faced with huge volume of data. This paper develops a new method based on sampling techniques and rough set theory to address the challenge of feature selection for massive data. To this end, this paper proposes using the ratio of discernible object pairs to all object pairs that should be distinguished to measure the discriminatory ability of a feature set. Based on this measure, a new feature selection method is proposed. This method constructs positive region preserved samples from massive data to find a feature subset with high discriminatory ability. Compared with other methods, the proposed method has two advantages. First, it is able to select a feature subset that can preserve the discriminatory ability of all the features of the target massive data set within an acceptable time on a personal computer. Second, the lower boundary of the probability of the object pairs that can be discerned using the feature subset selected in all object pairs that should be distinguished can be estimated before finding reducts. Furthermore, 11 data sets of different sizes were used to validate the proposed method. The results show that approximate reducts can be found in a very short period of time, and the discriminatory ability of the final reduct is larger than the estimated lower boundary. Experiments on four large-scale data sets also showed that an approximate reduct with high discriminatory ability can be obtained in reasonable time on a personal computer. 1 Introduction In many fields of artificial intelligence, it is important to remove redundant features and irrelevant features for intelligent machines to complete their tasks because redundant features and irrelevant features may deteriorate the performance of the classifier used [ 10 ] . By carefully selecting a small number of features, an intelligent machine can apply more constrained statistical models with fewer parameters and improve the quality of inference [ 9 ] . However, the time cost used by most available feature selection methods depends on the scale of target data sets. With the development of “big data”, the scale of data sets become larger and larger and traditional feature selection methods become inefficient in dealing with these data sets. Currently, there are two popular dimension reduction methods: feature selection and feature extraction. Compared with the feature extraction methods, feature selection methods do not construct new features from the original feature set, and the features selected have clear physical meaning and are easy to explain. Feature selection methods can be divided into two categories: wrapper and filter approaches [ 22 ] . In the wrapper approach, the feature subset selection algorithm searches for a good subset using the induction algorithm itself as part of the function that evaluates the feature subsets [ 22 ] . The wrapper approach takes into account the induction bias of the classifier. Accordingly, the classification result can have relatively high classification accuracy using the feature subset selected. However, the wrapper approach estimates the classification error probability of the classifier for each candidate feature subset [ 39 ] . Accordingly, it is very slow when dealing with large-scale data sets [ 22 ] . The filter approach ignores the effects of the selected feature subset on the performance of the induction algorithm [ 22 ] and directly selects features according to certain measures of the attributes. The most commonly used measures can be divided into four different categories: distance measures [ 31 ] , information measures [ 5 ] , dependence measures [ 30 ] and consistency measures [ 2 , 10 ] . A consistency measure does not attempt to maximize the class separability but tries to retain the discriminating power of the data defined by the original features [ 10 ] . Dash and Liu 2003 has shown that the consistency measure can evaluate a feature subset in O(N) time, check a subset of features at a time and help remove both redundant and irrelevant features simultaneously. Accordingly, the consistency measure-based feature selection methods are suitable for large-scale data analysis. The reduction technique in rough set theory is a well-developed consistency-based feature selection method. Meanwhile, most rough set-based reduction techniques also take the importance of attributes into account from different perspectives. Rough set theory [ 33 ] is an effective mathematical framework that has been successfully used in pattern recognition [ 38 , 29 ] , machine learning [ 15 , 20 ] , data mining, and knowledge discovery [ 6 , 3 , 32 ] in many fields. The reduction technique in rough set theory removes as many redundant features and irrelevant features as possible based on the principle of preserving the discriminatory ability of all features, i.e., two discernible objects can also be distinguished using the selected features. Compared with statistical methods, it requires no prior knowledge nor any assumptions about the distribution of the data. Based on different consistency and attribute importance measures in the rough set, numerous kinds of reduct have been developed, such as positive region reduct [ 23 ] , condition entropy reduct [ 42 ] , maximal distribution reduct [ 52 ] , and decision value preservation reduct [ 28 ] . Zhou et al. 2011 summarized 13 different reducts based on different measures and the relations among them. They also pointed out that the associated discernibility matrix can be constructed for different types of reduct. The reduct can then be obtained using the discernibility matrix. The discernibility matrix-based reduct finding algorithm [ 37 , 23 ] is one of the earliest proposed reduct finding algorithms. This method has been proven to be able to find the minimal reduct. Unfortunately, finding the minimal reduct was proven to be NP-hard [ 45 ] . However, rather than the minimal reduct, an easily found approximate reduct of sufficient quality is adequate for practical applications. Especially in the analysis of massive data, even algorithms with polynomial time complexity can barely achieve practical requirements. Accordingly, many approximate reduct finding algorithms have been proposed, using different methodologies from different perspectives. With respect to accelerating the finding process, these reduct finding algorithms can be divided into four types. The first type of algorithm speeds up the reduct finding process by reducing the feature subspace to be searched, or by using efficient search strategies to search the feature space. Besides some generally adopted feature subspace searching methods used in feature selection [ 10 ] , many new techniques have been used in finding reducts. For example, Wróblewski 1995 proposed using a genetic algorithm to speed up the search of the possible feature subset to find the approximate minimal reduct. This paper also integrated a genetic algorithm with a greedy algorithm to help search for short reducts. A greedy algorithm is another widely used technique for speeding up the search for the minimal reduct [ 17 , 13 ] . Other techniques that are used to speed up the search of the possible feature subsets include ant