快捷导航

用MST(minimum or maximum spanning tree)算法简化共现词关系图

2022-8-26 09:38| 发布者: Fuller| 查看: 809| 评论: 0

摘要: 本notebook将演示MST计算方法,下一篇notebook将演示通过设定边权重的阈值来简化图。MST一般是minimum spanning tree的简称,是图算法中的一个最最基础的算法,基于这个算法,可以把graph变成tree,每个节点只留一条 ...

1  介绍

上一篇Jupyter notebook《用networkx和python编程可视化分析共词关系图》我们讲解了怎样用networkx为GooSeeker分词和情感分析软件生成的共词矩阵画社会网络图,也展示了社会网络分析中常用的中心性计算方法。最后提出了一个改进问题:由于长文本的邻接矩阵密度太高,画出来的图黑乎乎一片,怎样简化图?

本notebook将演示MST计算方法,下一篇notebook将演示通过设定边权重的阈值来简化图。截至目前,都是用共词矩阵作为输入数据,会观察到一些不理想的结果,然后在后面更多notebook中我们用其他度量方式进行观察期望解决问题,最后通过精选词再做计算,最终会看到比较理想和稳定的结果。这是这一套notebook的演练路线。

MST一般是minimum spanning tree的简称,是图算法中的一个最最基础的算法,基于这个算法,可以把graph变成tree,每个节点只留一条最“小”的边与另一个节点相连。MST往往是其他图算法的基础,比如,给让人头疼的TSP问题设定上界以快速求解TSP问题。

将一个数据集构建成一个图以后,每个节点之间就有了空间关系,也就是他们之间有距离,可以有多种度量方法,有些甚至还可以不用满足三角不等式,在机器学习领域要求可以没有那么严,不符合三角不等式的距离也允许用来计算。

最小展开树始终寻找距离最小的边,但是,在很多计算中,度量出来的不是距离(距离越短表示越近),比如,相关性、相似度等,在这些情况下,相似度越大的才是距离越小的,如果要使用最小展开树算法,要把相似度转换成距离,是某种倒数关系。如果想省掉这种转换,可以使用maximum spanning tree。在networkx程序包中,这两个函数都有,本notebook使用最大展开树进行实验。

2  使用方法

为了完成本notebook讲解的数据处理过程,操作顺序是:

  1. 在GooSeeker分词和文本分析软件上创建文本分析任务并导入包含待分析内容的excel,分析完成后导出共词矩阵表
  2. 将导出的excel表放在本notebook的data/raw文件夹中
  3. 从头到尾执行本notebook的单元

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

3  修改历史

2022-08-18:第一版发布

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

%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[5] in item_filename:

        file_co_word_matrix = item_filename

        continue

if file_co_word_matrix:

    print("共词矩阵表:", "data/raw/", file_co_word_matrix)

else:

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

输出结果像这个样子:

C:\Users\work\workspace_219\notebook\发布-二舅\用MST(minimum or maximum spanning tree)算法简化共词关系图\notebook\eda\../../data/raw

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

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

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

6.1  用pandas dataframe读入共词矩阵

df_co_word_matrix = pd.read_excel(os.path.join(raw_data_dir, file_co_word_matrix))

df_co_word_matrix.head(2)

6.2  提取字段名

将用于给graph的node命名

coword_names = df_co_word_matrix.columns.values[1:]

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

coword_names

输出结果如下:

There are  133  words

array(['世界', '二舅', '现实', '时候', '故事', '人生', '事情', '苦难', '精神', '底层', '内耗',

       '时代', '人民', '视频', '社会', '人们', '问题', '母亲', '普通人', '国家', '农村', '作者',

       '东西', '中国', '回村', '作品', '时间', '残疾', '原因', '孩子', '命运', '个人', '力量',

       '年轻人', '价值', '意义', '一生', '经历', '感觉', '方式', '大学', '房子', '年代', '条件',

       '观众', '地方', '评论', '媒体', '城市', '态度', '村里', '能力', '本质', '青年', '文化',

       '能量', '医生', '老师', '办法', '大众', '电影', '鸡汤', '机会', '压力', '父母', '穷人',

       '小镇', '角度', '悲剧', '收入', '关系', '内容', '视角', '老人', '内心', '环境', '流量',

       '情况', '情绪', '文案', '目的', '观点', '人类', '农民', '资本', '个体', '励志', '代表',

       '平台', '文艺创作', '分钟', '经济', '想法', '朋友', '心理', '群众', '人物', '日子', '资源',

       '思想', '历史', '残疾人', '文艺', '编剧', '木匠', '过程', '生命', '身体', '状态', '艺术',

       '政府', '物质', '人人', '医疗', '村子', '文学', '热度', '心态', '网友', '周劼', '机制',

       '宁宁', '外甥', '兴趣', '主流', '公子', '父亲', '官方', '文艺作品', '好人', '源泉', '公寓',

       '彭叔'], dtype=object)

6.3  生成矩阵数据结构

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

array_co_word_matrix = df_co_word_matrix.values[:, 1:].astype(float)

