Data Set Editing by Ordered Projection

Data Set Editing by Ordered Projection Jes´us S. Aguilar, Jose ´ C. Riquelme and Miguel Toro Departamento de Lenguajes y Sistemas Inform ´aticos, Facultad de Inform ´atica, Universidad de Sevilla, Avda. Reina Mercedes s/n. 41012 Sevilla, Spain E-mail: {aguilar,riquelme,mtoro}@lsi.us.es Abstract. This paper presents a new approach to data set editing. The algorithm (EOP: Editing by Ordered Projection) has some interesting characteristics: important reduction of the number of examples from the database; lower computational cost (O(mn log n)) with respect to other typical algorithms due to the absence of distance calculations; conservation of the decision boundaries, especially from the point of view of the application of axis-parallel classifiers. The performance of EOP is analysed in two ways: percentage of reduction and classification. EOP has been compared to IB2, ENN and SHRINK concerning the percentage of reduction and the computational cost. In addition, we have analysed the accuracy of k-NN and C4.5 after applying the reduction techniques. An extensive empirical study using databases with continuous attributes from the UCI repository shows that EOP is a valuable preprocessing method for the later application of any axis-parallel learning algorithm. Keywords: Data mining, preprocessing techniques, data set editing, axis-parallel classifiers 1. Introduction The data mining researchers, especially those dedicated to the study of algorithms that produce knowledge in some of the usual representations (decision lists, decision trees, association rules, etc.), usually make their tests on standard and accessible databases (most of them of small size). The purpose is to verify and validate independently the results of their algorithms. Nevertheless, these algorithms are modified to solve specific problems, for example real databases that contain much more information (number of examples) than standard databases used in training. To accomplish the final tests on these real databases with tens of attributes and thousands of examples is a task that takes a lot of time and memory size. Among all the methodologies used by data mining researchers, those based on axis-parallel classifiers are the most common. These have an important advantage: they are classifiers that provide easy-to-understand decision rules by humans and are very useful for the expert interested in getting knowledge from the database. The C4.5 tool [9] is probably the most useful system of this type. It is advisable to apply to the databases preprocessing techniques to reduce the number of examples or the number of attributes in such a way as to decrease the computational cost. These preprocessing techniques are fundamentally oriented to one of the next goals: editing (reduction of the number of examples by eliminating some of them or calculating prototypes) and feature selection (eliminating non-relevant attributes). Our algorithm belongs to the first group. Editing methods are related to the nearest neighbours (NN) techniques [4]. Some of them are briefly cited in the following lines. Hart [5] proposed to include in the subset S those examples of the training set T whose classification with respect to S are wrong using the nearest neighbour technique, so that everymember of T is closer to a member of S of the same class than to a member of S of a different class; Aha et al. [2] proposed a variant of Hart’s method; Wilson [13] proposed to eliminate the examples with incorrect k-NN classification, so that each member of T is removed if it is incorrectly classified with the knearest neighbours; Tomek [11] extended the idea of Wilson eliminating the examples with incorrect classification from any i=1to k, where kis the maximum number of neighbours to be analysed; the work of Ritter [10] extended Hart’s method and every member of T must be closer to a member of S of the same class than to any member of T. Other variants are based on Voronoi diagrams [8], Gabriel neighbours (two examples are said to be Gabriel neighbours if their diametrical sphere does not contain any other examples) or relative neighbours [12] (two examples pand qare relative neighbours if for all other examples xin the set, is true the expression dist(p, q)<max{dist(p, x),dist(q,x)}. All of these techniques need to calculate distances between examples, which is rather time consuming. If n examples with m attributes are considered, the first methods take O(mn2) time, the Ritter’s algorithm is O(mn2+n3); the Voronoi neighbours, Gabriel neighbours and relative neighbours are O(mn3). In this paper we present an algorithm, called EOP (Editing by Ordered Projection), which has some important characteristics: –Considerable reduction of the number of examples. –Lower computational cost O(mn log n)than other algorithms. –Absence of distance calculations. –Conservation of the decision boundaries, especially interesting for applying classifiers based on axis-parallel decision rules (like C4.5). We have dealt with several databases from the UCI repository [3]. To show the performance of our method we have used k-NN and C4.5 before and after applying EOP. Among the most known editing methodswehavechosenIB2[2], ENN[13]andSRHINK[7]. A10-fold crossvalidationforeachmethod is achieved to reduced the databases. Afterwards, we have used the 1-NN to show the classification accuracy of the reduced sets using the original tests. In addition, C4.5 generates the decision trees from the reduced sets and they are proved with the original tests. Several tables with computational costs, percentages of reduction and classification accuracy for 1-NN, 3-NN, 5-NN and C4.5 are summarised in the experiment section. 2. Description of the algorithm If we choose a region where all examples inside have the same class, perhaps we could select some of them, which are not decisive, in order to establish the boundaries of the region. For example, in two dimensions we need four examples to determine the boundaries of one region, maximum. In general, in d-dimensions we will need 2dexamples, maximum. Therefore, if a region has more than 2dexamples, we could reduce the number of them. That is the main idea of our algorithm: to eliminate the examples that are not in the boundaries of the regions to which they belong. The aim is to calculate which set of examples could be covered by a “pure” region and then eliminate those inside that are not establishing the boundaries. A region is pure if all the examples inside have the same class. 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I P Fig. 1. An example of database. 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I P Fig. 2. The best solution with overlapped rules. The method is completely heuristic because EOP will independently work with the projection of the examplein each dimension, not all dimensions at the same time. This heuristic could seem poor for lack of generality, however the results are quite the opposite. To show graphically (Fig. 1) the idea of our algorithm we use a simple two-dimensional databasewith twelve numbered examples and two labels: I (odd numbers) and P (even numbers). An optimal classifier would obtain the two rules showed in Fig. 2. However, this classifier must be hierarchical, since it is producing overlapped rules. This is not the case of C4.5 and many others. An axis-parallel classifier might provide one of the following solutions presented in Figs 3, 4, 5 or 6, where rules are not overlapped. Before formally exposing the algorithm, we will briefly explain the main idea. Consider the situation depicted in Fig. 7: the projection of the examples on the abscissas axis produces four ordered sequences {I, P, I, P}corresponding to the examples {[9, 3, 5, 1, 11], [8], [7], [4, 6, 2, 12, 10]}. Identically, 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I P Fig. 3. One possible solution. 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I Fig. 4. One possible solution. with the projection on the ordinate axis we can obtain the sequences {P, I, P, I}formed by the examples {[12, 10, 8, 6, 4], [11], [2], [9, 7, 5, 3, 1]}. Each sequence represents a rectangular region as a possible solution of a classifier (a rule) and the initial and final examples of the sequence (if it has only one, it is simultaneously the initial and the final one) represent the lower and upper values for each coordinate of this rectangle. For example, in Fig. 5, there is a rectangle formed by the examples {1, 3, 5, 7, 9}. This region needs the examples {9, 7}to establish the boundaries of a dimension and the examples {1, 9} for another one. Therefore, the remaining exampleswill be candidates to be eliminated because they are never boundaries. The idea is best understood by analysing the non-empty regions obtained by means of projections on every axis, as shown in Fig. 7 and deleting the examples that are not relevant so as to establish the boundaries of a rule (Fig. 8). 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I Fig. 5. One possible solution. 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I Fig. 6. One possible solution. 2.1. Definitions Definition 1: Let the attribute Aibe a real variable that takes values in Ii=[min i,maxi]. Then, Ais the attributes space defined as A=I1×I2×...×Im, where mis the number of attributes. Definition 2: An example e∈Eis a tuple formed by the Cartesian product of the value sets of each attribute and the set Cof labels. We define the operations att and lab to access the attributes and its label (or class): att: E×N→Aand lab: E→C, where Nis the set of natural numbers. Definition 3: Let the universe Ube a sequence of examples from E. We will say that a database with nexamples, each of them with mattributes and a class, forms a particular universe. Then U=<u[1],...,u[n]>and asthe database is a sequence, the accessto an exampleis achievedby means of its position. Likewise, the access to j-th attribute of the i-th example is made by att(u[i],j), and for knowing its label lab(u[i]). 1 3 5 7 9 2 11 4 6 8 10 12 I P I P I P I P Fig. 7. Regions without overlapping. 1 7 9 2 11 4 8 10 12 I P I P I P I P Fig. 8. Result of applying EOP. Definition 4: An ordered projected sequence is a sequence formed by the projection of the universe onto the i-th attribute. This sequence is sorted out in increasing order and it contains the numbers of the examples. For example, in Fig. 1, for the first attribute we have {9, 3, 5, 1, 11, 8, 7, 4, 6, 2, 12, 10}and for the second attribute {12, 10, 8, 6, 4, 11, 2, 9, 7, 5, 3, 1}. Definition 5: A partition in subsequencesis the set of subsequencesformed from the ordered projected sequenceof an attribute in such a way as to maintain the projection order. All the examples belonging to a subsequence have the same class and every two consecutive subsequences are disjointed with respect to the class. In Fig. 7, we have for the first attribute {[9, 3, 5, 1, 11], [8], [7], [4, 6, 2, 12, 10]}and for the second attribute {[12, 10, 8, 6, 4], [11], [2], [9, 7, 5, 3, 1]}. Henceforth, a subsequence will be called a partition. Definition 6: If an example is in the left or right extreme of a partition, the example is called border. If the partition only has one example, it is a border. The remainders are not border, but inner. For example, 2 3 3 3 3 3 3 3 3 4 B A A A B B B B C A values classes Fig. 9. QuickSort. 2 3 3 3 3 3 3 3 3 4 B B B B B C A A A A values classes Fig. 10. ReSort. in the partition obtained in the previous definition, the examples 9, 11, 8, 4 and 10 are borders for the first attribute. Definition 7: The weakness of an example is defined as the number of times that that example is not a border in a partition (i.e., it is inner to a partition) for every partition obtained from ordered projected sequences of each attribute. In the previous example, let {[9, 3, 5, 1, 11], [8], [7], [4, 6, 2, 12, 10]}and {[12, 10, 8, 6, 4], [11], [2], [9, 7, 5, 3, 1]}be the partitions, the weakness of each example is given by: weakness =0⇒examples {9,11,4} weakness =1⇒examples {1,8,7,2,12,10} weakness =2⇒examples {3,5,6} Definition 8: Those examples whose weaknesses are equal to the number of attributes of the database are called irrelevant. In our example, there are three irrelevant examples: {3, 5, 6}, and they do not appear in the solution (Fig. 8). 2.2. Algorithm The algorithm is conceptually very simple. However, in some cases, it needs special treatment due to the sorting. Tosort the databasein increasing order by an attribute is a task achievedby the QuickSort [6] algorithm. This algorithm is O(nlog n), on average. After applying QuickSort, we might have repeated values with different class. For this reason, the algorithm firstly sorts by value and, in case of equality, by class. In spite of two comparisons, we could find the situation depicted as in Fig. 9. Despitesorting, the examplessharingthesamevaluefor anattribute arenotnearerto thatexamplesthat have the same class and haveanother value. In Fig. 9 we can observe that it might be more interesting to have the examples with value 3 and class B nearer to the example with value 2 and class B. The solution to that problem consists of resorting the interval containing repeated values. The heuristic is applied to obtain the least number of changes of class. In this way, the resorting method would produce the output shown in Fig. 10 from the example in Fig. 9. We haveconsideredthe two different values (2and4) aspivotsfor resorting. Then, everyexamplewith thesameclassastheleft pivotismovedto theleft, andeveryexamplewith thesameclassastheright pivot is moved to the right, looking for the adjacent partition. In the middle, the examples will remain with Input: E: training file (n examples, m attributes) Output: E edited training file (n* examples) For each example e i E with i in {1,...,n} weakness(e i ) = 0 For each attribute a j with j in {1,..., m} E j = QuickSort(E j ,a j ) in increasing order E j = ReSort(E j ) For each example e i E j with i in {1,...,n} If e i is not border weakness(e i ) = weakness(e i )+1 For each example e i of E with i in {1,...,n} If weakness(e i )=m remove e i from E Fig. 11. EOP algorithm. BD.data BD_N.data BD_N.test N={0,1,...,9} 10 sets 10 sets Fig. 12. Ten-fold cross-validation. the order generated by QuickSort. That is the algorithmic principle of the method implemented in the ReSort algorithm. The complexity of the ReSort algorithm is O(n), due to the shifting of equal-valued examples. Therefore, the average computational cost of the algorithm is O(mn log n), much lower than other algorithms proposed in the bibliography, normally O(mn2). The algorithm is illustrated in Fig. 11. 3. Experiments Tests have been achievedin over several databases of varying complexity from the UCI repository [3]. A summary of the characteristics of these databases appears in the Appendix. In our experiments they all use the range-normalised Euclidean Metric (EM) [14]. This function defines the distance between two values rand sof given attribute ias rn diffi(r, s)= |r−s| maxi−mini The overall distance between two examples xand yis given by EM(x, y)=    m  i=1 rn diffi(xi,y i)2 For each database (BD), 10-fold cross-validation was used. A ten-fold cross-validation is performed by dividing the data into ten blocks of cases that have approximately similar size, and for each block in turn, testing the model constructed from the remaining nine blocks on the unseen cases in the hold-out block (Fig. 12). BD_N.data METHOD={EOP, IB2, ENN, SHR} BD_METHOD_N.data 10 x 4 = 40 setsMETHOD Percentage of Retention (PR) Computational Cost in seconds (CCS) TABLE 1 N={0,1,...,9} Fig. 13. Reduction methods. BD_METHOD_N.data BD_N.test K-NN K={1, 3, 5} Error Rate (ER) Computational Cost in seconds (CCS) TABLES 2, 3 10 x 4 x 3 + 10 x 3 = 150 experiments METHOD={EOP, IB2, ENN, SHR}N={0,1,...,9} Fig. 14. Comparing the quality of reduced datasets from the editing methods by classifying with {1, 3, 5}-NN. BD_METHOD_N.data BD_N.test C4.5 Error Rate (ER) TABLE 4 10 x 4 x 3 + 10 x 3 = 150 experiments METHOD={EOP, IB2, ENN, SHR}N={0,1,...,9} Fig. 15. Comparing the quality of reduced datasets from the editing methods by classifying with C4.5. Each reducing method was given a training set (BD N) consisting of 90% of the available data, from which it returned a subset BD METHOD N (Fig. 13), where METHOD is one of {EOP, IB2, ENN, SHR}and N is a value in {0, 1, ...,9}. For example, from BD 1.data we would obtain BD IB2 1.data by applying the IB2 method. Since we are using four methods together with ten-fold cross-validation the total amount of experiments is forty for every database. Theremainder10%oftheunseendata(BD N.test)wastestedontheinstancesofBD METHOD N.data using k-NN, with k=1,3,5. For example, we could obtain iris ib2 1.data by applying the IB2 method to the iris 1.data file generatedby the cross validation. Afterwards, we will use iris ib2 1.data to classify iris 1.test by means of the nearest neighbour technique varying kfrom one to five (odd values). We report the results from ten datasets to which four editing methods are applied and three classifications are made, so that the total amount of experiments is 120 (see 10 ×4×3in Fig. 14), plus the classification over the original (non-reduced) BD N.data (see 10 ×3in Fig. 14), i.e. 150. As a further comparison, another widely-used learner, C4.5, was run on these datasets (Fig. 15). For example, after reducing iris 3.data with EOP, iris eop 3.data was generated, it was given as input to C4.5 and the decision tree generated was used to classify the iris 3.test file (test files are never reduced). The purpose is to demonstrate that EOP is more useful than other methods if we are interested in producing axis-parallel-based models like that of C4.5 (decision trees), COGITO [1] (decision lists), and many others. EOP conserves the axis-parallel decision boundaries better than IB2, ENN and SHRINK. The experiments show that by applying EOP, the knowledge in the original training file is conserved into the reduced training file since the decision boundaries of every region in the space are conserved. A summary of the results of the editing methods appears in Table 1. The first column (CCS) shows the computational cost in seconds of the complete 10-fold cross-validation (the sum of the ten experiments).