快捷导航

对共词关系求协方差矩阵后再用Girvan-Newman算法做社区发现

2022-10-21 15:56| 发布者: Fuller| 查看: 5701| 评论: 0

摘要: 本文使用中介中心度作为Girvan-Newman算法的指标,看起来先进行MST计算得到的效果更好。其实不难分析,因为MST得到的是一棵树,只要裁掉一条边,就变成了两棵不连通的树(树也是图)。另外,已经用MST生成了语义骨干 ...

1  介绍

此前我们写了系列文章和notebook,通过分析共词关系来分析文本的语义聚类。在《社区发现算法Girvan-Newman(GN)是否能应用于共词矩阵?》,我们尝试了使用Girvan-Newman算法,期望更直观地发现语义聚集。但是,我们遇到了难题:长文本中共词矩阵十分稠密,直接使用Girvan-Newman算法效率太低。本篇作为《对共词关系求协方差矩阵后是否有更好的社会网络分析结果?》的延伸,先经过社会网络图裁剪以后再进行社区发现,期望能提升分析效果。


在《共词分析中的共词关系是怎么得到的?》一篇我们讲解了共词关系描述了什么,同时也提到,如果为了衡量词与词之间在文档中的分布规律是否相似,还有其他一些度量方法。前面,通过《用networkx和python编程可视化分析共词关系图》这篇notebook,我们学会了怎样用社会网络图分析和观察共词关系,通过《用MST(minimum or maximum spanning tree)算法简化共词关系图》和《设置边权重阈值裁剪共词关系图》学会了两种简化图的方法,这两种方法提供了两个不同的视图去观察共词关系。

这些分析同样的可以用在co-word之外的co-auther, co-cited, co-reference等等社会网络分析中。用co-word进行演练有个好处:借助于GooSeeker分词和情感分析软件,一系列数据集唾手可得,而且可以很有意思地紧跟热点,想研究二舅就研究二舅,想研究糖水爷爷就研究糖水爷爷。

本notebook准备使用协方差矩阵来描述共词关系,同共词矩阵相比,这可以看作是更加细腻的考察,因为通过去中心化计算,词在文档中的分布规律不再是非负数描述的,而是有正有负,可以看作是有涨有跌,这样,如果两个词有相同的涨跌,那么他们的协方差就会比较大,同时跌虽然都是负值,两个负数相乘变成正数,为协方差的最终结果给予正向的贡献。

2  使用方法

操作顺序是:

  1. GooSeeker分词和文本分析软件上创建文本分析任务并导入包含待分析内容的excel,分析完成后导出选词矩阵表。选词矩阵表在NLP和机器学习领域也叫feature matrix
  2. 将导出的excel表放在本notebook的data/raw文件夹中
  3. 从头到尾执行本notebook的单元

注意:GooSeeker发布的每个notebook项目目录都预先规划好了,具体参看Jupyter Notebook项目目录规划参考。如果要新做一个分析项目,把整个模板目录拷贝一份给新项目,然后编写notebook目录下的ipynb文件。

3  修改历史

2022-10-20:第一版发布

4  版权说明

本notebook是GooSeeker大数据分析团队开发的,所分析的源数据是GooSeeker分词和文本分析软件生成的,本notebook中的代码可自由共享使用,包括转发、复制、修改、用于其他项目中。

5  准备运行环境

5.1  引入需要用到的库

# -*- coding: utf-8 -*-

import os

import numpy as np

import pandas as pd

import networkx as nx

import matplotlib.pyplot as plt

import pylab

from networkx.algorithms import community

%xmode Verbose

import warnings

# 软件包之间配套时可能会使用过时的接口,把这类告警忽略掉可以让输出信息简练一些

warnings.filterwarnings("ignore", category=DeprecationWarning)

# 把RuntimeWarning忽略掉,不然画图的时候有太多告警了

warnings.filterwarnings("ignore", category=RuntimeWarning)

5.2  设置中文字体

因为含有中文,plt画图会显示下面的错误信息:

C:\ProgramData\Anaconda3\lib\site-packages\matplotlib\backends\backend_agg.py:238: RuntimeWarning: Glyph 32993 missing from current font. font.set_text(s, 0.0, flags=flags)

