Q2

(a) Consider a set P containing the following four 2-dimensional data points.

a:(6, 6), b:(8, 8), c:(5, 9), d:(9, 5)

We can make use of the KL-Transform to find a transformed subspace containing a cluster. Let L be the total number of dimensions in the original space and K be the total number of dimensions in the projected subspace. Please illustrate the KL-transform technique with the above example when L=2 and K=1.

(b) Consider a set Q containing the following four 2-dimensional data points.

e:(5, 5), f:(9, 9), g:(3, 11), h:(11, 3)

(i) Let p = (xp, yp) be a point in P and q = (xq, yq) be a point in Q. In fact, we could express xq in a linear form involving xp such that xq = α . xp + β where α and β are 2 real numbers. Similarly, we could express yq in the same linear form involving yp. Please write down the values of α and β.

(ii) Similar to Part (a), we want to make use of the KL-Transform to find a transformed subspace containing a cluster for the set Q where L = 2 and K = 1. One “straightforward” or “naïve” method is to use the same method in Part (a) to obtain the answer. Is it possible to make use of the result in Part (a) and the result in Part (b)(i) to obtain the answer very quickly? If yes, please explain briefly and give the answer. There is no need to give a formal proof. A brief description it accepted. If no, please give an explanation briefly. In this case, derive the answer by using the method in Part (a).

(c) Consider Part (a). It is independent of Part (b). In Part (a), we know that there are 4 points.

Suppose that we have 4 additional points which are identical to the original 4 points. That is, we have the following 4 additional points. Totally, we have 8 data points.

(6, 6), (8, 8), (5, 9), (9, 5)

One “straightforward” or “naïve” method is to use the same method in Part (a) to obtain the answer. Is it possible to make use of the result in Part (a) to obtain the answer very quickly? If yes, please explain briefly and give the answer. There is no need to give a formal proof. A brief description it accepted. If no, please give an explanation briefly. In this case, derive the answer by using the method in Part (a).

(d) Consider two random variables X and Y with the following probabilistic table.

(i) Calculate the conditional entropy of H(X|Y) by using the original definition of the conditional entropy.

(ii) Calculate H(X|Y) as

where A = {1, 2, 3} and B = {1, 2, 3}.