前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >MMD_3a_CommunitiesInSN

MMD_3a_CommunitiesInSN

作者头像
用户1147754
修改2019-08-07 19:07:45
1.1K0
修改2019-08-07 19:07:45
举报
文章被收录于专栏:YoungGy

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 概述
    • 实例
      • 需要解决的问题
      • 从AGM到Network
        • 模型
          • 特点
          • 从AGM到bigClam
          • bigClam的求解问题
            • 最大似然的优化问题
              • 梯度下降法
                • 改进的梯度下降
                  • Scalability
                  相关产品与服务
                  大数据
                  全栈大数据产品,面向海量数据场景,帮助您 “智理无数,心中有数”!
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档