Connec ing Segmen s o Visual Da a Explo a ion and
In e ac i e Mining o Decision Rules
F ancisco J. Fe e –T oyano
(Compu e Science Dep ., Uni . o Se ille, Spain
[email p o ec ed])
Jes´us S. Aguila –Ruiz
(Compu e Science Dep ., Uni . Pablo de Ola ide, Spain
di escin @upo.es)
Jos´e C. Riquelme
(Compu e Science Dep ., Uni . o Se ille, Spain
[email p o ec ed])
Abs ac : Visualiza ion has become an essen ial suppo h oughou he KDD p o-
cess in o de o ex ac hidden in o ma ion om huge amoun o da a. Visual da a
explo a ion echniques p o ide he use wi h g aphic iews o me apho s ha ep es-
en po en ial pa e ns and da a ela ionships. Howe e , an only image does no always
con ey high–dimensional da a p ope ies success ully. F om such da a se s, isualiza-
ion echniques ha e o deal wi h he cu se o dimensionali y in a c i ical way, as he
numbe o examples may be e y small wi h espec o he numbe o a ibu es. In his
wo k, we desc ibe a isual explo a ion echnique ha au oma ically ex ac s ele an
a ibu es and displays hei anges o in e es in o de o suppo wo da a mining
asks: classifica ion and ea u e selec ion. Th ough diffe en me apho s wi h dynamic
p ope ies, he use can e-explo e meaning ul in e als belonging o he mos ele an
a ibu es, building decision ules and inc easing he model accu acy in e ac i ely.
Key Wo ds: Da a Mining, Visual Da a Explo a ion, Connec ing Segmen s
Ca ego y: E.1, E.2, H.4
1 In oduc ion
Visualiza ion echniques p o ide an impo an suppo o ex ac knowledge
om huge amoun s o da a by inco po a ing ingenui y, analy ic capabili y, and
expe ience o he use , which makes easie o s ee he KDD p ocess. F om isual
me apho s gi ing g aphic ep esen a ions o a que y o da a se , isual da a ex-
plo a ion allows he use o achie e an in e ac i e sea ch and iden i y in e es ing
da a ela ionships, om which new hypo heses and conclusions can be d awn.
Such hypo heses can be la e e ified by lea ning algo i hms. The e o e, isual
da a explo a ion ough o acili a e ge ing an insigh in o da a dis ibu ion by
means o diffe en de ail le el iews in o de o educe he space complexi y and
ob ain simple ha imp o e he in e p e a ion o esul s.
Jou nal o Uni e sal Compu e Science, ol. 11, no. 11 (2005), 1835-1848
submi ed: 1/9/05, accep ed: 1/10/05, appea ed: 28/11/05 © J.UCS
(a) Pa allel Coo dina es om he mos
ele an a ibu es ob ained by VETIS.(b) Connec ing segmen s ob ained by
VETIS.
Figu e 1: Wa e– o m da a se (5000 examples, 40 a ibu es, and 3 class labels).
An impo an issue in mul idimensional da a isual explo a ion is o a oid
diffe en en i ies o e lapping on he sc een. A g aphic en i y usually ep esen s
a da a agg ega ion gi en in he o m o i ems, examples, o ela ionships among
a ibu e alues. The eason o his is ha , i he alues a e di ec ly displayed,
hey usually a e a significan ly small po ion o he en i e a ailable da a. O he -
wise, i is likely ha he esul ing image does no clea ly con ey impo an da a
p ope ies and he explo a ion becomes a difficul ask. In he case o e y–la ge
nume ical da a se s, he numbe o diffe en alues is highe han he sc een es-
olu ion, making some isualiza ion app oaches ha e indi ec ly es ic ed o da a
size, wi h espec ei he he numbe o examples o he numbe o a ibu es.
As an example, Figu e 1(a) shows he Wa e– o m da a se , displayed using he
well–known Pa allel Coo dina es me hod [10]. Because o he high dimensional-
i y o his da a se , indi idual examples canno be clea ly seen om his display,
also p e en ing he de ec ion o ele an pa e ns and a ibu es.
Since i is no easy o p o ide clea in o ma ion abou a ibu e ele ance
unless he me hod can au oma ically ex ac a ele an subse o hem, a mo e
use ul app oach can be o display as ew g aphic en i ies as possible in o de
o ep esen as la ge amoun o da a as possible. The smalle he numbe o
g aphical en i ies con aining highe amoun o in o ma ion, he easie and mo e
meaning ul he in e p e a ion o esul s. Based on his app oach, in his pape
we desc ibe VETIS (Visual Explo a ion Th ough In e ac i e Segmen a ion), a
isual explo a ion echnique ha indi ec ly app oaches wo mining ask: classi-
fica ion and ea u e selec ion. VETIS ex ac s and segmen s he mos ele an
a ibu es, displaying hose in e als meaning ul o he use . F om a complex
da a s uc u e ha p o ides addi ional in o ma ion abou ela ionships among
a ibu es and examples, he g aphical en i ies displayed by VETIS ha e been
named connec ing segmen s.
1836 Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...
A segmen ep esen s he class dis ibu ion o a g oup o examples wi h
consecu i e alues in a dimension. Each segmen can be e-displayed bo h in
Pa allel Coo dina es and as se e al segmen s belonging o new dimensions, gi ing
da a iews in diffe en explo a ion le els. In addi ion, connec ing segmen s can
be aken as logic condi ions o build decision ules om hem in pa allel.
In o de o show he use ulness o ou p oposal, in his pape we include qui e
a ew figu es ob ained om mul idimensional UCI da a se s [5] ha desc ibe by
hemsel es he in e ac i e suppo o he wo abo e men ioned mining ask,
adi ionally achie ed wi h ba ch lea ning algo i hms.
This pape is o ganized as ollows. Sec ion 2 ou lines he s a e o he a
ela ed wi h isual da a explo a ion. In Sec ion 3, we desc ibe ou app oach,
pu ing emphasis on he da a s uc u e ha suppo s he me hod and he al-
go i hm, which is di ided in h ee simple s eps. In e ac i e mining examples wi h
VETIS a e shown in Sec ion 4, whe e g aphical ou pu s a e displayed oge he
wi h eal ed ules in e ac i ely buil . Finally, in Sec ion 5, he mos impo an
conclusions and u u e wo k a e summa ized.
2 Rela ed Wo k
Acco ding o Keim’s axonomy [12], isual explo a ion echniques can be classi-
fied using h ee o hogonal c i e ia:
–The da a ype o be isualized: one–dimensional [15], wo–dimensional [16],
mul idimensional [1, 13], ex & hype ex [15], hie a chies & g aphs [4, 6],
and algo i hms & so wa e [8].
–The da a ep esen a ion: s anda d 2D/3D displays [16], geome ically ans-
o med displays [9, 10], icon–based displays [7], dense pixel displays [13],
s acked displays [11], and hyb id echniques.
–The use in e ac ion way: dynamic p ojec ion [3], in e ac i e fil e ing [16],
zooming [14], dis o ion,andlinking & b ushing.
Wi h espec o he da a ype, VETIS isualizes mul idimensional da a se s wi h
nume ical a ibu es. Rega ding o he second dimension, ou p oposal belongs
o s anda d 2D echniques. Each g aphic en i y in VETIS means a meaning-
ul in e al belonging o a ele an a ibu e. These in e als a e displayed as
mul i–colo ed ba s in which he deg ee o impu i y wi h espec o he class
membe ship can be easily pe cei ed. Acco ding o he hi d ca ego y, VETIS
displays in ol e a dynamic p ojec ion in which he use can apply zooming and
fil e ing o de ec and alida e ele an a ibu es and po en ial pa e ns. Di-
mensionali y educ ion has been deal by diffe en isual app oaches [2]. VETIS
educes he dimensionali y in an in e ac i e manne so as o find meaning ul
subdomains acco ding o use measu es.
1837
Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...
3 Connec ing Segmen s
Wi hin he supe ised lea ning, he p oblem o classifica ion is gene ally defined
as ollows. An inpu fini e da a se To n aining examples is gi en. E e y
aining example is a pai e=(
−→
x,y), whe e −→
xis a ec o o ma ibu e– alues
(each o which may be nume ic o symbolic), and y∈Yis a nominal class– alue
named label. Unde he assump ion he e is an unde lying mapping unc ion
so ha y= (−→
x), he goal is o ob ain a model o T ha app oxima es as ˆ
in
o de o classi y non–labelled es examples, so ha ˆ
maximizes he p edic ion
accu acy.
VETIS app oaches he classifica ion o mul idimensional da a se s wi h nu-
me ical a ibu es by isual building o decision ules om meaning ul in e als
belonging o he mos ele an a ibu es. A decision ule is a logic p edica e o
he o m: i an eceden hen label. The an eceden is a conjunc ion o condi ions
A ibu e|=Values, whe e |= is an ope a o ha s a es a ela ionship be ween a
pa icula a ibu e Ajand alues o i s domain D(Aj). In ule lea ning, an
example e=(
−→
x,y) is said co e ed by a ule i −→
x ulfills o is desc ibed by
he condi ions belonging o he an eceden o , wha e e he label associa ed
wi h is. VETIS allows he use o ob ain ules associa ed wi h se e al labels,
which a e in e ac i ely o med om in e als belonging o diffe en a ibu es.
Fo e e y meaning ul in e al is displayed he dis ibu ion o labels wi hin i
and he ela ionship wi h o he in e als. Thus, he elemen al uni o g aphic
in o ma ion in VETIS is called connec ing segmen , desc ibed nex .
De ini ion 1 (Connec ing Segmen ) A connec ing segmen Sassocia ed wi h
an a ibu e Ajis a da a s uc u e consis ing o h ee elemen s (I,H,IH):
–In e al:I=[l, u)is a le –closed, igh –open in e al in R.
–His og am:H={H1,...,Hz}is a his og am wi h he numbe o examples
o each label in Y={y1;...;yz} ha a e co e ed by I.Anexampleeiis
co e ed by an in e al Iassocia ed wi h he a ibu e Aji he a ibu e– alue
(xij)belongs o he in e al I.
–O e laps:IH is a se o m-1 elemen s, one pe each a ibu e Ak=Aj.
Each elemen o his se is composed by a se o pai s (k;Hk), ela ed o
segmen s o o he a ibu e Akcon aining examples co e ed by I. The ele-
men kis he index o a segmen Sk,andHkis he his og am o class labels
o examples in he in e sec ion I∩I
k.
The pu pose o his s uc u e is o compu e he minimal se o segmen s
efficien ly om which da a label dis ibu ion can be clea ly isualized. This
p ocess is illus a ed in Algo i hm 1 and di ided in o h ee s eps:
1838 Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...
Algo i hm 1 VETIS - compu ing he minimal se o segmen s
INPUT T: Se o nexamples and ma ibu es; δ, γ: in ege
OUTPUT MS: Minimal Se o Segmen s
begin
Build he ini ial se o segmen s IS [S ep–1]
Join consecu i e ini ial segmen s JS [S ep–2]
Build he minimal se o segmen s MS [S ep–3]
end
1. Fi s , an ini ial se o segmen s is compu ed (s ep 1);
2. Second, he segmen s a e analyzed in o de o efine hem by means o joins
ha p ese e a measu e o impu i y γ(s ep 2);
3. Thi d, he minimal se o segmen s is gene a ed acco ding o γ oge he wi h
a measu e o co e age β(s ep 3). E e y se can be displayed in o de o ge
an insigh in o he po en ial complexi y o he final segmen s.
3.1 Ini ializing segmen s
This fi s phase builds mini ial se s ISj, one pe a ibu e Aj.Eachse ISj
is o med by αjconnec ing segmen s and p o ide he use wi h insigh abou
he label dis ibu ion o inpu da a. The diffe en alues o αa e calcula ed by
means o p ojec ions, i.e., he numbe o in e als ha con ain examples o an
only class label. E e y wo adjacen in e als ha e diffe en class. A leas , he e
will be zini ial segmen s pe a ibu e, whe e zis he numbe o diffe en labels
(Y={y1,...,y
z}). This si ua ion is ideal, and i happens when i is possible o
ob ain zsegmen s, each one o hem con aining all he examples o ha class.
In he wo s case, he e will be as much segmen s as n, wi h nbeing he numbe
o examples. In ha case, each segmen con ains only one example.
The ini ial se s o segmen s a e buil by one only scan, p e iously gene a ing
αemp y segmen s o each a ibu e wi h Hp=0(p∈{1; ...;z})andIHk=
0. Then e e y example ei=(xi;yi) upda es he class labels his og am o he
segmen S ha co e s xi(inc easing by one he Hpassocia ed wi h he label
yi), and he ela ionships IHkamong such upda ed segmen s.
The complexi y o his s ep is mainly de e mined by he so algo i hm and
he me hod o gene a e he cu poin s. The la e one akes linea ime, he e o e
he o e all complexi y is Θ(m2lg(m)). The simples way o ob ain he cu poin s
consis s in fixing a new in e al e e y ime a change o label is ound. Consecu i e
alues associa ed wi h he same label will compose a common segmen whe eas
a alue o which he e a e se e al examples o diffe en labels will mos likely
gene a e a segmen whe e I=l=u.
1839
Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...

