聚类分析 ——基本概念及算法外文翻译资料

聚类分析

——基本概念及算法

原文作者：Gooley W.W and Lohnes P.R

摘要： 聚类分析组数据对象仅仅基于MATLAB环境中，描述对象和它们之间的关系。我们的目标是，找出在一组类似（或相关）彼此和（或无关的）在其他各组对象的不同。越大组内和更大的群体之间的差异，更好或更明显的聚类相似性（相关性）。聚类的目的是找到对象（组），其中的用处是通过数据分析确定的目标有用的群体。

关键词：分组； 数据； 分析；对象

聚类分析将数据分为有意义的，有用的，或两者兼而有之的组（集群）。如果目标群体是有意义的，那么集群应该捕获数据的自然结构。但是在某些情况下，聚类分析只是一个用于其他目的有用的起点，如数据汇总。无论是理解或效用，聚类分析，长久以来在各个领域扮演重要角色：心理学等社会科学，生物学，统计，模式识别，信息检索，机器学习和数据采集。

聚类分析已经被应用到许多实际问题中。我们按照聚类的目的是了解或者实用而提供了一些具体的例子。
聚类理解类。对象或概念上是有意义的群体，有着共同的特点，在人们如何分析和说明事物上有重要的作用。事实上，人类善于将对象和特定对象分成组（集群）并且将它们分类。例如，即使是相对较小的儿童也可以快速识别出照片中的建筑物，车辆，人物，动物，植物等拍摄对象。在数据理解方面方面，集群是潜在的类，而聚类分析就是自动将集群分类的技术。以下是一些例子：
生物学。生物学家们花了很多年创造了万物分类（分层分类）：领域、语系、类、秩序、科、属和种。因此，这也许并不奇怪，在群集分析的早期多是试图建立一个数学学科分类，可以自动找到这样的分类结构。最近，生物学家已经将聚类应用到遗传信息处理放面。例如，集群已被用于寻找具有类似的功能基因组。
信息检索。万维网有数十亿的网页，一个搜索引擎的查询结果可以返回数千页。集群可以用来将这些搜索结果归为具有相同点的一大类。例如，一个“电影”的查询可能会返回到诸如评论，预告片，明星和剧院类别分组的网页。每个类别（集群）可以分成子类别（子集），产生一个层次结构，进一步帮助用户在查询结果。
气候。了解地球的气候需要找到模式分析大气和海洋。为此，聚类分析已被应用到寻找到对陆地上气候有重大影响的极地地区和海洋地区的大气压力。
心理学和医学。疾病或健康有很多的变数，聚类分析可以用来识别这些不同的子类别。例如，集群已被用于识别不同类型的抑郁症。聚类分析也可用于检测一种疾病空间和时间分布格局。
业务。企业收集当前和潜在客户大量信息。集群可以用来把客户分组以便进行额外的分析和营销活动。
聚类分析提供了一条从单个数据对象抽象到集群中。此外，一些集群技术根据一定的规则描述各集群的特点，也就是说，一个数据对象，它是在集群中的其他对象的代表。这些集束原型可以用来作为分析的数据或数据处理一些技术基础。因此，在公用事业方面，聚类分析是寻找最有代表性的集群原型研究方法。综述：许多数据分析技术。因此，不适合大数据集。然而，虽然算法不适用于整个数据集，它可以应用到减少簇原型组成的数据集。依据分析类型、原型的数量、准确度的不同，结果可以媲美那些将已获得的所有数据。压缩：集群原型也可用于数据压缩。特别是，一个表被创建为每个集群的原型组成，也就是说，每个原型分配一个整数值，是其在表中的位置（索引）。每个对象的代表是与其相关的原型群集索引。这种压缩类型被称为矢量量化，并经常用于图像，声音和视频数据，其中数据对象很多都是彼此非常相似，一些信息丢失是可以接受的，数据规模大幅减少是理想。有效发现最近邻居。最近的邻居发现可以要求计算所有点之间的成对的距离。通常集群与集群原型可以更有效的找到。如果对象比较接近其集群原型，然后我们可以使用原型，以减少其寻找对象的近邻距离计算数量。直观上，如果两个集群原型是相距甚远，那么在相应的簇对象不会是邻居。因此，要找到一个对象的近邻，只需要计算距离。
本章提供了一个聚类分析的介绍。我们首先介绍聚类，包括各种的分为簇集对象和不同类型的集群的分类方法。然后，我们描述了三个具体的聚类算法技术，代表了两大类，并说明一个概念品种有：K -均值，凝聚层次聚类，DBSCAN算法。本章最后一节是专门聚类有效性，评估方法由一个聚类算法产生的集群善良。

