【自然语言处理NLP】社区发现快速入门(2)

本文涉及的产品
NLP自然语言处理_高级版,每接口累计50万次
NLP自然语言处理_基础版,每接口每天50万次
NLP 自学习平台,3个模型定制额度 1个月
简介: 【自然语言处理NLP】社区发现快速入门

【自然语言处理NLP】社区发现快速入门(1)https://developer.aliyun.com/article/1541013

五、图分区的比较(指标)

5.1 无监督算法度量指标

  1. 图聚类算法选择
  • 集群的质量
  • 稳定性
  • 效率(时间空间)
  • 其他:不需要指定聚类的数量(k)、集群的层次结构等
  1. 图聚类是无监督学习,没有明确的目标函数,不同算法使用不同的目标函数。
  2. 图分割算法度量
  • 质量的衡量标准:sim(T,A),对给定的参考划分(ground truth partition)T计算图A的划分的相似度函数
  • 稳定性的衡量标准:sim(A,A),同一算法的运行多次比较
  • 比较算法之间的结果:sim(A,B)

5.2 图相似度度量指标

  1. 图无关度量——只看点的信息,不考虑边的影响
  • 基于成对计数:考虑对图节点的两个划分,度量指标基于A和B里面各个集群中的成对元素
  • Jaccard 指数
  • 调整兰德指数(ARI),取值范围是[-1, 1],-1表示聚类结果完全不一致,0表示聚类结果与随机结果相同,1表示聚类结果完全一致
  • 基于信息论:基于 A 和 B 之间的互信息
  • 归一化互信息 (NMI),取值范围是[0, 1],0表示两个聚类结果没有任何相似性,1表示两个聚类结果完全一致。NMI并不受聚类结果的绝对数目影响,而是关注聚类结果之间的相对关系和一致性
  • 基于卡方分布
  • Cramer 的 V指标 和 Tschurprow 的 T指标
  1. 图感知度量——只看边的信息,不考虑点的信息
  • AGRI

设网络G 的真实社区情况为 A, 并设 B1 和 B2 分别是 A 的粗化和细化,在某些情况下,在图无关度量下A更接近B2(细化);在图感知度量下A更接近B1(粗化)

  • 当使用图无关的度量时,集群的数量更多
  • 图感知度量生成的集群的数量更少

这两种指标都获得高值是我们做图聚类所希望的,但图感知和图无关度量在解决问题方面具有相反的行为(trade-off)。ECG算法可以使两者都达到一个较好的效果。

总结:

  • 使用调整后的基于集合的相似性度量,可以减少度量对分区粒度的偏差,消除随机性
  • 图无关(ARI,AMI)和图感知(AGRI)度量是互补的,在评估算法的优越性时应同时使用它们

5.3 其他指标

  1. 拓扑特征
  • 缩放密度(scaled density)
  • 内部传递性(internal transitivity)
  1. 社区强度指数CSI(ECG论文中提出的一个指标):边界(0 和 1)附近的 ECG 权重的双峰分布(bi-modal distribution)表明了强大的社区结构,由此提出了一个基于点质量 Wasserstein 距离(推土机距离(Earth Mover’s distance))的简单社区强度指标 (CSI)

 3.异常检测CADA(community-aware anomaly detection社团感知异常检测)对于每个节点 image.png ,令 image.png :v的邻居数; image.png 属于出现次数最多社区的邻居数(通过图聚类)。

image.png


六、图嵌入

图嵌入Graph Embedding,也叫图表示学习(Network Representation Learning),其目标是将网络(节点)映射到向量(特征)空间,将相似节点映射到向量空间中的附近位置。

何谓”相似“?

  • 图拓扑上较近
  • 图中相似的角色(例如:度相似)
  • 相似的节点属性

图嵌入的大部分算法基于大部分算法基于随机游走和用于词嵌入的SkipGram方法

NLP中的SkipGram:使用滑动窗口对每个词上下文的相关词进行组合,构建“词向量”,对应到图中:

  • 单词——节点
  • 词的上下文——节点与其周围的节点构成的链路

如何找出这样一条链路?——随机游走——node2vec

node2vec:定义了有偏随机游走(biased random walks)【有偏:从一个点跳到下一个不同点的概率是不一样的】混合了广度和深度优先搜索。关键参数:

  • p:控制重新访问同一节点的概率(留在附近)
  • q:控制探索更远的概率


