例如，每个聚类有几个离散点构成。我们可以将两个聚类间的距离定义为随便率性点间的最小(或最大年夜)距离，就如下图所示。还有其他办法定义连接标准，它们可能适应于不合的情景。

红/蓝：形心连接;红/绿：最小连接;绿/蓝：最大年夜连接

图集团检测(Graph Community Detection)

何时应用?

当你的数据可以被表示为一个收集或图(graph)时。

工作方法

下面给出了一小我门级的例子，这是一个简单直接的图，展示了我比来浏览过的 8 个网站，根据他们的维诽谤科页面中的链接进行了连接。这个数据很简单，你可以人工绘制，但对于更大年夜范围的项目，更快的方法是编写 Python 脚本。这里是我写的一个：https://raw.githubusercontent.com/pg0408/Medium-articles/master/graph_maker.py

图集团(graph community)平日被定义为一种顶点(vertice)的子集，个中的顶点相对于收集的其它部分要连接得加倍慎密。存在多种用于辨认图的算法，基于更具体的定义，个中包含(但不限于)：Edge Betweenness、Modularity-Maximsation、Walktrap、Clique Percolation、Leading Eigenvector……

图论是一个研究收集的数学分支，参考机械之心文┞仿《想懂得概率图模型?你要先懂得图论的根本定义与情势》。应用图论的办法，我们可以将复杂体系建模成为「顶点(vertice)」和「边(edge)」的抽象集合。

也许最直不雅的案例就是社交收集。个中的顶点表示人，连接顶点的边表示他们是同伙或互粉的用户。

然则，要将一个体系建模成一个收集，你必须要找到一种有效连接各个不合组件的方法。将图论用于聚类的一些立异应用包含：对图像数据的特点提取、分析基因调控收集(gene regulatory networks)。

这些顶点的色彩表示了它们的集团关系，大年夜小是根据它们的中间度(centrality)肯定的。可以看到谷歌和 Twitter 是最中间的吧?

别的，这些聚类在实际生活中也很有意义(一向是一个重要的表示指标)。黄色顶点平日是参考/搜刮网站，蓝色顶点全部是在线宣布网站(文┞仿、微博或代码)，而橙色顶点是 YouTube 和 PayPal——因为 YouTube 是由前 PayPal 员工创建的。机械还算总结得不错!

除了用作一种有效的可视化大年夜体系，收集的┞锋正力量是它们的数学分析才能。让我们将膳绫擎图片中的收集翻译成更数学的情势吧。下面是该收集的邻居矩阵(adjacency matrix)：

该邻居矩阵编码了该收集的所有属性——其给了我们开启所有有价值的看法的可能性的钥匙。起首，每一行或每一列的数字相加都能给你关于每个顶点的程度(degree)——即它连接到了若干个其它顶点，这个数字平日用字母 k 表示。类似地，将每个顶点的 degree 除以 2，则能获得边的数量，也称为链接(link)，用 L 表示。行/列的数量等于该收集中顶点的数量，称为节点(node)，用 N 表示。

只须要知道 k、L 和 N 以及该邻居矩阵 A 中每个单位的值，就能让我们计算出该收集的任何给定聚类的模块性(modularity)。

用 R 说话 3.3.3 版中的 igraph 绘制的图

模块性(modularity)是用于测量分区的「质量」的一种标准

这个公式有点复杂，但我们分化它，让我们可以更好地舆解。

M 就是我们要计算的模块性。

1/2L 告诉我们将后面的部分除以 2L，即收集中边的数量的两倍。

Σ 符号表示乞降，并且在该邻居矩阵 A 中的每一行和列长进行迭代。如不雅你对这个符号不熟悉，可以将 i, j = 1 和 N 懂得成编程说话中的 for-loop。在 Python 琅绫擎，可以写成如许：

代率攀琅绫擎的 #stuff with i and j(带有 i 和 j 的那一坨)是什么?

括号中的内容表示大年夜 A_ij 减去 ( k_i k_j ) / 2L。

k_i 和 k_j 是指每个顶点的 degree——可以经由过程将每一行和每一列的项加起来而获得。两者相乘再除以 2L 表示当该收集是随机分派的时刻顶点 i 和 j 之间的预期边数。

整体而言，括号中的项表示了该收集的┞锋实构造和随机组应时的预期构造之间的差。研究它的值可以发明，当 A_ij = 1 且 ( k_i k_j ) / 2L 很小时，其返回的值最高。这意味着，当在定点 i 和 j 之存放在一个「非预期」的边时，获得的值更高。

当我们将括号中的项与克罗内克 δ 函数相乘时，我们发明对于嵌套乞降 Σ，当有大年夜量「不测的(unexpected)」连接顶点的边被分派给同一个聚类时，其结不蚜?鲱高的。是以，模块性是一种用于衡量将图聚类成不合的集团的程度的办法。

最后，我们再将括号中的项和 δc_i, c_j 相乘。δc_i, c_j 就是大年夜名鼎鼎但根本无害的克罗内克 δ 函数(Kronecker-delta function)。下面是其 Python 解释：

　　推荐阅读

　　工业机器人四种编程技术，你知道几种？

一、概述当前机械人广泛应用于焊接、装配、搬运、喷漆及打磨等范畴，义务的复杂程度赓续增长，而用户对产品的质量、效力的寻求越来越高。在这种情势下，机械人的编程方法、编程效力和质量>>>详细阅读

本文标题：机器理解大数据的秘密：聚类算法深度详解

地址：http://www.17bianji.com/lsqh/34643.html

 1/2    1