计算机如何感知大数据——聚类算法

编译：伯乐在线 - LynnShaw，英文：Peter Gleeso

http://blog.jobbole.com/113745/

看看下面这张图片。这是一个不同形状大小的昆虫的集合。花点时间按照相似程度将它们分成几组。

这不是什么很有技巧性的问题。 我们从把蜘蛛分到一起开始。

图片来自Google图片搜索，标记以便重用

做完了吗？虽然这里没有必要有所谓的正确答案，不过你极有可能将这些虫子分成四组。蜘蛛分成一组，蜗牛一组，蝴蝶和蛾子一族，黄蜂和蜜蜂总共三个一组。

不算太糟糕，是吧？如果虫子数量是这个的两倍你可能还是会这么分，对吧？如果你有空余的时间——或者对昆虫学的热情——你甚至可能用相同方法对一百年个虫子这样分类。

然而对一个机器来说，将十个目标分成多个有意义的群组是个不小的任务，多亏了数学中一个令人费解的分支组合数学，它告诉我们将十个昆虫分组共有115975种不同的可能。如果对二十个虫子进行分组，将会有超过五十万亿种不同的可能。

如果对一百个虫子分类——方案数将是宇宙中粒子的数量的很多倍。多少倍呢？通过我的计算，大概是5*10的35次方倍。事实上，有四千万亿googol多种方案（什么是googol?）。仅仅是一百个目标。

而这些方案几乎都是没有意义的——虽然从这些数量异常庞大的可能的选择中，你可以很快地找到为数不多的对虫子分类的有用的方式。

我们人类理所当然的可以很快地对大量数据理解并分类。无论是一段文字，或者屏幕上的图像，或是一系列的目标——人类通常可以相当有效地搞清世界给我们的任何数据。

鉴于发展人工智能和机器学习的一个关键方面就是让机器迅速理解庞大的输入数据集，那么有什么捷径吗？在这本文中，你将会看到三个聚类算法，机器可以这些算法快速理解大型数据集。这决不是一个详尽的清单——还有很多其他的算法——但这三个算法代表了一个良好的开端！

当你想要使用它们的时候，你会得到对于每一个问题的总结，一个总体的功能介绍以及一个更细致的，一步一步实现的例子。我相信在现实中实现对于理解是非常有帮助的。如果你真的很喜欢这些，你会发现最好的学习方式是用笔和纸。加油去吧——没人评判哪种方式更好！

三个整齐的聚类，K=3

K-均值聚类

适用场景：

预先已经知道要分成多少组。

如何工作：

算法首先将每一个观测点随机地分配到K个类别中的一个，然后计算每一个类别的均值。下一步，在重新计算均值之前算法将每一个点重新分配给均值与该点数据最接近的类别。不断重复这一步直到不需要再重新分配。

实现例子：

考虑有12个足球运动员的一个足球队，这些运动员每个人在本赛季都获得了一定的进球数（3-30之间）。现在我们来将他们分成三个单独的聚类。

第一步需要我们随机地将这些运动员分成三组并计算每组的均值。

Group1

PlayerA(5goals),PlayerB(20goals),PlayerC(11goals)

GroupMean=(5+20+11)/3=12

Group2

PlayerD(5goals),PlayerE(3goals),PlayerF(19goals)

GroupMean=9

Group3

PlayerG(30goals),PlayerH(3goals),PlayerI(15goals)

GroupMean=16

第二步：对每一个运动员，将它们重新分配到均值离他们最近的组。即，运动员A（进球数5）被分配到第2个组（均值=9）。然后重新计算这几组的均值。

Group1(OldMean=12)

PlayerC(11goals)

NewMean=11

Group2(OldMean=9)

PlayerA(5goals),PlayerD(5goals),PlayerE(3goals),PlayerH(3goals)

NewMean=4

Group3(OldMean=16)

PlayerG(30goals),PlayerI(15goals),PlayerB(20goals),PlayerF(19goals)

NewMean=21

不断重复第二步直到所有组的均值不再变化。对于这个有些不太好的例子，下一次重复就会达到终止条件。停止！现在你已经形成三个聚类的数据集！

Group1(OldMean=11)

PlayerC(11goals),PlayerI(15goals)

FinalMean=13

Group2(OldMean=4)

