Euclidean distance stratified random sampling based clustering model for big data mining

INTRODUCTION

Nowadays, massive data has been grown by the use of digital and communication technologies, especially related to sensor networks, Internet of Things, social media, healthcare, e-commerce, cloud computing, cyber-physical systems, and so on. In May 2018, Forbes released an article related to the speed of data production. Stating that, Google searches 3.5 billion requests per day and 1.2 trillion requests per year worldwide. YouTube users watched 4,146,600 videos, Twitter users wrote 456,000 tweets, Instagram, and Snapchat users shared 46,740 and 527,760 photos, Facebook users wrote 510,000 comments, 293,000 status updates, and 300 million photos updated every minute worldwide.¹ These digital platforms have a variety of sources that generate heterogeneous data at high speed. Complex sources, data formats, and large-scale data production define big data. It is a revolution of conventional and batch data because internet users have grown by 7.5% from 2016 to 2018.¹ The above data statistics recognize big data in terms of volume, variety, velocity, and determine traditional data mining algorithms, tools, and techniques are incompatible.² Essential characteristics of big data are recognized as volume, variety, velocity, whatever value, veracity, variability, visualization identified under the supportable characteristics of big data.^3-6

One way of summarization is “The heterogeneous (variety) data is generated, created, and updated by heterogeneous (variety) sources through batch, real-time, and stream environment at high speed (velocity). The variety and velocity increase the data size (volume) to multiple Terabytes and Petabytes”. The veracity, value, variability, and visualization are recognized under extreme characteristics that are supported by volume, variety, and velocity. Based on the existing research examination,^3-6 extreme characteristics described as “Veracity encourages accuracy through variety. Value supports the results of data mining by volume, variety, and velocity. Variability boosts sentiment analysis via volume and variety. Visualization supports graphical representation according to the user-readable mode by using other big data characteristics”.

Data mining algorithms are required to improve upon their computational cost, speed, scalability, flexibility, and efficiency according to the essential characteristics of big data.⁷ Extraction of appropriate hidden predictive information, patterns and relations from the heterogeneous large-scale dataset is big data mining,⁸ which requires higher transparency for volume, variety and velocity because large-scale data contains valuable knowledge and information.⁹ Mining techniques have limited applicability for high volume datasets due to millions of tuples and records. To overcome these issues, two alternatives are presented. The first is to scale up the data mining algorithm and the second is to reduce the dataset size. These two alternatives allow effective and feasible data mining.¹⁰ Intelligent big data mining is a combination of statistics and mining techniques with data and process management.⁹

Sampling is a technique of data reduction that uses a statistical model.^{11, 12} It provides a more effective evaluation with accuracy¹³ and is recognized as a “bag of little bootstraps”.¹⁴ Author¹⁵ described a standard framework of the sampling process for data mining using clustering. According to this sampling framework, the entire dataset is split into a sample and an un-sample component. The data mining algorithm uses the sample component and gives partial results. This is referred to as an approximate result. Thereafter, merges the partial results and un-sample unit by using a sample extension strategy that produces a final approximate result.

Various applications adopt cluster analysis such as social network analysis, ontology, customer segmentation, scientific data analysis, bioinformatics, natural classification, underlying structure, data compression, mobile ad-hoc networks, target marketing, texture segmentation, scientific data analysis, and vector quantization.^{15, 16} Clustering is one of the essential techniques in data mining for discovering the class of unlabeled data based on distance, similarity and dissimilarity. It discovers hidden relations, patterns, dance and information between the two classes, and improves the efficiency and effectiveness of the data mining model.¹⁷ Some authors^{16, 18} identified conventional clustering algorithms for big data mining by comparing the volume, variety and velocity, and suggested K-Means, BFR, CURE, BIRCH, CLARA, DBSCAN, DENCLUE, Wavecluster, and FC are robust for big data mining.

Contributions in the past^{7, 15, 16, 19, 20} addressed cluster creation techniques under single and multiple machine execution environments of big data mining. Clustering techniques for big data mining are categorized into divide-and-conquer, parallel, center reduction, efficient nearest neighbor (NN) search, sampling, dimension reduction, incremental, and condensation methods. Implementation of the parallel method is useful inside of multiple machines and other cluster construction methods are executed inside of both machine environments.²¹ This article uses sampling-based method for cluster creation under a single machine execution environment. Sampling mechanism increases the speed of the clustering algorithm and reduces computation time. The efficiency of sampling depends on the sample selection strategies and sample size.

