Métodos para descubrir conocimientos en los datos

- i - Methods for Knowledge Discovery in Data University of Seville Department of Languages and Information Systems Dissertation submitted in partial fulfilment of the requirements for the degree of Doctor Europeo en Informática, presented by Santiago Patricio Serendero Sáez Advisor: Professor José Miguel Toro Bonilla June, 2004 ii The more perfect a nature is the fewer means it requires for its operation. Aristotle's All exact science is dominated by the idea of approximation Bertrand Russell iii Agradecimientos Agradezco muy sinceramente la ayuda prestada por mi Director de Tesis, Prof. Dr. Miguel Toro durante todos estos años. Su contribución ha sido fundamental en la formalización de los algoritmos de este trabajo. Agradezco a Erika y Andrea, cuyo amor ha sido la energía elemental que ayudó a mantener este barco contra viento y marea. Sin ellas este trabajo no habría podido ser. Agradezco a mis padres, que me dieron los materiales esenciales para la culminación exitosa de esta fase de mi vida, y que aquí y Allá se están todavía preguntando en que cosas he andado metido todo este tiempo. Agradezco a amigos y colegas que me han ayudado. A los colegas R. Martínez de la U. de Sevilla , H. Shahbazkia y Fernando Lobo de la U. de Algarve, por la gentileza que tuvieron de leer el manuscrito original y hacerme valiosas críticas. A G. Oliveira e A. Jones por su corrección del manuscrito en Inglés. A J. Lima, por su ayuda en la revisión de algunos algoritmos. A T. Boski, por su aliento permanente. A F. Saravia y a María Pía Labbé por su entusiasta apoyo desde mi distante y querido Chile. Una palabra especial de agradecimiento a los colegas del Departamento de Lenguajes y Sistemas de la Universidad de Sevilla. Me han tratado de tal modo, que en todo momento me he sentido allí como en mi tierra. Parte del tiempo de trabajo de esta tesis, ha sido hecho con el apoyo del programa de acción 5.2 PRODEP financiado por la Unión Europea. - iv - Abstract This thesis contributes to the development of tools for Supervised Learning, and in particular for the purposes of classification and prediction, a problem of interest to everyone working with data. After analysing some of the most typical problems found in instance-based and decision trees methods, we develop some algorithmic extensions to some of the most critical areas found in the process of Data Mining when these methods are used. We begin by studying sampling data and the benefits of stratified data composition in the training and test evaluations sets. We study next the characteristics and degree of relevance of attributes, a problem of paramount importance in data mining. We do this by means of identifying the discriminatory power of attributes with respect to classes. Selecting most relevant attributes increases algorithm complexity, which is exponential in the number of attributes. For this reason, verifying every other possible subset of candidate attributes is sometimes out of question. In this respect, we provide a lowcomplexity algorithm to help discover which attributes are relevant and which are not [Serendero et al., 2003]. This technique forms an integral part of the classification algorithm, and it could be utilised by rule induction algorithms using trees, as well as instance-based methods using distance metrics for the application of the principle of proximity. In most instance-based methods, vector records relate to a class as a whole, i.e., each record considered on its integrity relates to one class. The same idea is present in decision trees, and for that reason classes appear only at tree leaves. On the contrary, our algorithm relates class membership to cell prefixes, allowing a complete and new approximation of sub-cell component elements to class membership. This concept is a fundamental part of our algorithm. Most instance based methods, and in particular, k-NN methods deal with the problem of searching similar records to some unseen object in the data hyperspace based on distance metrics. Selecting “close” neighbour objects from the hyperspace can be a computationally expensive process. We contribute in this respect by offering a search mechanism based on a tree structure with a low complexity cost and where the distance calculation considers first attributes that are more relevant. v Selecting best neighbours of representative patterns not only depends on the proximity of similar objects. We define several selection criteria weighted according with data characteristics, thus adapting the algorithm to different data. For all experiments, we present a comparison of results from two different sources, namely results from the literature and results obtained in our own hardware using a relatively new benchmark tool. This way is possible to keep equal testing conditions, a condition difficult to find in figures from the literature. vi Contents Agradecimientos.........................................................................................................iii Abstract.......................................................................................................................iv Contents ......................................................................................................................vi List of Tables..............................................................................................................xi List of Figures...........................................................................................................xiv 1 Introduction.........................................................................................................1 1.1 Motivation for this thesis. Some background......................................................4 1.2 Instance-based and Decision Tree methods........................................................6 1.2.3.1 Problems with Decision Trees ..................................................................8 1.2.3.2 Problems with Instance-based methods....................................................9 1.3 Objectives..........................................................................................................10 1.4 Contributions of this thesis ...............................................................................11 1.5 Structure of this text..........................................................................................12 2 State-of-the-Art.................................................................................................15 2.1 Active areas of research and new challenges and directions...........................16 2.1.1 Active learning (AI)/experimental design (ED).........................................16 2.1.2. Cumulative learning..................................................................................17 2.1.3. Multitask learning .....................................................................................17 2.1.4. Learning from labelled and unlabeled data...............................................17 2.1.5 Relational learning.....................................................................................17 2.1.6 Learning from huge datasets......................................................................18 2.1.7 Learning from extremely small datasets....................................................18 vii 2.1.8 Learning with prior knowledge..................................................................18 2.1.9 Learning from mixed media data...............................................................18 2.1.10 Learning causal relationships...................................................................19 2.1.11 Visualization and interactive data mining................................................19 2.2 General trends...................................................................................................19 2.3 Different Perspectives of Data Mining .............................................................22 2.4 Similarity searching in tries..............................................................................25 2.4.1 Similarity searching metric spaces.............................................................26 2.4.2 Some concepts for a metric space..............................................................26 2.4.3 Types of search ..........................................................................................30 2.4.4 Equivalence relations.................................................................................31 2.5 Searching in tries..............................................................................................32 2.6 Data Mining and Statistical Sampling..............................................................35 2.6.1 Random sampling ......................................................................................35 2.6.1.1 Holdout method.......................................................................................36 2.6.1.2 Cross-validation method.........................................................................37 2.6.1.3 Leave one out method.............................................................................38 2.6.1.4 Bootstrap method...................................................................................38 3 The Trie-Class Algorithm. Basic definitions..................................................39 3.1 General overview of the algorithm ...................................................................39 3.2 Basic definitions................................................................................................40 3.3 Definitions on cell discretization ......................................................................41 3.4 Exclusiveness as a measure of attribute relevance...........................................47 3.5 Attribute selection .............................................................................................49 3.6 Shape definitions...............................................................................................50 3.7 Searching for nearest cells................................................................................55 3.7.1 Selecting closest pattern.............................................................................57 3.7.2 Using look-ahead to solve ties in cell pattern selection.............................59 viii 3.7.3 The search algorithm in practice................................................................60 3.8 Extraction of p1 is an efficient alternative to regular k-NN methods................61 3.9 General assumptions on some basic Principles................................................63 3.9.1 Data consistency ........................................................................................63 3.9.2 Partition granularity ...................................................................................64 3.9.3 Class membership, Patterns and the Continuity Principle.........................64 4 Pre-processing Data Before Mining................................................................67 4.1 Converting records into discretized patterns....................................................67 4.2 The special case of categorical attributes.........................................................69 4.3 Feature reduction and elimination ...................................................................73 4.3.1 Ordering attributes .....................................................................................75 4.3.2 Looking at sub-cells from the “clearest” viewpoint...................................75 4.3.3 Reducing attribute numbers .......................................................................77 5 Evaluation and Results.....................................................................................81 5.1 Data used in experiments..................................................................................81 5.1.1 Adult dataset. (Census USA 1994).................................................................81 5.1.2 Annealing dataset.......................................................................................82 5.1.3 Breast Cancer (Wisconsin) dataset ............................................................82 5.1.4 Dermatology dataset ..................................................................................83 5.1.5 Diabetes (Pima Indian) dataset ..................................................................83 5.1.6 Forest Cover type dataset...........................................................................83 5.1.7 Heart disease dataset (Cleveland). .............................................................84 5.1.8 Heart disease Statlog..................................................................................84 5.1.9 Hypothyroid dataset...................................................................................85 5.1.10 Iris dataset ................................................................................................85 5.1.11 Pen-Based Recognition of Handwritten Digits: “pendigits” dataset .......85 5.1.12 Satellite image dataset (STATLOG version)...........................................86 5.1.13 German credit dataset...............................................................................87 ix 5.2 The evaluation method used by Trie-Class.......................................................87 5.3 Comparison of results with other classifiers.....................................................89 5.3.1 Results using figures from the bibliography..............................................89 5.3.2 Results from experiments done in our own hardware................................96 5.4 Performance Conclusions...............................................................................100 6 Choosing the best close neighbour ................................................................103 6.1 Decision parameters .......................................................................................105 6.1.1 Semi-exclusive values..............................................................................105 6.1.2 Distance between selected cells...............................................................105 6.1.3 The shape of cells.....................................................................................106 6.1.4 Cell strength.............................................................................................106 6.1.5 Frequency of cells and sub-cells..............................................................107 6.1.6 The Majority Class...................................................................................108 6.2 Basic functions definitions for the selection of a representative cell’s class..108 6.3 Obtaining the weight of decision parameters .................................................110 6.4 Predicting the final output class .....................................................................115 7 Implementation...............................................................................................119 7.1 General overview............................................................................................119 7.2 Building a trie as the main tree structure .......................................................121 7.3 Insertion algorithm .........................................................................................125 7.4 Discussion on the actual implementation .......................................................126 7.5 Dictionary and other supporting files.............................................................129 8 Conclusions and Future work........................................................................131 8.1 Conclusions.....................................................................................................132 8.2 Future work.....................................................................................................135 - 1 - 1 Introduction The most important goal of handling data and performing computation is the discovery of knowledge. We store data about a certain process and retrieve later that information in order to use it in a meaningful way. To put it in the words of R. W. Hamming, the purpose of computing is insight, not numbers. [Hamming, 1973] Getting insight from small or moderate amounts of data was manageable until recently. However, data collection with today’s computer technology has had such an increment in volume in the last years that represents an explosion overwhelming all expectations. According to a recent study “ The world produces between 1 and 2 exabytes 1 of unique information per year, which is roughly 250 megabytes for every man, woman, and child on earth.” …”It’s taken the entire history of humanity through 1999 to accumulate 12 exabytes of information. By the middle of 2002 the second dozen exabytes will have been created”. In the conclusion of the same report, its authors say: “It is clear that we are all drowning in a sea of information. The challenge is to learn to swim in that sea, rather than drown in it. Better understanding and better tools are desperately needed if we are to take full advantage of the ever-increasing supply of information”[Lyman, 2000]. These huge amounts of information do not only represent a challenging data warehousing problem. In the last forty years database technology and disk capacity has allowed the easy storage, manipulation and fast retrieval of ever growing volumes of data, which is at the heart of today’s information society. However, much of this increased power is wasted because humans are poor at gaining insight from data presented in numerical form. When a database stores measurements, events, dates or simply numbers, queries on that database return facts. Facts however are not exactly knowledge, in the sense of concepts representing generalizations about data relations. These concepts are the ones permitting the learning process to take place, by improving our performance in an environment. Congruent with the above indicated data production of the last years, the increase in database size as well as the ever growing high dimension of records has dramatically 1 Introduction 2 expressed the idea that besides other relations than the ones defined a priori by database designers, there was knowledge which could be extracted from databases. Moreover, this knowledge would be crucial in the decision-making process. With this premise in mind, the field has had a tremendous impact primarily on industry wanting to take advantage of this hidden knowledge. The globalisation of information through the Internet and the establishment of the e-business have increased the need for tools and methods to elaborate knowledge from data produced massively every second. At the same time, the size of the problem made also clear that looking for knowledge through tedious manual queries on large databases would have to be replaced by advance computer algorithms running on faster hardware, as the sole possible solution. It is within the goal of addressing these challenging issues that has taken place the development of the area of Knowledge Discovery (KDD). Although inherently associated with the area of databases for they contain the raw material for the elaboration of knowledge, KDD is at the confluence of other research areas as well, such as statistics, machine learning, pattern recognition, neural networks, rough and fuzzy sets among others. KDD is all of them and none of them. It is all of them, because the discipline jointly uses techniques from several of these areas in order to attack the old problem of finding patterns in data. It is none of them, because it is something more than the simple joint utilization of these techniques developing its own methods, data structures and algorithms. The reason for this development came as a realization that in solving problems, which involve thousands of high dimensional records, no single method could be expected to work well in the face of such diversity of data. The term Knowledge Discovery appeared around 1989 and was defined as: “...The nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data” [Frawley et al., 1991]. However, the name popularising the field has been Data Mining, mostly used in the economic and financial spheres. Later, the name was extended to Knowledge Discovery 1 An exabyte is a billion gigabytes or 1018 bytes. 1 Introduction 3 in Databases or KDD [Fayyad et al., 1995] to refer to the whole process, reserving the name Data Mining only for the central inductive task 2 . For these late authors, KDD is: “The process of using the database along with any required selection, preprocessing, sub-sampling, and transformations of it; to apply data mining methods (algorithms) to enumerate patterns from it; and to evaluate the products of data mining to identify the subset of the enumerated patterns deemed ‘knowledge’”. In general, there are three main steps in the Knowledge Discovery process. First, target data needs to be selected whether at a raw state or already in database format. At this pre-processing stage, data is normalized and clean. A decision needs to be made on what to do with records exhibiting missing data or data that seems to be in error. It is also required at this stage to deal with the various types which data can present, in particular its domain size, ordering, boundary values, etc. Second, a phase recognized as Data Mining, which is the central inductive process of pattern extraction. Inductive means obtaining knowledge through the inference of a new theory from a set of observations, which is the experience. At this stage and depending on the method been used, global or local hypotheses are created capturing the existing relations in patterns of data under analysis. Third, knowledge can be extracted from the obtained patterns. However, the resulting information is not always in an easily interpretable form. For this reason, pattern information and relations found must be put in a textual, graphical or visual form which is more intelligible, such that can be understood and therefore useful to the expert domain. Still the users of the data mining process must use the resulting knowledge. They have to determine whether the accuracy of the results, the understandability of the extracted knowledge, the time span to produce results and its practicality is useful or not for them, establishing new goals. Generally, at this stage, the process reiterates again to approximate to new objectives such as improving results, simplifying already obtained knowledge or improving its visual representation. 2 In the context of this work we used indistinctively both expressions. 1 Introduction 4 In all these three phases, the interaction between the domain expert and the programmer is required several times. Data and its meaning is not known by the programmer. It is the domain expert experience and knowledge, which facilitates the work of the programmer. For knowledge always can use previous knowledge about a domain to generate a picture closer to reality. Furthermore, algorithm development and resulting performance are data dependent. Therefore, choosing existing or designing new algorithms requires the programmer expertise. In many cases, the parameters used to produce hypotheses about data need to be changed dynamically as a function of data and the algorithm itself. Interaction between the expert of the domain and the programmer is again required. Finally, yet important, at the very end of one iteration cycle within this process, is the decision of the data owner to accept or not the results produced and offered by the programmer. 1.1 Motivation for this thesis. Some background This thesis is about Data Mining and its related field Machine Learning (ML), itself a sub-field of Artificial Intelligence. ML is the scientific field studying how machines can learn, which is one of the components of intelligence. [Langley, 1996] proposes the following definition of learning: “Learning is the improvement of performance in some environment through the acquisition of knowledge resulting from experience in that environment” Both ML and Data Mining depend heavily on inductive reasoning, i.e. the reasoning from particular observations available to the researcher leading to general concepts or rules. 1 Introduction 5 Example 1 The following are examples of inductive reasoning and learning: A tennis player trying to hit a forehand shot, will spend hundreds of shots learning how to hit the ball in order to send it through the net at the desire height, speed and direction, in order to place it far from the reach of his/her opponent. After 1000 shots, he/she will have (hopefully) learned how to hit the ball appropriately. The knowledge extracted from all those patterns describing the ball trajectory and place of impact, will be then used the following time a similar shot is hit. Someone concerned with the lack of water for human needs could measure over a period of a year the amount of water wasted in a typical family home. This is the experience. After observing many patterns of water consumption, this information could be processed to demonstrate that 60% of that water contains only soap, 20% contains other polluters and the remainder 20% contains other organic matter. This is the knowledge. Using this knowledge in order to build houses with simple filter systems to recycle a scarce resource such as water would mean that we have learned something. In the context of this work, we deal only with the first subtask of the learning process, namely the methods to acquire knowledge including the first two phases of knowledge discovery referred to above. Knowledge has to be extracted from data. Most of the time, we found data on its original raw state, normally requiring a pre-process phase in order to be useful. Data has to be clean, ordered, complete and consistent. Let us accept for the time being, that data is ready to be processed. Records (examples, observations, objects) are usually presented to the programmer as a sequence of vectors formed by Attribute values of various data types. They represent the independent variables, with various degrees of correlations between them. These attributes can be associated or not with a given label or class, representing the dependent variable. Thus, a typical representation is the following: 1 1 2 2 | , | ,.., | ,.., | , i i n n r A a A a A a A a c = (1.1) We find an ordered sequence of the pair Attribute/value and optionally a corresponding class, a symbol representing one among a finite discrete set of values. 1 Introduction 6 Depending on the presence or absence of the class, two classical problems constitute a central goal in Data Mining. If the class is present in the available data, the goal can be class prediction. If there is no input of classes, the goal will be clustering: to find natural groupings or clusters of records in order to characterize data. In the first case, learning from examples with or without a known class is called Supervised Learning in Machine Learning taxonomy. Its goal is to obtain relevant data patterns from available examples. These in turn will be used to generate general or local hypotheses representing knowledge. This knowledge is used later to predict the class for new unseen data. This process, which organizes data into a number of predetermined categories, is called Classification. Classification is an uncertain task by nature, aiming at making an educated guess about the value of the dependent variable class, based on the value of the independent variables represented by attribute values. When the submitted examples do not exhibit class membership, and the original database has some natural cluster structure, a clustering algorithm must be first run, in order to make explicit to each example its associated class label. The classification algorithm can be executed after this. When no prior data is available for learning, we are in the world of Unsupervised Learning or Learning from Observation. The system must discover by itself its class membership. To do that, it must first characterize common properties and behaviour of examples forming clusters of records. The idea is to create groups of records with the smallest possible differences among their members and the largest possible differences between groups. This task has no prediction to make but to discover and report to the user about the most informative patterns found in the dataset under analysis. For this reason, it is also known as Data Description. It is within the framework of Supervised Learning that we have developed a Classification tool, which is described in the following sections. 1.2 Instance-based and Decision Tree methods Out of the many Supervised Learning methods used by Data Mining to create knowledge from data, we have concentrated our attention into two of the most popular inductive techniques: Decision Trees and Instance-Based methods. In the rest of this chapter, we briefly describe both methods and some of their difficulties. We will finish 1 Introduction 7 by proposing a method that uses a) the generation of local hypotheses according to nearby neighbours used by instance-based methods, and b) a tree structure as decision trees do, although in our case is not the tree making any class membership decision, but helping in the whole process. Decision trees have been used since the 1960s for classification [Hunt, 1966] and [Moret, 1982]. They did not receive much attention within statistics until the publication of the pioneering work on CART [Breiman, 1984]. Independently Quinlan popularised the use of trees in Machine Learning with his ID3 and C4.5 family of algorithms [Quinlan, 1983, 1987, 1993]. According with [Smyth, 2001] early work on trees uses statistics emphasizing parameter estimation and tree selection aspects of the problem, more recent work on trees in data mining has emphasized data management issues [Gehrke et al., 1999]. Decision trees perform classification by executing sequential tests on each of the attributes of a new instance against known records whose patterns are used to create the Decision Tree. While the tree’s nodes represent attribute value thresholds, the leaves represent the attached classes to these patterns. The new instance to be classified advances in the tree by executing attribute value comparisons at each node, with branching based on that decision. The process is reiterated until a leaf node is reached, assigning its class to the new instance. The attraction of these tools comes from the fact that data semantics becomes intuitively clear for domain experts. Much of the work on trees has been concentrated on univariate decision trees, where each node tests the value of a single attribute. [Breiman, 1984], [Quinlan, 1986, 1993]. The test done at each node in this type of decision trees, divides the data into hyperactive planes, which are parallel to the axis in the attribute space. Instance-based learning, (also known as case-based, nearest-neighbour or lazy learning) [Aha, 1991], [Aha, 1992], [Domingos, 1996], belongs to the inductive learning paradigm as is the case with Decision Trees. However, contrary to these, there is not a unique hypothesis generated before the classification phase. Rather, training examples are simply stored and local hypotheses are generated later at classification time for each new unseen object. The local generated hypothesis utilizes the mathematical abstraction of distance used to implement the Principle of Similarity 1 Introduction 8 applied to objects. Consequently, the class of a new object can be disclosed by finding an earlier object of known class, which is not perfectly symmetric but “similar” to it. Similarity can be understood using the mathematical concept of distance. To say that two objects are similar is the same as saying that the two objects are near to each other. To say “near” also means that we are interested in finding existing records, which do not necessarily produce exact matches with the unknown instance. Instead of using the nearest example [Duda, 1973], this paradigm uses the k nearest neighbours for classification (k-NN). There are two main methods for making predictions using k-NN: majority voting and similarity score summing. In majority voting, a class gets only one vote for each record of that class in the set of k top ranking nearest neighbours. The most similar class is assumed as the one with the highest vote score. In the second case, each class gets a score equal to the sum of the similarity scores of records of that class in the k top-ranking neighbours. The most similar class is the one with the highest similarity score sum. Methodologically, the Instance-Based approach represents the opposite when compared with Decision Trees because there is no explicit generalization of some general function. Rather, for each new case a specific function is locally constructed implicitly from the similarity measure above. On the other hand, Decision Trees methodology is a model approach. It creates a general explicit function drawn from the available examples, which is used in all new cases to determine class membership. These two methods present several problems, related to attributes characteristics, algorithm complexity and accuracy in prediction. 1.2.3.1 Problems with Decision Trees Some problems with Decision Trees described in the literature are among others: • They offer a unique hypothesis to interpret every other possible input, which not always fits the real class distribution of examples in the data space [Quinlan, 1993]. • In univariate trees, tests carried on each attribute are based on a certain threshold value calculated after some information gain criterion, which makes them sensible to inconsistent data as well as small changes in data [Murthy, 1996]. 1 Introduction 9 • The input order of attributes heavily determines the predictive skill of the classification algorithm. Choosing the right attribute subset and its order can be computationally expensive [Aha et al., 1994]. • The presence of irrelevant attributes increases the computational cost and can mislead distance metric calculations [Indk, 2000]. In datasets with high dimension, not only they do face higher computational cost problems, the interpretation becomes cumbersome to the expert domain as well. 1.2.3.2 Problems with Instance-based methods • They are “lazy” in the sense of storing data and not d oing much with it until a new instance is presented for classification [Cios, 1998]. • The cost of classifying new instances can be high [Mitchell, 1997]. The running time and/or space requirements grow exponentially with the dimension [Indyk, 1999]. • They can be very sensitive to irrelevant attributes [Domingos, 1996]. • They represent instances as points in the Euclidean space, a dimension reduction problem that constitutes a challenge on itself. • In k-NN methods, choosing the right value for k is not an easy task. A high value increases computational complexity. A small value makes them very sensible to noise data [Riquelme, 2001]. Still both of these methods face general problems common to other methods such as irrelevant attributes, noise sensibility, overfitting and symbolic attributes. We will refer to each one of these later. Furthermore, it is a known fact that no induction algorithm is better than other in all data domains [Mitchell, 1980], [Brodley, 1995]. For these reasons efforts have been done in order to unify some classification methods as done for instance with RISE, which tries to combine strengths and weaknesses of instance-based and rule based methods [Domingos, 1996]. In [Quinlan, 1993], instance-based and model-based methods are combined for classification; the method uses training data to provide both, local information (in the form of prototypes) and a global model. Another attempt uses a multi-strategy combining two or more paradigms in a single algorithm [Michalski, 2 State-of-the-Art 16 produce better, larger scale, and more automatic and reliable tools to extract knowledge from this data. 2.1 Active areas of research and new challenges and directions The scope of research topics in Data Mining is very broad, challenging scientists working on various communities. In 1997 [Dietterich, 1997] did a survey on the area of machine learning and suggests four current directions for the field as a reflex of the previous five years of research. His main selected topics where: (a) ensembles of classifiers, (b) methods for scaling up supervised learning algorithms, (c) reinforcement learning, and (d) learning complex stochastic models. He did still mention other active topics such as learning relations expressed as Horn clause programs, area also known as Inductive Logic Programming, the visualization of learned knowledge, neural networks methods, algorithms for dealing with overfitting, noise and outliers 4 in data and easy-to-understand classification algorithms. All of these areas where included later in a broader report on Data Mining from 1998, produced at a state-of-the-art workshop done at the Centre for Automated Learning and Discovery at Carnegie Mellon University (CONALD), which brought together an interdisciplinary group of scientists including approximately 250 participants [Thrun, 1998]. In their final report they were able to recognize eleven active areas of promising research, which in our opinion give the broader picture of present research in Data Mining. For this reason, in the following lines we enumerate and briefly describe each one of them. 2.1.1 Active learning (AI)/experimental design (ED) Known by these two names depending on whether the area is referred from the Artificial Intelligence of Statistics community, the area addresses the question of how to explore, i.e., choosing which experiment to run during learning. This is done under the assumption that during learning, there is an opportunity to influence data collection. 4 In statistics, an outlier refer as the case that does not follow the same model as the rest of the data. [Weisberg, 1985] 2 State-of-the-Art 17 Business-customer relations and robot training are two examples of choosing correctly the learning data. 2.1.2. Cumulative learning Many learning problems relate to a continuum of data growing incrementally, which can change patterns in non-obvious ways. The problem is that often, data complexity and volume and the statistical algorithm used for analysis makes almost prohibitive daily evaluation over the entire existing data starting from scratch. For instance customer behaviour can represent roughly steady patterns over a period of time, changing afterwards under influences such as fashion changes, social concerns or just new government regulations. 2.1.3. Multitask learning The main question posed in this area is whether we can devise effective multi-task learning algorithms, which generalize more accurately through transferring knowledge across learning tasks. This situation is the result of several domains characterized by families of highly related (but not identical) learning problems. Consumer behaviour on specific industry products shows similar attitudes. People’s different diseases share similar symptoms, making it a promising possibility of transferring knowledge on people patterns across domains. 2.1.4. Learning from labelled and unlabeled data The problem addressed in this area, is the fact that we do not always dispose of labelled data. Trying to filter e-commerce data and typifying customers on the fly in a busy Internet site is an expensive process. Can we afford to try labelling all customers? Is it possible to devise algorithms that exploit unlabeled data when learning a new concept? 2.1.5 Relational learning It refers to the fact that in many learning environments, instances are not presented as an already arranged vector of attributes in a static form. Rather, the relation exists 2 State-of-the-Art 18 between whole entities sitting in different files, as is the case with intelligent relational databases. And it is this relation the one that is important for learning new knowledge. For instance, being able to cross information of people among their jobs, their assets and bank situation together with their tax profile is crucial in tax evasion applications. Devising algorithms of the same relational nature of the data structure is here the challenge. 2.1.6 Learning from huge datasets Large data renders impossible the use of algorithms that require reading data files several times. For instance, astronomical web traffic and grocery data are among other areas where this situation forces to devise algorithms that can scale up extremely large databases. 2.1.7 Learning from extremely small datasets This is the opposite situation to the one describe above. Some datasets are just too small for current learning algorithms. Robotics and face recognition problems are examples of application areas with a very limited number of training cases. How can learning be done in these situations, other than resorting to prior knowledge? 2.1.8 Learning with prior knowledge This is one of the solutions referring to the problem above described of working with scarce training data. Specially, when there is available solid prior knowledge about certain pattern behaviours. The question is then how to incorporate this prior knowledge in statistical methods, and how to devise flexible tools that ease the insertion of this knowledge, sometimes uncertain and abstract. 2.1.9 Learning from mixed media data Existing algorithms cope in general with just a few types of data. The fast development of multimedia databases poses the challenge of learning from image, acoustic, numerical and nominal data together. Algorithms in this area will have to be able to integrate all these within the learning process, solving first the design problem of 2 State-of-the-Art 19 whether to learn separately for each data type as a first step, or handling all these different types on a feature level. 2.1.10 Learning causal relationships How do we know that a person’s obesity, which represents a massive problem in rich countries today, is not due to the consumption of diet colas or the absence of sugar in their daily diet? How do we separate correlation from causality? The challenge in this respect is in the development of algorithms able to learn causality, the necessary assumptions to be made and the implications they have. 2.1.11 Visualization and interactive data mining Visualization of data patterns takes an important part in the learning process of many domains. The owner of data participates interactively in the data mining process, observing partial results, rearranging data and reprocessing again until finding desired patterns. The problem is that high-dimensional data as well as some type of data such as text are hard for human visualization. So the problem is how can we devise algorithms able to look at these large and sometimes obscure datasets and how to incorporate in the learning cycle the knowledge of the expert “taking a look” at data? 2.2 General trends In 1999 a workshop took place on mining large distributed data, bringing together scientists working on information and data management, algebra and number theory, and statistics and probabilities [Grossman, 1999]. Their goal was to discuss the current state-of-the-art of data mining and data intensive computing, as well as opportunities and challenges for the future. The focus of their discussion was on mining large, massive, and distributed data sets. After confirming the explosion in the amount of digital data and the rather static growth of scientists, engineers and analysts available to work on this data, they conclude that the way to bridge the gap required the solution of the following fundamental new research problems: (a) developing algorithms and systems to mine 2 State-of-the-Art 20 large, massive and high dimensional data sets; (b) developing algorithms and systems to mine new types of data; (c) developing algorithms, protocols, and other infrastructure to mine distributed data; (d) improving the easy of use of data mining systems; and (e) developing appropriate privacy and security models for data mining. With the exception of the last topic, there is an agreement on all others as areas of interest in new research. Perhaps more interesting in this report is a chapter in advances on new applications, which is always a strong force for the discipline of Data Mining to advance. The list of these new applications at the time of the report are included in the following categories: (a) Business & E-commerce Data; (b) Scientific, Engineering & Health Care Data; and (c) Web Data. Several applications from each of these categories were reported: Business Transactions, Electronic Commerce, Genomic Data, Sensor Data, Simulation Data, Health Care Data, Multimedia Documents and The Data Web. These topics coincide with those indicated by [Witten, 1999] on his book. The book’s chapter “Looking forward” largely refers to these same topics. One simple way of verifying actual trends observed in Data Mining research is to look at research production presented on most recent international congresses of renowned prestige in the field. Obviously there is the risk of bias at various levels when using this method. First, one has to determine what constitutes a leading congress. Another area of potential bias is represented by the fact that a congress organizing committee uses its own criteria to define the areas of research that are important at present time. Still another element of bias is the classification of articles as full papers, short presentations or posters. In some cases, a crowded area of research reaching already the maximum number of articles defined by the organizing committee would end up classifying as a poster an article that in a normal situation would have been accepted. In view of these difficulties, one has to be careful when drawing conclusions from such an exercise. Nevertheless this method still allows us to see which research areas capture most attention, provided that we assume that organizing committees selection criteria represent a good sample of trends in the entire field. This is what we have done, selecting as input four international congresses [ICDM 2002], ICML-2002], [KDD 2002] and [ECML/2002] grouping together research topics roughly corresponding to coincident sub-areas. Table 2.1 shows a quantified volume of articles accepted by area of research in decreasing order. They are classified in one of two 2 State-of-the-Art 21 categories: full articles and posters/short presentations. We did assume that these last two were more the less equivalent, material still not mature enough but important to publish. Table 2.1 Accepted papers in Data Mining and Machine Learning in four International Congresses during 2002. Articles by Area of research Number and Type Full Short Total Statistical Methods 27 6 33 Clustering & Similarity 19 9 28 Graphs, Trees & Hierarchical structures 20 5 25 Text Classification 21 4 25 Rule Learning 16 6 22 Reinforcement Learning 22 0 22 Ensembles of Classifiers 20 1 21 Streams, Time series/Temporal Data 15 4 19 Support Vector Machines (SVM) 18 1 19 Theoretical Foundations 17 2 19 Web Mining 11 6 17 Frequent patterns/item sets/Sequential patterns 11 2 13 Sampling & Feature Selection 6 4 10 Classification / Evaluation 5 5 10 Intrusion Detection and Security 6 2 8 Bio informatics 6 2 8 Other 1 7 8 E-business. Market & cost. Analysis 2 5 7 Relational Learning 5 1 6 Visualization 2 2 4 Active Learning 3 0 3 Neural Networks 1 2 3 Medical Applications 3 0 3 Applications of Learning 3 0 3 ILP 3 0 3 Cost-sensitive learning 3 0 3 Outlier detection 1 2 3 Distributed Data Mining 0 2 2 Learning from examples 0 2 2 High Performance D.M. 0 1 1 Performance Evaluation 0 1 1 Total 351 We have grouped these publications following the structure adopted in the congresses themselves, putting together those that seem reasonably similar. This grouping still 2 State-of-the-Art 22 presents an additional bias, as some publications could perfectly be classified into two or more groups. To avoid this, we did follow the grouping use by congresses. Although these figures do not allow us to declare that these are the trends in research at present time, due to the difficulties in classifying this material and the inherent bias in their selection, they are still useful to visualize the big picture. The first one is to confirm that the traditionally developed areas in Data Mining and Machine Learning such as statistical methods (with a strong emphasis on Bayesian methods among them), clustering, decision trees, and rule learning are still leading the volume of activity. Secondly, there are other areas that show also growing activity such as text mining, ensemble of classifiers, time series, Support Vector Machines and Web mining. These trends cannot be a surprise as they were announced five years ago as reported earlier in this section. Coincident with these general trends, a recent article on the state-of-the-art by [Flach, 2001] identified similar trends after reviewing around a dozen books in the area of Machine Learning. These include: a trend towards combining approaches that were hitherto regarded as distinct and were studied by separate research communities; a trend towards a more prominent role of representation; and a tighter integration of machine learning techniques with techniques from application areas such as Bio informatics. 2.3 Different Perspectives of Data Mining The richness and fast evolving of the Data Mining discipline not only comes from its large variety of research areas of interest as reported in the previous section. Depending whether you look at Data Mining from the database, the statistical or machine learning perspectives, it exists in the field three strong and different perspectives of development and paradigms. In a recent work by [Zhou, 2003] in his own words he goes "mining" on Data Mining books. The author analyses three leading and popular authors in the field [Han et al., 2001], [Witten et al., 2000] and [Hand, 2001] whose academic books on Data Mining take respectively the three perspectives mentioned above. The observed differences are put in evidence from the very definition of Data Mining from each of these authors. In the Han and Kamber book [Han et al., 2001] data mining is defined as: 2 State-of-the-Art 23 “The process of di scovering interesting knowledge from large amounts of data stored either in databases, data warehouses, or other information repositories”. In Witten and Frank’s book [Witten et al., 2000], Data Mining is defined as: “The extraction of implicit, previous ly unknown, and potentially useful information from data” ([9], pp. xix) In D. Hand book [Hand et al., 2001], the authors define it as: “The analysis of (often large) observational data sets to find unsuspected relationships and to summarize the data in novel ways that are both understandable and useful to the data owner” ([6], pp.1). Others such as [Zhou, 2003] put next in evidence other differences among these views, such as the concept of Knowledge Discovery in Databases (KDD) and the whole theme of the chapters covered in all three books to finally suggest (rather than conclude as put it by the author) that: “…thus from the difference in the coverage of these books, it could be perceived that the database, machine learning and statistics perspectives of data mining put particular emphases on efficiency, effectiveness and validity, respectively” (Ibid, page 4). To our understanding, there are perhaps less differences between the Database and Machine Learning perspectives when compared against the Statistics view of the problem. The reason for this is that both approaches emphasize algorithms and data structures, bringing together the objectives of efficiency and effectiveness. In fact, machine learning and database scientists share a common core of computer science courses, which naturally bring close their views to solutions on data mining problems. On the other hand, they both lack a strong background on statistics, a deficiency that only interdisciplinary approaches can help solving. The difference between computer scientists and statisticians is precisely the subject of [Smyth, 2001] which devotes an 2 State-of-the-Art 24 entire chapter of a recent book dedicated to scientific and engineering applications [Grossman, 2001]. Beginning with a common understanding among statisticians that “data mining is not much more than the scaling up of conventional statistical methods to massive data sets”, this author explain which are the popular techniques in data mining that have their roots in applied statistics. Among them, nearest neighbours, naïve Bayes and logistic regression for prediction models, and k-means and mixture models using expectation-maximization for clustering and segmentation. The one exception to this rule is association rules [Agrawal et al, 1993], a technique that have no clear “ancestors” in the statistics literature, although the author immediately declares that is arguably that how many real-world data mining applications rely on association rules for their success. Nevertheless, while there is some truth in this view of data mining as an extension of applied statistics, this author clearly states that while there is some truth in this viewpoint, “a more accurate reflection of the state of affairs is that data mining (and more generally computer science) has indeed introduced a number of new ideas within the general realm of data analysis, ideas that are quite novel and distinct from any prior work in statistics” [Smyth, 2001]. There is one very important aspect that should be emphasized. For a data miner to understand the fundamental role of Statistics in data analysis, requires at the very least some minimal exposure to statistical concepts. Rather than learning a set of specific detailed models it is probably more important to appreciate the general mindset of statistical thinking. For instance, computer scientists are quite aware of the problems posed by very large datasets for analysis, and their efforts will concentrate on structures offline, parallel processing and other software and hardware resources to face the problem, rather than focusing their attention in the theory of sampling for instance and the search of a solution to develop their models with less but more representative data of the problem at hand. To over simplify this point, tell for instance to a computer scientist that the problem is to mine people’s opinion on the next national election. They will be thinking on how to hold and structure million of voters as part of the problem to solve. On the contrary, the statistician will focus on the sample size and quality in terms of people’s view representation. This is the sensibility lacking in many computer scientists. This lack of understanding from many computer scientists and engineers working in data mining comes from a limited exposure to statistical ideas in their undergraduate 2 State-of-the-Art 25 curriculum, although engineers are better prepared with this respect than computer scientists. [Lam, 2000]. After analysing several success stories of the joint efforts by data miners and statisticians working together, Smyth concludes correctly in our opinion that for data miners the message is clear: “Statistics is an essential and valuable component for any data mining exercise. The future success of Data Mining will depend critically on our ability to integrate techniques for modelling and inference from statistics into the mainstream of data mining practice” [Smith, 2001]. The figures from table 2.1 seem to confirm this assertion. 2.4 Similarity searching in tries Searching constitutes a fundamental problem not only in Data Mining techniques but also in computer science as a whole. Most computer programs search for specific data in order to execute their algorithms. For this reason, a good indicator of the state-of-the- art in Machine Learning and Data Mining techniques using distance metrics is to take the pulse to these algorithms. In this chapter we review a unifying view to these techniques, in relation to our own search mechanism. The search operation can be applied to structured (database) data or to unstructured repositories of information, developed in the evolution of information and communication technologies. For this last type of scenario, required search algorithms can no longer be those of exact search applied in structured data, where the answer represented by a key formed by a number or string, is identical to the one given in the query. Traditional database query languages were built around this principle. With the evolvement of unstructured data though, the concept of “similarity searching” or “pro ximity searching” has been developed. This is to say, searching for objects or elements which are similar or closer to a given query element. Within this framework searching in tries or multi-way trees takes advantage of its structure. In the rest of this section we explain the general concept and related algorithms in this area. 2 State-of-the-Art 32 between the objects and the pivots: two elements are equivalent if their distance to all pivots is the same. Instead of using “pivots”, another large class of algorithms use a different type of equivalence relation based on “groups”, meaning the proximity to a set of elements. This algorithms use the Voronoi equivalence relation based on groups {g1, g2,…,gm} is: x~(gi) y ⇔ closest (x, {gi} = closest (y, {gi}) where closest (x, S) = {w ∈ S, ∀ w’ ∈ S, d (z, w) ≤ d (z, w’)} . The associated partition is the Voronoi partition [Aurenhammer, 1991]. In other words, in these class of algorithms, the space is divided with one partition for each group gi and the class of ci is that of the points that have ci as their closest centre. 2.5 Searching in tries Most trie structures use for searching one of the two mechanisms described in the previous subsection, namely pivoting or Voronoi “centers”. Next, we give the general context for searching in tries and talk about some of these algorithms in no particular order. Tries are perhaps most widely used in text processing applications, such as string matching, approximation string matching and compression schemes [Andersson et al., 1994], as well as in algorithms with genetic sequences, data structures of dynamic hashing tables, remote sensing imagery, etc [Aoe et al., 1996; Bergman, 1994; Alber et al., 2001] Often, when searching in databases, people are often interested in close but not necessarily exact matches. The problem consist in finding “approximate” matches, such as spell checking, fingerprint analysis, voice recognition, image understanding and DNA sequences. These processes use some distance measure to compare how close or far are objects among themselves. For this reason they are in general computationally expensive. Therefore, the need for sub linear search is mandatory, hopefully using a mechanism where most of the database is never directly examined. Close objects in tries can be searched using a distance metric satisfying the mathematical equivalent of the triangle inequality, first introduced by [Burckhard et al., 1973] avoiding complex comparisons to each object in the database. Suppose that given 2 State-of-the-Art 33 objects x, y, z from a dataset R, an integer k, and some distance metric d, it is required to find all objects in the database with a distance from x of not more than k. The triangle inequality states that: x, y, z ° R, d(x, y)  | d(x, z) - d(y, z)| (2.12) If we assume now a node p at level l in the trie with value D, every object at leaves descendant from p has a distance d from the key object keyl. Thus, if |D – d(x, keyl)| > k, then we know from the triangle inequality above that d(x, s’) is greater than k for all objects s’ which are descendants of p. Thus search node can be pruned at p. Taken advantage of this property several search algorithms using tries defined some set of key objects or central objects from the universal set, being representative for some data clusters in the data space. Then, as the case for instance of the Triangulation Trie in [Berman, 1994], the trie becomes a representation of the distances from the objects in the database to this set of keys. In some remote sensing image problems the straightforward application of the triangle inequality theorem allows the search algorithm to discard a substantial number of images to compare in the feature space [Alber et al., 2001]. In [Berman, 1994] a Triangulation Trie is defined using only a distance measure as a tool. The only requirement being that this satisfies the triangle inequality property, in order for the algorithm compares distances only for a selected object’s subset. The construction of the trie is done first choosing a set of keys from the universal set, that can be chosen according to some arbitrary convenient criteria. This is important because the performance of searches in the trie depends on the choice of these keys. For each object in the database is created a vector consisting of the ordered set of distances to the key objects. These vectors are input into the trie. Hence, the trie is a compact representation of the distances from the objects in the database to this set of “keys”. In [Heinz, 2002], a Burst trie is proposed for searching string text, in which strings are maintained in order for faster access. Because tries and ternary search trees [Bentley, 1997], [Clement, 2001] are fast but space-intensive, the proposed structure compress data into so-called containers linked to a regular trie called access trie. Searching involves using the first few characters of a query string to identify a particular container. A list structure or a binary search tree can be used to give form to containers, 2 State-of-the-Art 34 so search within its boundaries is fast. When the container becomes inefficient, it is burst, that is, replaced by a trie node and a set of child containers holding each one half of the previously contained strings. The concept of containers is similar to the previous idea of super nodes developed in [Berchtold, 1996] on the structure called the X-tree. Observing the problem with the R*- tree [Beckmann, 1990] consisting in the overlap of the bounding boxes in the directory, which increases with higher dimensions, the authors proposed a split algorithm minimizing overlap by the use of super nodes for high dimensional spaces. Overlap is the percentage of the volume of data that is covered by more than one directory hyper rectangle. This is correlated to the query performance since in processing queries, overlap of directory nodes results in the necessity to follow multiple paths, thus increasing search time. More formally, the overlap of an R-tree node containing hyper rectangles {R1,R2,…,Rn} is defined as: ( ) . , {1.. }, , {1.. } i j i R R i j n i j overlap R i j n ∩ ∪ ∈ ≠ = ∪ ∈ (2.13) ||A|| denotes the volume covered by A. The X-tree consists of three different types of nodes: data nodes, normal directory nodes and super nodes. Super nodes are large directory nodes of variable size (such as multiple of the usual block size). The basic goal of these super nodes is to avoid splits in the directory that result in an inefficient structure. The LC-trie or level-compressed trie is introduced in [Andersson, 1993, 1994] corresponding to a compact version of the standard trie data structure. The central idea in this structure is that the highest complete levels of a trie can be replaced-without losing any relevant informationby a single node of degree mi, the replacement being made top-down. If it is assumed that the input consists of independent random strings from a Bernoulli-type process [Flajolet, 1983], the expected search cost in an LC-trie is O(log log n), which is significantly better than O(log n), achieved by the conventional trie. 2 State-of-the-Art 35 2.6 Data Mining and Statistical Sampling Inductive learning supposes the prior existence of a dataset with records of known class. Depending on the size of the target population the study of a sample from this population is sometimes required. Sampling is the subject of this sub-section. Let us begin by agreeing with [Smyth, 1999] on his assertion that the appreciation of the fundamental role of statistics in data analysis and in general about statistical ideas is an aspect often overlook by computer scientists simply by their lack of understanding. This is due in part by the fact that most courses in computer science give little room for anything other than a cursory introduction to statistics. This does not mean that our approach belongs to the stream of statistical data mining, neither that we share the view of some statisticians that might argue that data mining is not much more than the scaling up of conventions statistical methods to massive data sets. Indeed Data Mining has introduced its own ideas for data analysis, which are quite novel and distinct from any prior work on statistics. 2.6.1 Random sampling Simply stated, in statistical terms a random sample is a set of items that have been drawn from a population in such a way that each time an item was selected, every item in the population had an equal opportunity to appear in the sample This implies that (1) measurements taken on different items (or trials) are unrelated to one another and (2) the joint distribution of all variables remains the same for all items [Johnson, 1998]. Choosing a sample, and more specifically a statistical sample as define above is crucial for instance-based methods. This is particularly true today, in the presence of huge terabyte databases representing the size of available data we are planning to work with. It would take long hours if not days to execute the training phase without selecting just a small subset for this purpose. For this reason sampling is a good solution. But the results of the algorithm obtained from a sample must be representative for the whole population. With this in mind the goal consist in selecting a sample from the population, such that the performance of the mining algorithm is probably close to what it would be if we run it on the entire database [John, 1996]. At the very least, the selected records to form the sample should fulfil the requirements of a statistical simple random sample 2 State-of-the-Art 36 (SRS): “A SRS of size n is taken when every possible subset of n units in the populatio n has the same chance of being the sample” [Lohr, 1999]. This sample set sometimes called “evaluation” set (often confused in the literature with the “test” set), is used in the generation of the model function and permits also carrying out the evaluation of the mining algorithm. The final goal of evaluation is to measure the accuracy of the algorithm, which is the probability of correct classification of previously unseen randomly selected records. These records, only used for this purpose throughout the entire mining process are known as the test set, and they do not form part of the working sample. Sample records form the evaluation set, generally called the training set, which is mined to “learn” about data patterns, thus allowing the development of the classification algorithm. To preserve the validity of the estimation, these two sets must be mutually exclusive during the whole classification process. Out of the many possible existing bias in selecting sample records, we had two main concerns in creating the sample. First, the sample should have the characteristics of a SRS. Second, we want a sample that incorporates class distribution knowledge existing in the whole population database. The reason for this is obviously related to the final goal of building a class predictive model. When not available, information on class distribution can be collected from the evaluation set, calculating simple probabilities for each class. In some other cases prior knowledge from the expert domain exists, as is the case with several of available datasets from the UCI data repository [Murphy, 1994]. It is desirable that the final accuracy of a classifier be estimated using a method with low variance and bias. For this reason, several accuracy estimation methods exist: Holdout or Sub-sampling, k-fold Cross-validation, Leave-one-out, Stratification, Bootstrap [Kohavi, 1995], [Efron et al., 1993], [Mitchell, 1997]. 2.6.1.1 Holdout method The holdout method sometimes called test sample estimation, divide data into two mutually exclusive subsets called a training set and a test set, or holdout set. It is common to designate 2/3 of the data as the training set and the remaining 1/3 as the test 2 State-of-the-Art 37 set. The training set is used in the “learning” process while the test set serves t o measure the quality of the induced classifier. Formally, let 0 = , q$ be the space of labelled records and R = {r1, r2,...,rn} a dataset, where ri = <vi  ,i, ci  $>. An inducer I maps a given dataset R into a classifier  and this in turn maps an unknown record v  , to a class label c  $. The accuracy of classifier  is the probability of correctly classifying a randomly selected record: Acc = P ((r) = c) for a randomly selected instance <r, c>  0. Further let Rh be the holdout set, which is a subset of R of size h, and let *t = R / Rh. The holdout estimated accuracy is defined as: ( ) ( , ) 1 ( , , ), i i h h t i i v c R Acc C R v c h ϕ ∈ = ∑ (2.14) where K(i, j)=1 if i = 0, and 0 otherwise [Kohavi, 1995]. 2.6.1.2 Cross-validation method Cross validation is a method aiming to estimate the error of a given hypothesis generated by a concept-learning algorithm (classifier). The method specifically refers to generalization error, which is the error on data that has not been seen during training. The method is called sometimes k-fold-cross-validation or rotation estimation to indicate that the inducer is trained and tested k times. Given a set of training data and a concept learner this is how cross validation estimates the accuracy of the hypothesis gained by running the learning algorithm on the data set: Randomly divide the training data in k mutually exclusive sub-sets, called the “folds” R1, R2, R3, Rk of approximately equal size. For each one of the k folds t = {1,2,k} the classifier is trained using R/ Rt and tested on Rt. The resulting cross-validation accuracy estimation is the average of the k times the classifier is tested. Formally, let R (i) be the test set that include record ri = <vi, c>. Also let I(R, v) be the label assigned to an unlabelled instance v by the classifier build by inducer I on dataset R. Then the accuracy of a cross-validation estimate is given by: 2 State-of-the-Art 38 ( ) ( ) ( , ) 1 ( / , , ). i i h i i i v c R Acc I R R v c h ϕ ∈ = ∑ (2.15) 2.6.1.3 Leave one out method A special case of cross validation is the so-called leave one out method, where k is chosen as the cardinality of the training set. In other words, for each given example another run of learning is performed using all training data except for this example and the correctness of the classification of the single example left out is checked. For efficiency reasons leave one out is unusual in practice, although in general it will be closest to the real error. Instead, k=10 is a frequently chosen compromise between computational effort and quality of estimation results. 2.6.1.4 Bootstrap method Bootstrap was introduced by [Efron et al., 1993], and consists in given an evaluation file of size n, to create a so-called bootstrap sample by sampling n records uniformly from data with replacement. This is the training set. All other records form the test set. Since the sample is obtained with replacement, the probability of not being part of this list is (1 – 1/n)n  e-1  0.368, and the expected number of distinct objects from the original dataset appearing in the test set is 0.632n. For instance, consider a dataset R = {1,2,3,4,5,6,7,8,9,10,11,12}. Randomly sampling n instances with replacement would produce the following training set D = {1,2,10,7,10,5,6,10,5,1}. The remaining instances would form the test set T = {3,4,8,9}. - 39 - 3 The Trie-Class Algorithm. Basic definitions In this Section we provide a general overview of the Trie-Class algorithm and most of the basic definitions and functions used throughout this thesis, including some examples. We also explain in detail the search mechanism used to extract nearest neighbours and compare its classification skills with a regular k-NN algorithm. 3.1 General overview of the algorithm Our approach to induction is partially based on the instance-based methodology or Nearest Neighbours (NN) [Cover, 1967; Salzberg, 1990; Aha, 1991], sometimes also known as case-based reasoning (CBR) [Aha, 1998]. In general, the basic notions of NN and instance-based methods are the storage of learning data, the use of some metric to carry out similarity computations by means of calculating distances, and some indexing scheme to help the searching mechanism. A distinctive characteristic of NN and CBR in particular is its “lazy” approach to problem solving. According to [Aha, 1998] pure lazy problem solvers exhibit three typical behaviours: • They defer processing the input until they receive a query request. They just store input examples. • They are data-driven, meaning that they respond to requests by combining information from the stored data and, • They discard any temporary intermediate results created during problem solving. NN methods also present a more eager approach, resembling to a certain extent some model-based approaches in that they retain their inputs into an intensional 6 data structure, reply to queries using this structure and keep it for future requests. Combining elements that characterize these methods along with ideas from Decision Trees our approach uses a tree structure as an index to store cells from training data in order to “learn” , permitting at the same time a very fast search of “similar” instances. In a second thinking phase, queries on unseen instances are answered using training instances as model. Two of these instances will be selected from the data structure, 6 Including the rules that describe the inner structure of objects 3 The Trie-Class Algorithm. Basic definitions 40 using a non-Euclidean distance on an attribute-by-attribute basis without normalization. Later, we use different criteria to select one of them as the best available pattern representation of the new unseen instance, as will be explained in Section 6. 3.2 Basic definitions Notation {r R, c L | exp1(r,c) exp2(r,c)} ∈ ∈ • stand for the set of values of exp2 when r and c take values in R and L, and exp1 is true. If exp2(r,c) = r then the expression is reduced to {r ∈ R | exp1(r)}. Definition 1. Let’s consider the closed universe formed by a data file R composed of a finite set of N records r. R = {r1, r2,..,rN } . (3.1) In Supervised Machine Learning we find data containing a set of instances, each one described by a vector of attributes and a class label. Attributes are considered to be predictor or relevant attributes. They are used as independent variables to induce a certain classification hypothesis, which in turn is used to predict the class of an instance, considered the dependent variable. Therefore, much of this thesis is referred to attributes (or features as they are also called), its characteristics, types and values, and the way they can be used to generate the description of the concept, which is at the centre of the learning process. Definition 2. In any given record r we find a finite set of Ai attributes belonging to set S, 1 2 i n S = {A ,A ,..A ,..,A }, a nonempty set. (3.2) Definition 3. Each record r is formed by the Cartesian product of n attribute values A1|a1 x A2|a2 x...x An|an and a class label c. Each attribute Ai has its corresponding value ai, which belongs to domain Ti, such that: 3 The Trie-Class Algorithm. Basic definitions 41 1 2 = , ,.., , , (1.. ), , . n i i r a a a c i n a T c L ∈ ∈ ∈ (3.3) Definition 4. Every record r is associated with one of c class labels belonging to a set L. 7 { } 1 2 , ,.., l L c c c . = (3.4) Definition 5. Each class label c belonging to records r is obtained by the following function: label(r) = c if r = <a, c> . (3.5) 3.3 Definitions on cell discretization In many Data Mining applications large amounts of data as well as large instance vector dimensions demand some form of data reduction. This is particularly true for methods based on instances or Nearest Neighbours. One of the aspects of the problem attacked by Trie-Class, is to reduce the dimension of each feature by reducing the number of possible values an attribute can take. This goal can be reached by applying discretization to data domains, particularly interesting in attributes exhibiting continuevalue types. At the same time, discretization is required in order to work with metric spaces and distance calculations. Discretization has the disadvantage of a potential information loss, allowing two different attribute values to coexist within a given interval thus increasing entropy, a measure of the degree of purity of a given interval with respect to the class. However, the advantage of reducing the search space, a fundamental problem facing almost all algorithms in Data Mining, many times is not harmful for real-world applications [Weiss et al., 1998]. In Trie-Class, discretization is applied to numeric attributes whether discrete or continuous. In the case of nominal attributes, simply each nominal value is assigned a partition of its own. 7 In this thesis we use indistinctively the words class label, class or just label. 3 The Trie-Class Algorithm. Basic definitions 48 function semk() would return true allowing to visualize the predominance of class cj, thus allowing using this information regarding the class at the sub-cell level. Finding how many of these semi-exclusive intervals exist in whole cells is calculated using the function from next Definition 20: Definition 20. The degree of exclusiveness of a cell p corresponds to the fraction i of its n cell component values falling into intervals conforming to the semi-exclusive property. This property is calculated with the following function: ( ) { } ( , ) # 1.. | semk( , , ) / i semp p i n i v i n ϕ ϕ = ∈ • (3.23) We are interested in the fraction of intervals belonging to a given cell complying with the semi-exclusive property when this refers to the same class, so we can have consistent information. Used this way, the presence of one or more intervals of this type increases the probability for the cell to be associated with a given class. Hence, cells having intervals exhibiting this property constitute important class pattern predictors. Definition 21. If all discrete vi values belonging to attribute Ai  R are projected into its corresponding intervals, then the degree of relevance of attribute Ai with value ai denoted with symbol Gi, correspond to the fraction of records falling into those intervals where function semk() is true with respect to the total number of records in R. ( ) ( ) { } i i #| (,,)/ i r R k ord a r semk i k r N δ ϕ = ∈ = ∧ • (3.24) Parameter N represents the total number of records in set R.. Large values for / means a more relevant attribute when compared with others. The opposite represents irrelevant attributes. The next example illustrates this. Example 3.3 Let’s calculate the value of parameter / for two attributes, A1 and A2, each having domain si partitioned in ten equal sized intervals as in Fig. 3.1. The dataset has two classes: A and B. Frequencies for each interval are shown in the row labelled “freq”. 3 The Trie-Class Algorithm. Basic definitions 49 Notice that in this case it does not matter which is the predominant class in the set of semi-exclusive intervals included in the calculation of parameter /as it is the case with function semp(). This is so because it is perfectly possible for the same attribute to have different values that can be associated with different classes. This is precisely what matters for attribute relevance. How many values determine cell class membership. Projecting attribute A1 values into intervals vi , with  = 0.75 vi 0 1 2 3 4 5 6 7 8 9 Total  freq 77 32 62 49 79 20 12 23 11 43 408 Class * * * * * * * * A A 54 54/408=0.132 Projecting attribute A2 values into intervals vi , with  = 0.75 vi 0 1 2 3 4 5 6 7 8 9 Total  freq 227 23 35 17 17 14 12 13 5 45 408 class * A * * B B * B * B 112 112/408=0.274 Note: An asterisk means intervals where function semk() is false. Shadow areas represent intervals where semk() is true with  = 0.75. Fig. 3.1 Attribute values projection in one-dimension to depict its relevance 3.5 Attribute selection Trie-Class uses a tree structure to hold cell patterns as a mean of speeding up searching most similar objects. As search begins in the root of the tree, the input order of attributes is fundamental if we want most similar instances to remain close to each other in the data hyperspace. For this reason determining the order of attributes is a preprocessing phase executed before tree insertion. (Tree build is explained in Section 7). Definition 22. The predictive skill of attributes is a measure of its degree of relevance as defined in Equation (3.24). According with this relevance attributes can be ranked in decreasing order of relevance. 1 2 1 , ,.., ,.., , | | | (1.. ). i n i i i n β δ δ δ δ δ δ + = 〈 〉 ≥ ∈ (3.25) Attributes where its relevance /i = 0, are orderly pushed to the list’s end. These are candidates for elimination (“pruning”), which can be done to improve algorithm 3 The Trie-Class Algorithm. Basic definitions 50 complexity at the expense of some loss in accuracy as shown in Section 4.. An example of a dataset features ordered by its degree of relevance is shown next in Example 3.4. Example 3.4 Let’s consider the Cancer-Wisconsin dataset from Section (5.1.3). It contains nine working numeric attributes representing patient data for cancer diagnosis. Applying formula from Equation (3.24) for each attribute in this dataset, we obtain the following /values shown in Table 3.1 below. They are ranked by its degree of relevance. Table 3.1 Attributes degree of relevance values in Cancer dataset Nº Attribute name Frequency Gi 1 Uniformity of Cell Size 89 0.218 2 Uniformity of Cell Shape 69 0.169 3 Marginal Adhesion 59 0.145 4 Normal Nucleoli 58 0.142 5 Clump Thickness 54 0.132 6 Bland Chromatin 34 0.083 7 Mitosis 22 0.054 8 Single Epithelial Cell Size 16 0.039 9 Bare Nuclei 9 0.022 We show results later in Section 4 showing how classification accuracy changes with changes in accuracy using only relevant attributes. 3.6 Shape definitions The similarity hypothesis sustains that what defines a class is that its members are similar to each other and not similar to member of other classes. Therefore, object similarity is determined using distance calculation between corresponding attribute values using functions such as Euclidean or Manhattan. We are now interested in exploring additional information that might be useful to describe the similarity concept. One such case is constituted by the information concerning intra-attribute relationships within a cell. One of these is the relationship between consecutive attributes belonging to the same cell, which can be represented using the slope representation between these two points. 3 The Trie-Class Algorithm. Basic definitions 51 Fig. 3.2 Slope intersection form of a line For a given line in the xy-plane making angle R with the x-axis, the slope m is a constant given by tan , y m x θ ∆ ≡ = ∆ where x and y are changes in the two coordinates over some distance. In general, a slope represents a quantity, which gives the inclination of a curve or line with respect to another curve or line such as the one in Fig. 3.2. We could graphically represent the shape form of a given n-dimensional cell p drawing in two-dimensions all segment lines between pairs of consecutive attributes. We do this by converting each a cell component element into a point. We use the actual attribute value as the y-coordinate and we assign the attribute’s order number as the xcoordinate. Hence, we could draw all segment lines between the discrete points (1,v1), (2,v2),..,(n,vn). As we keep constant x each segment, segment y = (yi – yi-1) corresponds to a slope between consecutive cell values. An example of such shape representation can be seen in Figure 3.3. In total we would have n-1 line segments to represent a given shape. Designing a shape retrieval method involves other than shape representation, the definition of some similarity measure and the way these shapes will be accessed or retrieved. [Mehrotra, et al., 1995]. To answer this we first define the space H as the space of all h shapes. Within this space shape similarities are found using some distance x b y  y = mx + b 3 The Trie-Class Algorithm. Basic definitions 52 d(h1,h2) in order to compare two shapes. Within this framework we propose the following definitions: Fig. 3.3 A two-dimensional representation of a cell Definition 23. The shape of a cell is defined as the sequence of its m slope components between consecutive values: 1 2 1 1 1 , ,.., ,.., , m ( ), , with ,.., i n i i i n h m m m m v v h H p v v − + =< > = − ∈ =< > (3.26) This newly created shape vector contains positive and negative slope values and is one dimension shorter than the cell vector from which is built. The new space H represents a space change with respect to space Rn. As can be easily seen this space is not metric as some of its properties are not satisfied, namely, positiveness and symmetry. Within this space we can use a distance measure to determine how close or similar two shapes are from each other. We do that using the following function. Definition 24. The shape similarity between two cells, corresponds to the distance between its corresponding shapes: ' ' ( , ) ( , )sp p p d h h = (3.27) Distance d(h’, h) can be any of the standard distances belonging to the Minkowski family explained earlier in Section 2.4.2. (5,v5) (1,v1) y x shape of p (2,v2) (4,v4) (3,v3) (6,v6) 3 The Trie-Class Algorithm. Basic definitions 53 Using shape distances to represent cell similarities can help identifying shape patterns in a shape data space. If similar shapes relate to the same class, then this information can enrich the similarity concept. The degree of shape similarity between two shapes is affected by the actual value of each slope and the slope sign itself, which indicates the relationship between two consecutive attribute values. We illustrate in example 3.5 shape construction and a similarity function. Example 3.5 Imagine a dataset containing five cells p1,p2,..,p5, belonging to some training set, each one formed by seven cell components. Cell values are indicated in Table 3.2. Table 3.2 Cell vectors and their component values Cell component values Cells v1 v2 v3 v4 v5 v6 v7 p1 3 6 4 9 4 1 9 p2 17 10 14 9 9 11 6 p3 1 19 13 23 10 2 3 p4 12 9 7 4 8 15 19 p5 15 5 13 8 7 13 4 px 19 9 15 8 9 12 5 The task consists in classifying a new cell px from the test set using the shape similarity function. Let’s first convert all cell vectors from Table 3.2 into shape vectors applying the shape formula in (3.26). We obtain the shapes and its values indicated in Table 3.3. Table 3.3 Shape vectors corresponding to cells from Table 3.2 1 ( ) i i v v + − h1 3 -2 5 -5 -3 8 h2 -7 4 -5 0 2 -5 h3 18 -6 10 -13 -8 1 h4 -3 -2 -3 4 7 4 h5 -10 8 -5 -1 6 -9 hx -10 6 -7 1 3 -7 3 The Trie-Class Algorithm. Basic definitions 54 If we draw the two-dimensional representation of these h vectors, we have the figure shown next in Fig. 3.4 -15 -10 -5 0 5 10 15 20 order position values h1 h2 h3 h4 h5 hx Fig. 3.4 Shape representation of six cell vectors In this graphical representation, the y-coordinate corresponds to the m values and the x-coordinate corresponds to the corresponding mi order number within shape h. Next, apply the shape similarity function from Equation (3.27) to calculate distances between each shape and hx using values from Table 3.3 above. Using the Manhattan distance we obtain the following results with the sp value shown in the last column on Table 3.4. Table 3.4 Shape distances and similarity function values x m m − sp(hx, hi) d(hx,h1) 13 8 12 6 6 15 60 d(hx,h2) 3 2 2 1 1 2 11 d(hx,h3) 28 12 17 14 11 8 90 d(hx,h4) 7 8 4 3 4 11 37 d(hx,h5) 0 2 2 2 3 2 11 As visually observed in the graphic of Fig. 3.4, the smallest sp values correspond to those were shapes h2 and h5 are involved, (represented by segments with small triangles 3 The Trie-Class Algorithm. Basic definitions 55 on its ends) meaning that the distances amongst these shapes are the smallest ones with respect to hx. Obviously distance measures between shapes applied in the new shape space, although similar, do not yield the same results as the corresponding cell distances applied in the original record space. This can be seen in next Table 3.5, where we show the result of applying Euclidean and Manhattan distances to cells from Table 3.2, and its comparison with shape distances after changing space values. As it was in Example 3.4, all distance calculations are from px to all other points. Table 3.5 Distance comparison using selected criteria Total distance values by criterion Manhattan Euclidean Shapes d(px,p1) 51 549 60 d(px,p2) 7 9 11 d(px,p3) 58 758 90 d(px,p4) 37 335 37 d(px,p5) 14 42 11 As observed, in relative terms distance from p2 to px is the smallest for the Euclidean and Manhattan distances. As for the shape distance, distances to p2 and p5 are equally the smallest from px as confirmed by its graphical shapes from Fig. 3.4. Using shapes as a classification criterion yields good results as indicated later in Table 6.2 from Section 6. As will be seen, its class prediction capabilities are better that those of using a standard distance for the same purpose, when applied to contending pre-selected close neighbour cells p1 and p2. We have no formal demonstration at this point for the reason for this. Intuitively we believe that additional inter-attribute relationship information, besides attribute value information makes this difference. 3.7 Searching for nearest cells In this section we introduce the search mechanism done by Trie-Class to extract close neighbours with respect to some unknown instance. This is the first approach we use to determine similarity. A second approach will be done afterwards, where these pre- 3 The Trie-Class Algorithm. Basic definitions 56 selected cell patterns are carefully inspected through the use of Decision Parameters explained in Section 6. Eventually, the number of close neighbours selected could be any. We have chosen to implement our algorithm for just two of them, and we have kept this number in view of our results. The method we propose here to find nearest neighbours does not use the standard family of distances used by regular k-NN methods. It corresponds to a “greedy” search method in general, as the best solution at each point is taken using only available information at each node of the tree structure. To illustrate this, lets assume the existence of a new query cell px with format as in Equation (3.10). Lets call p+ the ideal closest object to px in the entire dataset. The algorithm’s task consists in extracting the closest cell to p+ and as a result the algorithm will obtain a cell we call p1 In the original NN algorithm this is done using a “brute force” method or some type of index, applying to them the Euclidean distance from px to considered objects. In our case distance calculation proceeds attribute by attribute, restricting the allowable search space for a given attribute based on previous attribute values. The allowable search space keeps cell component values in order, so the closest elements to pxi are searched starting at pxi-1 and pxi+1 respectively. The search proceeds to both “sides” of pxi looking for the closest element. As soon as one of these values is closer to pxi it is selected. Trie- Class uses a tree structure, which exactly allows doing this. If we call cells p1 and p2 the two “closest” objects to px found in a space with those characteristics, then it will be always true that: 1 2 ( , ) ( , ) and ( , ) ( , ) x x x x d p p d p p d p p d p p + + ≤ ≤ We argue later in Section 7 that objects p1 and p2 are more rapidly extracted using this structure when compared with regular NN methods, and also that they are better class predictors. In the next subsections we explain the way this is done introducing a general search algorithm for a closest cell, which is the same independently of the number of cell patterns that might be extracted. 3 The Trie-Class Algorithm. Basic definitions 57 3.7.1 Selecting closest pattern The algorithm extracts close cells one by one. In our case it first get cell p1. To do this initially dispose of the entire set P as its search data space. The extraction of cell p1 progress adding one more cell component at a time, where these cell components are the ones found closer to its corresponding px elements. As the search progresses, smaller and smaller subsets of P constitute the allowable search space to obtain the next cell component element. For each one of these Pi spaces its dimension and location is given by the values forming the corresponding sub-cell qi. We explain next the way this space is defined. The extraction of any cell is done attribute by attribute, with the algorithm proceeding incrementally. Any sub-cell qi is of the form qi = qi-1, k! where k is the next cell component element. Starting with i = 1, assuming an empty sub-cell q0= <> and knowing element qi-1, the problem consist in finding some interval k1 representing the next cell component, which is the closest value to the unknown element kx. The found element k1 must satisfy the following property: ( ) ( ) ( ) 1 1 1 x x i k K q k k k k − ∀ ∈ • − ≤ − (3.28) Where the set K(qi) is defined by: ( ) { } , i i i K q k | q k P = < > ∈ (3.29) Cell component k1 is the closest element to kx among the elements in K(q) and Pi correspond to its search space. As each new cell component element ki is added, the search space for next element k1+1 is further restricted to the space defined by the previous sub-cell qi which is Pi. So the search space of the last element gets confined to space Pn, thus avoiding the search of most of the total data space. Notice that as it happens with decision trees, the selection of each new k element divides the space into axis-parallel hyper planes. From the class viewpoint, as long as the search process does not reach the last cell component member, or sub-cell qi is not associated with just one class, the selection of 3 The Trie-Class Algorithm. Basic definitions 64 3.9.2 Partition granularity As we will explain in Section 4, Trie-Class pre-process data before tree building, in such a way that independently of the data type of attributes, their values are discretized. Discretization is the process by which the domain of a continuous attribute is partitioned into a finite number of intervals. This discretization is done using Equations (3.7), (3.8) and (3.9). In general, small numeric attributes domain, whether discrete or continuous are not discretized at all and the corresponding unit of the domain is used as a default partition, as in Trie-Class this is more a data structure requirement rather than a step in the classification process itself. In any case, for any cell p  P we assume that the granularity of all partitions generated by the discretization process is such, that allows every cell in the training set to have a known label, making function nlabels(p) = 1. 3.9.3 Class membership, Patterns and the Continuity Principle Which is the spatial class distribution of object in Supervised Learning? Are similar classes distributed into continuous areas in that space or rather they are scattered throughout that space at random? Intuitively, one might think that class distribution in real data tend to be characterized by continuity, meaning that there exists some correlation between attribute values and its mapping to classes, and therefore there are data areas of continuous class distribution. Many classification algorithms compress the feature space based on the certainty that just a few attributes bear the key to class membership. If this is the case, then class distribution indeed presents spatial continuity. We apply this principle to rather small regions of the dimensional R space covered by cells of the same class. If a new cell of unknown class falls into one of these regions, and existing training cells of the same class are located at distances representing upper and lower boundary values with respect to the unknown object, then we assume that its class is the same as the one hold by cells in that neighbour area. In Trie-Class specifically we apply this principle to sub-cells q as defined in Equation (3.12). 3 The Trie-Class Algorithm. Basic definitions 65 For instance, lets suppose the existence of sub-cells: <qi-1, k1> ° P and <qi-1, k2> ° P Applying function labels from Equation (3.17) to sub-cells we obtain: labels(<qi-1, k1>) = {c} and labels(<qi-1, k2>) = {c} then, for a new interval k ° [k1,k2] labels(<qi-1, k>) = {c} Thus, in interval k sub-cells will also exhibit class c. This criterion is applied in Trie- Class for all spatial areas with no available pattern information provided that cells with the same class bound those regions. In that sense, every other possible new query cell px is always approximated to some of the existing classes in the dataset. - 67 - 4 Pre-processing Data Before Mining The task of extracting knowledge cannot even begin without preparing data to fulfil the requirements of a particular mining algorithm. Preparation time taken before mining data represents a considerable portion of the whole knowledge extraction process. This fact is often overlooked by researchers fighting for a split second of execution time, forgetting the hours if not days spent in the preparation of data. For a given algorithm, the number of tasks involved in preprocessing data is independent of the size of the database. In any case, the farther apart the data format is with respect to the needs of the algorithm, the longer the time it takes to complete pre-processing it. Preparation time must not only be considered as the manipulation of data itself, but as their overall comprehension and meaning. Before anything else we have to know about data characteristics and its representation, including type of variables and their meaning, the type of noise and missing data which we might expect, information about the classes and its distribution, the frequency of updates and the cost of misclassification among others. But most important of all, we definitely have to know the purpose of the data owner, and the exact notion of the problem he/she wants to solve. This is fundamental, if we are planning to make any sense out of data. In the rest of this section, we explain the data preparation needed prior to tree construction and execution including sample selection, attribute value discretization, the treatment of categorical attributes, attribute selection and the effects of changing interval size after discretization. 4.1 Converting records into discretized patterns Attribute values belong to one of several data types: qualitative or non-numerical (symbolic, linguistic), quantitative or numerical (continuous, discrete). Because our classification algorithm and the ranking of attributes are based in a nominal space, all continuous attributes are first discretized. This is done, based on the information taken from a user-supplied dictionary file 11 . 11 For a layout of the dictionary, see Annex I. 4 Pre-processing Data Before Mining 68 Discretization is the process of partitioning the domain of a continuous attribute into a finite number of intervals [Lebowitz, 1985]. There are three criteria to classify discretization methods: global vs. local, supervised vs. unsupervised, and static vs. dynamic [Dougherty, 1995]. Numerous discretization methods used to induce one-level decision trees and instance-based methods utilize the class label in the partitioning of the data space [Payne, 1998]. Others use domain specific information [Lebowitz, 1985; Aha, 1995]. Still in some other cases the discretization process consider the number of instances in the interval [Cattlet, 1991]. We use the Equal Interval Width (EIW) single feature discretization method (sometimes called binning) [Wong et al., 1987], which do not make use of instance classes in the discretization process. For this reason sometimes it is called unsupervised discretization method. Intervals are represented by discrete integers using the symbol si, which corresponds to the number of intervals within a given domain. Function ord() described in (3.8) does this conversion. Notice that when ai and mi are equal, vi equals zero, which corresponds to the first possible interval value. The number of intervals obtained on each partition, are given by Equation in (3.7). For attributes represented by rational numbers the corresponding interval value is calculated according to Equation (3.8). For categorical attributes this simply corresponds to its ordinal value, as described in Equation (3.9). If a priori knowledge on domain information exists on the actual order of symbolic attributes, as done in some discretization methods [Kerber, 1992], then the interval value represents the corresponding order number, which is set in the dictionary (see Appendix I). Next section specifically deals with symbolic attributes. If this information does not exist, one has to be careful of not imposing any order on these values. In [Brodley, 1995a], when a feature has more than two observed values, then each featurevalue pair can be mapped to a prepositional feature, which becomes true if and only if the feature has the particular value in the instance. We explain in Section 4.2 the distance between two unordered symbolic values done in Trie-Class. It could be argued that using binning as discretization method causes us to lose information about the class distribution in the nth dimensional space. This effect is even more negative, in methods where discretization is done with the purpose of identifying class membership, using the so-called impurity or goodness measures. [Murthy et al., 4 Pre-processing Data Before Mining 69 1994]. The goal of most of these methods is to use discretization as an important component of the classification model. Some examples of these methods are Gini Index criterion [Breiman et al., 1984], Minimum Description Length [Rissanen, 1978], information gain [Quinlan, 1986], ChiMerge system [Kerber, 1992], recursive entropy discretization [Fayyad et al., 1993], Max minority [Heath et al., 1993], maximal marginal entropy [Chmielewski et al, 1994], StatDisc [Richeldi et al., 1995]. Although inferior to the entropy family of methods as shown in [Fayyad et al., 1993], the difference in performance between equal width discretization and some of these methods is small [Dougherty et al., 1995]. Other than the simplicity and lower computational cost of this method our goal with discretization has to do with storing training records in an index of manageable size, in order to increase searching efficiency, as long as the number of partitions is representative of the concept description. Partitioning attribute domains into si intervals helps reducing tree size as well as in some cases allowing concept generalization. The well-known loss of information problem derived from discretization is attenuated in our case. The most important information for each sub-cell individually considered is its class. With this respect, the only negative effect of this is class overlapping, which has the net effect of postponing class membership in sub-cells as they increase their size of component members. As additional help to attenuate some loss of information due to discretization, we keep class distribution information for semi exclusive values in a specific file as explained later on Section 7. It has also being related the equal width binning mechanism to a higher sensibility to outliers [Dougherty, 1995]. To help with this, semi-exclusive intervals can be tuned setting parameter M in Equation (3.22) to a somewhat larger threshold value. 4.2 The special case of categorical attributes Many Machine Learning and Pattern Recognition methods require that input take the form of numeric values. As Trie-Class uses a distance calculation for the extraction of near neighbours to some unknown cell px, the presence of symbolic attribute types represent a problem of its own. Symbolic values are values representing concepts that cannot be ordered, and therefore, there is not an obvious distance between them. This is 4 Pre-processing Data Before Mining 70 the case for instance for the letters of the alphabet, or concepts such as “red”, “white ” and “blue” (provided we do not consider their wave length values of course). Near neighbours methods resort to special metric schemes to solve the similarity problem in these cases, a problem central to pattern matching. Many methods have been proposed in the literature to overcome this problem, such as the Value Difference Metric (VDM) from [Stanfill, 1986], counting the features that match as in [Towel, 1990], the PEBLS system that incorporate MVDM, a modified version of VDM in [Cost, 1993]; the basic idea of the later being that two values of the same attribute are similar if they give similar likelihood for all possible classifications. Also, the Heterogeneous Euclidean Overlap Metric (HEOM) which basically attributes binary values to distances depending whether two values of the same attribute are equal or not equal, the Minimum Risk Metric (MRM) which directly minimizes the risk of misclassification using conditional probabilities [Blanzieri, 1999]. In many cases applications symbolic attributes appear along with continuous attributes. For this reason it is used a heterogeneous distance function, as is the case with the software IB1, IB2 and IB3 [Aha et al., 1991; 1992] as well as the one used in [Giraud-Carrier et al., 1995]. This function defines the distance between two values x and y of a given attribute a as: ( ) ( ) 1, , , if x or y is unknown, else d x y overlap(x,y) if a is nominal, else a rn_diff x y a       =         (4.1) When any of the attributes is unknown a maximal distance of 1 is returned. The overlap function is defined as: ( ) 0, , 1, if x = y overlap x y otherwise   =     (4.2) and the range-normalized difference rn_diff is defined as: 4 Pre-processing Data Before Mining 71 ( ) _ , min a a a x y rn diff x y max − = − (4.3) Where maxa and mina are the maximum and minimum values respectively observed in the training set for attribute a. The normalization serves to scale the attribute down to the point where differences are most of the time less than one. Overall, Trie-Class uses a heterogeneous distance calculation. The first one explained in Section 3.7 search cell patterns close to the unknown cell px. The second one used within the context of decision parameters, use a straightforward distance calculation when comparing two already pre-selected cell patterns, which will be shown in Section 6.1.2. For the case of symbolic attributes, Trie-Class uses a simple distance calculation. It is based on conditional probabilities in order to determine the distance between categorical attributes. As it was explained in Section 3.7, for the ith attribute belonging to the unknown sub-cell qx = <qxi-1, qxi>, the problem consist in determining whether element qxi is closer to element k1 or element k2 both belonging to the set of sub-cells p = <qi-1, k>. If qx presents the same value of some existing element k, then distance is zero and element k is selected. If not, Trie-Class uses the distance computation that we explain next. Definition 26. The distance between two categorical attributes vx and vi given the class c of vi, depends on the probability of class c given value vx. ( ) ( ) 0, , ( , ) 1 | | , , , , x i x i x i x i i i i if v v else d v v P c v label v c c c L v v s  =  =  − = ∈ ∈   (4.4) Expression P(c | v) expresses the conditional probability of class c given value vx and it is calculated as the prior probability of c times the joint probability of c and v: ( ) ( ) ( ) , P c v P c P c v = ∩ < (4.5) The meaning of this distance calculation is simple: the larger the probability that vx is associated to the class of vi, the shorter the distance between them. When this 4 Pre-processing Data Before Mining 72 probability is zero, the distance is a maximum, i.e., equal to one. If the probability is the maximum then distance is zero. As can be seen, this distance depends on the Prior Probability of a given class, represented as P(c), and the joint probability of value vx and the class associated with value vi. When comparing distances d(qx, k1|c1) and d(qx, k2|c2) where c1 and c2 represent the known classes of k1 and k2, the distance calculation is indirectly calculated and restricted only to the correlation of qx against classes c1 and c2. The intuition behind this is simple. When choosing the next closest element for subpattern qx, the only reference is the class associated with each of the two contending members. Therefore, the “closest” neighbour will be the one where its class correspond to the class that qx also better relates. When the label associated with vi is unknown and labels(qi) > 1, Trie-Class resort to one of the options of the general search case, which were described in Section 3.7. In all other cases the algorithm uses Equation (4.1). This mechanism works better than the simple overlap idea of Equation (4.4). We tested for this effect datasets Adult, Annealing, German credit and Census, which contain an important number of symbolic attributes. Classification performance when considering distance as decision parameter did improve on average over 2.5% when compared with the simple overlap distance for the same datasets. Next we show a simple example of distance calculation for symbolic attributes as done by Trie-Class. Example 4.1 Suppose a dataset formed by multidimensional attribute vectors, and attribute Ai is symbolic and its domain set consisting of Ai = {v1= “blue”, v 2 = “red”, v 3 = “yellow” }. The set of available classes in this dataset is L = {c1 = “A”, c2 = “B”, c3 = “C”}. Table 4.1 below shows prior class probabilities hypotheses and also joint probabilities for each class given the value. These data was compiled using training set data. Imagine we are given a new query value for sub-cell qx = (v3 = yellow, c = ?) with unknown class. Using the search process Trie-Class comes up with two possibilities as 4 Pre-processing Data Before Mining 73 the nearest sub-cells: q1 = (v1 = blue, c1), and q2 = (v2 = red, c2). The problem consist to know whether value yellow is closer to value blue or red, i.e., whether distance d1(v3,v1) is greater or smaller than distance d2(v3,v2). Table 4.1 Class distributions by value for a symbolic attribute Categorical values Class hypotheses c1 c2 c3 Prior class hypotheses P(c) 0.50 0.30 0.20 1.0 v1=blue 0.40 0.30 0.25 v2=red P(cv) 0.24 0.04 0.45 v3=yellow 0.36 0.66 0.30 Class probability 1.00 1.00 1.00 Using values from Table 4.1 and applying Equation (4.1) we obtain the following results: d1(v3, v1) = (1 – 0.18) = 0.820 and d2(v3 ,v2) = (1 – 0.198) = 0.802. So d1(v3, v1) > d2(v3, v2), value yellow is closer to value red than to value blue. Thus, there is a greater likelihood that the class corresponding to value yellow is c2, which is the class associated with value red. 4.3 Feature reduction and elimination Data Mining techniques face the challenge represented by the so-called dimensionality problem. Often, data is represented by datasets containing N instances each of them formed by n features or attributes. Sometimes know as multivariate data, it can be thought of as a (N x n) data matrix. The dimensionality n plays a significant role in multivariate modelling. In text classification problems, web traffic, commercial supermarket transactions or clustering of gene expression data, n can be as large as 103 or 104 dimensions and the amount of data needed according to density estimation theory scales exponentially in n. This is the so-called “curse of dimensionality” problem. Fortunately, transaction data is typically sparse, meaning that only a small percentage of the entries in the N x n matrix are nonzero. Taking advantage of this, the idea of using subsets of items or itemsets has been developed in market basket analysis, which 4 Pre-processing Data Before Mining 80 As expected, a large reduction in the number of attributes results in greater error rates although this could be user controlled by reducing attributes up to a maxim error value 0 accepted as stated in Equation (4.4). In the face of large datasets with high dimensions where traditional feature reduction methods represent very high computational costs, this method can be a fair solution. - 81 - 5 Evaluation and Results In this section, we present experiments to support the claim that Trie-Class compares favourably over a wide variety of induction algorithms tested on various data domains. We performed classification experiments with Trie-Class on several datasets and compared them against other classifiers in terms of accuracy and error figures, as we did in [Serendero et al., 2001 and 2003]. Additionally we use the well-known tool bench “WEKA” [Witten et al., 2000] to test selected typical classifiers running on our own hardware. The selection of classification tools used for testing is rather arbitrary and it was done with the purpose of offering a comparison with the most typical and different techniques. In presenting our results form these two different sources we use the same datasets. These datasets include from 2 to 10 classes, from 150 to half a million instances of available data and from four up to 56 attributes. All types of data can be found in these datasets, from discrete to symbolic, thus being somehow representative of the many available existing data for research in the public domain. Datasets used for testing Trie- Class come from public domain in the web, mainly from the U.C.I., [Murphy, 1994]. In the rest of this Section, we provide a brief description of datasets used in our experiments, the evaluation method to obtain results and present our results from two different sources. 5.1 Data used in experiments We next describe briefly each one of the datasets used in our experiments. They were manipulated to fit our algorithm from the original state in which we obtain them from the Web. The explanation that follows was taken from the data owners or researches using the data themselves. 5.1.1 Adult dataset. (Census USA 1994) B. Becher extracted data for this dataset from the 1984 USA Census Bureau Database. Found at UCI repository this database was given by R. Kohavi and B. Becker, and first quoted by [Kohavi, 1996]. It contains 45,222 instances after removing 5 Evaluation and Results 82 unknown values. Around 65% percent of these are used for training and the remaining 35% for testing. There are fourteen (14) attributes, most of them symbolic or categorical and two (2) classes: people earning up to fifty thousand dollars a year or more. The problems consist in determining whether a person earns over USD$50,000 per year. Classes are labelled as ‘>50K’ and ‘<50H’ and their probabil ity distribution is: Probability for label '>50K': 23.93% / 24.78% (without considering unknowns). Probability for label '<=50K': 76.07% / 75.22% (without considering unknowns). 5.1.2 Annealing dataset Donated by David Sterling and Wray Buntine, this database contains 798 instances and 38 Attributes. Out of these, six are continuously valued, three are integer-valued and the remaining twenty-nine are nominal-valued. There is six classes with one of them holding over 80% of records. This dataset contains many '-' values literally defined by the authors as ‘not applicable’, which are different from ‘missing values’, indicated with a ‘?’ Therefore, they can be treated as legal discrete values, which we have done in the case of all twenty-nine symbolic attributes. For a detail of the used dictionary definition, see Appendix II. There are also many missing attribute values in this dataset. We convert them all to the mean value of each class distribution group. 5.1.3 Breast Cancer (Wisconsin) dataset This dataset is one of several from the UCI repository [Murphy, 1994], and it was originally obtained from the University of Wisconsin Hospitals, Madison from Dr. W. H. Wolberg [Mangasarian, 1990]. There are originally 699 instances but we have eliminated 16 for missing some attribute values, so only 683 are used. Out of ten attributes, the first one is just a reference number so only nine (9) attributes are used. All of them are numeric with an equal domain value ranging from one to ten. There are two possible class labels: benignant or malignant and they have a distribution of 458 instances (65.5%) for the benignant class and 241 instances representing 34.5% for the malignant class. 5 Evaluation and Results 83 5.1.4 Dermatology dataset This database is from the UCI repository,, and was originally owned by Nilsel Ilter and H. Altay Guvenir. The database contains six classes, 366 instances and 34 attributes, one of which is nominal. The aim is to determine the type of Eryhemato-Squamous Disease. The differential diagnosis of this disease is a real problem in dermatology. They all share the clinical features of Erythema and scaling, with very little differences. 5.1.5 Diabetes (Pima Indian) dataset This dataset was originally prepared for the use of participants for the 1994 A.A.A.I. Spring Symposium on Artificial Intelligence in Medicine. Original donor is V. Sigillito from the National Institute of Diabetes and Digestive and Kidney Diseases, USA. There are 768 instances on this dataset where all patients were females at least 21 years old of Pima Indian heritage. Each instance has eight attributes. There are two possible classes. The diagnostic investigates whether the patient shows signs of diabetes according to World Health Organization criteria or not. There are no missing attribute values. Class Distribution is: No diabetes: 500 (65.1%). Positive for diabetes: 268 (34.9%). 5.1.6 Forest Cover type dataset Original donors of this database available since 1998 are from the Forest Service and the University of Colorado, USA. Owners are J. A. Blackard and the Colorado State University. There are 581,012 instances in this database, each representing a 30 x 30 meters square cell of undisturbed forest. Each of these holds 12 attribute measures and 54 columns of data. Ten of these attributes are quantitative variables, four are binary (wilderness areas), and forty represent binary soil type variables. Natural resource managers responsible for developing ecosystem management strategies require basic descriptive information including inventory data for forested lands to support their decision-making processes. However, managers generally do not have available data from neighbouring lands outside their immediate jurisdiction. One 5 Evaluation and Results 84 method of obtaining this information is using predictive models. Thus, the problem consists in recognizing various forest cover types as classes among the eight existing groups: Spruce/Fir, Lodge pole Pine, Ponderosa Pine, Cottonwood/Willow, Aspen, Douglas fir and Krummholz. Class distribution is largely dominated by two of these classes, holding around 80% of the instances among themselves (Spruce-Fir and Lodge pole Pine). We use a stratified sample of around 56,800 records with splits in 60 and 40% for training and testing datasets as shown in Table 5.1. 5.1.7 Heart disease dataset (Cleveland). From UCI repository, this database is from 1998 and the donors and responsible for the data collection are: 1. Hungarian Institute of Cardiology. Budapest: A. Janosi, M.D. 2. University Hospital, Zurich, Switzerland: W. Steinbrunn, M.D. 3. University Hospital, Basel, Switzerland: M. Pfisterer, M.D. 4. V.A. Medical Centre, Long Beach and Cleveland Clinic Foundation: R. Detrano, M.D., and Ph.D. This database contains 303 cases, including 13 attributes (4 cont, 9 nominal). There are seven vectors with missing values. Only two classes used out of the original five (no, degree 1, 2, 3, 4). Class distribution: 164 (54.1%) no, 55+36+35+13 yes (45.9%) with disease degree 1-4. We use all 303 vectors replacing all missing values with the mean value of their class group. 5.1.8 Heart disease Statlog Donated by R. King among a group of other databases, this particular version of the heart disease dataset contains 270 instances with 13 attributes each, (extracted from a larger group of 75), Among them, there are six real continuous values, three ordered, one ordered and three nominal or symbolic. There are no missing values. Out of the 270 instances, 150 plus 120 observations were selected from the 303 cases of the Cleveland Heart database. There are two classes to be predicted: Absence or presence of heart disease in patients. 5 Evaluation and Results 85 5.1.9 Hypothyroid dataset This dataset originally used by Quinlan in the case study of his article "Simplifying Decision Trees" (International Journal of Man-Machine Studies (1987) 221-234) contained 3772 learning and 3428 testing examples. There are 21 attributes on each instance, out of which 15 are binary and 6 continuous. There are three possible classes and the problem is to determine whether a patient referred to the clinic is hypothyroid. These classes are: normal (not hypothyroid), hyper function and subnormal functioning. Because 92 percent of the patients are not hyperthyroid, a good classifier must be significantly better than 92%. As we show later in this section, in our case this figure is 99.3%. All binary attribute fields with missing values were conserved as legitimate symbolic values. These correspond to attributes numbers: 2, 5 till 17 and 19th. 5.1.10 Iris dataset From Fisher, (1936), this is one of the best-known databases to be found in the area of pattern matching. The data set contains three classes of 50 instances each, including four attributes. Each class refers to a type of iris plant. One class is linearly separable from the other two and these are not linearly separable from each other. 5.1.11 Pen-Based Recognition of Handwritten Digits: “pendigits” dataset Donors of this dataset are E. Alpaydin and F. Alimoglu from the Department of Computer Engineering at Bogazici University, Istanbul, Turkey. There are 10,992 instances in this dataset, each with sixteen (16) attributes and ten (10) classes. The authors have used 7494 instances for training and validation and 3498 instances for test. All 16 attributes are integers in the range 0 to100. The database consists of a collection of 250 samples from 44 writers. The samples written by 30 writers are used for training, cross-validation and writer dependent testing, and the digits written by the other 14 are used for writer independent testing. A WACOM PL-100V pressure sensitive tablet with an integrated LCD display and a cordless stylus are used to collect handwriting samples. Each writer is asked to write 250 digits in random order inside boxes of 500 by 500 tablet pixel resolution. Written digits are represented as constant length feature vectors. 5 Evaluation and Results 86 5.1.12 Satellite image dataset (STATLOG version) The Statlog databases are a subset of the datasets used in the European Statlog project and the original title of them is: Statlog Databases. Donors are R. D. King and the Department of Statistics and Modelling Science, University of Strathclyde, Glasgow, Scotland. The databases available here were in used in the European Statlog project, which involves comparing the performances of machine learning, statistical, and neural network algorithms on data sets from real-world industrial areas including medicine, finance, image analysis, and engineering design. The Landsat Satellite database consists of the multi-spectral values of pixels in 3x3 neighbourhoods in a satellite image, and the classification associated with the central pixel in each neighbourhood. The aim is to predict this classification, given the multispectral values. In the sample database, the class of a pixel is codified as number. There are 6,435 instances in this dataset, where 4435 instances were used for training and the remaining 2000 cases were used for test. There are 36 semi-continuous attributes with numeric values ranging from zero to 255. There are six decision classes: 1, 2, 3, 4, 5 and 7. The original database was generated from Landsat Multi-Spectral Scanner image data. The sample database was generated taking a small section (82 rows and 100 columns) from the original data. One frame of Landsat MSS imagery consists of four digital images of the same scene in different spectral bands. The database is a small sub-area of a scene, consisting of 82 x 100 pixels. Each line of data corresponds to a 3x3 square neighbourhood of pixels completely contained within the 82x100 sub-area. Each line contains the pixel values in the four spectral bands (converted to ASCII) of each of the nine pixels in the 3x3 neighbourhood and a number indicating the classification label of the central pixel. In each line of data the four spectral values for the top-left pixel are given first followed by the four spectral values for the top-middle pixel and then those for the top-right pixel, and so on with the pixels read out in sequence left-to-right and top-to-bottom. Thus, the four spectral values for the central pixel are given by attributes 17,18,19 and 20, which are the attributes suggested by the authors to build predictive models. 5 Evaluation and Results 87 5.1.13 German credit dataset This dataset is a donation of Dr. H. Hofmann, from the Institute of Statistics, at the University of Hamburg, Germany. There are 1000 instances on this database. Two datasets are provided. The original dataset contains categorical/symbolic attributes. There exists also a version with numeric attributes for those classifiers that cannot handle categorical attributes. This file has been edited and several indicator variables added to make it suitable for this purpose. Several attributes such as attribute 17 are coded as integers. This was the form used by Statlog. There are 20 attributes (7 numerical and 13 categorical) in the original version, whereas are 24 attributes in the numeric version. The problem in this dataset consists in correctly classifying bank creditors as “bad ” or “good” . The dataset requires the use of a cost matrix, shown below 1 2 ---------------------------- 1 0 1 ----------------------- 2 5 0 (1 = Good, 2 = Bad) The rows represent the actual classification and columns represent the predicted classification. In this dataset, it is worse to class a customer being good when in fact is bad, than to class a customer as bad when it is good. 5.2 The evaluation method used by Trie-Class The method to evaluate our classification algorithm’s predictive accuracy, consists in repeatedly splitting of the evaluation data * into two mutually exclusive sets: Rh training and Rt test sets in 6/10 and 4/10 proportions respectively carrying both of them approximately the same class distribution as the one observed for the whole population (see Fig.5.1). We do this applying the stratified sampling strategy. One first pass over the evaluation data is done to obtain class distribution figures by copying records into subsets of the same class, thus creating as many subsets as classes exist. Out of each one 5 Evaluation and Results 88 of these, we randomly pick a subset of records without replacement, which amount according to their class distribution proportion calculated as: { } ( ) ( ) ( /100) ( /100) i i T Sample R Sclass N = × × (5.1) Function Sclass (i) returns the number of instances on a given class subset. The total size of the sample is then given by: { } ( ) # i TSample r Sample = ∈ (5.2) Tsample corresponds to the size of the training set. All complementary records to TSample in N go into the test set. This whole process is repeated 10 times. Each time, the classifier is rebuilt from scratch and trained again on a new training set. Estimating accuracy is done using once the new test set as input. Average mean error and standard deviation values are calculated from these runs. An example of stratified sample is shown in Table 5.1. It corresponds to the forest cover type dataset [Murphy, 1994]. This file contains 581,012 records and seven classes. Out of that total we have taken a sample of around 10% of the global population containing 56,800 records, with approximately the same class distribution. Database      "!#! $"%&$'( $ Class distribution )+* ,"--/.10"243* 5768#9:; <= ><>= ?A@ >4BC?D EGF4H FIJAK LM N OPQRST U V W7X4YZ"[ \ ] ^ _ `Gabdce f gih"j Sample (1) 5 Evaluation and Results 89 Fig. 5.1. Flowchart for training and test sample subset selection As shown in Table 5.1, the stratified sample technique preserves identical class distribution in the training file if compared with the distribution in the entire population. Table 5.1 Stratified sample characteristics in forest covert dataset Forest covert dataset Typical training file Sample size Class distribution Size (recs.) % Size % Size % Spruce fir 211,840 36.5 20,700 36.5 16,642 48.1 Lodgpole Pine 283,301 48.8 27,700 48.8 12,451 36.4 Ponderosa Pine 35,754 6.2 3,521 6.2 1,875 5.5 Cottonwood/Willow 2,747 0.5 284 0.5 176 0.5 Aspen: 9493 1.6 908 1.6 550 1.6 Douglas-fir 17,367 3.0 1,700 3.0 1,039 3.0 Krummholz 20,510 3.5 1,988 3.5 1,178 3.4 TOTAL 581,012 56,800 34,153 5.3 Comparison of results with other classifiers As already mentioned, we present our results in two ways depending on their source. For a larger number of classifiers we used figures from the bibliography. The idea in this case is to cover results for a large spectrum of classifiers, which sometimes are difficult if not impossible to obtain and experiment. This method might not be entirely correct from a statistics viewpoint. In fact, we do not control the testing conditions under which these results were obtained, such as possible differences in hardware, the sample selection method, the percentages of data records used for training and testing, the treatment to missing values as well as differences in evaluation methods under which results are presented. For this reason, we present a second set of results obtained after carrying experiments in our own hardware 14 , using the well-known benchmark “WEKA” [Witten et al., 2000]. 5.3.1 Results using figures from the bibliography We present next tables with results for classification tools taken from various sources in the bibliography, namely [Murthy, 1994], [Murthy, 1996], [Domingos, 1996], 14 A PC with a 32-bit architecture, nominal speed of 300Mhz, 128 MB of available RAM running under Windows 98. 5 Evaluation and Results 96 Table 5.14 German Credit dataset. Error Rate in predictive models Method Error Rate (%) Reference CBA 28.5 Liu, 2000 C4.5 tree 28.4 Liu, 2000 MsCBA+Boosted C4.5 24.8 Liu, 2000 RIPPER 27.8 Liu, 2000 LB 24.7 Liu, 2000 NB 25.9 Li, 2000 SORES 32.9 Duntsch, 1998 Naive Bayes 25.3 Friedman, 1996 Trie-Class 25.9 ± 1.5 Ours 5.3.2 Results from experiments done in our own hardware Results showed in this section were obtained running in our own hardware 15 some selected classifiers using Weka. This is an open-source machine learning workbench implemented in Java developed at the University of Waikato, New Zealand [Witten et al, 2000], which is freely available on the World Wide Web at the following address: (www.cs.waikato.ac.nz/ml/weka). The Weka experiment environment is a comprehensive tool for machine learning and data mining. Mainly directed to classification problems, this software implements old as well as new algorithms using the object-oriented Java programming language, and thus it allows the incorporation of other classification software using its Java class hierarchy. The tool also implements regression, association rules and clustering algorithms. Although is possible to run the environment from the command line, the system includes a GUI that provides the user with more flexibility and easiness of use. Evaluation methods include leave-one-out and cross-validation among others. We present results for three main classifiers. For all cases, we calculate error rate percentages and standard deviation ( s ) against the test set using the 10-fold crossvalidation evaluation method. All classifiers were executed against exactly the same datasets previously selected and converted to WEKA format “arff”. 15 A regular PC, Pentium II at 500Mhz, with 255Mb of main memory. 5 Evaluation and Results 97 The first classifier for which we show results is IBk, a nearest neighbour classifier where we set parameter k = 2, for comparison purposes with our own implementation that extracts also two best close neighbours. Other parameter settings for this and other classifiers are shown in Annex 2. The second one is Weka own improved version of Quinlan’s C4.5 called J4.8 which we used with confidence factor of 0.25 and 2 minimum number of objects. Actually, according with its authors, J4.8 implements a later and slightly improved version of C4.5 [Witten et al., 2000]. The third classifiers used is a version of Naive Bayes that we include because this is one of the classical classifiers whose accuracy figures can be used as a reference. The last classifier used for comparison purposes is SMO, a version of a Support Vector Machine classifier. Because SMO could only handle two-classes datasets, we show only results for datasets where this was the case. 5 Evaluation and Results 98 Table 5.15 Comparison in Classifiers accuracy using Weka against Trie-Class Datasets Percentage error and standard deviation in Classifiers Nº Name #inst,attrib,class Naive Bayes IBk(1) J4.8 SMO Trie-Class Error s Error s Error s Error s Error s 1 Adult 45221, 14, 2 17.4 0.52 20.9 0.4 14.7 0.48 15.0 0.69 10.6 0.51 2 Annealing 998, 38, 6 13.5 3.45 0.8 0.76 1.6 0.94 - - 2.3 0.30 3 Breast cancer W 699, 9, 2 4.0 2.31 4.7 3.63 5.9 3.13 3.0 2.73 1.5 0.20 4 Dermatology 358, 34,6 2.5 1.58 4.5 4.21 4.2 1.99 - - 4.5 1.11 5 Pima Diabetes 768, 8, 2 24.2 3.61 27.9 4.13 25.3 3.0 22.5 4.70 18.5 2.60 6 Forest cover (2) 53889, 12, 9 29.8 0.40 13.3 0.38 19.4 0.33 20.5 0.51 7 Heart Clev. 303, 13, 2 15.5 6.69 23.8 6.62 21.8 7.82 15.6 5.95 10.8 0.22 8 Heart Statlog 270, 13, 2 14.8 7.20 25.6 7.50 25.6 8.81 15.9 7.42 18.8 1.73 9 Hypothyroid 7200, 21, 3 4.8 0.64 8.7 0.79 0.5 0.38 - - 0.7 0.33 10 Iris 150, 4, 3 4.0 4.66 4.8 4.65 4.7 4.50 - - 2.1 0.25 11 Pendigits 10992, 16,10 14.2 1.41 0.6 0.30 3.4 0.69 - - 2.4 0.75 12 Satimage 6435, 36, 6 20.7 1.17 17.7 1.18 15.4 1.36 - - 10.1 1.21 13 German credit 1000, 20, 2 25.1 3.90 27.2 5.77 32.0 4.26 24.0 4.48 25.9 1.94 Note: All error results expressed in percentage of instances in error from the test set. Lower error rates for each dataset are indicated in bold face. (1) For all cases we use the IBk classifier with k =2, resembling our own case.. (2) WEKA did not run on the original full size dataset. 5 Evaluation and Results - 99 - Classification results in Table 5.15 are in general similar to those in the bibliography when comparing error values exhibited by classifiers from both sources and the same datasets. On average, relative percentage differences amount to a mere 4.9%. In addition, classifiers results from both sources show the same relative order of accuracy among themselves when classifying the same dataset. The first of these two aspects can be observed when comparing results obtained for the popular classifier C4.5 16 from these two different sources, as shown in Table 5.16. Table 5.16 Comparing C 4.5 Error Rates from two sources Nº Datasets Origin of error figures Relative Name Weka (ours) Bibliography Difference (%) 1 Adult 14.7 14.5 1.4 2 Annealing 1.6 1.4 12.5 3 Breast cancer W 5.9 4.7 20.3 4 Dermatology 4.2 3.9 7.1 5 Pima Diabetes 25.3 25.4 -0.4 6 Forest cover 19.4 29.2 -50.5 (1) 7 Heart -Cleveland 21.8 21.5 1.4 8 Heart Statlog 25.6 21.8 14.8 9 Hypothyroid 0.5 0.4 20.0 10 Iris 4.7 3.7 21.3 11 Pendigits 3.4 3.4 0.0 12 Satimage 15.4 14.8 3.9 13 German credit 32 28.4 11.3 Mean relative percentage difference 4.9 (1) This result was obtained training and testing only on 10% of the original file size. As explained before, we could not manage to put Weka to run against its full version. A third aspect, although secondary is the fact that in all cases but three classifier results from the bibliography are better than results from their counterparts running under Weka. This is normal because we did run C4.5 from Weka using the default options provided and did not tune up its parameter values, as is usually the case with results presented in the bibliography. Consequently, in this particular case, we believe that it is legitimate to extend the comparison from our own experiments to those of the bibliography for completeness 16 The commercial implementation receives the name of C5.0 5 Evaluation and Results 100 since it does not alter significantly the relationship in terms of accuracy between ours and other classifiers. We present next in Table 5.17 execution times for the very same cases indicated in table 5.16. This represents a straight and simple measure of algorithm complexity taken to build and to execute these classifiers. Table 5.17 Classifiers execution total time for each individual fold using Weka. Classifiers Build + execution time in wall clock seconds Dataset Name SMO IBk J4.8 Naive Bayes Trie-Class Adult 20602 6304 65.3 167 309 Annealing 3.8 3.92 0.82 45 Breast cancer W 0.35 3.91 0.1 0.04 0.5 Dermatology 0.65 0.19 0.07 0.3 Pima Diabetes 0.77 0.48 0.18 0.02 2 Forest covert 8220 817 50 5220 Heart Cleveland 0.82 0.18 0.07 0.01 0.5 Heart Statlog 0.68 0.18 0.09 0.03 0.5 Hypothyroid 613.8 5.8 0.24 260 Iris 0.1 0.11 0.06 0.5 Pendigits 325 10.21 1.42 45 Satimage 15.9 1.59 0.11 8 German credit 7.49 2.77 3.1 0.044 5 Execution time in Trie-Class is largely better than in traditional Nearest Neighbour algorithms, one of the objectives in creating this tool. Although we observe larger execution time figures compared with J4.8 in nine out of thirteen datasets these times are under 10 seconds. 5.4 Performance Conclusions Our results shows that on average Trie-Class performs as good as several of the leading classifiers reported here, whether this comparison is done against classifiers running in our test bench or whether we compare with those results from the bibliography. In particular this is true with respect to the landmark classifier C4.5 [Quinlan, 1986] and the instance-based learning k-NN algorithm [Aha, 1991]. Table 5.18 Error Rate comparison between Trie-Class, k-NN and two versions of C4.5 Classification error rates (%) 5 Evaluation and Results 101 Nº Dataset k-NN C 4.5 Bibliography J4.8 Weka Trie- Class 1 Adult 20.9 14.5 14.7 10.6 2 Annealing 0.8 1.4 1.6 2.3 3 Breast cancer W 4.7 4.7 5.9 1.5 4 Dermatology 4.5 3.9 4.2 4.5 5 Pima Diabetes 27.9 25.4 25.3 18.5 6 Forest cover 13.3 29.2 19.4 20.5 7 Heart -Cleveland 23.8 21.5 21.8 10.8 8 Heart Statlog 25.6 21.8 25.6 18.8 9 Hypothyroid 8.7 0.4 0.5 0.7 10 Iris 4.8 3.7 4.7 2.1 11 Pendigits 0.6 3.4 3.4 2.4 12 Satimage 17.7 14.8 15.4 10.1 13 German credit 27.2 28.4 32 25.9 Note: we show in bold type smaller error rates. These differences can be clearly seen when isolating the comparison in classification error rates between Trie-Class and these two other classifiers. As Table 5.18 shows, in eight out of thirteen cases (61.5%) Trie-Class was superior to IBk, C4.5 and J4.8 (Weka’s k-NN version), independently of the source for these figures. We believe that modified instance-based methods such as the one proposed in this thesis represent a powerful challenge to other classification methods. The key issues are solving the complexity of the search problem of similar instances by means of appropriate data structures as a first approximation to object similarity, and a dataset dependent set of criteria to inspect selected close patterns. Compared with other k-NN methods for instance, ours resolves successfully an important weakness of these methods represented by the search complexity problem and the determination of the value of k as stated in a recent work [Riquelme, 2001]. In the extreme case for these methods the distance calculation for all instances in the search space becomes intractable. About the execution time issue, it seems to exist a generalized view that execution time should be very small in all cases, for a classification algorithm to be considered useful. In our opinion, it is always desirable to have the goal of reducing algorithm complexity and thus execution time. Nevertheless, this goal finally depends on the data 5 Evaluation and Results 102 owner defined as the maximum allowed time he/she consider reasonable. A doctor waiting for a Data Mining program to forecast a patient possibility of a serious disease, does not have the same time requirements as a biologist trying to classify some type of diatomaceous. Moreover, one cannot forget that in many cases in real-life situations data preparation and pre-processing takes sometimes hours if not days even before the Data Mining algorithm can start execution. Within this context, to be concerned with few more or less seconds in execution time does not look reasonable, especially if the gain in execution time is done at the expenses of losing accuracy. Because this, we cannot more agree with the statement that: “Ideally, accuracy should not suffer at the expense of improved performance.” [Brighton et al, 2002]. 103 6 Choosing the best close neighbour Most NN classification algorithms use only the distance between objects as the sole criterion to select the best neighbour object. In the case of the family of k-NN algorithms, after k closest neighbours are selected, a voting on the majority class of selected close objects is used, with a neighbour vote decreasing with its distance from the test example [Bentley, 1980; Friedman et al., 1977; Dasarathy, 1991]. Algorithms for discrete and real-value functions have been developed as in [Mitchell, 1997] with refinements including the case where the query point exactly match one or more training objects. Also, many other algorithms have been developed to increase the search efficiency of k-NN in the sense of choosing a group of objects that best represent the class of the unknown object, as we refer in Section 2. However, most of the time the recurrent criterion for choosing among subset k of pre-selected training members is the dominant class. In Trie-Class we use a mixed method in two phases to select the best hypothesis. As a first phase, we extract two nearest cells from the tree structure holding training records using the search mechanism described in Section 3.7. We call these cells p1 and p2 and each one of them is associated to a different class. The second phase consist in the selection of one of them to assign its class to the unknown cell px. On this phase, cells p1 and p2 and the query object itself are inspected in order to make a final decision. This is what we explain next. Trie-Class uses six weighted decision parameters (DP) that characterize the selected cells to make its final selection. DP’s are weighted before run time according with their predictive skills on a particular dataset. Hence, adapting themselves to the characteristics of the dataset where the classification will be done. After weighted they are applied to contending cell patterns p1 and p2 to decide which one of them best represents the new object. By carrying this second inspection on similar cells including the unknown cell px we somehow try to overcome a known problem. The similarity criterion must be applied to a pre-defined set of features and the definition of this set is affected by the previous knowledge one has over the objects [Murphy et al., 1985]. Inspecting the unknown object px itself can bring into light new knowledge. 6 Choosing the best close neighbour 104 On what premises DP weights are attributed? They depend on how well a given DP classifies new objects. As shown later, we demonstrate that this ability changes from one dataset to the next. For this reason, DP weights are set every time a new dataset is under analysis. DP weights are individually calculated by testing to how many new unseen records a particular DP applies, and how well it classifies them. These two criteria correspond to ambit and precision respectively. Weights are computed learning from the training file and testing against an evaluation file. Weight calculation is explained in subsection 6.3. Once weighted, how DP’s are used to select p1 or p2? To each cell is applied a merit () function, which correspond to the joint application of allowable combinations of weighted DP’s. Several functions are used to fulfil the task of this function to which we refer next. As DP criteria are first weighted we use function apply() to determine a given criterion’s applicability or ambit which contributes to its weight. In this function a given DP is applied to both cells p1 and p2. We say that a particular DP “applies” to a given object when it produces a better result applied to one of these cells. Function apply() returns a Boolean value and is shown in Fig 6.1. One weighted, the primary usage of each individual criterion is to help selecting a cell and consequently its class for a new query cell px. In this context we develop a basic function criterion() that applies a given criterion to cell patterns p1 and p2 and returns a real value, which correspond to a measure of “goodness” of that criterion. Different criteria return different values as shown later in Table 6.1. This in turn allows the direct comparison between criteria applied to the same DP which is done by function apply() from Definition 28 which allows to determine to which cell the criterion applies best. As the weight of each criterion is already calculated, a final result corresponds to the sum of al applicable criteria multiplied by its pre-determined weight. This is carried by the merit() function applied separately to each cell pattern p1 and p2. A pattern with larger merit means larger similarity between a given cell pattern and query cell px. Based on each cell’s merit, a final comparison through function predict() returns the wining cell and class. 6 Choosing the best close neighbour 105 We begin this section by giving the characteristics of each DP criterion, its weight calculation and meaning, along with figures showing its discriminating power on various datasets. Next we explain each of the functions referred above putting it all together in the final predict() function. 6.1 Decision parameters We now explain the meaning and characteristics of each decision parameter. Its weight calculation as well as the class returned when applied as criterion. 6.1.1 Semi-exclusive values We have already defined the exclusiveness of a cell in Equation (3.23) of Section 3.4. This measure of exclusiveness tries to determine if the attribute values of a record belong to semi-exclusive intervals or not. The presence of attributes qualifying as semiexclusives within the unknown object px can only mean that there is a strong evidence that this cell is likely to be related to the class dominating those same intervals. The fact that this DP check first within the unknown cell px itself looking for one or more semi-exclusive intervals make it different from all others. When this is the case and function semp(px, K) applies, function criterion verifies if the actual class held by cell p (p1 or p2) correspond to the class found in px intervals. If so, the function returns the fraction of those intervals. Notice that this criterion is not applicable directly to cell patterns p1 and p2 as the information conveyed by the eventual presence of semi-exclusive intervals on these patterns, gives no reason to prefer one of them as the best representative for px. 6.1.2 Distance between selected cells Distance calculation used for the cell extraction of p1 and p2 is different from the one used here. In the first case distance was computed using the search mechanism already explained in Section 3.7. In the present case we use a standard distance calculation to find out the smallest distance between px and cells p1 and p2. Its computation is normalized using as divisor 6 Choosing the best close neighbour 112 cover dataset and the column for decision parameter semi-exclusive. Within the subset of those cells where this criterion applies, it correctly classified 88.1% of them. This table confirms that DP’s are data dependent, a fact shown by the variations observed in parameters ambit and precision. DP semi-exclusive shows on average the best precision with 93.9%. This is not surprise, as exclusiveness present in cell px is a strong assumption about the true hypothesis of the class. At the same time, it shows a reduced ambit or sphere of action. The next two parameters that follow very close are parameters frequency and shapes. It is rather surprising the performance of shapes, being such a simple similarity function. On average it applied to 84.7% of records with an average precision of 90.4%. Table 6.2 Ambit and Precision values for decision parameters in various datasets Datasets Degree of ambit and precision for each DP in percentage Name Set type Nº recs. Semi- Excl Shapes Distance Frequency Strength Majority forest Training 28457 Ambit 25.7 99.9 99.9 43.7 29.9 48.7 (7 classes) Evaluation 5691 Precision 88.1 86.0 82.0 81.0 74.5 72.2 pendigits Training 7495 Ambit 0.01 94.2 100 80.8 50.2 10.4 (10 classes) Evaluation 1499 Precision 100.0 98.8 98.4 98.5 98.3 97.7 landsat Training 3219 Ambit 41.2 68.6 88.0 57.3 49.6 37.8 (7 classes) Evaluation 644 Precision 95.2 87.4 76.7 89.1 85.0 62.8 adult Training 22612 Ambit 6.6 76.0 92.0 57.9 60.5 78.8 (2 classes) Evaluation 4522 Precision 98.6 87.1 83.4 92.5 89.6 86.1 Cancer-W Training 343 Ambit 34.8 99.6 87.4 89.3 86.1 67.0 (2 classes) Evaluation 69 Precision 93.7 100 97.7 98.7 97.8 96.0 Hypothyroid Training 1332 Ambit 5.5 99.9 100 99.7 31.6 92.1 (6 classes) Evaluation 266 Precision 96.2 99.4 99.3 99.7 99.7 99.3 Heart (Statlog) Training 135 Ambit 42.7 100 100 19.1 12.0 55.1 (2 classes) Evaluation 27 Precision 81.5 81.1 77.5 77.7 77.6 84.3 dermatology Training 180 Ambit 36.5 39.7 100 51.6 58.4 30.6 (6 classes) Evaluation 36 Precision 97.7 83.7 81.1 87.3 94 89.6 Average Ambit 24.1 84.7 95.9 62.4 47.3 52.6 Average Precision 93.9 90.4 87.0 90.6 89.6 86.0 Altogether, this makes it a very important component among decision parameters. On the other hand, distance remains the most solid criterion of all when we use both its ambit and precision for comparison purposes. 6 Choosing the best close neighbour 113 The table also shows that majority class is at the bottom of the classification, hence indicating the usefulness of developing other decision parameters, as a mean of improving classification accuracy. Adapting decision parameters to a given task is the confirmation that there is no classification algorithm performing well in all cases. [Mitchell, 1980; Brodley, 1995]. In [Shaffer, 1994] it is proposed for instance to try different induction paradigms, each one in turn, and to use cross-validation to choose the one that appears to perform best. Other approaches combine empirical with analytical evidence as in [Pazzani et al., 1992; Michalski et al., 1993]. Still others use multi-strategy learning by combining multiple methods in one algorithm [Domingos, 1996]. What combinations of ambit and precision values for a DP represent a better criterion in a given dataset? We use a heuristic that in general gives more weight to DP’s exhibiting large values for both ambit and precision. The contribution of these two factors is not equal though, as more weight is given to parameter ambit over precision. The reason for this being simply the fact that if the extent of a criterion is insignificant or very small, the value of factor precision, whatever it might be, is immaterial. On the contrary, a significant ambit of a criterion then a precision figure might be interesting if relatively high for classification purposes. Function B(DP) measures the weight of a given decision parameter, which is calculated using the following heuristic: B(DP) = ((((2ap) / (3a)) +1) / (((3a) / (2p)) + 1)) + 3p + 2a (6.7) Variables a and p stand for ambit and precision calculated according with Equations (6.5) and (6.6) respectively. Function B(DP) ranks over every other percentage combination of ambit and precision favouring ambit as observed by the value assigned to the coefficients. In general, when variables a and p increases, B increase also. The intuition here is simple. Assign more weight to those DP that extent over a large number of cases and at the same time have better classification skills. And within this general evaluation criterion, favours slightly more the value of ambit. A very high precision only applicable to a bunch of cases is not as good as a somewhat lower classification 6 Choosing the best close neighbour 114 value, but covering a larger fraction of records. In any case, as the discovery process seems, as a rule, to require human judgement [Langley, 1998], these figures can lead to modifications in the way weights are calculated. In Fig. 6.3 below we show the variations in the values of function B(DP) depending on various combinations of ambit and precision. 0 100 200 300 400 500 600 (ambit, precision) alpha Fig. 6.3 Variation in weight B for various combinations of ambit and precision In Appendix 3 you can find the table of values originating the graph of Fig. 6.3. Ranking decision parameters is done, calculating the value of function B(DP) from Equation (6.7) for each criterion and setting them in decreasing order. In Table 6.3 we show the result of applying Equation (6.7) to ambit and precision values from Table 6.2. Table 6.3 Decision parameters weights for different datasets Weight values by DP and dataset dataset Name Exclusive Shapes Distance Frequency Strength Majority Forest cover 256 501 494 301 243 301 Pendigits 200 505 524 459 356 227 Landsat 320 397 443 362 328 247 Adult 217 197 469 370 374 429 Cancer-W 358 354 363 368 359 351 6 Choosing the best close neighbour 115 Hypothyroid 209 526 526 525 298 499 Heart (Statlog) 299 493 486 215 192 345 Dermatology 310 293 493 339 375 275 Average weight 271.1 408.3 474.8 367.4 315.6 334.3 Fraction of total avg. values 12.5% 18.8% 21.9% 16.9% 14.5% 15.4% The last line in Table 6.3 corresponds to the fraction that each weight represents overall in the merit function for the considered datasets. This can be interpreted as the average influence of each decision parameter when applied into the merit function. Although parameter Distance continues to be the more important (21.9%), the participation of each other parameter is very homogeneous, perhaps with the exception of Semi-exclusives. In general, this denotes a combined effort to help choosing the best representative cell pattern when all these aspects are together considered. 6.4 Predicting the final output class Decision parameters are weighted just once for a dataset. The classification process starts next. Trie-Class is presented with a new test file to classify. Each new record is discretized using the same algorithms used to create the training file stored in a tree, and converted into cell px which becomes the first input to the function. Two near candidates cell patterns p1 and p2 are extracted from the training dataset using the algorithm described in Section 3.7 using function neighbours(). They also are input to the function. Next, function criterion() is applied to both cell patterns p1 and p2 using the six available decision parameters. Once each criterion is calculated, we proceed to measure the merit of each considered cell p. This is done using function merit(). Definition 31. We assume the existence of function merit() which measures how similar a given cell pattern is with respect to some unknown object px. ( ) ( ) 6 1 ( ) , , x i i i merit p criterion DP p p DP α = = ⋅ ∑ (6.8) 6 Choosing the best close neighbour 116 This function returns the aggregate value resulting from the application of function criterion() to all six decision parameters pondered by its corresponding weight. Resulting values produced by the criterion() function are normalized as their return values should be equally considered. This requires normalizing the distance, shape and strength criteria. In the case of both distance criteria, its intervals ranges from zero to the maximum distance observed between p1, p2 and px, so it is: [0 max(d(px,p))]. Therefore, on each case distance figures will be divided by the maximum value observed. The same is done with criterion strength, but this time applied to strength values. Function merit() returns a real value. In the case when all DP criteria values except one are set to zero, function merit can be used to measure the goodness of a single criterion for a particular cell pattern. Function merit() represent a similarity measure among cell patterns within a given data space, allowing their comparison with respect to another cell pattern (px in our case). In this sense we can say that it could be used as a new metric with its own similarity measure for classification problems. Therefore, and although not implemented in the present thesis, the use of this function could substitute completely the initial similarity measure used to extract cells p1 and p2. Probably this would be done at the expense of a larger algorithmic complexity and a different data structure given the number of parameters used. Once we know the merit value for each contending cell, the application of a final function predict() gets the winner class to be attributed to px. label predict(p1,p2) {if (merit(p1) > merit(p2) return label(p1) else if (merit(p2) > merit(p1) return label(p2) else return lmaj(); } 6 Choosing the best close neighbour 117 Fig 6.4 Function that predicts the label class for a new query px. Trie-Class always assign a class to each new object under scrutiny. The majority class is attributed in the default case, on the condition that one of the two cell patterns p1 or p2 actually exhibit this class (which in the case of datasets with more than two classes might not be true). If it is not, the pattern holding the criterion with the largest weight value will be chosen instead. 6 Choosing the best close neighbour 118 119 7 Implementation 7.1 General overview The drawing in Fig.7.1 shows the general idea on how Trie-Class algorithm is implemented. There are three main steps in the construction of our classifier: preprocessing data, building the required structures and running the classifier. Fig 7.1 Trie-Class main modules As every other algorithm learning by induction, Trie-Class begins by preparing the training and test datasets. The training file will be used for “learning” and evaluating the functioning of the algorithm. The test set is used once to finally classify unseen records. Sample stratification, explained in Section 4 is used to obtain these subsets. Original dataset Training dataset Dictionary Test dataset support data Trie- Class Stratify working files Tree build Parameter tuning Evaluation set Classifier Results 7 Implementation 120 All attribute records within these files are discretized. This discretization is done using interval values specified on the dictionary file for each attribute. In practice, in many cases of domains with small number of values, the discretization process does not alter the original values of an attribute and hence no domain compression takes place. For instance consider the famous Cancer dataset, which consist of 10 attributes, all with identical numeric domain values ranging from 0 to 10. If decided by the user, indicating an interval of 1 for each domain in the dictionary file would produce this effect. Trie-Class can handle missing values in categorical attributes if they form part of the allowable values of an attribute. Watching at the diagram it can be observed that the storage of records is not “lazy” , a characteristic of many instance-based methods. Trie-Class uses a trie as tree structure to hold cell information, which will be used as patterns at classification time. This tree structure does not hold training data on its original format. C-trie keeps count on cell frequencies within each attribute interval. These frequencies are used by the frequency DP criterion as explained earlier in Section 6. Besides this tree, a second file is created, which contains supporting information needed by the algorithm. Basically it contains information on semi-exclusive intervals, as defined in Equation (3.22) by function semk(), as well as information on joint probability values for each symbolic attribute, needed for the distance calculations of symbolic attributes as stated in Definition 26 and Equation (4.2). As for the first type of information the file contains orderly lists of attributes. For each of them the file stores those intervals where the semi-exclusive property holds. As it was explained in Definition 19 in Section 3.4, the value of parameter φ is user-defined. These two files appear labelled in Fig. 7.1 as “Trie” and “ supporting data” respectively. A dictionary permanently loaded into main memory during tree construction and classification completes the information for Trie-Class to work. It includes attribute information: data type, interval size, maximum and minimum values and a class flag. (For a complete layout of the dictionary see Annexe I). In order to assign weights to decision parameters, Trie-Class divides the training set itself into training and evaluation sets with approximately 80 and 20% of records respectively. Decision parameters are tested against this last subset in order to decide 7 Implementation 121 the weight to assign to each decision parameter. This last sub-process is iterative as depend on prediction error results, as suggested by the arrow pointing to itself in the parameter tuning process of Fig. 7.1. Once decision parameters have their weights the classification algorithm is ready to run against test data. In the rest of this chapter, we explain tree growing, its characteristics, related work and the search process. Finally, we argue that our search algorithm using best sub-cells to obtain p1 when compared with regular k-NN methods as the sole decision criterion increases classification accuracy and decrease execution time. 7.2 Building a trie as the main tree structure A fundamental and very well studied technique for storing and retrieving data is to use m-ary trees, also known as digital trees, lexicographic trees or simply tries, which is its most widespread name and the one we use in this thesis. Tries were first proposed in [de la Briandais, 1959] although the term trie, taken from information retrieval has been given by [Fredkin, 1960]. Tries are used to store multimedia images, web pages, string matching, remote sensing imagery, genetic sequences, etc using all kind of trie variations: Patricia trees [Morrison, 1968], Twotries [Aoe, 1996], Triangulation tries [Bergman, 1994], R-trees [Guttman, 1984], Quadtrees [Samet, 1984], Burst Tries [Heinz, LC-tries [Nilsson, 1999], among several others. Along the paths of the tree these structures do not store data at the nodes, which is usually the case in regular trees. In a trie a set of strings from an alphabet containing m symbols is stored in a natural way in an m-ary tree where each string corresponds to a unique path. Branching at the jth level is determined by the value of the jth element from the key. There are two types of nodes in a trie: branch nodes containing only pointers to a number of children and leaf or element nodes, containing the string or key. Leaves have no children. The root of the trie contains disjoint index values representing the first letter or element of the string. At index position i, the pointer to the next letter points to the sub-tree of all words starting with that letter. A pointer to the jth character of a key is located at the jth level of the trie. All words containing a common prefix are located in the same path represented by the various node levels. Trie structures represent incomplete trees. Its leaves are not at the same level as shown in Figure 7.2. 7 Implementation 128 small subsets of close neighbours each belonging to one class would participate in the final selection process using decision parameters. In these trees, equal binning discretization method would have no importance whatsoever in terms of information loss. It remains to see the time complexity of such forest structure. Mixing strategies for tries is not new as a mean to balance its fast searching capabilities with a large space usage [Knuth, 1997]. In both cases though, searching for identical or similar cells would increase search time costs by introducing sequential search mechanisms in these “big” nodes or linked lists. Compression techniques seem to be consistent with the fact that the most relevant attributes are indeed first located into the tree and these common prefixes are indeed strong representatives of the correct mapping between cells and classes. The search process described in Section 3.7 is constant and independent of the size of the training file, a very important factor. This search process could be also considered as searching in an ordered file as a matrix of i rows and j columns, with the search done on columns represented by the ordered array of nodes, as is the case with some algorithms such as [Micó, 1996]. The search is done starting from the ith column corresponding to a given element value in a circular way increasing the radius each time by one unit, looking each time to the next elements [i+1] and [i –1] discarding all others as soon as an existing cell value is found. For this reason algorithm’s complexity is constant and equal to 2(log n) on the average case. Search time is always constant in Trie-Class, unless used the “look ahead” mechanism. Search complexity is logarithmic, if we use total nodes visited as a measure of complexity, as done in other cases [Yanilos, 1993]. Keeping the count of frequencies at sub-cell level allows us to have a graphical distribution of cell density. This not only helps in breaking ties when selecting neighbour elements within a given node, as it could be used to extend the use of this structure for clustering as well [Anderberg, 1973]. Search time is fast in C-trie. Taking advantage of array indexing, for any given index value j we look for existing cell values to the “left” starting at j, j-1,..0, and to the right starting at j+1 within interval [1..i]. Once cell(s) found within the node, we eliminate from the search the rest of the tree, concentrating in the following sub-tree. This is equivalent to take into account the triangle inequality [Burkhard, 1973] to significantly 7 Implementation 129 reduce the number of direct distance calculations needed for an efficient search algorithm as in [Berman, 1999]. The search phase is done in O(ni) time complexity. Trie-Class can learn, due to the fact that is persistent. New training cells can be easily added. Record deletion is more complicated but is not considered as a functional part of the algorithm. Changing the training file is interpreted as growing again a new tree. It should not be neglected the fact that C-trie was designed to hold a sample from the database, whose only requirement is to be representative of the data in the statistical sense. This means that most of the time we are dealing with a manageable number of records. Although the actual structure for prototyping is done using dynamically sized arrays for every node, linked lists could also be used to save array size in sparse distributions. As it is well known, this structure unless indexed, has a drawback of a sequential search. Alternatively, hashing tables containing internal node indexes could also be used, but constructing them requires also extra time. 7.5 Dictionary and other supporting files Like many other data mining applications, ours also use a user-provided dictionary file. Basically it contains information on all attributes, the type of data, i.e. numeric discrete, continuous or symbolic, the minimum and maximum possible values they can take (their domain), the size of the interval to be used as a domain partition in the tree structure and a flag indicating whether this is the class field or not. An example of the dictionary can be found in the Appendix I. It is worth saying at this point that with an extra single read of the training sample most of this information could be automatically detected. The only requirement to be supplied by the user would be the size of the interval for each attribute. This information is crucial for tree construction, and allows the user adjust algorithm efficiency by altering the interval for whichever attribute. This user interface with the software is very important for all classification algorithms in data mining, where to a large degree they play a key role in the success of the end result. There is nothing compared with this knowledge, if such knowledge exists, and cannot be overlooked with the obsession of automation. 7 Implementation 130 Along with C-trie and dictionary files Trie-Class uses a couple more of files containing information devoted to two different purposes. One of them is to keep information on semi-exclusive intervals as defined in Equation (3.22), which is basically an ordered table keeping for each attribute and partition interval, values which relate to one class only. These are sometimes called “pure attributes” [Breiman, 1984] or “primary ” [Turney, 1996] in the literature. These attributes are informative of the class when considered by themselves [Kohavi, 1997]. Optionally, the user can decide to have this file information somehow softened: the information contains interval values for those attributes where one of the classes holds a user-defined threshold percentage of the number of training cells. Whichever the degree of exclusiveness is selected, this file is used at generalization time when cell values are checked for the presence of one or more of these values. A second file, also on disk is used to keep information on symbolic attributes frequencies. For each symbolic attribute the file keeps one record for each class containing the frequency of each value. These are used in the distance calculation for these types of attributes, specifically in the calculation of the joint probability P(vc) already explained in Section 4.2. These two files appear under the name “support data” in the diagram of Fig. 7.1. 131 8 Conclusions and Future work In this dissertation, we explored specific paradigms for data classification, namely, decision trees and instance-based methods in an effort to develop an experimental algorithm able to improve some of its aspects while simplifying algorithmic complexity. The order of the conclusions presented here is arbitrary with respect to its importance degree. Rather, we have followed the sequential order in which these topics appear on this work. There are literally dozens of algorithms to solve classification problems in the literature. Our approach was in general to keep it as simple as possible, considering the truthfulness of the well-known paradigm of the Minimum Description Length principle. Within this context we did retain two of the more popular methods, instance-based and decision trees as inspiration to develop our own. From the first one we took the main idea of not using a central model developed to classify all records – as done for instance in decision trees - but to use training records themselves as patterns to locally represent on each case the best model to assign its class to some unknown query. From the second of these methods, we have taken the idea of using a tree to store actual records as a means of rapidly searching records in the data hyperspace. This is as far as it goes the similarity between our algorithm and decision trees because in this kind of paradigm tree nodes are used as threshold decision values that together represent a general model used to classify in the same manner all test records. In our case, the use of a trie serves only the purpose of an index with very fast access, but not as a generator of a classification model. In fact our algorithm in this respect has a totally opposed behaviour to decision trees and it is similar to the nearest neighbour method. Trie-Class use a simple algorithm overall, formed by small contributions along the various phases of the Data Mining process. • The development of the concept of sub-cells, as a method for early class identification as well as pattern characterization for model selection (Section 3.3). • A sub-optimal search method for the extraction of near neighbours, different from the traditional distance calculation, which gives elimination power to more relevant attributes (Section 3.7). 8 Conclusions and Future work 132 • A simple mechanism to differentiate relevant and non-relevant attributes using a one-dimension projection of attribute values and semi-exclusive intervals (Section 4.3). • The use of joint probabilities to solve the distance calculation problem in the presence of symbolic attributes (Section 4.2). • The use of Decision Parameters in the final pattern selection process uses concepts such as cell strength, semi-exclusivity and shapes (Section 6.1). These parameters enrich the information about objects. By having a weight according with training data characteristics (Section 6.3), they adapt the algorithm to the data under inspection. 8.1 Conclusions Our experimental results from Section 5 show that on average Trie-CLASS performs at least as good as several of the leading classifiers reported, whether this comparison is done against classifiers running in our test bench or whether we compare with results found in the bibliography 18 . In particular this is true with respect to the landmark classifier C4.5 [Quinlan, 1986] and the instance-based learning k-NN algorithm [Aha, 1991]. In eleven out of thirteen files compared against C4.5, ours was better. It also appears clear from these figures that Trie-Class performs equally well with various types of data, numeric or symbolic as well as average dataset sizes and dimensions. Our figures also show that Trie-Class has poorer results when the number of classes is greater than two, perhaps due to the fact that the actual algorithm is only implemented to extract two cell patterns representing two different classes. A clear improvement over regular NN methods is the search mechanism used to extract selected records using a greedy strategy. Trie-Class extracts near objects using the concept of similarity in turn assimilated to a distance calculation. Its searching method restricts the search area within the trie according with previous values found at sub-cell levels, thus avoiding the visit to all unnecessary tree branches. The extraction of additional cells restricts even further the search space, as its class must be different 18 As new results on classifiers performance appear every day in the literature, some of our figures could be out of date. 8 Conclusions and Future work 133 from the class of the previous cells extracted. Overall, reduced areas of the data space are searched to obtain close neighbours. Greedy search strategies are in general sub-optimal, as they can loss better solutions. The counter part to this been that some complex algorithmic problems can find some acceptable solution. Our results, mixing a greedy search with look-ahead for ties situations prove to be encouraging. In fact, Trie-Class obtain better results than IBk, a Weka implementation of a k-NN algorithm, when the value of k = 1. Feature subset selection is the process of identifying and removing as much irrelevant and redundant information as possible. Searching the feature space within reasonable time is necessary, especially for the case o data with large number of features. For this reason reducing data dimensionality is dealt using a heuristic search strategy as opposed to an exhaustive search of the feature space prohibitive most of the time. They are more feasible and can give good results, although they do not guarantee finding the optimal subset. Regularities on data are found in Trie-Class using every other feature one at a time, independently from others using a previously discretized single-dimension space. Using this criterion attributes can be ordered by degree of relevance, allowing the removal of irrelevant values without diminishing severely classification accuracy. Feature selection is done before tree growth. Most relevant attributes produce the initial data space divisions and thus most similar objects remains close, a problem affecting several classification algorithms. This fact also influences distance calculation, because more elimination power is given to more relevant attributes largely reducing the search space. We have already said that Trie-Class extracts two near cells as a first approximation to classify new objects. In a next step it uses a “voting” mechanism to make a final decision that is different from all other k-NN algorithms we know of. This selection is done through the use of decision parameters, which allow the extraction of further information from pre-selected cell patterns. This represents richer knowledge about these competing neighbours, a procedure that goes beyond the standard mechanism of using distance as the sole criterion. Moreover, decision parameters are weighted according with its ability to classify new records, dynamically adapting the whole algorithm to the changing characteristics of data. This adaptation of the algorithm constitutes an important step towards fighting the known fact that not all classification 8 Conclusions and Future work 134 algorithms performs equally well with different datasets. We have no knowledge of these technique been used before. Distance calculation for symbolic attributes constitutes a problem of its own, dealt in different ways by different authors. Trie-Class uses a heterogeneous mechanism depending on the type of value (discrete, continuous or symbolic). In the specific case of symbolic attributes it uses a simple mechanism of low complexity based on the joint probability distribution of classes within attributes and its corresponding values, resembling somehow the functioning of Bayesian Networks at a given node. This mechanism works better than the simple overlap solution and is cheaper in complexity than more sophisticated methods. The choice of using a multi-way tree indexed on attribute values works as a very fast index and we believe it is a good solution for the type of search carried on. It has been demonstrated that this structure allows a very fast search and presents a low computational complexity for the required type of proximity search [Bentley, 1997] as well as in the case of large multimedia databases. Contrary to standard tries, useful information represented by records class membership is not found at tree leaves but at each tree level, i.e. associated with sub-cells, allowing the drawing of a very useful class map in the data space. Moreover, difficult choices of threshold values as in the case of decision trees are avoided. In this structure search time is independent of the file size and exhibit low algorithmic complexity, a problem found in many search methods as our results show with respect to execution time. The gain we obtain with a fast search has the cost of sometimes using a larger disk space, as our data structure is disk resident. As disk space has sky rocketed in terms of capacity, and at the same time with systematic decreasing prices and increasing access speeds in the last decade, our choice seems to be adequate. In any case, the eventual use of pruning at the level of sub-cells or prefixes belonging to a single class can diminish easily tree size, not to mention the fact that Trie-Class requires only a representative sample not the entire population in order to classify and thus the size of the required structure is always under control. The algorithm implemented by Trie-Class can be alternatively implemented using any database management system. This could simply 8 Conclusions and Future work 135 handle all required data and carry the search mechanism using some of the existing database techniques. 8.2 Future work Trie-Class extracts two near neighbours in order to select the class of one of them as the class to assign to a new query object. In this respect, as a proposal for further work, an obvious way of decreasing tree size and perhaps improve classification accuracy in datasets with more than two classes, would be the use of a forest with as many trees as classes exist in a given dataset. Each one of these trees would hold records belonging to one class only. At search time the actual search algorithm would be used to extract one or two cell patterns per tree, each one of them associated with a single class. Trie-Class tree structure called C-trie allows the identification of classes at the subcell level. Manipulating this map of classes would allow a graphical representation of clusters of classes and its frequencies. Clustering techniques could be easily implement with Trie-Class, an aspect in Data Mining that was out of the scope of this work. As clusters represent objects with common characteristics, all six decision parameters are a good solution to identify these common objects, especially applied at sub-cell levels. The application of these criteria would extend the use of distance as the sole similarity criterion used in many clustering algorithms, allowing a richer similarity concept and thus allowing the selection of clusters with a strong internal strength. In this sense, Trie-Class can become a bivalent tool, allowing the implementation of classification as well as clustering techniques. One of the decision parameters used to select the best representative pattern is shapes, a vector of values representing inter-attribute relationships, which are used to identify pattern similarity. Considering the encouraging results of this decision parameter in classification, it would be worth investigating further the possibility of creating a whole new metric space using this shape criterion. Finally, another aspect not implemented in this thesis is the fact that we use decision parameters and the merit() function as a mean of selecting the most representative cell pattern. We could well substitute the original search mechanism to extract near neighbours all together and replace it by the value provided by this function. Thus, it would be used to define a new similarity metric. This might represent a richer similarity 8 Conclusions and Future work 136 concept if compared with the use of distance as the only similarity criterion between objects. 137 9 Bibliography Agarwal, P., Erickson, J., 1999. Geometric range searching and its relatives, Advances in Discrete and Computational Geometry, Contemporary Mathematics 223, American Mathematical Society Press, pp. 1-56. Agrawal, R., Imielinski, T., Swami, A., 1993. Mining Association Rules between Sets of Items in Large Databases, Proceedings of the ACM International Conference on Management of Data, pp. 207-216. Aha, D. W., Kibler, D., Albert, K., 1991. Instance-Based Learning Algorithms, Journal of Machine Learning, Vol. 6, pp.37-66 Aha, D. W., 1992, Tolerating noisy, irrelevant and novel attributes in instance-based learning algorithms, International Journal of Man-Machine Studies, Vol. 36, pp 267-287. Aha, D. W, Bankert, R., 1994. Feature Selection for Case-Based Classification of Cloud Types: An Empirical Comparison, In D.W. Aha (Ed.) Case-Based Reasoning: Workshop (Technical Report WS-94-01, CA, AAI Press. Aha, D. W., Bankert, R., 1995. A comparative evaluation of sequential feature selection algorithms, Proc. of the Fifth Intl. Workshop on Artificial Intelligence and Statistics, pp., 1-7. Alber, I. E., Xiong, Z., Yeager, N. , Farber, M., Pottenger, 2001, W. M. Fast Retrieval of Multi-hand Hyperspectral Images Using Relevance Feedback. Proceedings of the International Geoscience and Remote Sensing Symposium, Vol 3, pp 1149- 1151. Anderberg, M.R., 1973. Cluster Analysis for Applications. Academic Press, N.Y., USA. Andersson, A, Nilsson, S., 1993, Improved behaviour of tries by adaptive branching. Information Processing Letters, Vol. 46, pp. 295-300 Andersson, A, Nilsson, S., 1994, Faster Searching in Tries and Quad trees – An Analysis of Level Compression, in Proceedings of the Second European Symposium on Algorithms, pp. 82-93.