The pervasiveness of big data has revolutionized the landscape of information technology (IT), offering a wealth of insights and opportunities for various sectors, including healthcare, education, and the Internet of Things (IoT). However, the sheer volume and complexity of big data pose challenges in extracting meaningful knowledge. To address this, we propose a novel model for optimal sample selection, enabling efficient extraction of representative subsets from big data. The proposed model, based on optimal jumps, dynamically adapts the clustering process to enhance the efficiency of data sampling. We employ the Adjusted Rand Index (ARI) to evaluate the similarity between clusters and guide the selection of new data in each iteration This model holds the potential to significantly enhance the utilization of big data while reducing computational demands. The proposed could run on big datasets and the samples taken represents the dataset.
Method Article
A Novel Intelligent Model Based on Optimal Jumps for Creating Data Sampling from Big Dataset
https://doi.org/10.21203/rs.3.rs-4015981/v1
This work is licensed under a CC BY 4.0 License
Version 1
posted
You are reading this latest preprint version
Big data sampling
Samples
DBSCAN
Optimal Jump
Cluster sampling
The emergence of big data has posed significant challenges in the field of information technology. With its vast volume, intricate nature, and diverse characteristics, big data presents formidable hurdles for traditional data processing techniques. Moreover, inherent issues such as noise, redundancy, imbalance, and false discovery rates further compound the challenges associated with big data. These factors collectively contribute to the computational complexity and burden, rendering many conventional algorithms ineffective.
To tackle these challenges, various approaches have been proposed, including feature selection methods and sampling techniques. Feature selection methods aim to identify and extract the most relevant and informative features from the dataset, thereby reducing dimensionality and improving computational efficiency. On the other hand, sampling techniques focus on extracting representative subsets from big data, enabling the construction of cost-effective models without compromising accuracy.
Our proposed model falls under the category of sampling-based approaches. We aim to alleviate the burden of big data volume by iteratively extracting small samples from the dataset. This approach not only reduces computational demands but also ensures that the extracted samples cover a wide range of cases, introduce an acceptable degree of redundancy, maintain data balance, and reduce noise. Additionally, it enhances practicality and scalability.
This paper introduces "Jump Sampling," an innovative approach to sample selection that leverages the DBSCAN clustering algorithm to efficiently select samples from big datasets. DBSCAN is renowned for its versatility in identifying clusters of various shapes and its adept handling of noisy patterns[1]. However, it faces computational challenges due to the high complexity of its nearest neighbor query[1]. To overcome this hurdle, two strategic approaches are employed.
Firstly, Algorithmic Optimization concentrates on refining the efficiency of the nearest neighbor query algorithm itself. This involves incorporating advanced techniques like spatial indexing structures (e.g., KD-trees) to expedite the search process. However, this method may encounter difficulties when dealing with high-dimensional datasets. Secondly, Data-driven Strategies implement sampling techniques to operate on a representative subset of instances, thereby reducing the overall data processed during the nearest neighbor query. Techniques such as random sampling, stratified sampling, or the application of locality-sensitive hashing (LSH) are deployed, striking a balance between precision and computational efficiency.
In our model, ARI is utilized to measure the similarity between two clusters, assessing the agreement between the labels assigned by a clustering algorithm. This index is often used in the evaluation of clustering algorithms as it considers all pairs of samples and measures how many pairs are assigned to the same or different clusters.
Samples shall cover as most variety of data as possible, to be bias, introduce an acceptable degree of redundancy and reduce noise with the least computational cost possible. In this approach, we employ the DBSCAN clustering algorithm to identify areas of density within the dataset, aided by the proposed jump and ARI metrics. ARI, which does not entail a high computational cost. our primary objective is not to establish clusters but rather to identify representative samples. DBSCAN is chosen for its ability to discern density-based structures within the data, allowing us to pinpoint regions of significance. By incorporating ARI, a measure of clustering similarity, we can evaluate the effectiveness of our approach in identifying these dense areas and selecting suitable samples from them. Although ARI itself does not impose significant computational overhead, the overall computational complexity of our approach may vary depending on the dataset's size and dimensionality and minPoints parameter of DBSCAN . It's important to note that the efficacy of our approach hinges on the suitability of DBSCAN and ARI for our specific dataset and objectives. In the proposed model, the Jump is a critical aspects as it keeps the probability of finding new minor clusters high , it does not neglect sparse areas. Jump mechanism divides dataset initially to 2 segments (visited, unvisited) the visited segments is further divided into promising areas and weak or sparse areas as the model will collocate the number of cluster created and how many noise points. the jump collects fixed number of records in every iteration fig 1 illustrates the flowchart of jump while fig 2 depicts the model .
2.1 algorithm for jump mechanism
- The initial jump is randomly made within the range of the dataset with a specific jump size.
- If the data points are good (resulting in many new clusters), this area is considered promising, and the next jump is made next to it.
- Jumping will continue to this area until it is fully utilized, meaning the returned data is similar to the data we already have or contains too much noise.
- A new jump is executed to a far unvisited area. The model controls the jump, utilizing DBSCAN and ARI to determine whether to accept, exclude, or replace the sample.
In this paper, our approach involves utilizing clustering on jump data to identify clusters and noise points, which are crucial for the functionality of the jump and for enabling comparison between clusters using ARI. The limited data provided by the jump enhances clustering efficiency, although the effectiveness of DBSCAN depends on two key parameters: minPoints and eps. To address this, we manually specify these parameters in our study.
We assess the output of each jump using ARI against all previously accepted samples. Clusters meeting our criteria are accepted and added to the array of accepted clusters. Conversely, if the ARI index falls below a certain threshold, the cluster is excluded. Excluded clusters are then compared to the most relevant clusters from the accepted set. If an excluded cluster demonstrates superior characteristics, it replaces the relevant accepted cluster, while the latter is added to the excluded array ,this process continues until we stopped finding new clusters as the ensures that we get the optimal representatives of the big dataset , and this is the stopping criteria thus there is no need to specify sample size
Fig. 1 Jump Algorithm Flow Chart
2.2 Flowchart and proposed model
1 Start
2 Supply minPTS and esp and jump size
3 Execute the initial jump, cluster it, and add it to the accepted cluster since there is nothing yet to compare it to
4 Execute the next jump, cluster it, and then compare it with the accepted clusters for similarity. The Adjusted Rand Index (ARI) comes in handy in this process. If the result of ARI is less than 0, the clusters are not accepted.
5 If the result is greater than or equal to 0, then the cluster is further checked for better sampling with the most similar cluster.
5.1 If the current cluster (doomed to be excluded) has better clusters, it is replaced with the already accepted weaker cluster. The replaced cluster is then added to the rejected.
5.2 If the current cluster is not better than the already accepted most similar cluster, it is added to the rejected clusters.
6 Check if the exit limit has been reached .
6.1 If no execute a jump .
6.2 If yes stop .
7 Stop.
Experiments were repeated with different DBSCAN parameters, specifically MinPoints, until the optimal value was found. The epsilon (eps) value was kept fixed at 0.5. Table 1 lists the final parameters used for DBSCAN, and the reported time is the average time of 5 runs.
The experiment was conducted on a PC running Windows 10 Enterprise with 8 GB of RAM and an Intel® Core™ i5-10400 CPU, utilizing an HDD hard disk. The experiments demonstrated that the model could handle big datasets, such as Machinery Fault\imbalance, which was 5.37 GB in size.
The execution time is affected by the MinPoints parameter; it should be set low because the data is divided into many chunks, thereby reducing redundancy. The jump sample size parameter does not have a significant effect on the result.
The model demonstrates excellent performance in selecting samples across datasets of varying sizes and densities.
DBSCAN parameters has great impact on the result for the best result these parameters shall be changed according to the locality of each jump ,Thus these parameters shall be set dynamically. Jump size does not have a direct impact to the result although it shall be set dynamically in the future work.
Author Contribution
M.Z wrote the main manuscript text and prepared all figures.All authors reviewed the manuscript
- Deng, Dingsheng. "DBSCAN clustering algorithm based on density." 2020 7th international forum on electrical engineering and automation (IFEEA). IEEE, 2020.
- Warrens, Matthijs J., and Hanneke van der Hoef. "Understanding the adjusted rand index and other partition comparison indices based on counting object pairs." Journal of Classification 39.3 (2022): 487-509.
- Chacón, José E., and Ana I. Rastrojo. "Minimum adjusted Rand index for two clusterings of a given size." Advances in Data Analysis and Classification 17.1 (2023): 125-133.
- de Moura Ventorim, Igor, et al. "BIRCHSCAN: A sampling method for applying DBSCAN to large datasets." Expert Systems with Applications 184 (2021): 115518.
- Ros, Frédéric, and Serge Guillaume. "DENDIS: A new density-based sampling for clustering algorithm." Expert Systems with Applications 56 (2016): 349-359.
- Ros, Frédéric, and Serge Guillaume. "DIDES: a fast and effective sampling for clustering algorithm." Knowledge and information systems 50 (2017): 543-568.
- [7] Zhu, Lu, et al. "Improvement of DBSCAN algorithm based on adaptive Eps parameter estimation." Proceedings of the 2018 international conference on algorithms, computing and artificial intelligence. 2018.
- Xianting, Qi, and Wang Pan. "A density-based clustering algorithm for high-dimensional data with feature selection." 2016 International Conference on Industrial Informatics-Computing Technology, Intelligent Technology, Industrial Information Integration (ICIICII). IEEE, 2016.
- Alwosheel, Ahmad, Sander van Cranenburgh, and Caspar G. Chorus. "Is your dataset big enough? Sample size requirements when using artificial neural networks for discrete choice analysis." Journal of choice modelling 28 (2018): 167-182.
- Silva, José, Bernardete Ribeiro, and Andrew H. Sung. "Finding the critical sampling of big datasets." Proceedings of the Computing Frontiers Conference. 2017.
- Luchi, Diego, Alexandre Loureiros Rodrigues, and Flávio Miguel Varejão. "Sampling approaches for applying DBSCAN to large datasets." Pattern Recognition Letters 117 (2019): 90-96.
- Berndt, Andrea E. "Sampling methods." Journal of Human Lactation 36.2 (2020): 224-226.
- Li, Mingyang, et al. "A method of two-stage clustering learning based on improved DBSCAN and density peak algorithm." Computer Communications 167 (2021): 75-84.
No competing interests reported.