1、14.11.2001,Data mining: Clustering,1,Intro/Ass. Rules,Episodes,Text Mining,Home Exam,24./26.10.,30.10.,Clustering,KDD Process,Appl./Summary,14.11.,21.11.,7.11.,28.11.,Course on Data Mining (581550-4),14.11.2001,Data mining: Clustering,2,Today 14.11.2001,Todays subject: Classification, clustering Nex
2、t weeks program: Lecture: Data mining process Exercise: Classification, clustering Seminar: Classification, clustering,Course on Data Mining (581550-4),14.11.2001,Data mining: Clustering,3,Classification and prediction Clustering and similarity,Classification and clustering,14.11.2001,Data mining: C
3、lustering,4,What is cluster analysis? Similarity and dissimilarity Types of data in cluster analysis Major clustering methods Partitioning methods Hierarchical methods Outlier analysis Summary,Cluster analysis,Overview,14.11.2001,Data mining: Clustering,5,Cluster: a collection of data objects simila
4、r to one another within the same cluster dissimilar to the objects in the other clusters Aim of clustering: to group a set of data objects into clusters,What is cluster analysis?,14.11.2001,Data mining: Clustering,6,Typical uses of clustering,As a stand-alone tool to get insight into data distributi
5、on As a preprocessing step for other algorithms,Used as?,14.11.2001,Data mining: Clustering,7,Applications of clustering,Marketing: discovering of distinct customer groups in a purchase database Land use: identifying of areas of similar land use in an earth observation database Insurance: identifyin
6、g groups of motor insurance policy holders with a high average claim cost City-planning: identifying groups of houses according to their house type, value, and geographical location,14.11.2001,Data mining: Clustering,8,What is good clustering?,A good clustering method will produce high quality clust
7、ers with high intra-class similarity low inter-class similarity The quality of a clustering result depends on the similarity measure used implementation of the similarity measure The quality of a clustering method is also measured by its ability to discover some or all of the hidden patterns,14.11.2
8、001,Data mining: Clustering,9,Requirements of clustering in data mining (1),Scalability Ability to deal with different types of attributes Discovery of clusters with arbitrary shape Minimal requirements for domain knowledge to determine input parameters,14.11.2001,Data mining: Clustering,10,Requirem
9、ents of clustering in data mining (2),Ability to deal with noise and outliers Insensitivity to order of input records High dimensionality Incorporation of user-specified constraints Interpretability and usability,14.11.2001,Data mining: Clustering,11,Similarity and dissimilarity between objects (1),
10、There is no single definition of similarity or dissimilarity between data objects The definition of similarity or dissimilarity between objects depends on the type of the data considered what kind of similarity we are looking for,14.11.2001,Data mining: Clustering,12,Similarity and dissimilarity bet
11、ween objects (2),Similarity/dissimilarity between objects is often expressed in terms of a distance measure d(x,y) Ideally, every distance measure should be a metric, i.e., it should satisfy the following conditions:,14.11.2001,Data mining: Clustering,13,Type of data in cluster analysis,Interval-sca
12、led variables Binary variables Nominal, ordinal, and ratio variables Variables of mixed types Complex data types,14.11.2001,Data mining: Clustering,14,Interval-scaled variables (1),Continuous measurements of a roughly linear scale For example, weight, height and age The measurement unit can affect t
13、he cluster analysis To avoid dependence on the measurement unit, we should standardize the data,14.11.2001,Data mining: Clustering,15,Interval-scaled variables (2),To standardize the measurements: calculate the mean absolute deviationwhere and calculate the standardized measurement (z-score),14.11.2
14、001,Data mining: Clustering,16,Interval-scaled variables (3),One group of popular distance measures for interval-scaled variables are Minkowski distanceswhere i = (xi1, xi2, , xip) and j = (xj1, xj2, , xjp) are two p-dimensional data objects, and q is a positive integer,14.11.2001,Data mining: Clust
15、ering,17,Interval-scaled variables (4),If q = 1, the distance measure is Manhattan (or city block) distanceIf q = 2, the distance measure is Euclidean distance,14.11.2001,Data mining: Clustering,18,Binary variables (1),A binary variable has only two states: 0 or 1 A contingency table for binary data
16、,Object i,Object j,14.11.2001,Data mining: Clustering,19,Binary variables (2),Simple matching coefficient (invariant similarity, if the binary variable is symmetric):Jaccard coefficient (noninvariant similarity, if the binary variable is asymmetric):,14.11.2001,Data mining: Clustering,20,Binary vari
17、ables (3),Example: dissimilarity between binary variables: a patient record tableeight attributes, of which gender is a symmetric attribute, and the remaining attributes are asymmetric binary,14.11.2001,Data mining: Clustering,21,Binary variables (4),Let the values Y and P be set to 1, and the value
18、 N be set to 0 Compute distances between patients based on the asymmetric variables by using Jaccard coefficient,14.11.2001,Data mining: Clustering,22,Nominal variables,A generalization of the binary variable in that it can take more than 2 states, e.g., red, yellow, blue, green Method 1: simple mat
19、ching m: # of matches, p: total # of variablesMethod 2: use a large number of binary variables create a new binary variable for each of the M nominal states,14.11.2001,Data mining: Clustering,23,Ordinal variables,An ordinal variable can be discrete or continuous Order of values is important, e.g., r
20、ank Can be treated like interval-scaled replacing xif by their rank map the range of each variable onto 0, 1 by replacing i-th object in the f-th variable bycompute the dissimilarity using methods for interval-scaled variables,14.11.2001,Data mining: Clustering,24,Ratio-scaled variables,A positive m
21、easurement on a nonlinear scale, approximately at exponential scale for example, AeBt or Ae-Bt Methods: treat them like interval-scaled variables not a good choice! (why?) apply logarithmic transformation yif = log(xif) treat them as continuous ordinal data and treat their rank as interval-scaled,14
22、.11.2001,Data mining: Clustering,25,Variables of mixed types (1),A database may contain all the six types of variables One may use a weighted formula to combine their effects:where,14.11.2001,Data mining: Clustering,26,Variables of mixed types (2),Contribution of variable f to distance d(i,j): if f
23、is binary or nominal: if f is interval-based: use the normalized distanceif f is ordinal or ratio-scaled compute ranks rif and and treat zif as interval-scaled,14.11.2001,Data mining: Clustering,27,Complex data types,All objects considered in data mining are not relational = complex types of data ex
24、amples of such data are spatial data, multimedia data, genetic data, time-series data, text data and data collected from World-Wide Web Often totally different similarity or dissimilarity measures than above can, for example, mean using of string and/or sequence matching, or methods of information r
25、etrieval,14.11.2001,Data mining: Clustering,28,Major clustering methods,Partitioning methods Hierarchical methods Density-based methods Grid-based methods Model-based methods (conceptual clustering, neural networks),14.11.2001,Data mining: Clustering,29,Partitioning methods,A partitioning method: co
26、nstruct a partition of a database D of n objects into a set of k clusters such that each cluster contains at least one object each object belongs to exactly one cluster Given a k, find a partition of k clusters that optimizes the chosen partitioning criterion,14.11.2001,Data mining: Clustering,30,Cr
27、iteria for judging the quality of partitions,Global optimal: exhaustively enumerate all partitions Heuristic methods: k-means (MacQueen67): each cluster is represented by the center of the cluster (centroid) k-medoids (Kaufman & Rousseeuw87): each cluster is represented by one of the objects in the
28、cluster (medoid),14.11.2001,Data mining: Clustering,31,K-means clustering method (1),Input to the algorithm: the number of clusters k, and a database of n objects Algorithm consists of four steps: partition object into k nonempty subsets/clusters compute a seed points as the centroid (the mean of th
29、e objects in the cluster) for each cluster in the current partition assign each object to the cluster with the nearest centroid go back to Step 2, stop when there are no more new assignments,14.11.2001,Data mining: Clustering,32,K-means clustering method (2),Alternative algorithm also consists of fo
30、ur steps: arbitrarily choose k objects as the initial cluster centers (centroids) (re)assign each object to the cluster with the nearest centroid update the centroids go back to Step 2, stop when there are no more new assignments,14.11.2001,Data mining: Clustering,33,K-means clustering method - Exam
31、ple,14.11.2001,Data mining: Clustering,34,Strengths of K-means clustering method,Relatively scalable in processing large data sets Relatively efficient: O(tkn), where n is # objects, k is # clusters, and t is # iterations. Normally, k, t n. Often terminates at a local optimum; the global optimum may
32、 be found using techniques such as genetic algorithms,14.11.2001,Data mining: Clustering,35,Weaknesses of K-means clustering method,Applicable only when the mean of objects is defined Need to specify k, the number of clusters, in advance Unable to handle noisy data and outliers Not suitable to disco
33、ver clusters with non-convex shapes, or clusters of very different size,14.11.2001,Data mining: Clustering,36,Variations of K-means clustering method (1),A few variants of the k-means which differ in selection of the initial k centroids dissimilarity calculations strategies for calculating cluster c
34、entroids,14.11.2001,Data mining: Clustering,37,Variations of K-means clustering method (2),Handling categorical data: k-modes (Huang98) replacing means of clusters with modes using new dissimilarity measures to deal with categorical objects using a frequency-based method to update modes of clusters
35、A mixture of categorical and numerical data: k-prototype method,14.11.2001,Data mining: Clustering,38,K-medoids clustering method,Input to the algorithm: the number of clusters k, and a database of n objects Algorithm consists of four steps: arbitrarily choose k objects as the initial medoids (repre
36、sentative objects) assign each remaining object to the cluster with the nearest medoid select a nonmedoid and replace one of the medoids with it if this improves the clustering go back to Step 2, stop when there are no more new assignments,14.11.2001,Data mining: Clustering,39,Hierarchical methods,A
37、 hierarchical method: construct a hierarchy of clustering, not just a single partition of objects The number of clusters k is not required as an input Use a distance matrix as clustering criteria A termination condition can be used (e.g., a number of clusters),14.11.2001,Data mining: Clustering,40,A
38、 tree of clusterings,The hierarchy of clustering is ofter given as a clustering tree, also called a dendrogram leaves of the tree represent the individual objects internal nodes of the tree represent the clusters,14.11.2001,Data mining: Clustering,41,Two types of hierarchical methods (1),Two main ty
39、pes of hierarchical clustering techniques: agglomerative (bottom-up): place each object in its own cluster (a singleton) merge in each step the two most similar clusters until there is only one cluster left or the termination condition is satisfied divisive (top-down): start with one big cluster con
40、taining all the objects divide the most distinctive cluster into smaller clusters and proceed until there are n clusters or the termination condition is satisfied,14.11.2001,Data mining: Clustering,42,Two types of hierarchical methods (2),14.11.2001,Data mining: Clustering,43,Inter-cluster distances
41、,Three widely used ways of defining the inter-cluster distance, i.e., the distance between two separate clusters, are single linkage method (nearest neighbor):complete linkage method (furthest neighbor):average linkage method (unweighted pair-group average):,14.11.2001,Data mining: Clustering,44,Str
42、engths of hierarchical methods,Conceptually simple Theoretical properties are well understood When clusters are merged/split, the decision is permanent = the number of different alternatives that need to be examined is reduced,14.11.2001,Data mining: Clustering,45,Weaknesses of hierarchical methods,
43、Merging/splitting of clusters is permanent = erroneous decisions are impossible to correct later Divisive methods can be computational hard Methods are not (necessarily) scalable for large data sets,14.11.2001,Data mining: Clustering,46,Outlier analysis (1),Outliers are objects that are considerably
44、 dissimilar from the remainder of the data can be caused by a measurement or execution error, or are the result of inherent data variability Many data mining algorithms try to minimize the influence of outliers to eliminate the outliers,14.11.2001,Data mining: Clustering,47,Outlier analysis (2),Mini
45、mizing the effect of outliers and/or eliminating the outliers may cause information loss Outliers themselves may be of interest = outlier mining Applications of outlier mining Fraud detection Customized marketing Medical treatments,14.11.2001,Data mining: Clustering,48,Cluster analysis groups object
46、s based on their similarity Cluster analysis has wide applications Measure of similarity can be computed for various type of data Selection of similarity measure is dependent on the data used and the type of similarity we are searching for,Summary (1),14.11.2001,Data mining: Clustering,49,Clustering
47、 algorithms can be categorized into partitioning methods, hierarchical methods, density-based methods, grid-based methods, and model-based methods There are still lots of research issues on cluster analysis,Summary (2),14.11.2001,Data mining: Clustering,50,Seminar Presentations/Groups 7-8,Classifica
48、tion of spatial data,K. Koperski, J. Han, N. Stefanovic: “An Efficient Two-Step Method of Classification of Spatial Data“, SDH98,14.11.2001,Data mining: Clustering,51,Seminar Presentations/Groups 7-8,WEBSOM,K. Lagus, T. Honkela, S. Kaski, T. Kohonen: “Self-organizing Maps of Document Collections: A
49、New Approach to Interactive Exploration”, KDD96T. Honkela, S. Kaski, K. Lagus, T. Kohonen: “WEBSOM Self-Organizing Maps of Document Collections”, WSOM97,14.11.2001,Data mining: Clustering,52,Thanks to Jiawei Han from Simon Fraser University for his slides which greatly helpedin preparing this lectur
50、e!,Course on Data Mining,14.11.2001,Data mining: Clustering,53,References - clustering,R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for data mining applications. SIGMOD98 M. R. Anderberg. Cluster Analysis for Applications. Academic Pres
51、s, 1973. M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the clustering structure, SIGMOD99. P. Arabie, L. J. Hubert, and G. De Soete. Clustering and Classification. World Scietific, 1996 M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorit
52、hm for discovering clusters in large spatial databases. KDD96. M. Ester, H.-P. Kriegel, and X. Xu. Knowledge discovery in large spatial databases: Focusing techniques for efficient class identification. SSD95. D. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2:139-172, 1987. D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on dynamic systems. In Proc. VLDB98.,