PlayerA(5goals),PlayerD(5goals),PlayerE(3goals),PlayerH(3goals)

FinalMean=4

Group3(OldMean=21)

PlayerG(30goals),PlayerB(20goals),PlayerF(19goals)

FinalMean=23

在这个例子中，聚类可能对应于球员在场上的位置——如后卫、中场和前锋。k-均值在这里使用因为我们合理地预期数据可以分成这三类。

通过这种方式，给出一系列性能统计数据，机器可以合理地评估任何团体运动中运动员的位置——这对运动分析很有用，对任何其他的将数据集按照预定义的组别进行分类也可以提供相关的见解。

细节：

这个算法有一些变体。对聚类进行“seeding”的初始化方法有好几种方式。在这里，我们将每个球员随机分配到一个小组，然后计算出这些组的均值。这会导致初始生成的组之间的均值很接近，致使后面有更多重复步骤。

另一种方法是初始化每个聚类时只分配一个球员，然后将其它球员分配到最近的聚类。这样返回的聚类比初始化seeding得到的聚类更有意义，降低了变化很大的数据集中的重复性。但是，这种方法可能会减少完成算法所需的迭代次数，因为这些组将花费较少的时间完成收敛。

K-均值聚类的一个明显的缺点是你必须提供关于你期望找到多少个聚类的先验假设。 有一些方法可以评估一组特定的聚类结果。 例如，聚类内平方和（Within-ClusterSum-of-Squares）是每个聚类内方差的度量。 聚类效果越好，整体WCSS越低。

层次聚类

什么时候使用：

…你希望发掘出你的观测数据之间的潜在关系。

如何工作：

计算距离矩阵，其中矩阵元素(i,j)的值是观察值i和j之间的距离度量值。 然后，将最接近的两个观察值进行配对并计算其平均值。通过将配对的观测值合并成一个单一的对象，形成一个新的距离矩阵。 从这个距离矩阵中，配对最近的两个观察值并计算它们的平均值。 重复这个过程，直到所有的观察结果合并在一起。

实例：

这是一个关于鲸鱼和海豚物种选择的超简化数据集。作为一名训练有素的生物学家，我可以向您保证，我们通常会使用更多更详细的数据集来重建系统发生树。 现在我们来看看这六种物种的典型体长。 我们将只使用两个重复的步骤。

Species Initials Length(m)

Bottlenose DolphinBD3.0

Risso'sDolphinRD3.6

Pilot WhalePW6.5

Killer WhaleKW7.5

Humpback WhaleHW15.0

Fin WhaleFW20.0

步骤1：计算每个物种之间的距离矩阵。在这里，我们将使用欧式距离——数据点之间的距离。你可以计算出距离就像在道路图上查看距离图一样。可以通过读取相关行和列的交点处的值来查找任何物种对之间的长度差异。

BD RD PW KW HW

RD0.6

PW3.52.9

KW4.53.91.0

HW12.011.48.57.5

FW17.016.413.512.55.0

步骤1：计算每个物种之间的距离矩阵。在这里，我们将使用欧式距离——数据点之间的距离。你可以计算出距离就像在道路图上查看距离图一样。可以通过读取相关行和列的交点处的值来查找任何物种对之间的长度差异。

BD RD PW KW HW

RD0.6

PW3.52.9

KW4.53.91.0

HW12.011.48.57.5

FW17.016.413.512.55.0

步骤2：配对两个最接近的物种。在这里，两个最接近的物种是宽吻海豚和灰海豚，平均长度为3.3米。

重复步骤1重新计算距离矩阵，但是这次将宽吻海豚和灰海豚合并成长度为3.3m的单个对象。

[BD,RD]PW KW HW

PW3.2

KW4.21.0

HW11.78.57.5

FW16.713.512.55.0

接下来，用这个新距离矩阵重复步骤2。现在，距离最小的是领航鲸与逆戟鲸，所以我们计算他们的平均——7.0米。

然后，我们重复第1步——重新计算距离矩阵，但是现在我们已经将领航鲸与逆戟鲸合并成了一个长度为7.0米的单个对象。

[BD,RD][PW,KW]HW

[PW,KW]3.7

HW11.78.0

FW16.713.05.0

