Attribute Reduction Based on Lift and Random Sampling

Abstract

As one of the key topics in the development of neighborhood rough set, attribute reduction has attracted extensive attentions because of its practicability and interpretability for dimension reduction or feature selection. Although the random sampling strategy has been introduced in attribute reduction to avoid overfitting, uncontrollable sampling may still affect the efficiency of search reduct. By utilizing inherent characteristics of each label, Multi-label learning with Label specIfic FeaTures (Lift) algorithm can improve the performance of mathematical modeling. Therefore, here, it is attempted to use Lift algorithm to guide the sampling for reduce the uncontrollability of sampling. In this paper, an attribute reduction algorithm based on Lift and random sampling called ARLRS is proposed, which aims to improve the efficiency of searching reduct. Firstly, Lift algorithm is used to choose the samples from the dataset as the members of the first group, then the reduct of the first group is calculated. Secondly, random sampling strategy is used to divide the rest of samples into groups which have symmetry structure. Finally, the reducts are calculated group-by-group, which is guided by the maintenance of the reducts’ classification performance. Comparing with other 5 attribute reduction strategies based on rough set theory over 17 University of California Irvine (UCI) datasets, experimental results show that: (1) ARLRS algorithm can significantly reduce the time consumption of searching reduct; (2) the reduct derived from ARLRS algorithm can provide satisfying performance in classification tasks.

1. Introduction

In data processing, as one of the mechanisms to obtain important attributes, attribute reduction has been widely studied. In general, the goal of attribute reduction is to eliminate unnecessary or irrelevant attributes from the raw attributes in light of the given constraint. The remaining attributes are then referred to as a reduct. Then, how to explore attribute reduction has experienced a long development.

In the early stage of exploring attribute reduction [1,2,3,4], the exhausted searching strategies such as the discernibility matrix-based strategy [5,6,7] grew vigorously. Unfortunately, in the age of big data, such time consumption becomes intolerable as data volume grows. This is mostly due to the fact that the majority of exhausted searches are NP-hard issues [8]. For these considerations, various heuristic searching-based strategies have been designed [9]. For example, Liu et al. [10] presented the bucket in the searching process. It can minimize the time necessary to derive reduct by reducing the calculations of distance between samples. Qian et al. [11] proposed an strategy based on positive rough set approximation that may significantly reduce sample size in the searching method. Clearly, both of them are designed from the perspective of samples, which means the searching efficiency is improved by compressing the space of samples.

From this point of view, it is not difficult to confirm that the efficiency of these two strategies depend strongly on the sample distribution. For example, the iterative efficiency of positive approximation decreases when the constrain of attribute reduction is difficult to met. Even the positive approximation will also lose its effectiveness, because the more iterations attribute reduction has, the fewer samples can be removed in each iteration. As far as the bucket is concerned, the samples may all appear in the same bucket in the worst case. In this case, the bucket would be invalid, even redundant, because it is not only necessary to calculate the distance between any two samples, but also requires additional time to obtain the bucket.

In order to reduce the strong influence of sample distribution on attribute reduction algorithm. Chen et al. [12] developed a random sampling accelerator. The first step of random sampling accelerator is to divide the samples into several groups, which can lead to rapid attribute assessment and selection for each group. The second step is to calculate reduct group-by-group based on guidance, which can reduce the search space of candidate attributes. Then, there are fewer candidate attributes to be evaluated, so the calculation process can be accelerated. However, the first group of samples constructed by Chen et al. [12] is still affected by the sample distribution. Even though the size of the first group of samples is much smaller than the entire dataset, there is often overfitting [13,14,15] in the first group, which will inevitably affect the reduction of subsequent groups.

In order to solve the above problem, it is needed to find the most representative samples of different labels to avoid overfitting. Multi-label learning with Label specIfic FeaTures (Lift) [16] has been proved to be effective for above needs. Briefly, Lift algorithm constructs inherent characteristics to every label by conducting clustering analysis on its negative class samples and postive class samples. Therefore, we try to optimize random sampling process by utilization of Lift algorithm, that is, the centers obtained from each cluster are used as the members of first group.

In this paper, the random sampling strategy optimized by Lift algorithm includes three main stages: (1) extract the samples that can best distinguish each label; (2) randomly group the rest of samples in the dataset (the dataset is a finite set of all samples); (3) the samples selected in the first step are trained, and the corresponding reduct is then obtained. For the reduction process of subsequent groups, the reduct of the previous groups is used at the current group to test the classification performance. If the given constraint is met, the reduct of this group will not be calculated. If not, the previously trained samples will be added into current group. Then, it is continued to calculate the reduct of the current group.

In the following, the main contributions of the proposed will be detailed: (1) By using Lift, the influence of sample distribution is further reduced, which speeds up the subsequent reduction and has satisfying classification performance. (2) Through random sampling strategy, the sample volume is reduced to obtain higher time efficiency. In addition to the two advantages mentioned above, it should be noted that our strategy may also be easily integrated with other well-liked strategies. For example, the core frameworks of the bucket and the positive approximation are easily inserted into our construct for increasing the efficiency of searching reducts further.

