algorithm but definitely different.

Step $1.$ Randomly select $k$ objects as initial representative objects.

Step $2.$ For each of non$-$representative $($unselected$)$ objects, compute the distances to $k$

representative $($selected$)$ objects and assign to the closest one to obtain a clustering

result.

Step $3.$ Find a new representative object of each cluster, which minimizes the sum of the

distances to other objects in its cluster. Update the current representative object in

each cluster by replacing with the new one.

Step $4.$ If the newly updated representative objects are the same with the previous ones,

then stop. Otherwise, go to Step $1.$

$(1)(3$pts$)$ What would be the strength$($s$)$ of this algorithm over the original $k-$means

algorithm? Explain why.

$(2)(3$pts$)$ What would be the strength$($s$)$ of this algorithm over the PAM $($Partitioning

Around Medoids$)$ algorithm? Explain why.

$(3$pts$)$ Suppose that we perform PCA using the five$-$dimensional dataset shown below.

$\backslash$table$[[$X$1,$X$2,$X$3,$X$4,$X$5],[2,4,0\mathrm{.}4,0\mathrm{.}2,0\mathrm{.}02],[5,10,1\mathrm{.}0,0\mathrm{.}5,0\mathrm{.}05],[1,2,0\mathrm{.}2,0\mathrm{.}1,0\mathrm{.}01],[6,12,1\mathrm{.}2,0\mathrm{.}6,0\mathrm{.}06],[8,16,1\mathrm{.}6,0\mathrm{.}8,0\mathrm{.}08],[3,6,0\mathrm{.}6,0\mathrm{.}3,0\mathrm{.}03],[4,8,0\mathrm{.}8,0\mathrm{.}4,0\mathrm{.}04],[7,14,1\mathrm{.}4,0\mathrm{.}7,0\mathrm{.}07],[9,18,1\mathrm{.}8,0\mathrm{.}9,0\mathrm{.}09],[10,20,2\mathrm{.}0,1\mathrm{.}0,0\mathrm{.}10]]$

How much variability of the dataset can be explained by the first principal component? Explain why.

$(6$pts$)$ Consider the similarity matrix of four data points $(A,B,C,D)$ shown below.

$(1)(3$pts$)$ Find the optimal clustering result that maximizes the following quantity,

$Z=\frac{{\displaystyle \underset{k=1}{\overset{3}{}}}}{b}ar({\displaystyle \underset{ijin{C}_k}{\overset{?}{}}}s(i,j)),$

where $s(i,j)$ is the similarity between object i and $j,$ and $C_k$ indicates the $k$ th cluster.

Notice that the number of clusters is $3.$ If there are multiple optimal results, find them all.

$(2)(3$pts$)$ Covert similarities to distances and cluster the four points using complete linkage.

Draw a dendrogram. $(5$pts$)$ Answer the following questions using the datasets in the figure shown below. Note that each dataset contains $1,000$ items and $10,000$ transactions. Dark cells indicate ones $($presence of items$)$ and white cells indicate zeros $($absence of items$).$ We will apply the apriori algorithm to extract frequent itemsets with minsup$=10\%($i$.$e$.,$ itemsets must be contained in at least $1,000$ transactions.$)$

$($c$)(1)($Ipt$)$ Which dataset$($s$)$ will produce the most number of frequent itemsets? Explain why.

$(2)($lpt$)$ Which dataset$($s$)$ will produce the fewest number of frequent itemsets? Explain why.

$(3)(1$pt$)$ Which dataset$($s$)$ will produce the longest frequent itemset? Explain why. $(e)$

$(4)($lpt$)$ Which dataset$($s$)$ will prodyce the frequent itemset with highest support? Explain ${|}_{{?}_{?}}b$

why.

$(5)(1$pt$)$ Which dataset$($s$)$ will pooduce frequent itemsets with wide$-$varying support levels?

Explain why.