聚類分析外文文獻(xiàn)及翻譯

1、本科畢業(yè)論文外文文獻(xiàn)及譯文文獻(xiàn)、資料題目： Cluster AnalysisBasic Concepts and Algorithms文獻(xiàn)、資料來源：文獻(xiàn)、資料發(fā)表（出版）日期：院 （部）： 土木工程學(xué)院專 業(yè)： 土木工程班 級(jí)： 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師：翻譯日期： 外文文獻(xiàn)：Cluster AnalysisBasic Concepts and AlgorithmsCluster analysis divides data into groups (clusters) that are meaningful, useful,or both. If meaningful groups ar

2、e the goal, then the clusters should capture the natural structure of the data. In some cases, however, cluster analysis is only a useful starting point for other purposes, such as data summarization. Whether for understanding or utility, cluster analysis has long played an important role in a wide

3、variety of elds: psychology and other social sciences, biology,statistics, pattern recognition, information retrieval, machine learning, and data mining.There have been many applications of cluster analysis to practical problems. We provide some specic examples, organized by whether the purpose of t

4、he clustering is understanding or utility.Clustering for Understanding Classes, or conceptually meaningful groups of objects that share common characteristics, play an important role in how people analyze and describe the world. Indeed, human beings are skilled at dividing objects into groups (clust

5、ering) and assigning particular objects to these groups (classication). For example, even relatively young children can quickly label the objects in a photograph as buildings, vehicles, people, animals, plants, etc. In the context of understanding data, clusters are potential classes and cluster ana

6、lysis is the study of techniques for automatically nding classes. The following are some examples:Biology. Biologists have spent many years creating a taxonomy (hierarchical classication) of all living things: kingdom, phylum, class,order, family, genus, and species. Thus, it is perhaps not surprisi

7、ng that much of the early work in cluster analys is sought to create a discipline of mathematical taxonomy that could automatically nd such classication structures. More recently, biologists have applied clustering to analyze the large amounts of genetic information that are now available. For examp

8、le, clustering has been used to nd groups of genes that have similar functions. Information Retrieval. The World Wide Web consists of billions of Web pages, and the results of a query to a search engine can return thousands of pages. Clustering can be used to group these search results into a small

9、number of clusters, each of which captures a particular aspect of the query. For instance, a query of “movie” might return Web pages grouped into categories such as reviews, trailers, stars, and theaters. Each category (cluster) can be broken into subcategories (sub-clusters), producing a hierarchic

10、al structure that further assists a users exploration of the query results. Climate. Understanding the Earths climate requires nding patternsin the atmosphere and ocean. To that end, cluster analysis has been applied to nd patterns in the atmospheric pressure of polar regions and areas of the ocean

11、that have a signicant impact on land climate. Psychology and Medicine. An illness or condition frequently has a number of variations, and cluster analysis can be used to identify these different subcategories. For example, clustering has been used to identify different types of depression. Cluster a

12、nalysis can also be used to detect patterns in the spatial or temporal distribution of a disease. Business. Businesses collect large amounts of information on current and potential customers. Clustering can be used to segment customers into a small number of groups for additional analysis and market

13、ing activities.Clustering for Utility：Cluster analysis provides an abstraction from individual data objects to the clusters in which those data objects reside. Additionally, some clustering techniques characterize each cluster in terms of a cluster prototype; i.e., a data object that is representati

14、ve of the other objects in the cluster. These cluster prototypes can be used as the basis for a number of data analysis or data processing techniques. Therefore, in the context of utility, cluster analysis is the study of techniques for nding the most representative cluster prototypes. Summarization

15、. Many data analysis techniques, such as regression or PCA, have a time or space complexity of O(m2) or higher (where m is the number of objects), and thus, are not practical for large data sets. However, instead of applying the algorithm to the entire data set, it can be applied to a reduced data s

16、et consisting only of cluster prototypes. Depending on the type of analysis, the number of prototypes, and the accuracy with which the prototypes represent the data, the results can be comparable to those that would have been obtained if all the data could have been used. Compression. Cluster protot

17、ypes can also be used for data compres-sion. In particular, a table is created that consists of the prototypes for each cluster; i.e., each prototype is assigned an integer value that is its position (index) in the table. Each object is represented by the index of the prototype associated with its c

18、luster. This type of compression is known as vector quantization and is often applied to image, sound, and video data, where (1) many of the data objects are highly similar to one another, (2) some loss of information is acceptable, and (3) a substantial reduction in the data size is desired Effcien

19、tly Finding Nearest Neighbors. Finding nearest neighbors can require computing the pairwise distance between all points. Often clusters and their cluster prototypes can be found much more effciently. If objects are relatively close to the prototype of their cluster, then we can use the prototypes to

20、 reduce the number of distance computations that are necessary to nd the nearest neighbors of an object. Intuitively, if two cluster prototypes are far apart, then the objects in the corresponding clusters cannot be nearest neighbors of each other. Consequently, to nd an objects nearest neighbors it