Algo i hm 2 VETIS - S ep–1
INPUT T: Se o nexamples and ma ibu es
OUTPUT IS: Ini ial Se o Segmen s
begin
o all a ibu e Ajin Tdo
So a ibu e alues
o all change o label in Ajdo
Se a new in e al
Calcula e his og ams o each class and each segmen
end
The fis s ep o he o e all p ocess is shown in Algo i hm 2, whose pu pose
is o ini ialize he da a s uc u e ha suppo s he final display. The addi ional
cos equi ed o compu e he ela ionships among segmen s is no expensi e
since he index ko a segmen Sassocia ed wi h he a ibu e– alue xij can be
calcula ed di ec ly wi h he ollowing exp ession:
k=no m(xij)×α;no m(xij)= xij −MINj
MAXj−MINj
(1)
whe e MINjand MAXja e he lowe and uppe bounds o he a ibu e ange
D(Aj), and αjis he numbe o segmen s o a ibu e Aj. Fu he mo e, VETIS
can inc emen ally educe he numbe o segmen s by joining consecu i e seg-
men s wi h equal dis ibu ion. Le Saand Sbbe wo consecu i e segmen s wi h
associa ed his og ams Haand Hb, espec i ely. They a e g ouped i :
|H
a
p|
suppo (Sa)=|H
b
p|
suppo (Sb);∀p∈{1,...,z}
Al e na i ely, ini ial segmen s can be compu ed using he same α– alue in
all he a ibu es (Figu e 2). By his op ion, αequal–wid h emp y in e als a e
gene a ed o e e y a ibu e so ha his og ams a e inc emen ally comple ed
acco ding o Equa ion 1. In addi ion, segmen s can be displayed in he o m o
bo h egula ba cha s and equal–wid h ba cha s (Figu e 3). As poin ed ou
in [13], he ad an age o equal–heigh ba cha s is a be e use o he a ailable
sc een space, bu his comes a he disad an age ha he p esen ed i ems a e
ha de o compa e. Al hough VETIS displays seem e y simila o Keim & Hao’s
Hie a chical Pixel Ba Cha s [13], ou app oach does no belong o pixel–based
echniques since he main goal is no o ep esen inpu da a di ec ly. Con a y,
VETIS is based on da a agg ega ion in o de o p o ide in e ac i e ule mining
om diffe en g aphic en i ies. VETIS p o ides displays o he eigh op ions in
o de o ge an insigh in o he po en ial complexi y o he final minimal se (see
Figu es 2 and 3).
1840 Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...
(a) Diffe en α– alue op ion (α7= 652,
α12 = 516, and α17 = 531).
(b) Equal α– alue op ion (α=100).
Figu e 2: Wa e– o m da a se . Ini ial segmen s in h ee a ibu es (x7, x15, and
x16) displayed as equal–wid h ba s.
(a) A ibu e x5. Fixed α– alue equal
o 200 (181 segmen s).
(b) A ibu e x10. Dynamic α– alue
(532 segmen s).
Figu e 3: Wa e– o m da a se : ini ial segmen s in a ibu es x5 and x10 displayed
sepa a ely as egula ba s.
3.2 Joining segmen s
In he second phase, p e ious ini ial segmen s a e efined in o de o ob ain m
smalle se s JSj, one pe each ini ial se ISj(j∈{1,...,m}). The new segmen s
a e ob ained by union o consecu i e ini ial segmen s om a measu e o impu i y
biassing in a ou o he a ibu es wi h leas numbe o segmen s and smalle
in e sec ion among hem. Some defini ions ela ed o his s ep a e p o ided nex .
De ini ion 2 (Pu e Segmen ) A pu e segmen S ep esen s an in e al Io
he j h a ibu e Aj o which all he examples a e associa ed wi h he same class
label:
ei,e
i∈T ·xij ∈I∧xij∈I∧yi=yi
1841
Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...
Algo i hm 3 VETIS - S ep–2
INPUT IS: Se o Ini ial Segmen s; δ, γ: in ege
OUTPUT JS: Se o Join Segmen s
begin
o all a ibu e Ajdo
epea
Sbes ←∅
o all pai o consecu i e impu e segmen s (Sa,Sb)∈ISjdo
S←S
a∪S
b
i pu i y(S)≥δand suppo (S)>suppo (Sbes ) hen
Sbes ←S

