MMD_3a_CommunitiesInSN

SN means social network。

The first 12 videos cover this topic.

The first four videos are part of the basic track, and cover machine-learning techniques for finding the best set of “overlapping communities,” following the intuition that people generally belong to more than one community, e.g., their high-school friends, their coworkers, etc.

Videos 5-12 are part of the advanced track. They use concepts from linear algebra to explain how to break graphs optimally (i.e., break the fewest edges) into disjoint “communities.”

概述

实例

想要将社交网络所属的不同组给划分开来。

需要解决的问题

从AGM到Network

如何从模型推出社交网络

所谓社交网络,就是两个人U,V是不是朋友,或者理解成图论中的两个node是否需要连接。

模型

Community-Affiliation Graph

特点

flexibility

从AGM到bigClam

AGM是一种计算P(u,v),即u,v两个点之间是否有edge的概率。 同样的,bigClam也是计算两点间是否有edge的概率。

区别是: 前者有:社区C中的任何两个人是朋友的概率 后者有:每个人对于特定组的归属度

bigClam的求解问题

这里讨论的是,已知一个网络,求解模型的问题。

已知: 网络中的任何两个人是否是好友,是否有edge相连。也就是前面讨论中求出的连接概率。 求: 网络的参数F矩阵。

转化成优化问题,可以使用梯度法求解。 并且根据一些trick,将问题的复杂性减小。

最大似然的优化问题

注意,这里对优化问题去了log值,理由是:

  1. 乘法问题变成了加法问题,方便计算分析
  2. 乘法问题的话错误会不断快速地累积,加法问题可以避免这个问题
  3. log不改变原来的单调性

梯度下降法

对每个点进行一次迭代,每经过一个点更新参数,直到达到稳定值。

注意,这里是求最大似然值

  1. 可以变下符号
  2. 更新参数的时候把减号变成加好,因为求导的方向也就是梯度的方向,是函数增长最快的方向。

但是,这种方法有个缺点,对于和u不适邻居的数据,都要进行迭代计算,所以每次更新的话会遍历所有的样本点,这样时间复杂度是O(N)O(N)的,不利于大数据的计算。

改进的梯度下降

改进后的方法,只需要预先计算一次全体值,然后cache方便之后计算。 接下来每次只需要计算与u相邻的节点值,这样的话在大数据的情况下极大地减少了时间,时间复杂度是关于邻居集合的线性的。

Scalability

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

数据科学与机器学习管道中预处理的重要性(一):中心化、缩放和K近邻

1653
来自专栏人工智能头条

优秀的排序算法如何成就了伟大的机器学习技术(视频+代码)

【导读】在机器学习中,支持向量机(SVM)算法是针对二分类任务设计的,可以分析数据,识别模式,用于分类和回归分析。训练算法构建一个模型,将新示例分配给一个类别或...

672
来自专栏小樱的经验随笔

灰色理论预测模型

灰色理论 通过对原始数据的处理挖掘系统变动规律,建立相应微分方程,从而预测事物未来发展状况。  优点:对于不确定因素的复杂系统预测效果较好,且所需样本数据较小...

3426
来自专栏大数据挖掘DT机器学习

支持向量机(SVM)入门详解(续)与python实现

接前文 支持向量机SVM入门详解:那些你需要消化的知识 让我再一次比较完整的重复一下我们要解决的问题:我们有属于两个类别的样本点(并不限定这些点在二维空间中)若...

2768
来自专栏程序员宝库

Python+OpenCV实现增强现实(第1部分)

你可能已经(或可能没有)听过或看过增强现实电子游戏隐形妖怪或Topps推出的3D棒球卡。其主要思想是在平板电脑,PC或智能手机的屏幕上,根据卡片的位置和方向,...

3289
来自专栏机器学习ML

UdaCity-机器学习工程师-项目2:为CharityML寻找捐献者

在这个入门项目中,我们将探索部分泰坦尼克号旅客名单,来确定哪些特征可以最好地预测一个人是否会生还。

21811
来自专栏AI研习社

如何使用高大上的方法调参数

本文主要介绍作者与 Elad Hazan, Adam Klivans 合作的最新论文: Hyperparameter Optimization: A Spec...

3479
来自专栏技术沉淀

KNN算法实现及其交叉验证

1193
来自专栏机器之心

ACL 2018 | 利用Lattice LSTM的最优中文命名实体识别方法

作为信息抽取的一项基本任务,命名实体识别(NER)近年来一直受到研究人员的关注。该任务一直被作为序列标注问题来解决,其中实体边界和类别标签被联合预测。英文 NE...

1292
来自专栏企鹅号快讯

Python数据分析与实战挖掘

基础篇 书推荐:《用python做科学计算》 ? 扩展库 简介 Numpy数组支持,以及相应的高效处理函数 Scipy矩阵支持,以及相应的矩阵数值计算模块 Ma...

3095

扫码关注云+社区