Completing an uncertainty criterion of classification

Mathware & Soft Computing 12 (2005) 83-95 Completing an Uncertainty Criterion of Classification J. Abell´an Dpto. Ciencias de la Computaci´on e I.A. Univ. Granada, ETSI Inform´atica, 18071 Granada - Spain [email protected] Abstract We present a variation of a method of classification based in uncertainty on credal set. Similarly to its origin it use the imprecise Dirichlet model to create the credal set and the same uncertainty measures. It take into account sets of two variables to reduce the uncertainty and to seek the direct relations between the variables in the data base and the variable to be classified. The success are equivalent to the success of the first method except in those where there are a direct relations between some variables that decide the value of the variable to be classified where we have a notable improvement. Keywords. Imprecise probabilities, uncertainty, imprecision, non-specificity, classification, classification trees, credal sets. 1 Introduction A classic application of the theory of probability is the task of classification, a typical machine learning task, where we have an incoming set of observations, called the training set, and generally we want to obtain a set of rules to assign to any new set of observations one value of the variable to classify. The set used to assess the quality of this set of rules is also called the test set. It has notable applications in medicine, recognition of hand-written characters, astronomy, banks, etc... The learned classifier can be represented as a Bayesian network, a neural network, a classification tree, etc... Normally, these methods use the theory of Probability to estimate the parameters with a stopping criterion to limit the complexity of the classifier and to avoid overfitting. In this paper, we will use the theory of imprecise probabilities to build a classification tree. A classification tree is a structure easy to understand and is an efficient classifier. It has its origin in ID3 algorithm by Quinlan [16]. A basic reference is the book by Breiman et al. [6]. Here, we also apply decision trees for classification, but as in Zaffalon [23], the imprecise Dirichlet model is used to estimate the probabilities of belonging to the respective classes defined by the variable to be classified. 83 84 J. Abell´an In Abell´an and Moral [2, 3], we have studied how to measure the uncertainty of a credal set generalizing the measures used in the theory of evidence [8, 18]. We consider two main sources of uncertainty: entropy and non-specificity. We have proved that the proposed functions verify the most basic properties of this type of measures (Abell´an and Moral [3], Dubois and Prade [10], Klir and Wierman [13]). In the first method [5] we started with an empty tree and selecting, in each step, a node and a variable to branch with a greater decreasing in the final entropy of the variable to be classified. In classical probability a branching always implies a decreasing of the entropy. So, it is necessary to include an additional criterion not to create too complex models with over-fitting to the data. With credal sets, a branching will produce a lower entropy but, at the same time, a greater nonspecificity. In these conditions, we followed the same procedure as in probability theory, but measuring the total uncertainty of a branching. The stopping criterion was very simple: when every possible branching produces an increment of the total uncertainty (the entropy decrement does not compensate the increment of non-specificity). Finally to carry out the classification in front of a set of observations, we used a strong dominance criterion to obtain the value of the variable to classify. The new method quantify the uncertainty of each individual variable in each node of the same way and the uncertainty of the sets of two variables jointly. Going into the node the variable that most reduce the uncertainty belonging to the individual calculations or to the double calculations. So is in the last case go into the variable of the pair that more reduce the uncertainty in an individual way. This method improve one that make go in set of two variables in a node. It allows to see the future uncertainty before to branching. In Section Two we present necessary previous concepts on uncertainty on credal sets. In Section Three we introduce notations and definitions previous to the method. In Section Four we describe in detail our method. In Section Five we will test our procedure with known data sets used in classification and we will make an studio of an artificial database that allows us to know the advantages our new method has. 2 Total Uncertainty on Credal Sets Theory of evidende is based on the concept of basic probability assignment, and this defines a special type of credal set [8, 18]. In this theory, Yager [22] distinguishes two types of uncertainty. One is associated with cases where the information is focused in sets with empty intersections and the other is associated with cases where the information is focused in sets with cardinality over one. We call them randomness and non-specificity respectively. Since we consider that a general convex set of probability distributions (a credal set) may contain the same type of uncertainty as a b.p.a., we consider similar randomness and non-specificity measures on it. In Abell´an and Moral [3], we have defined a measure of non-specificity for convex sets that generalizes Dubois and Prade’s measure of non-specificity in the theory of evidence [9]. Using the M¨obius inverse function for monotonic capacities [7], we Completing an Uncertainty Criterion of Classification 85 can define: Definition 1 Let Pbe a credal set on a frame X. We define the following capacity function, fP(A) = inf P∈P P(A),∀A∈℘(X), where ℘(X)is the power set of X. Definition 2 For any mapping fP:℘(X)→IR another mapping mP:℘(X)→IR can be associated by mP(A) = X B⊂A (−1)|A−B|fP(B),∀A∈℘(X), This correspondence is one-to-one, since conversely, we can obtain fP(A) = X B⊂A mP(B),∀A∈℘(X), as we can see in Shafer [18], who calls the correspondence M¨obius inversion. Definition 3 Let Pbe a credal set on a frame X,fPits minimum lower probability as in Definition 1 and let mPbe its M¨obius inverse. We say that function mPis an assignment of masses on P. Any A∈Xsuch that mP(A)6= 0 will be called a focal element of mP. Now, we can define a general function of non-specificity. Definition 4 Let Pbe a credal set on a frame X. Let mPbe its associated assignment of masses on P. We define on Pthe following function of non-specificity: IG(P) = X A⊂X mP(A) ln(|A|). In Abell´an and Moral [4], we have proposed the following measure of randomness for general credal sets GG(P) = Max (−X x∈X pxln px) where the maximum is taken over all probability distributions on P,and Pis a general credal set. This measure generalizes the classical Shannon’s measure [19], for Dempster-Shafer’s theory verifying similar properties. It can be used as one of the components of measure of total uncertainty, Harmanec and Klir [12]. We have proved that this function is also a good randomness measure for credal sets and verifies all the basic properties that were verified in Dempster-Shafer’s theory [4]. We define a measure of total uncertainty as T U(P) = IG(P) + GG(P). This measure could be modified by the factor introduced in Abell´an and Moral [2], but this will not be considered here, due to its computational difficulties (it is a supremum that is not easy to compute). The properties of this measure are studied in Abell´an and Moral [3, 4] and these are similar to the properties verified by total uncertainty measures in Dempster-Shafer’s theory [15]. 86 J. Abell´an 3 Notation and previous definitions For a classification problem we shall consider that we have a data set Dwith values of a set Lof discrete variables {Xi}n 1called attribute variables. Each variable will take values or states on a finite set ΩXi={x1 i, x2 i, ..., x|ΩXi| i}. Our aim will be to create a classification tree on the data set Dof one target variable C, with values or attributes in ΩC={c1, c2, ..., c|ΩC|}. Definition 5 Let {Xi}n 1be a set of discrete variables with values in the finite sets ΩXi, respectively. We call a configuration of {Xi}n 1any m-tuple (Xr1=xtr1 r1, Xr2=xtr2 r2, ..., Xrm=xtrm rm), where xtrj rj∈Ωrj,j∈ {1, ..., m},rj∈ {1, ..., n}and rj6=rhwith j6=h. That is, a configuration is an assignment of values for some of the variables in {Xi}n 1. Definition 6 Given a data set and a configuration σof set {Xi}n 1we consider the credal set Pσ Cfor variable Cwith respect to σdefined by the set of probability distributions, p, such that pj∈nσ cj N+s,nσ cj+s N+s, for every j∈ {1, ..., |ΩC|}, obtained on the basis of the imprecise Dirichlet model, Walley [21], for a generic state cj∈ΩC. Here nσ cjis the number of occurrences of the configuration {C=cj} ∪ σin the data set, Nis the number of observations compatible with configuration σand s > 0is a hyperparameter. We denote this interval as P(cj|σ), P(cj|σ). This parameter sdetermines how quickly the lower an upper probabilities converge as more data become available, larger values of sproduce more cautious inferences. Walley [21] suggests a candidate value for sbetween s= 1 and s= 2, but no definitive statement is given. 4 Exposition of the method 4.1 Classification procedure In a similar way that we build our classification tree in the simple method, Abellan and Moral [5], we will build our new method. A classification tree is a tree where each interior node is labeled with an attribute variable of the data set Xjwith a child for each one of its possible values: Xj= xt j∈ΩXj. In each leaf node, we shall have a credal set for the variable to be classified, Pσ C, as defined above, where σis the configuration with all the variables in the path from the root node to this leaf node, with each variable assigned to Completing an Uncertainty Criterion of Classification 87 the value corresponding to the child followed in the path. This method can be described using the following points: I. We start with an empty tree. We calculate the minimum of the following values: α= min Xi∈L   X r∈{1,..,|ΩXi|} ρ{xr i}TU(P{xr i} C)  , β= min Xi,Xj∈L   X r∈{1,..,|ΩXi|},t∈{1,..,|ΩXj|} ρ{xr i,xt j}TU(P{xr i,xt j} C)  , with ρxr ithe relative frequency of xr i,ρ{xr i,xt j}the relative frequency of {xr i, xt j} and Lthe list of attribute variables in the data base. This value should be less than TU(P∅ C). In other case, the classification tree will have an only node with P∅ Cand the classification will take into account only the frequency of the states of the variable in classification, and not the values of the rest of the variables. If α≤βwe choose with root node the variable that attains this minimum, in other case we have a pair of attribute variables and we choose of them the one with minimum value of uncertainty in an individual way as in αvalue. II. For each node already generated, we compute the total uncertainty of the credal set associated to the configuration, σ, of the path from the root node to that node: T U(Pσ C). Again we calculate the minimum value of Then we find the variable Xi0with the value: α0= min Xi∈L∗  X r∈{1,..,|ΩXi|} ρσ∪{xr i}TU(Pσ∪{xr i} C)   β0= min Xi,Xj∈L∗  X r∈{1,..,|ΩXi|},t∈{1,..,|ΩXj|} ρσ∪{xr i,xt j}TU(Pσ∪{xr i,xt j} C)  , where L∗is the set of attribute variables of the data set minus those that appear in the way from the actual node to the root node. That is, in a node with a configuration σ, we compute for each attribute variable the weighted average of the total uncertainty of the leaves associated to the branching for this variable, where the weights are the frequencies of occurrence of the different values of the variable under configuration σ. Then, we take the variable Xi0, with minimum value of total uncertainty after branching in a similar sense as in the choose of root node. If this value is lower than the total uncertainty before branching TU(Pσ C), this node is labeled with Xi0and a branch is added for each one of its children. The process will be repeated for each one of them. 88 J. Abell´an III. If there is no attribute variable that reduces the uncertainty or L∗is empty, then this node will be a leaf and will contain the credal set associated to the configuration with the values of the variables in the path from the root node to this leaf. The original method [5] need the same points, but only the calculation of αand α0no of βand β0. This variation make the method finds some relations between variables for the first method that the new method finds by its construction. The new method is a natural extension of the first. This way to introduce an attribute variable in a node can improve the one that introduce two attribute variables in that node because it is posible that for a case of the variable the uncertainty can obtain a reduction major than with its pair in the optimum. This allows us to continue reducing the uncertainty. 4.2 Decision in the leaves To classify a new case with observations in all the attribute variables except in the variable to be classified C, then we start in the root of the tree and follow the path corresponding to the observed values of the variables in the interior nodes of the tree, i.e., if we are in a node with variable Xiand this variable takes the value xr i in the set of observations, then we choose the child corresponding to this value. This process is followed till we arrive to a leaf node. Then, we use the associated credal set about Cto obtain a value for this variable. We will use a strong dominance criterion on C. This criterion generally implies only a partial order, and in some situations, no possible precise classification can be done. We will choose an attribute of the variable C=chif it verifies that ∀i6=h P(ci|σ)< P(ch|σ) When there is no value dominating all other possible values of C, the output can be the set of non-dominated cases (cases cifor which there is not another case chverifying above inequality). In this way, we obtain what Zaffalon [24] calls a credal classifier, in which for a set of observations we obtain a set of possible values for the variable to classify, non-dominated cases, instead of an unique prediction. (In the experiments, when there is not a dominant value, we simply do not classify, without calculating the set of non-dominated attributes. This implies to lose some valuable information in some situations.) This avoid the loss of information that we have if no classify some cases where there is a major frequency in two cases and cero in the others as occur in Cleveland, where our method has a high grade of no classified cases. As we will see, we want to compare our methods with another already known. These methods classify all the record of the training and test sets. They no have a rule of rejected data set. So for comparing with these methods we also use a dominance criterion based on frequency of the data, i.e., we will choose an attribute of the variable to be classified with mayor frequency, but this could produce an overfitting on the data base to training, as we will see in Table 5. Completing an Uncertainty Criterion of Classification 89 An alternative criterion for classification is credal dominance [24] called also strict preference [20]. This criterion is based in comparing the probability of the two cases for each one of the probabilities of the credal set. Strong dominance implies credal dominance, but the converse is not true: there are situations in which there is credal dominance but not strong dominance. However, in this particular case in which we have credal sets that are defined by reachable intervals for the values of the variable to classify it is easy to prove that both criteria are equivalent. 5 Experimentation We have applied this method to some known data sets, obtained from the Uci Repository of Machine Learning Databases (we can find them in the direction http://www.sgi.com/Technology/mlc/db) with the parameter less conservative s= 1, since with s > 1 we obtained a high degree of non-classified data in some databases (though with a greater percentage of correct classifications). The data sets Breast,Breast Cancer,Heart,Hepatitis and Cleveland (medical); Vote1 (political); Australian (banking); Soybean-small (botanical) and Monks1 (artificial). These databases were used by Acid [1]. Some of the original data sets have observations with missing values and in some cases, some of the variables are not discrete. The cases with missing values were removed and the continuous variables have been discretized using MLC++ software, available in http://www.sgi.com/ Technology/mlc. The measure used to discretize them have been the entropy. The number of intervals is not fixed, and it is obtained following Fayyad and Irani [11] procedure. Only the training part of the database was used to determine the discretization procedure. In Table 1 there is a brief description of these databases. We can see the number of cases of the training set (N. Tr), of the test set (N. Ts), number of variables in the database (N. variables) and the number of different values of the variable to be classified (N. classes). In general, when there is not a case dominating all the other possible values of the variable to classify, we simply does not classify this individual. Algorithms have been implemented using Java language version 1.1.8. The obtained percentages of correct classifications with the simple model can be seen in Table 2. The Training column is the percentage of correct classifications in the data set that was used for learning. In UC(T r) column we have the percentage of rejected cases, i.e., the observations that were not classified by the method due to the fact that no value verifies the strong dominance criterion, and in UC(Ts) column we have the rejected cases in the test set. The success rate can be improved if we had used s= 2, though the percentage of rejected observations will be also increased. As we can see in Table 2 there is no overfitting (one of the most common problems of learning procedures): the success of the training set and the test set are very similar. Only database Cleveland has a high rate of non-classified data. This is the case with the highest number of cases of the variable to classify and then it is 90 J. Abell´an Data base N. Tr N. Ts N. variables N. classes Breast Cancer 184 93 9 2 Breast 457 226 10 2 Cleveland nominal 202 99 7 5 Cleveland 200 97 13 5 Pima 512 256 8 2 Heart 180 90 13 2 Hepatitis 59 21 19 2 Vote1 300 135 15 2 Australian 460 230 14 2 Soybean-small 31 16 21 4 Table 1: Description of the databases Data base Training UC(Tr) Test UC(Ts) Breast Cancer 75.5 0.0 81.7 0.0 Breast 98.0 1.3 96.9 0.9 Cleveland nominal 62.7 4.4 66.0 5.0 Cleveland 72.8 21.0 69.9 24.7 Pima 79.7 0.2 80.5 0.0 Heart 92.2 7.2 95.2 6.7 Hepatitis 96.4 5.0 94.7 9.5 Vote1 96.1 6.6 96.9 5.9 Australian 92.3 3.4 91.0 3.4 Soybean-small 100.0 0.0 100.0 0.0 Table 2: The measured experimental percentages of the simple method more difficult to obtain a class dominating all the other values. In this case, we would have obtained more information by changing the output to a set of nondominated cases. In most of the other databases, the variable to be classified has two possible states and in this situation our classification is equivalent to the set of non-dominated values. In Table 3 we compare the results with another known methods with good behavior on the same databases, Acid [1]. We have used the same sets of training and test that the used for this experiments. The NB-columns correspond to results of the Naive Bayesian classifier on the Training set and the Test set. This known method is based on the conditional independence of the variables given the variable to be classified. Similarly, the C4.5-columns correspond to the Quinlan’s method [17], based on ID3 [16], where a classification tree with classical precise probabilities is used. It is possible to obtain a implementation of this method in http://www.sgi.com/Technology/mlc. Completing an Uncertainty Criterion of Classification 91 Data set NB(Tr) NB(Ts) C4.5(Tr) C4.5(Ts) Breast Cancer 78.2 74.2 81.5 75.3 Breast 97.8 97.3 97.6 95.1 Cleveland nominal 63.9 57.6 69.3 51.5 Cleveland 78.0 50.5 73.5 54.6 Pima 76.4 74.6 79.9 75.0 Heart 87.8 82.2 83.3 75.6 Hepatitis 96.2 81.5 96.2 85.2 Vote1 87.6 88.9 94.5 88.3 Australian 87.6 86.1 89.3 83.0 Soybean-small 100 93.8 100 100 Table 3: Percentages of another methods Data base Training UC2(Tr) Test UC2(Ts) Breast Cancer 75.5 0.0 81.7 0.0 Breast 98.0 1.3 96.9 0.9 Cleveland nominal 64.6 5.0 68.8 6.1 Cleveland 72.8 21.0 69.9 24.7 Pima 79.7 0.2 80.5 0.0 Heart 91.7 6.1 94.1 5.6 Hepatitis 96.4 5.0 94.7 9.5 Vote1 96.1 6.6 96.9 5.9 Australian 90.8 0.6 89.0 0.9 Soybean-small 100.0 0.0 100.0 0.0 Table 4: The measured experimental percentages with the strong dominance criterion with the new model We report the results obtained by Acid [1]. We can see that there is overfitting in these methods, principally in C4.5 being specially notable in some data sets (Cleveland nominal,Cleveland,Hepatitis. Now, we can see the success of our extended method in Table 4 and Table 5. In the first we have the success with strong dominance criterion and in the second we have the mayor frequency criterion, i.e., with all the cases classified (0% of rejected cases), to compare it with the models C4.5 and Naive Bayes. As we can see in Table 4, there is a little variation with respect to to simple method, though we must into account that the simple method branching if the uncertainty is equal to the node actual. There is a high percentage of no classified in data base Cleveland where the variable to be classified have 5 posible states. We can think that our method fails, but we do not have an avoid of information because there is a lot of cases where