为了防止plt显示找不到字体的问题,先做如下设置。

参看glyph-23130-missing-from-current-font

#plt.rcParams['font.sans-serif']=['SimHei']

# 上面一行在macOS上没有效果,所以,使用下面的字体

plt.rcParams['font.sans-serif'] = ['Arial Unicode MS']

plt.rcParams['axes.unicode_minus']=False

5.3  常量和配置

在我们发布的一系列Jupyter Notebook中,凡是处理GooSeeker分词软件导出的结果文件的,都给各种导出文件起了固定的名字。为了方便大家使用,只要把导出文件放在data/raw文件夹,notebook就会找到导出文件,赋值给对应的文件名变量。下面罗列了可能用到的文件名变量:

file_all_word:词频表

file_chosen_word: 选词结果表

file_seg_effect: 分词效果表

file_word_occurrence_matrix: 选词矩阵表(是否出现)

file_word_frequency_matrix: 文档词频对应矩阵

file_word_document_match: 选词匹配表

file_co_word_matrix: 共词矩阵表


pd.set_option('display.width', 1000)  # 设置字符显示宽度

pd.set_option('display.max_rows', None)  # 设置显示最大

# np.set_printoptions(threshold=np.inf) # threshold 指定超过多少使用省略号,np.inf代表无限大

# 存原始数据的目录

raw_data_dir = os.path.join(os.getcwd(), '../../data/raw')

# 存处理后的数据的目录

processed_data_dir = os.path.join(os.getcwd(), '../../data/processed')

filename_temp = pd.Series(['词频','分词效果','选词矩阵','选词匹配','选词结果','共词矩阵'])

file_all_word = ''

file_seg_effect = ''

file_word_occurrence_matrix = ''

file_word_frequency_matrix = ''

file_word_document_match = ''

file_chosen_word = ''

file_co_word_matrix = ''

5.4  检测data\raw目录下是否有GooSeeker分词结果表

在本notebook使用选词矩阵表,不再是共词矩阵表,因为选词矩阵表含有更丰富的内容:每个词在每篇文档中出现的次数。下面的代码将检查data/raw中有没有这个表,如果没有会报错,后面的程序就没法执行了。

# 0:'词频', 1:'分词效果', 2:'选词矩阵', 3:'选词匹配', 4:'选词结果', 5:'共词矩阵'

print(raw_data_dir + '\r\n')

for item_filename in os.listdir(raw_data_dir):

    if filename_temp[2] in item_filename:

        file_word_frequency_matrix = item_filename

        continue

if file_word_frequency_matrix:

    print("选词矩阵表:", "data/raw/", file_word_frequency_matrix)

else:

    print("选词矩阵表:不存在")

输出结果如下:

C:\Users\work\notebook\社区发现算法Girvan-Newman(GN)学习-对比\notebook\eda\../../data/raw

选词矩阵表: data/raw/ 选词矩阵-知乎-二舅.xlsx

6  读取选词矩阵表并存入矩阵

读入过程不展开讲解,具体参看《共词分析中的共词关系是怎么得到的?

6.1  用pandas dataframe读入选词矩阵

df_word_frequency_matrix = pd.read_excel(os.path.join(raw_data_dir, file_word_frequency_matrix))

df_word_frequency_matrix.head(2)

6.2  提取字段名

将用于给graph的node命名

coword_names = df_word_frequency_matrix.columns.values[2:]

print("There are ", len(coword_names), " words")

coword_names

输出结果:

There are  100  words

