Discretization of Continuous Features by Using a Kernel

Disc e iza ion o Con inuous Fea u es by Using aKe nel L. Gonz´alez1,F.Velasco 1,F.J.Cube os 2,J.A.O ega 3and C. Angulo4 1COSDE Resea ch G oup, Dep . Applied Economics I, Uni e si y o Se ille (Spain) {luisgon, elasco}@us.es 2Dep . Planificaci´on-Radio Tele isi´on de Andaluc´ıa, Se ille (Spain) [email p o ec ed] 3Dep . Compu e Science, Uni e si y o Se ille (Spain) [email p o ec ed] 4GREC Resea ch G oup, Technical Uni e si y o Ca alonia, Vilano a i Gel ´u. (Spain) [email p o ec ed] Keywo ds: Quali a i e knowledge, Time se ies, TV- iewing sha e 1 Mo i a ion The in e ope abili y be ween he diffe en sys emso ancompany cons i u es a undamen al aspec o omen he compe i i eness. This compe i i eness is maximumin he elecommunica ion sec o , because in his case i mus ake in o accoun no only he compe ence be ween companies bu also he in ol ed in e es s o he holdings which manage hem. The inc easing egula ions o he Eu opean Commission which implies he en y o he new compe i i e ele- ision ope a o s ha e hugely inc eased he necessi y in his sec o o offe ing quali y se ices o he use s and auspicious economic esul s o i s manage- men commi ee. I is necessa y o define new echniques o in a-sys ems in e ope abili y o any company and specifically, in he TV sec o . Se e al wo ks may be ound in [6]. In his pape , we in oduce a new ool o imp o e he decision suppo sys emso ancompany. I helps us o compa e imese iesinane icien way and wi h a low compu a ional cos . These echniques a e applied o imp o e he in e ope abili y o wo in a-sys ems o a TV en e p ise. They a e he p og amming and me chandising sys ems. 130 L. Gonz´alez,F.Velasco,F.J.Cube os,J.A.O egaandC.Angulo On he o he hand, au oma ed p ocessing and knowledge ex ac ion om da a is an impo an ask pe o med by machine lea ning algo i hms. Hence, he gene a ion o classifica ion ules omclass-labelled examples is possible. Ins ances can be desc ibed by a se o nume ical, nominal, o con inuous ea- u es. Se e al o hese algo i hms a e exp essly designed o handle nume ical o nominal da a; o he algo i hmspe o mbe e wi h disc e e- alues ea u es, despi e he ac ha hey can also handle con inuous ea u es [13]. Meanwhile a ce ain numbe o algo i hms de eloped in he machine lea ning commu- ni y ocus on lea ning omnominal ea u e spaces. Real-wo ld classifica ion includes pa e ns wi h con inuous ea u es whe e such algo i hmscanno be applied, unless he con inuous ea u es a e fi s ly disc e ized. Disc e iza ion is he p ocess o ans o ming a con inuous a ibu e in o a fini e numbe o in e als associa ed wi h a disc e e, nume ical alue –a numbe , symbol o le e . This is he usual app oach o lea ning asks ha use mixed-mode – con inuous and disc e e- da a. The Disc e iza ion p ocess is de eloped in wo s ages: gi en he ange o alues o he con inuous a ibu e, fi s he numbe o disc e e in e als is ound; hen, he wid h o bounda ies o he in e als. In [14] i was shown han e en on pu ely nume ical- alued da a, esul s o ex classifica ion on he de i ed ex -like ep esen a ion ou pe o ms hemo e nai e numbe s-as- okens ep esen a ion and, mo e impo an ly, is compe i i e wi h ma u e nume ical classifica ion me hods such as C4.5[15], Rippe [2] and SVM[1, 3, 8, 17]. The mos s aigh o wa d way is o ea each numbe ha a ea u emay ake on as a dis inc “wo d”, and p oceed wi h he use o a ex classifica ion me hod using he combina ion o ue wo ds and okens- o - numbe s wo ds. Howe e , his makes he numbe s1and2asdissimila as he numbe s 1 and 100 –all h ee alues a e un ela ed okens o he classifica ion me hods. An app oach o applying ex -classifica ion me hods p oblemswi h nume ical- alued ea u es would be desi able so ha he dis ance be ween such nume ical alues can be disce ned by he classifica ion me hod. Mos o he me hods ansla ing a con inuous ea u e in o symbols –le e s– in o de o deal wi h ex s –le e s chains– lose pa o hei e icien since hey a e no designed o his ask. The ke nel p oposed in his pape is specifically designed o wo k wi h le e s chains coming oma disc e iza ion p ocess o a con inuous ea u e and i highligh s he p ope ies o hese ea u es. To cope he effec i eness o his ke nel, i will be used on wo ds oma dic iona y whe e a dis ance exis s be ween le e s o he alphabe . The ke nel was fi s ly p oposed o compa e among ime se ies ha had been con e ed in o symbol chains –wo ds– [4, 5]. Thus, he simila i y measu e be ween wo ds quan ified a dis ance be ween o iginal imese ies. The es o his pape is s uc u ed as ollows: fi s , bo h a ke nel and a dis ance be ween fini e in e als a e defined. Dis ance is used o define a eal unc ion measu ing he simila i y be ween wo wo ds and i wo ds ha e he same leng h, his unc ion is a Ke nel because i ulfills he Me ce con- Disc e iza ion o Con inuous Fea u es by Using a Ke nel 131 di ion. Nex , one example abou classifica ion ules is de eloped. Finally, he conclusions and ideas o u u e wo ks a e enume a ed. 2In e aldis ance omake nel In essence, he goal in he cons uc ion o ke nel unc ions is o gua an ee he exis ence o an applica ion φ, defined om he wo king se , X o a ec o ial space endowed wi h a do p oduc , F.F om his unc ion φ he ke nel unc ion is defined, deno ed k(·,·), o e pai s o elemen s o he wo king se as he do p oduc o hei ans o ma ions in o he ea u e space, k(·,·)=φ(·),φ(·)F, whe e ·,· is deno ed a do p oduc . The ke nel unc ion le us k(·,·) es ablish simila i ies be ween he o iginal elemen s om hei ans o med ones, so a dis ance be ween he poin s in he inpu space can be defined. I mus be conside ed, when elabo a ing a simila i y and dis ance measu e, ha he φ applica ion mus be able o highligh he essen ial cha ac e is ics o he ini ial se o elemen s[7]. Following he ideas p esen ed in [11], le I=(c− , c + )⊂R:c∈R, ∈R+ be he amily o all he open in e als con ained in he eal line o fini e dimension (in de aul , we a e wo king wi h open in e als, bu i is posible o ansla e he s udy o closed in e als na u ally). A unc ion φ1:I→R2 is defined as: φ1(I)=P(c, ) and he ke nel kand a dis ance d2 1be ween in e als a e: k(I1,I 2)=c1 1Sc2 2d2 1(I1,I 2)=Δc Δ SΔc Δ  whe e I1=(c1− 1,c 1+ 1), I2=(c2− 2,c 2+ 2), Δc =c2−c1and Δ = 2− 1,andPmus be a non singula ma ix (S=P P). Thus, he disc e iza ion o a con inuous ea u e in symbols ep esen ing diffe en in e als, allows us o use as a dis ance be ween symbols he dis ances defined be ween in e als as i will be showed. 3Ke nel F om his poin , we always conside ha he symbols a e le e s (A,B,···) because he o dinal scale is eflec ed in he alphabe ical o de . Le A= {A1,A 2,··· ,A ℓ}be an alphabe o ℓle e s and le Pbe a se o he wo ds ob ained om his alphabe . Le P1=P11P12···P1nand P2= P21P22···P2mbe wo ds omPwhe e P1i,P2j∈Aand n≥m.Amap Kλis defined as ollow: 132 L. Gonz´alez,F.Velasco,F.J.Cube os,J.A.O egaandC.Angulo Kλ(P1,P2) = max m  i=1 λd2(P1i+k,P 2i),k=0,··· ,n−m whe e 0 <λ<1andd(·,·) is a dis ance be ween le e s. P ope y 1. Fo all P1,P2∈Pand 0 <λ 1<λ 2<1, hen: Kλ1(P1,P2) ≤ Kλ2(P1,P2). P ope y 2. Fo all P1,P2∈Pand 0 <λ<1, hen: Kλ(P1,P2) ≤m.This uppe bound is a ained: I P2=P11P12···P1m,andKλ(P1,P2) = m. P ope y 3. Le =maxij d(Ai,A j), wi h Ai,A j∈A. Fo all P1,P2∈P and 0 <λ<1 hen: mλ 2≤Kλ(P1,P2). This lowe bound is a ained: Le A=Aiand B=Ajbe such ha d(A, B)= 2.I P1=AA ···Aand P2= BB ···Bwi h size o P1, n,andsizeo P2, m, henKλ(P1,P2) = mλ 2. The eby, o all 0 <λ<1: mλ 2≤Kλ(P1,P2) ≤m, ∀P1,P2∈P P ope y 4. Le Abe an alphabe ob ained oma disc e iza ion p ocess o a con inuous ea u e and P={P1P2···Pn,P i∈A} he se o all he wo ds ha ing leng h n, hen: Kλ(P1,P2) = n  i=1 λd2(P1i,P 2i) is a Ke nel. The p oo o hese p ope ies a e in [9]. 3.1 Gene alized simila i y Le P1andP2 be wo wo ds o he sameleng hn om he se P.In he defini ion o simila i y be ween wo ds, Kλ(P1,P2) = n i=1 λd2(P1i,P 2i),all he le e s ha e he same in e es . I is possible o gene alize his simila i y by weigh ing each le e in such a o m ha he sumo he weigh s is equal o n. Le w1,w 2,··· ,w n∈Rbe scala numbe s accomplishing wi≥0and n i=1 wi=n. The gene alized simila i y can be defined in wo diffe en ways: K1 λ(P1,P2) = n  i=1 λwi·d2(P1i,P 2i)K2 λ(P1,P2) = n  i=1 wi·λd2(P1i,P 2i) I is no di icul o p o e ha bo h a e ke nels ( he sumand he p oduc o ke nels is a ke nel [3]); howe e he second one has a mo e in ui i e meaning o he weigh s. Also, using he p ope ies o he exponen ial unc ion we ha e: Disc e iza ion o Con inuous Fea u es by Using a Ke nel 133 K1 λ(P1,P2) = n  i=1 λwi·d2(P1i,P 2i)= n  i=1 w′ i·λd2(P1i,P 2i) whe e w′ i=λ(wi−1) d2(P1i,P 2i). Al hough i is no necessa ily ue ha n i=1 w′ i= n. Fo his we p opose as a gene aliza ion o simila i y he unc ion K2 λ(·,·). 4Implemen a ion In he cu en ele ision, he p og amming is implemen ed aking in o ac- coun he esponse o he audience acco ding o he in e sion ca ied ou . This is known as ”sha e”. The in e ope abili y be ween he p og amming and exploi a ion sys ems is a undamen al aspec in hese en e p ises. The e o e, i is necessa y o dispose o good ools which allow o iden i y he esponse o he audience acco ding o he execu ed p og amming. The compa ison mus be done wi h he esponses ob ained by he channel in he p e ious weeks in o de o p o e i he expec ed esul s ha e been achie ed. Besides, he achie ed esul s mus be compa ed wi h hose ob ained by he compe i i e channels. These decision suppo sys ems ha e been designed aking in o accoun ha hey may be defined by means o a ma hema ical base. The p oposed ech- niques and me hods e i y his equi emen . The echniques allow o op imize he exploi a ion o he in o ma ion sys ems, by p o iding compa ison mecha- nisms be ween he diffe en channels. In pa icula , his compa ison has been made be ween opened b oadcas ing channels in Andalucia (Spain). An example o he classifica ion ule is de eloped. Da a o be conside ed is a se o ele ision sha es om he se en main ele ision s a ions in Andalusia, Spain. I has been p o ided by Canal Su Tele isi´on and i has been collec ed om[18]. Time se ies ep esen he a e age sha e o 15 minu es blocks, so he daily se ies a e 96 elemen s leng h. We a e going o use se e al disc e iza ion me hods and will see ha he e- sul s a e good in all hem. A a ie y o disc e iza ion me hods can be ound in he li e a u e. F om he unsupe ised algo i hms: equal in e al wid h, equal equency in e al, k-means clus e ing o unsupe ised MCC; o supe ised algo i hms like ChiMe ge,CADD,1RD,D-2 o maximumen opy. An ex en- si e lis can be ound in [13]. The me hods o be e alua ed in his wo k a e: i) Equal Wid h In e als o EWI, ii) Equal F equency In e als o EFI, iii) CAIM (Class-A ibu e In e dependence Maximiza ion) [13], i ) Ame a [12], ) CUM [10], and i) DTW [16]. In he ollowing s ep se e al ela ed ask a e accomplished: i) The dis- c e iza ion me hods a e applied o e he lea ning subse p oducing a se o landma ks, ii) The landma ks a e used as he limi s o in e als and a symbol is assigned o each one, and iii) he se ies a e ansla ed in o symbol chains. The se ies a e labelled wi h he name o he co esponding ele ision s a- ion. We ha e selec ed he fi s 32 Wednesdays o yea 2003 (32 ·7 = 224 134 L. Gonz´alez,F.Velasco,F.J.Cube os,J.A.O egaandC.Angulo se ies) as he inpu se o se ies. O he 20 Wednesdays a e used as wo k se (140 se ies) o be p edic ed. In he Equal Wid h, Equal F equency and CUM me hods, he use mus speci y he numbe o in e als o be compu ed. As no ule o an op imal alue exis , all hose me hods will be calcula ed om2 o9in e als.All he me hods a e applied o he lea ning subse and a lis o in e al bounda ies a e ob ained. Indi idual le e s a e assigned in alphabe ical o de o each in e al. The lea ning sys eme alua es (a comple e s udy can be ound in [5]) he numbe o success ul iden ifica ions on he es subse using he k-neighbou s algo i hm o each disc e iza ion me hod. The applica ion o he p esen ed me hodology achie es a 95% co ec iden ifica ion a e o he wo k se se ies, 133 o e 140. The bes disc e iza ion me hod o his da a se was Equal F equency In e al wi h 3 labels. Table 1 shows he a e age pe cen age and a iance o all he me hods in 200 d aws o 1, 3 and 5 neighbou s. In Table 1 can be obse ed ha , al hough he disc e izaci´on me hods build he in e als ollowing diffe en app oaches, excep o someanomalous case, he esul s a e simila , ha is, he ke nel is e y obus in on o he disc e iza ion me hods. Wi h espec o he pa ame e λused in he ke nel, i does no signi- fican ly affec o he a e age o co ec iden ifica ion. Table 2 shows ha only he CAIM me hod is affec ed by he a iance o λ. 5 Conclusions and u he wo k Anewsimila i y unc ion o symbol chains has been p oposed, gene a ing in some cases a ke nel. This unc ion measu es simila i ies be ween wo ds in a dic iona y when a dis ance measu e be ween symbols is defined. In he nea u u e, we will ocus on he ex ension o his me hodology o ime se ies wi h mul iple a ibu es and o he kinds o da a. A he same ime, we will use new da a se s o ex end i s alida ion. Finally, i mus be men ioned ha his ke nel has ce ain implica ions in he ype o conside ed simila i y ha will be s udied in u u e esea ches. The small influence o he λpa ame e in iden ifica ion asks mus also be a gued. 6Acknowledgemen s This wo k was pa ially suppo ed by he he Jun a de Andaluc´ıa g an s PAI- (2004-2005/SEJ-442). Mo eo e , i has been pa ly suppo ed by he Spanish In e minis e ial Commi ee o Science and Technology by means o he p o- g ams TIN2004-07246-C03-03 and DPI2003-07146-C02-01. Disc e iza ion o Con inuous Fea u es by Using a Ke nel 135 Table 1. Iden ifica ion A e age (%) and S anda d De ia ion in Tes Subse (200 D aws) s. Numbe o neighbou s Neighbou s 135 Me hod Labels A g. S De . A g. S De . A g. S De . 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. Pe cen age o co ec iden ifica ions in he Wo k Se o each me hod s. alue o λ. 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.Cube os,J.A.O egaandC.Angulo 7 Re e ences [1]. C. Angulo and L. Gonz´alez. 1- -1 T i-Class SV Machine. In P oc. 11 h Eu opean Symposium on A ificial Neu al Ne wo ks, ESANN, pages 355–360, 2003. [2]. W. Cohen. Fas e ec i e ule induc ion. In P oceedings o he Twel h In e na- ional Con e ence on Machine Lea ning, pages 115–123, 1995. [3]. N. C is ianini and J. Shawe-Taylo . An in oduc ion o Suppo Vec o Machines and o he ke nel-based lea ning me hods.Camb idge Uni e si y p ess 2000, 2000. [4]. F.J. Cube os, J.A. O ega, F. Velasco, and L. Gonz´alez. Qsi - Al- e na i e Labelling and Noise Sensi i i y. In 17 In e na ional Wo k- shop on Quali a i e Reasoning., olume 17, pages 229–239, 2003. h p://www.unb.b /ib/necbio/QR03/pd s/QR03pos e Cube os.pd . [5]. F.J. Cube os, J.A. O ega, F. Velasco, and L. Gonz´alez. A me hod- ology o quali a i e lea ning in imese ies. In18 In e na ional Wo kshop on Quali a i e Reasoning., olume 2, pages 147–153, 2004. h p://www.q g.cs.no hwes e n.edu/QR04/pape s/FJC QR044.pd . [6]. Kons an as D., Bou i`e es J.-P., L´eona d M., and Boudjlida N. In e ope abili y o En e p ise So wa e and Applica ions. Sp inge , 2006. [7]. L. Gonz´alez, , F. Velasco, and R. M. Gasca. A s udy o he simila i ies be ween opics. Compu a ional S a is ics, 20(3):465–479, 2005. [8]. L. Gonz´alez, C. Angulo, F. Velasco, and M. Vilchez. M´aquina ℓ-SVCR con salidas p obabil´ıs icas. In eligencia A ificial. Re is a Ibe oame icana de IA, (17):72–82, 2002. In Spanish. [9]. L. Gonz´alez, F.J. Cube os, F. Velasco, and J.A. O ega. Un n´ucleo en e li - e ales. Tech. Repo 02, Dep . o Applied Economy I, Uni e si y o Se ille (Spain), 2003. [10]. L. Gonz´alez and J.M. Ga il´an. Una me odolog´ıa pa a la cons ucci´on de his- og amas. Aplicaci´on a los ing esos de los hoga es andaluces. XIV Reuni´on ASEPELT-Spain, 2001. [11]. L. Gonz´alez, F. Velasco, C. Angulo, J.A. O ega, and F. Ruiz. Sob e n´ucleos, dis ancias y simili udes en e in e alos. In eligencia A ificial. Re is a Ibe oame icana de IA, (23):111–117, june 2004. In Spanish. [12]. L. Gonz´alez, F. Velasco, F.J. Cube os, and J.A. O ega. Ame a: A disc e iza- ion algo i hm.Machine Lea ning, in Re ision:–, 2006. [13]. L. Ku gan and K.J. Cios. Caimdisc e iza ion algo i hm.IEEE T ansac ions on Knowledge and Da a Enginee ing, 16(2):145–153, 2004. [14]. A.A. Macskassy, H. Hi sh, A. Bane jee, and A. Dayanik. Con e ing nume ical calssifica ion in o ex classifica ion. A ificial In eligence, (143):51–77, 2003. [15]. J.R. Quinlan. C 4.5 P og ams o Machine Lea ning. Mo gan Kau mann, 1993. [16]. H. Sakoe and S. Chiba. Dynamic-p og amming algo i hmop imiza ion o spoken wo d ecogni ion. IEEE T ansac ions on Acous ics, Speech and Signal P ocessing, 26(1):43–49, 1978. [17]. B. Sch¨olkop and A. J. Smola. Lea ning wi h Ke nel. MIT P ess, 2002. [18]. TNS Audiencia de Medios. A se ice o So es AM company. www.so esam.com, yea 2003.