In literature 15 discussed the CURE hierarchical clustering algorithm, which is based on uniform random sampling and improves computational efficiency. This method first selects the sample and thereafter carries the hierarchical clustering. Kollios et al.²² has used the density biased sampling technique for cluster construction and outlier detection within the K-Means and K-medoids algorithm. David et al.²³ present a sample-based clustering framework for K-Means and K-Median clustering algorithms. This sampling framework achieves approximation results and depends on the sample size and accuracy parameters because the sample bounds the convergence to optimal clustering.

Aggarwal et al.²⁴ proposed a bi-criteria approximation approach for the initial centroid selection of K-Means clustering using adaptive sampling. This approach achieves ineffective triangle inequalities due to excessive Euclidean distance computations and distance comparison. Bejarano et al.²⁵ suggested a sampler algorithm for K-Means clustering based on random sampling. This algorithm reduces the distance estimation and computational cost in each iteration. The sampler algorithm increases the computation time for massive multi-dimensional data due to sample size estimation in each iteration. Cui et al.²⁶ suggested optimized K-Means clustering by random sampling and parallel execution strategies. This strategy eliminates the iteration of K-Means inside parallel execution and yields effective performance. Xu et al.²⁷ described the random instance sampling-based approximate clustering approach for text-based data and compared it against K-Means, and observed sampling-based clustering to reduce computationally expensive.

Zhan et al.²⁸ introduced a spectral clustering algorithm by incremental Nystrom sampling method for large-scale and high-dimensional datasets. This algorithm achieves optimal approximation results and shows that maximum sampling trials efficiently reduce sampling error. Ros et al.²⁹ used a combination of distance and density sampling for K-Means and hierarchical clustering. This method eliminates multiple distance computations in both clustering algorithms and is insensitive to data size, cluster noise, data, and cluster initialization. However, the combination of both sampling techniques increases the computation cost in the first iteration of the clustering. Zhao et al.³⁰ presents Cluster Sampling Arithmetic (CSA) efficient heuristic approach for clustering through random sampling. This algorithm reduces the computation time by obtaining the minimum sample set and avoids the local optimum problem. The CSA uses a parallel execution strategy and discovered the initial centroid of K-Means clustering.

Aloise et al.³¹ used iterative sampling to solve the minimax diameter clustering problem. The minimax diameter clustering problem is related to minimizing the maximum intra-cluster dissimilarity. The solution to the minimax diameter clustering problem is to solve the partitioning clustering objective. Ben Hajkacem et al.³² used reservoir random sampling and proposed the sampling-based STiMR K-Means clustering algorithm. The STiMR K-Means algorithm is used triangle inequality and MapReduce acceleration techniques for fast execution. This algorithm suffers from scalability-related issues. Li et al.³³ proposed sampling-based K-Means (SKMeans) and discovered excellent results as compared to the K-Means algorithm. This algorithm effectively reduces data size and increases cluster effectiveness and efficiency. Luchi et al.³⁴ enhanced the DBSCAN clustering algorithm by sampling in terms of clustering time and scalability, which is known as Rough-DBSCAN and I-DBSCAN. These algorithms are influenced by some parameters such as sample size.

Based on the above research perspective, sampling is used for different kinds of clustering problems such as outlier detection, initial centroid identification, cluster construction, data size selection, computation cost, sampling error, trails of sampling, local optima, clustering objective, enormous distance computation, scalability, speed-up, and so on. The literatures 26, 27, 30, 33 used multiple machines and literatures 22-25, 28, 29, 31, 32, 34 used a single machine execution environment for clustering, and most of the clustering algorithms achieved approximation results. This study considers the improvement of random sampling concerning cluster creation in a single machine execution environment.

