sheet uco points Explain the following aspects of the K-means flat clustering algorithm [2 points]: 1. What do we need to know about our dataset before using the algorithm? 2. What is the input and the output of the algorithm? 3. What are the two steps that take place in every epoch? 4. How do we decide in which epoch to stop the algorithm? 3. RfiA.$$i^mn^ , r«c**n|Htin} centra*. H . kentcVi^s converged. Given the points O, and the seeds □, run the K-means algorithm for three epochs. Draw the state of the algorithm at the beginning and after every epoch; no computation should be necessary. What is the output of the algorithm? [2 points] ■—c )— k * c J k \ A k V sn n ^_r □ ft V A / )— rv \ J C ft \ y A \ \ \ A \ ( c J J 1 A ] ( ft L) / \ / y b N ,c f K. ' / H N \ 1 / 9 i, ) f r r <\ be Perform a hierarchical clustering of the above dataset into three classes using the single-link hierarchical agglomerative clustering algorithm, and draw the resulting dendrogram. [1 point] Is the output the same as the output of the K-means flat hierarchical clustering algorithm above? [1 point] yes,** 'is- Write your solution only on this side of the sheet! sheet E uco points Consider the following collection of four documents df. • d\: BREAKTHROUGH DRUG FOR HIV • NEW HIV DRUG • dy. NEW APPROACH FOR TREATMENT OF HIV • d±: NEW HOPES FOR HIV PATIENTS Produce a list of (term, document ID) tuples [1 point], sort this list in lexicographical order [1 point], and use the sorted list to construct an inverted index [1 point]. Write down each step. Describe how you would produce this index using the MapReduce distributed framework [2 points]. ( taeikfchrtujh j), ( drug l ^, ( \ox, l) , ( K\v, l) ( Uyfr**^, 3>, ( bi*AkMirai^b('Ol (Mr^,l)) ()l(v\twtH){ (o\t$)} (patients, *0( f or -> 1 -> 3 -f H vie —? z-i 3 -f 4 0^ 3 E«cla y«vfSeir woulA process dociAWBVlt ip) list. r^vge »| terms fro face Write your solution only on this side of the sheet! Compute an unbiased estimate of a text retrieval system's precision, recall, and the Fi measure on the ^first fiv^>esults [2 points], and the precision at 40% recall [2 points] given the following lists of results for queries q\, and c\2, where R is a relevant result, and N is a non-relevant result: • Results for c\\ : RNNRRNR (10 relevant results for c\\ exist in the collection.) • Results for qi : NRNRRRRN (5 relevant results for qi exist in the collection.) Ihe f»r?t five r^lts for ^enj ^ : RMNKR ojz : M N fc. R, ? «-2- = 10 \ 2-3|r -3/10 3*5" + 3110 9!zr 9/10 2 ■t — r ? -4- F _ 2-3|s-3lS" 3 li r 3I5" +3/S" J " 10 iV»iS "(5 ^>5Ji tie 50lntv»t K ^>lA couU use \ri\cro \vv yuv cmy nitons The rentes »UV\ «(0% refill {or <|Ker\j ^ : RNN fcR.N R, Write your solution only on this side of the sheet! sheet c j H ,1 rr ,n r, T-| r, ,n r. ,1 r, ,n r. ,n points Given a directed graph G that represents three Web pages V(G) = {a,b,c}, and the links E(G) = {(fr,fl), (c,a), (c,b), (b,c)} between these three pages, draw G [1 point] and produce the adjacency matrix (also known as the link matrix) A [1 point], and the Markov transition matrix P [2 points]. Describe the intuition behind the PageRank algorithm [1 point]. Compute the PageRank of the pages a, b, and c using a single iteration of the PageRank algorithm [2 points]. Describe what we mean, when we call a page a fowfr, or an authority [1 point]. Compute the hub, and authority scores of the pages a, b, and c [2 points]. F- * 6 0 0 1 0 1 1 1 0 " 1 1 1 'Ml 113 1)3 1 0 1 0 Ml 112 11* _ 1 1 0 . i JM7. 112 1/2 < The ?age1U*vk *W)*rMfc\ c^Mf^es the fr*UWiil^j 1 VHjpatlrietu*\ flVlAtUt'»tvj s)5 a. \K/et |>^e Waa/fc VHAHjj Uv\>5 ^ink to . "& 0 * 7 f 0 1 o r & 0 1 0 4 l-l 0 0 4 I- 0 Z .1 1 0JL0 1 0^ L * 1 t A. r 0 1 11 ra ^ 01 r A A - 0 0 /i • 4 0 1 l- a, A-AT - 0 1 2 2. 1 1 110 18 1 Write your solution only on this side of the sheet! You maintain a text retrieval system. Let E\ denote the complete set of documents in the index of your system and let E2 denote the complete set of documents in the index of a competing system. Suppose the indices of both systems are independent uniform random samples without replacement from the World Wide Web N. The size of £1 is |£i | = 110 trillion (110 • 1012) documents. You take a uniform random subsample of documents without replacement from E\ and you submit each document to the competing system. This gives you an estimate x = 0.2 of the conditional probability P(d G £2 I d G E\),d G N. You repeat the same procedure with E2, obtaining an estimate y — 0.4 of the conditional probability P(d G E\ \ d G £2),^ G N. Assume the estimates x,y are the true probabilities. What is the size \E2 \ of the competing system's index? [3 points] The grey parrot, native to equatorial Africa, is categorized as an endangered species by the International Union for Conservation of Nature (IUCN). Suppose you take a uniform random sample M without replacement of size |M| = 8 000 from the grey parrot population N and mark the sampled animals. After returning the marked animals back into the population, you take a second independent uniform random sample T without replacement of the same size \T\ = 8 000 from the population. The number of marked animals R = M fl T in the second sample is \ R\ = 10. What is the most likely size \ N\ of the grey parrot population? [2 points] rUeE.,)* i^I/imi Write your solution only on this side of the sheet!