Choquet distances and their applications in data classification

Abstract

In the last decades, numerous optimization-based methods have been proposed for solving classification problems in pattern recognition. These methods mainly construct a straight line or a hyperplane to separate a given data set to be two classes. In this paper, we propose a new nonlinear classifier based on the Choquet integral with respect to a signed efficiency measure, and the boundary is a broken line (two considered attributes) or a Choquet broken-hyperplane (more considered attributes). Firstly, the Choquet distance of two points in n-dimensional space is proposed. Secondly, according to the Choquet distance, two nonlinear classification optimal models are presented. Finally, some experimental results show that the efficiency of the models for solving classification problems. The related results enrich the research of classification problems in pattern recognition.

Keywords

Nonlinear classification signed efficiency measure Choquet integral Choquet distance

1 Introduction

Classification is an important topic in areas of machine learning, statistics, and pattern recognition. Given a data set, which includes n attributes, m classes, l numerical records of each considered attributes, and the corresponding classes, a classification is a procedure to determine which class a new record of attributes belongs to. Essentially, this type of classification is an optimization problem and has been widely applied in knowledge discovery and data mining. Numerous approaches have been proposed for solving the classification problems, such as decision trees [10, 11], Bayesian networks [22], neural networks [21], Support vector machine [3], and etc.

Recently, the classification methods based on nonlinear integrals are studied and some encouraging results have been obtained. In these methods, using a nonlinear integral to fuse the values of a new record and to determine which class it belongs to. Paper [9] uses the fuzzy integral in the field of image processing. Grabisch and Sugeno propose to use fuzzy t-conorm integrals for classification [15]. Paper [16] uses the Choquet integral with respect to the non-additive measure on statistical pattern classification based on possibility theory. An optimization-based classification model is later proposed with a non-additive measure [17]. Paper [14] proposes the 2-additive classification with feature selections. Paper [1] gives a classification method by using Choquet integrals and Logistic regression. Paper [18] uses Choquet integral in supervised classification. Classification can also be achieved by directly separating the date using the weighted Choquet integral projection [13] or using a penalized signed fuzzy measure [6]. A detailed discussion of geometric meaning of the contributions from feature attributes in nonlinear classification can be found in [8]. Paper [2 , 24] gives the method for multiple classifiers and using the fuzzy integral as aggregation Operators.

We can use the Choquet integral [5] as a special nonlinear integral and make it to be a key role in classification. In particular, Wang and his collaborators make an outstanding contribution in this field [6 , 26].

The advantage of above methods by using nonlinear integrals is that they consider the interaction among attributes’ contributions towards the classification. As we have known, that in many real data sets, such an interaction among the considered attributes exists. Most existing classification methods do not care the such type interaction. The classifying boundary depend on the observed values of attributes. If the above-mentioned interaction exists, we may use it to get more reasonable results.

In this paper, based on the works of Wang, we use the Choquet integral for classification. A new concept “Choquet distance” is proposed and the optimal models based on Choquet distance for data classification are given.

The paper is organized as follows. After the introduction, in Section 2, nonadditive set function and nonlinear integrals are described. Section 3 proposes the Choquet distance. In Section 4, a new optimization-based classification models with the Choquet distance are developed. Section 5 shows the performance of proposed models in experimental results. Finally, Section 6 summarizes some conclusions from this research.

2 Fundamental concepts

Let X = {x₁, x₂, ⋯ , x_n} be the attributes set. In classification, a data set consisting of l example records, called training set, is given. Each record contains the values of feature attributes and the corresponding class. Positive integer l is called the data size. The values of attributes are numerical, and described by an n-dimensional vector, f = (f (x₁) , f (x₂) , …, f (x_n)), that is, f : X → (- ∞ , ∞). The range of attributes, which is a subset of n-dimensional Euclidean space (simply n-dimensional space), is called the feature space. The set of all possible values of classes, {C₁, C₂, ⋯ , C_m}, is denoted by C, where each C_k, k = 1, 2, ⋯ , m, refers to a specified class. Thus, the j-th sample record consists of the j-th observation for all feature attributes and the classifying attribute, and is denoted by (f_j, C_{k
_j}) = (f_j (x₁) , f_j (x₂) , ⋯ , f_j (x_n) , C_{k
_j}), j = 1, 2, ⋯ , l, where k_j belongs to {1, 2, ⋯ , m}.

The objective of classification is to build a classification model expressed by the feature attributes. When a new record of feature attribute is available, we can use the model to determine the class to which the new record belongs. That is to say, based on the training set, the required model should provide mathematical expressions of decision boundaries that divide the feature space into several pieces, each of them correspnds to a class in C.

We present a method of classification based on the Choquet integral [13 , 26]. This method can be regarded as the idea of projecting all data points in the feature space onto a real axis through a Choquet integral, and then using a one-dimensional classifier to classify these points according to a certain criterion optimally. At the same time, the classifying attribute is numericalized to be a virtual variable. Good performance of this method comes from the use of the nonadditive measure and the relevant Choquet integral, since the nonadditivity of the set function reflects the importance of the feature attributes, as well as their inherent interaction, toward the discrimination of the points. In fact, each feature attribute plays a respective role in making a decision that points out which class a given observation of feature attributes belongs to. That is, each feature attribute has respective important index reflecting their amounts of contributions toward the decision. Furthermore, the global contribution of several feature attributes to the decision of classification is not just the simple sum of the contribution of each feature to the decision, but may vary nonadditivity. A combination of the feature attributes may have a mutually restraining or a complementary synergy effect on their contributions toward the classification decision. So, the nonadditive set function defined on the power set of all feature attributes is a proper representation of the respective importance of the feature attributes and the interaction among them, and a relevant Choquet integral is a good fusion tool to aggregate the information coming from the feature attributes for the classification. The following are the details of these basic concepts and the mathematics model for the classification problem.