Some other sampling-based data mining techniques are density biased sampling,²² CURE (Clustering Using REpresentatives), RSEFCM (Random Sampling plus Extension Fuzzy C-Means), CLARANS (Clustering Large Applications based on Randomized Sampling),¹⁵ eNERF (extended non-Euclidean relational fuzzy c-means clustering),³⁵ progressive sampling-based mining of association rules,³⁶ GOFCM (geometric progressive fuzzy c-means),¹⁵ EM clustering,³⁵ STiMR K-Means,³² AdROIT (Adaptive Reservoir sampling Of stream In Time),³⁷ random pairing,³⁸ adaptive-size reservoir sampling, Stratified Reservoir Sampling,³⁹ Monte Carlo based uncertainty quantification and Refined Stratified Sampling,⁴⁰ SSEFCM (Stratified sampling Plus Extension Fuzzy C Means),¹⁵ BIRCH,¹⁶ and so forth.

The objective of this article is to improve the computational efficiency and computing speed of conventional clustering algorithms without affecting cluster quality in big data mining using stratified random sampling. Section 0 describes the problem of data mining in large-scale data and presents big data clustering techniques based on existing computational methods. Section 0 has a stratified sampling method, stratum creation algorithm, and stratified sampling-based data mining algorithm. Section 0 contains the implementation of proposed work using the K-Means algorithm and validates them using internal measures. Section 0 concluded the study contribution and determines further research directions.

PROPOSED WORK

This section describes the clustering objective and presents the stratified sampling-based K-Means algorithm (SSK-Means) with Euclidean distance-based stratum (EDS) for cluster construction to big data mining using single machine execution. The proposed method enhances computational efficiency, computation cost and computing speed without affecting cluster quality and cluster objective.

Proposed model for big data mining

This subsection presents the stratified sampling based data mining model which has the capability to scale-up and speed-up any conventional data mining algorithm in big data environment. The proposed model uses a three phase with the help of stratified sampling, data mining technique as clustering and sample extension. In the following, details of stratified sampling and sample extension are described separately.

Stratified sampling (SS)

A successful sampling technique must be scalable under the high volume, variety, and velocity characteristics of big data. The SS reduces data volume size, data categorization from heterogeneous to homogeneous, and changes sample data concerning the time and user requirements.^{15, 30} The SS is an unbiased sampling approach from a statistical point of view that improves the convergence rate and reduces the variance.⁴⁰ These capabilities illustrate that SS is more scalable for big data mining compared to other sampling methods.

The objective of SS is to improve upon the precision of results based on homogeneous strata. It conducts the sampling process in two phases. In the first step, the entire dataset is grouped into small strata based on the similarity that is known as the stratification process. The second step extracts some relevant data points from each stratum for data mining or analysis called sample allocation. The data points of the sample collection are chosen by any sampling method according to the objective function.^{42, 43}

Suppose the dataset N is grouped into L strata and h^th stratum has consisted of N_h data points where $\sum _{h=1}^L{N}_h=N$ and h = 1,2,3,4…,L. The sample size n_h of each stratum is drawn by any suitable sampling technique as a research problem requirement where $\sum _{h=1}^L{n}_h=n$. The conceptual representation of SS is shown in Figure 1.

Let $Y_{\mathit{hi}}$ represents stratified dataset unit, where i is the selected attribute of the study from the h^th stratum, $i=1,2,3,\dots N_h$. Thereafter, random sampling extracts some homogeneous data points from each h stratum according to sample size. Let y_hi is a random sample unit_, where i^th data unit is selected from the h^th stratum for the mining model. The mean of h^th stratum is $\overline{Y_h}$ based on the ${\mathrm{N}}_h$ data units and mean of a random sample of the h^th stratum is $\overline{y_h}$ based on the $n_h$ data units.

$$\overline{Y_h}=\frac{1}{N_h}\sum _{i=1}^{N_h}{Y}_{\mathit{hi}}$$ ()

$$\overline{y_h}=\frac{1}{n_h}\sum _{i=1}^{n_h}{y}_{\mathit{hi}}$$ ()

The proportion $W_h$ of stratified sampling is $W_h=\frac{N_h}{N}$. The SS is an unbiased sampling process and produces high precision as compared to another biased sampling.

Stratification

In computer science, numerous stratification techniques are available for stratum formation, such as locality-sensitive hashing,¹⁵ greedy stratification method,⁴⁴ Latin Hypercube Sampling,⁴⁰ hamming distance and other collision-related hashing and bucket-based strategies. This article considers a new method of stratum creation using the Euclidean distance, which is known as Euclidean distance based stratum (EDS). The EDS algorithm used the maxmin data range heuristics approach for k stratum construction, which produces a high homogeneity within-stratum as compared to the mid-square, division, multiplication, and flooding hashing technique. This method first determines the k centroid of the dataset based on max and min range heuristics of the data points and thereafter assigns each data point to the k stratum through the Euclidean distance between the data points and the k centroid of the dataset. This approach describes the high density and compaction within each stratum. The EDS algorithm is described in Algorithm 1.

