参考文献：(1)《Introduction to Data Mining (Second Edition)》，2018，Tan, Pang-Ning；Steinbach, Michael；Karpatne, Anuj；Kumar, Vipin; (2) 范明 范宏建 等译《数据挖掘导论（完整版）》，2011. 注：以下笔记是结合了以上两本书并加入自己的理解而整理，如果有不恰当之处，请提出宝贵意见。
Contents
1 Introduction2 What is Cluster Analysis？3 Applications of Cluster Analysis4 Different Types of Clusterings5 Different Types of Clusters
1 Introduction
本文主要对于聚类分析有一个概览：聚类分析的概念，聚类分析的应用领域，聚类（clustering）的类型，簇（cluster）的类型等。
Cluster analysis divides data into groups(clusters) that are meaningful or useful. The groups or clusters should capture the natural structure of the data. In some case, cluster analysis is used for data summarization in order to reduce the size of the data)。
其实，聚类分析就是将数据划分成有意义或有用的组（簇）。这些组（簇）应该能够代表数据的自然结构（natural structure），也就是本质特征。聚类分析可以用来对庞杂的数据进行描述总结，达到概括数据的目的。
注：术语：cluster - 簇；clustering - 聚类；cluster prototype - 簇原型；
2 What is Cluster Analysis？
Given a set of objects, place them in groups such that the objects in a group are similar (or related) to one another and different from (or unrelated to) the objects in other groups. The greater the similarity (or homogeneity) within a group and the greater the difference between groups, the better or more distinct the clustering.
聚类就是根据一组数据对象之间的关系，对数据对象进行分组，目标是：组内的对象是相似的（相关的），不同组中的对象是不同的（不相关的）。组内的相似性（similarity）越小，组间的相似性越大，聚类效果就越好。如下图所示：
注意：
“segmentation” 和 “partitioning” 这两个词有时也表示聚类。例如，在市场调研行业里面我们会使用"segmentation"这个词来表示客户分群, 而使用的具体技术就是cluster analysis；图像分割(graph partitioning)的许多工作也都和cluster analysis有关。不过segmentation通常指使用简单的技术将数据分组，如根据收入水平将人群分组。聚类（clustering）和分类（classification）的区别：聚类的任务是找到有意义的组，而分类的任务是要确定对象属于哪个预定义的目标组。虽然聚类也可以看成是分类，但classification是有监督的分类（supervised classification)，必须有预定义的类别标签，然后再根据这个类别标签来标记对象属于哪一个类别；而clustering属于无监督的分类（unsupervised classification), 没有预先给定的分类标记，只能从数据中找到隐藏的簇，从而用簇标号来标记簇中的对象。
然而，从数据集中的找到簇(cluster)并不是容易的事情。如下图1的数据集里，不同的聚类方法可以得出不同的结果，看似都有道理，但也有可能是人的视觉系统造成的假象。可见，簇的定义无法做到精确，而最好的定义是基于数据的特征和期望的结果。
The definition of a cluster is imprecise and that the best definition depends on the nature of data and the desired results.
图1-1 同一数据集的不同聚类效果
3 Applications of Cluster Analysis
聚类分析的应用领域很广泛。下面主要从理解和实用两个方面来介绍。
用于理解的聚类：
聚类分析帮助我们分析和描述这个世界。人以类聚，物以群分。簇（cluster）就是潜在的类。聚类分析就是用来自动找到这些类的一种技术，其在各领域的应用如下：
生物学(biology)。系统分类学(taxonomy)属于层次结构的分类(hierarchical classification): 届（kingdom）- 门（phylum）- 纲（class) - 目（order）- 科（family）-- 属（genus） – 种（species） 聚类还用于发现有类似功能的基因组。信息检索(Information Retrieval)。搜索引擎(search engine)也是层次结构。气候(Climate)。用来发现大气层和海洋的模式(pattern)。心理学和医学(Psychology and Medicine)。用来识别一种疾病的不同类型的变种；用来检测疾病的时间和空间分布模式。商业(Business)。市场研究中的客户细分(Segmentation)。
旨在效用的聚类:
某些聚类分析方法使用簇原型(cluster prototypes)来描述簇的特征。簇原型(cluster prototypes)就是能够代表簇中其他对象的数据，如平均值，中位数。这些簇原型(cluster prototypes)可以用作大量数据分析和数据处理的基础。简而言之，聚类分析就是发现最具有代表性的簇原型(cluster prototypes)的一种技术。聚类的具体作用包括:
汇总概括(Summarization)。像回归和主成分分析(PCA)，这些模型的运算具有O(m^2)或者更高的时间和空间复杂度（m是数据对象的个数），当应用于大型数据集就吃不消了。但是可以将这些算法用于仅包含簇原型的数据集，而不是整个数据集，最终的结果也会和使用所有数据的结果相媲美。使用簇原型相当就减少了数据的规模。压缩(Compression)。数据的压缩称作向量量化（vector quantization), 常用于图像、声音、视频数据，这类数据满足：（1）许多数据对象之间高度相似，（2）我们可以接受部分信息丢失，（3）我们希望大幅度压缩数据量。 例如，创建一个包含所有簇原型的表，赋予每个簇原型一个整数值作为位置索引，这样每个对象就能够用簇原型的索引表示。有效发现最近邻(Nearest Neighbors)。找出最近邻可能需要计算所有点与点之间的距离，计算量时非常大的。而簇和簇原型（cluster prototype)是比较容易找到的，那么当想要找到一个对象的最近邻，我们只需要计算其到邻近簇中对象的距离，不需要计算到较远簇中对象的距离（如果两个簇离得很远，两个簇内的对象就不可能互为近邻），这样就减少发现最近邻时的计算量。计算两个簇的邻近性可以用簇原型之间的距离表示。
4 Different Types of Clusterings
数据中所有的簇cluster的组合通常叫做聚类clustering，聚类的不同类型有：
层次的（嵌套的）与划分的（非嵌套的）: hierarchical (nested) vs partitional (unnested)。通过下面两个图1-2和图1-3就很容易区分层次聚类和划分聚类了 图1-2 层次聚类
图1-3 划分聚类
互斥的、重叠的与模糊的 : exclusive vs overlapping vs fuzzy
在上面图1-1中的聚类都是互斥的，既每个对象属于单个簇。如果点对象同时属于多个簇，那么就是非互斥或重叠的聚类。比如在大学里，一个人可能既是学生，又是雇员。 模糊聚类（Fuzzy clustering）也属于非互斥聚类的一种。模糊聚类中，每一个对象是否属于某个簇是由权值或概率值决定的，权值的取值范围是0~1，每个对象的权值总和等于1。 非互斥聚类主要用于：当一个对象接近于多个簇时，避免将对象随意的指派到某一个簇。
完全的与部分的: complete vs partial
在某些情况下，我们希望只对数据集的部分数据进行聚类。数据集中有一些不能够明确定义的对象，比如有一些噪声、离群点和我们并不感兴趣的点。
5 Different Types of Clusters
聚类的主要任务是发现有意义的簇(cluster)。要想找到这些簇，我们先来了解一下簇有哪些类型。 图1- 4 不同的簇类型
明显分离的簇（well-separated clusters)
每个点到同簇中任意点的距离比到其他簇的点的距离更近（图a)。不过，只有当数据包含互相远离的自然簇时，才会满足这种理想的定义。明显分离的簇不一定是球型的，可以是任意形状。
基于原型的簇（protetype-based clusters)。
每个点到其簇原型的距离比到任何其他簇原型的距离更近（图b)。连续性变量的数据集的簇原型通常是质心（即均值）；分类型变量的数据集的簇原型通常是中心点（即簇中最具代表性的点）。所以基于原型的簇也称作基于中心的簇（Center-based clusters)。这种簇趋向于球型（globular）。
基于图的簇（Graph-Based clusters）。
簇内的点互相连通但不与簇外的对象连通（图c左边的两个簇）。一个重要的例子就是基于邻近的簇（contiguous clusters/ Nearest neighbor or Transitive），每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近（图c)。基于邻近的簇适用于当簇不规则或者缠绕时，但是当数据有噪点时就可能出现问题，如图c的两个不同 的球型簇会因为一个点桥合并为一个簇。
基于密度的簇（Density-based clusters）。
簇是被低密度区域分开的高密度区域（图d)。图c中的点桥和曲线到了图d中并没有形成簇，而是消失在噪声中，且两个圆形簇并没有合并。因此当簇不规则或者互相盘绕，并且有噪声和离群点时，常使用基于密度的簇。
概念簇（Conceptual clusters)。针对比较复杂的簇类型，需要具体的簇概念来检测，将涉及模式识别（pattern recognition）。
写在最后：本文的一些知识点将会在后面的文章深入学习。后面的文章会涉及几种常见的聚类方法，而下一章就是K-means算法的介绍。
精彩内容
您阅读本篇文章共花了：
发表评论