Q.1 Explain with neat block diagram K-Means Clustering
Q.2 What are various applications of k-means clustering? Explain |
1. It is relatively efficient and fast. It computes result at O(tkn), where n is number of objects or points, k is number of clusters and t is number of iterations.
2. k-means clustering can be applied to machine learning or data mining
3. Used on acoustic data in speech understanding to convert waveforms into one of k categories (known as Vector Quantization or Image Segmentation).
4. Also used for choosing color palettes on old fashioned graphical display devices and Image Quantization. |
Q.3 Assume the following dataset is given: (2,2), (4,4), (5,5), (6,6),(9,9) (0,4), (4,0) . K-Means is run with k=3 to cluster the dataset. Moreover, Manhattan distance is used as the distance function to compute distances between centroids and objects in the dataset. Moreover, K-Mean’s initial clusters C1, C2, and C3 are as follows:
C1: {(2,2), (4,4), (6,6)}; C2: {(0,4), (4,0)}; C3: {(5,5), (9,9)}
Now K-means is run for a single iteration; what are the new clusters and what are their centroids?
Solution:-
Center c1: (4,4) Center c2: (2,2) Center c3: (7,7)
d(2,2)(4,4)=4; d(2,2)(2,2)=0; d(2,2)(7,7)=10;
d(4,4)(4,4)=0;d(4,4)(2,2)=4;d(4,4)(7,7)=6;
d(5,5)(4,4)=2;d(5,5)(2,2)=6;d(5,5)(7,7)=4;
d(6,6)(4,4)=4;d(6,6)(2,2)=8;d(6,6)(7,7)=2;
d(9,9)(4,4)=10;d(9,9)(2,2)=14;d(9,9)(7,7)=4;
d(0,4)(4,4)=4;d(0,4)(2,2)=4;d(0,4)(7,7)=10;
d(4,0)(4,4)=4;d(4,0)(2,2)=4;d(4,4)(7,7)=10;
So: c1{(4,4),(5,5),(0,4),(4,0)} or c1{(4,4),(5,5 )}
c3{(6,6),(9,9)} or c3{(6,6),(9,9)}