Some related definitions are introduced as follows.

Let P (X) be the power set of X.

Definition 1. [26] A monotone measure, μ, is a mapping from P (X) to [0, ∞) satisfying the following conditions:

μ (∅) =0;

A ⊂ B ⇒ μ (A) ≤ μ (B) , ∀ A, B ∈ P (X).

Conditions 1) and 2) imply the nonnegativity. Monotone measure μ is nonadditive in general. If μ (X) =1, then μ is said to be regular.

Definition 2. [26] let f be a nonnegative function on X and μ be a monotone measure on P (X). The Choquet integral of f with respect to μ, (C) ∫fdμ, is defined by $(C) \int fd μ = \int_{0}^{\infty} μ (F_{α}) d α,$ where F_α = {x|f (x) ≥ α} is the α-level set of f for any α ∈ [0, ∞).

To calculate the value of the Choquet integral of a given function f on X, the values of f = (f (x₁) , f (x₂) , ⋯ , f (x_n)), should be first rearranged into a nondecreasing order, that is $f (x_{1}^{'}) \leq f (x_{2}^{'}) \leq \dots \leq f (x_{n}^{'})$ , where $(x_{1}^{'}, x_{2}^{'}, \dots, x_{n}^{'})$ is a certain permutation of {x₁, x₂, ⋯ , x_n}. Then, the value of the Choquet integral, (C) ∫fdμ, can be obtained by computing $\sum_{i = 1}^{n} [f (x_{i}^{'}) - f (x_{i - 1}^{'})] μ ({x_{i}^{'}, x_{i + 1}^{'}, \dots, x_{n}^{'}}) .$ (1) where $f (x_{0}^{'}) = 0$ .

The Choquet integral is a generalization of the Lebesgue-like integral. When μ is a classical measure (i.e., additive), the Choquet integral coincides with the Lebesgue-like integral. The Choquet integral possesses most properties (but not the linearity) of the Lebesgue-like integral and has its naturalsemantics.

The signed efficiency measure defined below is a generalization of monotone measure and is adopted to develop optimization-based nonlinear classification models in general cases.

Definition 3. [26] A signed efficiency measure μ on P (X) is a set function μ : P (X) → (- ∞ , + ∞), with μ (∅) =0.

Nonlinear integrals are used as data aggregation tools to integrate the values of the attributes with respect to a signed efficiency measure. As one of nonlinear integrals, the translatable Choquet integral is more appropriate for applications, such as classification, because it provides very important information in interactions among attributes.

Definition 4. [26] Let μ be a signed efficiency measure. The translatable Choquet integral of f with respect to a signed efficiency measure μ on P (X), denoted by (C) ∫fdμ, is defined as follows: $\begin{matrix} (C) \int fd μ & = & \int_{- \infty}^{0} [μ (F_{α}) - μ (X)] d α \\ + \int_{0}^{\infty} μ (F_{α}) d α, \end{matrix}$ where F_α = {x|f (x) ≥ α} for α ∈ (- ∞ , ∞) is called the α-level set of f.

For every d = 1, 2, ⋯ , 2ⁿ - 1, we can use a corresponding bit string d_nd_n-1 ⋯ d₁ to express d, where each d_i, i = 1, 2, ⋯ , n is either 1 or 0. For example, when n = 5, 1 is expressed by 00001, 2 is 00010, 3 is 00011, ⋯, and 31 is 11111. Each set E_d ∈ P (X) corresponds to a bit string d with E_d = ∪ _{d_i=1} {x_i}. Thus, μ (E_d) = μ (∪ _{d_i=1} {x_i}) can be simply denoted by μ_d, d = 1, 2, ⋯ , 2ⁿ - 1. For example, μ₃₁ = μ ({x₁, x₂, x₃, x₄, x₅}), μ₁₅ = μ ({x₁, x₂, x₃, x₄}) , μ₁₀ = μ ({x₂, x₄}), and so on.

Using the above notation, the translatable Choquet integral can be calculated by: $(C) \int fd μ = \sum_{d = 1}^{2^{n} - 1} z_{d} μ_{d},$ (2) where $\begin{matrix} z_{d} & = & \min_{i | frc (d / 2^{i}) \in [1 / 2, 1)} (f (x_{i})) \\ - \max_{i | frc (d / 2^{i}) \in [0, 1 / 2)} (f (x_{i})), \end{matrix}$ if z_d > 0 or d = 2ⁿ - 1; otherwise z_d = 0, for d = 1, 2, ⋯ , 2ⁿ - 1. Here, frc (d/2ⁱ) denotes the fractional part of d/2ⁱ, and we need the convention that the maximum taken on the empty set is zero. The expression can also be written in a simple form via the replacement {i|frc (d/2ⁱ) ∈ [1/2, 1)} = {i|d_i = 1}, {i|frc (d/2ⁱ) ∈ [0, 1/2)} = {i|d_i = 0}.

The validation of (2) is proved as a theorem in [26].

Example 1. Let X = {x₁, x₂, x₃}, f (x₁) =1, f (x₂) =3, f (x₃) = -2, the signed efficiency measure: $\begin{matrix} μ_{1} & = & μ ({x_{1}}) = - 0.5, μ_{2} = μ ({x_{2}}) = 0.2, \\ μ_{3} & = & μ ({x_{1}, x_{2}}) = - 0.6, μ_{4} = μ ({x_{3}}) = 0.4, \\ μ_{5} & = & μ ({x_{1}, x_{3}}) = - 0.3, μ_{6} = μ ({x_{2}, x_{3}}) = 0.9, \\ μ_{7} & = & μ (X) = 0.3, with μ (\emptyset) = 0 . \end{matrix}$

Thus, using (2) we can get: $\begin{matrix} z_{1} & = & \max (0, \min (f (x_{1})) - \max (f (x_{2}), f (x_{3}))) = 0, \\ z_{2} & = & \max (0, \min (f (x_{2})) - \max (f (x_{1}), f (x_{3}))) = 2, \\ z_{3} & = & \max (0, \min (f (x_{1}), f (x_{2})) - \max (f (x_{3}))) = 3, \\ z_{4} & = & \max (0, \min (f (x_{3})) - \max (f (x_{1}), f (x_{2}))) = 0, \\ z_{5} & = & \max (0, \min (f (x_{1}), f (x_{3})) - \max (f (x_{2}))) = 0, \\ z_{6} & = & \max (0, \min (f (x_{2}), f (x_{3})) - \max (f (x_{1}))) = 0, \\ z_{7} & = & \min (f (x_{1}), f (x_{2}), f (x_{3})) = - 2 . \end{matrix}$

So $(C) \int fd μ = \sum_{d = 1}^{7} z_{d} μ_{d} = - 2$ .

The significance of this alternate formula is that the value of the Choquet integral is now expressed as a linear function of the values of μ. Hence, when the data set of the values of the integrand f and the corresponding integration value are available, an algebraic method can be used to estimate the optimal values of μ.

In the following, the translatable Choquet integral of f with respect to a signed efficiency measure is called the Choquet integral for short. A generalized weighted Choquet integral may be expressed by (C) ∫ (a + bf) dμ where μ is a signed efficiency measure, and a = (a₁, a₂, ⋯ a_n), b = (b_l, b₂, ⋯ , b_n) are n-dimensional vectors. We can use it as a projection tools to convert an n-dimensional classification problem to a one dimensional classification problem. We call a and b the matching vectors. They indicate the phase and scaling matching requirements of feature attributes. i.e., they are used to balance the ranges and scales of diverse feature attributes with respective dimensions such that the signed efficiency measure μ can reflect the interaction appropriately.

3 Choquet distances

Based on the Choquet integral, an aggregation tool that projects the feature space onto a real axis is shown. Under the projection, each point in the feature space becomes a value of the virtual variable.

A point f = (f (x₁) , f (x₂) , ⋯ , f (x_n)) in n-dimensional feature space can be regarded as a function defined on X. It represents an observation of the feature attributes.

Equations a₁ + b₁f (x₁) = a₂ + b₂f (x₂) = ⋯ = a_n + b_nf (x_n) represent a straight line in n-dimensional space, denoted by L, which is just a projection axis. Signed efficiency measure μ on P (X) indicates the importance of feature attributes as well as the interaction. Each point f = (f (x₁) , f (x₂) , ⋯ , f (x_n)) in n-dimensional space is projected to L with value c = (C) ∫ (a + bf) dμ.

Definition 5. For any given real number c, set {f ∈ Rⁿ| (C) ∫ (a + bf) dμ = c}, which is a broken-hyperplane in Rⁿ, is called the Choquet broken-hyperplane at c, the intersection with line L is denoted by Q, called the projection point of f on L according to signed efficient measure μ.

Definition 6. Let f₁ = (f₁ (x₁) , f₁ (x₂) , ⋯ , f₁ (x_n)) and f₂ = (f₂ (x₁) , f₂ (x₂) , ⋯ , f₂ (x_n)) are two points in n-dimensional space. According to μ, the project points of f₁, f₂ on L are Q₁, Q₂. Then the Choquet distance of two points f₁, f₂, denoted by C (f₁, f₂), is defined by C (f₁, f₂) = |Q₁Q₂|, where |Q₁Q₂| is the Euclidean distance between two points Q₁ and Q₂ in n-dimensional space.

Theorem 1.For any given pointf, its projection pointQonLhas coordinates are $\frac{c - μ (X) a_{1}}{μ (X) b_{1}}, \frac{c - μ (X) a_{2}}{μ (X) b_{2}}, \dots, \frac{c - μ (X) a_{n}}{μ (X) b_{n}}$ , wherec = (C) ∫ (a + bf) dμ, if μ (X) ≠0 andb_i ≠ 0, i = 1, 2, ⋯ , n.

Proof. From Definition 5, in n-dimensional space, all the points whose Choquet integral value equals to c form a Choquet broken-hyperplane.

If a₁ + b₁f (x₁) ≤ a₂ + b₂f (x₂) ≤ ⋯ ≤ a_n + b_nf (x_n), then the Choquet broken-hyperplane is (μ (X) - μ ({x₂, ⋯ , x_n})) (a₁ + b₁f (x₁)) + (μ ({x₂, ⋯ , x_n}) - μ ({x₃, ⋯ , x_n})) (a₂ + b₂f (x₂)) + ⋯ + μ ({x_n})(a_n + b_nf (x_n)) = c, combining with L : a₁ + b₁f (x₁) = a₂ + b₂f (x₂) = ⋯ = a_n + b_nf (x_n), then coordinates of projection point of f are $\frac{c - μ (X) a_{1}}{μ (X) b_{1}}, \frac{c - μ (X) a_{2}}{μ (X) b_{2}}, \dots, \frac{c - μ (X) a_{n}}{μ (X) b_{n}}$ .

In other cases, we can similarly get the same result, so the coordinates of Q are $\frac{c - μ (X) a_{1}}{μ (X) b_{1}}, \frac{c - μ (X) a_{2}}{μ (X) b_{2}}, \dots, \frac{c - μ (X) a_{n}}{μ (X) b_{n}}$ .

From Theorem 1, the following theorem can be obtained.

Theorem 2.Let two pointsh = (h (x₁) , h (x₂) , ⋯ , h (x_n)) , g = (g (x₁) , g (x₂) , ⋯ , g (x_n)). Then the Choquet distance ofhandgis $C (h, g) = \sqrt{{(\frac{c_{1} - c_{2}}{μ (X)})}^{2} (\frac{1}{b_{1}^{2}} + \frac{1}{b_{2}^{2}} + \dots + \frac{1}{b_{n}^{2}})},$ where c₁ = (C) ∫ (a + bh) dμ, c₂ = (C) ∫ (a + bg) dμ.

Example 1. Let X = {x₁, x₂}. μ ({x₁}) =0.2, μ ({x₂}) =0.5, μ (X) =1, and μ (∅) =0. f = (1, 2) and g = (3, 1/2). a₁ = a₂ = 0, b₁ = b₂ = 1. Then the projection axis is L : x₂ = x₁, (C) ∫ (a + bf) dμ = 1.5, (C) ∫ (a + bg) dμ = 1, the projection point of f is Q_f = (1.5, 1.5), the projection point of g is Q_g = (1, 1), $C (f, g) = \sqrt{0.5}$ .

We can also see that all points whose Choquet integral equals to 1.5 is broken lines L1, and to 1 is broken lines L2, as shown in Fig. 1, they indicate the projection direction on both side of axis L. The broken lines L1 and L2 interact the projection axis L at projection points Q_f and Q_g respectively.

Fig.1

The illustration of Example 1.

Example 2. Let X = {x₁, x₂, x₃}. μ ({x₁}) =0.2, μ ({x₂}) =0.3, μ ({x₁, x₂}) =0.3, μ ({x₃}) =0.5, μ ({x₁, x₃}) =0.6, μ ({x₂, x₃}) =0.9, μ (X) =1, and μ (∅) =0. f = (2, 2, 1/2), g = (-2, - 1, - 1/2). Taking a₁ = 0.2, a₂ = 0.3, a₃ = 0.6, b₁ = 0.1, b₂ = 0.2, and b₃ = 0.8. The projection axis L has equations 0.2 + 0.1x₁ = 0.3 + 0.2x₂ = 0.6 + 0.8x₃, (C) ∫ (a + bf) dμ = 0.82, and (C) ∫ (a + bg) dμ = 0.14. The projection point of f is Q_f = (6.2, 2.6, 0.275), while the projection point of g is Q_g = (-0.6, - 0.8, - 0.575). The distance between f and g is C (f, g) =7.65.

We can also see that all points whose Choquet integral equals to 0.82 is broken-planes S1, and to 0.14 is broken-planes S2, as shown in Fig. 2. The broken-planes S1 and S2 interact the projection axis L at projection points Q_f and Q_g.

Fig.2

The illustration of Example 2.

We can reveal that the Choquet distance can be considered as the generalization of the distance between two corresponding (n-1)-dimensional hyperplanes.

When n = 3, μ is additive, and $\frac{μ ({x_{1}})}{b_{1}} = \frac{μ ({x_{2}})}{b_{2}} = \frac{μ ({x_{3}})}{b_{3}}$ , consider two points f and g in R³.Choqut hyperplane {h ∈ R³| (C) ∫ (a + bh) dμ = (C) ∫ (a + bf) dμ} is a plane orthogonal to axis L, denoted by S1 in Fig. 3. Similarly, Choqut hyperplane {h ∈ R³| (C) ∫ (a + bh) dμ = (C) ∫ (a + bg) dμ} is also a plane orthogonal to axis L, denoted by S2 in Fig. 3 too. Then the Choquet distance C (f, g) with respect to L and μ is just the distance between plane S1 and plane S2. So, we can consider that the Choquet distance is the generalization of the distance between two corresponding (n - 1)-dimensional hyperplanes.

Fig.3

The illustration of Choquet distance when μ is additive and L is orthogonal to Choquet hyperplane in R³.

In order to optimally estimate the values of parameters μ, a, b, the range of the parameters should be classified.

Let u = max (|μ ({x₁}) |, |μ ({x₂}) |, ⋯ , |μ ({X}) |), v = max (|a₁|, |a₂|, ⋯ , |a_n|, |b₁|, |b₂|, ⋯ , |b_n|). Then we can get new parameters $μ^{'} = \frac{μ}{u}, a^{'} = \frac{a}{v}, b^{'} = \frac{b}{v}$ . From Theorem 2, we can get the following theorem easily.

Theorem 3.Given μ, a, andb, let μ′, a′, andb′ be defined above. Then the Choquet distance of two pointshandgwith respect to μ, a, bequals their Choquet distance with respect of μ′, a′, b′.

From Theorem 3, without loss of generality, we can see that the parameters μ, a, b can be restricted in [–1, 1]. These can make us to solve the optimization model in the next section conveniently.

4 The optimiziton models of classification based on the Choquet distance

Now, based on the Choquet distance, we want to find an appropriate aggregation formula that projects the n-dimensional feature space onto a real axis L, such that each point becomes a value of the virtual variable that is optimal with respect to classification. In such a way, the classifying boundary is a Choquet broken-hyperplane.

The weighted Choquet integral projection depends on a, b and signed efficiency measure μ, once these values are available, the n-dimensional classification problem is reduced to a one-dimensional classification problem. We consider a 2-class nonlinear classification problem with classes C₁ and C₂. Suppose that the learning data consist of l₁ sample points f₁, f₂, ⋯ , f_{l
₁} belonging to class C₁ and l₂ sample points g₁, g₂, ⋯ , g_{l
₂} belonging to class C₂. Also, suppose that all of these sample points have the same feature attributes x₁, x₂, ⋯ , x_n.

Now we want to find a Choquet broken-hyperplane, denoted by S, has the equation (C) ∫ (a + bf) dμ = c that can separate classes C₁ and C₂ optimally under a certain criterion. In this model, the signed efficiency measure μ and the projection axis a and b are unknown.

In fact, the successive classification is to find a classifying boundary S, on which the value of Choquet integral of each point is c, such that Choquet broken-hyperplanes {(C) ∫ (a + bf) dμ|f ∈ C₁} and {(C) ∫ (a + bg) dμ|g ∈ C₂} can be separated by c completely. Furthermore, the best classification boundary S, must make the Choquet distance of farthest right (largest) point (denoted by f) of C₁ and the farthest left (smallest) point (denoted by g) of C₂ is maximum. In this way, we can get the classifying boundary, a Choquet broken-heperplane, with form {h ∈ Rⁿ| (C) ∫ (a + bh) dμ = c}, where $c = ((C) \int (a + bf) d μ + (C) \int (a + bg) d μ) / 2 .$

Thus, the first optimal classification model can be given as follows:

Maximize $\begin{matrix} C (f, g) \\ = \sqrt{{(\frac{(C) \int (a + bf) d μ - (C) \int (a + bg) d μ}{μ (X)})}^{2} (\frac{1}{b_{1}^{2}} + \frac{1}{b_{2}^{2}} + \dots + \frac{1}{b_{n}^{2}})} \end{matrix}$

subject to: $\begin{matrix} (C) \int (a + {bf}_{j}) d μ \leq ((C) \int (a + bf) d μ \\ + (C) \int (a + bg) d μ) / 2, j = 1, 2, \dots, l_{1} . \\ (C) \int (a + {bg}_{j}) d μ > ((C) \int (a + bf) d μ \\ + (C) \int (a + bg) d μ) / 2, j = 1, 2, \dots, l_{2} . \end{matrix}$

Now, another optimal model like the Fisher method can be presented. Once a, b and μ are chosen, let f be the point on L such that (C) ∫ (a + bf) dμ is the arithmetic average of {(C) ∫ (a + bh) dμ|h ∈ C₁}. Similarly, g be the point on L such that (C) ∫ (a + bg) dμ is the arithmetic average of {(C) ∫ (a + bh) dμ|h ∈ C₂}. The aim of the classification is to find a projection axis L, which is determined by a and b, and signed efficiency measure μ such that the data sets can be well separated when they are projected onto L. Through learning procedure, a projection axis, L, is found such that C (f, g) is maximum and the sum of the Choquet distance from each point in C₁ to f and the sum of the Choquet distance from each point in C₂ to g are minimized. The second optimal model is expressed as follows. $Maximum \frac{C (f, g)}{\sum_{j = 1}^{l_{1}} C (f_{j}, f) + \sum_{j = 1}^{l_{2}} C (g_{j}, g)}$ subject to $\begin{matrix} (C) \int (a + {bf}_{i}) d μ \\ \leq (\max_{j = 1, 2, \dots, l_{1}} ((C) \int (a + {bf}_{j}) d μ), \\ + \min_{j = 1, 2, \dots, l_{2}} ((C) \int (a + {bg}_{j}) d μ)) / 2, \\ i = 1, 2, \dots, l_{1} . \\ (C) \int (a + {bg}_{i}) d μ \\ > (\max_{j = 1, 2, \dots, l_{1}} ((C) \int (a + {bf}_{i}) d μ), \\ + \min_{j = 1, 2, \dots, l_{2}} ((C) \int (a + {bg}_{j}) d μ)) / 2, \\ i = 1, 2, \dots, l_{2} . \end{matrix}$ i.e. $Minimum \frac{\sum_{j = 1}^{l_{1}} C (f_{j}, f) + \sum_{j = 1}^{l_{2}} C (g_{j}, g)}{C (f, g)}$ subject to $\begin{matrix} (C) \int (a + {bf}_{i}) d μ \\ \leq (\max_{j = 1, 2, \dots, l_{1}} ((C) \int (a + {bf}_{j}) d μ), \\ + \min_{j = 1, 2, \dots, l_{2}} ((C) \int (a + {bg}_{j}) d μ)) / 2, \\ i = 1, 2, \dots, l_{1} . \\ (C) \int (a + {bg}_{i}) d μ \\ > (\max_{j = 1, 2, \dots, l_{1}} ((C) \int (a + {bf}_{j}) d μ) \\ + \min_{j = 1, 2, \dots, l_{2}} ((C) \int (a + {bg}_{j}) d μ)) / 2, \\ i = 1, 2, \dots, l_{2} . \end{matrix}$

If f be the point onto L such that (C) ∫ (a + bf) dμ is the arithmetic average of {(C) ∫ (a + bh) dμ|h ∈ C₁}. From Theorem 1, the coordinates of f are $\sum_{j = 1}^{l_{1}} \frac{c_{j} - μ (X) a_{1}}{l_{1} μ (X) b_{1}},$ $\sum_{j = 1}^{l_{1}} \frac{c_{j} - μ (X) a_{2}}{l_{1} μ (X) b_{2}}, \dots,$ and $\sum_{j = 1}^{l_{1}} \frac{c_{j} - μ (X) a_{n}}{l_{1} μ (X) b_{n}})$ . where c_j = (C) ∫f_jdμ, j = 1, 2, ⋯ , l₁. Thus, anther expression for the second optimal model is given as follows: $\begin{matrix} Minimum \\ \frac{\sum_{j = 1}^{l_{1}} (c_{j} - \sum_{j = 1}^{l_{1}} c_{j} / l_{1})^{2} + \sum_{j = 1}^{l_{2}} (d_{j} - \sum_{j = 1}^{l_{2}} d_{j} / l_{2})^{2}}{(\sum_{j = 1}^{l_{1}} c_{j} / l_{1} - \sum_{j = 1}^{l_{2}} d_{j} / l_{2})^{2}} \end{matrix}$ subject to $\begin{matrix} (C) \int (a + {bf}_{j}) d μ \\ \leq (e_{1} + e_{2}) / 2, j = 1, 2, \dots, l_{1} . \\ (C) \int (a + {bg}_{j}) d μ \\ > (e_{1} + e_{2}) / 2, j = 1, 2, \dots, l_{2} . \end{matrix}$ where $\begin{matrix} c_{j} & = & (C) \int (a + {bf}_{j}) d μ, j = 1, 2, \dots, l_{1}, \\ d_{j} & = & (C) \int (a + {bg}_{j}) d μ, j = 1, 2, \dots, l_{2}, \\ e_{1} & = & \max_{j = 1, 2, \dots, l_{1}} (c_{j}), \\ e_{2} & = & \min_{j = 1, 2, \dots, l_{2}} (d_{j}) . \end{matrix}$

When μ is additive and the projection axis is orthogonal to classifying boundary, the second optimal model can be considered as a generalization form of Fisher linear classification.

5 Applications

In this section, some data classification’s examples, which are nonlinear classification problems, are given to show that the above optimal models based on Choquet integral are effective.

Fig.4

The data of Example 3.

Example 3. The 2-dimensional data records are given in Fig. 4, ∘ for class1 and + for class2. The two classes can not be classified by linear function. The classification results, which can be solved by fmincon function of MATLAB, are shown in Fig. 5. The detail results are μ ({x₁}) = -125/10016, μ ({x₂}) =109/2253, and μ ({x₁, x₂}) = -545/6953. The projection axis L is -557/963 - (688/1087) x₁ = -2737/4742 + (859/1549) x₂ . The classification boundary are two broken lines. The Choquet integral value of classification boundary is 164/731, and the coordinates of joint point is 3482/965, and –2291/556.

Fig.5

The classification of Example 3.

Example 4. The 2-dimensional data records are given in Fig. 6, ∘ for class1 and + for class2. The classification results are shown in Fig. 7. The detail results are μ ({x₁}) =729/2350, μ ({x₂}) =1565/3819, μ ({x₁, x₂}) =185/7483, and projection axis L is 667/1768 - (911/1505) x₁ = 293/1160 + (1209/1814) x₂. The Choquet integral value of classification boundary is 480/1753, and the coordinates of joint point is –4118/233 and 5099/314.

Fig.6

The data of Example 4.

Fig.7

The classification of Example 4.

Example 5. The 3-dimension data records are given in Fig. 8, + for class1 and ∘ for class2. Figure 9 shows the classification results by optimal models based on Choquet integral. The detail results are μ ({x₁}) = -441/3232, μ ({x₂}) =641/1510, μ ({x₁, x₂}) = 251/1973, μ ({x₃}) =1809/3193, μ ({x₁, x₃}) = 1171/2076, μ ({x₂, x₃}) =1462/1475, μ ({x₁, x₂, x₃}) =471/529, and projection axis L is: 259/1353 - (929/1389) x₁ = 2076/2077 + (6211/6348) x₂ = 472/821 + (3507/4477) x₃. The classification boundary is Choquet broken-plane. The Choquet integral value of classification boundary is 335/414, and the coordinates of joint point is –709/661, –443/4779 and 503/1180.

Fig.8

The data of Example 5.

Fig.9

The classification of Example 5.

In Fig. 10 the horizontal ordinate is the Choquet integral value of each record, and vertical ordinate is the ordinal number of each record. The dividing line is the Choquet integral value of classifying boundary. From Fig. 10, we can see that the records can be divided effectively.

Fig.10

The classification of Example 5.

Example 6. The Iris Data. To investigate different types of iris, people collect its 150 flowers and measure their sepal length, sepal width, petal length, and petal width. Iris data set has 4 attributes and 150 records. In paper [13], the error classification number is 3. Using the proposed optimal models based on Choquet integral in the paper, The error classification number is 0. The 3-classification can be transferred two 2-classification.

Firstly, as shown in Fig. 11, class1 and the other two classes can be classified, but class2 and class3 can not be classified. The detail results are μ ({x₁}) = -637/5412, μ ({x₂}) = -212/309, μ ({x₃}) =445/ 654, μ ({x₄}) =1639/2891, μ ({x₁, x₂}) = -1147/3246, μ ({x₁, x₃}) =212/419, μ ({x₁, x₄}) =788/2301, μ ({x₂, x₃}) = -333/415, μ ({x₂, x₄}) =524/1635, μ ({x₃, x₄}) =1355/1508, μ ({x₁, x₂, x₃}) = -2770/3533, μ ({x₁, x₂, x₄}) = -331/727, μ ({x₁, x₃, x₄}) =1168/1821, μ ({x₂, x₃, x₄}) =97/148, μ ({x₁, x₂, x₃, x₄}) = -38/32467.

Fig.11

The classification of Iris data for the class1 and class2, class3.

The projection axis L is -586/1759 + 1013/17768 x₁ = -1761/3484 + 267/1615 x₂ = -699/2588 + 313/4355x₃ = -551/2339 + 340/1731x₄. The Choquet integral value of the classification boundary is 8/118649. Being the Choquet integral values of the records are very close, so each value times a constant p = 3247/471 in order to show well in Fig. 11.

Secondly, holding the same projection axis and using the optimal model based on Choquet integral again, class2 and class3 can be classified effective in Fig. 12. The detail results are μ ({x₁}) =2533/14894, μ ({x₂}) = -101/112, μ ({x₃}) =1959/4105, μ ({x₄}) =901/1721, μ ({x₁, x₂}) = -1019/2230, μ ({x₁, x₃}) =305/806, μ ({x₁, x₄}) =130/3087, μ ({x₂, x₃}) = -488/1559, μ ({x₂, x₄}) =590/1489, μ₍ {x₃, x₄}) =287/1035, μ ({x₁, x₂, x₃}) =231/2243, μ ({x₁, x₂, x₄}) = -2936/5489, μ ({x₁, x₃, x₄}) =645/1813, μ ({x₂, x₃, x₄}) = -587/641, μ ({x₁, x₂, x₃, x₄}) =667/2168. The Choquet integral values of the classifying boundary are –38/803 and 397/11005. Each Choquet integral value times a constant p = 8503/357 in order to show well in Fig. 12.

