A Geometric Theory of Feature Selection and Distance-Based Measures

1 Introduction

Feature selection is indeed one of the central focuses of machine learning research. In this paper, we understand the feature selection problem as follows:

Given a dataset, select an appropriately small number of features that faithfully determine the classes of the examples of the dataset.

If we could find a feature subset such that the features correctly determine the classes of the examples, it could be an answer we wanted [Almuallim and Dietterich, 1994]. Such feature subsets are referred to as reducts in the rough set theory [Pawlak, 1991] and as consistent feature sets in this paper [Liu et al., 1998].

A dataset, however, does not necessarily include a consistent feature subset, and in such cases, we have to be satisfied with selecting feature subsets that are sufficiently close to being consistent. In other words, we need a measure that can measure the "distance" of a feature subset to the "closest" consistent feature set. However, we only know two necessary conditions for such a measure, namely, determinacy and monotonicity: Determinacy corresponds to the identity of indiscernibles of the axioms of metrics and requires that the measurement is zero, if, and only if, the feature set is consistent; Monotonicity, on the other hand, requires that the measurement of an arbitrary feature set is no greater than the measurement of its subset. When a measure has the determinacy and monotonicity properties, we also say that it is determinant and monotonous. With a determinant and monotonous measure, a feature selection algorithm attempts to find feature sets whose measurements are close to zero.

Generally, the feature selection measures proposed in the literature are categorized into two groups. One consists of measures that simply evaluate dependence between two features [Mengle and Goharian, 2009; Bol´on-Canedo et al., 2011; Foithong et al., 2012; Suzuki and Sugiyama, 2013; Wang, 2015]. The framework of mRMR [Peng et al., 2005] takes advantage of measures of this group and aims to select a feature set that maximizes the difference of the relevance from the redundancy of the feature set: The relevance is the collective dependence of the feature set to class labels, while the redundancy is the the internal mutual dependence of the features of the feature set. On the other hand, the other consists of determinant and monotonous measures [Liu et al., 1998; Shin and Xu, 2009; Arauzo-Azofra et al., 2008], and 14 of the 17 feature selection measures studied in [Molina et al., 2002] are known to belong to this group [Shin et al., 2011]. In this paper, we are interested in the latter group.

Example 1 Bayesian risk, also known as inconsistency rate [Liu et al., 1998], is defined as follows.

S is a feature subset of a dataset D, and C is the random variable to represent classes. ΩS and ΩC are the sample spaces of S and C, and p is the empirical probability distribution of D. This measure is, indeed, determinant and monotonous.

Example 2 Zhao et al. [Zhao and Liu, 2007] proposed In-

teract, a feature selection algorithm that leverages the Bayes risk µbr to evaluate the closeness of feature sets to the state of being consistent. Therefore, Interact selects feature sets with small µbr measurements.

Example 3 Shin et al. [Shin and Xu, 2009] also proposed the conditional entropy defined by

as a determinant and monotonous measure. On the other hand, the well-known feature selection algorithm that selects the top n features X with respect to the mutual information I(X; C) actually selects those feature sets that minimize

By using µD instead of µceD , this algorithm is fast but is not very accurate, since µD is not determinant.

When a measure represents the distance of a feature set to the closest consistent feature set in some metric space, we call it distance-based. About distance-based measures, we only knew two necessary conditions, that is, determinacy and monotonicity, and hence, the distance-based measure was only an analogy to explain the desirable natures of feature selection measures. This paper changes this.

In this paper, we present a way to identify a feature subset of a dataset uniquely with a point in a common metric space. The metric space is parameterized by a real number p ∈ [1,∞], and hence, we have infinitely many such metric spaces. In the metric space, consistent feature sets form a closed subspace, and hence, we can determine the distance of an arbitrary feature set to the closest consistent feature set. This is nothing other than a distance-based measure. A different values of p determines a different metric function. For p = 1, we show that the measure is identical to the wellknown Bayesian risk. On the other hand, for p > 1, the measure is novel and unknown in the literature. Also, through experiments, we show that measurements by our novel distancebased measures correlate with classification accuracy.

2 Formulating feature selection measures