The remainder of this paper is structured as follows: Section 2 discusses the basic concepts used in this paper. Section 3 describes the optimization of the random sampling strategy by Lift algorithm. Section 4 reports the comparative experimental results and detailed analysis. Section 5 summarizes the contributions of this paper and arranges some further prospects.

2. Preliminaries

2.1. Basic Concept of Rough Set

Usually, a decision system can be described as $\mathcal{DS}=\langle U,AT\cup \left\{d\right\}\rangle$: the universe U is the finite set including all samples; $AT$ is the finite set of condition attributes; d is a label. $\forall x_i\in U$, $\forall a\in AT$, $a\left(x_i\right)$ implies the attribute value of sample $x_i$ over the attribute a, $d\left(x_i\right)$ indicates the label of sample $x_i$. Immediately, if $A\subseteq AT$, then an indiscernibility relation can be given by ${\mathrm{IND}}_A=\{(x_i,x_j)\in U\times U:a\left(x_i\right)=a\left(x_j\right),\forall a\in A\}$ which is also an equivalence relation having reflexivity, symmetry, transitivity. As a result, the construction of classical rough set will be given in the Definition 1.

Definition 1.

Given a decision system $\mathcal{DS}$, $\forall A\subseteq AT,\forall X\subseteq U$, the lower and upper approximations of X related to A are defined as:

$$\underline{R}X=\{x_i\in U:{\mathrm{IND}}_A\left(x_i\right)\subseteq X\};$$

(1)

$$\overline{R}X=\{x_i\in U:{\mathrm{IND}}_A\left(x_i\right)\cap X\ne \varnothing \};$$

(2)

${\mathrm{IND}}_A\left(x_i\right)=\{x_j\in U:(x_i,x_j)\in {\mathrm{IND}}_A\}$ is the set of all samples in U which are equivalent to x in terms of A.

According to Definition 1, the equivalence class ${\mathrm{IND}}_A\left(x\right)$ is the key to construct upper and lower approximations. In general, the process of obtaining ${\mathrm{IND}}_A\left(x\right)$ is known as information granulation in the field of Granular Computing. Although indiscernibility relation is used to perform information granulation in Definition 1, other strategies of dealing with complex data have also been developed, e.g., information granulation based on fuzzy [17,18,19,20], information granulation based on neighborhood [21,22], information granulation based on clustering, information granulation based on strongly connected components [23] and so on [24].

It should be emphasized that the information granulation based on neighborhood is especially accepted in many researching fields. Such a mechanism is not only suitable to mixed data, but also equipped with the natural structure of multi-granularity. The detailed form is given as follows.

Definition 2.

Given a decision system $\mathcal{DS}$, $\forall A\subseteq AT$, $\forall x_i\in U$, the neighborhood ${\delta }_A\left(x_i\right)$ is defined as:

$${\delta }_A\left(x_i\right)=\{x_j:x_j\in U,di{s}_A(x_i,x_j)\le \delta \},$$

(3)

in which $di{s}_A(x_i,x_j)$ indicates the distance between sample $x_i$ and sample $x_j$ in the terms of A, δ is a given radius.

${\delta }_A\left(x_i\right)$ indicates the neighborhood based information granule centered with sample $x_i$ in the terms of A. As a result, Definition 3 can be used to denote the definitions of upper and lower approximations in the neighborhood rough set.

Definition 3.

Given a decision system $\mathcal{DS}$, $\forall A\subseteq AT$, $\forall X\subseteq U$, the neighborhood-based lower and upper approximations of X are defined as:

$$\underline{N}X=\{x_i:x_i\in U,{\delta }_A\left(x_i\right)\subseteq X\};$$

(4)

$$\overline{N}X=\{x_i:x_i\in U,{\delta }_A\left(x_i\right)\cap X\ne \varnothing \}.$$

(5)

Following Definition 3, Approximation Quality (AQ) is a definition of a measure for expressing the degree of approximation in terms of the neighborhood rough set, which will show in the following:

Definition 4.

Given a decision system $\mathcal{DS}$, $\forall A\subseteq AT$, the approximation quality in terms of neighborhood rough set is:

$$AQ\left(A\right)=\frac{\left|\right\{x_i:x_i\in U,{\delta }_A\left(x_i\right)\subseteq {\left[x_i\right]}_d\left\}\right|}{\left|U\right|},$$

(6)

in which ${\left[x_i\right]}_d=\{x_j:x_j\in U,d\left(x_i\right)=d\left(x_j\right)\}$ indicates the label which contains $x_i$.

2.2. Attribute Reduction