array(['苦难', '精神', '内耗', '故事', '问题', '社会', '时代', '人生', '时候', '世界', '作者',

       '残疾', '中国', '作品', '农村', '城市', '现实', '电影', '命运', '人民', '东西', '底层',

       '媒体', '文化', '年轻人', '人们', '事情', '感觉', '观众', '普通人', '孩子', '经历', '一生',

       '价值', '内容', '编剧', '鸡汤', '能力', '年代', '时间', '原因', '能量', '意义', '老人',

       '评论', '励志', '文案', '村里', '资本', '医生', '流量', '文艺创作', '国家', '艺术', '个人',

       '情绪', '内心', '大众', '朋友', '农民', '母亲', '悲剧', '观点', '大学', '机会', '思想',

       '残疾人', '文艺', '压力', '力量', '角度', '心理', '父母', '分钟', '方式', '人物', '老师',

       '环境', '态度', '物质', '关系', '个体', '条件', '历史', '情况', '群众', '穷人', '房子',

       '回村', '本质', '办法', '官方', '平台', '想法', '视角', '生命', '热度', '地方', '医疗',

       '身体'], dtype=object)

6.3  生成矩阵数据结构

# 使用astype函数对数据类型进行转换,否则,下面画图的时候可能会报错

array_word_frequence_matrix = df_word_frequency_matrix.values[:, 2:].astype(float)

array_word_frequence_matrix

7  求协方差矩阵

在《共词分析中的共词关系是怎么得到的?》我们说过,如果选词矩阵称为R,那么,RTR(R的转置乘以R)就是共词矩阵(这里假定R中只有0和1两个值表示是否出现这个词,我们下面的计算所用的不只是1,而是>=1的数值表示词频,原理一样)。如果先把R去中心化得到矩阵B(转换成mean deviation form),那么,BTB(B的转置乘以B)就是协方差矩阵。

covariance = np.cov(array_word_frequence_matrix, rowvar = False)

covariance

协方差矩阵是一个对称矩阵,对角线上的值是每个词的方差(variance),为了画图的时候不画环回的边,我们把对角线的所有值赋0

np.fill_diagonal(covariance, 0)

covariance

8  生成图并进行探索

8.1  从NumPy数组生成networkx图

参看networkx文档,有专门的函数从其他数据结构直接生成graph

graph_covariance = nx.from_numpy_array(covariance)

print(nx.info(graph_covariance))

#graph_covariance.edges(data=True)

输出结果:

Name: 

Type: Graph

Number of nodes: 100

Number of edges: 4950

Average degree:  99.0000

8.2  给node加上label

对程序代码的解释参看《用networkx和python编程可视化分析共词关系图》,不再赘述。

coword_labels = {}

for idx, node in enumerate(graph_covariance.nodes()): 

    print("idx=", idx, "; node=", node)

    coword_labels[node] = coword_names[idx]

graph_covariance = nx.relabel_nodes(graph_covariance, coword_labels)

sorted(graph_covariance)

8.3  画图

figure函数的使用方法参看pyplot官网 。其他参考资料:

由于是一个全连接图,就没有画的必要了,下面的代码都注释掉了。

#pos = nx.spring_layout(graph_covariance)

#plt.figure(1,figsize=(120,120)) 

#nx.draw(graph_covariance, pos, node_size=10, with_labels=True, font_size=22, font_color="red")

#plt.show()

9  定义画社区图的函数

# 用这个函数,可以最多画4种颜色不同的社区

def plot_communities(G, group_array):

    color_map = []

    for node in G:

        found = False

        for idx, group in enumerate(group_array):

            if node in group:

                found = True

                if idx == 0:

                    color_map.append('blue')

                elif idx == 1:

                    color_map.append('green')

                elif idx == 2:

                    color_map.append('orange')

                elif idx == 3:

                    color_map.append('red')

                else:

                    color_map.append('purple')

        if found == False:

            color_map.append('black')

    pos = nx.spring_layout(G)

    plt.figure(1,figsize=(15,15))

    #nx.draw(G, pos, node_size=100, font_size=22, node_color=color_map, with_labels=True, font_color='white')

    nx.draw(G, pos, node_color=color_map, with_labels=True, font_color='white')

    plt.show()

10  用MST(maximum spanning tree)删减边

10.1  MST计算

graph_covariance_mst = nx.maximum_spanning_tree(graph_covariance)

print(nx.info(graph_covariance_mst))

# graph_covariance_mst.edges(data=True)

输出结果:

Name: 

Type: Graph

Number of nodes: 100

Number of edges: 99

Average degree:   1.9800

10.2  画MST后的图

#pos = nx.circular_layout(graph_covariance_mst)