In this paper, we do not discriminate between features and random variables. Furthermore, for a dataset D, we use the following notations.

• FD is the entire set of features of D. FD is finite and includes the feature CD that represents classes. Also, we denote FD \ {CD} by FD.
• ΩFD = ∏X∈FD ΩX is the entire sample space, where ΩX is the sample space of an individual feature X. For a feature set S, ΩS means the Cartesian product ∏X∈S ΩX, which is the sample space of S. · pD : ΩFD → Q is the empirical probability distribution.
• We also denote D by the triplet (FD, ΩFD , pD).
• For S ⫅ FD, D|S is the dataset derived from D by eliminating the features in FD \ S.
• For S ⫅ FD, D∧S is the dataset derived from D by replacing the features of S with a single feature ∧S such that Ω∧S = ΩS. The values for S of an example in D are replaced with the vector consisting of the values.

Example 4 For the dataset D determined by (a) below, we have FD = {B,R,G,CD} and ΩFD = {A,B,O,AB} × {M,N,C,A} × {M, F} × {p, n}. When S = {R,G}, (b) and (c) determine D |S and D∧S .

On the other hand, a feature selection measure µ is formulated as a family of µD indexed by datasets D, and each µD is a real-valued function defined over the power set P(FD) of FD. In this paper, we assume that a feature selection measure supports the following three requirements, which all of the 19 measures surveyed in [Shin et al., 2011] support as well.

Requirement 1 (Naming invariance)

Measurements by the measure are invariant to renaming of features and feature values. This also implies that the measure assumes that every feature is categorical.

Requirement 2 (Localization invariance)

Requirement 3 (Feature aggregation invariance)

If T ⫆ S, µD (T ) = µD∧S ((T \ S) ∪ {∧S}) holds.

Example 5 Bayesian risk µbr has all of these invariance properties: µbrD (FD) = µbr E (FE) = 15 indicates the naming invariance; For S = {R,G}, µbrD ({G}) and µbrD|S ({G}) are identical to 25 , and µbrD∧S ({B, ∧S}) = 15 holds These indicate the localization and feature aggregation invariance properties. E F1 F2 F3 CD 1 1 1 +1 1 1 1 -1 2 2 1 +1 3 3 2 -1 4 4 1 -1

In this paper, we will identify (D, S) and (E, T), pairs of a dataset and a feature subset, if µD (S) = µE (T) holds for any measure µ that supports Requirements 1, 2 and 3. For this, we introduce the notion of coherent mappings and then prove Proposition 1.

Definition 1 A mapping ϕ : FD → FE is coherent between D and E, if, and only if, there exist injections vY : Ωϕ-1 (Y ) → ΩY for Y ∈ Im(ϕ) and an injection vCE : ΩCD →ΩCE such that

Example 6 We consider the datasets D of Example 4 and E below. When we define ϕ by ϕ(B) = F1 and ϕ(R) = ϕ(G) = F2, ϕ is coherent. To show this, we determine vF1 and vF2 as below and vCE by vCE (p) = 1 and vCE (n) = 2. For example, pD(A,M,M, p) = 15 and pE(1, 1, 1, 1) + pE(1, 1, 3, 1) = 1 10 + 1 10 = 15 hold.

E

Proposition 1 If a feature selection measure µ supports Requirement 1 to 3, µE (S) = µD (ϕ-1 (S)) holds for an arbitrary coherent mapping ϕ : FD → FE between D and E and an arbitrary S ⫅ Im(ϕ).

Proof. We let ϕ = ϕ ◦ ϕ such that ϕ : FD → Im(ϕ) and ϕ : Im(ϕ) → FE. Since ϕ yields a sequence of feature aggregations that convert D into E|Im(ϕ) up to renaming of features and feature values, µE (S) = µE|Im(ϕ) (S) = µD (ϕ-1 (S)) follows from Requirement 1 to 3.

Example 7 For the same D, E and ϕ as Example 6, µbr E ({F1, F2}) = µbrD ({B,R,G}) = µbr E ({F1}) = µbrD ({B}) = µbr E ({F2}) = µbrD ({R, G}) = 1 5 holds.

