CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Additional Tutorial Exercises Suggested Solutions
Important Notes:
• This set of additional exercises aims to supplement the exercises/questions in Tutorials,
Assignments, and Mid-Term Test as well as the examples in the lecture slides.
• Please do not take this set of exercises as hints for the final examination. In particular,
types of questions and topics not appeared here may still appear in the final paper.
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 1
Consider building a decision tree for the following data set:
(𝑥1 , 𝑥2 ) label
(4, 18) Yes
(13, 95) No
(24, 26) Yes
(25, 73) No
(44, 41) No
(53, 19) Yes
(66, 87) No
(77, 39) No
(80, 9) No
(94, 79) No
(a) Suppose we have decided to split on attribute 𝑥1 based on Gini index. Furthermore, we are
restricted to choose among the three splits, “𝑥1 ≤ 4”, “𝑥1 ≤ 24”, “𝑥1 ≤ 53”. Which one is
the best? Show your calculations.
The weighted sum of Gini index for the split “𝑥1 ≤ 4”:
1 9 2 2 7 2
(1 − 1 − 0) − (1 − ( ) − ( ) ) ≈ 0.311
10 10 9 9
The weighted sum of Gini index for the split “𝑥1 ≤ 24”:
3 2 2 1 2 7 1 2 6 2
(1 − ( ) − ( ) ) − (1 − ( ) − ( ) ) ≈ 0.305
10 3 3 10 7 7
The weighted sum of Gini index for the split “𝑥1 ≤ 53”:
6 3 2 3 2 4
(1 − ( ) − ( ) ) − (1 − 0 − 1) ≈ 0.3
10 6 6 10
So, the best split is “𝑥1 ≤ 53”.
(b) Suppose your decision tree wrongly classifies 78 out of 1531 yes-instances as no-instances
and 21 out of 967 no-instances as yes-instances. What is the precision and recall of your
decision tree?
1531−78 1531−78
Precision = (1531−78)+21 ≈ 0.986 Recall = ≈ 0.949
1531
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 2
Consider the following pseudocode for linear regression:
1 Initialize 𝑡 = 0
2 Initialize 𝒘0 to some random value
3 Repeat
4 𝒘𝑡+1 ← 𝒘𝑡 − 𝛼∇𝐽(𝒘𝑡 )
5 𝑡 ←𝑡+1
6 Until |∇𝐽(𝒘𝑡 )| ≤ 𝛿
Here, 𝒘 = (𝑤0 , … , 𝑤𝐷 )T , 𝛼 is the learning rate, and 𝛿 is some small positive constant. Suppose
𝜕𝐽
𝐽(𝒘) is the mean squared error, compute the partial derivatives 𝜕𝑤 for 𝑗 = 0, … , 𝐷. Then
𝑡,𝑗
rewrite the pseudocode for line 4 in the form:
for 𝑗 = 0, … , 𝐷:
𝑤𝑡+1,𝑗 ←…
to show how 𝑤𝑡+1,𝑗 is computed for each 𝑗.
The mean squared error is
1
T (𝑖) 2
𝐽(𝒘𝑡 ) = 𝑁 ∑𝑁
𝑖=1(𝒘𝑡 𝒙 − 𝑡 (𝑖) ) .
𝜕𝐽 2 T (𝑖) (𝑖)
So, = 𝑁 ∑𝑁
𝑖=1(𝒘𝑡 𝒙 − 𝑡 (𝑖) )𝑥𝑗 for 𝑗 = 0, … , 𝐷
𝜕𝑤𝑡,𝑗
Hence line 4 can be rewritten as:
for 𝑗 = 0, … , 𝐷:
2 T (𝑖) (𝑖)
𝑤𝑡+1,𝑗 ← 𝑤𝑡,𝑗 − 𝛼 𝑁 ∑𝑁
𝑖=1(𝒘𝑡 𝒙 − 𝑡 (𝑖) )𝑥𝑗
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 3
Consider the following pseudocode for linear regression
1 Initialize 𝑡 = 0
2 Initialize 𝒘 to some random value
3 Repeat
4 𝒘 ← 𝒘 − 𝛼∇𝐽(𝒘)
5 Until |∇𝐽(𝒘)| ≤ 𝛿
Here, 𝛼 is the learning rate and 𝛿 is some small positive constant.
(a) Write the kernelized version of lines 2 and 4 with 𝝓(∙) and 𝐾(∙,∙) representing the feature
map and kernel function respectively.
With feature mapping 𝝓(∙), 𝒘 is a linear combination of 𝝓(𝒙(𝑖) )s. I.e., 𝒘 = ∑𝑁 (𝑖)
𝑖=1 𝛽𝑖 𝝓(𝒙 ).
Line 2 can be implemented by randomly choosing the 𝛽𝑖 s.
In linear regression, the output 𝑦 (𝑖) can be computed using 𝐾(∙,∙) as:
𝑦 (𝑖) = 𝒘T 𝝓(𝒙(𝑖) )
(𝑘) T
= ∑𝑁
𝑘=1 𝛽𝑘 𝝓(𝒙 ) 𝝓(𝒙(𝑖) )
(𝑘) (𝑖)
= ∑𝑁
𝑘=1 𝛽𝑘 𝐾(𝒙 ,𝒙 )
1 2 1 (𝑖) 2
(𝑖) (𝑖) (𝑖)
Then 𝐽(𝑤) = 𝑁 ∑𝑁 T 𝑁
𝑖=1(𝒘 𝝓(𝒙 ) − 𝑡 ) = 𝑁 ∑𝑖=1(𝑦𝑡 − 𝑡 ) .
𝜕𝐽 2 (𝑖)
is the 𝑗th entry of the vector 𝑁 ∑𝑁 (𝑖) (𝑖)
𝑖=1(𝑦𝑡 − 𝑡 )𝝓(𝒙 )
𝜕𝑤𝑗
2 (𝑖)
(𝑖) (𝑖)
and ∇𝐽 = 𝑁 ∑𝑁
𝑖=1(𝑦𝑡 − 𝑡 )𝝓(𝒙 ).
2𝛼 T (𝑖)
So, 𝒘 ← 𝒘 − ∑𝑁
𝑖=1(𝒘 𝒙 − 𝑡 (𝑖) )𝝓(𝒙(𝑖) )
𝑁
(𝑖) 2𝛼 (𝑖) (𝑖) (𝑖)
← ∑𝑁
𝑖=1 𝛽𝑖 𝝓(𝒙 ) − ∑𝑁
𝑖=1(𝑦𝑡 − 𝑡 )𝝓(𝒙 )
𝑁
2𝛼 (𝑖)
I.e., 𝒘 = ∑𝑁
𝑖=1 (𝛽𝑖 − (𝑦𝑡 − 𝑡 (𝑖) )) 𝝓(𝒙(𝑖) ) which can be computed by updating the 𝛽𝑖 s.
𝑁
So, line 4 can be implemented as:
for 𝑖 = 1, … , 𝑁:
2𝛼 (𝑖)
𝛽𝑖 ← 𝛽𝑖 − (𝑦𝑡 − 𝑡 (𝑖) ).
𝑁
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
(b) Suppose we have an artificial data set of (𝑥, 𝑦)-pairs generated from a degree 3 polynomial
with some added Gaussian noise, i.e., 𝑦 = 𝑤0 + 𝑤1 𝑥 + 𝑤2 𝑥 2 + 𝑤3 𝑥 3 + 𝜀 where
𝜀~𝒩(0, 𝜎 2 ). Moreover, we apply linear regression with two feature mappings, 𝝓𝐴 (𝑥) =
(1, 𝑥, 𝑥 2 ) and 𝝓𝐵 (𝑥) = (1, 𝑥, 𝑥 2 , 𝑥 3 , 𝑥 4 ), on this data set. Which feature mapping is more
likely to give a smaller testing error?
Assuming there are sufficient training data, 𝝓𝐵 (𝑥) is more likely to give smaller test error
since it has more than enough model capacity to model the degree 3 polynomial. On the
other hand, 𝝓𝐴 (𝑥) does not have enough model capacity whether there is sufficient training
data or not.
Question 4
Consider an 𝑁 × 𝐷 data matrix 𝑨 where the 𝑖 th row is the vector 𝒙(𝑖)T. So, there are 𝑁 vectors in
1 (𝑖)
a 𝐷-dimensional space. Assume the vectors are centered at the origin, i.e., 𝝁 = 𝑁 ∑𝑁
𝑖=1 𝒙 = 𝟎.
Consider a 𝐷-dimensional unit-length vector 𝒘 = 𝛼1 𝒒1 + ⋯ + 𝛼𝐷 𝒒𝐷 where 𝒒1 , … , 𝒒𝐷 are the
eigenvectors of 𝑴 = 𝑨T 𝑨 with corresponding eigenvalues 𝜆1 , … , 𝜆𝐷 respectively. Find the
variance of the projections of the 𝑁 vectors onto 𝒘. Express your answer in terms of 𝜆𝑖 s and
𝛼𝑖 s.
Let 𝑧 (𝑖) = 𝒙(𝑖)T 𝒘. We want to find the variance of {𝑧 (𝑖) }s.
First, the mean of 𝑧 (𝑖) s is zero:
(𝑖)
∑𝑁 𝑁
𝑖=1 𝑧𝑗 = ∑𝑖=1 𝒙
(𝑖)T
𝒘
(𝑖)T
= (∑𝑁𝑖=1 𝒙 )𝒘
T
=𝟎 𝒘
=0
Therefore, the variance of {𝑧 (𝑖) }s is:
1 2 1
T (𝑖) (𝑖)T
∑𝑁 (𝑖) 𝑁
𝑖=1(𝑧 ) = ∑𝑖=1(𝒘 𝒙 )(𝒙 𝒘)
𝑁 𝑁
1 (𝑖) (𝑖)T
= 𝑁 𝒘T (∑𝑵
𝒊=𝟏 𝒙 𝒙 )𝒘
1
= 𝑁 𝒘T 𝑨T 𝑨𝒘
1
= 𝑁 (𝛼1 𝒒1 + ⋯ + 𝛼𝐷 𝒒𝐷 )(𝛼1 𝜆1 𝒒1 + ⋯ + 𝛼1 𝜆𝐷 𝒒𝐷 )
1
= 𝑁 (𝛼12 + ⋯ + 𝛼𝐷2 )
Remark: This is similar to questions 3 and 4 of Tutorial 9. Please also see p34 of Lec9.
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 5
Consider the following points on a straight line:
𝑥1 = 0.0, 𝑥2 = 1.0, 𝑥3 = 2.1, 𝑥4 = 3.3, 𝑥5 = 4.6, 𝑥6 = 6.0, 𝑥7 = 7.5, 𝑥8 = 9.1
(a) Run the single-linkage clustering algorithm and show the hierarchy of clusters.
First, each point is a cluster of itself.
Then we merge {𝑥1 } and {𝑥2 } into the cluster 𝑆1 = {𝑥1 , 𝑥2 }.
Then we merge 𝑆1 and {𝑥3 } into the cluster 𝑆2 = {𝑥1 , 𝑥2 , 𝑥3 }.
Then we merge 𝑆2 and {𝑥4 } into the cluster 𝑆3 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 }.
Then we merge 𝑆3 and {𝑥5 } into the cluster 𝑆4 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 }.
Then we merge 𝑆4 and {𝑥6 } into the cluster 𝑆5 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 }.
Then we merge 𝑆5 and {𝑥7 } into the cluster 𝑆6 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 }.
Then we merge 𝑆6 and {𝑥8 } into the cluster 𝑆7 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 , 𝑥8 }.
The hierarchy of clusters is as follows:
𝑆7
𝑆6
𝑆5
𝑆4
𝑆3
𝑆2
𝑆1
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7 𝑥8
(b) Run the complete-linkage clustering algorithm and show the hierarchy of clusters.
First, each point is a cluster of itself.
Then we merge {𝑥1 } and {𝑥2 } into the cluster 𝑆1 = {𝑥1 , 𝑥2 }.
Then we merge {𝑥3 } and {𝑥4 } into the cluster 𝑆2 = {𝑥3 , 𝑥4 }.
Then we merge {𝑥5 } and {𝑥6 } into the cluster 𝑆3 = {𝑥5 , 𝑥6 }.
Then we merge {𝑥7 } and {𝑥8 } into the cluster 𝑆4 = {𝑥7 , 𝑥8 }.
Then we merge 𝑆1 and 𝑆2 into the cluster 𝑆5 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 }.
Then we merge 𝑆3 and 𝑆4 into the cluster 𝑆6 = {𝑥5 , 𝑥6 , 𝑥7 , 𝑥8 }.
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Then we merge 𝑆5 and 𝑆6 into the cluster 𝑆7 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 , 𝑥8 }.
.
The hierarchy of clusters is as follows:
𝑆7
𝑆5 𝑆6
𝑆1 𝑆2 𝑆3 𝑆4
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7 𝑥8
Question 6
Consider running DBSCAN with 𝜀 = 1.3 and minpts=3 on the point set in the previous question.
(a) Which are the core points, border points and noise points?
Core points: 𝑥2 , 𝑥3 , 𝑥4 .
Border points: 𝑥1 , 𝑥5 .
Noise points: 𝑥6 , 𝑥7 , 𝑥8
(b) Which points are density-reachable from 𝑥2 ?
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , and 𝑥5 are density-reachable from 𝑥2 .
(c) Show all the density-based cluster(s).
There is only one density-based cluster: {𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 }.
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 7
Consider the following distance matrix for a set of five points:
𝑑𝑖𝑠𝑡() A B C D E
A 0 10 15 12 7
B 0 8 14 13
C 0 7 15
D 0 10
E 0
Note that the distance measure represented by the matrix is symmetric, i.e., 𝑑𝑖𝑠𝑡(𝑥, 𝑦) =
𝑑𝑖𝑠𝑡(𝑦, 𝑥). So, we only show the upper triangular part of the matrix.
Run the k-medoids algorithm starting with the partition {{A, B, C}, {D, E}}. When choosing
the medoid, ties are broken by alphabetical order. Show the final clusters.
1st iteration:
Medoid of {𝐴, 𝐵, 𝐶} is 𝐵, medoid of {𝐷, 𝐸} is 𝐷.
Cluster of 𝐵 is {𝐴, 𝐵}, cluster of 𝐷 is {𝐶, 𝐷, 𝐸}.
2nd iteration:
Medoid of {𝐴, 𝐵} is 𝐴, medoid of {𝐶, 𝐷, 𝐸} is 𝐷.
Cluster of 𝐴 is {𝐴, 𝐵, 𝐸 }, cluster of 𝐷 is {𝐶, 𝐷}.
3rd iteration:
Medoid of {𝐴, 𝐵, 𝐸 } is 𝐴, medoid of {𝐶, 𝐷} is 𝐶.
Cluster of 𝐴 is {𝐴, 𝐸}, cluster of 𝐶 is {𝐵, 𝐶, 𝐷}.
4th iteration:
Medoid of {𝐴, 𝐸 } is 𝐴, medoid of {𝐵, 𝐶, 𝐷} is 𝐶.
Cluster of 𝐴 is {𝐴, 𝐸}, cluster of 𝐶 is {𝐵, 𝐶, 𝐷}.
The clustering remains the same. So, the algorithm stops and the final clusters are:
{𝐴, 𝐸} and {𝐵, 𝐶, 𝐷}
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 8
Consider running Apriori on a data set. Suppose we have computed 𝐹3 , the set of all frequent 3-
itemsets:
ABC, ABD, ABE, ACD, ACE, BCD, BCE
(Note: To simplify the notation, we denote by, for example, “ABC” the itemset “{A. B, C}.”)
Follow the Apriori algorithm to find all the candidate 4-itemsets, 𝐶4 .
ABCD, ABCE, ABDE, ACDE, BCDE
Question 9
Consider running Apriori on a data set. Suppose that when generating rules from the frequent
itemset ABCD, we have determined that the rule AB→CD does not meet the minconf
requirement. Based on this information, which other rules also do not meet the minconf
requirement, and which other rules must also meet the minconf requirement?
A→ BCD and B→ ACD do not meet the minconf requirement
and
AB→C and AB→D meet the minconf requirement
Question 10
Suppose in a data set of 1000 transactions, the support count of itemsets ABCD, AB and CD are
15, 180 and 100 respectively. Compute the lift of the rule AB→ 𝐶𝐷. Are the itemsets, AB and
CD, positively or negatively correlated?
Support ratio of ABCD, AB and CD are 0.015, 0.18 and 0.1 respectively. The lift of the rule
0.015
AB→ 𝐶𝐷 is ≈ 0.833.
0.18×0.1
Since it is <1, AB and CD are negatively correlated
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
Question 11
7
Consider running the Scaled PageRank algorithm with scaling factor 𝑠 = 8 on the following
graph:
̃ for this Scaled PageRank update.
(a) Find the transition matrix 𝑴
0 0 0 1 1 1
1⁄2 0 0 0 0 0
0 0 0 0 0
𝑴 = 1⁄2
0 1⁄2 0 0 0 0
0 1⁄2 1⁄2 0 0 0
[ 0 0 1⁄2 0 0 0]
1 1 1 1 1 1
1 1 1 1 1 1
7 1 1 1 1 1 1 1
̃ = 𝑴+
𝑴
8 48 1 1 1 1 1 1
1 1 1 1 1 1
[1 1 1 1 1 1]
0 0 0 42 42 42 1 1 1 1 1 1
21 0 0 0 0 0 1 1 1 1 1 1
1 21 0 0 0 0 0 1 1 1 1 1 1 1
= 48 + 48
0 21 0 0 0 0 1 1 1 1 1 1
0 21 21 0 0 0 1 1 1 1 1 1
[0 0 21 0 0 0 ] [ 1 1 1 1 1 1]
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
1 1 1 43 43 43
22 1 1 1 1 1
1 22 1 1 1 1 1
= 48
1 22 1 1 1 1
1 22 22 1 1 1
[1 1 22 1 1 1]
(b) Check if the values indicated in the figure form an equilibrium set of PageRank values for
this Scaled PageRank update.
1 1 1 1 1 1 T
The initial PageRank vector specified in the figure is (4 , 8 , 8 , 8 , 4 , 8) .
Consider the PageRank of node A. The initial PageRank is 1/4.
After one step of this Scaled PageRank update, the new PageRank of A is:
1 1 1 1 1 1 1 22 1
(1 ∙ 4 + 1 ∙ 8 + 1 ∙ 8 + 43 ∙ 8 + 43 ∙ 4 + 43 ∙ 8) = 48 ≠ 4
48
Therefore, the values indicated in the figure do not form an equilibrium set of PageRank
values.
Question 12
Consider the following graph:
A B C
Let 𝑴 be the transition matrix for the Basic PageRank Update.
(a) Compute 𝑴2 and 𝑴3
0 1⁄2 0
𝑴 = [1 0 1],
0 1⁄2 0
0 1⁄2 0 0 1⁄2 0 1⁄2 0 1⁄2
𝑴2 = [1 0 1] [1 0 1] = [ 0 1 0 ]
0 1⁄2 0 0 1⁄2 0 1⁄2 0 1⁄2
CMSC5724 Data Mining and Knowledge Discovery 8 December 2025
1⁄2 0 1⁄2 0 1⁄2 0 0 1⁄2 0
3
𝑴 =[ 0 1 0 ] [1 0 1 ] = [1 0 1]
1⁄2 0 1⁄2 0 1⁄2 0 0 1⁄2 0
(b) Suppose we apply the Basic PageRank Update starting with the vector 𝒓 = (1,0,0)T.
What vector will be obtained after 100 such update steps?
From above, 𝑴3 = 𝑴. Therefore, 𝑴𝟐 = 𝑴4 = ⋯ = 𝑴100
1⁄2 0 1⁄2 1 1⁄2
100 𝟐
The vector is 𝑴 𝒓 = 𝑴 𝒓 = [ 0 1 0 ] [0] = [ 0 ]
1⁄2 0 1⁄2 0 1⁄2