At present, not only the amount, but also the dimensions of datasets are quickly increasing. In the realm of rough set, an interesting mechanism known as attribute reduction can efficiently reduce dimension by deleting superfluous attributes. Various kinds of attribute reduction strategies have been described for various needs [25,26,27,28,29,30,31]. However, Yao et al. [22] noted that the majority of them have a similar mechanism. They provided the following general form to clearly express the concept of attribute reduction.

Definition 5.

Given a decision system $\mathcal{DS}$, ${\mathcal{C}}_{\rho }^U$ is a constraint related to measure ρ over the universe U, $\forall A\subseteq AT$, A is referred to as a ${\mathcal{C}}_{\rho }^U$-reduct if and only if the following conditions hold:

(1) 

A meets the constraint ${\mathcal{C}}_{\rho }^U$;

(2) 

$\forall A^{\prime }\subset A$, $A^{\prime }$ does not meet the constraint ${\mathcal{C}}_{\rho }^U$.

In Definition 5, $\rho$ can be regarded as a function such that $\rho$: $P\left(U\right)\times P\left(AT\right)\to \mathbb{R}$, $\mathbb{R}$ is the set of all real numbers, $P\left(U\right)$ and $P\left(AT\right)$ are the power sets of U and $AT$, respectively. For instance, $\forall x_i\in U$ and $\forall a\in AT$, if the lower approximation is employed, then by using a, $\rho (x_i,a)$ = 1 or 0 means that $x_i$ is in or out of the lower approximation. Some typical explanations will be displayed in Example 1 below.

Example 1.

The following two phases can be elaborated.

(1) 

The greater the degree of the constrain obtained by $rho$, the less the level of approximation will be described. One example of such a metric is the definition of approximation quality.

(2) 

The less the degree of the constrain we derived by utilizing $rho$, the less the amount of approximation in the dataset. One example of such a metric is the idea of decision error rate.

Finally, $\forall U^{\prime }\subseteq U,\rho (U^{\prime },A)$ can be considered as a fusion of $\{\rho (x_i,A):\forall x_i\in U^{\prime }\}$, is denoted by

$$\rho \left(U^{\prime },A\right)=\underset{x_i\in U^{\prime }}{⨀}\rho (x_i,A).$$

(7)

In Equation (7), ⨀ is viewed as a fusion operator [32,33] with a variety of forms. In [32], the fusion operator is explained as the averaging operator. In addition, in [33], the fusion operator is explained as the summation operator. As a result, various forms to calculate $\rho (U^{\prime },A)$ can yield various results. For instance, if ⨀ can be demonstrated at ∑, i.e., $\rho \left(U^{\prime },A\right)={\sum }_{x_i\in U^{\prime }}\rho (x_i,A)$, then $\rho (U^{\prime },A)$ can be utilized to determine the degree of approximation quality over $U^{\prime }$.

2.3. Obtaining Reduct

Following Definition 5, the minimal attribute subset is called a reduct which meet the constraint ${\mathcal{C}}_{\rho }^U$. Immediately, it has become a serious challenge how to seek out such the minimum attribute subset. Algorithm 1 depicts a comprehensive procedure of forward greedy searching that can be utilized to determine one reduct.

For every iteration of determing reduct in Algorithm 1, every candidate attribute must be examined. In the worst-case, every attribute in $AT$ is added to the reduct. As a result, the time complexity of Algorithm 1 is $\mathcal{O}\left(\right|U{|}^2·\left|AT{|}^2\right)$.

Even if the Algorithm 1 is successful in obtaining reduct, there are still problems. For instance, if the size of dataset becomes large, the consumption of time to derive reduct will be too extensive. As a result, several researchers have built many strategies from diverse perspectives. All of them have their own disadvantages and advantages. In the next subsection, three strategies built from the perspective of samples will be introduced in detail.

Algorithm 1: Forward Greedy Searching for Attribute Reduction (FGSAR)

2.4. Strategy Based on Sample

The key of strategy based on sample is compression of sample space [34]. These strategies can immediately reduce the number of scanned samples or comparisons between samples. Here are three classical strategies based on the sample.

• Bucket based searching for attribute reduction. Liu et al. [10] have considered the bucket method for fast obtaining reduct. A hash function is used in their technique, and every sample in the dataset will then be mapped into a number of separate buckets. Following the intrinsic properties of such a mapping, only samples from the same bucket must be compared rather than samples from the entire dataset. According to this viewpoint, the computing burden of information granulation may be minimized. As a result, the technique for obtaining reduct by the bucket-based strategy is identical to that of Algorithm 1, except for the device of information granulation.
• Positive approximation for attribute reduction (PAAR). Qian et al. [11] have presented the method based on positive approximation to calculate reduct rapidly. The essence to positive approximation is to compress gradually the sample space. The compressing process should be guided by the values associated with the constrain $rho$. The following are the precise steps of the attribute reduction based on positive approximation.

  (1)

  The hypothetical reduct A will be defined as ∅, as well as the sample compressed space $U^{\prime }$ will be defined as U.

  (2)

  By using the constrain of $\rho \left(U^{\prime },A\cup \left\{a\right\}\right)$, analyse all hypothetical $a\in AT-A$ which in $U^{\prime }$.

  (3)

  Using the acquired constrain, choose one qualified attribute $b\in AT-A$ then merge in b to A.

  (4)

  Based on A, calculate $\rho \left(U^{\prime },A\right)$ and then reanalysis construction of the sample compressed space $U^{\prime }$.

  (5)

  If the specified constraint is met, produce reduct A; otherwise, back to step(2).