3 Projecting a feature set of a dataset into a subspace P + R 〈∞〉 of the ℓp space (p ∈ [1,∞])

We let n ∈ N ∪ {∞}. We introduce the space P0 〈n〉 into which feature sets of datasets are projected. We start with preparation. Let K be either the rational number field Q or the real number field R. We define PK〈∞〉 and P + K 〈∞〉 as follows, which are sets of functions p such that p : N2 → K.

Definition 2 We define PK〈∞〉 and P + K 〈∞〉 by:

We can identify N2 with N (for example, f : (i, j) ↦→ (i+j-1)(i+j-2) 2 + i is bijective), and therefore, PR〈∞〉 and P + R 〈∞〉 can be viewed as subspaces of ℓp for 1 ≤ p ≤ ∞. If we focus on datasets that include at most n classes, we can use PK〈n〉 and P + K 〈n〉 instead.

Definition 3 We define PK〈n〉 and P + K 〈n〉 by:

PR〈n〉 and P + R 〈n〉 are metric spaces with the metric derived from the norm ‖ · ‖p of ℓp . PR〈n〉 is closed in ℓp only when p = 1, while P + R 〈n〉 is the closure of PR〈n〉 in ℓp for 1 < p ≤ ∞. Therefore, PR〈n〉 in ℓ1 and P + R 〈n〉 in ℓp for 1 < p ≤ ∞ are complete, since ℓp is a Banach space. Although PR〈n〉 and P + R 〈n〉 are bounded, none of them is compact.

We define P0 〈n〉 , a subspace of PR〈n〉 , as follows.

Definition 4 We let supp(p) be the smallest ΩU ×ΩC such that ΩU ⫅ N, ΩC ⫅ N and ΩU × ΩC ⫆ Supp(p) = {(i, j) | p(i, j) > 0}. We define P0 〈∞〉 and P0 〈n〉 for n ∈ N by:

Example 8 When we define p by p(i, i) = (1 - r)ri-1 for r ∈ (0, 1), p ∈ PR〈∞〉 holds, because ∑∞i=1 (1 - r)ri-1 = (1 - r) limn→∞ 1-rn 1-r = 1. Furthermore, if r ∈ Q, p ∈ PQ〈∞〉 holds. For this p, we have ΩU = N, ΩC = N and supp(p) = {(i, i) | i ∈ N}. Hence, p /∈ P0 〈∞〉 .

For n ∈ N ∪ {∞}, P0 〈n〉 turns out to be dense in PR〈n〉 . For p ∈ P0 〈n〉 , Dp = ({U,C},N × N, p) is not a dataset, because N × N is infinite. Nevertheless, we can think of a coherent mapping ϕ : FD → {U} between a dataset D and Dp. Theorem 1 shows how to project a feature set S of a dataset D into P0 〈n〉 .

Theorem 1 We let D be a dataset with n classes and S ⫅ FD. There exists p ∈ P0 〈n〉 such that ϕ : S → {U} is coherent between D|S and Dp. Conversely, for arbitrary p ∈ P0 〈n〉 , there exists a dataset D with n classes such that ϕ : FD → {U} is coherent between D and Dp.

Proof. Let v1 : ΩS → N and v2 : ΩCD → {1, . . . , n} be injective. It suffices to define p ∈ P0 〈n〉 by p(i, j) = pD|S (v-1 1 (i), v-1 2 (j)) if (i, j) ∈ Im(v1×v2) and p(i, j) = 0 otherwise. To show the converse, we have only to let D = ({U, C}, supp(p), p).

Example 9 To project D|S of Example 4 into P0 〈2〉 , we determine p ∈ P0 〈2〉 by p(1, 1) = p(1, 2) = p(3, 1) = p(6, 2) = p(7, 4) = 1 5 and p(i, j) = 0 otherwise. When we determine vU and vC identical to vF2 and vCE of Example 6, ϕ : S → {U} is coherent between D|D and Dp, and hence, D|D is projected to p.

Example 10 A single D|S can be projected to infinitely many points in P0 〈n〉 . For example, we let D|S, p and vU be the same as Example 9. For an arbitrary bijection π : N → N, we define pπ by pπ(π(i), j) = p(i, j). Apparently, D|S projects to pπ with π ◦ vU .

