ࡱ > " v$ bjbjVV , < < % 3 K K K _ _ _ 8 $ _ N " ! HN JN JN JN JN JN JN P YS j JN - K l @ JN ! K wN R ( K ! HN HN G l ) " L ! PPf _ @I * 4N N 0 N jI S 4 S T L S K L JN JN N S : Dr. Eick
COSC 6342Machine Learning Homework2 Spring 2011
First Draft
Due: all graded problems (10, 11, 13, and 14) are due Mo. March 7, 11a; problem 10b can be submitted after Spring Break, but try your best to submit on Monday!
Last updated: March 3, 10a
10) PRINCIPAL COMPONENT ANALYSIS
i) What is the main difference between principal component analysis and subset selection?
ii) Compute the first principal component for the covariance matrix of Problem 9 (use any procedure you like). What percentage of the variance does the first principal component capture? Interpret your result!
11) K-Means and EM
a) What is the meaning of b_it and h_it in the minimization process of K-means/EMs objective function? What constraint holds with respect to h_it and b_it?
Remark: b_it means h_it means
b) Why do K-means and EM employ an iterative optimization procedure rather than differentiating the objective function and setting its gradient to 0 to derive the optimal clustering? What is the disadvantage of using an iterative optimization procedure?
c) EM is called a soft clustering algorithmwhat does this mean?
d) What are advantages you see in using EM over K-means?
e) Assume you cluster a 2-dimensional dataset with K-means with k=2 using Manhattan distance as your distance function and the initial clusters are:
Cluster1: {(8,8), (8,7), (1,1)} Cluster2:= {(5,4), (2,3), (2,2)}
What clusters will K-means compute in his next iteration! Give all steps of the computation!
12) kNN [8] (not graded)
a) Selecting the proper value for the number of neighbors k is a critical problem when using kNN to solve real-world problems. What approach could be used to select k? [2]
b) Compare kNN with parametric classification approaches. What are the main differences between the two approaches?
c) kNN is a lazy classifier; what does this mean? What are the advantages/disadvantages of using lazy classifiers?
13) Non-Parametric Density Estimation
Assume we have a one dimensional dataset containing values {2, 3, 7, 8, 9, 12}
Assume h=2 for all questions (formula 8.2); compute p(x) using equation 8.2 for x=8 and x=12
Now compute the same densities using Silvermans nave estimator (formula 8.4)!
Now assume we use a Gaussian Kernel Estimator (equation 8.7); give a verbal description and a formula how this estimator measures the density for x=11
Compare the 3 density estimation approaches; what are the main differences and advantages for each approach?
14) Decision Trees
a) We would like to predict the gender of a person based on two binary attributes: leg-cover (pants or skirts) and beard (beard or bare-faced). We assume we have a data set of 20000 individuals, 16000 of which are male and 4000 of which are female. 80% of the 16000 males are barefaced. Skirts are present on 50% of the females. All females are bare-faced and no male wears a skirt.
Compute the information gain of using the attribute leg-cover for predicting gender! Just giving the formula that computes the information gain is fine; you do not need to compute the exact value of the formula! Use H as the entropy function in your formula (e.g. H(1/3,2/3) is the entropy that 1/3 of the examples belong to class1 and 2/3 of the examples belong to class 2).
Computer the information gain of using the attribute beard to predict gender!
Based on your computations which of the two tests would you use as the root test of a decision tree which predicts gender.
b) Why do MANY decision tree learning algorithms grow the entire tree and then apply pruning techniques to trim the t r e e t o o b t a i n a t r e e o f s m a l l e r s i z e ? [ 3 ]
c ) T h e d e c i s i o n t r e e l e a r n i n g a l g o r i t h m i s a g r e e d y a l g o r i t h m . W h a t d o e s t h i s m e a n ? W h a t i s t h e r e a s o n t h a t m o s t d e c i s i o n t r e e l e a r n i n g a l g o r i t h m s a r e g r e e d y a l g o r i t h m s ?
G a i n ( S k i r t = { y e s , n o } ) = H ( 4 / 5 , 1 / 5 ) -( 1 / 1 0 * H ( # $ % . / 8 : ; F G L M _ t } ֿ~skc[cScSKSKS h2 B*php0 hzv B*php0 h; B*php0 hF$r B*php0 hDS B*php0 hC h B*php0 hk~0 h; CJ" aJ" h; CJ" aJ" h@K CJ" aJ" h CJ" aJ" hk~0 hk~0 CJ" aJ" hk~0 h CJ" aJ" hDS CJ" aJ" hk~0 he,T CJ" aJ" hk~0 hk~0 6CJ" aJ" hk~0 h'7 6CJ" aJ" hk~0 h/* CJ" aJ" hk~0 h'7 CJ" aJ" h( CJ aJ ; G & S
g
/ 0 / t B
gdF$r
P
gd $
P
a$gde,T $a$gde,T $a$gde,T % & . ;
R
S
U
e
f
g
i
+ . / 0 t A
B
p
s
w
z
·³tplll h; h1tN j hF$r h 8 UmH nH u h; CJ aJ hF$r hF$r CJ aJ hF$r CJ aJ hF$r hF$r hz8 hF$r h 8 hW h; h1tN CJ aJ h; hW CJ aJ h; hF$r CJ aJ h
hbM hbM B*
ph hR e B*
ph h B*
ph h~ B*php0 *
( 5 # 8 9 : ; O o 1 t y H J Y l j $ $ ʻʻʳ Uhz hz OJ QJ hz
h; PJ h; h; CJ aJ hDS h; hW h 8 h 8 CJ aJ h1tN h"^ h!L h2 hF$r hF$r CJ aJ hF$r CJ aJ hF$r hF$r h 8 hF$r hz8 9 d K K Z $ $ $ $ $ $ $ $
P
gd $
P
a$gdU|[
& F
88^8gd; gd;
& F gdW gdF$r 0/1)+ 9/10*H(8/9,1/9)
PAGE
PAGE 2
EMBED Equation.3
EMBED Equation.3
$ $ $ $ $ $ $ !$ #$ $$ &$ '$ )$ *$ 0$ 1$ 2$ 4$ 5$ ;$ <$ =$ >$ ?$ A$ B$ C$ V$ W$ X$ Y$ [$ \$ o$ p$ q$ r$ t$ u$ v$ Կ h j h hF$r EHUjYM
hF$r UVj h h 8 EHUj1YM
hF$r UVhF$r j hF$r Uh> 0J mH nH uhy :
hy : 0J j hy : 0J UhX~* j hX~* U h$ h h# hF$r h; h; ' $ $ $ "$ #$ %$ &$ ($ )$ 2$ 3$ 4$ ?$ @$ A$ B$ Z$ [$ s$ t$ u$ v$
P
gd gdF$r h]hgd'7 &`#$gdB+ , 1h / =!"#$% `!9 `! { P
2 @ XJ xcdd`` $X bbd12 ,(ㆫar`V`3H1 g` YРW@P5< %!
`3) ,L !
~
Ay ?'i,@պ@9cXgI% Ϭ7S_ &%P$UrI>1@"#RpeqIj. @ ]
@u; b#3X? M@`!9 `Xp53Zg @ XJ xcdd`` $X bbd12 ,(ㆫar`V`3H1 g` YРW@P5< %!
`3) ,L !
~
Ay ?' fiYu&s i#.Y`%D0?L
j>#Ȟp{ @Q$A>$ ; FLLJ% Af Pdh ,] ` MO D d
T 0
# A 2 e `! { P
2 A D `!9 `! { P
2 @ XJ xcdd`` $X bbd12 ,(ㆫar`V`3H1 g` YРW@P5< %!
`3) ,L !
~
Ay ?'i,@պ@9cXgI% Ϭ7S_ &%P$UrI>1@"#RpeqIj. @ ]
@u; b#3X? M@ D d
T b
c $ A ? ? 3 " ` ? 2 e wjJ-;}|4 A - `!9 wjJ-;}|4 @ XJ xcdd`` $X bbd12 ,(ㆫar`V`3H1 g` YРW@P5< %!
`3) ,L !
~
Ay ?'r,@պ@9,ΒJS"Y o@
H5d=Lf pɨ s} cE #F&&\ w3 u(2tA4 | .Ff~ M
! $ % & ' ) ( * + , X . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W R o o t E n t r y F @ f# D a t a
W o r d D o c u m e n t , O b j e c t P o o l `f@ f _ 1 2 9 7 6 7 8 8 9 7
F `f`f O l e
C o m p O b j f O b j I n f o
" # $ % ' ( ) + , - . / 1
F Microsoft Equation 3.0 DS Equation Equation.3 9q W . @ & & MathType Times New Roman Xwaw @w5f - 2
ty O l e P r e s 0 0 0 E q u a t i o n N a t i v e ; _ 1 2 9 7 6 7 8 9 9 2 F `f`f O l e
2
G iy Times New Roman Xwaw @w5f - 2
@" by
&
"System 5f
! - NANI q x2
b i t
F Microsoft Equation 3.0 DS Equation Equation.3 9q C o m p O b j f O b j I n f o O l e P r e s 0 0 0
E q u a t i o n N a t i v e ; W . @ & & MathType Times New Roman Xwaw @w6f - 2
ty 2
a iy Times New Roman Xwaw @w6f - 2
@6 hy
&
"System ǐ6f
! \ - NANI q .
h i t Oh +'0 |
, 8 D
P \ d l t 1) Computer Science Normal Christoph Eick 9 Microsoft Office Word @ ~mg @ G@ 1 T a b l e - T S u m m a r y I n f o r m a t i o n ( D o c u m e n t S u m m a r y I n f o r m a t i o n 8 ! 0 M s o D a t a S t o r e PߔfPPf @ O A ՜. +,0 h p
University of Houston 1) Title
^ 2 0 @ P ` p 2 ( 0 @ P ` p 0 @ P ` p 0 @ P ` p 0 @ P ` p 0 @ P ` p 0 @ P ` p 8 X V ~ _HmH nH sH tH @ ` @ N o r m a l CJ _HaJ mH sH tH : : H e a d i n g 1 $@& 5\ D A` D D e f a u l t P a r a g r a p h F o n t V i V T a b l e N o r m a l :V 4 4
l a ( k ( N o L i s t 4 @ 4 '7 F o o t e r
! . )@ . '7 P a g e N u m b e r 6 B 6 [/ B o d y T e x t PJ aJ B ^ "B [/ N o r m a l ( W e b ) d d [$\$ 6 U 16 H y p e r l i n k >*B*ph > B>
F o o t n o t e T e x t CJ aJ < Q< F o o t n o t e T e x t C h a r @ & a@ F o o t n o t e R e f e r e n c e H* PK ! [Content_Types].xmlj0Eжr(Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi} ;~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭? PK ! ֧ 6 _rels/.relsj0 }Q%v/C/} (h"O
= C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_ 6LR7`0̞O,En7Lib/Se е PK ! ky theme/theme/themeManager.xml M
@}w7c(Ebˮ CAǠҟ7՛K
Y,
e.|,H ,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+&
8 PK ! P theme/theme/theme1.xmlYOo6w toc'vuر-Mn iP@I}úama[إ4:l ЯGRX^6؊>$ !)O^rC$y@ /yH*)UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSe bORD۫qu gZo~ٺlAplxpT0+[}`j zA V2Fi@qv֬5\|ʜ̭NleXd sjcs7f
W+Ն7` g ȘJj|h(KD-
dXiJ؇(x$( :;˹! I_TS 1?E ??ZBΪmU/ ?~xY'y5g&/ɋ>GMGeD3Vq%'#q$8K )fw 9:ĵ
x}rxwr:\TZaG*y8IjbRc|XŻǿI
u3KGnD 1NIBs
RuK>V.E L+M2#'fi ~V vl{u8z H
* :( W ☕
~JTe\O*tHGHY }KNP*ݾ˦ TѼ9/#A7qZ $*c?qUnwN%Oi4 =3ڗP
1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g-
eW
)6-rC Sj
id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q% p%m&]caS l=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f
Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ .uχYC6OMf3or$5N HT[XF64T,ќM0E)`#5XY`פ ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R 3U~7+#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vp IYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07% < ҍ PK !
ѐ ' theme/theme/_rels/themeManager.xml.relsM
0wooӺ&݈Э5
6?$Q
,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{ P8g/ ]QAsم(#L[ PK- ! [Content_Types].xmlPK- ! ֧ 6 + _rels/.relsPK- ! ky theme/theme/themeManager.xmlPK- ! P theme/theme/theme1.xmlPK- !
ѐ ' theme/theme/_rels/themeManager.xml.relsPK ]
2 v 2 5 v * $ $ $ '
$ v$ $ v$
' ! ! - / 5 :: / X 2 $ `! { P
2 A .* 2 $ `Xp53Zg A o+ @ @ (
B A ? ? O b j e c t 4 " ?
B A ? ? O b j e c t 4 " ? B
S ? g h v ; t w t & ' $ ( X [ # " # % & ( ) A B w O Q + 4 # S U
" # % & ( ) A B w 3 3 3 3 3 3 3 } ; R 4 5 " # % & ( ) A B Z [ s t w } ; R 4 5 " # % & ( ) A B Z [ s t w N%pڋ xCv wu"tv ap( :<)z.Ά ~,Y, ,6w( "j/ Rbf
|S ><dK<d wu" ~, x "j/ lB NTVޑ oBw_h,"2H*@u "
ЩL1 4VN D3>Aڂך t. }̡F6 d b f9 ~ ; + > d $ r n 1 4Q !L +" v% F( /* * X~* B+ $W- . V;/ ry/ k~0 j3 '7 8 8 z8 y : < j= @@ O@ >I dLJ jJ @K rK -M bM N 1tN 7 O d&O gQ e,T _X U|[ Hf^ e R e =m ~o Seq F$r zv 0 W ^ & < DS 5 b C 4C y8 # Y 8 \ C 0V e 2 ] +] 7 E x P O b% @: "^ rt S [
7 k q
< } {B w s* ' X f@ CV z [/ _ 9 k; V M ( C U
@( v @ H @ U n k n o w n G * Ax T i m e s N e w R o m a n 5 S y m b o l 3. * Cx A r i a l G=
j M S M i n c h o -3 f g =. C o r d i a N e w ?= * Cx C o u r i e r N e w ; W i n g d i n g s A B C a m b r i a M a t h " q h FBFR 5 A A ! 24 d 3Q HX ? b 2 ! x x 1 ) C o m p u t e r S c i e n c e C h r i s t o p h E i c k T
F' Microsoft Office Word 97-2003 Document
MSWordDoc Word.Document.8 9q