Algorithm 1. Proposed Euclidean distance based stratum (EDS)

Input:

1. data = Dataset with N data points.

2. i = Attributes of the dataset.

3. k = Required number of strata.

Output:

1. $L=\left\{N_1,N_2\dots N_k\right\}$ of homogeneous strata.

Method

Data set centroid identification

1. $v=(\mathit{max}\text{\_}\mathit{value}(i)-\mathit{min}\text{\_}\mathit{value}(i))/(k+1)$

2. if $v$ is greater than $\mathit{max}\text{\_}\mathit{value}(i)$ than

3. dataset has noise data point and exit()

4. else

Stratum centroid identification

5. $c_1=\mathit{min}\text{\_}\mathit{value}(i)+v$

6. $c_2=c_1+v$

7. $c_k=c_{k-1}+v$

8. End if

Assign data point into stratum

9. for i = 1 to length of data(i)

$${\mathit{dis}}_{\mathit{euclidean}}(\mathit{data}(i),\mathit{ck})=\sqrt{{\left|\mathit{data}(i)-\mathit{ck}\right|}^2}$$

10. Assign each data on the closed k stratum.

11. end for

12. Exit()

Sample allocation techniques

The efficiency of stratification depends upon the sample size taken from i^th stratum. Optimum allocation is one of the sample allocation techniques that decides sample size and variability according to stratum size and variability, with the lowest cost. The optimum allocation obeys the sample allocation characteristics of SS. The Neyman allocation method is a specific case of optimal allocation that minimizes the variance and total cost of the sample allocation. The number of sample units (sample size) to be selected from the h^th stratum is defined in Equation 6.

$$n_h=\frac{n{\mathrm{W}}_h{\sigma }_h}{\sum _{h=1}^L{\mathrm{W}}_h{\sigma }_h^2}$$ ()

where n is the total sample size, ${\sigma }_h$ is the standard deviation of h^th stratum, ${\sigma }_h^2$ is the variance of h^th stratum based on $N_h$ units.

$${\sigma }_h^2=\frac{1}{{\mathrm{N}}_h}\sum _{i=1}^{N_h}{\left(Y_{\mathit{hi}}-\overline{Y_h}\right)}^2$$ ()

$${\sigma }_h=\text{sqrt}\left({\sigma }_h^2\right)$$ ()

After deciding the optimum sample size of the stratum, the next is to data from the stratum through random sampling. The selection of data points from each stratum has equal changes with $1/n_h$ probability. Random sampling is used as the probability distribution and without-replacement procedure. The sample pool has n data units from the h^th stratum and this sample pool is used for mining.

Sample extension

Sample extension method produces final results by merging the results of the sample pool with un-sample data points through the sample extension technique. This study uses the K-NN classifier as a sample extension technique defined in Equation 9. The K-NN classifier is related to Euclidean distance and centroid that assigns un-sample data to the nearest sample pool results through Euclidean distance. According to the K-NN formulation, $A_i$ is a member of the un-sample data unit and $B_i$ is the mean of the sample pool result of the i^th variable.¹⁵

$${\mathit{dis}}_{\text{euclidean}}(A,B)=\sqrt{\sum _{i=1}^n{\left|A_i-B_i\right|}^2}$$ ()

Algorithm description

This subsection presents the stratified sampling-based data mining algorithm for K-Means (SSK-Means) clustering based on a single machine execution environment that reduces the computation cost and memory resources without impacting conventional K-Means effectiveness. The proposed model first constructs the stratum through the EDS algorithm and then collects samples from each stratum in the sample pool with the help of Neyman allocation and random sampling. Hereafter, the data mining technique is applied inside the sample pool that produces partial results. The last step merges the final result using a sample extension method that merges the un-sample data into partial results. The final result is validated through data mining measures. The details of the proposed SSK-Means algorithm is described in Algorithm 2 and their flowchart in Figure 2. The flow chart explains the essential concept of the SSK-Means algorithm.

