摘要：基于图的机器算法学习是一个强大的工具。结合运用模块特性，能够在集合检测中发挥更大作用。
可扩展集合检测
编者按：基于图的机器算法学习是一个强大的工具。结合运用模块特性，能够在集合检测中发挥更大作用。
很多复杂的问题都可以使用图来表示和学习----社交网络，细菌行为，神经网络等等。本文探讨了图中节点
自发地形成内部密集链接（在此称为“集合”）的趋势; 生物网络的显着的和普遍的属性。
集合检测旨在将图划分为密集连接的节点的群集，其中属于不同集合的节点仅稀疏地连接。
图形分析涉及到节点（描述为磁盘）的研究及其与其他节点（线）的交互。 社区检测旨在通过其“团体”对节点进行分类。
模块化的公式为：
其中：nc是集合的数量; lc为边数; dc为顶点度和; m是图的大小（边数）。 我们将使用这个方程以寻找最佳分区的全局度量。 简而言之：更高的分数将被给予一个集合配置提供更高于外部的内部链接。
那么该如何进行优化呢？优化方案的重点是利用图形拓扑知识。我这里使用了一个特殊的算法簇，称为聚合。这些算法能够很快捷地将节点收集（或合并）。 这具有许多优点，因为它通常仅需要邻近节点的第一级知识和小的增量合并步骤，便可使全局解决方案朝向逐步平衡。您可能会指出，模块度量提供了图形状态的全局视图，而不是本地指示器。 那么，这如何转化为我刚才提到的小地方增量？
基本方法确实包括迭代地合并优化局部模块化的节点，让我们继续定义：
其中Σin是C内的加权链路的总和，Σtot对链接到C的节点进行求和，k i对链接到节点i,ki的节点进行求和，m为 归一化因子作为整个图的加权链接的和。
这个局部优化函数可以很容易地转换为图表域内的可解释的度量。 例如，
• 集合强度：集合中的加权链接的总和。
• 集合人气：对特定集合中的节点的加权链接事件的总和。
• 节点所属：从节点到社区的加权链接的总和。
换句话说，加权链接可以是在运行时计算的节点的类型的函数（如果你处理具有各种类型的关系和节点的多维图，则是有用的）。
压缩阶段之前的收敛迭代示例
现在我们都设置了我们的优化函数和局部成本，典型的聚集策略包括两个迭代阶段（传输和压缩）。假设N个节点的加权网络，我们开始通过向网络的每个节点分配不同的集合。
传输：对于每个节点i，考虑其邻近节点j，并通过交换c_i为c_j来评估模块化的增益。贪婪过程将节点传送到相邻集合，使模块化的增益最大化（假设增益为正）。该过程应用于所有节点，直到没有单独的移动点。
压缩：构建一个新的网络，其节点是在第一阶段发现的集合;称为压缩的过程（见下图）。为此，集合之间的边权重被计算为对应的两个集合中的节点之间的内部边之和。
聚集过程：阶段1收敛到局部模块化的局部平衡。 第二阶段包括压缩下一次迭代的图形，因此减少了要考虑的节点数量，同时也减少了计算时间。
需要解决的关键问题：因为这是一个贪婪的算法，你必须根据你的情况和手头的数据定义一个停止标准。
如何定义这个标准？ 可以尝试的方式有：最大数量的迭代，在传输阶段期间的最小模块性增益，或任何其他相关的信息。仍然不确定什么时候停止？ 只要确保你保存迭代过程的每个中间步骤，运行直到你的图形中只剩下一个节点。 有趣的是，通过跟踪每个步骤，您还可以从您的集合的层次视图中获益，然后作进一步探索和利用。
在后续的博文中，我将讨论如何在使用Spark GraphX的分布式系统上实现这一点，Spark GraphX是我的项目的一部分。
文章原标题《Graph-based machine learning: Part I》，作者：Sebastien Dery
文章为简译，更为详细的内容，请查看原文：insightdatascience
本文由北邮@爱生活-爱可可老师推荐，阿里云云栖社区组织翻译。
网友评论