以下图为例,假设当前节点v的上一时刻的节点为t(即节点v是从节点t转移过来的),定义从节点v游走到节点x1 , x2 , x3之间的概率为α。其中,节点v游走到与上一时刻节点t直接相连的节点x1 的概率为1,游走到其他节点(x2 , x3)的概率为1/q,回到上一时刻节点t的概率为1/pp,q为可调整参数。

节点v下一时刻游走到其余节点的概率的数学表述为:

image.png

参数允许在以下之间进行权衡:

  • 低 p:在本地探索;这将侧重于图形拓扑结构中的社区结构(同质性);
  • 低q:探索更远;这允许捕获节点之间的一些结构相似性(例如:集线器hubs,网桥bridges);

node2vec的参数P和q取值不同,得到的嵌入特征向量在二维空间上的可视化效果也不同。如下图所示,p比较小、q比较大时,算法更加关注局部特征,嵌入特征在局部上是比较相近的(上图);p比较大、q比较小时,算法倾向于捕获在结构上相似的一些点(下图)。

其他图嵌入算法

不同算法之间的结果可能会有很大差异,并且随着参数的选择也会有很大不同,如何比较算法的嵌入效果?

  • 核心:使用嵌入后的向量构建同分布随机图,比较随机图和原图的JS散度,若很小,说明相近,进而说明嵌入效果良好

首先,将原始图中的节点通过嵌入算法转换为向量表示,这些向量表示可以捕捉到节点之间的关系和特征。然后,使用这些向量来构建同分布随机图(通常是通过随机过程生成),即生成一张与原图在节点分布上相似的新图。

接下来,通过计算随机图和原图的JS散度来衡量它们之间的差异。JS散度(Jensen-Shannon divergence)是一种度量两个概率分布之间差异的指标。当JS散度越小时,表示两个概率分布越接近,即随机图和原图在节点分布上越相似。

因此,如果通过嵌入得到的向量能够很好地保留原始图中节点之间的关系和特征,那么使用这些向量构建的同分布随机图与原图之间的JS散度会很小,说明嵌入效果良好。

给定具有度分布 w=(w1,w2,...,wn)的 n 个顶点上图G=(V,E) 及其顶点到 k 维空间的嵌入,ε:VRk,我们的目标是为这个嵌入分配一个**“分歧分数”(divergence score)**,该分数用于比较不同嵌入结果在多个维度上的差异,分数越低,嵌入越好。这将使我们能够在不同的维度上比较多个嵌入的结果。

流程总述

非随机图(原图)表现出类似社区的结构,所以我们一般:

  1. 将节点分组为集群(使用聚类算法/框架进行分组)
  2. 测量簇之间和簇内的边缘密度
  3. 通过计算散度分数将其与嵌入(矢量)空间中空间模型的预测密度进行比较
  4. 选择得分最高的嵌入

聚类算法/框架主要关注两个角度:

  • 图拓扑视图:一个好的、稳定的图聚类算法(ECG、Louvain或InfoMap)
  • 空间视图:引入基于度分布 w 和嵌入 ε 的几何 Chung-Lu (GCL) 模型

计算嵌入分歧分数(embedding divergence score)的算法


给定G=(V,E),它在 V上的度分布w,以及它的顶点的嵌入ε : V → Rk,执行接下来的五个步骤。通过计算分歧分数的算法获得嵌入的分歧分数ΔE(G),可以应用该算法来比较几个嵌入算法的分歧分数指标,选出最好的(最小的)那个。

  • 第一步:在G上运行一些稳定的图聚类算法以获得顶点集V的分区C,一共产生l个社区 image.png
  • 第二步:令ci表示两个端点都在ci中的边的比例,ci,j表示一个端点在ci中且另一个端点在Cj中的边的比例,定义 image.png 这些向量从G的角度表征分区C,嵌入ε不影响cˉc^
  • 接下来需要在 α 的一系列值上重复步骤 3-4
  • 第三步:给定α ∈ R+,使用 image.png 的GCL模型(也可以使用其他稳定的模型)计算①biCi内边的比例期望,②bi,jCi中一个端点和Cj中另一个端点的边的比例期望,计算公式为 image.png 这些向量从嵌入ε的角度表征分区C
  • 第四步:使用 Jensen-Shannon 散度 (JSD)计算 image.png 之间的距离,以及 image.png 之间的距离,公式为 image.png 这是给定 α 的(分歧)分数。
  • 第五步:从重复的步骤 3-4,我们获得了一系列Δα,选择 image.png ,将分期函数定义为 image.png