array_co_word_matrix

输出结果如下:

array([[101.,  74.,  24., ...,   1.,   1.,   1.],

       [ 74., 403.,  59., ...,   5.,   1.,   1.],

       [ 24.,  59.,  76., ...,   1.,   1.,   1.],

       ...,

       [  1.,   5.,   1., ...,   7.,   0.,   0.],

       [  1.,   1.,   1., ...,   0.,   1.,   0.],

       [  1.,   1.,   1., ...,   0.,   0.,   1.]])

看一下字数有多少:

word_num = len(array_co_word_matrix)

word_num

输出结果是:133

6.4  对角线赋值0

对角线是一个词出现的文档数量,为了防止画图时出现自环边,赋值为0

np.fill_diagonal(array_co_word_matrix, 0)

array_co_word_matrix

输出结果如下:

array([[ 0., 74., 24., ...,  1.,  1.,  1.],

       [74.,  0., 59., ...,  5.,  1.,  1.],

       [24., 59.,  0., ...,  1.,  1.,  1.],

       ...,

       [ 1.,  5.,  1., ...,  0.,  0.,  0.],

       [ 1.,  1.,  1., ...,  0.,  0.,  0.],

       [ 1.,  1.,  1., ...,  0.,  0.,  0.]])

7  生成图并进行探索

7.1  从NumPy数组生成networkx图

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

graph_co_word_matrix = nx.from_numpy_array(array_co_word_matrix)

print(nx.info(graph_co_word_matrix))

#graph_co_word_matrix.edges(data=True)

输出结果如下:

Name: 

Type: Graph

Number of nodes: 133

Number of edges: 7710

Average degree: 115.9398

7.2  给node加上label

如果不加label,画出来的图上的每个节点只是一个编号,加上label可以看到节点对应的词。

根据get_node_attributes,查看现在的note labels

coword_labels = nx.get_node_attributes(graph_co_word_matrix,'labels')

coword_labels

输出结果是:{}

根据How-do-I-label-a-node-using-networkx-in-python,重新命名labels

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

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

    coword_labels[node] = coword_names[idx]

graph_co_word_matrix = nx.relabel_nodes(graph_co_word_matrix, coword_labels)

sorted(graph_co_word_matrix)

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

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

7.3  画图

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

# 方案1:用pylab画图

#pos=nx.shell_layout(graph_co_word_matrix)

#nx.draw(graph_co_word_matrix,pos,with_labels=True, node_color='white', edge_color='grey', node_size=1200, alpha=1 )

#pylab.title('co-word matrix',fontsize=25)

#pylab.show()

# 方案2

#pos = nx.circular_layout(maximum_tree)

pos = nx.spring_layout(graph_co_word_matrix)

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

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

#nx.draw(graph_co_word_matrix, pos, with_labels=True)

#nx.draw_networkx_labels(graph_co_word_matrix, pos, labels)

plt.show()

8  使用MST简化图

上面的图可以看到,连线太多了,使用MST算法,可以化简掉节点之间的边,每个节点只留一条边,如果使用maximum算法,那么只保留权重最大的边(可以看作是距离的倒数)。可以想到,这样的化简可能太狠了一点,其实还有一些没那么狠的spanner算法,这里就不多说了。

经过下面的计算,nx.info的结果与前面一节的对比,发现现在的边数比节点数还少,刚好少1.

graph_co_word_mst = nx.maximum_spanning_tree(graph_co_word_matrix)

print(nx.info(graph_co_word_mst))

#graph_co_word_mst.edges(data=True)

输出结果如下:

Name: 

Type: Graph

Number of nodes: 133

Number of edges: 132

Average degree:   1.9850

再次画图

# 方案1:用pylab画图

#pos=nx.shell_layout(graph_co_word_mst)

#nx.draw(graph_co_word_mst,pos,with_labels=True, node_color='white', edge_color='grey', node_size=1200, alpha=1 )

#pylab.title('co-word MST',fontsize=25)

#pylab.show()

# 方案2:

#pos = nx.circular_layout(graph_co_word_mst)

pos = nx.spring_layout(graph_co_word_mst)

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

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

plt.show()

9  点度中心性分析

经过MST处理以后糊成一片的图精简成了一棵树,有局部的星状结构,代表共现关系中最核心的一些词。下面用程序从几个侧面观察一下。

9.1  定义一个公共画图函数

下面的代码来自NetworkX的中心性分析案例:plot_degree.html。将用来从多个角度观察点度中心性。