Fig.12

The classification of Iris data.

In order to reduce the parameters of the problem, the projection axis is considered to across the center of all records. In this restriction, the projection axis can be obtained just solving b, which can reduce 4 unknown parameters. As shown in Fig. 13, class1 and the other two classes can be classified. The detail results are μ ({x₁}) = -767/3175, μ ({x₂}) = -1837/21899, μ ({x₃}) = -968/35353, μ ({x₄}) = -157/2588, μ ({x₁, x₂}) = -403/1145, μ ({x₁, x₃}) = -82/1781, μ ({x₁, x₄}) =154/4339, μ ({x₂, x₃}) = -991/3486, μ ({x₂, x₄}) =873/7688, μ ({x₃, x₄}) =61/1850, μ ({x₁, x₂, x₃}) = -485/2292, μ ({x₁, x₂, x₄}) = -47/336, μ ({x₁, x₃, x₄}) =857/2918, μ ({x₂, x₃, x₄}) =2600/12381, μ ({x₁, x₂, x₃, x₄}) =1371/1400 . and the projection axis L is -16851pt/1pt2627 + (209/1904) x₁ = -111/112 + (377/1163) x₂ = -561/1117 + (400/ 2993) x₃ = -1165/2696 + (717/1990) x₄. The Cho-quet integral value of the classifying boundary is –1039/3415. By a way, being the Choquet integral values of the records are very close, so each value times a constant p = 2309/367 in order to show well in Fig. 13.

