聚类分析（CA）是一种典型的无监督学习方法，这种方法是根据对象的特点将它们分成不同的组，即将一组对象分组到类似对象的类中的过程称为聚类。群集（cluster）是数据对象的集合，这些数据对象在同一群集中彼此类似，并且与其他群集中的对象不相似。一组数据对象可以统一处理为一个组，因此也可以将聚类方法视为一种数据压缩形式。
尽管分类（classification）是区分对象群体或类别的有效手段，但它需要经常昂贵地收集和标注大量训练元组或模式，分类器用这些元组或模式对每个组进行建模。聚类作为无监督学习方法，在这方面有着天然的优势。
聚类分析是一项重要的人类活动。在童年早期，我们学习如何区分猫和狗，或动物和植物之间，不断改进潜意识里的聚类方案。通过自动聚类，我们可以识别物体空间中的密集区域和稀疏区域，从而发现数据属性之间的整体分布模式和有趣的相关性。聚类分析已广泛应用于众多应用领域，包括市场研究，模式识别，数据分析和图像处理。在商业中，集群可以帮助营销人员在其客户群中发现不同的群体，并根据采购模式刻画客户群体的特征。在生物学中，它可用于推导植物和动物分类标准，对具有相似功能的基因进行分类，并深入了解群体内在结构。集群还可以帮助识别地球观测数据库中类似土地使用的区域，以及根据房屋类型，价值和地理位置确定城市中的住房群体，以及识别汽车保险组保单持有人的平均索赔成本较高。它也可以用来帮助对Web上的文档进行信息发现分类。
聚类在某些应用程序中也称为数据分段（data segmentation），因为聚类分析根据它们的相似性将大数据集分成组。聚类也可用于异常值检测，异常值检测的应用包括检测信用卡欺诈和监控电子商务中的犯罪活动。例如，信用卡交易中的例外情况，例如非常昂贵和频繁的购买行为，可能是欺诈活动的预兆。作为数据挖掘功能，聚类分析可以用作独立工具，以深入了解数据分布，观察每个聚类的特征，并专注于一组特定的聚类以进一步分析。或者，它可以用作其他算法的预处理步骤，例如表征，属性子集选择和分类，然后将对检测到的聚类和选定的属性或特征进行操作。
K-均值是应用最广泛的聚类方法，其它方法还包括k-Medoids、分层聚类和DBSCAN。期望最大化法（EM）也是聚类分析的一种解决方案。聚类分析在数据挖掘、市场调研、异常值检测等许多领域都有应用。另外，降维技术也是一类类似于聚类分析的无监督学习方法，其典型的代表有主成分分析（PCA）、线性判别分析和Isomap。
[描述来源：Han J.; Kamber M.; Pei J. (2011). Data mining: concepts and techniques. Morgan Kaufman.]
发展历史
描述
聚类分析的早期研究始于60年前——K-means算法的出现，它最初在1955年由Steinhaus提出，随后Stuart Lloyd在1957年提出K-均值聚类算法。这是一种用于推荐系统的早期技术，可以将用户分成不同的组别以便针对性的推荐，因此聚类分析被划分至应用阶段。1978年，David Harrison和Daniel L Rubinfeld将K-均值聚类算法用于研究房产市场数据，他们使用住房市场数据来衡量对清洁空气的支付意愿。1987年，Kaufman和Rousseeuw提出围绕中心点的分割聚类（Partitioning Around Medoids Clustering），是许多我们现在熟悉的聚类算法的基础。1992年，Vladimir Batagelj, Anuška Ferligoj, Patrick Doreian开发出改进过的重定位算法和改进过的凝聚分层算法（agglomerative hierarchical algorithm）；1996年Martin Ester, Hans-Peter Kriegel, Jörg Sander及Xiaowei Xu提出有噪声应用的基于密度的空间聚类（Density-Based Spatial Clustering of Applications with Noise/DBSCAN）。这个算法是以密度为本的：给定某空间里的一个点集合，这算法能把附近的点分成一组（有很多相邻点的点），并标记出位于低密度区域的局外点（最接近它的点也十分远），DBSCAN是其中一个最常用的聚类分析算法，也是其中一个科学文章中最常引用的，对聚类分析造成了深远的影响。在2014年，这个算法在数据挖掘会议KDD上获颁发了Test of Time award，该奖项是颁发给一些于理论及实际层面均获得持续性的关注的算法。同年，利用分层方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering using Hierarchies/BIRCH）方法诞生。BIRCH（使用层次结构进行均衡迭代减少和聚类）是一种无监督数据挖掘算法，用于对特别大的数据集执行分级聚类。BIRCH的一个优势是它能够递增和动态地聚集传入的多维度量数据点，以便为给定的资源集合（内存和时间约束）产生最佳质量的聚类。在大多数情况下，BIRCH只需要对数据库进行一次扫描。它的发明者声称BIRCH是“在数据库领域提出的第一种有效处理'噪声'（数据点不是基本模式的一部分）的聚类算法”，并在模型表现上击败了DBSCAN，该算法在2006年获得SIGMOD10 year test of time award。
有关聚类分析的研究已经相当成熟，目前主要集中在对聚类算法的产业化应用上，如2005年起Netflix 使用DBSCAN来寻找运行速度显著慢于主流的异常服务器；2011年Roman Filipovych等学者引用聚类分析检验老年人的健康状况并评估了他们所使用的聚类方法在发现人脑MR图像聚类问题方面的表现。
当使用IEEE搜索时，我们找到了超过1500万个与聚类分析相关的结果；但是，聚类分析的受关注度仅有回归分析的一半，所以这种模型离公众认知可能还有一定距离。
主要事件
年份 | 事件 | 相关论文/Reference |
1955 | K-means算法的雏形由Steinhaus被提出 | Steinhaus, H. (1956). Sur la division des corps matériels en parties. Bull.acad.polon.sci.cl.iii, 801-804. |
1957 | Stuart Lloyd首次开发出K-均值算法（也叫Lloyd's algorithm） | Lloyd, S. P. (1982). Least squares quantization in PCM, IEEE Transactions on Information Theory, 28(2): 129–137. |
1978 | Harrison D.和Rubinfeld D.L.将K-均值聚类算法用于研究房产市场数据 | Harrison, D.; Rubinfeld, D. L. (1978).Hedonic housing prices and the demand for clean air.Journal of Environmental Economics and Management. 5(1):81-102. |
1987 | Kaufman 和 Rousseeuw 提出围绕中心点的分割聚类（Partitioning Around Medoids Clustering） | Kaufman, L.; Rousseeuw, P.; (1987).Clustering by means of medoids.Statistical Data Analysis Based on the L1 Norm and Related Methods. pp 405-416. |
1992 | Vladimir Batagelj, Anuška Ferligoj, Patrick Doreian开发出改进过的重定位算法和改进过的凝聚分层算法（agglomerative hierarchical algorithm） | Batagelj, V.; Ferligoj, A.; Doreian, P. (1992).Direct and indirect methods for structural equivalence.Social Networks. 14(1–2):63-90. |
1996 | Martin Ester, Hans-Peter Kriegel, Jörg Sander及Xiaowei Xu提出有噪声应用的基于密度的空间聚类（Density-Based Spatial Clustering of Applications with Noise/DBSCAN） | Ester, M.;Kriegel, H.-P.; Sander, J.; Xu, X. (1996).A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). |
1996 | 利用分层方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering using Hierarchies/BIRCH）方法诞生 | Zhang, T.; Ramakrishnan, R.; Livny, M. (1996). BIRCH: an efficient data clustering method for very large databases. Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96. pp. 103–114. |
2011 | Roman Filipovych等学者引用聚类分析检验老年人的健康状况 | Filipovych, R.; Resnick, S. M.; Davatzikos, C. (2011). Semi-supervised cluster analysis of imaging data. NeuroImage. 54(3): 2185-2197. |
发展分析
瓶颈
聚类是一个具有挑战性的研究领域，以下是聚类分析面临的一些典型挑战：
- 可扩展性（Scalability）：许多聚类算法适用于包含少于几百个数据对象的小数据集;但是，大型数据库可能包含数百万个对象。聚类分析很容易受规模的影响（如K-均值），而且有时候也可靠性也不高。对特定大型数据集的样本进行聚类可能会导致结果偏差，因此我们需要高度可扩展的聚类算法。
- 处理不同类型的属性的能力（Ability to deal with different types of attributes）：许多算法被设计为聚类基于区间的（数值）数据。但是，应用程序可能需要同时聚类其他类型的数据，例如二进制，分类（标称）和有序数据，或这些数据类型的混合。
- 不局限于某一种距离度量的聚类算法（Discovery of clusters with arbitrary shape）：许多聚类算法基于欧几里德距离度量或曼哈顿距离度量来确定聚类。基于这种距离度量的算法倾向于找到具有相似大小和密度的球形群集。但是，群集可以是任何形状。开发可以检测任意形状的聚类的算法是非常重要的。
- 对超参数取值鲁棒（Minimal requirements for domain knowledge to determine input parameters）：许多聚类算法要求用户在聚类分析中输入某些超参数（例如所需聚类的数量）。聚类结果可能对输入参数非常敏感，依赖于分析师做出正确的选择，而且聚类分析的解可能不是唯一的。但在实际情况中这些超参数通常很难确定，特别是对于包含高维对象的数据集。这不仅给用户带来负担，而且也使得聚类的质量难以控制。还有如在DBSCAN中，如果数据集的密度不均匀，就很难确定ε的选择。
- 处理嘈杂数据的能力（Ability to deal with noisy data）：大多数真实世界的数据库包含异常值或缺失，未知或错误的数据。一些聚类算法对这些数据很敏感，并可能导致质量很差的聚类结果。
- 增量聚类和对输入记录顺序的不敏感性（Incremental clustering and insensitivity to the order of input records）：某些聚类算法不能将新插入的数据（即数据库更新）合并到现有的聚类结构中，而是必须从头开始确定新的聚类。而另一些聚类算法对输入数据的顺序很敏感。也就是说，给定一组数据对象，这样的算法可能会根据输入对象的表示顺序返回显着不同的聚类。开发对输入顺序不敏感的增量聚类算法和算法非常重要。
- 高维度（High dimensionality）：数据库可以包含多个维度或属性。许多聚类算法擅长处理低维数据，只涉及二维到三维。人眼很擅长判断多达三个维度的聚类质量。在高维空间中查找数据对象的集群非常具有挑战性，特别是考虑到这些数据可能很稀疏且高度倾斜。
- 基于约束的聚类（Constraint-based clustering）：真实世界的应用程序可能需要在各种约束条件下执行聚类。假设您的工作是选择城市中给定数量的新自动银行机（ATM）的位置。要做出这样的决定，您可以在考虑城市河流和高速公路网络等约束条件以及每个集群的客户类型和数量的情况下对家庭进行分组。找到满足指定约束同时还具有良好表现的聚类结果是很有挑战性的。
- 可解释性和可用性（Interpretability and usability）：用户期望聚类结果是可解释的，可理解的和可用的。也就是说，聚类可能需要绑定到特定的语义解释和应用程序。研究应用程序目标如何影响集群功能和方法的选择非常重要。
此外，从理论角度分析，聚类分析总是假设存在分组，但这个假设可能很弱或是错误的。
未来发展方向
在未来应用中，聚类分析可能会被用作「第一步」技术。也可能会出现「后聚类（Post-cluster）」技术被用来减少误差，让聚类分析更加可靠、稳定，能在更多行业领域应用。
Contributor: Yuanyuan Li, Mos Zhang