1.1概述
在具体讨论什么事聚类技术时，我们提供一些必要的背景。首先，我们进一步确定聚类分析，说明和解释其难点以及和其他集群方法的关系。然后探索两个重要议题：（1）将不同的事物组合成类，（2）类型的集群。
1.1.1什么是聚类分析？
聚类分析组数据对象仅仅基于MATLAB环境中，描述对象和它们之间的关系。我们的目标是，找出在一组类似（或相关）彼此和（或无关的）在其他各组对象的不同。越大组内和更大的群体之间的差异，更好或更明显的聚类相似性（相关性）。
另外，在分割和分配的条款是作为同义词集群，这些条款是经常使用的聚类分析之外的传统界限的方法。例如，分为子图和并不强烈连接到群集的连接。通常指的是分割成组的数据用简单的技术分工，例如，图像可分为基于像素的强度和颜色只分部分裂，人群可可依据收入进行分类。
1.1.2不同类型的群集合
整个集群的一个集合通常称为聚类，并在本节中，我们区分不同类型的群集合：层次（嵌套）与分割式（非嵌套），独有的与重叠与模糊。
划分的层次与最经常讨论的距离之间的群集合是不同类型的，簇集嵌套或非嵌套，或在更传统的术语，分层或划分的。 A集群是一个简单的数据对象设置成不重叠的子集（集群），使得每个数据对象的完全是分工的。
如果我们允许集群有子群，然后我们得到了一个层次聚类，这是该组织为一树嵌套簇集。树中的每个节点（群）（除叶节点）是它的子联盟，树的根是群集包含所有的.但并非总是如此，树上的叶子是对象的个人资料单身集群。最后，注意分层聚类可作为划分的群集合的序列和划分聚类效果，可采取任何成员的序列。
叠与模糊控制在图8.1所示的群集合都是排他性的，因为他们给每个对象都是一个单独的群。其中一点可以合理地在多个群集设了很多情况。在最一般的意义上，重叠或不重叠是用来反映一个事实，即一个对象可以同时属于多个组（类）。例如，在一所大学的人既可以是已登记的学生也可以是大学雇员。除非非重叠群也使用，一个对象是“与”两个或多个群集，可以合理地分配到其中任何群.

在一个模糊聚类，每个对象属于每一个成员的体重是介于0（绝对不属于）和1群集。换句话说，集群被视为模糊集。（数学，模糊集在其中任何一个对象属于0和1之间的权重）。模糊聚类，我们经常施加额外的约束，即对每个对象的权重之和必须等于1。）同样，概率聚类技术的概率计算每个点属于每个集群，还必须总结这些概率为1。因为成员权或任何对象之和为1，概率聚类没有解决真正的多用户情况下，如一个学生的雇员，其中一个对象属于多个类的情况。相反，这些方法是最合适的避免在分配一个对象只有一个群集的随意性可能接近时数。 或概率的模糊聚类经常转换为非重叠群，每个对象分配到集群中，其成员的重量或概率最高。
整的聚类与偏每个对象分配到集群，而不是一个局部聚类。对于一个局部聚类的动机是，在一个数据集的某些对象可能不属于明确界定的群体。很多时候，在数据集对象可能代表噪音，孤立点，或“无趣的背景。”例如，一些报纸报道，可能都有一个共同的主题，如全球变暖一类。因此，为了找到在上个月的故事中的重要议题，我们可能要搜索的文件是由一个共同的主题紧密相关的集群。在其他情况下，需求完整的对象聚类.例如，一个应用程序，使用聚类组织文档进行检索需要保证所有的文件可以浏览。

1.1.3簇的不同类型

聚类的目的是找到对象（组），其中的用处是通过数据分析确定的目标有用的群体。毫不奇怪，有几种不同的群集的概念在实践中证明是有益的。为了直观地说明这些类型的集群中的差异，我们使用二维点，如图8.2所示，由于我们的数据对象，我们强调，但是，这里描述的集群类型同样为其他类型的数据无效。

分隔集群是一组对象，其中每个对象是密切（或更多类似）集群中的每个对象比其他任何对象群集。有时，一个阈值用来指定集群中的所有对象都必须充分接近（或类似）彼此。这种理想的集群技术信息研究所的定义，只有当数据满足包含从很远的自然相互集群。图8.2（a）给出了一个良好的分离集群的两个例子，在一个两维空间点群组成。任意两点之间的距离是不同的群体大于他任意两点间的距离保持在一组。井分隔群集不须球状，但可以有任意形状。