Fig.13

The classification of Iris data for the class1 and class2, class3.

Similarly, holding the same projection axis and using the optimal model based on Choquet integral again, class2 and class3 can be classified effective in Fig. 14. The detail results are μ ({x₁}) =363/2954, μ ({x₂}) = -1185/1207, μ ({x₃}) =646/1279, μ ({x₄}) = 1109/1838, μ ({x₁, x₂}) = -440/1021, μ ({x₁, x₃}) =419/1129, μ ({x₁, x₄}) =154/3645, μ ({x₂, x₃}) = -303/968, μ ({x₂, x₄}) =487/1229, μ ({x₃, x₄}) =249/872, μ ({x₁, x₂, x₃}) =683/6608, μ ({x₁, x₂, x₄}) = -937/1792, μ ({x₁, x₃, x₄}) = 1373/3840, μ ({x₂, x₃, x₄}) = -596/ 1941, μ ({x₁, x₂, x₃, x₄}) =1696/5423 .

Fig.14

The classification of Iris data.

The Choquet integral values of the classifying boundary are –310/4431 and 433/6227. Each Choquet integral value times a constant p = 3963/406 in order to show well in Fig. 14.

6 Conclusion

In this paper, the Choquet distances between two points in Rⁿ are given. According to the Choquet distance, two optimal classification models are proposed. From the applications shown in this work, we can see that the models are effective and useful. Of course, there are some topics to be studied deeply. The number of unknown parameters is large. If the attributes number is n, then the number of unknown parameters may be at the level of 2ⁿ, such that the complexity of the calculation is very high. How to reduce the number of parameters is a very important topic to explore. Using k-interactive measures and/or hierarchical method is a feasible way.