Algorithm 2. Stratified sampling-based K-Means using proposed big data mining model

Input:

1. Data $N=\left\{N_1,N_2\dots N_n\right\}$ points on D dimension space.

2. i = Attributes of the dataset.

3. k = Required number of clusters.

Output:

1. $\mathit{AFc}=\left\{C_1,C_2\dots C_n\right\}$ Approximate Final clustering result.

Method

1. Call the EDH(N,i,k) algorithm to create an L stratum, where EDH returns the number of L strata equal to k.

2. Determine the number of data objects $n_h$ from each stratum using Equation 6.

3. Using random sampling, collect $n_h$ data objects from each stratum and assign each $n_h$ data object into the Ns sample pool and leftover data objects to the Us un-sample pool.

4. Apply required clustering techniques in the Ns pool such as PFc = KMeans(k,Ns)

5. Used Equation 9 for sample extension to obtain final clustering results through centroids of PFc and Us pool such as $\left[\mathit{AFc}={\mathit{dis}}_{\text{euclidean}}(\mathit{Us},\mathit{Mean}(\mathit{PFc}))\right]$

6. Exit

COMPUTATIONAL ANALYSIS

This section first explains the experimental setup and details of datasets for evaluation and then computes the performance of the SSK-Means algorithm using effectiveness and efficiency-related evaluation criteria.

Results

The reported results of internal measures are shown in Tables 2–6 based on the average of 10 trials. Optimal values for each investigation are marked in boldface. A number of clusters are set at three for experiments. Tables 2–4 presents the comparative examination of SC, DB, and CH values on experimental datasets using RSK-Means and SSK-Means algorithms, respectively. Table 2 illustrates that the proposed SSK-Means algorithm attained improved cluster compaction and separation than RSK-Means algorithm by maximization of SC value. The SC value of the SSK-Means algorithm is achieved better than RSK-Means except for the sample size 10% on the skin dataset and SC value of the SSK-Means algorithm is much optimized compared to RSK-Means in all sample sizes on the poker dataset.

TABLE 2. Comparison of SC values ($\text{means}\pm \mathrm{std}$) of RSK-Means and SSK-Means

Dataset	Sample size	RSK-Means	SSK-Means
Skin segmentation	5%	$0.51524\pm 0.0015$	$\mathbf{0.51566}\mathit{\pm }\mathbf{0.00152}$
	10%	$\mathbf{0.51567}\mathit{\pm }\mathbf{0.0014}$	$0.51482\pm 0.00130$
	15%	$0.51468\pm 0.00145$	$\mathbf{0.51528}\mathit{\pm }\mathbf{0.0012}$
	20%	$0.51483\pm 0.00145$	$\mathbf{0.51501}\mathit{\pm }\mathbf{0.00136}$
Poker	5%	$0.11876\pm 0.00269$	$\mathbf{0.11934}\mathit{\pm }\mathbf{0.00151}$
	10%	$0.11848\pm 0.00356$	$\mathbf{0.11895}\mathit{\pm }\mathbf{0.00235}$
	15%	$0.11892\pm 0.00261$	$\mathbf{0.11973}\mathit{\pm }\mathbf{0.00197}$
	20%	$0.11900\pm 0.00263$	$\mathbf{0.120020}\mathit{\pm }\mathbf{0.0020}$

• Note: Optimal values for each investigation are marked in boldface.

TABLE 3. Comparison of DB values ($\text{means}\pm \mathrm{std}$) of RSK-Means and SSK-Means

Dataset	Sample size	RSK-Means	SSK-Means
Skin segmentation	5%	$0.81746\pm 0.00969$	$\mathbf{0.81737}\mathit{\pm }\mathbf{0.00997}$
	10%	$0.81703\pm 0.00649$	$\mathbf{0.81634}\mathit{\pm }\mathbf{0.00774}$
	15%	$0.81684\pm 0.00771$	$\mathbf{0.81646}\mathit{\pm }\mathbf{0.00654}$
	20%	$0.81956\pm 0.00449$	$\mathbf{0.81584}\mathit{\pm }\mathbf{0.00744}$