基于原型的集群是一组对象，其中每个对象是密切（更多类似）的原型定义，而不是任何其他群集原型群集。对于连续属性的数据，集群的原型往往是重心，即所有在集群点的平均值（平均）。当质心是没有意义的，例如，当数据类别属性，原型往往是最有代表性的集群。对于许多类型的数据，该原型可以被看作是最核心的一点，在这种情况下，我们通常所说的中心的集群原型为基础的集群。毫不奇怪，这种集群往往是球状。基于图的数据是，如果作为一个图，其中的节点对象和对象之间的联系表示连接，然后一组可以作为一个连接组件中定义的代表，也就是说，对象的组彼此相连，但不会对本集团以外对象的连接。一种基于图的集群重要的例子是连续性的群集，其中只有两个对象，如果它们连接在一个相互指定距离之内。这意味着，每一个连续性的群集对象是接近到群集中的其他一些对象比任何一个不同的聚点。基于密度的群集是一组环绕低密度区域对象的密集区。集群的一个基于密度的定义时，往往采用集群不规则或交织，在噪声和离群点都存在。相比之下，集群的一个连续性的定义都不能很好的工作数据。

共享属性（概念集群）更普遍，我们可以定义为一个共享对象的一些属性设置群集。这个定义包括所有以前的群集的定义，在一个中心的群集共享，例如，对象的属性，它们都是相同的质心。然而，共享属性的方法还包括集群研究的新类型。一个三角区（集群）毗邻长方形之一，有两个交织在一起的圆圈（集群）。在这两种情况下，聚类算法将需要集群的一个非常具体的概念，成功地检测到这些集群。对查找安泰这种集群的过程称为概念聚类。然而，过于复杂的集群的一个概念，会考虑在模式识别领域的我们，所以我们只考虑在这本书集群简单的类型。

在路线图这一章中，我们使用以下三个简单的，但聚类分析所涉及的许多重要概念：

K均值。这是一个以原型为基础，试图找到一个均值的聚类技术。

凝聚层次聚类。此分群方式是指一组密切相关的聚类技术，开始时各自作为一个单身聚点，然后反复，直到一个单一的合并两个最接近的集群的层次聚类集合，全方位的集群仍然存在。这些方法在一些有基于图形的聚类方面自然解释，而其他人在一个原型为基础的方法方面作出解释。

DBSCAN。这是一个基于密度的聚类算法，划分聚类，在其中的簇数量为自动，由算法确定。但低密度区的点容易被忽略，因此DBSCAN不是一种完整的聚类方法。

外文文献出处：Multivariate Data Analysis (John Wiley amp; Sons, Inc., New York, 1971):35-40

剩余内容已隐藏，支付完成后下载完整资料

Cluster Analysis

—Basic Concepts and Algorithms

Cluster analysis divides data into groups (clusters) that are meaningful, useful,or both. If meaningful groups are 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 variety of fields: 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 specific examples, organized by whether the purpose of the 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 (clustering) and assigning particular objects to these groups (classification). 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 analysis is the study of techniques for automatically finding classes. The following are some examples:

Biology. Biologists have spent many years creating a taxonomy (hierarchical classification) of all living things: kingdom, phylum, class,order, family, genus, and species. Thus, it is perhaps not surprising that much of the early work in cluster analys is sought to create a discipline of mathematical taxonomy that could automatically find such classification structures. More recently, biologists have applied clustering to analyze the large amounts of genetic information that are now available. For example, clustering has been used to find groups of genes that have similar functions.

bull; 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 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 hierarchical structure that further assists a userrsquo;s exploration of the query results.

bull; Climate. Understanding the Earthrsquo;s climate requires finding patternsin the atmosphere and ocean. To that end, cluster analysis has been applied to find patterns in the atmospheric pressure of polar regions and areas of the ocean that have a significant impact on land climate.

bull; 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 analysis can also be used to detect patterns in the spatial or temporal distribution of a disease.

bull;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 marketing 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 representative 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 finding the most representative cluster prototypes.

bull; Summarization. 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 set 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.

bull; Compression. Cluster prototypes 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 cluster. 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

bull; Effciently 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 reduce the number of distance computations that are necessary to find 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 find an objectrsquo;s near

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[286858]，资料为PDF文档或Word文档，PDF文档可免费转换为Word