Example 11 More than one datasets are projected to a single point in P0 〈n〉 . For example, D|S of Example 4 and E|{F2} of Example 6 are both projected to any of pπ of Example 10. To be precise, a single point in P0 〈n〉 has infinitely many datasets that project to the point.

Based on Proposition 1 and Theorem 1, Theorem 2 asserts that a feature selection measure can be uniquely viewed as a real-valued function defined over P0 〈n〉 .

Theorem 2 For a feature selection measure µ, ˆµ : P0 〈∞〉 → R uniquely exists and ˆµ(p) = µD (S) holds for arbitrary D, S and p such that ϕ : S → {U} is coherent between D|S and Dp.

Proof. We let D∗p be ({U,C}, supp(p), p) for p ∈ P0 〈∞〉 . We determine ˆµ(p) by µD∗p ({U}). For a dataset D such that ϕ : S → {U} is coherent between D|S and Dp with vU : ΩS → N and vC : ΩCD → N, we let D# p = ({U,C}, Im(vU) × Im(vC), p). ϕ : S → {U} is coherent between D|S and D# p , and the inclusion supp(p) ⫅ Im(vU) × Im(vC) yields coherence between D∗p and D# p . Therefore, µD (S) = µD# p ({U}) = µD∗p ({U}) = ˆµ(p).

Example 12 Datasets that are projected to the same point in P0 〈n〉 have the same measurement for an arbitrary feature selection measure µ. For example, as seen in Example 11, D|S of Example 4 and E|{F2} of Example 6 are both projected to the same point P0 〈2〉 . On the other hand, µbrD (S) = µbr E ({F2}) = 15 holds as seen in Example 7. Therefore, by letting ˆµ(p) = µD (S) for D|S that projects to p, ˆµ is well defined.

The problem of the projection determined by Theorem 1 consists in the fact that a single pair (D, S) is mapped to an infinite number of different points in P0 〈n〉 (Example 10). In the next section, we will solve this problem.

4 Defining a quotient space Q+R 〈∞〉 of P + R 〈∞〉

Our idea to solve the problem is to introduce an equivalence relation that unifies points of P0 〈n〉 that are the images of the same single pair (D, S) and then use the resulting quotient space. The relation ∼ defined below is an equivalence relation. We assume n ∈ N ∪ {∞}.

Definition 5 Let p and q be in P + R 〈∞〉 . We define p ∼ q, if, and only if, there exist bijections vU : N→N and vC : N→ N such that p(i, j) = q(vU (i), vC(j)).

Example 13 pπ ∼ p holds for pπ and π of Example 10.

Definition 6 We let Q+R 〈∞〉 = P + R 〈∞〉/∼. Moreover, for the canonical projection π : P + R 〈∞〉 → Q+R 〈∞〉 , we let Q+R 〈n〉 = π(P + R 〈n〉 ), QR〈n〉 = π(PR〈n〉 ) and Q0 〈n〉 = π(P0 〈n〉 ).

Proposition 2 is easy to see but plays a crucial rule to prove Theorem 3 and 4.

Proposition 2 For p and q in P0 〈∞〉 , the following are equivalent.

1. p ∼ q.

1. ϕ : S → {U} is coherent between D|S and Dp, if, and only if, it is coherent between D|S and Dq.
2. There exists (D, S) such that ϕ : S → {U} is coherent between D|S and Dp and between D|S and Dq.

Theorem 3 and 4 follow from Theorem 1, Theorem 2 and Proposition 2. In the following, [p] denotes π(p), and [D, S] denotes the image of (D, S) in Q0 〈∞〉 .

Theorem 3 We let D be a dataset with n classes and S ⫅ FD. There uniquely exists [p] ∈ Q0 〈n〉 such that ϕ : S → {U} is coherent between D|S and Dp. Conversely, for arbitrary [p] ∈ Q0 〈n〉 , there exists a dataset D with n classes such that

• ϕ : FD → {U} is coherent between D and Dp.