21、 is only necessary to compute the distance to objects in nearby clusters, where the nearness of two clusters is measured by the distance between their prototypes. This chapter provides an introduction to cluster analysis. We begin with a high-level overview of clustering, including a discussion of t

22、he various ap- proaches to dividing objects into sets of clusters and the different types of clusters. We then describe three specic clustering techniques that represent broad categories of algorithms and illustrate a variety of concepts: K-means, agglomerative hierarchical clustering, and DBSCAN. T

23、he nal section of this chapter is devoted to cluster validitymethods for evaluating the goodness of the clusters produced by a clustering algorithm. More advanced clusteringconcepts and algorithms will be discussed in Chapter 9. Whenever possible,we discuss the strengths and weaknesses of different

24、schemes. In addition,the bibliographic notes provide references to relevant books and papers that explore cluster analysis in greater depth.1.1Overview Before discussing specic clustering techniques, we provide some necessary background. First, we further dene cluster analysis, illustrating why it i

25、sdiffcult and explaining its relationship to other techniques that group data.Then we explore two important topics: (1) different ways to group a set ofobjects into a set of clusters, and (2) types of clusters.1.1.1What Is Cluster Analysis? Cluster analysis groups data objects based only on informat

26、ion found in thedata that describes the objects and their relationships. The goal is that theobjects within a group be similar (or related) to one another and dierent from(or unrelated to) the objects in other groups. The greater the similarity (orhomogeneity) within a group and the greater the dier

27、ence between groups,the better or more distinct the clustering.Cluster analysis is related to other techniques that are used to divide data objects into groups. For instance, clustering can be regarded as a form of classication in that it creates a labeling of objects with class (cluster) labels.How

28、ever, it derives these labels only from the data. In contrast, classicationn the sense of Chapter 4 is supervised classication; i.e., new, unlabeled objects are assigned a class label using a model developed from objects with known class labels. For this reason, cluster analysis is sometimes referre

29、d to as unsupervised classication. When the term classication is used without any qualication within data mining, it typically refers to supervised classication.Also, while the terms segmentation and partitioning are sometimesused as synonyms for clustering, these terms are frequently used for appro

30、aches outside the traditional bounds of cluster analysis. For example, the termpartitioning is often used in connection with techniques that divide graphs into subgraphs and that are not strongly connected to clustering. Segmentation often refers to the division of data into groups using simple tech

31、niques; e.g.,an image can be split into segments based only on pixel intensity and color, orpeople can be divided into groups based on their income. Nonetheless, somework in graph partitioning and in image and market segmentation is relatedto cluster analysis.1.1.2 Different Types of Clusterings An

32、entire collection of clusters is commonly referred to as a clustering, and in this section, we distinguish various types of clusterings: hierarchical (nested) versus partitional (unnested), exclusive versus overlapping versus fuzzy, and complete versus partial.Hierarchical versus Partitional The mos