Footnotes

Acknowledgments

This work is partially supported by National Natural Science Foundation of China (Grant No. 11501435), Scholarship Fund for Studying Abroad by China Scholarship Council, Scientific Research Program Funded by Shaanxi Provincial Education Department (Program No. 12JK0878) and Science and Technology Plan Project Funded by Science and Technology Bureau of Xi’an City (Program No. CXY1441(2)).

References

Tehrani

, Cheng

, Dembczynski

and Hüllermeier

, Learning monotone nonlinear models using the Choquet, Mach Learn89 (2012), 183–211.

Abdallah

A.C.B.

, Frigui

and Gader

, Adaptive local fusion with fuzzy integrals, IEEE Transaxtions on Fuzzy Systems20(5) (2012), 849–864.

Cortes

and Vapnik

, Support-vector networks, Machine Learning20 (1995), 273–297.

Schmitt

, Bombardier

and Wendling

, Improving fuzzy rule classifier by extracting suitable features from capacities with respect to the choquet integral, IEEE Trans Syst, Man, Cybern B, Cybern38(5) (2008), 1195–1206.

Choquet

, Theory of capacities, Annales de l’Institut Fourier5 (1954), 131–295.

Fang

, Rizzo

, Wang

, Espy

and Wang

, A new nonlinear classifier with a penalized signed fuzzy measure using effective genetic algorithm, Pattern Recognition43(4) (2010), 1393–1401.

