Discretization of Continuous Features by Using a Kernel

Discretization of Continuous Features by Using aKernel L. Gonz´alez1,F.Velasco 1,F.J.Cuberos 2,J.A.Ortega 3and C. Angulo4 1COSDE Research Group, Dept. Applied Economics I, University of Seville (Spain) {luisgon, velasco}@us.es 2Dept. Planificaci´on-Radio Televisi´on de Andaluc´ıa, Seville (Spain) [email protected] 3Dept. Computer Science, University of Seville (Spain) [email protected] 4GREC Research Group, Technical University of Catalonia, Vilanova i Geltr´u. (Spain) [email protected] Keywords: Qualitative knowledge, Time series, TV-viewing share 1 Motivation The interoperability between the different systemsofancompany constitutes a fundamental aspect to foment the competitiveness. This competitiveness is maximumin the telecommunication sector, because in this case it must take into account not only the competence between companies but also the involved interests of the holdings which manage them. The increasing regulations of the European Commission which implies the entry of the new competitive television operators have hugely increased the necessity in this sector of offering quality services to the users and auspicious economic results to its management committee. It is necessary to define new techniques for intra-systems interoperability of any company and specifically, in the TV sector. Several works may be found in [6]. In this paper, we introduce a new tool to improve the decision support systemsofancompany. It helps us to compare timeseriesinanefficient way and with a low computational cost. These techniques are applied to improve the interoperability of two intra-systems of a TV enterprise. They are the programming and merchandising systems. 130 L. Gonz´alez,F.Velasco,F.J.Cuberos,J.A.OrtegaandC.Angulo On the other hand, automated processing and knowledge extraction from data is an important task performed by machine learning algorithms. Hence, the generation of classification rules fromclass-labelled examples is possible. Instances can be described by a set of numerical, nominal, or continuous features. Several of these algorithms are expressly designed to handle numerical or nominal data; other algorithmsperformbetter with discrete-values features, despite the fact that they can also handle continuous features [13]. Meanwhile a certain number of algorithms developed in the machine learning community focus on learning fromnominal feature spaces. Real-world classification includes patterns with continuous features where such algorithmscannotbe applied, unless the continuous features are firstly discretized. Discretization is the process of transforming a continuous attribute into a finite number of intervals associated with a discrete, numerical value –a number, symbol or letter. This is the usual approach for learning tasks that use mixed-mode – continuous and discretedata. The Discretization process is developed in two stages: given the range of values for the continuous attribute, first the number of discrete intervals is found; then, the width or boundaries for the intervals. In [14] it was shown than even on purely numerical-valued data, results for text classification on the derived text-like representation outperformsthemore naive numbers-as-tokens representation and, more importantly, is competitive with mature numerical classification methods such as C4.5[15], Ripper[2] and SVM[1, 3, 8, 17]. The most straightforward way is to treat each number that afeaturemay take on as a distinct “word”, and proceed with the use of a text classification method using the combination of true words and tokens-fornumbers words. However, this makes the numbers1and2asdissimilar as the numbers 1 and 100 –all three values are unrelated tokens to the classification methods. An approach to applying text-classification methods problemswith numerical-valued features would be desirable so that the distance between such numerical values can be discerned by the classification method. Most of the methods translating a continuous feature into symbols –letters– in order to deal with texts –letters chains– lose part of their efficient since they are not designed for this task. The kernel proposed in this paper is specifically designed to work with letters chains coming froma discretization process of a continuous feature and it highlights the properties of these features. To cope the effectiveness of this kernel, it will be used on words froma dictionary where a distance exists between letters of the alphabet. The kernel was firstly proposed to compare among time series that had been converted into symbol chains –words– [4, 5]. Thus, the similarity measure between words quantified a distance between original timeseries. The rest of this paper is structured as follows: first, both a kernel and a distance between finite intervals are defined. Distance is used to define a real function measuring the similarity between two words and if words have the same length, this function is a Kernel because it fulfills the Mercer con- Discretization of Continuous Features by Using a Kernel 131 dition. Next, one example about classification rules is developed. Finally, the conclusions and ideas for future works are enumerated. 2Intervaldistancefromakernel In essence, the goal in the construction of kernel functions is to guarantee the existence of an application φ, defined fromthe working set, Xto a vectorial space endowed with a dot product, F.Fromthis function φthe kernel function is defined, denoted k(·,·), over pairs of elements of the working set as the dot product of their transformations into the feature space, k(·,·)=φ(·),φ(·)F, where ·,· is denoted a dot product. The kernel function let us k(·,·) establish similarities between the original elements fromtheir transformed ones, so a distance between the points in the input space can be defined. It must be considered, when elaborating a similarity and distance measure, that the φ application must be able to highlight the essential characteristics of the initial set of elements[7]. Following the ideas presented in [11], let I=(c−r, c +r)⊂R:c∈R,r∈R+ be the family of all the open intervals contained in the real line of finite dimension (in default, we are working with open intervals, but it is posible to translate the study to closed intervals naturally). A function φ1:I→R2 is defined as: φ1(I)=P(c, r)tand the kernel kand a distance d2 1between intervals are: k(I1,I 2)=c1r1Sc2 r2d2 1(I1,I 2)=Δc Δr SΔc Δr  where I1=(c1−r1,c 1+r1), I2=(c2−r2,c 2+r2), Δc =c2−c1and Δr =r2−r1,andPmust be a non singular matrix (S=PtP). Thus, the discretization of a continuous feature in symbols representing different intervals, allows us to use as a distance between symbols the distances defined between intervals as it will be showed. 3Kernel Fromthis point, we always consider that the symbols are letters (A,B,···) because the ordinal scale is reflected in the alphabetical order. Let A= {A1,A 2,··· ,A ℓ}be an alphabet of ℓletters and let Pbe a set of the words obtained fromthis alphabet. Let P1=P11P12···P1nand P2= P21P22···P2mbe words fromPwhere P1i,P2j∈Aand n≥m.Amap Kλis defined as follow: 132 L. Gonz´alez,F.Velasco,F.J.Cuberos,J.A.OrtegaandC.Angulo Kλ(P1,P2) = max m  i=1 λd2(P1i+k,P 2i),k=0,··· ,n−m where 0 <λ<1andd(·,·) is a distance between letters. Property 1. For all P1,P2∈Pand 0 <λ 1<λ 2<1, then: Kλ1(P1,P2) ≤ Kλ2(P1,P2). Property 2. For all P1,P2∈Pand 0 <λ<1, then: Kλ(P1,P2) ≤m.This upper bound is attained: If P2=P11P12···P1m,andKλ(P1,P2) = m. Property 3. Let r=maxij d(Ai,A j), with Ai,A j∈A. For all P1,P2∈P and 0 <λ<1 then: mλr2≤Kλ(P1,P2). This lower bound is attained: Let A=Aiand B=Ajbe such that d(A, B)=r2.IfP1=AA ···Aand P2= BB ···Bwith size of P1, n,andsizeofP2, m,thenKλ(P1,P2) = mλr2. Thereby, for all 0 <λ<1: mλ r2≤Kλ(P1,P2) ≤m, ∀P1,P2∈P Property 4. Let Abe an alphabet obtained froma discretization process of a continuous feature and P={P1P2···Pn,P i∈A}the set of all the words having length n, then: Kλ(P1,P2) = n  i=1 λd2(P1i,P 2i) is a Kernel. The proof of these properties are in [9]. 3.1 Generalized similarity Let P1andP2 be two words of the samelengthnfromthe set P.Inthe definition of similarity between words, Kλ(P1,P2) = n i=1 λd2(P1i,P 2i),all the letters have the same interest. It is possible to generalize this similarity by weighting each letter in such a formthat the sumof the weights is equal to n. Let w1,w 2,··· ,w n∈Rbe scalar numbers accomplishing wi≥0and n i=1 wi=n. The generalized similarity can be defined in two different ways: K1 λ(P1,P2) = n  i=1 λwi·d2(P1i,P 2i)K2 λ(P1,P2) = n  i=1 wi·λd2(P1i,P 2i) It is no difficult to prove that both are kernels (the sumand the product of kernels is a kernel [3]); however the second one has a more intuitive meaning for the weights. Also, using the properties of the exponential function we have: Discretization of Continuous Features by Using a Kernel 133 K1 λ(P1,P2) = n  i=1 λwi·d2(P1i,P 2i)= n  i=1 w′ i·λd2(P1i,P 2i) where w′ i=λ(wi−1) d2(P1i,P 2i). Although it is no necessarily true that n i=1 w′ i= n. For this we propose as a generalization of similarity the function K2 λ(·,·). 4Implementation In the current television, the programming is implemented taking into account the response of the audience according to the inversion carried out. This is known as ”share”. The interoperability between the programming and exploitation systems is a fundamental aspect in these enterprises. Therefore, it is necessary to dispose of good tools which allow to identify the response of the audience according to the executed programming. The comparison must be done with the responses obtained by the channel in the previous weeks in order to prove if the expected results have been achieved. Besides, the achieved results must be compared with those obtained by the competitive channels. These decision support systems have been designed taking into account that they may be defined by means of a mathematical base. The proposed techniques and methods verify this requirement. The techniques allow to optimize the exploitation of the information systems, by providing comparison mechanisms between the different channels. In particular, this comparison has been made between opened broadcasting channels in Andalucia (Spain). An example of the classification rule is developed. Data to be considered is a set of television shares fromthe seven main television stations in Andalusia, Spain. It has been provided by Canal Sur Televisi´on and it has been collected from[18]. Time series represent the average share for 15 minutes blocks, so the daily series are 96 elements length. We are going to use several discretization methods and will see that the results are good in all them. A variety of discretization methods can be found in the literature. Fromthe unsupervised algorithms: equal interval width, equal frequency interval, k-means clustering or unsupervised MCC; to supervised algorithms like ChiMerge,CADD,1RD,D-2 or maximumentropy. An extensive list can be found in [13]. The methods to be evaluated in this work are: i) Equal Width Intervals or EWI, ii) Equal Frequency Intervals or EFI, iii) CAIM (Class-Attribute Interdependence Maximization) [13], iv) Ameva [12], v) CUM [10], and vi) DTW [16]. In the following step several related task are accomplished: i) The discretization methods are applied over the learning subset producing a set of landmarks, ii) The landmarks are used as the limits of intervals and a symbol is assigned to each one, and iii) the series are translated into symbol chains. The series are labelled with the name of the corresponding television station. We have selected the first 32 Wednesdays of year 2003 (32 ·7 = 224 134 L. Gonz´alez,F.Velasco,F.J.Cuberos,J.A.OrtegaandC.Angulo series) as the input set of series. Other 20 Wednesdays are used as work set (140 series) to be predicted. In the Equal Width, Equal Frequency and CUM methods, the user must specify the number of intervals to be computed. As no rule for an optimal value exist, all those methods will be calculated from2to9intervals.Allthe methods are applied to the learning subset and a list of interval boundaries are obtained. Individual letters are assigned in alphabetical order to each interval. The learning systemevaluates (a complete study can be found in [5]) the number of successful identifications on the test subset using the k-neighbours algorithmfor each discretization method. The application of the presented methodology achieves a 95% correct identification rate for the work set series, 133 over 140. The best discretization method for this data set was Equal Frequency Interval with 3 labels. Table 1 shows the average percentage and variance for all the methods in 200 draws for 1, 3 and 5 neighbours. In Table 1 can be observed that, although the discretizaci´on methods build the intervals following different approaches, except for someanomalous case, the results are similar, that is, the kernel is very robust in front of the discretization methods. With respect to the parameter λused in the kernel, it does not significantly affect to the average of correct identification. Table 2 shows that only the CAIM method is affected by the variance of λ. 5 Conclusions and further work Anewsimilarity function for symbol chains has been proposed, generating in some cases a kernel. This function measures similarities between words in a dictionary when a distance measure between symbols is defined. In the near future, we will focus on the extension of this methodology to time series with multiple attributes and other kinds of data. At the sametime, we will use new data sets to extend its validation. Finally, it must be mentioned that this kernel has certain implications in the type of considered similarity that will be studied in future researches. The small influence of the λparameter in identification tasks must also be argued. 6Acknowledgements This work was partially supported by the the Junta de Andaluc´ıa grants PAI- (2004-2005/SEJ-442). Moreover, it has been partly supported by the Spanish Interministerial Committee of Science and Technology by means of the programs TIN2004-07246-C03-03 and DPI2003-07146-C02-01. Discretization of Continuous Features by Using a Kernel 135 Table 1. Identification Average (%) and Standard Deviation in Test Subset (200 Draws) vs. Number of neighbours Neighbours 135 Method Labels Avg. StDev. Avg. StDev. Avg. StDev. CAIM 7 90.5 4.26 89.4 4.56 89.1 4.74 AMEVA 3 91.6 2.74 89.4 2.77 89.7 2.81 2 90.7 2.86 88.4 2.91 89.0 2.98 3 85.9 4.04 85.1 4.20 86.1 3.88 4 75.9 6.01 71.3 5.29 70.9 5.59 5 73.2 5.41 71.0 5.42 72.3 5.52 CUM 6 82.4 4.21 80.8 4.03 80.8 4.95 7 83.2 3.56 80.0 3.69 80.0 4.28 8 85.2 3.33 82.8 2.95 82.1 3.36 9 86.4 3.15 84.9 2.60 84.6 3.13 2 91.1 2.88 90.9 2.65 90.7 2.87 395.5 2.13 95.4 1.98 95.1 2.02 4 88.8 3.07 87.6 3.15 87.4 3.40 5 85.2 3.87 85.1 4.14 85.4 3.85 EFI 6 80.2 4.11 77.6 4.71 76.4 4.90 7 74.6 4.78 71.7 5.31 71.0 5.37 8 75.7 4.32 71.2 4.91 70.6 5.01 9 74.7 5.26 70.4 5.27 69.1 6.20 2 71.0 11.5 65.2 13.2 66.5 12.9 3 46.0 8.08 36.3 8.26 35.0 8.90 4 71.9 11.9 67.3 14.2 68.8 14.3 5 74.9 10.7 71.0 13.0 71.9 11.9 EWI 6 72.3 10.9 68.3 13.7 70.3 13.6 7 85.8 7.76 84.7 8.22 85.9 8.28 8 75.3 9.32 73.3 10.3 74.2 11.0 9 88.1 4.90 87.4 5.76 88.0 5.27 DTW - 80,2 3,74 78,0 4,44 76,4 4,27 Table 2. Percentage of correct identifications in the Work Set for each method vs. value of λ. Lambda 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 CAIM 0.88 0.88 0.88 0.86 0.86 0.84 0.84 0.82 0.80 AMEVA 0.88 0.88 0.88 0.88 0.88 0.88 0.88 0.88 0.87 CUM02 0.88 0.88 0.88 0.88 0.88 0.88 0.86 0.86 0.88 EFI03 0.91 0.91 0.91 0.92 0.92 0.92 0.92 0.92 0.90 EWI09 0.85 0.85 0.85 0.85 0.84 0.84 0.85 0.87 0.85 136 L. Gonz´alez,F.Velasco,F.J.Cuberos,J.A.OrtegaandC.Angulo 7 References [1]. C. Angulo and L. Gonz´alez. 1-v-1 Tri-Class SV Machine. In Proc. 11th European Symposium on Artificial Neural Networks, ESANN, pages 355–360, 2003. [2]. W. Cohen. Fast effective rule induction. In Proceedings of the Twelfth International Conference on Machine Learning, pages 115–123, 1995. [3]. N. Cristianini and J. Shawe-Taylor. An introduction to Support Vector Machines and other kernel-based learning methods.Cambridge University press 2000, 2000. [4]. F.J. Cuberos, J.A. Ortega, F. Velasco, and L. Gonz´alez. Qsi - Alternative Labelling and Noise Sensitivity. In 17 International Workshop on Qualitative Reasoning.,volume 17, pages 229–239, 2003. http://www.unb.br/ib/necbio/QR03/pdfs/QR03posterCuberos.pdf. [5]. F.J. Cuberos, J.A. Ortega, F. Velasco, and L. Gonz´alez. A methodology for qualitative learning in timeseries. In18 International Workshop on Qualitative Reasoning.,volume 2, pages 147–153, 2004. http://www.qrg.cs.northwestern.edu/QR04/papers/FJC QR044.pdf. [6]. Konstantas D., Bourri`eres J.-P., L´eonard M., and Boudjlida N. Interoperability of Enterprise Software and Applications. Springer, 2006. [7]. L. Gonz´alez, , F. Velasco, and R. M. Gasca. A study of the similarities between topics. Computational Statistics, 20(3):465–479, 2005. [8]. L. Gonz´alez, C. Angulo, F. Velasco, and M. Vilchez. M´aquina ℓ-SVCR con salidas probabil´ısticas. Inteligencia Artificial. Revista Iberoamericana de IA, (17):72–82, 2002. In Spanish. [9]. L. Gonz´alez, F.J. Cuberos, F. Velasco, and J.A. Ortega. Un n´ucleo entre literales. Tech. Report 02, Dept. of Applied Economy I, University of Seville (Spain), 2003. [10]. L. Gonz´alez and J.M. Gavil´an. Una metodolog´ıa para la construcci´on de histogramas. Aplicaci´on a los ingresos de los hogares andaluces. XIV Reuni´on ASEPELT-Spain, 2001. [11]. L. Gonz´alez, F. Velasco, C. Angulo, J.A. Ortega, and F. Ruiz. Sobre n´ucleos, distancias y similitudes entre intervalos. Inteligencia Artificial. Revista Iberoamericana de IA, (23):111–117, june 2004. In Spanish. [12]. L. Gonz´alez, F. Velasco, F.J. Cuberos, and J.A. Ortega. Ameva: A discretization algorithm.Machine Learning, in Revision:–, 2006. [13]. L. Kurgan and K.J. Cios. Caimdiscretization algorithm.IEEE Transactions on Knowledge and Data Engineering, 16(2):145–153, 2004. [14]. A.A. Macskassy, H. Hirsh, A. Banerjee, and A. Dayanik. Converting numerical calssification into text classification. Artificial Inteligence, (143):51–77, 2003. [15]. J.R. Quinlan. C 4.5 Programs for Machine Learning. Morgan Kaufmann, 1993. [16]. H. Sakoe and S. Chiba. Dynamic-programming algorithmoptimization for spoken word recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1):43–49, 1978. [17]. B. Sch¨olkopf and A. J. Smola. Learning with Kernel. MIT Press, 2002. [18]. TNS Audiencia de Medios. A service of Sofres AM company. www.sofresam.com, year 2003.