33、t commonly discussed distinc- tion among different types of clusterings is whether the set of clusters is nested or unnested, or in more traditional terminology, hierarchical or partitional. Apartitional clustering is simply a division of the set of data objects into non-overlapping subsets (cluster

34、s) such that each data object is in exactly onesubset. If we permit clusters to have subclusters, then we obtain a hierarchical clustering, which is a set of nested clusters that are organized as a tree. Each node (cluster) in the tree (except for the leaf nodes) is the union of its children (subclu

35、sters), and the root of the tree is the cluster containing all the objects.Often, but not always, the leaves of the tree are singleton clusters of individual data objects. If we allow clusters to be nested, then one interpretation of Figure 8.1(a) is that it has two subclusters (Figure 8.1(b), each

36、of which, inturn, has three subclusters (Figure 8.1(d). The clusters shown in Figures 8.1(ad), when taken in that order, also form a hierarchical (nested) clusteringwith, respectively, 1, 2, 4, and 6 clusters on each level. Finally, note that a hierarchical clustering can be viewed as a sequence of

37、partitional clusterings and a partitional clustering can be obtained by taking any member of that sequence; i.e., by cutting the hierarchical tree at a particular level.Exclusive versus Overlapping versus Fuzzy The clusterings shown in Figure 8.1 are all exclusive, as they assign each object to a si

38、ngle cluster.There are many situations in which a point could reasonably be placed in more than one cluster, and these situations are better addressed by non-exclusiveclustering. In the most general sense, an overlapping or non-exclusiveclustering is used to reect the fact that an object can simulta

39、neously belong to more than one group (class). For instance, a person at a university can be both an enrolled student and an employee of the university. A non-exclusiveclustering is also often used when, for example, an object is “between” two or more clusters and could reasonably be assigned to any

40、 of these clusters.Imagine a point halfway between two of the clusters of Figure 8.1. Rather than make a somewhat arbitrary assignment of the object to a single cluster,it is placed in all of the “equally good” clusters.In a fuzzy clustering, every object belongs to every cluster with a membership w

41、eight that is between 0 (absolutely doesnt belong) and 1 (absolutelybelongs). In other words, clusters are treated as fuzzy sets. (Mathematically,a fuzzy set is one in which an object belongs to any set with a weight thatis between 0 and 1. In fuzzy clustering, we often impose the additional constra

42、int that the sum of the weights for each object must equal 1.) Similarly,probabilistic clustering techniques compute the probability with which each point belongs to each cluster, and these probabilities must also sum to 1. Because the membership weights or probabilities for any object sum to 1, a f

43、uzzyor probabilistic clustering does not address true multiclass situations, such as the case of a student employee, where an object belongs to multiple classes .Instead, these approaches are most appropriate for avoiding the arbitrariness of assigning an object to only one cluster when it may be cl

44、ose to several. Inpractice, a fuzzy or probabilistic clustering is often converted to an exclusiveclustering by assigning each object to the cluster in which its membership weight or probability is highest.Complete versus Partial A complete clustering assigns every object to a cluster, whereas a par

45、tial clustering does not. The motivation for a partial clustering is that some objects in a data set may not belong to well-dened groups. Many times objects in the data set may represent noise, outliers, or“uninteresting background.” For example, some newspaper stories may share a common theme, such

46、 as global warming, while other stories are more genericor one-of-a-kind. Thus, to nd the important topics in last months stories, we may want to search only for clusters of documents that are tightly related by a common theme. In other cases, a complete clustering of the objects is desired.For exam

47、ple, an application that uses clustering to organize documents forbrowsing needs to guarantee that all documents can be browsed. 1.1.3Different Types of Clusters Clustering aims to nd useful groups of objects (clusters), where usefulness is dened by the goals of the data analysis. Not surprisingly,

48、there are several different notions of a cluster that prove useful in practice. In order to visually illustrate the differences among these types of clusters, we use two-dimensional points, as shown in Figure 8.2, as our data objects. We stress, however, thatthe types of clusters described here are

49、equally valid for other kinds of data.Well-Separated A cluster is a set of objects in which each object is closer (or more similar) to every other object in the cluster than to any object notin the cluster. Sometimes a threshold is used to specify that all the objects in a cluster must be suciently

50、close (or similar) to one another. This ideal istic denition of a cluster is satised only when the data contains natural clusters that are quite far from each other. Figure 8.2(a) gives an example of well-separated clusters that consists of two groups of points in a two-dimensional space. The distan

51、ce between any two points in different groups is larger than he distance between any two points within a group. Well-separated clusters do not need to be globular, but can have any shape.Prototype-Based A cluster is a set of objects in which each object is closer(more similar) to the prototype that

52、denes the cluster than to the prototype of any other cluster. For data with continuous attributes, the prototype of a cluster is often a centroid, i.e., the average (mean) of all the points in the cluster. When a centroid is not meaningful, such as when the data has categorical attributes, the proto

53、type is often a medoid, i.e., the most representative pointof a cluster. For many types of data, the prototype can be regarded as the most central point, and in such instances, we commonly refer to prototype-based clusters as center-based clusters. Not surprisingly, such clusters tend to be globular

54、. Figure 8.2(b) shows an example of center-based clusters.Graph-Based If the data is represented as a graph, where the nodes are objects and the links represent connections among objects (see Section ),then a cluster can be dened as a connected component; i.e., a group of objects that are connected

55、to one another, but that have no connection to objects outside the group. An important example of graph-based clusters are contiguity-based clusters, where two objects are connected only if they are within a specied distance of each other. This implies that each object in a contiguity-based cluster

56、is closer to some other object in the cluster than to any point in a different cluster. Figure 8.2(c) shows an example of such clusters for two-dimensional points. This denition of a cluster is useful when clusters are irregular or intertwined, but can have trouble when noise is present since, as il

57、lustrated by the two spherical clusters of Figure 8.2(c), a small bridge of points can merge two distinct clusters. Other types of graph-based clusters are also possible. One such approach (Section ) denes a cluster as a clique; i.e., a set of nodes in a graph that are completely connected to each o

58、ther. Specically, if we add connections between objects in the order of their distance from one another, a cluster is formed when a set of objects forms a clique. Like prototype-based clusters, such clusters tend to be globular.Density-Based A cluster is a dense region of objects that is surrounded

59、bya region of low density. Figure 8.2(d) shows some density-based clusters for data created by adding noise to the data of Figure 8.2(c). The two circular clusters are not merged, as in Figure 8.2(c), because the bridge between them fades into the noise. Likewise, the curve that is present in Figure 8.2(c) also fades into the noise and does not form a cluster in Figure 8.2(d). A density-based denition of a clu