ࡱ> &(#$%_ ^bjbj,E,E .pN/N/*'8dV|mj("mZ>ZZ iiiiiii$)lni]ZSRmZZZi73'j5f5f5fZzi5fZi5f5fiTidr)E] ii=j0mj(i,so`bsoTiTisohi(ZZ5fZZZZZii5fZZZmjZZZZsoZZZZZZZZZ : Preparing for Final Exam We will have 5 problems to solve on the exam. They will be of the same type as the ones below, except with different numbers / data, or a distance function. The distance function to be used will be specified. Partial credit will be given if only part of the solution is correct. For example, if you solved half of the problem you will get half of the points. 1. Find the set of optimal rules in Table T1 describing C in terms of A, F, G. Use ID3 algorithm. XAFGCx1a2f1g3c2x2a1f2g1c1x3a1f2g2c1x4a1f1g1c2x5a2f2g2c2x6a1f2g3c2Table T1 Solution: E(A) = 4/6(1) + 2/6(0) = 0.6667 E(F) = 4/6(1) + 2/6(0) //same as E(A) = 0.6667 E(G) = 2/6(0) + 2/6(1) + 2/6(1) = 0 + 2/6 + 2/6 = 4/6 = 0.6667 We need to decide which attribute to use, in order to split the tree (table). We choose the attribute with the smallest entropy. They are all the same = 0.6667. We can choose either. We choose E(A) here:  XFGCx2f2g1c1x3f2g2c1x4f1g1c2x6f2g3c2 XFGCx1f1g3c2x5f2g2c2 T2 The table to the right has all values for decision attribute C = c2, so we create a leaf for it. For the table to the left, (we will call it T2) we have different values for the decision attribute C, so we need to split further. So, we calculate entropy for it: E(T2, F) = 1/4(0) + 3/4(1/3log1/3 2/3log2/3) = 0 + 3/4(0.159 + 0.117) = 0.207 E(T2, G) = 1/4(0) + 1/4(0) + 2/4(1) = 0 + 0 + 2/4 = 1/2 = 0.5 We choose the attribute with the smallest entropy - E(T2, F) = 0.207   XGCx2g1c1x3g2c1x6g3c2 XGCx4g1c2 T3 For the table to the left, there is only 1 object (when G=1, we always have c2), so we create a leaf. For the table to the right, (we will call it T3) we have different values for the decision attribute C, so we need to split further. The only attribute we have left is - G, so there is no need to calculate entropy, and we just use G:  Optimal Rules: (by traversing the tree we get the following rules) a2 ! c2 a1 ^ f1 ! c2 a1 ^ f2 ^ g1 ! c1 a1 ^ f2 ^ g2 ! c1 a1 ^ f2 ^ g3 ! c2 2. Find coverings of C in Table T1 (from the previous problem) using Rosetta algorithm. Solution: Discernibility Matrix  x1x2afgx3afg-x4-ffgx5-aga-x6-gg--x1x2x3x4x5x6 Discernibility Function  C(A, F, G) = (a) (f) (a + f + g) (f + g) (g) (a + g) = (af) (af + ag) = afg Possible coverings: {a, f, g} 3. Let (S, S1) be a distributed information system. Find certain objects in S satisfying query q = b1*c1*f1. Use help from S1. System S System S1 ABCDEx1a1b1c1d1e1x2a2b1c1d1e1x3a1b2c2d2e1x4a1b2c1d1e1x5a2b2c2d2e2 ABCGFy1a1b1c1g1f1y2a1b1c1g2f1y3a2b1c2g1f1y4a2b2c1g2f2y5a2b2c2g1f1 Solution: Since the attribute F is not present in the System S, to which the query q = b1*c1*f1 was sent to, the system cannot answer the query. Therefore, we need to extract definitions of f1 from a remote site system S1, in terms of attributes, which the system S recognizes. So, we will use the attributes, that are common for both databases {A, B, C} (overlap). We do that by following LERS strategy (find definitions of F in terms of A, B, C in the System S1). We will obtain: certain rules: //we only use certain rules, since we are asked a1 ! f1 //to find certain objects satisfying the query b1 ! f1 by using the definition of f1 which we learned: a1 ! f1 and b1 ! f1 we can replace f1 with either a1 OR b1 in the query: (we recall that OR is represented by the + (plus sign), and AND is represented by the * (multiplication sign) ) So, q = b1*c1*f1 = b1*c1*(a1 + b1) = b1*c1*a1 + b1*c1  = b1*c1*a1 + b1*c1 //since b1*c1 includes b1*c1*a1 = b1*c1 Certain objects in S satisfying the query: x1, x2 4. Cluster the following four objects (with (x, y) representing locations) into two clusters. Initial cluster centers are: Medicine A (1, 1) and Medicine B (2, 1). Use Euclidean distance. Use k-means algorithm to find the two cluster centers after the first iteration. ObjectAttribute 1 (x)Attribute 2 (y)Medicine A11Medicine B21Medicine C43Medicine D54 Solution: Iteration 1 (1, 1)(2, 1)PointDist Mean 1Dist Mean 2Cluster(1, 1)(2, 1)(4, 3)(5, 4) First we list all objects / points in the first column of the table above. The initial cluster centers means, are (1, 1) and (2, 1) - chosen randomly. Next, we will calculate the distance from the first point (1, 1) to each of the two means, by using the distance function - Euclidean distance. The distance from the first point (1, 1) to the first mean (1, 1) is = 0, because the point is equal to the mean. point mean2 x1, y1 x2, y2 (1, 1) (2, 1) We recall from a previous lecture, the formula for Euclidean distance between two points i and j is:  d(i, j) = |xi1 - xj1 |2+ | xi2 - xj1|2 + + | xip - xjp|2 where xi1 is the value of attribute 1 for i and xj1 is the value of attribute 1 for j, and so on, as many attributes we have shown up to p - xip in the formula. In our case, we only have 2 attributes. So, the Euclidean distance between our points point1 and mean2, which have attributes x and y would be calculated as follows:  d(point1, mean2) = |xp1 xp1 |2+ | yp1 - yp2|2  = |1 2 |2+ | 1 1|2  = | 1 |2+ | 0 |2  = 1 + 0  = 1 = 1 *Note: Euclidean distance calculator can be found here:  HYPERLINK "http://people.revoledu.com/kardi/tutorial/Similarity/EuclideanDistance.html" http://people.revoledu.com/kardi/tutorial/Similarity/EuclideanDistance.html Square root calculator can be found here:  HYPERLINK "http://www.csgnetwork.com/squarerootsquarecalc.html" http://www.csgnetwork.com/squarerootsquarecalc.html So, we fill in these values in the table: Iteration 1 (1, 1)(2, 1)PointDist Mean 1Dist Mean 2Cluster(1, 1)011(2, 1)(4, 3)(5, 4) Which cluster should the point (1, 1) be placed in? The one, where the point has the shortest distance to the mean that is mean 1 (cluster 1), since the distance is 0. Cluster 1 Cluster 2 (1, 1) So, we go to the next point; and, analogically, we fill in the rest of the table. Iteration 1 (1, 1)(2, 1)PointDist Mean 1Dist Mean 2Cluster(1, 1)011(2, 1)102(4, 3)3.602.832(5, 4)54.242 Cluster 1 Cluster 2 (1, 1) (2, 1) (4, 3) (5, 4) Next, we need to re-compute the new cluster centers (means). We do so, by taking the mean of all points in each cluster. For Cluster 1, we only have one point A(1, 1), which was the old mean, so the cluster center remains the same. For Cluster 2, we have ( (2+4+5)/3, (1+3+4)/3 ) = (3.66, 2.66) 5. Assume that the database D is given by the table below. Follow single link technique to find clusters in D. Use as a distance measure - the number of attribute values, on which the objects differ. D XAFGCx1a2f1g3c2x2a1f2g1c1x3a2f2g2c1x4a1f1g1c2x5a2f2g2c2x6a1f2g3c2 Solution: Calculate the distance from each object to all other objects, using as a distance measure - the number of attribute values, on which the objects differ. For example, the object x1 has the following values: x1 (a2, f1, g3, c2) The object x3 has the following values: x3 (a2, f2, g2, c1) The distance between x1 and x3 is the number of attribute values, on which the objects differ: x1 (a2, f1, g3, c2) x3 (a2, f2, g2, c1) They differ on 3 of the attribute values. Distance matrix  x10x240x3320x42240x523130x6223220x1x2x3x4x5x6 With single link, we start by placing each object in a separate cluster. Next, we identify the two clusters with the shortest distance in the matrix, and merge them together. Re-compute the distance matrix, as those two clusters are now in a single cluster, (no longer exist by themselves). By looking at the distance matrix above, we see that x3 and x5 have the smallest distance from all - 1 So, we merge those two in a single cluster, and re-compute the distance matrix. dendogram  Since, we have merged (x3, x5) together in a cluster, we now have one entry for (x3, x5) in the table, and no longer have x3 or x5 separately. Therefore, we need to re-compute the distance from each point to our new cluster - (x3, x5). We recall that, with the single link method the proximity of two clusters is defined as the minimum of the distance between any two points in the two clusters. Therefore, the distance between lets say (x3, x5) and x1 would be calculated as follows: dist( (x3, x5), x1 ) = MIN ( dist(x3, x1) , dist(x5, x1) ) = MIN ( 3 , 2 ) //from original matrix = 2 Distance matrix  x10x240(x3, x5)220x42220x622220x1x2(x3, x5)x4x6 Looking at the last distance matrix above, we see that the smallest distance is 2 . A number of clusters have that same distance, so we can pick either one. We choose (x3, x5) and x4 to merge together. dendogram  Re-computing the distance matrix with the new cluster: Distance matrix x10x240(x3, x5, x4)220x62220x1x2(x3, x5, x4)x6 Looking at the last distance matrix above, we see that the smallest distance is 2 . A number of clusters have that same distance, so we can pick either one. We choose (x3, x5, x4) and x2 to merge together. dendogram  Re-computing the distance matrix with the new cluster: Distance matrix x10(x3, x5, x4, x2)20x6220x1(x3, x5, x4, x2)x6 Looking at the last distance matrix above, we see that the smallest distance is 2 . A number of clusters have that same distance, so we can pick either one. We choose (x3, x5, x4, x2) and x1 to merge together. dendogram  Re-computing the distance matrix with the new cluster: Distance matrix  (x3, x5, x4, x2, x1)0x620(x3, x5, x4, x2, x1)x6 (12                   " # % & ( ) + , . / 0 2 3 5 6 8 9 ; < > ? @ B C E F H I K L N O hCJaJhnHtH h5h@mHsHhh@ h@5\T $Ifgd$a$ JDDDDD$Ifkd$$Iflrj U@,"FFFFF t0644 lBayt    JDDDDD$Ifkd$$Iflrj U@,"FFFFF t0644 lBayt       JDDDDD$Ifkdp$$Iflrj U@,"FFFFF t0644 lBayt # & ) , / JDDDDD$Ifkd($$Iflrj U@,"FFFFF t0644 lBayt/ 0 3 6 9 < ? JDDDDD$Ifkd$$Iflrj U@,"FFFFF t0644 lBayt? @ C F I L O JDDDDD$Ifkd$$Iflrj U@,"FFFFF t0644 lBaytO P Y Z [ e f } JEEEEEEgdkdP$$Iflrj U@,"FFFFF t0644 lBaytO P V X Y [                 ! # $ & ' ( * + - . 0 1 3 4 5 7 8 : ; = > @ A B C D E F G H I J K L N O Q R ߽h<nHtHh>*B* phjhUnHtHhB* mHphsHhB* phhnHtH h5hhCJaJG}        gd     Ckd$$Ifl\ FFFF t 6 0644 lBayt$ &#$/If     ! $ ' Ckd$$Ifl\ FFFF t 6 0644 lBayt$ &#$/If' ( + . 1 4 RCCCC$ &#$/Ifkd$$Ifl\ FFFF t 6 0644 lBayt4 5 8 ; > A RCCCC$ &#$/IfkdK$$Ifl\ FFFF t 6 0644 lBaytA B C E G I K RM<<<<$1&#$/Ifb$gdkd $$Ifl\ FFFF t 6 0644 lBaytK L O R U X P????$1&#$/Ifb$kd$$Ifl\ , F&F&F&F& t 610644 lBae4ytR T U W X Y [ \ ^ _ a b d e f g   خh5B* \phh<nHtHjhUnHtHh5B* phhB* phhB* nHphtHhCJaJhnHtHhDX Y \ _ b e P????$1&#$/Ifb$kd $$Ifl\ , F&F&F&F& t 610644 lBae4yte f g h i j k l PKKKKKKgdkdU $$Ifl\ , F&F&F&F& t 610644 lBae4ytl r s t u } ~ 1F[\]gd^gd$E&#$/IfgdeVVV$E&#$/Ifkd $$IflFFFF t 6E06    44 lBayteVVV$E&#$/Ifkd $$IflFFFF t 6E06    44 lBayteVVV$E&#$/Ifkd $$IflFFFF t 6E06    44 lBayte`SSS $&`#$/Ifgdkd\ $$IflFFFF t 6E06    44 lBaytgZZZ $&`#$/Ifkd$$IflFFFF t 6`06    44 lBaytgbbbbUHb p^p`gd ^`gdgdkd$$IflFFFF t 6`06    44 lBaytop  24gd2 *,<|028:FHLNTV`bfhnprt|~hCJaJhB* mHnHphsHtHhB* nHphtH h5\hhB* o(phh>*B* phjhUnHtHh5B* phhB* ph>468:<04:<>@BDF$IfgdFHNV$$Ifkd$$Ifl֞ |sja,"F t0644 lBaytVXZ\^`$If`bhp$$Ifkd]$$Ifl֞ |sja,"FF t0644 lBaytptvxz|$If|~$$Ifkd#$$Ifl֞ |sja,"FFF t0644 lBayt$If$$Ifkd$$Ifl֞ |sja,"FFFF t0644 lBayt$If$$Ifkd$$Ifl֞ |sja,"FFFFF t0644 lBayt%&/1;QȾ𮪢h@B* phh@>*B* phhqhq<h@mHsHh@hjhUnHtHh>*B* phhB* mHphsHhB* mHnHphsHtHhB* nHphtHhB* phhCJaJ5$If$$Ifkdu$$Ifl֞ |sja,"FFFFFF t0644 lBayt$If$gdkd;$$Ifl֞ |sja,"FFFFFF t0644 lBaytRu78PQSUWY[$$n&`#$/Ifa$b$$a$gd[\_-$$n&`#$/Ifa$b$kd$$Ifl2ֈ/ A  t 6`n0644 lae4_behkn$$n&`#$/Ifa$b$nor-$$n&`#$/Ifa$b$kd$$Ifl2ֈ/ A  t 6`n0644 lae4rux{~$$n&`#$/Ifa$b$-$$n&`#$/Ifa$b$kdw$$Ifl2ֈ/ A  t 6`n0644 lae4$$n&`#$/Ifa$b$-$$n&`#$/Ifa$b$kd+$$Ifl2ֈ/ A  t 6`n0644 lae4$$n&`#$/Ifa$b$-$$n&`#$/Ifa$b$kd$$Ifl2ֈ/ A  t 6`n0644 lae4$$n&`#$/Ifa$b$-(gdqkd$$Ifl@ֈ/ A  t 6`n0644 lae4$$}&`#$/Ifa$b$+$$}&`#$/Ifa$b$kdU$$Ifl2ֈ/ A  t 6`}0644 lae4$$}&`#$/Ifa$b$+$$}&`#$/Ifa$b$kd $$Ifl2ֈ/ A  t 6`}0644 lae4$$}&`#$/Ifa$b$+$$}&`#$/Ifa$b$kd$$Ifl2ֈ/ A  t 6`}0644 lae4$$}&`#$/Ifa$b$+$$}&`#$/Ifa$b$kd$$Ifl2ֈ/ A  t 6`}0644 lae4  $$}&`#$/Ifa$b$+$$}&`#$/Ifa$b$kdC$$Ifl2ֈ/ A  t 6`}0644 lae4 #&$$}&`#$/Ifa$b$&'()*+&&&$a$kd$$Ifl@ֈ/ A  t 6`}0644 lae4*+,-./01;<HJBRT`b:MN $a$QRl/0:C 2Y< > @ B D F H J K L M O 똮h@B*ph3fh@5B* \phh@>*B* phh@mHsHhh@B* mHphsH+jh@B* U_HXmHnHphtHuh@B*phh@B*ph3h@6B* ]phh@h@B* phh@B*ph2$If tnnn$Ifkd$$IflF ,"   t06    44 latnnn$Ifkd"$$IflF ,"   t06    44 latnnn$Ifkd$$IflF ,"   t06    44 latnnn$Ifkd$$IflF ,"   t06    44 la  !")01trrrrrrllll$Ifkdo$$IflF ,"   t06    44 la 128DPX\VVVV$Ifkd$$Ifl\F2 ,[/ t0644 laXY`abc\VVVV$Ifkd $$Ifl \F2 ,[/ t0644 lacdklmn\VVVV$Ifkd"!$$Ifl \F2 ,[/ t0644 lanovwxy\VVVV$Ifkd!$$Ifl\F2 ,[/ t0644 layz\VVVV$Ifkdf"$$Ifl \F2 ,[/ t0644 la- . / < K \ZZZZZZZZZkd#$$Ifl \F2 ,[/ t0644 la O P V W Y Z ] ^ !! ! !!!!!!! !!!&!P!Q!S!T!!!!{""""""""""""""""""""""ӭӛӛ"jh@U_HXmHnHtHuh@B* mHphsH h@H* h@H*jh@CJUmHnHuh@B* phh@mHsHh@B*ph2h@B* phh@h@B*phw=K ^ _ ` !!!!!z"{"""""""""###%#F#G#I#f#^^$a$"""""## #"###$#E#F#G#H#e#f#g#####$$$c$d$$$$$$%% % %7%8%U%|%%%&&&''''')'4'6';'='L'N'O'P''ккh@B* mHphsHh@5B* \phjO%h@B* Uph h@0Jj#h@B* Uphjh@B* Uph"jh@U_HXmHnHtHuh@B* ph h@H*h@:f#g#h####f$$ % % % %7%8%D%E%L%S%T%$If^^T%U%[%g%s%{%\VVVV$Ifkd&$$Ifl\F2 ,[/ t0644 la{%|%%%%%\VVVV$Ifkd6'$$Ifl \F2 ,[/ t0644 la%%%%%%\VVVV$Ifkd'$$Ifl \F2 ,[/ t0644 la%%%%%%\VVVV$Ifkdz($$Ifl\F2 ,[/ t0644 la%%%%%%\VVVV$Ifkd)$$Ifl \F2 ,[/ t0644 la%%%%X&Y&o&v&w&&&\ZZZZZZZZZkd)$$Ifl \F2 ,[/ t0644 la &&&&&&&&&'Tkd`*$$Ifl\ m9 t0+644 la$If ' ''''''Vkd+$$Ifl\ m9 t0+644 la$If''#'%''')'\VVVV$Ifkd+$$Ifl\ m9 t0+644 la)'*'1'6';'='\VVVV$IfkdF,$$Ifl\ m9 t0+644 la='>'E'G'L'N'\VVVV$Ifkd,$$Ifl\ m9 t0+644 laN'O'P'f'v''''((t(\ZZZZZZZZZkd-$$Ifl\ m9 t0+644 la ''-(.(0(1((((((((((((((((((((((())++&,(,--D.E.v//$0%0K0O0l0p0|0000뙍h@B* mHphsHh@6B* ]mHphsHh@5B* \phh@B* ph+jh@B* U_HXmHnHphtHuh@>*B* phhh@mHsHh@h@B* phh@B* mHphsH1t(u(((((())))))))$If)))))))NHHHHH$Ifkd,.$$Iflrj U@," t0644 la)))))))NHHHHH$Ifkd.$$Iflrj U@," t0644 la)))))))NHHHHH$Ifkd&/$$Iflrj U@," t0644 la)))))))NHHHHH$Ifkd/$$Iflrj U@," t0644 la)))))))NHHHHH$Ifkd 0$$Iflrj U@," t0644 la)))))))NHHHHH$Ifkd0$$Iflrj U@," t0644 la))))))***NLLLLLLLkd1$$Iflrj U@," t0644 la** + ++++++++++++++++++++$If$a$++++(""$Ifkd1$$Ifl֞v gXI:," t0644 la++,,,,$If,,, ,(""$Ifkd>2$$Ifl֞v gXI:," t0644 la , , ,,,,$If,,,,(""$Ifkd2$$Ifl֞v gXI:," t0644 la,,,,,,$If,,",$,(""$Ifkd3$$Ifl֞v gXI:," t0644 la$,&,(,*,,,-,$If-,.,1,3,(""$Ifkd34$$Ifl֞v gXI:," t0644 la3,5,7,9,;,=,$If=,>,?,B,(""$Ifkd4$$Ifl֞v gXI:," t0644 laB,E,H,K,N,Q,$IfQ,R,S,T,(&!$a$kd5$$Ifl֞v gXI:," t0644 laT,x-y-8.9.C.D.F.G.H.I.J.K.L.M.N.O.P..J0K000001^ $p^p`a$$^a$$a$0001111#1$1'191@1B1M1O1[1d111L2M2222222222222D3E33344.4/4142444K4P4R4Y4j444W5X555555555555\Z\[\g\h\ܻܻܻܻܻܻܻܻܻܻܻܳܳܯܻܻܻܻܳܯܻܻܻܭUh@h@B*phh@5B* \ph+jh@B* U_HXmHnHphtHuh@B* phh@B* mHphsHh@6B* ]mHphsHD111111111$If111!1#1$182222$IfkdD6$$Iflֈv gXI; t0644 la$1%1&1'101212kd6$$Iflֈv gXI; t0644 la$If2141617181912kd7$$Iflֈv gXI; t0644 la$If91<1>1@1B1D1E1$IfE1F1I1K1M1O182222$IfkdH8$$Iflֈv gXI; t0644 laO1Q1S1T1U1X12kd8$$Iflֈv gXI; t0644 la$IfX1[1d1g1j1k12kd9$$Iflֈv gXI; t0644 la$Ifk1l1m1<2=2>2?2@2J2K2L2N2O2P2Q2R2S2T2U2V2W2X2Y2Z2[2\2222 p^p`22222222CkdZ:$$Iflrv gXI t0644 la$If22222222Ekd0;$$Iflrv gXI t0644 la$If22222222Ekd<$$Iflrv gXI t0644 la$If22222222Ekd<$$Iflrv gXI t0644 la$If22222233ECCCCkd=$$Iflrv gXI t0644 la$If3333333333333333344*4+4.4142434$If p^p`3444E4G4I4J4\VVVV$Ifkd>$$Ifl2\T\ dT t0644 laJ4K4N4P4R4T4\VVVV$IfkdT?$$Ifl2\T\ dT t0644 laT4U4V4Y4j4m4\VVVV$Ifkd@$$Ifl2\T\ dT t0644 lam4n4o4p4K5L5M5W5Y5Z5\ZZZZZPZZ p^p`kd@$$Ifl2\T\ dT t0644 la Z5[5\5]5^5_5`5a5b5c5d5e5f5g5h55555555$If55555oiii$IfkdA$$Ifl3F,(p t06    44 la55555oiii$IfkdLB$$Ifl3F,(p t06    44 la5555[\\\]\g\i\j\k\l\ommmmmcmmmm p^p`kd C$$Ifl3F,(p t06    44 la The only two clusters left are (x3, x5, x4, x2) and x1 , so we merge them together. dendogram  There is no need to re-compute the distance matrix at this time, as there are no more clusters to merge.     PAGE  PAGE 12 A 1 2 A 1 2 c2 F 1 2 A 1 2 c2 F 1 2 By looking at the table T3, we can see that we only have 1 object for each value of G (when G=1, we always have c1; when G=2, we always have c1; when G=3, we always have c2) so we create leaves. c2 G 1 2 3 c1 c2 c1 -3 -2 -1 x3 x5 -3 -2 -1 x3 x5 x4 -3 -2 -1 x2 x4 x3 x5 -3 -2 -1 x1 x2 x4 x3 x5 -3 -2 -1 x1 x2 x4 x3 x5 x6 l\m\n\o\p\q\r\s\t\u\v\w\\\\\\\\\\\\\]]]$h]ha$h]h&`#$h\\\\\\\\\\\\\\\\\\]]]]]]] ] ] ] ]]]]]]]]]]]] ]"]#]%]&](])]+],].]/]2]3]5]6]8]9];]<]T]V]]^^^^^^^׿׿׿׿׿׿׿׿׿׿׿׿׿׿׿׿׷׿׿׿h5B* \phhB* phhh@>*CJaJh0JmHnHuh@ h@0Jjh@0JUhqjhqUh@B* phD]] ] ] ] ]]]]]]]]]]]] ]"]#]%]&](])]+],].]/]2]gd2]3]5]6]8]9];]<]]^^^^^^ ^ ^ ^^^^^^^^^^ ^!^gd!^"^#^&^'^(^)^,^-^.^/^2^3^6^7^:^;^<^=^@^A^B^C^F^G^H^I^L^M^P^^*^+^.^7^>^?^D^E^H^U^\^]^b^c^f^^^^^^^^^^^^^^^^^^h@B* phhqh@mHsHh@B*CJaJphh@h@B* CJaJphh@CJaJ P^Q^T^U^X^Y^Z^[^^^_^`^a^d^e^f^g^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^,1h/ =!"#$% $$If!vh#v#v:V l t0655/ /  / Byt$$If!vh#v#v:V l t0655/ / / Byt$$If!vh#v#v:V l t0655/ / / Byt$$If!vh#v#v:V l t0655/ / / Byt$$If!vh#v#v:V l t0655/ / / Byt$$If!vh#v#v:V l t0655/ / / Byt$$If!vh#v#v:V l t0655/ / / Byt$$If!vh#v:V l t 6 065/ /  / Byt$$If!vh#v:V l t 6 065/ / / Byt$$If!vh#v:V l t 6 065/ / / Byt$$If!vh#v:V l t 6 065/ / / Byt$$If!vh#v:V l t 6 065/ / / Byt$$If!vh#v&:V l t 61065&/ /  / Be4yt$$If!vh#v&:V l t 61065&/ / / Be4yt$$If!vh#v&:V l t 61065&/ / / Be4yt$$If!vh#v:V l t 6E065/ /  / Byt$$If!vh#v:V l t 6E065/ / / Byt$$If!vh#v:V l t 6E065/ / / Byt$$If!vh#v:V l t 6E065/ / / Byt$$If!vh#v:V l t 6`065/ /  / Byt$$If!vh#v:V l t 6`065/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v#v#v:V l t06555/ / / Byt$$If!vh#v:V l2 t 6`n065/ /  / e4$$If!vh#v:V l2 t 6`n065/ / / / e4$$If!vh#v:V l2 t 6`n065/ / / e4$$If!vh#v:V l2 t 6`n065/ / / e4$$If!vh#v:V l2 t 6`n065/ / / e4$$If!vh#v:V l@ t 6`n065/ / / / e4$$If!vh#v:V l2 t 6`}065/ /  / e4$$If!vh#v:V l2 t 6`}065/ / / / e4$$If!vh#v:V l2 t 6`}065/ / / e4$$If!vh#v:V l2 t 6`}065/ / / e4$$If!vh#v:V l2 t 6`}065/ / / e4$$If!vh#v:V l@ t 6`}065/ / / e4m$$If!vh#v :V l t065 m$$If!vh#v :V l t065 m$$If!vh#v :V l t065 m$$If!vh#v :V l t065 m$$If!vh#v :V l t065 $$If!vh#v#v#v#v/ :V l t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#v#v#v#v/ :V l t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ DyK Lhttp://people.revoledu.com/kardi/tutorial/Similarity/EuclideanDistance.htmlyK http://people.revoledu.com/kardi/tutorial/Similarity/EuclideanDistance.htmlEDyK 4http://www.csgnetwork.com/squarerootsquarecalc.htmlyK hhttp://www.csgnetwork.com/squarerootsquarecalc.html$$If!vh#v#v#v#v/ :V l t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#v#v#v#v/ :V l t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#v#v#v#v/ :V l  t065555/ $$If!vh#vm#v#v#v9 :V l t0+65m5559 $$If!vh#vm#v#v#v9 :V l t0+65m5559 $$If!vh#vm#v#v#v9 :V l t0+65m5559 $$If!vh#vm#v#v#v9 :V l t0+65m5559 $$If!vh#vm#v#v#v9 :V l t0+65m5559 $$If!vh#vm#v#v#v9 :V l t0+65m5559 {$$If!vh#v#v:V l t0655{$$If!vh#v#v:V l t0655{$$If!vh#v#v:V l t0655{$$If!vh#v#v:V l t0655{$$If!vh#v#v:V l t0655{$$If!vh#v#v:V l t0655{$$If!vh#v#v:V l t0655$$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / / $$If!vh#v#v:V l t0655/ / / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / $$If!vh#v#v:V l t0655/ / / / $$If!vh#v#v:V l t0655/ / / $$If!vh#vX#v#v#vI#v:V l t065X555I5/ / / $$If!vh#vX#v#v#vI#v:V l t065X555I5/ / / $$If!vh#vX#v#v#vI#v:V l t065X555I5/ / / $$If!vh#vX#v#v#vI#v:V l t065X555I5/ / / / $$If!vh#vX#v#v#vI#v:V l t065X555I5/ / / $$If!vh#v#v#vT:V l2 t06555T/ / / $$If!vh#v#v#vT:V l2 t06555T/ / / $$If!vh#v#v#vT:V l2 t06555T/ / / / $$If!vh#v#v#vT:V l2 t06555T/ / / $$If!vh#v(#vp#v:V l3 t065(5p5/ / $$If!vh#v(#vp#v:V l3 t065(5p5/ / / $$If!vh#v(#vp#v:V l3 t065(5p5/ / / b 666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~PJ_HmH nH sH tH D`D NormalCJPJ_HaJmH sH tH DA`D Default Paragraph FontVi@V 0 Table Normal :V 44 la (k ( 0No List FVF FollowedHyperlink >*B* ph4@4 Header  _$4 @4 Footer  _$.)@!.  Page Number6U@16  Hyperlink >*B*phPK![Content_Types].xmlN0EH-J@%ǎǢ|ș$زULTB l,3;rØJB+$G]7O٭V$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3N)cbJ uV4(Tn 7_?m-ٛ{UBwznʜ"Z xJZp; {/<P;,)''KQk5qpN8KGbe Sd̛\17 pa>SR! 3K4'+rzQ TTIIvt]Kc⫲K#v5+|D~O@%\w_nN[L9KqgVhn R!y+Un;*&/HrT >>\ t=.Tġ S; Z~!P9giCڧ!# B,;X=ۻ,I2UWV9$lk=Aj;{AP79|s*Y;̠[MCۿhf]o{oY=1kyVV5E8Vk+֜\80X4D)!!?*|fv u"xA@T_q64)kڬuV7 t '%;i9s9x,ڎ-45xd8?ǘd/Y|t &LILJ`& -Gt/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 0_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!0C)theme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]  "%(,/25 (,0BFJN`z,  uwx "%(,/25 (,0BFJN`z  !"#$%&, p &&&)O R QO "'0h\^^$,8Canp~   / ? O }   ' 4 A K X e l FV`p|[_nr&*1XcnyK f#T%{%%%%%&'')'='N't()))))))*++, ,,,,$,-,3,=,B,Q,T,11$12191E1O1X1k122222334J4T4m4Z5555l\]2]!^P^^^ !"#%&'()*+-./012345679:;<=>?@ABDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`bcdefghijklmoqrstuvwxyz{|}c,XX !)!!8@22(  VB a C D"?*VB b C D"?)VB c C D"?+VB d C D"?-VB e C D"?,VB f C D"?6VB g C D"?/VB h C D"?.VB i C D"?7VB j C D"?1VB k C D"?0VB l C D"?8VB m C D"?3VB n C D"?2VB o C D"?9VB p C D"?5VB q C D"?4VB r C D"?:VB s C D"?;Jn T\ | C"?<n u C u"`\ ZB v S D@T@H` w C wC0 ` x C xC ZB y S D14x4HZB z S D1xH`B { c $D14xxVB } C D"?=n -X R;  C"?>n  C "`.X ;9 ZB  S D<-<9`  C 9,R; `  C  9R;  ZB  S D10709ZB  S D179`B  c $D1077`  C !9; !ZB  S D129ZB  S D1,2,7`B  c $D12,2VB  C D"??b  !*  #" ?@n  C ""`fX ' "ZB  S D<<(ZB  S D10%0(ZB  S D1%(`B  c $D10%%`B  c $D1!P!h  3 #"`( !* #ZB  S D1!(`B  c $D1!!ZB  S D1d!d(ZB  S D1P!P%VB  C D"?A6b 0 !7  #" ?Bn  C $"`< !p $ZB  S D0$ZB  S D10(0ZB  S D1(`B  c $D10((`B  c $D1 P h  3 %"` !7 %ZB  S D1 `B  c $D1  ZB  S D1d dZB  S D1P PKZB  S D1 $VB  C D"?Cb ,!E:  #" ?Dn  C &"`,!^7 &ZB  S D,8ZB  S D106508ZB  S D1658`B  c $D106565`B  c $D1 1<!1h  3 '"`)8 !E: 'ZB  S D1!1)8`B  c $D1!1*1ZB  S D1d!1d)8ZB  S D1P!1PY5ZB  S D1*128ZB  S D1< 1<8VB  C D"?(l\ HH   "42  Hd`  C H BB B  HdBB   d `  C d `  C l l\ HH   "42  Hd`  C H BB B  HdBB   d `  C d `  C l (2  T  C  (2  T  C  6B @  6B   T  C    T  C     l\ HH   " 42  Hd`  C  H  BB B  HdBB   d `  C  d  `  C  l  (2   T  C   (2   T  C  6B @  6B   T  C  T  C  T  C  (B  $(B  %(B  &(B  '(2   T   C   (2   T   C   6B  @  6B   6B   T  C  T  C  T  C  (2  T  C  (2   T  C ! (2  "T  C # B S  ?[\]^_`abcdefghijklmnopqrst    {|}~#GD"%L&&'.(W))V*,@  t@ Ttd04Ltd0Lt 0 Lt 0\ t t tT^pzt^zt mdt t4 t$   t  _t8h$ t h t% A t% ,A t &t p t p t ,p t p  t @ ,tt t t,@H\t4t,t,t4,t4,t$  t$  t8!Zt@ @t@ @txH@tp tb H dta$ dtc HHte@ 1 Mtd @ Mth@ m tg !@ tk@  tj ]@ tn@ tm @ tq@ <tp @ <tf 11ti 11tl 11to 11tr 11ts8!\t|XW t}at LP tDSt<ntbthottHot _Hlt185001769 _Hlt18500177088,@@99, g i l n q s       z}  '(45;<LM-.019"B"K$O$R$X$\$k$l$p$q$$$$$$@&I&''M)V)L*U************,,fh~  g i F R %,#/bg/4<>+5');=LN+-  AG k!u!!!9"B"Z"f"""4#>#$$K$$$$%%%&+&@&I&D'G'''''((M)V) **L*U************, ,",$,8,:,<,>,@,B,W,Y,,,,,,,3333333333333333333333333333333333333333333333333333333333333'( 8 /   !!""128=DIPWXY``kkvvuw/<K`E8Dovw #(1<EMOOuy S z z 7"7"9"D"D"O"P"$k% &=&@&Z&[&\&&&&&''+(1(4(m(M)W)Y)\)))))))J*J*L*e*e*f*f********************++++++ + +++++++++++++!+"+$+%+'+(+*+++++++++ ,,,,, ,",$,&,4,8,:,<,>,@,B,D,T,W,n,p,,,,,,,,,,,9Hh^`OJQJo(hHhpp^p`OJQJo(hHoh@ @ ^@ `OJQJo(hHh^`OJQJo(hHh^`OJQJo(hHoh^`OJQJo(hHh^`OJQJo(hHhPP^P`OJQJo(hHoh  ^ `OJQJo(hH,9         ~+@qK**@X ),`@```(@``8@`@UnknownG*Ax Times New Roman5Symbol3. *Cx ArialG=  jMS Mincho-3 fg?= *Cx Courier New;WingdingsA$BCambria Math"1hi'i'Fcl$ Mcl$ M$0** 3QHP $PK2!xx K-Means Clustering - ExampleAngelina Tzacheva Ramya Anoo Oh+'0p   , 8 DPX`h K-Means Clustering - ExampleAngelina Tzacheva Normal.dotm Ramya Anoo2Microsoft Office Word@@@^)@^) cl$՜.+,D՜.+,|8 px  Department of Informatics USCUpstateM* K-Means Clustering - Example Title 8@ _PID_HLINKSAl {=4http://www.csgnetwork.com/squarerootsquarecalc.html&(Lhttp://people.revoledu.com/kardi/tutorial/Similarity/EuclideanDistance.html  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"'Root Entry F@))Data C1TableoWordDocument.pSummaryInformation(DocumentSummaryInformation8CompObjr  F Microsoft Word 97-2003 Document MSWordDocWord.Document.89q