Feature selection, defined as the automatic selection of the most relevant features from a machine learning dataset, has three objectives: to improve the prediction performance of the predictors, to provide faster and more cost-efective predictors, and to ofer a better understanding of the underlying process that generated the data. In the case of dimensional (e.g., temporal or spatial) data, feature selection is often approached using standard methods that neglect or denature the dimensional component. This paper provides a first step towards systematic and general dimensional feature selection, with a portfolio of supervised and unsupervised, filter-based selectors that can be naturally combined into an end-to-end methodology. In a hypothesis-testing setting, our experiments show that our approach can extract provably relevant features in both the temporal and spatial cases.
CEUR ceur-ws.org
CEUR Workshop Proceedings
Feature selection methods can be classified into filter, wrapper, embedded and hybrid
methods [
In the era of big data, more-than-tabular data embodies 95% of all existing data [
Learning from temporal and/or spatial datasets has been primarily accomplished with
subsymbolic techniques, specifically neural networks; the current literature on this topic is too
wide to be reviewed here. Recently, however, symbolic learning in both the temporal and the
spatial case has started to be systematically explored. Among several examples, for the temporal
case we mention [
Let a tabular instance, also referred to as adimensional instance, be an object of the type = ( 1, … , ) where ∈ ℝ, for each 1 ≤ ≤ . Each value is the value for a variable, whose name is denoted by ; in the following, we identify variables with their names. A tabular dataset (or adimensional dataset) is, therefore, a collection ℐ = { 1, … , } of tabular instances whose values are taken from a set of variables = {
1, … , }. Tabular datasets can be also labelled if each instance is associated to a unique label from a set ℒ = { 1, … , }.
Tabular datasets are classic, scalar datasets as they are usually defined in data science and machine learning; note that categorical variables can always be transformed into scalar ones via one-hot encoding. Tabular datasets, however, are a particular case of dimensional ones. A -dimensional instance is an -tuple of functions = ( 1, … , ), each defined as ∶ ℕ → ℝ, and a -dimensional dataset a collection ℐ = { 1, … , } of -dimensional instances each possibly associated to a unique label. The notion of -dimensional dataset generalizes tabular datasets (when = 0 ), as well as datasets of time series ( = 1 ), images ( = 2 ), and videos ( = 3 ), among others. In a -dimensional instance too, a variable (function) has a name . In the following, we restrict ourselves to the case of finite datasets, in which we have exactly distinct points in every dimension.
Information extraction from -dimensional data occurs via using a predetermined set of feature extraction functions ℱ = { 1, … , }. Each function is abstractly defined as ∶⋃ℝ 1 × … × ℝ → ℝ.
1≤ 1,…, ≤ Examples are the generalized mean, maximum and minimum, but ℱ may include more elaborate examples whose concrete definition may depend on the relative order of values; an example in this category in the case = 1 could be the number of local maxima in a given interval of values. A function is applied to a variable to generate the feature ( ) .
There are many possible logical representations for a -dimensional dataset. A very natural one is inspired by both the interval temporal logic ℋ [15] and the Rectangle Algebra [16], which, in turn, can be immediately generalized to the case of -dimensions. Let be an initial prefix of ℕ of cardinality , and let its corresponding -dimensional generalization. Let
⟨⟩ (after) ⟨⟩ (later) ⟨⟩ (begins) ⟨⟩ (ends) ⟨⟩ (during) ⟨⟩ (overlaps) [, ] vertical axis). A hyperinterval is a set the ( − 1) -dimensional discrete space passing through the -th point of the -th component of and whose normal is non-null only on that component (e.g., when = 1 , 1 is simply the -th point; when = 2 , 1 is the straight that goes through the -th point and is parallel to the = {( 1
1 , ℎ1ℎ 1), … , ( , ℎℎ )} where
≤ , for each 1 ≤ ≤ . Thus, this notion simply generalizes the one of interval in one dimension. Describing a hyperinterval is easily achieved via a -tuple of pairs of natural numbers such as
= [( 1, 1), … , ( , )], where the -th component corresponds to the -th dimension, and, as before, ≤ , for each 1 ≤ ≤ . A notion of a point belonging to a hyperinterval, denoted by ( 1, … , ) ∈ , emerges naturally. Given the 13 so-called Allen’s relations that allow one to qualitatively describe the geometric arrangement between any two intervals in a linear order, whose notation and informal semantics is depicted in Tab. 1, it is immediate to generalize such relations to the case dimensions (see Fig. 1). of hyperintervals. Thus, given any two hyperintervals , exactly one hyperinterval relation 1… , where ∈ = {, ′, they are related to each other by , , , , , , , , , , , =} , for each 1 ≤ ≤ , and 1 2… , which generalizes the definition of an Allen’s relation to
Given a set of propositional letters, the logic ℋ is the -dimensional generalization of the interval temporal logic ℋ . Well-formed ℋ formulas are obtained by the following syntax: via duality.
∶∶= ∣ ¬ ∣ ∨ ∣ ⟨ 1 … ⟩, where, for each , ∈ , and ⟨ 1 … ⟩ ≠ ⟨= … =⟩. The remaining Boolean operators, as well as the universal version of each of the 13 − 1 existential operators can be defined as a shortcut
The strict semantics of ℋ is given in terms of -dimensional models of the type = ⟨( ), ⟩ , where (
) is the set of all hyperintervals over , and is a valuation function ∶ → 2 ( ) which assigns to every atomic proposition ∈ the set of hyperintervals () on which holds. The truth of a formula on a given hyperinterval in an interval model , denoted by , ⊩ , is defined by structural induction on the complexity of formulas as follows: , ⊩ , ⊩ ¬ , ⊩ , ⊩ ⟨ 1 ∨ 2 1 … ⟩ if and only if ∈ (), for each ∈ ; if and only if , ⊩ ̸; if and only if , ⊩ 1 or , ⊩ 2; if and only if there exists ′ s.t. 1… ′ and , ′ ⊩ .
The notion of formula satisfied by a model, satisfiable formula, and valid formula are defined in the standard way.
Quite naturally, a -dimensional instance described by the variables in can be seen as a dimensional model, provided that, fixed a set of feature extraction functions ℱ, the propositional vocabulary is defined as
= { ( ) ⋈ ∣ ∈ ℱ , ∈ , ⋈ ∈ {<, ≤, =, ≠, ≥, >}, ∈ ℝ}, so that, given a -dimensional instance , a hyperinterval = [( 1, 1), … , ( , )], and a variable , we can define the value of on in , denoted ( , ) as a hypermatrix in ℝ 1− 1+1×…×ℝ − +1 whose generic element with indexes 1, … , , with 1 ≤ ≤ − , for all [ , ] ∈ , is defined as: ( , )
1,…, = ( 1 + 1 − 1, … , + − 1).
Then, for a given propositional letter = ( ) ⋈ , we define ( ( ) ⋈ ) = { ∣ ∈ ( ) and ( ( , )) ⋈ }.
Modal decision trees and modal random forests, when applied to -dimensional datasets, may extract patterns written in ℋ [13, 14]. Therefore, establishing which variables and feature extraction functions, that is, which features, are informative in which hyperintervals, is a natural pre-processing step. Typical -dimensional datasets are described by hundreds or thousands of variables in several dimensions, to which tens of feature extraction functions can be applied; this leads to a number of features in the order of the tens of thousands, from which a choice of a few units is usually made for further analysis.
ℐ ℐ
ℐ ′ ℐ ″ ℐ ‴ … parameter description ℱ { 1, … , }: hyperwindowing { 1, … , }: feature extraction unsupervised algorithm unsupervised aggregation unsupervised selected fraction supervised algorithm supervised aggregation supervised selected fraction
Given a -dimensional dataset in which every instance is described by distinct points on each of the dimensions leads to the need of considering ( ( + 1)/2) distinct hyperintervals; on each one of them, one should assess the value of distinct variables under distinct functions. A few considerations can be immediately drawn: (i) even in the context of filters, exploring all combinations seems infeasible, and (ii) hypothesis test-based selection should be avoided altogether, considering their probabilistic nature (that is, considering that performing too many probabilistic tests on the same data may lead to an unreliable result [17, 18]). However, the potential predictive power of features in -dimensional data should be evaluated on hyperintervals, so that symbolic learning methods can take advantage of them.
As a tradeof, let us introduce the notion of hyperwindow. Let be a finite space defined as before, and let 1, … , be a set of hyperintervals such that, for every point ( 1, … , ) ∈ , there is a hyperinterval (1 ≤ ≤ ) with ( 1, … , ) ∈ ; we call each such hyperinterval a hyperwindow, and the set 1, … , a hyperwindowing of . By extracting all features on all hyperwindows for a given and evaluating them, one is able to approximate the behaviour of such features on a generic hyperinterval; there are, of course, several ways in which a hyperwindowing can be produced.
Based on the idea that a feature can be evaluated on a hyperwindow, unsupervised and supervised methods in the whole range of classic techniques can be systematically used to this end. Given a -dimensional dataset ℐ, with dimensional variables to which feature extraction functions can be applied, and given a set of hyperwindow parameterizations { 1, … , }, a high-level description of the entire approach can be given in the following steps: 1. A -dimensional dataset ℐ
is built by hyperwindowing the original one; ℐ encompasses Σ=1 dimensional variables. 2. A tabular dataset is derived from ℐ , with Σ=1 adimensional features. Each feature represents the result of applying a feature extraction function to a variable in a particular hyperwindow, to which a min-max normalization is applied, to allow comparisons. This can be done in several ways: variable-wise, function-wise, function and window-wise, or across any combination of variables, depending on the nature of the dataset. Let ℐ ′ be the result of this phase. 3. An univariate unsupervised filter is applied to ℐ ′. Since values are normalized, an unsupervised individual score ( ) can be computed for each triple variable-functionhyperwindow. Selecting a pre-determined fraction of pairs based on their produces a new tabular dataset ℐ ″. 4. An univariate supervised filter is then applied to ℐ ″. As before, each featurehyperwindow pair is assigned a supervised individual score ( ). Selecting a predetermined fraction of triples based on produces a new tabular dataset ℐ ‴. It should be noted that the unsupervised and the supervised steps are actually independent of each other; however, the practice suggests that the unsupervised step should be applied first to eliminate the pairs that most probably do not contain any relevant information, and then, the supervised step (usually, computationally more expensive) should be applied to select the pairs that most probably contain information that is relevant to the problem. Furthermore, the above schema can be further extended by adding suitable aggregation functions: both unsupervised and supervised selection can be indeed performed after aggregating the triples either by feature extraction function, variable, hyperwindow, or a combination of them; in fact, it is convenient to assume that an aggregation function is always applied, whereas the simplest choice is an identical aggregation function with no efect. Other examples of aggregation functions include computing the maximum score or the average score across hyperwindows or across functions. Aggregation can be applied to the end result as well, in order to return the best variables, the best functions, and the best hyperwindows.
Summarizing, the following parameters should be set for a given set of experiments: the set of feature extraction functions (ℱ), the hyperwindowing parametrization ({ 1, … , }), the unsupervised filter ( ), the supervised filter ( ), and two aggregation functions ( , ), along with the fraction of selected elements after the unsupervised step ( ) and the fraction of selected elements after the supervised one ( ). A schematic representation of our approach and its parametrization can be found in Fig. 2.
In order to evaluate the efectiveness of our approach we considered two cases, in the temporal ( = 1 ) and spatial ( = 2 ) setting, respectively. In both cases the datasets are public and had been used in the past for several other learning experiments.
In the temporal case, we use a dataset of audio samples, specifically of cough recordings, each one is labelled as positive or negative to COVID-19 infection [19]. The dataset is composed of 9986 audio samples recorded by 6613 volunteers, of which 235 declared to be positive. This data was originally used to derive smaller datasets, each posing a diferent form of the same task of COVID-19 diagnosis depending on the specific set of symptoms and conditions of the subjects. We refer to these tasks and datasets as TA1, TA2, and TA3. After the original 1,000 2,000 3,000 5,000 6,000 7,000 10 20 30 40 0 10 20 30 40 1,000 2,000 3,000 4,000 5,000 6,000 7,000 10 20 30 40 10 20 30
40 4,000 S F 0.25 0.20 0.15
E M I T E C A P S 1 FS TA MI 2 FS TA MI 3 FS TA MI P I MI C P MI
FS FS
FS U
P MI -values of the selected features for COVID-19 (TIME) and LCC (SPACE) tasks. publication, these tasks were approached and solved in several diferent way, among which 200 400 800 1,000 10 20 30 40 10 20 30 40 100 200 400 500 600 10 20 30 40 10 20 30 40 100 200 300 400 500 600 10 20 30 40 1.50 1.00 0.50 0.000 1.9 I 1.8 M 1.7
1.60 modal decision trees and forests [13]. In this paper, we considered the tasks TA1 ( = 343 ), TA2 ( = 71 ), and TA3 ( = 55 ). The temporal interpretation of audio signals emerges after the initial pre-processing via Mel-Frequency Cepstral Coeficients (MFCC) [20]. In short, MFCC consists of, first, separating the raw signal into chunks of small size and applying a Discrete Fourier Transform (DFT) to each of the chunks to produce a spectrogram of the sound at each chunk, second, converting and representing the frequency spectrum in mel scale, and third, convolving a set of triangular band-pass filters across the frequency spectrum, discretizing it into a finite number of frequencies. Ultimately, this produces a multivariate time series representation where the variables describe the power of the diferent sound frequencies; in this experiment, we fixed = 30 , that is, the variables are 1, … , 30. For all these tasks we set = {1, 3, 6} for a total of 7 hyperwindows for each variable. There are several feature extraction functions that can be applied to temporal data. A commonly used portfolio is the so-called Catch22 set [21], encompassing 22 selected functions that have shown the ability of extracting relevant information from temporal data in several cases; to this set, we add minimum, maximum, and mean, leading to a set of = 25 feature extraction functions.
As for the spatial case, we considered three multiclass datasets, that is, Indian Pines (IP), Pavia University (PU), Pavia Centre (PC), commonly used to benchmark methods for a problem known as land cover classification (LCC), which typically refers to the task of classifying pixels in remotely sensed images, associating each pixel with a label that captures the use of the land it depicts (e.g., forest, urban area, or crop field ). Despite being an instance of standard image segmentation, this problem is usually dealt with as an image classification task. Images of this kind are usually captured from satellite or aerial sensors, and a single pixel carries the average electromagnetic response of a wide surface area; as such, the classification of a pixel in the image typically depends only on a close neighborhood of pixels around it. Additionally, the imagery is hyperspectral, that is, it encloses a large number of spatial variables (spectral channels), describing the strength of signals at diferent electromagnetic wavelengths. In the case of IP, we considered 1600 5 × 5 images ( = 1600 ) with = 200 (in this cases, then, variables are named 1, … , 200), each labelled with one of 16 classes ( = 16 ), while in the case of PC we had = 103 and = 9 ( = 1600 , 1, … , 103). In all cases we let = {2} , and, in terms of feature extraction functions: in particular, we limited our search to generalized mean, maximum, and minimum, that is, = 3 .
For both the temporal and the spatial case we used a variance-based unsupervised filter ( ). This method is based on the idea that features with too low variance should be excluded. Examples of such filters include the Variance Threshold method in the ScikitLearn suite [22]. In this step we let be the identity function (no aggregation was performed), selecting the ifrst half of the total number of the variables ( = 0.5). In regard to the supervised selection we applied two diferent methods for both datasets: Mutual Information (MI) [23] and Fisher Score (FS) [24]. Depending on the problem and task we used diferent values for : for all temporal dataset tasks we set = 0.032 (so that the total number of selected features is 12); for the spatial datasets we used = 0.02 for IP (the final selection resulting in 12 features) and = 0.04 for both PC and PU (13).
All results are summarized in graphical form in Fig. 3 and 4. In both cases the scores in the unsupervised step decrease quite steeply well before reaching the first half of the set of analyzed features. This indicates that excluding as much as 50% of the features is quite efective, and that this fraction could be increased. After the second step, the value of the selected features can only be estimated: one way to do so is to use each feature in a pairwise, non-parametric hypothesis test (validation step). In the temporal case, the test is binary; in the spatial, multiclass case, instead, we performed one-versus-all tests to identify the class that is best distinguished from the other ones, and its corresponding -value. It is crucial to observe that a hypothesis test could not be used in any preceding step as a selection criterium: given its probabilistic nature, performing too many tests renders its results unreliable [18]. This problem still exists during validation, though to a lesser extent. To compensate for it we applied the Bonferroni method for -value correction; the corrected -values are shown in Tab. 2. As it can be seen, most of the selected features, but not all, passed the test with confidence greater than 95%, and in most of those cases greater than 99%. The fact that not all the selected features are validated indicates that the choice is not trivial, and our approach was able to select a few very informative variable-function-hyperwindow triples from sets of between 600 and 7500. By way of example, the first selection for TA1 in the case of FS corresponds to the total power in lowest ifth of frequencies in the Fourier power spectrum (from Catch22) applied to 2 on the whole series, while for IP corresponds to the mean value of 3 applied to the innermost 3 × 3 window.
Feature engineering and selection are a very well-known problem. Most, if not all the work, however, has been confined to the case of adimensional, tabular data. In this paper, we approached feature engineering and selection for dimensional data. Our proposal is inspired by recent results regarding symbolic learning from dimensional data, but it can be applied independently of any learning method as a way to study dimensional datasets. Conceived as a combination of known techniques, our framework is capable of identifying the most informative variables, the most informative feature extraction functions, and the most informative hyperwindows in a dimensional dataset of any number of dimensions. We performed a series of experiments in the case of two and three dimensions, obtaining quite encouraging results.
Our implementation, written in Julia, is open-source and it is part of a bigger project that includes symbolic learning techniques, feature selection, and post-hoc interpretation of symbolic models for non-tabular data.
We acknowledge the support of the project Modal Geometric Symbolic Learning, founded by the University of Ferrara under the FIRD program. [8] Y. Yamada, E. Suzuki, H. Yokoi, K. Takabayashi, Decision-Tree Induction from Time-Series Data Based on a Standard-Example Split Test, in: Proceedings of the 12th International Conference on Machine Learning (ICML), 2003, p. 840–847. [9] A. Brunello, E. Marzano, A. Montanari, G. Sciavicco, J48SS: A novel decision tree approach for the handling of sequential and time series data, Computers 8 (2019) 21. [10] S. Jha, A. Tiwari, S. A. Seshia, T. Sahai, N. Shankar, TeLEx: learning signal temporal logic from positive examples using tightness metric, Formal Methods in System Design 54 (2019) 364–387. [11] X. Li, C. Claramunt, A spatial entropy-based decision tree for classification of geographical information, Transactions in GIS 10 (2006) 451–467. [12] D. Della Monica, G. Pagliarini, G. Sciavicco, I. Stan, Decision trees with a modal flavor, in: Proc. of the 221st Conference of the Italian Association for Artificial Intelligence (AIXA), volume 13796 of LNCS, Springer, 2022, pp. 47–59. [13] F. Manzella, G. Pagliarini, G. Sciavicco, I. Stan, The voice of COVID-19: breath and cough recording classification with temporal decision trees and random forests, Artifcial Intelligence in Medicine 137 (2023) 1–14. [14] G. Pagliarini, G. Sciavicco, Decision tree learning with spatial modal logics, in: Proc. of the 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF), volume 346 of EPTCS, 2021, pp. 273–290. [15] J. Halpern, Y. Shoham, A Propositional Modal Logic of Time Intervals, Journal of the ACM 38 (1991) 935–962. [16] P. Balbiani, J. Condotta, L. Fariñas del Cerro, A model for reasoning about bidimensional temporal relations, in: Proc. of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR’98), Morgan Kaufmann, 1998, pp. 124–130. [17] G. Heinze, D. Dunkler, Five myths about variable selection, Transplant International (2017) 6–10. [18] M. Jafari, N. Ansari-Pour, Why, when and how to adjust your p values?, Cell 20 (2019) 604–607. [19] C. Brown, J. Chauhan, A. Grammenos, J. Han, A. Hasthanasombat, D. Spathis, T. Xia, P. Cicuta, C. Mascolo, Exploring automatic diagnosis of COVID-19 from crowdsourced respiratory sound data, in: Proc. of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2020, pp. 3474–3484. [20] S. Davis, P. Mermelstein, Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences, IEEE Transactions on Acoustics, Speech and Signal Processing 28 (1980) 357–366. [21] C. Lubba, S. Sethi, P. Knaute, S. Schultz, B. Fulcher, N. Jones, Catch22: Canonical timeseries characteristics - selected through highly comparative time-series analysis, Data Mining and Knowledge Discovery 33 (2019) 1821–1852. [22] F. Pedregosa, et. al., Scikit-learn: Machine learning in Python, Journal of Machine Learning
Research 12 (2011) 2825–2830. [23] A. Kraskov, H. Stögbauer, P. Grassberger, Estimating mutual information, Physical review
E 69 (2004) 066138. [24] R. Duda, P. Hart, D. Stork, Pattern Classification, Wiley, 2012.