• Random sampling accelerator for attribute reduction(RSAR). Chen et al. [12] examined the above-mentioned strategies, they found that: (1) Regardless of the searching technique, information granulation over the entire dataset is required; (2) Information granulation over the dataset always needs to be regenerated in each iteration throughout the entire searching process. In this aspect, sample distribution may influence the effectiveness of searching. Therefore, the two above-mentioned strategies have their own restrictions since they are directly tied to sample distribution. The restriction of BBSAR is that Bucket strategy will become inefficient when sample is too centralized, which is time-consuming. The restriction of PAAR is that the sample distribution strongly affect the construction of positive approximation, and then affect the effectiveness of attribute reduction. In view of this, Chen et al. [12] developed a new random sampling strategy. The following shows the exact structure of the random sampling being used to derive reduct.

  (1)

  The samples were randomly separated to n sample groups of equal size: $U_1,\cdots ,U_n$.

  (2)

  Compute the reduct $A_1$ over $U_1$; reduct $A_1$ will then provide advice for computing the reduct $A_2$ over $U_1\cup U_2$, and so on.

  (3)

  Get the reduct $A_n$, use it as the ultimate reduct over the entire dataset.

RSAR can reduce the influence of sample distribution on attribute reduction to a certain extent. It is well-known that the reduct obtained from a small volume of samples often does not represent the attribute importance of the entire dataset. However, there are two facts in RSAR: (1) the volume of first sample group is frequently much less than the volume of entire dataset; (2) the reduct obtained from the first sample group is used to guide the reduction calculation of subsequent sample groups which have symmetry. These two facts may reduce the efficiency of attribute reduction. As a result, developing an effective attribute reduction strategy to solve the problem is widely valued.

3. Lift for Attribute Reduction

3.1. Theoretical Foundations

This section provides an attribute reduction strategy based on random sampling and Lift [16] which can select a small volume of represented samples from entire dataset. Lift considers that samples with different labels should have their own characteristics, which should be helpful to find samples with high discernibility.

In Lift, given an n-dimensional attribute space, $DL=\left\{d^1,d^2,\cdots ,d^q\right\}$ represents the finite set of q possible labels possessed by all samples. Therefore, the sample space can be expressed as $S=\{(x_i,d_i)\mid i=1,2,\cdots ,m\}$, $x_i$ is a sample with n-dimensional attribute in the dataset, and $d_i\subseteq DL$ represents the label set of $x_i$. In order to extract the characteristics that can best distinguish one label from every other label, the internal relationship between samples under each label will be consider. Specifically, for a label $d^k\in DL$, samples are divided into two categories, the positive class samples set $P_k$ and the negative class samples set $N_k$, as shown in following:

$$P_k=\left\{x_i\mid \left(x_i,d_i\right)\in S,d^k\in d_i\right\};$$

(8)

$$N_k=\left\{x_i\mid \left(x_i,d_i\right)\in S,d^k\notin d_i\right\}.$$

(9)

For the label $d^k$, if one sample possesses this label, the sample will be classified into positive class, otherwise it will be classified into negative class. In order to explore the internal structures of positive and negative classes, k-means [35] clustering is, respectively, carried out on $P_k$ and $N_k$. Since the clustering information of $P_k$ can be regarded as equally important with $N_k$, the number of cluster centers is set as $m_k$, that is:

$$m_k=⌈\delta ·min\left(\left|P_k\right|,\left|N_k\right|\right)⌉;$$

(10)

$|·|$ is the cardinality of set; $\delta \in [0,1]$ is the parameters controlling the number of clusters; the cluster centers of $P_k$ and $N_k$ are recorded as $\left\{p_1^k,p_2^k,\cdots ,p_{m_k}^k\right\}$ and $\left\{n_1^k,n_2^k,\cdots ,n_{m_k}^k\right\}$.

By utilizing the ability of Lift on selecting the represented samples, we try to give a new strategy for deriving reduct:

(1)

Collect all cluster centers into $U_1$.

(2)

The other samples were randomly separated to n − 1 sample groups of equal size: $U_2,\cdots ,U_n$.

(3)

Compute the first reduct $A_1$ over $U_1$; this reduct will then provide advice for computing the second reduct $A_2$ over $U_1\cup U_2$; $A_2$ will also provide advice for computing $A_3$ over $U_1\cup U_2\cup U_3$ and so on.

(4)

