在理解大数据中，聚类是一种非常常见的基本方法。近日，数据科学家兼程序员PeterGleeson在freeCodeCamp上发表了一篇深度文章，对一些聚类算法进行了基本介绍，并通??过简单而详细的例子解释了它们的工作过程。看下图，有各种各样的虫子和蜗牛，你试着把它们分成不同的组？不难，先从找出蜘蛛开始吧！你做完了吗？虽然没有必然的“正确答案”，但大体上我们可以将这些虫子分为四类：蜘蛛、蜗牛、蝴蝶/飞蛾、蜜蜂/蜂类。很简单，对吧？你可以用两倍的错误来区分错误，对吧？你所需要的只是一点时间和对昆虫学的热情——即使有成千上万的昆虫。分开他们。但对于机器来说，将这10个对象分类成有意义的分组并不是微不足道的——借助称为组合数学的数学分支，我们知道对于这10个错误，我们可以有115,975种不同的分组方式。如果错误的数量增加到20，则有超过50万亿种可能的方法来对它们进行分组。如果有100个错误，可能的解决方案的数量将超过已知宇宙中的粒子数量。还有多少？根据我的计算，大约是500,000,000,000,000,000,000,000,000,000,000,000倍，这是一个难以想象的超级天文数字！但是大部分的分组方案都是没有意义的，在那些浩如烟海的分组选项的分组方法中，你只能发现一小部分有用的bug。虽然我们人类可以很快做到这一点，但我们倾向于认为我们具有快速分组和理解大量数据的能力是理所当然的。无论是一段文本、屏幕上的图像还是一系列对象，人类通常都能有效地理解他们所面对的数据。鉴于人工智能和机器学习的关键是快速理解大量输入数据，开发这些技术有哪些捷径？在本文中，您将了解三种聚类算法——机器可以使用它们来快速理解大量数据集。当然，除了这些还有其他算法，但希望这里的介绍能给你一个好的开始！在本文中，我将对每个聚类算法进行概述，简要介绍其工作原理，以及更详细的分步实现案例。我相信这将有助于您理解这些算法。3neatclusters,K=31.K-meansclustering1.什么时候用？当你事先知道你会找到多少组？2.工作原理该算法可以随机化将每个观察值分配给k个类中的一个，然后计算每个类的平均值。接下来，它将每个观察值重新分配到最接近平均值的类别，然后重新计算其平均值。重复此步骤，直到不需要新的分配为止。3.有效案例假设有一组9名足球运动员，每个人在赛季中都打进了一定数量的进球（比如3-30个）。然后我们想将它们分成几组——比方说3组。第一步：我们需要将这些玩家随机分成3组，计算每组的均值。第1组球员A（5个球），球员B（20个球），球员C（11个球）该组的平均值=(5+20+11)/3=12第2组球员D（5个球），球员E（9球），球员F（19球）组平均=11第3组球员G（30球），球员H（3球），球员I（15球）组平均=16第2步：对于每个球员，重新分配他们到平均分数最接近的组；例如，球员A（5个球）被重新分配到第2组（平均值=11）。然后计算新的均值。第1组（原始平均值=12）球员C（11个球），球员E（9个球）新平均数=(11+9)/2=10第2组（原始平均值=11）球员A（5个球），球员D（5球），选手H（3球）新平均值=4.33第3组（原始平均值=16）选手B（20球），选手F（19球），运动员G（30球），运动员I（15球）新平均值=21重复第二步，直到每组的平均值不发生变化。对于这个简单的任务，下一次迭代将达到我们的目标。现在就是这样，您从原始数据集中获得了3个聚类！第1组（原始平均值=10）球员C（11个球），球员E（9个球），球员I（15个球）最终平均=11.3第2组（原始平均值=4.33）球员A（5个球），球员D（5个球），球员H（3个球）最终平均=4.33第3组（原始平均值=21）球员B（20个球），球员F（19个球），球员G（30个球），最终平均=23以这个例子，集群或许能够对应到这些球员在场上的位置——比如防守、中场和进攻。K-means在这里起作用是因为我们可以合理地预测数据将自然地分为这三个组。通过这种方式，当给定一系列性能统计数据时，机器可以很好地估计任何足球队的球员位置——这对体育分析很有用，而且对将数据集分类到预定义的分组中也很有用。用于其他目的的分类任务。4.细节：上述算法有一些变体。最初的“种子”聚类可以通过多种方式完成。在这里，我们将每个运动员随机分成一组并计算该组的平均值。这导致了这样一个事实，即最初手段可能彼此接近，这增加了后面的步骤。选择种子集群的另一种方法是每组只有一个玩家，然后开始将其他玩家分配到最接近它的组。以这种方式返回的集群对初始种子更敏感，减少了高度可变数据集中的重复。然而，这种方法有可能减少完成算法所需的迭代次数，因为分组将花费更少的时间来收敛。K均值聚类的一个明显限制是您必须提前提供有关预期聚类数量的假设。还有一些方法可以评估对特定集群的适合度。例如，簇内平方和测量每个簇内的方差。聚类越好，整体WCSS越低。二、层次聚类1、什么时候用？当我们想进一步挖掘观测数据的潜在关系时，可以使用层次聚类算法。2.它是如何工作的首先我们计算一个距离矩阵，其中矩阵的元素(i,j)代表观测值i和j之间的距离度量。然后将最接近的两个观察值组合成一对并计算它们的平均值。通过将成对的观察结果组合成一个对象，我们生成了一个新的距离矩阵。具体的合并过程是计算每对最近观察值的均值，并填充新的距离矩阵，直到所有观察值都被合并。3.工作示例：下面是一个超级简单的鲸鱼或海豚物种分类数据集。作为一名受过训练的生物学家，我可以保证通常我们会使用更详尽的数据集构建系统。我们现在可以看看这六个物种的典型体长。在这种情况下，我们将使用2次重复。步骤1：计算每个物种之间的距离矩阵。在这种情况下，使用欧氏距离，即数据点之间的距离。您可以像查看路线图上的距离图一样计算距离。我们可以通过查看相关行和列的交集值来查看任意两个物种之间的长度差异。第2步：选择两个最接近的物种，在本例中为宽吻海豚和灰海豚，平均体长为3.3m。重复第一步并再次计算距离矩阵，但这次将宽吻海豚和灰海豚的平均长度替换为3.3m。接下来，使用新的距离矩阵重复第二步。现在，距离最近的是领航鲸和逆戟鲸，所以我们计算它们的平均长度（7.0m）并将它们组合成一个新术语。然后我们重复步骤1再次计算距离矩阵，但是现在将领航鲸和逆戟鲸合并为一个项目并将长度设置为7.0m。我们使用当前的距离矩阵再次重复步骤2。最近的距离(3.7m)出现在两个已经合并的项中，我们现在将其合并为一个更大的项（平均5.2m）。然后，我们再次重复步骤2，最小的距离（5.0m）出现在座头鲸和长须鲸身上，所以继续将它们合并为一项，并计算平均值（17.5m）。回到第1步，计算一个新的距离矩阵，其中座头鲸和长须鲸已合并为一个。最后，重复步骤2，距离矩阵中只有一个值（12.3m），我们已经全部合并为一项，现在可以停止循环过程了。让我们先看看最终的合并。它现在具有嵌套结构（请参阅JSON），可以绘制为树图。这类似于阅读家谱的方式。在树状图中，两个观察值越接近，它们就越相似和密切相关。R-Fiddle.org生成的树状图通过树状图的结构，我们可以更深入地了解数据集的结构。在上面的案例中，我们看到两个主要分支，一个分支是HW和FW，另一个是BD、RD、PW、KW。在生物进化中，通常使用包含更多物种和测量值的大型数据集来推断这些物种之间的分类关系。在生物学之外，层次聚类也用于机器学习和数据挖掘。重要的是，使用此方法不需要像K均值聚类那样设置bin的数量。您可以按给定的高度“切割”树以返回拆分的簇。高度的选择可以通过多种方式完成，具体取决于我们希望对数据进行聚类的分辨率。比如上图中，如果我们在高度等于10的地方画一条线，那么两个主分支就会分成两个子图。如果我们从等于2的高度开始拆分，则会生成三个聚类。4.更多细节：此处介绍的层次聚类算法具有三个不同的方面。最基本的方法是我们使用的凝聚过程，我们从单个数据点开始迭代并将数据点聚合在一起，直到它成为一个大集群。另一种（计算量更大的）方法从巨型集群开始，然后将数据分解为更小的集群，再细分为单个数据点。还有计算距离矩阵的方法。对于许多情况，欧几里德距离（参见毕达哥拉斯定理）就足够了，但也有一些更适合特殊情况的替代方案。最后，链接标准也可以改变。集群根据它们的不同距离连接，但我们定义“接近”的方式是灵活的。在上述情况下，我们通过测量每个聚类均值（即质心）之间的距离并将其与最近的聚类配对来实现。但您可能想使用其他定义。例如，每个簇由几个离散点组成。我们可以将两个簇之间的距离定义为任意点之间的最小（或最大）距离，如下图所示。还有其他定义连接标准的方法，可能适用于不同的场景。红色/蓝色：质心连接；红/绿：最小连接；绿色/蓝色：最大连接数3.GraphCommunityDetection1.什么时候用？当您的数据可以表示为网络或图（graph）时。2.它是如何工作的图社区通常被定义为比网络其他部分连接更紧密的顶点的子集。基于更具体的定义，存在各种用于识别图的算法，包括（但不限于）：边介数、模块化最大化、Walktrap、CliquePercolation、LeadingEigenvector...3.EfficientCases图论是一个研究网络对于数学分支，参考机器之心的文章《想了解概率图模型?你要先理解图论的基本定义与形式》。使用图论，我们可以将复杂系统建模为“顶点”和“边”的抽象集合。也许最直观的例子是社交网络。顶点代表人，连接顶点的边代表彼此是朋友或粉丝的用户。但是，要将系统建模为网络，您必须找到一种有效连接各种组件的方法。图论在聚类方面的一些创新应用包括：图像数据的特征提取、基因调控网络的分析。下面给出了一个入门级的例子，一个简单的图表显示了我最近浏览过的8个网站，这些网站是根据它们的维基百科页面中的链接连接起来的。此数据非常简单，您可以手动绘制它，但对于较大的项目，更快的方法是编写Python脚本。这是我写的一个：https://raw.githubusercontent.com/pg0408/Medium-articles/master/graph_maker.py在R版本3.3.3中用igraph绘制的图顶点的颜色表示它们的社区关系的大小根据他们的中心地位。你能看出Google和Twitter是最核心的吗？此外，这些集群在现实生活中很有意义（始终是一个重要的性能指标）。黄色顶点通常是参考/搜索站点，蓝色顶点是所有在线发布站点（文章、推文或代码），橙色顶点是YouTube和PayPal——因为YouTube是由前PayPal员工创建的。机器可以很好地总结它！除了用作可视化大型系统的有用方法之外，网络的真正力量在于它们的数学分析能力。让我们将上图中的网络翻译成更数学的形式。下面是网络的邻接矩阵：每行和每列相交处的值表示对应的一对顶点之间是否存在边。例如，Medium和Twitter之间有边，所以它们的行列交集为1。同样，Medium和PayPal之间没有边，所以它们的行列交集为0。这个邻接矩阵编码了这个的所有属性网络——它给了我们打开所有有价值见解的可能性的钥匙。首先，将每行或每列中的数字相加得到每个顶点的度数——即它连接到多少个其他顶点——一个通常用字母k表示的数字。类似地，将每个顶点的度除以2得到边的数量，也称为链接，用L表示。行/列的数量是网络中顶点的数量，称为节点（node），用N表示。只要知道k、L和N以及邻接矩阵A中每个单元的值，我们就可以计算该网络任何给定集群的模块性。假设我们已经将网络聚类成组。然后我们可以使用这个模块化分数来评估这个集群的质量。较高的分数表示我们将网络划分为“准确”的组，而较低的分数表示我们的集群更接近随机。如下图所示：模块化是衡量分区“质量”的标准。可以使用以下公式计算模块化：这个公式有点复杂，但让我们分解一下以便更好地理解它。M是我们要计算的模块化。1/2L告诉我们将后者除以2L，即网络中边数的两倍。Σ表示法表示求和并迭代此邻接矩阵A中的每一行和每一列。如果您不熟悉这种表示法，可以将i、j=1和N视为编程语言中的for循环。在Python中可以这样写：Whatis#stuffwithiandj(thestuffwithiandj)inthecode?括号中的内容表示A_ij减去(k_ik_j)/2L。A_ij指的是邻接矩阵中第i行第j列的值。k_i和k_j指的是每个顶点的度数——可以通过对每一行和每一列的条目求和来获得。将两者相乘除以2L表示随机分配网络时顶点i和j之间的预期边数。总的来说，括号中的项表示随机组合时网络的真实结构与预期结构之间的差异。研究其值可知，当A_ij=1且(k_ik_j)/2L较小时，返回最高值。这意味着当顶点i和j之间存在“意外”边时，结果值会更高。最后，我们将括号中的项乘以δc_i，c_j。δc_i,c_j是著名但几乎无害的Kronecker-delta函数。这是一个Python解释：是的，就是这么简单。Kroneckerdelta函数有两个参数。如果两个参数相等则返回1，不相等则返回0。即如果顶点i和j已经被放入同一个簇中，则δc_i,c_j=1；否则它们不在同一个簇中，函数返回0。当我们将括号中的项与Kroneckerdelta函数相乘时，我们发现对于嵌套和Σ，当存在大量“意外（unexpected）”时是当连接顶点的边被分配给同一个集群时最高。因此，模块化是衡量图形聚类成不同组的程度的指标。除以2L将模块化的上限设置为1。接近或小于0的模块化表示网络的当前聚类没有用。模块化程度越高，网络聚类到不同的组中的效果就越好。通过最大化模块化，我们可以找到集群该网络的最佳方式。请注意，我们必须预先定义图的聚类方式，以便找到一种方法来评估聚类的好坏。不幸的是，使用蛮力尝试每一种可能的聚类方法来找到最高的模块化分数是计算密集型的，即使在有限的样本量下也是不可能的。组合学告诉我们，对于一个只有8个顶点的网络，有4140种不同的聚类方式。一个由16个顶点组成的网络可以以超过100亿种方式聚类。对于具有32个顶点的网络，有超过128septillion(10^21)种可能的聚类方法；如果你的网络有80个顶点，那么可能的聚类方法的数量超过了可观察宇宙中可能的聚类方法的数量。原子数。因此，我们必须求助于一种启发式方法，该方法可以很好地评估产生最高模块化分数的集群，而无需尝试所有可能性。这是一种称为Fast-GreedyModularity-Maximization的算法，它有点类似于上面介绍的凝聚层次聚类算法。只不过Mod-Max并不是根据距离来融合分组，而是根据模块化的变化来分组。它是这样工作的：首先最初将每个顶点分配给它自己的社区，然后计算整个网络的模块化M。步骤1要求每个社区对至少由一条边连接。如果合并两个社区，算法会计算由此产生的模块性变化ΔM。第二步，取ΔM增幅最大的组对，然后进行融合。然后为该集群计算并记录新的模块化M。重复步骤1和2——每次融合组对，使你最终获得最大增益ΔM——然后记录新的聚类模式及其相应的模块化分数M。当所有顶点被分组到一个巨大的集群时停止。该算法然后检查流程中的记录并找到返回最高M值的聚类模式。这是返回的组结构。4.更多细节：哇！这个过程的计算量实在是太大了，至少对我们人类来说是这样。图论提出了许多计算上困难的问题，通常是NP-hard，但它也具有为复杂系统和数据集提供有价值的见解的巨大潜力。拉里佩奇知道这一点，他的著名的PageRank算法完全基于图论——该算法帮助谷歌在不到十年的时间里从初创公司成长为近乎世界的统治者。社区检测是图论中的一个热门研究领域，Modularity-Maximization有很多替代方案（虽然有用，但也有缺点）。首先，它的聚合方式是从指定规模的小群体开始，然后逐渐转移到越来越大的群体。这称为分辨率限制-该算法不会搜索小于特定大小的组。另一个挑战是性能超过一个显着的峰值，Mod-Max方法往往会产生许多高模块化分数的“平台”，这有时会导致难以确定最大分数。其他算法使用不同的方式来确定组。Edge-Betweenness是一种分裂算法，它将所有顶点聚集到一个大簇中。它迭代地删除网络中“最不重要”的边数据，直到所有顶点都被分离。这个过程产生层次结构，其中相似的顶点在结构中彼此靠近。另一种算法是CliquePercolation，它考虑了图cliques之间可能的重叠。虽然其他算法基于图中的随机游走，但也有谱聚类算法：从邻接矩阵和派生矩阵的特征分解开始。这些方法应用于计算机视觉等特征提取任务。给出每种算法的深入应用示例超出了本介绍的范围。从数据中提取可用信息的有效方法在几十年前是难以捉摸的，但现在是一个非常活跃的研究领域。4.结语希望这篇文章能给你启发，让你更好地理解机器是如何理解大数据的。未来是一个快速变化的时代，其中许多变化将由下一代或两代的有能力的技术驱动。正如引言中提到的，机器学习是一个非常有前途的研究领域，需要以准确有效的方式解决大量复杂的问题。当由机器完成时，人类可以轻松完成的任务需要创新的解决方案。我们在这方面还有很多工作要做，谁为下一个重大突破做出贡献，无疑将获得丰厚的回报。也许读到这篇文章的人会成为下一个强大的算法发明者？所有伟大的想法都是从头开始的。原文：https://medium.freecodecamp.com/how-machines-make-sense-of-big-data-an-introduction-to-clustering-algorithms-4bd97d4fbaba【本文为机器之心专栏原创翻译,微信公众号《机器之心（id：almosthuman2014）》】点此阅读作者更多好文