Theorem 4 For a feature selection measure µ, there uniquely exists [ˆµ] : Q0 〈∞〉 → R such that [ˆµ]([D, S]) = µD (S) holds for any dataset D and S ⫅ FD.

5 Introducing a metric dp into Q+R 〈∞〉

Although a quotient of a metric space is not always a metric space, we can derive a metric into Q+R 〈∞〉 from ℓp as follows.

Definition 7 For [p] and [q] in Q+R 〈∞〉 , we define dp([p], [q]) = inf{‖p′ - q′‖p | p ∼ p′ , q ∼ q′}.

Theorem 5 For 1 ≤ p ≤ ∞, dp is a metric over Q+R 〈∞〉 .

Proof. We only prove the triangle inequality dp([p], [r]) ≤ dp([p], [q]) + dp([q], [r]) taking advantage of Lemma 1.

Lemma 1 For p ∼ p′ and q in P + R 〈∞〉 , there exists q′ ∼ q such that ‖p - q‖p = ‖p′ - q′‖p.

For ε > 0, we assume ‖p - q‖p - dp([p], [q]) < ε2 and ‖q′ - r‖p - dp([q], [r]) < ε2 for q ∼ q′ . By Lemma 1, we have ‖q - r′ ‖p = ‖q′ - r‖p and dp([p], [r]) ≤ ‖p - r′ ‖p ≤ ‖p - q‖p + ‖q - r′‖p < dp([p], [q]) + dp([q], [r]) + ε.

µℓp from dp

Q〈n〉 0 Definition 8 p ∈ P + R 〈∞〉 is consistent, if, and only if, there exists j : N → N such that p(i, j) = 0 if j ̸= j(i).

6 Deriving a measure ̂ We see that the minimum of dp distance from [D, S] to a consistent feature set determines a feature selection measure. We first define consistent points of P + R 〈∞〉 .

C+ R 〈∞〉 denotes the entire set of consistent p, and we let C+ R 〈n〉 = C+ R 〈∞〉 ∩ P + R 〈n〉 , CR〈n〉 = C+ R 〈∞〉 ∩ PR〈n〉 and C0 〈n〉 = C+ R 〈∞〉 ∩ P0 〈n〉 for n ∈ N ∪ {∞}.

Definition 9 For j : N → N such that j(i) ∈ argmax{p(i, j) | j ∈ N} and p ∈ P0 〈∞〉 , we define:

Dp, µbrD (S) = ̂ Proof. We assume that vU : ΩS → N and vC : ΩC → N yield the coherence between D|S and Dp.

Theorem 6 For p ∈ P0 〈∞〉 , the following holds.

Proof. Here, we prove only 1. For q ∈ C0 〈∞〉 , we assume j : N → N such that q(i, j) = 0 if j ̸= j(i). Also, we let j : N → N satisfy j(i) ∈ argmax{p(i, j) | j ∈ N}. We first fix i ∈ N.

Then, we sum up the both sides across all i ∈ N.

On the other hand, for q ∈ C0 〈∞〉 such that q(i, j) = ∑j∈N p(i, j) if j = j(i) and 0 otherwise, we have

As q′ ∈ CR〈∞〉 if q′ ∼ q, Lemma 1 implies the assertion.

7 Contrasting d1 and dp with p > 1

Determinacy of ̂ µℓp immediately follows from Theorem 6. Also, it is easy to show monotonicity of ̂ µℓp. Furthermore, ̂ µℓp turns out continuous under dq for arbitrary 1 ≤ p, q ≤ ∞.

Proposition 3 asserts that ̂ µℓ1 is identical to the Bayesian risk, which is well known in the literature. On the other hand, ̂ µℓp with p ∈ (1,∞] is a novel measure unknown in the literature. Also, as a metric function, d1 and dp with p ∈ (1,∞] are significantly different as stated below without proof.

• QR〈∞〉 is complete under d1, while Q+R 〈∞〉 is complete under dp for p ∈ (1,∞].
• QR〈n〉 is not compact under d1, while Q+R 〈n〉 is compact under dp for p ∈ (1,∞].
• Q0 〈n〉 is dense in QR〈n〉 under d1, while it is dense in Q+R 〈n〉 under dp for p ∈ (1,∞].