Get the n-th reduct $A_n$, use it as the ultimate reduct over the entire dataset.

According to the previous description, it can be seen that the new strategy provides the following advantages. To begin, when the sample distribution information is unclear, Lift is used to select the most representative samples as the first sample group to better guide the subsequent attribute reduction. Then, except the attribute reduction of the first sample group, the sample distribution will no longer affect the efficiency of attribute reduction of other sample groups which have symmetry. Obviously, these two advantages may aid in reducing the time consumption of attribute reduction.

3.2. Detailed Algorithm

In the worst case of the Algorithm 1, it contains two aspects: (1) There is always only one attribute to be added to the reduct in the each iteration; (2) The final reduct contains all attributes in the dataset. After that, the following will show the time complexity of Algorithm 2.

Remark 1.

The time complexity of Algorithm 2 is $\mathcal{O}\left((\frac{1}{n}{\left|U\right|)}^2·S_1^2+(\frac{2}{n}{\left|U\right|)}^2·S_2^2+\cdots +(\frac{n}{n}{\left|U\right|)}^2·S_n^2\right)$, i.e., $\mathcal{O}\left(\frac{{\left|U\right|}^2}{n^2}·{\sum }_{i=1}^n(i^2·S_i^2)\right)$. For such complexity, n refers to the amount of sample groups, $S_n$ indicates the amount attributes ought to be included in the reduct for every iterations, thus ${\sum }_{i=1}^n{S}_i=S_1+S_2+\cdots +S_n=\left|AT\right|$. As a result, it is simple to arrive at the following conclusions:

$$\begin{array}{ccc}& & \mathcal{O}\left((\frac{1}{n}{\left|U\right|)}^2·S_1^2+(\frac{2}{n}{\left|U\right|)}^2·S_2^2+\cdots +(\frac{n}{n}{\left|U\right|)}^2·S_n^2\right)\hfill \\ & & =\mathcal{O}\left(\frac{{\left|U\right|}^2}{n^2}·\sum _{i=1}^n(i^2·S_i^2)\right)\hfill \\ & & \le \mathcal{O}\left(\frac{{\left|U\right|}^2}{n^2}·\sum _{i=1}^n(n^2·S_i^2)\right)\hfill \\ & & =\mathcal{O}\left({\left|U\right|}^2·(\sum _{i=1}^n{S}_i^2)\right)\hfill \\ & & \le \mathcal{O}\left({\left|U\right|}^2·{(\sum _{i=1}^n{S}_i)}^2\right),\hfill \end{array}$$

i.e., $\mathcal{O}(\frac{{\left|U\right|}^2}{n^2}·{\sum }_{i=1}^n(i^2·S_i^2))\le {\mathcal{O}\left(\right|U|}^2·{\left|AT\right|}^2)$.

Algorithm 2: Attribute Reduction Based on Lift and Random Sampling

In this section, according to the above strategy, an attribute reduction algorithm called ARLRS is proposed as Algorithm 2. In ARLRS, Lift algorithm is used to choose the samples from the dataset as the members of the first group, and random sampling strategy is used to divide the rest of samples into groups. Generally, the reduct of the first sample group is calculated quickly by Algorithm 1. For every subsequent sample group, if the given constrain is satisfied, the attribute reduction calculation of current sample group can be skipped; if the given constrain is not satisfied, the previous sample groups are integrated into the current sample group, then attribute reduction calculation of this integrated group is carried out. As a result, by gradually integrating many previous sample groups, the classification performance of the temporary reduct over the current sample group will be improved until the attribute reduction constrain is met.

4. Analysis of Experiment

4.1. Datasets

To illustrate the effectiveness of the proposed ARLRS algorithm, 17 UCI datasets were chosen for the tests. The UCI datasets is a collection of databases, top level theory, and data generators used by the machine learning to conduct empirical evaluations of machine learning algorithms. David Aha and his fellow graduate students at UC Irvine established the archive as an ftp archive in 1987. Since then, it has been widely used as a key source of machine learning datasets by students, instructors, and researchers all over the world. All the datasets this paper used were download on: https://archive.ics.uci.edu/ml/datasets.php (accessed on 12 January 2022). The

Table 1. Datasets used in the experiment.

ID	Datasets	# Samples	# Attributes	# Labels	Attributes Type
1	Australian Credit Approval [36]	690	14	2	Real
2	Breast Cancer Wisconsin (Diagnostic) [37]	569	30	2	Real
3	Cardiotocography [38]	2126	21	10	Real
4	Connectionist Bench (Sonar, Mines vs. Rocks) [39]	208	60	2	Real
5	Crowdsourced Mapping [40]	10,845	28	6	Real
6	Diabetic Retinopathy Debrecen [41]	1151	19	2	Integer & Real
7	DrivFace [42]	606	6400	3	Real
8	Forest Type Mapping [43]	523	27	4	Integer & Real
9	Glass Identification [44]	214	9	6	Real
10	Ionosphere [45]	351	34	2	Integer & Real
11	MAGIC Gamma Telescope [46]	19,020	28	6	Real
12	Parkinson Multiple Sound Recording [47]	1208	26	2	Real
13	QSAR Biodegradation [48]	1055	41	2	Real
14	Musk (Version 1) [49]	476	166	2	Integer
15	Page Blocks Classification [50]	5473	10	5	Integer & Real
16	Urban Land Cover [51]	675	147	9	Integer & Real
17	Quality Assessment of Digital Colposcopies [52]	287	62	2	Real

