Data Mining
Practical Machine Learning Tools and Techniques
Slides for Chapter 3 of Data Mining by I. H. M. %. Hall itten! ". #ran$ and
Input' Concepts! instances! attributes
Ter*inology hat+s a concept,
Classification! association! clustering! nu*eric prediction .elations! flat files! recursion /o*inal! ordinal! inter0al! ratio %.##! attributes! *issing 0alues! getting to $no1 data
hat+s in an e-a*ple,
hat+s in an attribute,
Preparing the input
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&
Ter*inology
Co*ponents of the input'
Concepts' $inds of things that can be learned
%i*' intelligible and operational concept description
Instances' the indi0idual! independent e-a*ples of a concept
/ote' *ore co*plicated for*s of input are possible e 1ill focus on no*inal and nu*eric ones
%ttributes' *easuring aspects of an instance
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
hat+s a concept,
Styles of learning'
Classification learning' predicting a discrete class %ssociation learning' detecting associations bet1een features Clustering' grouping si*ilar instances into clusters /u*eric prediction' predicting a nu*eric quantity
Concept' thing to be learned Concept description' output of learning sche*e
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &) 2
Classification learning
"-a*ple proble*s' 1eather data! contact lenses! irises! labor negotiations Classification learning is supervised
Sche*e is pro0ided 1ith actual outco*e
4utco*e is called the class of the e-a*ple Measure success on fresh data for 1hich class labels are $no1n (test data) In practice success is often *easured sub5ecti0ely
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
%ssociation learning
Can be applied if no class is specified and any $ind of structure is considered 7interesting8 Difference to classification learning'
Can predict any attribute+s 0alue! not 5ust the class! and *ore than one attribute+s 0alue at a ti*e Hence' far *ore association rules than classification rules Thus' constraints are necessary
Mini*u* co0erage and *ini*u* accuracy
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
Clustering
#inding groups of ite*s that are si*ilar Clustering is unsupervised
The class of an e-a*ple is not $no1n
Success often *easured sub5ecti0ely
Sepal length Sepal width 3.5 3.0 3.2 3.2 3.3 2.7 Petal length 1.4 1.4 4.7 4.5 6.0 5.1 Petal width 0.2 0.2 1.4 1.5 2.5 1.9 Type Iris setosa Iris setosa Iris versicolor Iris versicolor Iris virginica Iris virginica 5.1 4.9 7.0 6.4 6.3 5.8
1 2 51 52 101 102
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
/u*eric prediction
;ariant of classification learning 1here 7class8 is nu*eric (also called 7regression8) Learning is super0ised
Sche*e is being pro0ided 1ith target 0alue
Measure success on test data
Outloo# Sunny Sunny Overcast Rainy Tem"erature Hot Hot Hot Mild Humidity High High High Normal !indy False True False False Play time 5 0 55 40
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
hat+s in an e-a*ple,
Instance' specific type of e-a*ple
Thing to be classified! associated! or clustered Indi0idual! independent e-a*ple of target concept Characteri=ed by a predeter*ined set of attributes .epresented as a single relation>flat file /o relationships bet1een ob5ects
Input to learning sche*e' set of instances>dataset
.ather restricted for* of input
Most co**on for* in practical data *ining
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
<
% fa*ily tree
Peter M = Peggy F Grace F = Ray M
Steven M
Graham M
Pam F
Ian M
Pippa F
Brian M
Anna F
Nikki F
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?@
#a*ily tree represented as a table
Name Peter Peggy Steven &raham Pam $an Pi""a 'rian %nna Ni##i
&ender Male Female Male Male Female Male Female Male Female Female
Parent* ( ( Peter Peter Peter &race &race &race Pam Pam
"arent) ( ( Peggy Peggy Peggy Ray Ray Ray $an $an
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
??
The 7sisterAof8 relation
First "erson Peter Peter Steven Steven Steven $an %nna Ni##i Second "erson Peggy Steven Peter &raham Pam Pi""a Ni##i %nna Sister o,( No No No No +es +es +es yes
?&
First "erson Steven &raham $an 'rian %nna Ni##i
Second "erson Pam Pam Pi""a Pi""a Ni##i %nna
Sister o,( +es +es +es +es +es +es No
All the rest
Closed-world assumption
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
% full representation in one table
First "erson Name Steven &raham $an 'rian %nna Ni##i &ender Male Male Male Male Female Female Parent* Peter Peter &race &race Pam Pam Parent) Peggy Peggy Ray Ray $an $an Name Pam Pam Pi""a Pi""a Ni##i %nna Second "erson &ender Female Female Female Female Female Female Parent* Peter Peter &race &race Pam Pam Parent) Peggy Peggy Ray Ray $an $an +es +es +es +es +es +es No Sister o,(
All the rest
If second persons gender = female and first persons parent = second persons parent then sister-of = yes
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?3
Benerating a flat file
Process of flattening called 7denor*ali=ation8
Se0eral relations are 5oined together to *a$e one
Possible 1ith any finite set of finite relations Proble*atic' relationships 1ithout preAspecified nu*ber of ob5ects
"-a*ple' concept of nuclear-family
Denor*ali=ation *ay produce spurious regularities that reflect structure of database
"-a*ple' 7supplier8 predicts 7supplier address8
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?2
The 7ancestorAof8 relation
First "erson Name Peter Peter Peter Peter Pam &race &race &ender Male Male Male Male Female Female Female Parent* ( ( ( ( Peter ( ( Parent) ( ( ( ( Peggy ( ( Name Steven Pam %nna Ni##i Ni##i $an Ni##i All the rest Second "erson &ender Male Female Female Female Female Male Female Parent* Peter Peter Pam Pam Pam &race Pam Parent) Peggy Peggy $an $an $an Ray $an +es +es +es +es +es +es +es +es No %ncestor o,(
Other positive examples here
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?3
.ecursion
Infinite relations require recursion
If person1 is a parent of person2 then person1 is an ancestor of person2 If person1 is a parent of person2 and person2 is an ancestor of person3 then person1 is an ancestor of person3
%ppropriate techniques are $no1n as 7inducti0e logic progra**ing8
(e.g. Cuinlan+s #4IL)
Proble*s' (a) noise and (b) co*putational co*ple-ity
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &) ?6
MultiAinstance Concepts
"ach indi0idual e-a*ple co*prises a set of instances
%ll instances are described by the sa*e attributes 4ne or *ore instances 1ithin an e-a*ple *ay be responsible for its classification
Boal of learning is still to produce a concept description I*portant real 1orld applications
e.g. drug acti0ity prediction
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?9
hat+s in an attribute,
"ach instance is described by a fi-ed predefined set of features! its 7attributes8 Dut' nu*ber of attributes *ay 0ary in practice
Possible solution' 7irrele0ant 0alue8 flag
.elated proble*' e-istence of an attribute *ay depend of 0alue of another one Possible attribute types (7le0els of *easure*ent8)'
Nominal, ordinal, interval and ratio
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?:
/o*inal quantities
;alues are distinct sy*bols
;alues the*sel0es ser0e only as labels or na*es Nominal co*es fro* the Latin 1ord for na*e ;alues' 7sunny8!8o0ercast8! and 7rainy8
"-a*ple' attribute 7outloo$8 fro* 1eather data
/o relation is i*plied a*ong no*inal 0alues (no ordering or distance *easure) 4nly equality tests can be perfor*ed
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
?<
4rdinal quantities
I*pose order on 0alues Dut' no distance bet1een 0alues defined "-a*ple' attribute 7te*perature8 in 1eather data
;alues' 7hot8 E 7*ild8 E 7cool8
/ote' addition and subtraction don+t *a$e sense "-a*ple rule' te*perature F hot play G yes Distinction bet1een no*inal and ordinal not al1ays clear (e.g. attribute 7outloo$8)
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&@
Inter0al quantities
Inter0al quantities are not only ordered but *easured in fi-ed and equal units "-a*ple ?' attribute 7te*perature8 e-pressed in degrees #ahrenheit "-a*ple &' attribute 7year8 Difference of t1o 0alues *a$es sense Su* or product doesn+t *a$e sense
Hero point is not definedI
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&?
.atio quantities
.atio quantities are ones for 1hich the *easure*ent sche*e defines a =ero point "-a*ple' attribute 7distance8
Distance bet1een an ob5ect and itself is =ero %ll *athe*atical operations are allo1ed %ns1er depends on scientific $no1ledge (e.g. #ahrenheit $ne1 no lo1er li*it to te*perature)
.atio quantities are treated as real nu*bers
Dut' is there an 7inherently8 defined =ero point,
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&&
%ttribute types used in practice
Most sche*es acco**odate 5ust t1o le0els of *easure*ent' no*inal and ordinal /o*inal attributes are also called 7categorical8! 8enu*erated8! or 7discrete8
Dut' 7enu*erated8 and 7discrete8 i*ply order
Special case' dichoto*y (7boolean8 attribute) 4rdinal attributes are called 7nu*eric8! or 7continuous8
Dut' 7continuous8 i*plies *athe*atical continuity
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&3
Metadata
Infor*ation about the data that encodes bac$ground $no1ledge Can be used to restrict search space "-a*ples'
Di*ensional considerations (i.e. e-pressions *ust be di*ensionally correct) Circular orderings (e.g. degrees in co*pass) Partial orderings (e.g. generali=ation>speciali=ation relations)
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&2
Preparing the input
Denor*ali=ation is not the only issue Proble*' different data sources (e.g. sales depart*ent! custo*er billing depart*ent! J)
Differences' styles of record $eeping! con0entions! ti*e periods! data aggregation! pri*ary $eys! errors Data *ust be asse*bled! integrated! cleaned up 7Data 1arehouse8' consistent point of access
"-ternal data *ay be required (7o0erlay data8) Critical' type and le0el of data aggregation
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&3
The %.## for*at
% % ARFF file for weather data with some numeric features % relation weather attri!ute attri!ute attri!ute attri!ute attri!ute outloo" #sunny$ o%ercast$ rainy& temperature numeric humidity numeric windy #true$ false& play' #yes$ no&
data sunny$ ()$ ()$ false$ no sunny$ (*$ +*$ true$ no o%ercast$ (3$ (,$ false$ yes ---
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&6
%dditional attribute types
%.## supports string attributes'
attri!ute description string
Si*ilar to no*inal attributes but list of 0alues is not preAspecified
It also supports date attributes'
attri!ute today date
Kses the IS4A:6@? co*bined date and ti*e for*at yyyy-MM-dd-T !mm!ss
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
&9
.elational attributes
%llo1 *ultiAinstance proble*s to be represented in %.## for*at
The 0alue of a relational attribute is a separate set of instances
attri!ute !ag relational attri!ute outloo" # sunny$ o%ercast$ rainy & attri!ute temperature numeric attri!ute humidity numeric attri!ute windy # true$ false & end !ag
/ested attribute bloc$ gi0es the structure of the referenced instances
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &) &:
MulitAinstance %.##
% % .ultiple instance ARFF file for the weather data % relation weather attri!ute !ag/I0 # 1$ 2$ 3$ 1$ )$ ,$ 2 & attri!ute !ag relational attri!ute outloo" #sunny$ o%ercast$ rainy& attri!ute temperature numeric attri!ute humidity numeric attri!ute windy #true$ false& attri!ute play' #yes$ no& end !ag data 1$ 3sunny$ ()$ ()$ false4nsunny$ (*$ +*$ true5$ no 2$ 3o%ercast$ (3$ (,$ false4nrainy$ 2*$ +,$ false5$ yes --Data Mining' Practical Machine Learning Tools and Techniques (Chapter &) &<
Sparse data
In so*e applications *ost attribute 0alues in a dataset are =ero
".g.' 1ord counts in a te-t categori=ation proble*
%.## supports sparse data
*$ 2,$ *$ *$ * $*$ ,3$ *$ *$ *$ 3class A5 *$ *$ *$ 12$ *$ *$ *$ *$ *$ *$ 3class 65 #1 2,$ , ,3$ 1* 3class A5& #3 12$ 1* 3class 65&
This also 1or$s for no*inal attributes (1here the first 0alue corresponds to 7=ero8)
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &) 3@
%ttribute types
Interpretation of attribute types in %.## depends on learning sche*e
/u*eric attributes are interpreted as
ordinal scales if lessAthan and greaterAthan are used ratio scales if distance calculations are perfor*ed (nor*ali=ation>standardi=ation *ay be required)
InstanceAbased sche*es define distance bet1een no*inal 0alues (@ if 0alues are equal! ? other1ise)
Integers in so*e gi0en data file' no*inal! ordinal! or ratio scale,
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
3?
/o*inal 0s. ordinal
%ttribute 7age8 no*inal
If age = young and astigmatic = no and tear production rate = normal then recommendation = soft If age = pre-pres!yopic and astigmatic = no and tear production rate = normal then recommendation = soft
%ttribute 7age8 ordinal (e.g. 7young8 F 7preApresbyopic8 F 7presbyopic8)
If age pre-pres!yopic and astigmatic = no and tear production rate = normal then recommendation = soft
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
3&
Missing 0alues
#requently indicated by outAofArange entries
Types' un$no1n! unrecorded! irrele0ant .easons'
*alfunctioning equip*ent changes in e-peri*ental design collation of different datasets *easure*ent not possible
Missing 0alue *ay ha0e significance in itself (e.g. *issing test in a *edical e-a*ination)
Most sche*es assu*e that is not the case' 7*issing8 *ay need to be coded as additional 0alue
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
33
Inaccurate 0alues
.eason' data has not been collected for *ining it .esult' errors and o*issions that don+t affect original purpose of data (e.g. age of custo*er) Typographical errors in no*inal attributes 0alues need to be chec$ed for consistency Typographical and *easure*ent errors in nu*eric attributes outliers need to be identified "rrors *ay be deliberate (e.g. 1rong =ip codes) 4ther proble*s' duplicates! stale data
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
32
Betting to $no1 the data
Si*ple 0isuali=ation tools are 0ery useful
/o*inal attributes' histogra*s (Distribution consistent 1ith bac$ground $no1ledge,) /u*eric attributes' graphs (%ny ob0ious outliers,)
&AD and 3AD plots sho1 dependencies /eed to consult do*ain e-perts Too *uch data to inspect, Ta$e a sa*pleI
Data Mining' Practical Machine Learning Tools and Techniques (Chapter &)
33