机器如何理解大数据的解释：聚类算法简介 。看看下面的图片。 这是各种形状和大小的昆虫（蜗牛不是昆虫，但我们不会发现错误）的集合。 现在根据相似程度将它们分为几组。 没抓住 首先将蜘蛛分组。
做完了吗 尽管这里没有“正确”的解决方案，但您必须将这些生物分为四个类。 在一个群中有蜘蛛，在第二群中有一对蜗牛，在第三群中有蝴蝶，在第四群中有蜜蜂和黄蜂。
做得好吧？ 如果图片中的昆虫数量是原来的两倍，您可能会做同样的事情。 而且，如果您有足够的时间-或渴望昆虫学-那么您可能将数百只昆虫归为一类。
但是，对于一台机器而言，将十个对象分组为有意义的簇并不是一件容易的事。 归功于诸如
组合数学之类的复杂的数学分支，我们知道10种昆虫以115,975种方式进行了分组。 如果有20种昆虫，那么聚类选择的数量
将超过50万亿 。
对于一百种昆虫，可能的解决方案的数量将大于
已知宇宙中基本粒子的
数量 。 还有多少 据我估计，大约有
五千亿亿倍 。 事实证明，有超过
四十亿个Google解决方案（
什么是Google？ ）。 这仅适用于数百个对象。
几乎所有这些组合都是毫无意义的。 尽管解决方案数量惊人，但是您自己却很快找到了几种有用的集群方法之一。
我们人类认为我们拥有出色的编目和理解大量数据的能力。 不管是文本，屏幕上的图片还是一系列对象，人们都可以有效地理解来自周围世界的数据。
鉴于AI开发和机器学习的一个关键方面是机器可以快速理解大量输入数据，我如何提高工作效率？ 在本文中，我们将考虑三种聚类算法，机器可以使用它们来快速理解大量数据。 这个列表还远远不够完整-还有其他算法-但是从它开始已经很有可能。
对于每种算法，我将描述它何时可以使用，如何工作，并通过逐步分析给出一个示例。 我相信，要对算法有个真正的了解，您需要自己重复一下它的工作。 如果您
真的感兴趣 ，您将意识到最好在纸上运行算法。 行动起来，没人会怪你！
k = 3的三个可疑的整齐簇K均值聚类
使用者：
当您了解可以找到多少组以查找
预定 （先验）时。
运作方式：
该算法将每个观察随机分配给
k个类别之一，然后计算每个类别的
平均值 。 然后，他将每个观察值重新分配给具有最接近平均值的类别，然后再次计算平均值。 重复该过程，直到需要重新分配为止。
工作示例：
拿一个由12名球员组成的小组以及每个球员在当前赛季得分的进球数（例如，从3到30）。 例如，我们将玩家分为三个类。
步骤1 ：您需要将玩家随机分为三组，并计算每组的平均值。
Group 1 Player A (5 goals), Player B (20 goals), Player C (11 goals) Group Mean = (5 + 20 + 11) / 3 = 12 Group 2 Player D (5 goals), Player E (3 goals), Player F (19 goals) Group Mean = 9 Group 3 Player G (30 goals), Player H (3 goals), Player I (15 goals) Group Mean = 16
步骤2 ：将每个玩家重新分配到最近的平均值组中。 例如，玩家A（5个进球）进入第二组（平均= 9）。 然后我们再次计算组平均值。
Group 1 (Old Mean = 12) Player C (11 goals) New Mean = 11 Group 2 (Old Mean = 9) Player A (5 goals), Player D (5 goals), Player E (3 goals), Player H (3 goals) New Mean = 4 Group 3 (Old Mean = 16) Player G (30 goals), Player I (15 goals), Player B (20 goals), Player F (19 goals) New Mean = 21
一次又一次
重复步骤2，直到玩家停止更改组。 在此人工示例中，这将在下一次迭代中发生。
别说了 您已经从数据集中形成了三个聚类！
Group 1 (Old Mean = 11) Player C (11 goals), Player I (15 goals) Final Mean = 13 Group 2 (Old Mean = 4) Player A (5 goals), Player D (5 goals), Player E (3 goals), Player H (3 goals) Final Mean = 4 Group 3 (Old Mean = 21) Player G (30 goals), Player B (20 goals), Player F (19 goals) Final Mean = 23
分组应与场上球员的位置相对应-后卫，中后卫和前锋。 K均值在此示例中起作用是因为有理由相信数据将被分为这三类。
因此，基于性能的统计差异，机器可以为任何团队运动证明运动员在场上的位置。 这对于体育分析以及其他将数据集划分为预定义组有助于得出适当结论的其他任务很有用。
所描述算法有几种变体。 团簇的初始形成可以以各种方式进行。 我们检查了玩家的随机分组，然后计算了平均值。 结果，初始组平均值彼此接近，这增加了可重复性。
另一种方法是形成仅由一个玩家组成的集群，然后将玩家分组到最近的集群中。 所得的簇更依赖于形成的初始阶段，并且具有高变异性的数据集中的重复性降低。 但是使用这种方法，完成算法所需的迭代次数可能更少，因为花在拆分组上的时间会更少。
k均值聚类的明显缺点是，您需要
预先猜测有多少个聚类。 有一些评估一组特定群集的符合性的方法。 例如，集群内平方和是每个集群内变异性的度量。 群集“越好”，群集内的总平方和越低。
层次聚类
使用者：
当您需要揭示值之间的关系（观测值）。
运作方式：
计算距离矩阵，其中单元格（
i，j ）的值是
i和
j值之间的距离的度量。 然后，取一对最接近的值并计算平均值。 创建一个新的距离矩阵，将成对的值组合到一个对象中。 然后从该新矩阵中获取一对最接近的值，并计算出新的平均值。 重复该循环，直到将所有值分组。
工作示例：
采取极为简化的数据集，其中包含多种鲸鱼和海豚。 我是一名生物学家，可以向您保证，将使用更多的属性来构建
系统树 。 但对于我们的示例，我们将自己限制在六种海洋哺乳动物的特征体长上。 将有两个计算阶段。
步骤1 ：计算所有视图之间的距离矩阵。 我们将使用欧几里得度量标准来描述我们的数据之间的距离，例如地图上的居民点。 通过读取相应列和行的交点处的值，可以得到每对主体的长度差异。
步骤2 ：取一对彼此最接近的两个物种。 在这种情况下，它是宽吻海豚和灰海豚，平均体长为3.3 m。
我们重复步骤1，再次计算距离矩阵，但是这次我们将宽吻海豚和灰海豚合并为一个体长为3.3 m的对象。
现在我们重复步骤2，但是有一个新的距离矩阵。 这次，灰鲸和虎鲸将是最接近的，所以让我们将它们成对放置，并计算出平均值-7 m。
接下来，重复步骤1：再次计算距离矩阵，但将鲸鱼和虎鲸以7 m体长的单个对象的形式存在。
对此矩阵重复步骤2。 最小的距离（3.7 m）将在两个组合对象之间，因此我们将它们组合成一个更大的对象，并计算出平均值5.2 m。
然后重复步骤1，并结合宽吻海豚/灰海豚与磨碎/虎鲸来计算新矩阵。
重复第2步。座头鲸和尾鳍之间的最小距离（5 m），因此我们将它们合并并计算出平均值-17.5 m。
再次执行步骤1：计算矩阵。
最后，重复步骤2-仅剩一个距离（12.3 m），因此我们将每个人团结成一个物体并停下来。 这是发生了什么：
[[[BD, RD],[PW, KW]],[HW, FW]]
该对象具有分层结构（请记住
JSON ），因此可以将其显示为树形图或树状图。 结果类似于家谱。 一棵树上的两个值越接近，它们越相似或联系得越紧密。
使用R-Fiddle.org生成的简单树状图树状图的结构使您可以了解数据集本身的结构。 在我们的示例中，我们有两个主要分支-一个带有座头鲸和finwal，另一个带有宽吻海豚/灰海豚和磨碎/虎鲸。
在进化生物学中，具有许多物种和大量特征的更大数据集被用于识别分类学关系。 在生物学之外，层次聚类应用于数据挖掘和机器学习领域。
此方法不需要预测所需的群集数量。 您可以将生成的树状图拆分为簇，将树“修剪”到所需的高度。 您可以根据所需的数据群集分辨率以不同方式选择高度。
例如，如果上述树状图在高度10处被切除，则我们将与两个主要分支相交，从而将树状图分为两列。 如果在高度2处切割，则将树状图分为三个簇。
其他分层聚类算法可能在三个方面与本文所述的不同。
最重要的是方法。 在这里，我们使用了
凝聚法：从单个值开始，然后将它们循环聚类，直到得到一个大的聚类。 另一种方法（计算上更复杂）表示相反的顺序：首先创建一个巨大的簇，然后将其顺序划分为越来越小的簇，直到剩下单独的值为止。
还有几种计算距离矩阵的方法。 欧几里得度量足以完成大多数任务，但
其他度量则更适合某些情况。
最后，链接标准可能会有所不同。 群集之间的关系取决于它们彼此之间的接近程度，但是“接近度”的定义可以不同。 在我们的示例中，我们测量了每个组的平均值（或“质心”）之间的距离，并将最接近的组成对组合。 但是您可以使用另一个定义。
假设每个群集由几个离散值组成。 可以将两个群集之间的距离定义为它们的任何值之间的最小（或最大）距离，如下所示。 对于不同的上下文，使用连接条件的不同定义很方便。
红色/蓝色：质心池； 红色/绿色：基于最小值的组合； 绿色/蓝色：根据高点合并。图形中社区的定义（图形社区检测）
使用者：
您的数据何时可以网络或“图形”的形式呈现。
运作方式：
图中的社区可以粗略地定义为顶点的子集，这些顶点彼此之间的联系比与网络其余部分的联系更多。 基于更具体的定义，有不同的社区定义算法，例如边之间的间隔，最大模块化，Walktrap，集团渗透，前导特征向量...
工作示例：
图论是数学中一个非常有趣的部分，它使我们能够以由“线”（边）连接的“点”（顶点，节点）的抽象集合的形式对复杂的系统进行建模。
可能想到的图形的第一个应用是对社交网络的研究。 在这种情况下，山峰代表通过肋骨与朋友/订户联系的人。 但是，如果您可以证明有意义的组件连接方法是合理的，则可以想象网络形式的任何系统。 使用图论进行聚类的创新应用包括从视觉数据中提取属性并分析遗传调控网络。
作为一个简单的示例，让我们看一下下面的图。 这显示了我最常访问的八个站点。 它们之间的链接基于Wikipedia文章中的链接。 可以手动收集此类数据，但是对于大型项目，编写Python脚本要快得多。 例如，这是：
https :
//raw.githubusercontent.com/pg0408/Medium-articles/master/graph_maker.py 。
该图是使用适用于R 3.3.3的igraph包构建的山峰的颜色取决于社区的参与程度，其大小取决于中心性。 请注意，最核心的是Google和Twitter。
而且，生成的群集非常准确地反映了实际任务（这始终是性能的重要指标）。 代表链接/搜索站点的顶点以黄色突出显示； 蓝色突出显示的在线出版物网站（文章，推文或代码）； 用红色突出显示的是由前PayPal员工创建的PayPal和YouTube。 对电脑好扣！
除了可视化大型系统外，网络的真正功能还在于数学分析。 首先，将网络图片转换为数学格式。 以下
是网络
的邻接矩阵。
列和行的交点处的值指示在这对顶点之间是否存在边。 例如，在Medium和Twitter之间，因此在此行和列站立的交点处为1。在Medium和PayPal之间没有边，因此在相应的单元格中为0。
如果我们以邻接矩阵的形式表示网络的所有属性，这将使我们得出各种有用的结论。 例如，任何列或行中的值之和表示每个顶点的
程度 -即连接到该顶点的对象数。 通常用字母
k表示 。
如果我们将所有顶点的度数相加并除以2，则得出L-网络中边的数量。 行和列的数量等于N-网络中顶点的数量。
仅知道k，L，N和邻接矩阵A的所有像元中的值，我们就可以计算任何聚类的模块化。
假设我们已将一个网络集群为多个社区。 然后，您可以使用模块化值来预测群集的“质量”。 较高的模块化表明我们将网络划分为“精确”社区，而较低的模块化则表明集群是偶然而非合理地形成的。 为了更清楚：
模块化是衡量群体“质量”的标准。
模块化可以使用以下公式计算：
让我们看一下这个非常棒的公式。
如您所知
M ，这是模块化。
1 / 2L系数意味着我们将公式的“主体”的其余部分除以2L，即除以网络中边的两倍。 在Python中，可以这样写：
sum = 0 for i in range(1,N): for j in range(1,N): ans =
#stuff with i and j是什么？ 方括号中的位告诉我们从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): if ci == cj: return 1 else: return 0 Kronecker_Delta("A","A")
是的，很简单。 该函数接受两个参数，如果它们相同，则返回1，否则返回0。
换句话说，如果顶点i和j属于一个簇，则δc_i，c_j =1。如果它们位于不同的簇中，则函数将返回0。
由于我们将括号的内容乘以Kronecker符号，所以当一个簇中的顶点通过大量“意外”边缘相连时，总和
∑的结果将最高。 因此，模块性是图形被聚类到各个社区的程度的指标。
2L除法将上层模块性限制为统一。 如果模块化接近于0或负数，则意味着网络的当前群集没有意义。 通过增加模块化，我们可以找到更好的集群网络方法。
请注意，为了评估对图进行聚类的“质量”，我们需要预先确定如何对图进行聚类。 不幸的是，除非样本很小，否则由于计算复杂性，在物理上不可能愚蠢地通过比较它们的模块性来愚弄所有将图聚类的方法。
组合法表明，对于具有8个顶点的网络，有4,140种聚类方法。 对于具有16个顶点的网络，已经有超过100亿种方法，对于具有32个顶点，128九亿个顶点的网络，对于具有80个顶点的网络，聚类方法的
数量将超过
可观察到的宇宙中的原子数量 。
因此，我们将使用启发式方法代替枚举，这将有助于相对容易地计算具有最大模块化的聚类。 这是一种称为
快速贪婪模块化最大化的算法，类似于上述凝聚式层次聚类算法。 Mod-Max并非根据邻近性进行组合，而是根据模块化的变化来统一社区。 运作方式：
首先，将每个顶点分配给它自己的社区，并计算整个网络的模块化-M。
步骤1 ：对于通过至少一条边连接的每对社区，该算法在组合这些社区对的情况下计算模块化ΔM的结果变化。
步骤2 ：然后取一对，当组合时，ΔM将最大并组合。 对于此群集，将计算并存储新的模块化。
重复步骤1和2：每次加入一对社区，这会产生最大的ΔM，同时会采用新的聚类方案及其M。
将所有顶点分组为一个大簇时，迭代
停止 。 现在，该算法将检查存储的记录，并找到具有最高模块化的聚类方案。 她是作为社区结构返回的。
至少对于人来说，这在计算上很困难。 图论是困难的计算问题和NP困难问题的丰富来源。 使用图，我们可以得出许多有关复杂系统和数据集的有用结论。 Ask Larry Page的PageRank算法完全基于图论，该算法帮助Google在不到一代人的时间里从一家初创企业转变为全球主导企业。
今天，关于图论的研究集中于识别社区。 模块化最大化算法有多种选择，尽管有用，但并非没有缺点。
首先，采用集结方法，将定义明确的小型社区合并为较大的社区。 这称为分辨率限制-算法不会分配小于特定大小的社区。 另一个缺点是，Mod-Max算法不是一个明显的，易于实现的全局峰值，而是试图从许多接近的模块化值中生成一个宽广的“平台”。 结果，很难选出获胜者。
其他算法使用不同的方法来定义社区。 例如，“边缘之间的间隔”是一种划分（划分）算法，首先将所有顶点分组为一个巨大的簇。 然后，迭代删除最不重要的边缘，直到所有顶点都被隔离为止。 结果是一个层次结构，在这些层次中，顶点越相似，它们彼此之间就越靠近。
Clique Percolation算法考虑了社区之间可能的交集。 有一组基于图上
随机游走的算法，并且有一些
光谱聚类方法可以处理邻接矩阵和从中得出的其他矩阵的光谱分解（本征分解）。 所有这些想法都用于突出功能，例如机器视觉中的功能。
我们不会详细分析每种算法的工作示例。 , , 20 .
结论
, - , , . , , 20-40 .
, — , . , , .
, , , , . , - , , ? - !