接下来，我们用这个距离矩阵重复步骤2。最小距离是两个合并对象之间的（3.7米）——现在我们将它们合并成一个更大的对象，并取平均值（即5.2米）。

然后，我们重复步骤1并计算一个新的距离矩阵，合并了宽吻海豚和灰海豚与领航鲸与逆戟鲸。

[[BD,RD],[PW,KW]]HW

HW9.8

FW14.85.0

接下来，我们重复步骤2。最小的距离（5.0米）在座头鲸与长须鲸之间，所以我们将它们合并成一个单一的对象，取平均值（17.5米）。

然后，返回步骤1——计算距离矩阵，座头鲸与长须鲸已经合并。

[[BD,RD],[PW,KW]]

[HW,FW]12.3

最后，我们重复步骤2——在这个矩阵中只有一个距离（12.3米），我们把所有东西都放在一个大对象中，现在我们可以停下来了！我们来看看最后的合并对象：

[[[BD, RD],[PW, KW]],[HW, FW]]

它有一个嵌套的结构（可以认为是JSON），可以把它绘制成一个树状的图形或者树形图。 它读取的方式与家谱相同。 两个观察结果在树上离得越近，就被认为是更相似或更密切相关的。

在R-Fiddle.org上生成一个简单的树状图

树状图的结构使我们能够深入了解数据集的结构。在我们的例子中，我们看到两个主要分支，一个分支是 HW 和 FW，另一个是 BD、RD、PW、KW。

在进化生物学中，具有更多样本和测量的更大的数据集以这种方式被用来推断它们之间的分类关系。 除了生物学之外，层次聚类在数据挖掘和机器学习环境中也有应用。

很酷的是，这种方法不需要假设你正在寻找的聚类数量。 您可以通过在给定高度“切割”树来将返回的树形图划分为聚类。 这个高度可以通过多种方式进行选择，具体取决于你希望对数据进行聚类的分辨率。

例如，从上面的树状图可以看出，如果我们在高度为10的情况下绘制一条水平线，我们就会将两条主要分支分割，将树状图分成两个子图。 如果我们在高度= 2切割，树状图就被分成三个聚类。

细节：

关于层次聚类算法可以出现的变化，基本上有三个方面。

最根本的是方法——在这里，我们使用了一个凝聚的过程，我们从单个数据点开始，并将它们迭代地聚集在一起，直到剩下一个大聚类。 另一种（但是计算量更大）的方法是从一个大聚类开始，然后将数据分成越来越小的聚类，直到剩下孤立的数据点为止。

还有一系列的方法可以用来计算距离矩阵。 很多情况下，欧几里得距离（参考毕达哥拉斯定理）就足够了，但是在某些情况下还有其他可能更适用的选择。

最后，连接标准也可以变化。 聚类根据彼此之间的距离而相互连接，但是我们定义“近”的方式是灵活的。 在上面的例子中，我们测量了每个组的平均值（或“质心”）之间的距离，并将最近的组进行配对。 但是， 你可能想要使用其他的定义。

例如，每个聚类由多个离散点组成。 我们可以将两个聚类之间的距离定义为任意点之间的最小（或最大）距离——如下图所示。 还有其他方法来定义连接标准，它们可能适用于不同的环境。

红/蓝：形心连接；红色/绿色：最少连接；绿/蓝：最大连接

图社区发现

什么时候使用：

…你可以将数据表示为网络或“图”的时候。

如何工作：

图中的社区通常被定义为与网络其余部分相比，彼此连接更多的顶点的子集。 存在各种算法来基于更具体的定义来识别社区。 算法包括但不限于：Edge Betweenness，Modularity-Maximsation，Walktrap，Clique Percolation，Leading Eigenvector …

实现例子：

图论或网络的数学研究是数学的一个有趣的分支，它让我们将复杂系统建模为由“线”（或边）连接的“点”（或顶点）的抽象集合。

最直观的案例研究也许就是社交网络了。在这里，顶点代表人，边连接的是朋友/关注者的顶点。 然而，如果你能证明一个方法可以有意义地连接不同的部分，任何系统都可以被建模为一个网络。 图论中聚类的创新应用包括从图像数据中提取特征，分析基因调控网络。

