Introduction Clustering in data mining, is useful in discovery of distribution patterns in underlying data. Our interest is in clustering based on non-numerical data-categorical or Boolean attributes. An example of hierarchical clustering algorithm used in sample data is ROCK (RObust Clustering using linKs). The clustering technique is useful for grouping data points such that a single group or cluster have similar characteristics while different groups are dissimilar. ROCK belongs to the class of agglomerative hierarchical clustering algorithms. OCK algorithm has mainly 3 steps namely, ‘Draw random sample’, ‘Cluster with links’, ‘Label data in disk’ the steps are described in the following diagram: ROCK’s hierarchical algorithm accepts as input the set S of N sample points to be clustered, and the number of desired clusters K. The first step in the procedure is to compute the number of links between pairs of points. Initially each point is separate cluster. For each cluster i, we build a local heap q[i] and maintain the heap during the execution of the algorithm. Q[i] contains every cluster j such that link[i,j] is non-zero. The clusters j in q[i] are ordered in the decreasing order of the goodness measure with respect to I, g(i,j). In addition to the local heaps q[i] for each cluster I, the algorithm also maintains an additional global heap q that contains all the clusters. Furthermore, the clusters in q are ordered in the decreasing order of their best goodness measures. Thus, g(j, max(q[j])) is used to order the various clusters j in q, where max(q[j]), the max element in q[j], is the best cluster to merge with cluster j. At each step, the max cluster j in q and the max cluster q[j[ are the best pair of clusters to be merged. Example program in R is as follows: For every point, after computing a list of its neighbors, the algorithm considers all pairs of its neighbors. For each pair, the point contributes one link. If the process is repeated for every point and the link count is incremented for each pair of neighbors, then at the end, the link counts for all pairs of points will be trained. If M¬I is the size of the neighbor list for point I, then for point I, we have to increase the link count by one in M2i entries. This, the complexity of the algorithm is the sum of M2i which is O(N*Mm*Ma), where Ma and Mm are the average and maximum number of the neighbors for a point, respectively. In the worst case, the value of Mm can be n in which case the complexity of the algorithm becomes O (Ma*N2). In practice, we expect Mm to be reasonably close to Ma and thus, for these cases, the complexity of the algorithm reduces to O (M2a*n) on average. ROCK performs agglomerative hierarchical clustering and explores the concept of links for data with categorical attributes. The various attributes include:
a. Links: These are the number of common neighbors between two objects.
b. Neighbors: If similarity between two points exceeds certain similarity threshold they are neighbors.
c. Criterion function: The objective is o maximize the criterion function to get the good quality clusters. By maximizing we mean maximizing the sum of links of intra cluster point pairs while minimizing the sum of links of inter cluster point pairs.
A given real life application of ROCK algorithm is in congressional votes. It is the US Congressional Voting records in 1984. Each record corresponds to one congress man’s votes on 16 issues. All attributes are Boolean values, and very few contain missing values. A classification label of Republican or Democratic is provided with each data record. The data set contains records for 168 republicans and 267 Democrats.
The following are the general applications of clustering:
1. Pattern recognition
2. Spatial data analysis:
– create thematic maps in GIS by clustering feature spaces
– detect spatial clusters and explain them in spatial data mining
3. Image Processing
4. Economic Science (especially market research)
5. World Wide Web:
– Document classification
– Cluster Weblog data to discover groups of similar access patterns
Examples of clustering applications include:
1. Software clustering: cluster files in software systems based on their functionality
2. Intrusion detection: Discover instances of anomalous (intrusive) user behavior in large system log files
3. Gene expression data: Discover genes with similar functions in DNA microarray data.
4. Marketing: Help marketers discover distinct groups in their customer bases, and then use this knowledge to develop targeted marketing programs
5. Land use: Identification of areas of similar land use in an earth observation database
6. Insurance: Identifying groups of motor insurance policy holders with a high average claim cost
7. City-planning: Identify groups of houses according to their house type, value, and geographical location.
8. Earth-quake studies: Observed earth quake epicenters should be clustered along continent faults.
9. Biology: plant and animal taxonomies, genes functionality