contains full descriptions of 17 datasets. All experiment were conducted on a personal computer running Windows 10, with an Intel Core i7-6700HQ CPU (2.60 GHz) and 16.00 GB of RAM. Matlab R2019b is the programming language. In order to further analyze the advantages of ARLRS algorithm, the experiment will be shown in two aspects: time consumption and classification performance.

4.2. Basic Experiment Setting

In this paper, the neighborhood rough set [53,54,55,56,57,58] was used as the model for deriving reducts. It should be noted that the computational results of the neighborhood rough set are heavily reliant on the radius chosen, and we pick 0.2 as our radius to illustrate the generality of ARLRS algorithm. Moreover, the concept of approximation quality (Equation (6)) is selected as the constrain of ARLRS algorithm. The approximation quality describes the ability of the approximation in terms of attribute reduction. In general, the higher the degree of approximation quality is, the better performance the selected attribute has.

Five classical algorithms are chosen to compare with the proposed ARLRS algorithm. The four algorithms of them have been introduced detailed in previous context of this paper, that are FGSAR [59,60,61], BBSAR [10], PAAR [11] and RSAR [12]. The fifth compared algorithm is the Attribute Group for Attribute Reduction (AGAR) [62]. AGAR is also a sample based algorithm and has excellent time efficiency and classification performance. Adding AGAR to the comparison can better help us test the performance of ARLRS algorithm.

4.3. Time Consumption

In this subsection, the time consumption of five compared algorithms (FGSAR, BBSAR, PAAR, RSAR and AGAR) and ARLRS algorithm on computing reducts are listed in

Table 2. The time consumption (unit is second) of six attribute reduction algorithms.

ID	ARLRS	RSAR	FGSAR	PAAR	BBSAR	AGAR
1	1.3439	1.6046	1.9683	1.9533	3.0378	2.0001
2	2.8514	3.2616	3.7553	3.6474	4.9878	6.3496
3	1.7156	2.3740	3.6215	3.3452	4.0248	2.6923
4	3.114	3.8712	4.6534	4.4532	4.9458	6.3526
5	0.0331	0.0351	0.3561	0.3424	0.4138	0.0493
6	1.5043	1.6542	3.3462	3.3977	2.7745	3.4527
7	21.5071	21.6074	22.9543	22.6464	32.7441	24.2342
8	3.2707	4.9173	10.2732	10.2480	4.4253	4.5429
9	36.6825	39.9173	55.4524	54.2809	46.355	40.6939
10	2.2156	2.3740	3.5643	3.5754	4.0248	2.5551
11	32.6542	34.7645	35.3475	35.3342	35.4578	34.9578
12	2.5127	2.7545	3.1642	3.0008	2.8361	3.147
13	9.6467	11.9454	13.6468	13.4522	12.5647	12.3949
14	16.9655	18.3361	19.7468	19.2312	19.1485	18.5435
15	44.4554	46.1265	48.4641	48.8529	45.5659	48.4844
16	3.6125	4.0415	4.8353	4.1237	4.7264	4.9645
17	38.4124	41.5415	43.8515	43.4529	45.4554	44.5455

. For every dataset, the best time consumption is bold.

Table 2 shows that ARLRS performs admirably on time consumption compared to the other five classical algorithms. Using the “QSAR Biodegradation” (ID 13) dataset as an example, the time consumptions of RSAR, FGSAR, PAAR, BBSAR and AGAR are 11.9454, 13.6468, 13.4522, 12.5647 and 12.3949 seconds, respectively. The proposed ARLRS algorithm only takes 9.6467 seconds. Obviously, ARLRS algorithm has the ability to remarkable accelerate the process of computing reduct.

To further demonstrate the superiority of ARLRS algorithm, the speedup ratios of ARLRS algorithm against the five compared algorithms (FGSAR, BBSAR, PAAR, RSAR and AGAR) are shown in

Table 3. The speed up ratio of five compared algorithms to ARLRS.