作为一个入门级的例子，看看这个快速组合在一起的图。 它显示了我最近访问过的八个网站，根据它们各自的维基百科文章是否彼此连接而连接在一起。 您可以手动组合这些数据，但是对于大型项目，编写Python脚本执行相同的操作要快得多。这是我之前写的一个。

根据其社区成员对顶点进行着色，并根据其中心位置来确定大小。 看看Google和Twitter是最中心的吧？

而且，这些聚类在现实世界中也很有意义（一直一个重要的性能指标）。黄色的顶点通常是参考/搜索网站；蓝色顶点全部用于在线发布（文章，推文或代码）；红色的顶点包括YouTube，因为Youtube是由前PayPal员工创建的。 机器推论的不错！

除了作为有用的大型系统可视化的方式之外，网络的真正威力是其数学分析。 让我们开始把我们的这张网络图片变成一种更加数学的格式。 以下是网络的邻接矩阵。

GHGlMPQTWY

GitHub11

Google1111111

Medium11

PayPal111

Quora111

Twitter111111

Wikipedia11

YouTube111

每行和每列交点处的值记录该对顶点之间是否存在边。例如，Medium和Twitter之间存在一条边（惊喜！），所以它们的行/列相交的值是1。同样，Medium和PayPal之间没有边，所以它们行/列交点的值为0。

在邻接矩阵内进行编码就会得到这个网络的所有属性——它给了我们解锁各种有价值见解的钥匙。首先，将任意列（或行）相加，就可以得出每个顶点的度数——即连接了多少个顶点。通常用字母k表示。

同样，将每个顶点的度数相加并除以2得到L，即网络中边（或“连接”）的数量。行数/列数即网络中顶点（或“节点”）的数量，用N表示。

知道k，L，N和邻接矩阵A中每个单元的值，就可以计算任意给定的网络聚类的模块性。

假设我们已经将网络聚类成了一些社区。我们可以使用模块性评分来评估这个聚类的“质量”。更高的分数将表明我们已经把网络分成了“准确”的社区，而低分表明我们的聚类更随机。下面的图片说明了这一点。

模块性是衡量分区“质量”的指标。

模块性可以使用下面的公式计算：

这个公示包含相当数量的数学知识，但我们可以一点一点地分解它，使它更好理解。

M当然是我们正在计算的——模块性。

1/2L告诉我们把后面所有的东西除以2L，即网络中边的数量的两倍。到现在为止，一切都很好理解。

Σ符号告诉我们对右边的所有东西求和，并迭代邻接矩阵A中的每一行和列。对于那些不熟悉求和符号的人来说，i，j = 1和N的作用非常像编程中的嵌套for循环。在Python中，你可以这样写：

sum=

foriinrange(1,N):

forjinrange(1,N):

ans=#stuff with i and j as indices

sum+=ans

具体是什么？

括号里的东西告诉我们从A_ij中减去（k_i k_j）/ 2L。

A_ij是邻接矩阵中第i行第j列的值。

k_i和k_j的值是每个顶点的度数——通过将第i行和第j列中的项分别相加而得到。将它们相乘并除以2L得到如果网络是随机分布的顶点i和j之间的期望的边数。

总的来说，括号中的项表示网络的真实结构和随机重组的预期结构之间的差异。研究这个值表明，当A_ij = 1，（k_i k_j）/ 2L小的时候，它返回最大值。这意味着如果在顶点i和j之间存在“非预期”边缘，我们会看到更大的值。

最后，我们将括号中的项和后面几个符号相乘。

δc_i，c_j就是有名的Kronecker-delta函数。 这里是其Python解释：

def Kronecker_Delta(ci,cj):

ifci==cj:

return1

else:

return

Kronecker_Delta("A","A")#returns 1

Kronecker_Delta("A","B")#returns 0

是的——这真的很简单。Kronecker-delta函数有两个参数，如果相同则返回1，否则返回0。

这意味着如果顶点i和j已经被放入同一个聚类中，则δc_i，c_j = 1。否则，如果它们在不同的聚类中，则该函数返回0。

我们用这个Kronecker-delta函数乘以括号中的项，我们发现对于嵌套总和Σ，当分配给同一个聚类很多“非预期”的连接顶点的边时，其结果是最高的。因此，模块性是衡量图如何聚类到不同社区中的一种衡量标准。

