Supervised Learning Using Instance-based Patterns

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/228937485 Supervised Instance-based Learning Using Patterns in a Trie like Structure Article CITATION 1 READS 283 2 authors: Some of the authors of this publication are also working on these related projects: GEOZOCO View project Fairness View project Patricio Serendero Universidade do Algarve 4 PUBLICATIONS18 CITATIONS SEE PROFILE Miguel Toro Universidad de Sevilla 210 PUBLICATIONS1,642 CITATIONS SEE PROFILE All content following this page was uploaded by Miguel Toro on 29 May 2014. The user has requested enhancement of the downloaded file. Supervised Learning Using Instance-based Patterns Patricio Serendero1, Miguel Toro2 [email protected], [email protected] 1Faculty of Sciences and Technology, U. of Algarve, Faro, Portugal 2Dept. of Languages and Information Systems, U. of Seville, Seville, Spain Abstract: This paper introduces a new classification algorithm of the instance-based learning type. Training records are converted into patterns associated with a known class label, and stored permanently into a trie1-like tree structure along with other helpful information. Classifying new records is done selecting from the trie two best patterns as solutions hypotheses. Best pattern selection is done using standard distance metrics, a strength function and an exclusive values concept. Classification tests done on several data files have shown very accurate results. Keywords: supervised learning, instance-based, pattern strength, exclusive values, trie. 1 Introduction Supervised learning techniques, known also as classification, belong to the areas of Machine Learning and Knowledge Data Discovery. In general, their goal is to build up algorithms able to predict class labels in data files or whole databases. Training records of known class labels are used in the creation of the algorithm. Later, these are used to predict unknown classes previously unseen records. A plethora of methods and tools exists for this purpose. Among them: classification tree induction [23], [16], Bayesian classification methods [5], [9], neural networks [26], genetic algorithms [13], [17], and others2. Motivation for this work is around the following topics: a) To treat data in such a way as to make them independent from attribute types. 1 Pronounced “try”, taken from the middle part of word “retrieve” [12] 2 See also a comparison of Data Mining Tools in [10]. Patricio Serendero, Miguel Toro CAEPIA 2001 b) Have not one general hypothesis model but many hypotheses functions for records to be classified. c) To use data structures that soften somehow problems of attribute selection and threshold value typical of binary decision trees. [32]. 2 Problem Definition Let us consider the closed universe formed by a data file R composed of a finite set of m records r. R = {r1, r2,..,rm } (1) We consider set R as formed by a training subset RT and a test subset RX, such that R = RT ∪ RX. The first one will be used to learn data patterns and to help developing the classification algorithm. RX is used for testing and algorithm verification. In a given record r, we find a finite sequential set of attributes S. S = {A1, A2, Ai… An }, a nonempty set. (2) Every attribute Ai ∈ S can take vi values belonging to a set Ti, where Ti is the domain value. Every record can be associated with class labels l1, l2, etc. belonging to a set L.3 L = {l1, l2, lk} (3) Each record r is formed by the Cartesian product of attribute values A|V and a label l, such that: r = { v1, v2, ..., vn, l } vi ∈ Ti, l ∈ L. (4) From these definitions, we can define the following basic functions: vali(r) = vi, the value associated to attribute i from record r label(r) = l, the label associate with record r. (5) 3 Pattern Definition Data attributes can have different data types: qualitative or non-numerical (symbolic, linguistic); quantitative or numerical (continuous, discrete). We would like to treat them equally, in order to create patterns where all attribute values are represented by integers. For non-numerical or categorical data, we do an arbitrary enumeration, if not already ordered by the domain expert. In addition, we apply discretization to all continuousvalued record’s attributes. Discretization is the process of transforming the domain of a continuous attribute or feature into a finite number of intervals. For all Ai, user-defined intervals with lower and upper value-limits are established in Ti. Thus, for each attribute Ai corresponds a partition of the domain Ti. Intervals are represented by integers with 3 In this article we use indistinctively the words class label, class or just label. Supervised Learning Using Instance-based Patterns CAEPIA 2001 values from 1 to si. Thus, we convert every attribute Ai into a pattern value. Function ord() does this conversion: pi = ordi (vi), v i∈ Ti, pi ∈ 1,.. si . (6) This function returns pi, an integer value representing one interval value for attribute Ai. We can define a pattern p as the sequence formed by n values. p = <p1, p2,.., pi,..,pn> pi = {1..si} (7) To each record r = <v1,v2,..,,vn, l> corresponds a pattern obtained by applying function ordi(). Hence, for every record r we obtain the corresponding pattern p associated with a given label as follows: pat(r) = p = < p1, p2,..,pn> = 〈ord1(v1), ord2(v2),..,ordn(vn)〉 (8) For every pattern p we can define n sub-patterns qi, which are the prefix portion of a pattern. qi = <p1, p2,.., pi >, qi subsequence of p, i = {1..i}. (9) Function freq(p) returns the number of records in RT with pattern p. freq(p) = { r ∈ RT pat(r) = p } (10) In addition from above we can define λi = freq(qi), the frequency of sub-patterns qi. (11) Labels are attached to patterns. Function labels(p) returns the set of labels associate to the subset of records with pattern p. labels(p) = { l ∈ L  ∃ r ∈ RT • label(r) = l ∧ pat(r) = p } (12) From this, we define function nlabels(p) =  labels(p) , nlabels(p) = {1..L } We can extend this concept to sub-patterns. Hence, (nlq)i = nlabels(qi) (12a) In any dataset RT we find that generally function nlabels (pn) = 1, meaning that a given full pattern p ∈ RT is associated with one label, making data consistent. As for sub-patterns, we often find that nlqi > 1, meaning that more than one label shares the same qi. This is the overlapped area of patterns. In general this is the case for initial values of i; As the value of i approaches n, factor nlqi tend to be associated with one label and nlabels (p) = 1. From an intuitively viewpoint each pattern p represent a hypercube in a space of n dimensions. Function freq (p) measures the number of records from RT in that hypercube. Function labels (p) represents the set of labels present in that hypercube. Patricio Serendero, Miguel Toro CAEPIA 2001 4 Other Definitions 4.1 Distance Between Patterns Several supervised learning methods use a metric distance to compare attribute values. [7]. We calculate the minimum distance between two patterns applying the minimum square method: 1 2' 1 /)||()',(λ i n iippppd −= ∑ = (13) The overall frequency of pattern p represented by λ1, is used to add weight to the measure of distance. 4.2 The strength of a Pattern We differentiate between strong and weak patterns according to the number of single class labels associated to each one of its n sub-patterns. If (nlq) i = 1, sub-pattern qi is strong. The contrary means a weak sub-pattern. We define function strongp(p) as a measure of pattern strength as follows: strongp(p) = {i : 1..n. nlabels(qi) = 1 } | (14) Function strongp() varies from 0 to n and represents the total number of sub-patterns qi of p associated with just one label. When strongp (p) = n, the pattern strength is maximum. If (nlabels (qi) > 1 then (nlq) i = 0, a weak sub-pattern. An important property of sub-patterns is that once the ith sub-pattern becomes associated with one label, then all subsequent pi+1, pi+2, pi+n sub-patterns also relate to the same label. When i = n, class overlapping should disappear; we expect that the label attached to the nth element is the label attached to pattern p as a whole. This is our basic assumption: no two identical full patterns are related to different classes. If such case exists probably due to noise data, we consider the pattern as completely weak. We could not make any prediction about its label. This same criterion has been used before. See [11] and [31]. 4.3 Exclusive Values We define exclusive values as the unique maximum and minimum interval values shown by a given pi ∈ p always associated with the same label in RT. From the point of view of a label, this represents its association with a given pi and some value k for all patterns p in RT. This can be represented with the following functions: sr(i, k) = { r ∈ RT | pat(r) = <p1,..,pi,..,pn> and pi = k } ; sl(i, k) = label((sr(i, k)) and function Supervised Learning Using Instance-based Patterns CAEPIA 2001 nsl(i,k) = sl(i,k) (15) Then, we define exclusive values as: α = ex(p) = Ni : 1..n (nsl(i, pi) = 1)) (16) The number of pi values in pattern p that appear always related to a given class. 4.4 The Majority Class Training set RT includes one or more subsets of records associated with the same class l; that is: RT = Rl1 ∪ Rl2 ∪ Rli ∪ Rlj where Rlj is the set of records with label lj. We define majority class as the class with maximum number of records in RT, calculated as follows: lmaj(RT) = max(R11,Rl2,..,Rlj ) (17) In populations with say, two classes l1 and l2, where class l1 is strongly predominant, we will predict l2, only when strong evidence is found that this is the case [14]. 5 Algorithm The algorithm is executed in two phases. The first corresponds to a pre-processing. It is the learning phase. It consists in reading sequentially all records in RT and applying to each one of them the function in (7) converting them into p patterns and storing them into a trie structure. In this process the label indicator and a frequency λi for each subpattern qi, are stored as well. Hence, for every pattern in RT, the structure holds: p = <(q1, nlq1, λ1), (q2, nlq2, λ2),..,(qn, nlqn, λn)> (18) We define P as the set of patterns in RT with freq () > zero. This is to say, all existing patterns in RT. Each one of them is associated with a known class l. P = {p  freq (p) > 0 } (19) The second phase is the actual classification process. This is the predictive phase. A new test file RX is read in sequentially; for each record r in RX, the algorithm performs the conversion px = pat(r) generating the target pattern px of unknown class label. For each pxi value in px, the algorithm looks in the stored pattern structure for the closest pi values using its distance metric obtaining pattern p+. This is the closest existing pattern in RT with respect to px. We repeat this operation in a slightly different way to obtain a “second” best pattern p-. These two patterns represent our solution hypotheses. One of them will be chosen to predict the class for the unseen pattern px. Patterns p+ and pcan be defined as follows: For any sub-pattern qi, we define the set of k integers next(qi). An integer k is in next(qi) if <qi, k> if is a sub-pattern of P. Given px, then p+ and pare defined recursively: Let q+i, q-i, and qxi, be sub-patterns of p+, pand px respectively. Further, let be Patricio Serendero, Miguel Toro CAEPIA 2001 q+i +1 = <q+i, k+>, q-i +1= <q-i, k-> and qxi +1 = <qx i, kx>. Thus, k+ is the closest integer in next (q+i) to kx and kis the closest integer in next (q-i,) to kx. Pattern p+ is the closest to px in RT and is calculated first. If two identical patterns exist in RT and RX, then px = p+, and labels(px) = labels(p+.) Pattern pis searched next. The selected pattern must be different from p+, but as close as possible to px. If a kvalue different from k+ is not available to add in next sub-pattern <q-i, k->, existing value k+ is used instead. When this is achieved, q-i becomes distinct from q+i,. Subsequent p-i+1 values are calculated as p+ was. Unseen px instances are predicted based on the closest distance from p+ and p- (13), plus three other parameters. The first is the strength of a pattern. From strength function in (14), we define the following two functions: st+ = strongp(p+) and st- = strongp(p-) (20) We consider a pattern strong, if the area were it belongs is clearly more disjunctive than others, with respect to a given class. Secondly, the algorithm sees whether patterns p+ and pshow the presence of exclusive values. Applying the exclusive function ex() from (16) we can obtain parameters α+ and αas follows: α+ = ex(p+) and α- = ex(p-) (21) Factor α represents a degree of confidence in the disjunctive quality of a pattern's set of attribute values. Its value increases from zero by one as more pi values present that feature. The algorithm will favor the pattern showing a larger ex (p) value. If after applying these criteria the algorithm still cannot predict a label for px, then function lmaj() is used. p + p - p x Region of the hyperspace ℜn not covered by set P Exclusive value Figure 1. A new pattern px from RX. Patterns p+ and pare obtained from RT. Pattern px is closer to p+ in the hyperspace. It shows an exclusive value corresponding to the same class as p+. 6 Results We have performed experiments with our algorithm that we call Trie-Class on several datasets, and compared with published results in the literature. Datasets used for testing Supervised Learning Using Instance-based Patterns CAEPIA 2001 comes from public domain in the web, mainly from the UCI[19]. Records with unknown attribute values were removed or converted to its mean value. Using a random function each time on the complete file, the standard ten-fold cross validation procedure has been done for all results. Accuracy values are calculated for the test file. We have used around 60% of records for the training file RT; the remaining 40% for test file RX. Results obtained with other tools were taken from several sources, namely [22], [20], [21], [24], [25] and [3]. Table I. Table I. Statlog Heart disease file. _____________________________________________ Method Accuracy % Reference _____________________________________________ Trie-CLASS 96.2 Ours Naï ve Bayes 83.6 WEKA, RA K* 76.7 WEKA, RA IB1 74.0 WEKA, RA 1R 71.4 WEKA, RA T2 68.1 WEKA, RA MLP+BP 65.6 ToolDiag, RA FOIL 64.0 WEKA, RA RBF 60.0 ToolDiag, RA InductH 58.5 WEKA, RA Table II. Pima Indian Diabetes file. ____________________________________________________________ Method Accuracy % Reference ____________________________________________________________ Trie_CLASS 89.5 Ours LogDisc 77.7 Statlog Incnet 77.6 N.jankowski DIPOL92 77.6 Statlog Linear Discr. Analysis 77.2 -77.5 Statlog, Ster & Dobnikar SMART 76.8 Statlog GTO DT(5xCV) 76.8 Bennet and Blue ASI 76.6 Ster & Dobnikar kNN, k=22, Manhattan 75.5 Karol Grudzinski OC1(10 5-fold CV) 73.4 -75.4 Murthy et al. C4.5 73.0 Statlog . Table III. Heart disease, Cleveland file. ___________________________________________________________________ Method Accuracy % Reference ___________________________________________________________________ Trie_CLASS 98.2 Ours Patricio Serendero, Miguel Toro CAEPIA 2001 Incnet 90.0 N. Jankowski 28-NN,stand Euclidean, 7 features 85.1± WD/KG LDA 84.5 Ster & Dobnikar Fisher discriminant analysis 84.2 Ster & Dobnikar 16-NN, stand, Euclidean 84.0±0.6 NCU 25-NN, stand, Euclidean 83.6 ±0.5 NCU FSM, 82.4-84% on test only 84.0 R. Adamczak Naïve Bayes 82.5-83.4 Rafal, Ster, Dobnikar C4.5(5xCV) 77.8 Bennet and Blue Table IV. Annealing file. (Sterling & Buntine). Attribute intervals used: width= 20, strength = 700, len = 50 and thick = 50. __________________________________________________ Method Accuracy % Reference ________________________________________________ Trie-CLASS 98.6 Ours LB 96.4 Bing Liu CBA 96.4 Bing Liu RIPPER 95.4 Bing Liu C4.5 (AdaBoost Ensemble) 95.1 Quinlan [24] Table V. Satellite image file (STATLOG version) We used only four attributes as suggested: 17, 18,19 and 20. ________________________________________________ Method Accuracy % Time ________________________________________________ Trie_CLASS 91.1 8 k-NN 90.6 944 LVQ 89.5 44 Dipol92 88.9 111 Radial 87.9 74 Alloc80 86.8 28757 IndCart 86.2 9 CART 86.2 14 MLP+BP 86.1 53 Bayesian Tree 85.3 10 C4.5 85.0 1 New ID 85.0 53