{'fraction_non_alphanumeric': 0.0282024926121033, 'fraction_numerical': 0.008736990877553643, 'mean_word_length': 4.919011406844106, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Unsupervised Feature Selection Based on Space Filling Concept

The paper deals with the adaptation of a new measure for the unsupervised feature selection problems. The proposed measure is based on space filling concept and is called the coverage measure. This measure was used for judging the quality of an experimental space filling design. In the present work, the coverage measure is adapted for selecting the smallest informative subset of variables by reducing redundancy in data. This paper proposes a simple analogy to apply this measure. It is implemented in a filter algorithm for unsupervised feature selection problems. The proposed filter algorithm is robust with high dimensional data and can be implemented without extra parameters. Further, it is tested with simulated data and real world case studies including environmental data and hyperspectral image. Finally, the results are evaluated by using random forest algorithm.


Introduction
In recent years, the techniques of collecting environmental data (such as: wind speed, permafrost, rainfall, pollution . . .) have been improved. Moreover, environmental phenomena are mostly: non-linear, multivariate, and in many cases they are studied in high dimensional feature spaces [1]. Usually, the input space is constructed by considering available information and expert knowledge.
The empirically designed input feature space can gain rapidly a high dimension.
In addition to the original features, there is always redundancy in the input data. In fact, the data points are not uniformly distributed in the experimental domain in which the data are embedded. In other word, the data space is not well filled or covered in the presence of redundancy. Consequently, the modelling of these data could take much time when introducing all features. Such problems are known as the curse of dimensionality.
To overcome this issue, feature selection (FS) algorithms play an important role in data driven modelling. Therefore, numerous methods and measures for FS have been proposed [2,3]. The main purpose is to retain only features that bring new and relevant information by reducing the existing redundancy in data. This procedure helps to manage the curse of dimensionality. In fact, it improves the accuracy of modelling, speeds up the learning process, and offers a good interpretation of the results.
The literature of machine learning distinguishes two well-known techniques of FS, according to the availability of the output variable: supervised and unsupervised feature selection [4,5,6,7]. These techniques try to find the smallest informative subset of features regarding to a defined measure or criterion.
Other methods are available, such as feature ranking [8,9], which consists in giving an order to features regarding their importance. Then, a learning process to choose how many features can be selected usually follows these methods.
In the unsupervised methods, the goal is mainly to carry out an exploratory analysis and to improve the discovering of hidden pattern. Therefore, the techniques of unsupervised feature selection (UFS) [16,17,18] do not require a prior information (output variable). They try to minimise existing redundancy, which leads to a reduction of dimensionality of data. Further, UFS techniques improve the understanding, the visualisation, and the interpretation of the results. In short, the dimensionality reduction consists in choosing a subset of features that contain new and relevant information about the data. This paper is an adaptation of a new measure based on space filling concept, which is called the coverage measure. It was mainly used in experimental designs [19,20]. Moreover, the proposed measure was used also for the construction of spatial coverage designs in [21], which proposes its implementation in Splus.
Other implementation for the spatial coverage is available in the R library spcosa proposed in [22]. The DiceDesign R library proposes an implementation of this measure, in the context of space filling design [23].
The coverage measure is adapted here for the UFS problems. It can be implemented in all search techniques such as exhaustive search [24] , sequential forward selection (SFS) [25], and sequential backward selection [26] (SBS). In this work, it is considered with a SFS technique.
The proposed measure computes how well the space is covered by the data points. In fact, it quantifies the uniformity of points in a hypercube by comparing the repartition of points to a regular grid [19]. The smallest coverage value means that the hypercube is well filled. Intuitively, the coverage measure gives zero value or near to zero if the data points are distributed as a regular grid, or near to be a regular grid, in the data space.
The analogy is quite simple and clear, the selected features have to fill uniformly all the space in which the data are incorporated. In fact, the repartition of points expresses the information amount disseminated. Therefore, the smallest value of coverage means that the variables cover well the space in which they are embedded. Moreover, the selected variables should contain new and relevant information about the data.
A filter algorithm is used to implement the coverage measure. It is applied on simulated dataset and on several well-known benchmark datasets used for feature selection purpose. In addition, real environmental data are used as well.
Further, the algorithm is tested with different scenarios of noise injection and shuffling data. Then, the results are verified and evaluated with random forest algorithm [27,28] by using a consistent methodology.
The remainder of this paper is organized as follows. Section 2 explains the coverage measure and its use in experimental designs. Section 3 presents the implementation of this measure for the UFS problems and introduces the corresponding filter algorithm. In section 4, the measure is evaluated by several datasets. In the last section, the conclusion is given with future developments.

Definition and basic notions
Design and modelling of experiments have always been a fundamental approach over the years. The experimenter has to propose and choose the suitable factor space (i.e. experimental domain) for the experiment under study. The most important early step to check is the coverage or the uniformity of the proposed design. There are many ways to select the best design regarding several conditions and criteria [29].
Numerous space filling design have been proposed under some prior properties. They can be constructed by using algebraic methods: based on incomplete block resolvable design [29], based on association schemes [30]. The construction algorithms were as well considered in [31,32,33]. Other high quality designs, based on space filling concept, were proposed in [34,35,36]. Furthermore, different measures for choosing the best design have been given in [37,38,39,40].
In the literature of sampling methods, one strategy is to generate randomly different designs. Then, a comparison is carried out using a defined measure to find the best design. Another approach can be on the extension of an existing design. The objective is to add more points in the sampling design by taking into account the prior defined measure.
Other strategies in choosing the best design is to adopt some optimality criterion, such as: • The entropy criterion [41,42], which has been widely used in coding theory and statistics. The Shannon entropy measures the amount of information contained in the distribution of a set of points. In [42] it is described as the classical idea of the information amount in an experiment. Moreover, it is proposed with a linear model (a simple Kriging model), and presents the corresponding maximum entropy designs.
• The integrated mean squared error [43], which is computationally more demanding and needs a powerful optimisation algorithm due to the large combinatorial design space. This criterion can be replaced by the maximum mean squared error involving a multidimensional optimisation [44].
• Minimax or Maximin distance criteria, proposed in [45], which measure Besides, several uniformity measures have been proposed in [29]. The most known is the discrepancy. Numerous kinds of discrepancies have been defined such as: the star discrepancy, the centred L 2 -discrepancy, and wrap-around L 2discrepancy. These uniformity criteria are based on the Kolmogorov-Smirnov test. In fact, it compares the design to a uniform distribution.
In addition to the discrepancy, the coverage measure was also proposed to quantify the uniformity. In contrast to the discrepancy, the coverage measure compares the proposed design to a regular grid. Furthermore, the coverage measure is more stable than the discrepancy in a high dimensional design. Therefore, it can be applied to high dimensional data.

Coverage measure
The coverage measure is defined as follows: is the minimal distance between x i and the other points of the sequence. And: If the data points are distributed as a regular grid: Hence, λ = 0 The quality coverage of points can be detected by using the minimum euclidean distance between the points. Further, it takes into account the dispersion of distances. In fact, the coverage measure λ makes appear the coefficient of variation of the ϑ i , which is known as the relative standard deviation (the ratio of the standard deviation to the mean of ϑ i ).
The smaller the value of λ is, the smaller the distance between the points is. In this case, the design is near to be a regular grid. The best design should have the smallest coverage value λ. Figure 1 shows the capability of the coverage measure to compute and quantify the filling of space. Therefore, the use of such measure helps to find the best experimental design regarding the distribution of points.
From this point of view starts the adaptation idea of this measure for the unsupervised feature selection problems. Furthermore, the simplicity of this measure offers a good implementation in a filter algorithm for selecting variables.
It is important to note that the results giving by this measure are acceptable regarding the selection of the informative feature subset. In addition, it can make use of a parallel CPU computing and a GPU computing to speed up the search procedure.  Dataset D with d features X 1,...,d .

Empty vectors IdR and CovD
Output: IdR and CovD respectively, the features id and the coverage values. The lowest value of λ is stored in CovD[j] 7: The corresponding id of the lowest λ is stored in IdR[j] 8: end for

Experimental case studies
The simulated and the real world datasets presented in this section are commonly used in several papers on machine learning and feature selection. Moreover, several scenarios of noise injection and shuffling data are proposed to evaluate and to explore the limitation of the UfsCov algorithm.
Further, this section discusses the quality of the obtained results. Finally, the results are verified and evaluated by using random forest algorithm.

Simulated case study
The simulated Butterfly dataset, introduced in [46], is composed of 8 features

Noise injection
The robustness of UfsCov is evaluated against noise. In fact, several experiments of noise injection were performed for two different scenarios. The first one consists in injecting noise to all features of the Butterfly dataset. The second one consists to corrupt only the redundant features (J 3 , J 4 , J 5 , I 7 , I 8 ). A Gaussian noise is used with a mean fixed at 0 and a standard deviation set at: 1%, 5%, 10%, 20%, and 50% of the original standard deviation of feature.    (see table 1).
Therefore, it can be concluded that the UfsCov algorithm is robust against noise.

Benchmark case studies
Benchmark case studies [47,48] are also used to test the UfsCov algorithm.
The datasets used in this work are: Parkinson, PageBlocks, Ionosphere, and COIL20 [48]. Table 3 describes these datasets and the number of selected features for each dataset.

Results and discussions
In addition to applying the UfsCov algorithm on simulated and real world datasets, this subsection discusses the evaluation of the results. Here, random forest algorithm is used as a classifier for the four datasets used above (Parkin-  son, PageBlocks, Ionosphere, and COIL20).
The used procedure of testing with random forest is applied once with all features of the datasets and once with only selected features. The procedure can be summarised as follows: • the data were split into training and testing sets (80% for training and 20% for testing); • the training set was used to find the optimal parameters of random forest (the number of trees and the number of predictors). Furthermore, the training step was performed by using a 10-fold cross-validation; • a random forest model was generated with the optimal parameters found above (previous step), and then applied to classify the testing set. Two classification evaluation metrics are used: -the overall accuracy of classification is computed with the following formula: whereŷ i is the predicted class label for the ith observation using the random forest model. And I(y i =ŷ i ) is an indicator variable with: Therefore, the OA formula computes the fraction of correct classifications, which means that the best classification has the highest overall accuracy.
-Cohen's Kappa coefficient k [49] is also used to compare the classification results of random forest. The Kappa evaluation metric is computed on the test subset by using the following formula:

Environmental case studies
This section shows the potential of the proposed unsupervised feature selection algorithm on environmental data. In fact, the algorithm is applied on Permafrost data and the Indian Pines hyperspectral image.

Permafrost case study
The data were collected in the Alp Mountains of Switzerland. 26 features (excluding the XY coordinates) are used to predict Permafrost presence or absence. For more details on the study, including more complete references and more information about the collected features, see N. Deluigi et al. [50].   case study of hyperspectral image shows that the UfsCov algorithm is able to deal with remote sensing problems. Furthermore, the proposed algorithm help to manage high dimensional datasets (more than 100 features). Figure 11 shows the results of the proposed algorithm. The minimum value is reached with the 69 features. Table 7 compares the difference between the two random forest models, with all features and with only the selected features.

Conclusion
The research introduced a space filling measure for the unsupervised feature selection problems. A new filter algorithm considered is based on the coverage measure. The proposed UfsCov algorithm minimises redundancy in data. The proposed algorithm showed its efficiency by testing on simulated and real world case studies including environmental data. Random forest results confirm the potential of space filling concept in the unsupervised feature selection problems.
Finally, the UfsCov was programmed in R language and will be available on the CRAN repository in the SFtools library.
Future development could be in the adaptation of new measures based on space filling concept for machine learning use and data mining. Furthermore, it could be important to propose algorithms with a parallel CPU computing version and GPU computing to speed up the execution time.

Acknowledgements
Golay, and Fabian Guignard for fruitful discussions about machine learning.