Unsupervised Learning Clustering KMean and Hirarchical.pptx

Unsupervised Learning

1. Clustering

2. Clustering is the process of grouping a set of patterns. Representations or descriptions of the clusters formed are used in decision making classification is one of the popular decision-making paradigms used.

3. Clustering Types Clustering algorithms which typically group sets of unlabelled patterns called unsupervised classification . Algorithms which cluster labelled patterns called: supervised clustering The process of clustering is carried out so that patterns in the same cluster are similar whereas different clusters are dissimilar

4. Inter-cluster and intra-cluster The Euclidean distance between any two points belonging to the same cluster is smaller than that between any two points belonging to different clusters.

5. The distance matrix All sub-matrices satisfy the condition that the value of any entry in the sub-matrix is less than 5 units.

6. In the previous example, the intra-cluster distance is less than 5 units and the distance between two points belonging to two different clusters ( inter-cluster distance ) is greater than 5 units .

7. Applications Data reduction Example: let Computing the clusters using the previous technique yields:

8. Continue So These reduced data can be used for the nearest neighbor algorithm So, there is a reduction in both space and time.

9. Data re- organisation Can eliminate Similar rows

10. Removing outliers clustering can identify outliers. The outlier will show up as an element of a singleton cluster. This forms the basis for a variety of applications like automatic auditing of records in a database and detection of intrusions .

11. K-means algorithm

12. Example Pattern Feature 1 Feature 2 p1 1.0 1.0 p2 1.5 2.0 p3 3.0 4.0 p4 5.0 7.0 p5 3.5 5.0 p6 4.5 5.0 p7 3.5 4.5 Cluster the following data into two clusters using pattern p1 and p4 as cluster centers :

13. Step 1   Individual Mean Vector ( centroid ) Group 1 1 (1.0, 1.0) Group 2 4 (5.0, 7.0) The initial means are. 

14. The assigned patterns   Cluster 1 Cluster 2 Step Individual Mean Vector ( centroid ) Individual Mean Vector (centroid) 1 1 (1.0, 1.0) 4 (5.0, 7.0) 2 1, 2 (1.2, 1.5) 4 (5.0, 7.0) 3 1, 2, 3 (1.8, 2.3) 4 (5.0, 7.0) 4 1, 2, 3 (1.8, 2.3) 4, 5 (4.2, 6.0) 5 1, 2, 3 (1.8, 2.3) 4, 5, 6 (4.3, 5.7) 6 1, 2, 3 (1.8, 2.3) 4, 5, 6, 7 (4.1, 5.4)

15. The new means   Individual Mean Vector (centroid) Cluster 1 1, 2, 3 (1.8, 2.3) Cluster 2 4, 5, 6, 7 (4.1, 5.4)

16. The distances Individual Distance to mean ( centroid ) of Cluster 1 Distance to mean ( centroid ) of Cluster 2 1 1.5 5.4 2 0.4 4.3 3 2.1 1.8 4 5.7 1.8 5 3.2 0.7 6 3.8 0.6 7 2.8 1.1

17. Step 5, the final means individual 3 is nearer to the mean of the opposite cluster (Cluster 2). A new iteration is required. So, add pattern 3 to cluster 2 The final result is:   Individual Mean Vector (centroid) Cluster 1 1, 2 (1.3, 1.5) Cluster 2 3, 4, 5, 6, 7 (3.9, 5.1)

18. Finally… Putting all together

19. An Application: Handwritten Digit Recognition There are ten classes corresponding to the handwritten digits ‘‘0’’ to ‘‘9’’. The data set consists of 6670 training patterns and 3333 test patterns. The nearest neighbour algorithm (NN), the kNN and the mkNN algorithms have been used on this data set.

20. An Application: Handwritten Digit Recognition The k-means algorithm (KMA) is used on the data and the centroids of the clusters formed are used as prototypes representing all the patterns in the cluster.

21. Description of the Digit Data Each original digit pattern is a binary image of size 32 ×24 pixels. The Feature vector: Non-overlapping windows of size 2 × 2 are formed over the entire image and each window is replaced by one feature whose value corresponds to the number of one bits in that window. This results in 192 features, where the value of each feature varies from 0 to 4. the data patterns vary in terms of orientation of the digit, width and height.

22. A sample collection of training patterns

23. Mean and standard deviation of each class

24. More data reduction The dimensionality of the data set is further reduced by using the 2x2 windows. Finally, each pattern gets a total of 48 features. the dimensionality reduction improve the speed of the nearest neighbour classifier

25. Pre-processing of Data Take some algorithms to deal with scaling, translation, and rotation problems before feature extraction.

26. Recognition results Results show that, the classification accuracy ranges from 65% to 93% depending on the variation of NN classifiers, prototyping, and the clustering methods used.

27. Questionnaire …