Tahani

and Keller

J.M.

, Information fusion in computer vision using the fuzzy integral, IEEE Tr on Systems, Man, and Cybernetics20(3) (1990), 733–741.

Chu

, Wang

and Shi

, Analysis to the Contribu-tions from Feature Attributes in Nonlinear Classification Based on the Choquet Integral, 2010 IEEE International Conference on Granular Computing (GrC), San Jose, 2010, pp. 677–682.

Keller

J.M.

, Qiu

and Tahani

, The fuzzy integral and image segmentation, In North Amer Fuzzy Information Proc Soc, New Orleans, 1986, pp. 324–339.

10.

Quinlan

J.R.

, Induction of decision tree, Machine Learning (1) (1986), 81–106.

11.

Quinlan

J.R.

, C4. 5: Programs for Machine Learning. [S. 1.]: Morgan Kaufman1993.

12.

Jing

, Liu

, Cai

and Chen

, Sparse representation and fisher discrimination based method for tumor classification, Journal of Computational & Theoretical Nanoscience13(1) (2016), 343–348.

13.

, Wang

, Heng

and Leung

, Classification by nonlinear integral projections, IEEE Transactions on Fuzzy Systems11(2) (2003), 187–201.

14.

Mikenina

and Zimmermann

H.J.

, Improved feature selection and classification by the 2-Additive fuzzy measure, Fuzzy Sets and Systems107(2) (1999), 197–218.

