# Assignment: Discrete Maths

Assignment: Discrete Maths
Assignment: Discrete Maths
Based on the data in the following table,
(1) estimate a Bernoulli Naive Bayes classifer (using the add-one smoothing) (2) apply the classifier to the test document. (3) estimate a multinomial Naive Bayes classifier (using the add-one smoothing) (4) apply the classifier 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. Initialize k centers C = [c1, c2, . . . , ck];1
canStop ? false;2 while canStop = false do3
Initialize k empty clusters G = [g1, g2, . . . , gk];4
for each data point p ? D do5 cx ? NearestCenter(p, C);6 gcx .append(p);7
for each group g ? G do8 ci ? ComputeCenter(g);9
return G;10
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 final 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 clusters
cost(g1, g2, . . . , gk) = k?
i=1
cost(gi)
where cost(gi) = ?
p?gi 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 dataset.
You need to show the steps and final result of the clustering algorithm. You will show the final results by drawing a dendrogram. The dendrogram should clearly show the order in which the points are merged.
p1 p2 p3 p4 p5 p1 1.00 0.10 0.41 0.55 0.35 p2 0.10 1.00 0.64 0.47 0.98 p3 0.41 0.64 1.00 0.44 0.85 p4 0.55 0.47 0.44 1.00 0.76 p5 0.35 0.98 0.85 0.76 1.00
Q4. (10 marks)
Play several rounds of the Akinator game at http://au.akinator.com/.
(1) It is not uncommon that users may give completely or partially wrong answers during a game. Assume the site maintains a large table, where each row is about a person, and each column is a Boolean-type question, and each cell value is the correct answer (Yes or No), and that the core algorithm the site uses is a decision tree. To accommodate possible errors, lets assume the site allows up to one error in a game. That is, a person will still be a candidate if at most one question answer the user provided does not match the correct answer in the data table. Now describe how you will modify the ID3 decision tree construction algorithm to build a decision tree for the site while allowing up to one error in a game.
COMP9318 (13S2) ASSIGNMENT 2 3
Figure 1. Example
(2) Assume that you do not think the site uses decision trees as the backbone algo- rithm. What are the reason(s) to support this conjecture? You may list more than one reason. If you design some experiments and will refer to them, please include the setup and the details of the experiments (e.g., something like Figure 1)
Q5. (20 marks)
We consider the linear counting estimator that estimates the number of distinct elements in a data stream. Using this as a building block, we shall derive methods to estimate the number of distinct elements after some common set operations on several data streams.
Let S1 and S2 be two data streams 1, and C(Si) be the linear counting estimator for Si
using the same hash function h() and same length of bit array (i.e., using m bits and the bit array is denoted as C(Si).B).
(1) Prove that C(S1 ? S2) = C(S1)? C(S2). Here ? is the multiset union operator, and the ? operator on two linear counting estimators C1 and C2 returns a new estimator (with the same hash function) with a m-bit bit array where its j-th entry is the result of bitwise OR of the corresponding bits in C1 and C2, i.e., C1.B[j] | C2.B[j].
(2) Prove that C(S1?S2) 6= C(S1)?C(S2). Here ? is the multiset intersection operator, and the ? operator is defined similar to ? except that we use bitwise AND instead of bitwise OR, i.e., C1.B[j] & C2.B[j].
(3) Derive a method to estimate the number of distinct elements in S1?S2, based only on linear counting estimators.
Submission
Please write down your answers in a file named ass2.pdf. You must write down your name and student ID on the first page.
1Note that an element could appear in both S1 and S2.
4 DUE ON 23:59 1 NOV, 2013 (FRI)
You can submit your file by
give cs9318 ass2 ass2.pdf
Late Penalty. -10% for the first two days, and -30% for the following days.

Struggling to find relevant content? Order a custom essay on
Assignment: Discrete Maths
Let our experts save you the hassle
Calculate the price
Pages (550 words)
\$0.00
*Price with a welcome 15% discount applied.
Pro tip: If you want to save more money and pay the lowest price, you need to set a more extended deadline.
We know how difficult it is to be a student these days. That's why our prices are one of the most affordable on the market, and there are no hidden fees.

Instead, we offer bonuses, discounts, and free services to make your experience outstanding.
Sign up, place your order, and leave the rest to our professional paper writers in less than 2 minutes.
step 1
Fill out the order form and provide paper details. You can even attach screenshots or add additional instructions later. If something is not clear or missing, the writer will contact you for clarification.
s
Get personalized services with GPA Fix
One writer for all your papers
You can select one writer for all your papers. This option enhances the consistency in the quality of your assignments. Select your preferred writer from the list of writers who have handledf your previous assignments
Same paper from different writers
Are you ordering the same assignment for a friend? You can get the same paper from different writers. The goal is to produce 100% unique and original papers
Copy of sources used
Our homework writers will provide you with copies of sources used on your request. Just add the option when plaing your order
What our partners say about us
We appreciate every review and are always looking for ways to grow. See what other students think about our do my paper service.
Social Work and Human Services
Excellent Work
Customer 452587, November 22nd, 2021
Nursing
Always a job well done. I really appreciate the hard work.
Customer 452453, January 4th, 2021
Human Resources Management (HRM)
Thank you so much.
Customer 452701, October 11th, 2023
Nursing
Always a wonderful experience!
Customer 452453, February 23rd, 2023
Nursing
I appreciate all the hard work. Thank you!
Customer 452525, August 13th, 2021
Social Work and Human Services
Excellent Work!
Customer 452587, November 30th, 2021
IT, Web
Don did an excellent job!!!
Customer 452885, January 25th, 2023
Education
Thank you so much for your help so I do not go insane from trying to do this. I have 2 more courses to do. Probably will be using you again.
Customer 452675, November 28th, 2021
Human Resources Management (HRM)
Thanks. I am very pleased with my paper.
Customer 452701, August 1st, 2023
Human Resources Management (HRM)
Thank you so much.
Customer 452701, August 14th, 2023
Nursing
Thank you!
Customer 452707, April 3rd, 2022
DISCUSSION D SCIENCE 210
GREAT
Customer 452813, June 28th, 2022