除以2L这一操作将模块性的上限值界定为1。模块性分数接近或低于0表示网络的当前聚类实际上是无用的。模块性值越高，网络分散到不同社区的聚类越好。通过最大化模块性，我们可以找到聚类网络的最佳方式。

请注意，我们必须预先定义图形如何聚类，以找出聚类实际上的“好”。不幸的是，使用暴力对图的每一种可能的聚类方式进行计算，以找到

具有最高模块性分数的方式，即使是在有限样本大小的情况下也是不可能的。

组合学告诉我们，对于只有8个顶点的网络，有4140种不同的聚类方式。 规模两倍的16个顶点的网络将有超过一百亿种可能的聚集顶点的方式。再次将网络加倍（对一个非常适中的32个顶点）将会产生128 septillion （128*10^24）种可能的方式，而且有八十个顶点的网络的聚类方式将比宇宙中可观察的原子数还多。

所以，我们不得不转向一种启发式的方法，该方法在评估可以产生最高模块性分数的聚类方面做得相当不错，而不是尝试每一种可能性。 这是一种叫Fast-Greedy Modularity-Maximization的算法，它有点类似于上面描述的凝聚层次聚类算法。 “Mod-Max”不是根据距离进行合并，而是根据模块性的变化来合并。它是这样工作的：

首先将每个顶点分配到自己的社区，然后计算整个网络的模块性。

第一步要求每一个社区至少被一条单边连接，如果两个社区合并为一个，算法计算模块性的变化结果ΔM。

然后，步骤2将使得ΔM增加最多的一对社区合并。为这个聚类计算新的模块性M，并记录下来。

重复步骤1和2——每次合并产生最大ΔM增益的社区，然后记录新的聚类模式及其相关的模块性评分M。

当所有的顶点被分成一个大聚类时停下来。现在，算法检查它整个过程的记录，并确定返回最高值M的聚类模式。这就是返回的社区结构。

细节：

这需要进行的计算太多了，至少对于我们人类来说。图论中有丰富的计算难题，通常是NP-hard问题，但它也具有难以置信的潜力，为复杂的系统和数据集提供有价值的见解。与Larry Page同名的PageRank算法——帮助Google在不到一代人的时间里从初创阶段发展到了几乎统治世界——完全基于图论。

社区发现是当前图论研究的一个焦点问题，模块性最大化有许多替代方案，虽然有用，但也有一些缺点。

一开始，其聚集的方法往往将小而明确的社区吞并为大的社区。 这就是所谓的分辨率限制——算法不会在一定大小以内找到社区。 另一个挑战是，Mod-Max方法实际上倾向于产生许多具有类似的高模块性分数组成的“高原”，而不是一个独特的，易于到达的全局高峰值，这导致有时候难以确定最大分数。

其他算法使用不同的方式来定义和处理社区发现。Edge-Betweenness是一个分裂的算法，从所有顶点分组在一个大聚类开始。持续迭代去除网络中最不重要的边，直到所有的顶点都被分开。这个过程产生了一个层级结构，类似的顶点在层级结构中更接近。

另一种算法是Clique Percolation，它考虑了图社区之间可能的重叠。 还有另一组算法是基于图上的随机漫步，然后是谱聚类方法，它从邻接矩阵和由其导出的其它矩阵的特征分解开始研究。这些方法被用于例如计算机视觉等领域的特征提取。

给每个算法提供一个深入的实例，这已经远远超出了本文的范围。我想说的是，这是一个活跃的研究领域，它提供了强大的方法来理解数据，即使在十年前还是个非常困难的过程。

结论

希望这篇文章能够让你更好地理解机器如何理解大数据。未来瞬息万变，其中许多变化将由在下一代或两代中的产生的技术所驱动。

正如介绍中所概述的，机器学习是一个雄心勃勃的研究领域，其中大量复杂的问题需要尽可能准确和高效地解决。对于我们人类来说任何容易完成的任务都需要机器采取创新的解决方案。

这个领域内还有很大的进步空间，谁来贡献下一个突破的想法，无疑将会得到丰厚的回报。 也许读了这篇文章的某个人就会发明下一个强大的算法？所有伟大的想法都必须从某处开始！

觉得本文有帮助？请分享给更多人

关注「算法爱好者」，修炼编程内功