pos = nx.spring_layout(graph_covariance_mst)

plt.figure(2,figsize=(15,15)) 

nx.draw(graph_covariance_mst, pos, node_size=50, with_labels=True, font_size=15, font_color="red")

plt.show()

10.3  社区发现

10.3.1  分拆社区

comm_gen = community.girvan_newman(graph_covariance_mst)

top_level_co_word = sorted(map(sorted, next(comm_gen)))

top_level_co_word

second_level_co_word = sorted(map(sorted, next(comm_gen)))

second_level_co_word

third_level_co_word = sorted(map(sorted, next(comm_gen)))

third_level_co_word

10.3.2  画社区图

前面我们做了三层分解,那么就用这三层分解的结果分别画图,以示对比

plot_communities(graph_covariance_mst, top_level_co_word)

plot_communities(graph_covariance_mst, second_level_co_word)

plot_communities(graph_covariance_mst, third_level_co_word)

11  设定阈值删减边

11.1  选择阈值

删掉多少边比较好呢?我们先看看这些位置上的边权重是多少:

  • 中位数
  • 10%位
  • 2%位

coword_median = np.median(covariance)

coword_median

输出结果:

0.008842583189465455

coword_max = np.max(covariance)

coword_max

输出结果:

2.4578551843200986

coword_min = np.min(covariance)

coword_min

输出结果:

-0.060885718154429454

coword_per10 = np.percentile(covariance, 90)

coword_per10

输出结果:

0.0691976828814191

coword_per2 = np.percentile(covariance, 98)

coword_per2

输出结果:

0.22641354388815757

11.2  删除权重小于2%分位的边

我们不挨个尝试删减度了,直接实验重度删减后的效果

graph_covariance_per2 = graph_covariance.copy()

graph_covariance_per2.remove_edges_from([(n1, n2) for n1, n2, w in graph_covariance_per2.edges(data="weight") if w < coword_per2])

pos = nx.spring_layout(graph_covariance_per2)

plt.figure(1,figsize=(15,15)) 

nx.draw(graph_covariance_per2, pos, node_size=10, with_labels=True, font_size=15, font_color="red")

plt.show()

11.3  删除基于2%分位裁剪的图的孤立点

graph_covariance_per2.remove_nodes_from(list(nx.isolates(graph_covariance_per2)))

#pos = nx.circular_layout(graph_covariance_per2)

pos = nx.spring_layout(graph_covariance_per2)

plt.figure(1,figsize=(15,15)) 

nx.draw(graph_covariance_per2, pos, node_size=10, with_labels=True, font_size=15, font_color="blue")

plt.show()

11.4  社区发现

11.4.1  分拆社区

comm_gen = community.girvan_newman(graph_covariance_per2)

top_level_cov_per2 = sorted(map(sorted, next(comm_gen)))

top_level_cov_per2

second_level_cov_per2 = sorted(map(sorted, next(comm_gen)))

second_level_cov_per2

third_level_cov_per2 = sorted(map(sorted, next(comm_gen)))

third_level_cov_per2

11.4.2  画社区图

plot_communities(graph_covariance_per2, top_level_cov_per2)

plot_communities(graph_covariance_per2, second_level_cov_per2)

plot_communities(graph_covariance_per2, third_level_cov_per2)

12  总结

本文使用中介中心度作为Girvan-Newman算法的指标,看起来先进行MST计算得到的效果更好。其实不难分析,因为MST得到的是一棵树,只要裁掉一条边,就变成了两棵不连通的树(树也是图)。另外,已经用MST生成了语义骨干,再用Girvan-Newman算法结合上色显示,仅仅是提升了一下显示效果。相对来说,将Girvan-Newman算法用于根据阈值裁剪的图的作用更大,因为即使做了大幅度裁剪,连通关系还是很复杂,使用Girvan-Newman算法可以进一步聚类一下。

13  下载源代码

点击下载Jupyter Notebook源代码:社区发现算法Girvan-Newman(GN)学习-对比.zip

1

鲜花

握手

雷人

路过

鸡蛋

刚表态过的朋友 (1 人)

最新评论

GMT+8, 2024-3-19 16:28