Poker	5%	$2.14451\pm 0.0418$	$\mathbf{2.13567}\mathit{\pm }\mathbf{0.01555}$
	10%	$2.15167\pm 0.03592$	$\mathbf{2.14005}\mathit{\pm }\mathbf{0.01956}$
	15%	$2.14843\pm 0.03371$	$\mathbf{2.13856}\mathit{\pm }\mathbf{0.02105}$
	20%	$2.14216\pm 0.03183$	$\mathbf{2.12686}\mathit{\pm }\mathbf{0.01957}$

• Note: Optimal values for each investigation are marked in boldface.

TABLE 4. Comparison of CH values ($\text{means}\pm \mathrm{std}$) of RSK-Means and SSK-Means

Dataset	Sample size	RSK-Means	SSK-Means
Skin segmentation	5%	$305228.77\pm 129.69$	$\mathbf{305245.70}\mathit{\pm }\mathbf{107.42}$
	10%	$305262.29\pm 71.75$	$\mathbf{305282.88}\mathit{\pm }\mathbf{87.54}$
	15%	$\mathbf{305288.51}\mathit{\pm }\mathbf{49.36}$	$305279.05\pm 79.75$
	20%	$305253.11\pm 76.16$	$\mathbf{305273.44}\mathit{\pm }\mathbf{88.24}$
Poker	5%	$112017.24\pm 3764.91$	$\mathbf{112870.93}\mathit{\pm }\mathbf{2004.81}$
	10%	$111403.47\pm 3336.27$	$\mathbf{112326.03}\mathit{\pm }\mathbf{2308.14}$
	15%	$111794.62\pm 3351.86$	$\mathbf{112290.39}\mathit{\pm }\mathbf{2201.60}$
	20%	$112221.03\pm 2813.21$	$\mathbf{113468.85}\mathit{\pm }\mathbf{1909.35}$

• Note: Optimal values for each investigation are marked in boldface.

TABLE 5. Comparison of SC, DB, and CH values ($\text{means}\pm \mathrm{std}$) of K-Means, RSK-Means, and SSK-Means

Dataset	Evaluation criteria	K-Means	RSK-Means	SSK-Means
Skin segmentation	SC	$0.5123\pm 0.00291$	$0.51511\pm 0.00147$	$\mathbf{0.51519}\mathit{\pm }\mathbf{0.00134}$
	DB	$0.81712\pm 0.00583$	$0.81772\pm 0.00656$	$\mathbf{0.8165}\mathit{\pm }\mathbf{0.00645}$
	CH	$305269.71\pm 59.38$	$305258.17\pm 86.25$	$\mathbf{305270.27}\mathit{\pm }\mathbf{88.96}$
Poker	SC	$0.1167\pm 0.00402$	$0.11879\pm 0.00279$	$\mathbf{0.11951}\mathit{\pm }\mathbf{0.00195}$
	DB	$20.19172\pm 0.06467$	$2.14669\pm 0.03208$	$\mathbf{2.13528}\mathit{\pm }\mathbf{0.01895}$
	CH	$107753.84\pm 4693.99$	$111859.093\pm 3217.61$	$\mathbf{112739.056}\mathit{\pm }\mathbf{2086.43}$

• Note: Optimal values for each investigation are marked in boldface.

TABLE 6. Comparison of ET values ($\text{means}\pm \mathrm{std}$) of RSK-Means and SSK-Means

Dataset	Sample size	RSK-Means	SSK-Means
Skin segmentation	5%	$104.6961\pm 34.7258$	$\mathbf{72.0375}\mathit{\pm }\mathbf{18.3354}$
	10%	$\mathbf{69.3591}\mathit{\pm }\mathbf{25.4227}$	$87.3679\pm 17.5049$
	15%	$208.2860\pm 73.2868$	$\mathbf{70.5661}\mathit{\pm }\mathbf{15.3212}$
	20%	$219.1936\pm 105.7125$	$\mathbf{139.8222}\mathit{\pm }\mathbf{39.0222}$
Poker	5%	$\mathbf{168.71725}\mathit{\pm }\mathbf{35.4200}$	$162.05747\pm 25.58619$
	10%	$233.82127\pm 79.3378$	$\mathbf{211.25498}\mathit{\pm }\mathbf{37.78515}$
	15%	$316.57931\pm 94.7075$	$\mathbf{235.40716}\mathit{\pm }\mathbf{54.46616}$
	20%	$413.60596\pm 75.4575$	$\mathbf{397.17432}\mathit{\pm }\mathbf{113.9999}$