def diplay_graph_degree(G):

    seq_degree = sorted((d for n, d in G.degree()), reverse=True)

    dmax = max(seq_degree)

    

    fig = plt.figure("Degree of the count graph", figsize=(8, 8))

    # Create a gridspec for adding subplots of different sizes

    axgrid = fig.add_gridspec(5, 4)

    

    ax0 = fig.add_subplot(axgrid[0:3, :])

    Gcc = G.subgraph(sorted(nx.connected_components(G), key=len, reverse=True)[0])

    pos = nx.spring_layout(Gcc, seed=10396953)

    nx.draw_networkx_nodes(Gcc, pos, ax=ax0, node_size=20)

    nx.draw_networkx_edges(Gcc, pos, ax=ax0, alpha=0.4)

    ax0.set_title("Connected components of G")

    ax0.set_axis_off()

    

    ax1 = fig.add_subplot(axgrid[3:, :2])

    ax1.plot(seq_degree, "b-", marker="o")

    ax1.set_title("Degree Rank Plot")

    ax1.set_ylabel("Degree")

    ax1.set_xlabel("Rank")

    

    ax2 = fig.add_subplot(axgrid[3:, 2:])

    ax2.bar(*np.unique(seq_degree, return_counts=True))

    ax2.set_title("Degree histogram")

    ax2.set_xlabel("Degree")

    ax2.set_ylabel("# of Nodes")

    

    fig.tight_layout()

    plt.show()

9.2  针对原始图(共现次数)的处理

9.2.1  对点度中心性排序

观察哪些词是中心词。可以看到,由于数据集中的每个文档都比较长,共现的机会很高,所以,点度中心性很近似,前面的这些基本上都是全连接。

sorted(graph_co_word_matrix.degree(), key=lambda x: x[1], reverse=True)

输出结果如下:

[('世界', 132),

 ('二舅', 132),

 ('现实', 132),

 ('时候', 131),

 ('故事', 131),

 ('人生', 131),

 ('事情', 131),

 ('苦难', 131),

 ('精神', 131),

 ('底层', 131),

 ('内耗', 131),

 ('时代', 130),

 ('人民', 130),

 ('视频', 130),

 ('社会', 130),

 ('人们', 130),

 ('问题', 130),

 ('母亲', 129),

 ('普通人', 129),

 ('国家', 129),

 ('农村', 129),

 ('作者', 129),

 ('东西', 128),

 ('中国', 128),

 ('回村', 128),

 ('作品', 127),

 ('时间', 127),

 ...

 ('兴趣', 93),

 ('主流', 93),

 ('公子', 90),

 ('父亲', 87),

 ('官方', 78),

 ('文艺作品', 71),

 ('好人', 63),

 ('源泉', 63),

 ('公寓', 54),

 ('彭叔', 36)]

9.2.2  综合展示点度中心性

因为图的密度很高,用这个新定义的画图函数依然显示一片黑,但是还有两个图值得注意,实际上这两个图展示了相同内容,只是展示的角度不同,从这两个图可以看到具有某个点度的节点数量。

diplay_graph_degree(graph_co_word_matrix)

9.3  MST以后的图

9.3.1  对点度中心性排序

前面直接看画出来的图不太容易,因为图的幅面太大,不好找某个词,排序以后就很清楚了。

sorted(graph_co_word_mst.degree(), key=lambda x: x[1], reverse=True)

输出结果如下:

[('二舅', 116),

 ('视频', 11),

 ('世界', 3),

 ('故事', 2),

 ('苦难', 2),

 ('精神', 2),

 ('艺术', 2),

 ('现实', 1),

 ('时候', 1),

 ('人生', 1),

 ('事情', 1),

 ('底层', 1),

 ('内耗', 1),

 ('时代', 1),

...

 ('外甥', 1),

 ('兴趣', 1),

 ('主流', 1),

 ('公子', 1),

 ('父亲', 1),

 ('官方', 1),

 ('文艺作品', 1),

 ('好人', 1),

 ('源泉', 1),

 ('公寓', 1),

 ('彭叔', 1)]

9.3.2  综合展示点度中心性

diplay_graph_degree(graph_co_word_mst)

10  总结

“二舅”中心性最高,其实没有意义,因为所有文档本来就是说二舅的。类似没有意义的词是“视频”。这些高度集中的词,严重影响了MST生成的结果,几乎所有的词跟这个词最近。

是否可以用其他一些度量避免这种集中度很高的词呢?我们将在后面的notebook中演示协方差和皮尔森相关系数所带来的变化,可以看到,有些突出问题有所改善,但是同时又会出现新问题:比如,一些文档频率很低的词严重影响了网络图的关系,这是遇到了理论瓶颈,比如,维度诅咒(curse of dimension),这个数据集总共只有730个文档,数量是很少的,稍微选一些词就会在空间模型中显的极其稀疏了,使用代数模型计算将有很大偏差。

面对一个内容分析任务,没必要去深究这类理论,而是应该专注于发现内容中的信息。GooSeeker分词和情感分析软件界面上有根据词频和文档频率分别排序的功能,可以把普遍词和很稀有的词都筛选出来删掉,确保留下的词有很好的统计特性。

通过手工筛选词以后,再经过同样的分析,可以看到这样的结果。后面的notebook还将通过计算协方差和皮尔森相关系数以后再对比。

11  下载Jupyter Notebook

下载本notebook的源代码,请点击:用MST(minimum or maximum spanning tree)算法简化共现词关系图.zip


鲜花

握手

雷人

路过

鸡蛋

最新评论

GMT+8, 2022-12-10 14:45