为了比较同一个图G的多个嵌入,我们重复上面的步骤3-5并比较分歧分数(分歧分数越低越好);步骤1-2值执行一次,因此我们对每个嵌入使用相同的图划分算法到l个社区。

目录
相关文章
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【自然语言处理】自然语言处理NLP概述及应用
自然语言处理(Natural Language Processing,简称NLP)是一门集计算机科学、人工智能以及语言学于一体的交叉学科,致力于让计算机能够理解、解析、生成和处理人类的自然语言。它是人工智能领域的一个关键分支,旨在缩小人与机器之间的交流障碍,使得机器能够更有效地识别并响应人类的自然语言指令或内容。
32 4
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【自然语言处理】GPT-5技术突破预测:引领自然语言处理革新的里程碑
随着科技的飞速发展,人工智能(AI)领域正迎来一场前所未有的革命。近日,OpenAI首席技术官米拉·穆拉蒂在采访中透露,新一代大语言模型GPT-5将在一年半后发布,这一消息无疑在科技界掀起了巨大的波澜。GPT-5的即将登场,预示着AI技术将迈入一个新的时代,我们的工作和日常生活也将随之发生深刻的变化。 GPT-5的发布,将为我们带来前所未有的智能体验。穆拉蒂将其与高中生到博士生的成长相比,可见其在智能水平上的巨大飞跃。GPT-5将具备更高的智能水平,能够处理更为复杂、精细的任务,如高级数据分析、自动化编程、智能内容生成等。这将极大地提高各行各业的工作效率,推动社会生产力的快速发展。
42 4
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【人工智能】自然语言处理(NLP)的突破,关注NLP在机器翻译、情感分析、聊天机器人等方面的最新研究成果和应用案例。
自然语言处理(NLP)作为人工智能的一个重要分支,近年来取得了显著的突破,特别在机器翻译、情感分析、聊天机器人等领域取得了显著的研究成果和广泛的应用。以下是对这些领域最新研究成果和应用案例的概述,并附带相应的代码实例。
58 1
|
1月前
|
机器学习/深度学习 自然语言处理 搜索推荐
自然语言处理 Paddle NLP - 预训练模型产业实践课-理论
自然语言处理 Paddle NLP - 预训练模型产业实践课-理论
26 0
|
1月前
|
机器学习/深度学习 自然语言处理 区块链
自然语言处理 Paddle NLP - 开放域对话系统-理论
自然语言处理 Paddle NLP - 开放域对话系统-理论
13 0
|
1月前
|
机器学习/深度学习 自然语言处理
自然语言处理 Paddle NLP - 任务式对话系统-理论
自然语言处理 Paddle NLP - 任务式对话系统-理论
41 0
|
1月前
|
自然语言处理 语音技术
自然语言处理 Paddle NLP - 机器同传技术及应用-理论
自然语言处理 Paddle NLP - 机器同传技术及应用-理论
25 0
|
9天前
|
机器学习/深度学习 人工智能 自然语言处理
AI技术在自然语言处理中的应用
【9月更文挑战第17天】本文主要介绍了AI技术在自然语言处理(NLP)领域的应用,包括文本分类、情感分析、机器翻译和语音识别等方面。通过实例展示了AI技术如何帮助解决NLP中的挑战性问题,并讨论了未来发展趋势。
|
4天前
|
机器学习/深度学习 人工智能 自然语言处理
探索AI技术在自然语言处理中的应用
【9月更文挑战第22天】本文将探讨AI技术在自然语言处理(NLP)领域的应用,包括文本挖掘、情感分析、机器翻译等方面。我们将通过实例和代码示例,展示如何使用Python和相关库实现这些功能。
|
6天前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习在自然语言处理中的应用与未来展望
本文探讨了深度学习技术在自然语言处理(NLP)领域的应用,重点分析了神经网络模型如循环神经网络(RNN)、长短期记忆网络(LSTM)和Transformer等在文本生成、语义理解及情感分析等任务中的卓越表现。通过具体案例展示了这些模型如何有效解决传统方法难以处理的问题,并讨论了当前面临的挑战及未来可能的发展方向,为进一步研究提供了新的视角和思路。

热门文章

最新文章