Due to technological advances to massively collect data, the last decades have raised several challenges for data analysis. Data reduction is one of the most important. Typically such reduction can be made in two ways: decrease the number of instances (elements) of the dataset and decrease the number of required attributes (columns) to describe each of these instances. In the last case, methods as Principal Component Analysis (PCA) and Low Variance Filter are usually applied. They are based on statistical measures that allow us to obtain the set of features or attributes with the minimal correlation between them. Since the dataset may have uncorrelated variables that cannot be eliminated, the number of obtained features might not always be appropriate. A dataset with this characteristic may represent a performance problem when there are constraints of time or space. To avoid this, we propose a method that allows us to represent a n-dimensional instance as a numerical data in one-dimensional space. We show that this transformation preserves the properties of the original dataset and thus, it can be suitable for many applications where a high reduction is required.
rst approach]
Multivariate data analysis represents challenges in both theoretical and empirical
levels. Until now, several methods for dimensionality reduction like Principal
Component Analysis [
Based on the above, we assume that the instances of a dataset may be represented by a set of quantiles, which preserves the properties of such instances when several operations are applied. As mentioned, typically the quantiles are de ned over one-dimensional space. We propose a methodology that extends such de nition to n-dimensional space. We want to project every instance of the dataset to its corresponding quantile. Every quantile is identi ed by an unique numerical code. The projection of an instance to its corresponding quantile allows us to obtain the numerical representation of such instance (encoding instances). The set of encoded instances will be the new dataset, we show experimentally that this set preserves the information and properties of the original dataset when several operations are applied.
The rest of this work is organized as follows: In Section 2 we present the main idea about dataset discretization based on quantiles. In Section 3 we explain how to map a data instance into one-dimensional space through its corresponding quantile. Then, in Section 4, we show the experimental methodology to measure the e ectiveness of our method and present the results. Finally, in Section 5 we conclude and mention some future work. 2
Given a dataset Y in a one-dimensional space, we can divide its space into a set of quantiles as it is shown in Figure 1.
In this case, a quantile qi is an interval of the form qi = [yi; yi] where yi and yi are the lower and upper limits of qi respectively. To determine the values of yi and yi a quantile width must be de ned. Such value is given by: = jmax(Y )
min(Y )j N where N is a prior value of the desired number of quantiles. Based on the above, the rst quantile is de ned as a half-closed interval of the form: and the subsequent quantiles are de ned as:
q1 = [min(Y ); min(Y ) + ) qi = ([yi 1; yi 1 + ] if i = N [yi 1; yi 1 + ) otherwise (1) (2)
The idea could be extended to higher dimensional data, in which case, a quantile will be a n-dimensional partition of the data space. In this case, given a dataset Y 2 Rn with instances of the form y = [y1; y2; :::; yn], we can divide the data space into a set of n-dimensional quantiles.
Each n-dimensional quantile is composed by a set of intervals that determine the upper and lower limits for each dimension. Such de nition is expressed as: qi = [[yi1; yi1]; [yi2; yi2]; : : : ; [yin; yin]] where yi;k and yi;k are the lower and upper limit of qi in the kth dimension and the width of each interval is now given by: The variable Yk corresponds to the data in the kth dimension. We can generalize the way to determine the limits of a quantile when Y 2 Rn as: k = jmax(Yk)
N
min(Yk)j 2 [min(Y1); min(Y1) + 1) 3T 6 [min(Y2); min(Y2) + 2) 7 q1 = 664 ... 775 [min(Yn); min(Yn) + n) (4) (5) (6) for the rst quantile, and: > > [y(i 1);n; y(i 1);1 + n] > > qi = < for subsequent quantiles. Note that in general a partial order is formed corresponding to the left-to-right precedence relation where qi < qj if 9k such that yi;k < yj;k, for k n. Thanks to the precedence relation, we can assign to each quantile a numerical code that preserves the partial order. To illustrate the above idea, in Figure 1 the leftmost quantile can be identi ed as 1 while the rightmost quantile can be identi ed as 10. Even any other numerical basis can be used (instead of 10 base), as long as the order is preserved.
Now consider Figure 2 which illustrates a possible encoding of three-dimensional quantiles. The quantile code is formed by combining of the sequence number of the intervals that de ne qi in each dimension. It means, that a three-dimensional quantile encoded as 111 is de ned by the leftmost intervals per dimension. Likewise, a three-dimensional quantile encoded as 333 is de ned by the rightmost intervals per dimension. In such encoding, we can see that the quantile encoded as 113 precedes the quantile encoded as 323. The evident precedence order given in one-dimensional space is preserved in higher order spaces. 3
So far, we have shown how to divide the data space into a set of n-dimensional quantiles. Now, the idea is to map the dataset instances to the quantile to which they belong. Those instances that belong to qi can be represented (encoded) through the code assigned to it. Thus, given a set of quantiles Q de ned from a n-dimensional dataset Y; a one dimensional dataset Y 0; composed only by encoded instances, can be obtained. Table 1 shows a set of quantiles Q for an hypothetical dataset Y 2 R.
Possible instances of Y have been encoded, according to the quantile code to which they belong, as it is shown in Table 2.
From this example the encoded dataset Y 0 is:
Y 0 = f01; 01; 02; 02; 03; 03; 04; 04; 05; 05; 07; 07; 08; 08; 09; 09; 10; 10; 10; 06g (8)
Code Y
Code
The above idea can be extended to n-dimensional case. For instance, let Y be a dataset in R3. Assume that the space of the dataset in the kth dimension (Yk) is divided into ve intervals (for illustrative purposes) where min(Y1) = 1:22, max(Y1) = 1:94, min(Y2) = 1:21, max(Y2) = 2:70, min(Y3) = 1:26 and max(Y3) = 1:12. Also, assume that 1 = 0:64, 2 = 0:78 and 3 = 0:48. In this way, the leftmost quantile is comprised by the intervals set [ 1:22; 0:58); [ 1:21 0:43); [ 1:26 0:78), which correspond to the leftmost intervals per dimension. Using a decimal numerical code of two digits to identify every interval, the corresponding quantile can be encoded as 01 01 01 or merely 010101. In Table 3, this and other quantiles are illustrated including their corresponding boundaries per dimension.
Quantile Code
Y1
Y2
Y3 Given the set of quantiles Q, assume an instance y 2 Y of the form [ 1:15; 0:5; 0:4]. Since this instance lies into the quantile 010103, it can be represented by the quantile code.
Based on this representation process, we can obtain a one-dimensional dataset
denoted as Y 0. Note that the above representation method may involve a loss of
information allegedly depending on the number of quantiles. This value is
implicitly associated to the number of bins in which the space of Yk (the dataset in the
kth dimension) is divided. In this regard, an appropriate selection of this value
is compulsory. Typically, Sturges's rule is used [
Having de ned the way to represent a n-dimensional data, in the next sections we show the experimental results which allow us to con rm that our proposal is promissory. 4
In this section, rst we show in subsection 4.1 some preliminary results of the e ectiveness of our method to preserve the properties of the original dataset in clustering analysis. Subsequently, in subsection 4.2, we evaluate the e ectiveness through a wide sample of systematic experiments that allow us to generalize the results. 4.1
Preliminary Results: preserving clustering properties We applied a non supervised classi cation algorithm over the well known Iris dataset (available at https://archive.ics.uci.edu/ml/datasets/Iris). This dataset (in what follows Yiris) contains 3 classes of 50 instances each, where each class refers to a type of iris plant.
Figure 3 shows the iris data classes obtained by the k-means algorithm for three centers, using Yiris and the encoded dataset Yi0ris. The plot was obtained using the plotcluster function of fpc R module with the default parameters.
Table 4 is the confusion matrix obtained for three classes. We can see that in this case the ratio of well classi ed instances is 80%.
The above results show that the encoded dataset achieves to retain the information conveyed by the original data. However, these results are not enough to generalize this observation. In the following subsection, we present an experimental methodology that allows us to generalize the e ectiveness of our proposal.
Fig. 3: Classi cation of k-means using Yiris vs. encoded dataset Y 0 . iris In order to generalize the above results, we generated a wide set of synthetic datasets (about 5000) in Rn for n = 2; 3; :::100. To generate each dataset, a number of classes was de ned a prior. For each dataset an encoded dataset (based on our proposal) was obtained. Subsequently k-means algorithm is applied to both non-encoded (Y ) and encoded dataset (Y 0). As mention the e ectiveness is given by the percentage matching between the class labels found with Y dataset and the class labels found with Y 0. The average result is shown in Table 5. For completeness, we show the con dence interval of the results with a -value of 0.05.
The experiments show that in average the encoded data allows us to preserve the properties (at least those associated to the proximity of instances) of the dataset in more than 80%. 5
In this paper we have described a method to encode multivariate data. Such encoding, could be interpreted as a data reduction method, in a way that using the codes we are able to apply data mining methods and obtain similar results as using the original data. We applied the reduction method over iris data and results show good performance in classi cation. Also we show that statistically our method achieves to preserve about 80% of information conveyed by the original data.
However, there are some more hypotheses to prove in order to generalize the reduction method. For instance, we suspect that precision in classi cation tasks could improve if a ner number of quantiles is used; more experiments are needed in order to explore this idea. Another future research will be the inclusion of non numerical data types. 6
The authors acknowledge the support of Consejo Nacional de Ciencia y Tecnolog a (CONACyT), Centro de Investigacion y Estudios Avanzados-CINVESTAV and Autonomous University of Tamaulipas.