15.

Grabisch

and Sugeno

, Fuzzy integrals and dual measures: Application to pattern classification, In Sino-Japan Joint Meeting on Fuzzy Sets & Systems, Beijing, China, 1990.

16.

Grabisch

and Sugeno

, Multi-Attribute Classification Using Fuzzy Integral, IEEE International Conference on Fuzzy System, San Diego, 1992, pp. 47–54.

17.

Grabisch

and Nicolas

J.M.

, Classification by fuzzy integral: Performance and tests, Fuzzy Sets System65(2-3) (1994), 255–271.

18.

Grabisch

, Fuzzy Integral for Classification and Feature Extraction. in Fuzzy Measures and Integrals: Theory and Applications, Physica Verlag, 2000, pp. 415–434.

19.

Yan

, Chen

, Shi

, Wang

and Huang

, Using non-additive measure for optimization-based nonlinear classification, American Journal of Operations Research2 (2012), 364–373.

20.

Yang

, Wang

, Heng

P.A.

and Leung

K.S.

, Classification of heterogeneous fuzzy data by Choquet integral with fuzzy-valued integrand, IEEE Trans Fuzzy Syst15(5) (2007), 931–942.

21.

Gallant

S.I.

, Perceptron-based learning algorithms, IEEE Transactions on Neural Networks1(2) (1990), 179–191.

22.

Leonard

and Hsu

J.S.J.

, Bayesian methods: An analysis for statisticians and interdisciplinary researchers, Cambridge University Press, 1999.

23.

Liu

, Ma

and Mathew

, Machinery fault diagnosis based on fuzzy measure and fuzzy integral data fusion techniques, Mechanical Systems and Signal Processing3(23) (2009), 690–700.

24.

Wang

, Wang

, Feng

and Wang

, A new approach to classifier fusion based on upper integral, IEEE Transactions on Cybernetics44(5) (2014), 620–635.

25.

Wang

, Leung

K.S.

and Klir

G.J.

, Applying fuzzy measures and nonlinear integrals in data mining, Fuzzy Sets and Systems156(3) (2005), 371–380.

26.

Wang

, Yang

and Leung

, World Scientific Publishing, Nonlinear Integrals and Their Applications in Data Mining, New Jersey, 2010.