i Sbes =∅ hen
Replace Saand Sbwi h Sbes
un il Sbes =∅
o all segmen Sjin ISjdo
i suppo (Sj)≥γand pu i y(Sj)≥δ hen
JSj←JSj∪{S
j}
end
De ini ion 3 (Impu e Segmen ) An impu e segmen S ep esen s an in e -
al Io he j h a ibu e Aj o which he e a e examples associa ed wi h diffe en
class labels:
∃ei,e
i∈T ·xij ∈I∧xij∈I∧yi=yi
De ini ion 4 (Suppo ) The suppo o a segmen Sis he numbe o examples
co e ed by S:
suppo (S)=
z

p=1
|H
p|
De ini ion 5 (Pu i y) The pu i y o a segmen Sis he pe cen age o examples
co e ed by Swi h a majo i y label wi h espec o i s co e age:
pu i y(S)= z
max
p=1
|H
p|
suppo (S)
De ini ion 6 (Minimum Suppo δ)The minimum suppo δis he lowes
suppo ha a segmen mus su pass o belong o he Minimal Se o Connec ing
Segmen s (MS).
De ini ion 7 (Minimum Pu i y γ)The minimal pu i y γis he lowes pe -
cen age o examples wi h a majo i y label wi h espec o he numbe o examples
co e ed by an impu e segmen in o de o belong o MS.
1842 Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...
(a) Join segmen s in egula ba s using
β= 100 and γ=0.5. (b) Join segmen s in g ey scale using
β= 1 and γ=0.4.
Figu e 4: Wa e– o m da a se . Join segmen s in x7, x15, and x16.
The JS se s a e buil by an i e a i e p ocedu e (see Alg. 3). Fo each a ibu e
Aj,VETIS sea ches he ISj o consecu i e impu e segmen s whose union is
possible and whose esul ing suppo is he highes . Two consecu i e impu e
segmen s can be joined i he esul ing pu i y is g ea e han o equal o he
minimum pu i y γ. The use can se bo h pa ame e s δand γini ially. The
pa ame e δcon ols indi ec ly he size o he segmen (numbe o examples
included in he segmen ). The pa ame e γdeals wi h he dis ibu ion o classes
wi hin segmen s. By de aul , δis se o 1, because use can be in e es ed in any
alid segmen , and γ o 95% as pu e segmen s a e p e e ed. I he pa ame e s δ
and γexceed he co e age and pu i y alues, espec i ely, o a specific segmen
ha has been ecen ly joined, hen bo h segmen s can be defini ely joined.
3.3 Building he minimal se
In he las phase, he goal is o find he leas numbe o segmen s om which o
isualize he label dis ibu ion, ans o ming housands o examples wi h dozens
o a ibu es in o ew in e als ha can be clea ly sepa a ed in he display. An
i e a i e p ocedu e adds joined segmen s om he JS o he MS (see Alg. 4).
In each i e a ion, only a new segmen is included in he MS: he one wi h he
la ges numbe o examples ha a e no ye co e ed by o he segmen s al eady
included in he MS se . Thus, he fi s segmen o be included will be he one
wi h he highes suppo . The p ocedu e ends when ei he all he examples ha e
been co e ed o he e is no segmen ha co e s examples non–co e ed by he
MS se . The numbe o new examples Δassocia ed wi h an a ibu e Aj ha
a segmen Sj∈JSjcan p o ide o he MS se is compu ed by he in e sec ion
among IHjand all he his og ams Hassocia ed wi h he segmen s Sal eady
included in he MS se . Smay no be necessa ily associa ed wi h Aj.
1843
Fe e -T oyano F.J., Aguila -Ruiz J.S., Riquelme J.C.: Connec ing Segmen s ...