• Note: Optimal values for each investigation are marked in boldface.

Table 3 reveals that the proposed SSK-Means algorithm obtained a better distance within and between clusters than RSK-Means algorithm through minimization of DB value. The DB value of the skin dataset is close to zero because the dataset uses an exact number of clusters. The DB value of the poker dataset is higher than one due to the reason it requires more clusters. The DB value of SSK-Means is accurate as opposed to RSK-Means in both datasets. Table 4 reflects that the proposed algorithm achieved excellent variance ratio between sum of squares within and between by maximization of CH value. Validation of CH score and SSK-Means algorithm, the skin dataset obtained better CH as compared to RSK-Means excluding sample size 15%, and poker dataset achieved better-optimized CH value as compared to RSK-Means in all sample sizes.

Table 5 presented the SC, DB, and CH examinations of K-Means, RSK-Means, and SSK-Means using average results of the selected sample size, where SSK-Means obtained better SC, DB, and CH results compared to K-Means and RSK-Means on both datasets. This reflection demonstrates that the SSK-Means seems to be achieved efficiencies homogeneity, compaction, separation, similarity and than K-Means, RSK-Means algorithms.

The execution time and speedup ratio validate the algorithm efficiency. Table 6 shows the execution time of the RSK-Means and SSK-Means algorithms on selected sample sizes and their speedup ratio as mentioned in Figure 3 using K-Means execution time. The execution time of SSK-Means is achieved better than the RSK-Means algorithm on each sample size. The speedup of SSK-Means achieved high scalability and speed as compared to the RSK-Means algorithm on each sample size except for the 10% sample size in the skin dataset. The sample size 15% obtains higher scalability and speed of SSK-Means while compared with other sample sizes in both datasets.

The average execution time of the K-Means, RSK-Means, and SSK-Means algorithms are in Figure 4 that indicates the SSK-Means comments less execution time compared to K-Means and RSK-Means. The proposed SS-based algorithm reduces the execution time without affecting the quality of conventional and random sampling-based algorithms. The SSK-Means reduce the average execution time by 58% and 31% with respect to RSK-Means in the skin and poker datasets, respectively.

The SSK-Means algorithm uses smaller iterations during clustering that reason the SSK-Means algorithm is to reduce the execution time, computation cost, resource consumption, and improve the convergence speed of K-Means. The reported results of Table 5 and the average execution time of Figure 4 indicate that the SSK-Means have achieved better effectiveness and efficiency against the RSK-Means algorithm and comparable to the K-Means. This indicates that the proposed algorithm is straightaway scalable and robust for big data clustering.

CONCLUSION

This study has suggested two strategies to overcome the shortcomings of the sample-based clustering algorithm in the terms of computation time, resource utilization, and quality. The first is known as the EDS method that is used for stratum creation by dividing original data into different strata according to a number of cluster requirements. The second approach is a stratified random sampling-based data mining model for big data (abbr. SS-based data mining algorithm as SSK-Means). The SSK-Means algorithm has been compared to random sampling-based K-Means (abbr. RSK-Means) using SC, DB, CH, ET, and SR validation. The 5%, 10%, 15%, and 20% sample size data objects have been chosen by EDS, sample allocation and stratified sampling. The K-Means partial clustering results of 5%, 10%, 15%, 20% selected sample sizes data have been obtained and merged into 95%, 90%, 85%, 80% un-sample data by sample extension for final results. The SSK-Means obtained a high speedup ratio in a sample size of 15% as compared to other sample sizes and RSK-Means. Experimental studies on real data sets show that the proposed algorithm has superior clustering performance than RSK-Means and conventional K-Means algorithms in terms of efficiency and effectiveness. The SSK-Means achieved better computing time, cluster quality, and efficiency in 15% and 20% sample sizes. Sampling strategies significantly reduce the clustering time on large-scale data, but they may decrease the cluster quality due to small sample size selection. The sample selection, sample allocation, clustering algorithm, and sample extension are based on the stratification process. Therefore, better stratification determines the effectiveness and efficiency of the clustering algorithm. Further scope of the study is to overcome stratification process, sample size selection, sample allocation concerns for excellence cluster effectiveness by validating other internal and external measurements on single or multiple machine-based environments.

CONFLICT OF INTEREST

The authors declare that they have no conflict of interest.