ID	RSAR	FGSAR	PAAR	BBSAR	AGAR
1	16.37	31.19	41.17	30.34	32.81
2	12.58	24.07	21.82	20.53	19.31
3	27.73	35.12	27.82	18.21	26.34
4	19.63	33.14	30.13	25.75	7.22
5	2.36	23.38	2.65	2.71	17.78
6	9.06	14.64	42.91	34.52	27.98
7	13.15	19.01	18.62	4.57	5.99
8	8.11	33.85	32.42	34.91	9.86
9	20.13	37.84	38.03	24.24	13.29
10	10.23	11.09	22.97	23.13	30.23
11	6.07	7.02	7.88	7.91	6.59
12	25.97	20.59	16.27	11.40	20.16
13	19.24	9.39	7.71	23.22	22.17
14	25.09	18.28	13.71	12.93	6.77
15	3.62	8.27	6.00	2.44	8.31
16	15.23	13.88	14.76	17.84	20.76
17	31.25	4.33	6.12	7.32	15.9
avg	15.63	20.29	20.64	17.79	17.14

and the lengths of reducts produced by overall six algorithms are shown in

Table 4. Reduct lengths of six algorithms.

ID	ARLRS	RSAR	FGSAR	PAAR	BBSAR	AGAR
1	7.14	7.32	8.03	8.03	8.03	7.17
2	8.67	8.21	9.19	9.19	9.19	8.11
3	7.38	8.66	7.57	7.57	7.57	8.45
4	7.13	7.43	8.17	8.17	8.17	7.43
5	14.34	15.32	14.38	14.38	14.38	16.64
6	9.46	9.21	8.32	8.32	8.32	8.76
7	8.74	9.87	7.15	7.15	7.15	9.75
8	8.65	9.07	9.25	9.25	9.25	8.98
9	7.91	9.87	8.57	8.57	8.57	8.07
10	8.65	8.97	8.78	8.78	8.78	9.21
11	23.87	24.58	25.32	25.32	25.32	27.98
12	7.03	10.34	10.01	10.01	10.01	9.28
13	6.98	9.01	8.34	8.34	8.34	7.32
14	8.75	8.65	8.90	8.90	8.90	10.76
15	13.66	15.32	16.24	16.24	16.24	15.23
16	14.31	15.09	15.65	15.65	15.65	16.32
17	8.02	8.06	8.19	8.19	8.19	9.15

. It is worth mentioning that FGSAR and PAAR have similar mechanism, so their reduct lengths have symmetry. For every dataset, the shortest length of reducts produced by six algorithms is set bold.

According to Table 3, all speedup ratios of ARLRS algorithm against other five classic sample based algorithms are substantially greater than 1. Even that average speedup ratio approaches 15. These findings show that the proposed ARLRS algorithm can speed up the process of computing reducts from datasets. Furthermore, Table 4 shows that in the most of datasets, the lengths of reducts generated by ARLRS are substantially shorter than those acquired by the other five algorithms. The reducts with shorter length often indicate that ARLRS needs fewer iterations to get the reducts with satisfying classification performance. From this viewpoint, it also shows that ARLRS can effectively reduce the time consumption of attribute reduction.

Among the above six attribute reduction algorithms, ARLRS and RSAR are designed both based on random sampling. It is not difficult to find that for the two algorithms with the similar mechanism, ARLRS algorithm has obvious advantage on the time consumption. Especially on high-dimensional datasets such as “Musk (Version 1)” (ID 14), “DrivFace” (ID 7), “Quality Assessment of Digital Colposcopies” (ID 17) and “MAGIC Gamma Telescope” (ID 11), ARLRS algorithm performs particularly well. In order to better show the advantage of ARLRS algorithm on high-dimensional datasets, Figure 1 shows the time consumption over these four datasets. Obviously, the time consumption of ARLRS is less than that of RSAR over the four high-dimensional datasets.

It is worth mentioning that ARLRS will filter out the samples with low representation, then only evaluate the samples with most representation. The filtration process leads to reduce greatly the time consumption of samples evaluation in the process of attribute reduction. Therefore, comparing with other attribute reduction strategies, the proposed ARLRS algorithm has better performance in time consumption.

4.4. Classification Performance

K-Nearest Neighbor (KNN, K parameter will be set as 3) and Support Vector Machine (SVM) classifiers are used to test the classification accuracies of different reducts produced by six algorithms. The average values of the classification accuracies of generated reducts are provided in

Table 5. Based on KNN classifier, the classification accuracies of reducts produced by six attribute reduction algorithms.

ID	ARLRS	RSAR	FGSAR	PAAR	BBSAR	AGAR
1	0.8555	0.8742	0.8168	0.8168	0.8557	0.9175
2	0.9785	0.9000	0.8534	0.8534	0.9347	0.9456
3	0.9399	0.9320	0.8824	0.8824	0.8356	0.8943
4	0.9569	0.9642	0.8074	0.8074	0.9741	0.9456
5	0.8848	0.8351	0.8022	0.8022	0.8149	0.8624
6	0.8449	0.8272	0.9074	0.9074	0.8736	0.8488
7	0.9089	0.9003	0.8075	0.8075	0.8572	0.8197
8	0.8437	0.8326	0.8731	0.8731	0.8186	0.8279
9	0.8441	0.8741	0.8507	0.8507	0.9117	0.7986
10	0.9575	0.9320	0.9269	0.9269	0.8356	0.8943
11	0.9145	0.8487	0.8366	0.8366	0.8869	0.8747
12	0.9035	0.9055	0.9266	0.9266	0.8845	0.8647
13	0.8364	0.8641	0.8644	0.8644	0.9153	0.8279
14	0.9634	0.9534	0.9128	0.9128	0.8934	0.8634
15	0.9314	0.9169	0.8674	0.8674	0.8467	0.8469
16	0.9299	0.9064	0.8796	0.8796	0.9074	0.8534
17	0.8036	0.8712	0.8642	0.8642	0.8541	0.8779