Moreover, in Section 8, we will see that ̂ µℓ1 and ̂ µℓp for p ∈ (1,∞] have different properties in terms of correlation between their measurements and classification accuracy. Although we cannot explain the reason for this difference, we imagine that it is related with the aforementioned difference between d1 and dp with p ∈ (1,∞] as a metric function.

8 Correlation between measurements by ̂ µℓp and classification accuracy

We evidently expect that there exists strong correlation between measurements by a good measure and classification accuracy. From this point of view, we ran experiments with ̂ µℓp for p = 1, 2, . . . , 5. In particular, we focus on comparison between p = 1 and p > 1: ̂ µℓ1 is identical to the Bayesian risk and is the feature selection measure that is used the most widely in the literature; On the other hand, the other measures are novel and introduced in this paper for the first time.

8.1 Datasets

Table 1 shows the datasets that we use in our experiments as well as their important attributes, namely, the numbers of features, examples and classes. All of the datasets are obtained from the UCI repository of machine learning databases [Blake and Merz, 1998].

8.2 Methods

The following are the steps of our experiments.

Sampling feature sets

For each dataset of Table 1, 60 feature sets are selected at random. The sizes of the selected feature sets also vary at random. In total, we obtain 60 × 12 = 720 pairs of a feature set and a dataset.

Localizing datasets

For each pair of a feature set and a dataset, we localize the dataset by eliminating all of the features that do not belong to the relevant feature set. Consequently, we obtain 720 localized datasets.

Measuring accuracy of classification

We apply three classifiers, namely, Na¨ıve Bayes, C4.5 and SVM, to each of the localized datasets in the manner of 10-fold cross validation and record the averaged AUC-ROC scores, which we use as classification accuracy scores.

8.3 Results

Figure 1, 2 and 3 display scatter plots of the results of our experiments with Na¨ıve Bayes, C4.5 and SVM, respectively. The x-axis of each chart represents measurements by a measure out of (a) ̂ µℓ1, (b) ̂ µℓ2, (c) ̂ µℓ3, (d) ̂ µℓ4 and (e) ̂ µℓ5 , while the y-axis does the averaged AUC-ROC scores. From the charts, we have the impression that ̂ µℓp with p > 1 shows stronger negative correlation with classification accuracy than µℓ1 . We look into this more closely in the next subsection.

To compare ̂ µℓ1 and ̂ µℓp with p > 1 in terms of correlation with classification accuracy, we introduce a function Pt(x) as an index. We let Nx be the number of plots whose ̂ µℓp distances fall within [x, x + 0.01) and Nt,x be the number of plots whose AUC-ROC scores exceed t and ̂ µℓp distances fall

̂ 8.4 Analysis on correlation

within [x, x+0.01). Then, we define Pt(x) by Pt(x) = Nt,x Nx . Intuitively, Pt(x) approximates the probability of the case that the classification accuracy exceeds t when the measurement by the relevant measure is x.

Figure 4, 5 and 6 show the curves of Pt(x) for Na¨ıve Bayes, C4.5 and SVM. The value of t varies in {0.95, 0.90, 0.85, 0.80}. Since Pt(x) ≥ Pt′(x) holds for t < t′ , the curve for t is located above the curve for t′ . We observe two properties from the charts.

• The curves for ̂ µℓp for p > 1 are akin to one another in shape, while the curves for ̂ µℓ1 appear significantly different from the other measures.

classification accuracy than the curves for ̂ In fact, the table below presents the correlation coefficients between the measurements x and the values of Pt(x). The presented values also support the observation stated above.

• The curves for ̂ µℓp with p > 1 exhibits clearer negative correlation between measurements by the measure and µℓ1 .

9 Conclusion

We have introduced a family of feature selection measures { ̂ µℓp | p ∈ [1,∞]} that are derived from the distance functions of some metric spaces. Although ̂ µℓ1 turns out to be identical to the Bayesian risk, ̂ µℓp for p ∈ (1,∞] are novel. Through experiments, we have shown that ̂ µℓp with p > 1 exhibits clearer negative correlation between its measurements and classification accuracy than ̂ µℓ1 does.