The hierarchical agglomerative clustering algorithm is to cluster data from bottom to

up. Here is the pseudo-code for it. Please implement hierarchical agglomerative clustering

algorithm on 2dimensional numerical data by C++, which should be fairly easy to derive

from this.

SIMPLEHAC(d1, . . . , dN)

for o 1 to N

for p 1 to N

C[o][p] SIM(do, dp)

end

I[o] 1 (keeps track of active clusters)

end

A [] (assembles clustering as a sequence of merges)

for k 1 to N 1

argmax{:imI[i]=1I[m]=1} C[i][m]

A.APPEND() (store merge)

for j 1 to N

C[i][j] SIM(i,m, j)

C[j][i] SIM(i,m, j)

End

I[m] 0 (deactivate cluster)

end

return A

Use your code to cluster the following 12 points (with (x, y) representing locations) into clusters

A1(2, 2) A2(3.01, 2) A3(4.02, 2) A4(5.03, 2) A5(6.04, 2) A6(7.05, 2) A7(2, 3.5) A8(3.01,

3.5), A9(4.02, 3.5), A10(5.03, 3.5), A11(6.04, 3.5) and A12 (7.05, 3.5). The distance (similarity)

function between two points a=(x1, y1) and b=(x2, y2) is defined as L2-norm: (a, b) = ((x2

x1)^2 + (y2 y1)^2)^1/2 . Please use single linkage, complete linkage, and centroid linkage to

generate three different dendrograms. In the code, SIM(i,m, j) needs to be altered based on the

selected cluster distance metric (single linkage, complete linkage, and centroid). Based on the

generated dendrogram, show the clustering result of two clusters and six clusters in single

linkage, complete linkage, and centroid linkage.