{"id":415,"date":"2018-08-27T11:58:36","date_gmt":"2018-08-27T11:58:36","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=415"},"modified":"2019-01-02T07:30:52","modified_gmt":"2019-01-02T07:30:52","slug":"introduction-to-clustering","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/introduction-to-clustering\/","title":{"rendered":"Introduction to Clustering"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Machine Learning.In this module we will discuss clustering, a very important function of machine learning called clustering. We will discuss the broad categories of clustering with illustrative examples.<\/p>\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand Clustering and its applications\r\n\r\n\u2022 To understand Hierarchical Clustering\r\n\r\n\u2022 To understand Agglomerative Clustering with an Illustrative Example\r\n\r\n \r\n\r\n23.1Introduction<\/strong>\r\n\r\n \r\n

Clustering is the most important unsupervised learning<\/strong>approach associated with machine learning. It can be viewed as a method for data exploration<\/strong>which essentially means looking for patterns or structures in the data space that may be of interest in a collection of unlabeled data. Essentially no classes are associated with data instances a priori as in the case of supervised learning.<\/p>\r\n \r\n

Now let us look at simplistic definition of clustering. Clustering can be defined as the method of organizing data instances into groups based on their similarity. In other words a cluster is a collection or group of data instances that are similar to each other and dissimilar to data instances belonging to other clusters.<\/p>\r\n \r\n\r\n23.1.1 Natural Grouping -Clustering is subjective<\/strong>\r\n\r\n \r\n

A set of data instances or samples can be grouped differently based on different criteria or features, in other words clustering is subjective. Figure 23.1 shows a set of seven people. They have been grouped into three clusters based on whether they are school employees, they belong to a family or based on the gender. Therefore choosing the attributes or features based on which\u00a0clustering is to be carried out is an important aspect of clustering just as it was for classification.<\/span><\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\n \r\n\r\nCriteria 23.1.2 Clusters \u2013 Distance viewpoint<\/strong>\r\n\r\n \r\n

When we are given a set of instances or examples represented as a set of points, we need to define the notion of distance between these points. We then group the points into some number of clusters, such that members of a cluster are close or similar to each other while members of different clusters are dissimilar or farther apart than members belonging to the same cluster. Figure 23.2 shows a data set that has three natural clusters where the data points group together based on the distance. An outlier is a data point that is isolated from all other data points.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n23.2 Applications of Clustering<\/strong>\r\n\r\n \r\n

In the context of machine learning, clustering is one of the functions that has many interesting applications. One of the applications of clustering is for understanding. Understanding is achieved through appropriate grouping. Grouping related documents for browsing, grouping genes and proteins that have similar functionality, or grouping stocks with similar price fluctuations are some examples that help in understanding the commonalities and differences between groups. Another use of clustering is in summarization, in other words we reduce the size of large data sets. Some examples of clustering are shown in Figure 23.3 (a) and (b). The example in Figure 23.3 (a) shows how Google news uses clustering of news articles to help in better presentation of news. In fact by using appropriate features for clustering we can also bring out a personalized presentation. Figure 23.3 (b) shows the use of clustering to show areas clustered based on the amount of precipitation<\/p>\r\n \r\n\r\n\"\"\r\n

Let us see some real-life examples of clustering. When designing T-shirts making them to fit each person is too expensive while one-size-fits-all is not a satisfactory policy. We could group people with similar sizes to design \u201csmall\u201d, \u201cmedium\u201d and \u201clarge\u201d T-shirts. Example 1: groups people of similar sizes together to make \u201csmall\u201d, \u201cmedium\u201d and \u201clarge\u201d T-Shirts.<\/p>\r\n \r\n

In today\u2019s world of online marketing, segmenting customers according to their similarities would help in targeted marketing. Features such as previous products bought, effect of discounts etc.. could be used for such marketing.<\/p>\r\n \r\n

Another example of clustering is in document clustering where given a collection of text documents, we cancluster them according to their content similarities in order to create a topic hierarchy.<\/p>\r\n \r\n

As we can see from the varied applications clustering is one of the most utilized data mining techniques. In image processing it is used to cluster images based on their visual content. In the web scenario it is used to cluster groups of users based on their access patterns on webpages or cluster searchers based on their search behavior or to cluster webpages based on their content and links. In bioinformatics clustering can be used to group similar proteins based on similarity of their chemical structure and\/or functionality. It has been used in almost every field, e.g., medicine, psychology, botany, sociology, biology, archeology, marketing, insurance, libraries, etc. Due to the large increase of online documents text clustering is now becoming very important.<\/p>\r\n \r\n\r\n23.3 Aspects of clustering<\/strong>\r\n\r\n \r\n

In general clustering deals with high dimensional data. Example of such data include text documents and images. Dealing with such high dimensional data is an important aspect of clustering. Another important aspect that influences the effectiveness of clustering is the choice of distance function or the similarity or dissimilarity measure used. The basic clustering algorithms can be divided into two types namely hierarchicalclustering and partitional clustering. The choice of which type and which algorithm is another important aspect of clustering. We also need to decide on the parameters to evaluate clustering quality. In general the algorithms strive to maximize inter-cluster distance and minimize intra-clusterdistance (Figure 23.4). In other words the quality of clustering depends on the algorithm used, the distance function selected , and the application for which it is to be used.<\/p>\r\n \r\n\r\n\"\"\r\n

\r\n\r\n \r\n\r\n23.3.1 High Dimensional Data<\/strong>\r\n\r\n \r\n

Often as we discussed clustering needs to deal with high dimensional data where given a cloud of data points we want to understand its structure.Clustering needs to capture the structure using some dimensionality techniques and then performing clustering (Figure 23.5).<\/span><\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\n23.4 Similarity Measures<\/strong>\r\n\r\n \r\n

As we have already discussed clustering is the grouping together of \u201csimilar\u201d data. Choosing an appropriate (dis)similarity measure is a critical step in clustering. Similarity measure is often described as the inverse of the distance function that is less the distance more is the similarity. There are many distance functions for the different types of data such as numeric data, nominal data etc. Distance measures can also be defined specifically for different applications.<\/p>\r\n \r\n\r\n23.4.1 Distance functions for Numeric Attributes<\/strong>\r\n\r\n \r\n

In general in the case of numeric attributes distance is denoted asdist<\/em>(xi<\/em>, xj<\/em>), where xi<\/em> and xj<\/em> are data points. Please note that these data points can be vectors. The most commonly used distance functions in this context are Euclidean distance and Manhattan (city block) distance. These two distance functions are special cases of Minkowski distance.<\/p>\r\n \r\n\r\n23.4.1.1<\/strong>\u00a0\u00a0\u00a0\u00a0 Minkowski Distance<\/strong>\r\n\r\n \r\n

Given below is the Minkowski distance, where h is any positive integer. In other words the distance between two data points xi and xj is defined as the hth root of the sum of the difference between them in each dimension taken to the power of h.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n23.4.1.2 Euclidean Distance<\/strong>\r\n\r\n \r\n

In the case of Euclidean distance h=2.<\/p>\r\n \r\n\r\n\"\"\r\n

In other words Euclidean distance between two data points xi and xj is the square root of the sum of the squares of the difference between them in each dimension. This is one of the most commonly used distance function for clustering data points with numerical attributes<\/p>\r\n \r\n\r\n23.4.1.3 Manhattan Distance<\/strong>\r\n\r\n \r\n\r\nIn the case of Manhattan distance h=1.\r\n\r\n \r\n\r\n\"\"\r\n

Here the sum of the weights w1,w2,\u2026wr =1 In the case of weighted Euclidean distance the difference between the data points in each dimension is weighted. Each dimension in the vector representing the points corresponds to different attributes or features so this essentially means that we can weight each feature according to its importance in defining the cluster.<\/p>\r\n \r\n

23.4.1.5<\/strong>\u00a0Chebychev distance<\/strong><\/p>\r\n \r\n

This distance is equal to the maximum difference between the values of any one of the attributes and the distance measure is given as:<\/p>\r\n\"\"\r\n\r\n \r\n\r\n23.4.2<\/strong>\u00a0Distance functions for BinaryAttributes<\/strong>\r\n\r\n \r\n

Binary attributes have two values or states but no ordering relationships, e.g., attribute gender has two values male and female.<\/p>\r\n \r\n

In the case of binary attributes normally a confusion matrix is used where the i<\/em>th and j<\/em>th data points are represented asvectors xi<\/em> and xj<\/em> (Figure 23.6).We use a confusion matrix to introduce the distance functions\/measures.<\/p>\r\n \r\n\r\n\"\"\r\n

In Figure 23.6 \u201ca\u201d corresponds to the number of attributes with the value of 0 for both data pointsxi<\/em> and xj<\/em>, \u201cb\u201d corresponds to 0 for xi<\/em>and 1 for<\/em> xj<\/em>, \u201cc\u201d corresponds to 1 for xi<\/em>and 0 for<\/em> xj<\/em>, while \u201cd\u201d corresponds to the number of attributes with the value of 1 for both data pointsxi<\/em> and xj<\/em>,<\/p>\r\n \r\n

The confusion matrix can be used when the binary attribute is symmetric that is if both states (0 and 1) have equal importance, and carry the same weights. Then the distance function is the proportion of mismatches of their values:<\/p>\r\n \r\n

dist(xi<\/em>,xj<\/em>)<\/em> = (b+c)\/(a+b+c+d)<\/p>\r\n \r\n

However sometimes the binary attributes are asymmetric that is one of the states is more important than the other. We assume that state 1 represents the important state in which case the Jaccard measure using the confusion matrix can be defined as:<\/p>\r\n \r\n

JDist(xi<\/em>,xj<\/em>)<\/em> = (b+c)\/(a+b+c)<\/p>\r\n \r\n

For text documents normally we usecosine similarity which is a similarity measure not a distance measure.Cosine similarity is a measure of similarity between two vectors obtained by measuring the cosine of the angle between them (Figure 23.7). The similarity between any two given documents d<\/em>j<\/em> and d<\/em>k<\/em>, represented as vectors is given as:<\/p>\r\n\"\"\r\n\r\n \r\n

In this case wi is a weight probably based on the frequency of words in the documents.<\/p>\r\n\"\"\r\n

The result of the Cosine function is equal to 1 when the angle is 0, and it is less than 1 when the angle is of any other value. As the angle between the vectors decreases, the cosine value approaches 1, that is the two vectors are closer, and the similarity between the documents increases.<\/p>\r\n \r\n

23.5 Methods of Clustering<\/strong><\/p>\r\n \r\n

The basic method of clustering is the hierarchical method which is of two types agglomerative and divisive. Agglomerative clustering is a bottom up method where initially we assume that each data point is by itself a cluster. Then we repeatedly combine the two \u201cnearest\u201d clusters into one. On the other hand divisive clustering is a top down procedure where we start with one cluster and recursively split the clusters until no more division is possible. We normally carry out point assignment where we maintain a set of clusters and allocate points to nearest cluster.<\/p>\r\n \r\n\r\n23.6<\/strong>\u00a0\u00a0\u00a0 Hierarchical Clustering<\/strong>\r\n\r\n \r\n

In the hierarchical clustering approach we carry out partitioning of the data set in a sequential manner. The approach constructs nested partitions layer by layer by grouping objects into a tree of clusters (Figure 23.8). In this context there is no need to know the number of clusters in advance. In general the distance matrix is used as the clustering criteria.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n23.6.1 Types of Hierarchical Clustering<\/strong>\r\n\r\n \r\n

Hierarchical clustering methods can be further classified as either agglomerative or divisive, depending on whether the hierarchical decomposition is formed in a bottom-up (merging) or top-down (splitting) fashion. As we have discussed the hierarchical approach sequentially partitions the data points and constructs a tree of clusters. The following are two sequential clustering strategies for constructing the tree of clusters. The important issues in both cases are cluster distance to be considered and the termination condition to be used.<\/p>\r\n \r\n

23.6.1.1 Agglomerative Clustering<\/strong><\/p>\r\n \r\n

Agglomerative clustering is a bottom-up strategy where initially each data pointforms its own (atomic) cluster. We then merge these atomic clusters into larger and larger clusters based on some distance metric. The algorithm terminates when all the data points are in a single cluster or merging is continued until certain termination conditions are satisfied. Most hierarchical clustering methods belong to this category.Agglomerative and divisive clustering on the data set {a, b, c, d ,e } is shown in Figure 23.9.<\/p>\r\n \r\n

23.6.1.2<\/strong>\u00a0 Divisive Clustering<\/strong><\/p>\r\n \r\n

Divisive clustering is a top-down strategywhich does the reverse of agglomerative hierarchical clustering where initially all data points together form a single cluster. Then the cluster is subdivided into smaller and smaller clusters based on some distance metric.It subdivides the clusters into smaller and smaller pieces, until it satisfies certain termination conditions, such as a desired number of cluster or the diameter of each cluster is within a certain threshold<\/p>\r\n \r\n\r\n\"\"\r\n

\r\n\r\n \r\n\r\n23.7 Hierarchical Clustering: The Algorithm<\/strong>\r\n\r\n<\/div>\r\n \r\n

Hierarchical clustering takes as input a set of points. It then creates a tree in which the points are leaves and the internal nodes reveal the similarity structure of the points.The tree is often called a \u201cdendogram.\u201dThe method is summarized below:<\/p>\r\n\r\n