and

Table 6. Based on SVM classifier, the classification accuracies of reducts produced by six attribute reduction algorithms.

ID	ARLRS	RSAR	FGSAR	PAAR	BBSAR	AGAR
1	0.8396	0.8614	0.8318	0.8318	0.8496	0.8779
2	0.8984	0.8401	0.8302	0.8302	0.7121	0.7326
3	0.8351	0.8741	0.9164	0.9164	0.8813	0.8801
4	0.8433	0.8381	0.8041	0.8041	0.8701	0.8912
5	0.9103	0.8701	0.9328	0.9328	0.9488	0.8468
6	0.9434	0.9362	0.9723	0.9723	0.9356	0.9147
7	0.8841	0.8766	0.8452	0.8452	0.8141	0.7998
8	0.8321	0.8311	0.9723	0.9723	0.7318	0.7323
9	0.9194	0.9248	0.9049	0.9049	0.8722	0.8413
10	0.8954	0.8888	0.7763	0.7763	0.8052	0.7113
11	0.9165	0.8971	0.9460	0.9460	0.8741	0.8492
12	0.9365	0.9207	0.9194	0.9194	0.8279	0.7812
13	0.9153	0.8803	0.7436	0.7436	0.7799	0.8940
14	0.8915	0.8766	0.8622	0.8622	0.8348	0.8786
15	0.9255	0.8903	0.8802	0.8802	0.8584	0.9205
16	0.9044	0.8909	0.8633	0.8633	0.8261	0.8759
17	0.8759	0.9204	0.8816	0.8816	0.9362	0.8294

. It is worth mentioning that FGSAR and PAAR have similar mechanism, so the classification performance of them have symmetry. For every dataset, the best classification accuracy is bold.

According to Table 5 and Table 6, ARLRS’s classification performance is somewhat greater than the other five algorithms. Especially for high-dimensional dataset “DrivFace” (ID 7), the classification accuracies of proposed ARLRS are 0.9089 on KNN classifier and 0.8841 on SVM classifier, respectively, which perform better than other five algorithms. As a result, regardless of which two classifiers are utilized, the reducts obtained from ARLRS deliver satisfying classification performance.

It is because Lift can filter out samples with low representation, some candidate attributes will be deleted after the attribute reduction of the first sample group. The subsequent reduction process can receive better guidance for selecting attributes with better classification performance. This mechanism enables the attribute reduction process to focus on attributes with most representation. This is why the classification performances of reducts produced by ARLRS can be satisfying.

4.5. Discussion

In the above experimental analysis, it can be concluded that ARLRS algorithm often performs well in big data, both in terms of time consumption and classification performance, for this conclusion, the following reasons can be given.

(1)

The higher the dimension of the datasets is, the more information the selected sample can carry. Then, the more information can better help to guide the subsequent attribute reduction. Therefore, ARLRS algorithm performs well in handling big data.

(2)

Due to the low value density of big data, it is often necessary to preferentially extract relevant and useful information from a large amount of datasets. The above-mentioned needs are well solved by introducing Lift. The most representative samples found by LIFT make the unclear information under each label have available structure, from the perspective of samples, thus different samples form a certain association. Such preprocessing is very effective in the processing big data, so ARLRS will have certain advantages in processing big data.

5. Conclusions and Future Perspectives

This paper combines Lift with random sampling strategy to proposed an attribute reduction algorithm call ARLRS. The utilization of Lift reduces the impact of overfitting in the first sample group, which can produce the reduct being able to provide better guidance for subsequent attribute reduction. The retainment of random sampling strategy is helpful to reduce the impact of sample distribution. Due to the fact that Lift can mine the samples with most representation, the proposed ARLRS algorithm also has satisfying results in classification performance. The experimental results over 17 UCI datasets show that the above conclusions are effective and credible.

The following research directions will be of great value as our next work.

(1)

In light of the uncertainty existed in constraints and classification performances, the resultant reduct may result in over-fitting. As a result, in future investigation, we will try balance the efficiency of attribute reduction with the classification performance.

(2)

The attribute reduction strategy presented in this research is only applied from the sample’s perspective. Therefore, we will try to investigate some novel algorithms taking into account both samples and attributes for improving more efficiency.