Document Preview:

COMP9318 (13S2) ASSIGNMENT 2 DUE ON 23:59 1 NOV, 2013 (FRI) Q1. (25 marks) Based on the data in the following table, (1) estimate a Bernoulli Naive Bayes classifer (using the add-one smoothing) (2) apply the classier to the test document. (3) estimate a multinomial Naive Bayes classier (using the add-one smoothing) (4) apply the classier to the test document You do not need to estimate parameters that you don’t need for classifying the test document. docID words in document class = China? training set 1 Taipei Taiwan Yes 2 Macao Taiwan Shanghai Yes 3 Japan Sapporo No 4 Sapporo Osaka Taiwan No test set 5 Taiwan Taiwan Taiwan Sapporo Bangkok ? Q2. (20 marks) Algorithm 1: k-means(D, k) Data: D is a dataset of n d-dimensional points; k is the number of clusters. 1 Initialize k centers C = [c1; c2; : : : ; ck]; 2 canStop false; 3 while canStop = false do 4 Initialize k empty clusters G = [g1; g2; : : : ; gk]; 5 for each data point p 2 D do 6 cx NearestCenter(p;C); gcx 7 :append(p); 8 for each group g 2 G do 9 ci ComputeCenter(g); 10 return G; 1
2 DUE ON 23:59 1 NOV, 2013 (FRI) Consider the (slightly incomplete) k-means clustering algorithm as depicted in Algo- rithm 1. (1) Assume that the stopping criterion is till the algorithm converges to the nal k clusters. Can you insert several lines of pseudo-code after Line 8 of the algorithm to implement this logic. (2) The cost of k clusterscost(g1; g2; : : : ; gk) =Xk i=1 cost(gi) where cost(gi) = Pp2gi dist(p; ci). dist() is the Euclidean distance. Now show that the cost of k clusters as evaluated at the end of each iteration (i.e., after Line 11 in the current algorithm) never increases. (You may assume d = 2) (3) Prove that the cost of clusters obtained by k-means algorithm always converges to a local minima. (Hint: you can make use of the previous conclusion even if you have not proved it). Q3. (25 marks) Consider the given similarity matrix. You are asked to perform group average hierar- chical clustering on this…