Coggle 30 Days of ML（23年2月）

发布时间：2023-02-01，作者：阿水, 鱼遇雨欲语与余

## Part1 内容介绍

本月竞赛学习将以知识图谱中基础的图分析展开。图是复杂系统中常用的信息载体，可以表示现实中许多复杂关系，如社交网络、犯罪网络、交通网络等。在本次学习中我们将学习：

networkx基础使用
图节点分析和中心性计算
图查询与图嵌入原理

上述步骤都是一个知识图谱算法工程师必备的基础，在本月我们将逐步从基础出发，逐步学习图算法。

## Part2 活动安排

免费学习活动，不会收取任何费用。
请各位同学添加下面微信，并回复【竞赛学习】，即可参与。

## Part3 积分说明和奖励

为了激励各位同学完成的学习任务，将学习任务根据难度进行划分，并根据是否完成进行评分难度高中低的任务分别分数为3、2和1。在完成学习后（本次活动，截止2月1），将按照积分顺序进行评选 Top3 的学习者。

打卡链接(可以重复提交)：https://shimo.im/forms/uyIl0p5DArI5iL4h/fill

打卡可以写在一个地址，每次有新完成的可以重复提交打卡！

昵称	任务1	任务2	任务3	任务4	任务5	任务6
墨语	✅	✅	✅	✅	✅	✅
徐乜乜	✅	✅	✅	✅	✅	✅
irrational	✅	✅	✅	✅	✅	✅
ruler同学	✅	✅	✅	✅	✅
徐乜乜	✅	✅	✅	✅
形而上学的唯心主义者	✅	✅
Neo	✅	✅
林望黎	✅	✅
Ben	✅	✅
糖醋鱼	✅
Weltberg	✅
H2O	✅
Mr.Turtle	✅
芬达	✅
Alas	✅
Znz	✅
simple	✅
natelie	✅
阿水	⭕️	⭕️	⭕️	⭕️

Top1的学习者将获得以下奖励：

Coggle 竞赛专访机会
百度音响随身版

Top2-3的学习者将获得以下奖励：

Coggle 周边福利
Coggle 竞赛专访机会

历史活动打卡链接，可以参考如下格式：

## Part4 图节点嵌入

### 背景介绍

图（Graphs）是一种对物体（objects）和他们之间的关系（relationships）建模的数据结构，物体以结点（nodes）表示，关系以边（edges）表示。图是复杂系统中常用的信息载体，可以表示现实中许多复杂关系，如社交网络、犯罪网络、交通网络等。

### 环境配置

实践环境建议以Python3.7+，且需要安装如下库：

numpy
pandas
networkx
igraph
gensim

### 学习打卡

任务名称	难度
任务1：图属性与图构造	低、1
任务2：图查询与遍历	低、2
任务3：节点中心性与应用	中、2
任务4：图节点嵌入算法（DeepWalk/node2vec）	高、3
任务5：图节点嵌入算法：LINE/SDNE	高、3
任务6：图节点嵌入算法：GraphGAN	高、3

任务1：图属性与图构造
- 步骤1：导入networkx
- 步骤2：加载Wiki数据集，包含来自 19 个类别的 2405 个文档和它们之间的 17981个边。
- 步骤3：使用networkx构造上述有向图

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

# 两列，分别为节点id，节点类别
group = pd.read_csv('http://mirror.coggle.club/dataset/graph-wiki/group.txt.zip', sep='\t', header=None)

# 两列，分别为出发节点id，目的节点id
graph = pd.read_csv('http://mirror.coggle.club/dataset/graph-wiki/graph.txt.zip', sep='\t', header=None)

g = nx.DiGraph()

# 只添加前100条边
g.add_edges_from(graph.values[:100])
nx.draw_spring(g)

# 添加所有数据
g = nx.DiGraph()
g.add_edges_from(graph.values[:])

任务2：图查询与遍历
- 步骤1：使用networkx对Wiki数据集进行如下统计
  - 节点个数、边个数
  - 节点度平均
  - 存在指向自身节点的个数
- 步骤2：对节点1397进行深度和广度遍历，设置搜索最大深度为5
- 步骤3：判断节点1573与节点1397之间是否存在联通性

# 边个数 节点个数
g.number_of_edges(), g.number_of_nodes()

# 度均值
np.mean([x[1] for x in list(g.degree())])

# 对节点1397的深度5内进行深度和广度遍历
nx.dfs_tree(g, 1397, 5).nodes()
nx.bfs_tree(g, 1397, 5).nodes()

# 节点1573与节点1397之间的路径
list(nx.connectivity.node_disjoint_paths(g, 1573, 1397))

任务3：节点中心性与应用
- 步骤1：筛选度最大的Top10个节点，并对节点深度1以内的节点进行可视化；
- 步骤2：使用PageRank筛选Top10个节点，并对节点深度1以内的节点进行可视化；
- 步骤3：文本关键词提取算法RAKE
  - 使用jieba对文本进行分词
  - 单词作为节点，距离2以内的单词之间存在边
  - 计算单词打分$\text { wordDegree }(w) / \text { wordFrequency }(w)$
  - 按照打分统计每个文章Top10关键词
- 步骤4：文本关键词提取算法TextRank
  - 使用jieba对文本进行分词
  - 单词作为节点，距离2以内的单词之间存在边
  - 使用PageRank对单词进行打分
  - 按照打分统计每个文章Top10关键词

# 文章1
'''
一纸四季报，令芯片巨头英特尔一夜间股价重挫近6.5%，市值蒸发80亿美元，再度被AMD反超。

这份严重缩水的财报显示，英特尔在去年四季度营收大降32%至140亿美元，是2016年以来最低单季收入；净利润由三季度的10.2亿美元转为近7亿美元净亏损；毛利率更从2021年四季度的53.6%大幅下降至39.2%。

此番业绩“跳水”并非英特尔一家的一时失利，在全球PC出货量整体下滑的背景下，包括英特尔、AMD、英伟达、高通在内的芯片企业，均在过去一年里出现不同程度的收入与利润下滑，但英特尔的确是其中的重灾区。
'''

# 文章2
'''
2021年，成都地区生产总值已经超过1.99万亿元，距离2万亿门槛仅咫尺之间。在去年遭受多轮疫情冲击及高温限电冲击的不利影响下，2022年，成都市实现地区生产总值20817.5亿元，按可比价格计算，比上年增长2.8%。

成都因此成为第7个跨过GDP2万亿门槛的城市。目前，GDP万亿城市俱乐部中形成了4万亿、3万亿、2万亿和万亿这四个梯队。上海和北京在2021年跨过了4万亿，深圳2021年跨过了3万亿，重庆、广州、苏州和成都则是2万亿梯队。

在排名前十的城市中，预计武汉将超过杭州。武汉市政府工作报告称，预计2022年武汉地区生产总值达到1.9万亿元左右。而杭州市统计局公布的数据显示，杭州2022年地区生产总值为18753亿元。受疫情影响，武汉在2020年GDP排名退居杭州之后。
'''


# 文章3
'''
据报道，美国证券交易委员会（SEC）与特斯拉首席执行官埃隆·马斯克之间又起波澜。SEC正对马斯克展开调查，主要审查内容是，马斯克是否参与了关于特斯拉自动驾驶软件的不恰当宣传。

据知情人士透露，该机构正在调查马斯克是否就驾驶辅助技术发表了不恰当的前瞻声明。

特斯拉在2014年首次发布了其自动驾驶辅助功能，公司声称该功能可以让汽车在车道内自动转向、加速和刹车。目前所有特斯拉车辆都内置了该软件。
'''

# 筛选度最大的Top10个节点，并对节点深度1以内的节点进行可视化；
g_degree = pd.DataFrame(g.degree()).sort_values(by=1)
g_degree = g_degree.iloc[-10:]

selected_nodes = []
for node in g_degree[0].values:
    selected_nodes += list(nx.dfs_tree(g, node, 1).nodes())

nx.draw_spring(g.subgraph(selected_nodes), node_size=3)

# 使用PageRank筛选Top10个节点，并对节点深度1以内的节点进行可视化
g_pagerank = pd.DataFrame.from_dict(nx.pagerank(g), orient='index')
g_pagerank = g_pagerank.sort_values(by=0)

g_pagerank = g_pagerank.iloc[-10:]
selected_nodes = []
for node in g_pagerank[0].index:
    selected_nodes += list(nx.dfs_tree(g, node, 1).nodes())

nx.draw_spring(g.subgraph(selected_nodes), node_size=3)

文本关键词提取算法RAKE

import jieba
from collections import Counter

g2 = nx.Graph()
words = jieba.lcut(content)
words = [x for x in words if len(x) > 1]
for i in range(len(words)-2):
    for j in range(i-2, i+2):
        if i == j:
            continue
        g2.add_edge(words[i], words[j])

g2_node_gree = dict(g2.degree())
word_counter = dict(Counter(words))

g2_node_gree = pd.DataFrame.from_dict(g2_node_gree, orient='index')
g2_node_gree.columns = ['degree']

g2_node_gree['freq'] = g2_node_gree.index.map(word_counter)
g2_node_gree['score'] = g2_node_gree['degree'] / g2_node_gree['freq']

g2_node_gree.sort_values(by='score').index[-10:]

# ['32%', '140', '2016', '以来', '最低', '单季', '收入', '利润', '缩水', '净利润']
# ['增长', '2.8%', '成都', '2020', '成为', '超过', 'GDP2', '目前', '可比价格', '因此']
# ['主要', '审查', '内容', '参与', '关于', '软件', '所有', '宣传', '人士', '恰当']

文本关键词提取算法TextRank

g2 = nx.Graph()

words = jieba.lcut(content)
words = [x for x in words if len(x) > 1]
for i in range(len(words)-2):
    for j in range(i-2, i+2):
        if i == j:
            continue
        g2.add_edge(words[i], words[j])

g2_node_gree = pd.DataFrame.from_dict(nx.pagerank(g2), orient='index')
g2_node_gree.columns = ['degree']
g2_node_gree = g2_node_gree.sort_values(by='degree')

# ['39.2%', '四季', '一纸', 'AMD', '下滑', '四季度', '收入', '芯片', '亿美元', '英特尔']
# ['万亿元', '成都', '地区', '2021', '城市', '杭州', '武汉', '2022', '生产总值', '万亿']
# ['功能', '是否', '辅助', '调查', '恰当', 'SEC', '驾驶', '自动', '马斯克', '特斯拉']

任务4：图节点嵌入算法：DeepWalk/node2vec
- 步骤1：使用DeepWalk对Wiki数据集节点嵌入，维度为50维
- 步骤2：每个group中20%的节点作为验证集，剩余的作为训练集
- 步骤3：使用节点嵌入向量 + 逻辑回归进行训练，并记录验证集准确率
- 步骤4：使用node2vec重复上述操作
- 步骤5：使用t-SNE将节点的DeepWalk/node2vec特征降维，绘制散点图，节点颜色使用group进行区分

2014 DeepWalk: Online Learning of Social Representations, PDF

DeepWalk的思想类似word2vec，使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。

RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。

import random
def deepwalk(G, walk_length):
    nodes = G.nodes()
    history_walks = []

    # 对于每个节点
    for node in nodes:

        # 从当前节点开始
        random_walk_length = [node]

        # 开始游走
        for i in range(walk_length-1):

            # 找到节点邻居
            neighbors = list(G.neighbors(node))

            # 排除已经游走的邻居
            neighbors = list(set(neighbors) - set(random_walk_length))    
            if len(neighbors) == 0:
                break

            # 随机挑选邻居
            random_neighbor = random.choice(neighbors)            
            random_walk_length.append(random_neighbor)

            # 从下一个邻居继续游走
            node = random_neighbor

        # 此节点的游走路径
        history_walks.append(random_walk_length)

    return history_walks

g = nx.DiGraph()
# 构件图
g.add_edges_from(graph.values[:])
# 游走
history_walks = deepwalk(g, 100)

from gensim.models import Word2Vec
# 训练word2vec
w2v = Word2Vec(history_walks, vector_size=50, window=5)
# 节点类别，因为word2vec有单独节点次序
node_group = group.iloc[list(w2v.wv.key_to_index.keys())][1].values

from sklearn.manifold import TSNE

tsne = TSNE(n_components=2)
tsne_data = tsne.fit_transform(w2v.wv.vectors)

import matplotlib.cm as cm
x = np.arange(20)
ys = [i+x+(i*x)**2 for i in range(20)]
colors = cm.rainbow(np.linspace(0, 1, len(ys)))

plt.scatter(
    tsne_data[:, 0], 
    tsne_data[:, 1],
    color=colors[node_group]
)

from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression

# 划分数据集
x_tr, x_val, y_tr, y_val = train_test_split(
    w2v.wv.vectors, node_group, test_size=0.2, stratify=node_group
)

# 模型训练与验证，准确率0.535
model = LogisticRegression()
model.fit(x_tr, y_tr)
model.score(x_val, y_val)

2016 node2vec: Scalable Feature Learning for Networks, PDF

node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说，可以看作是deepwalk的一种扩展，是结合了DFS和BFS随机游走的deepwalk。node2vec依然采用随机游走的方式获取顶点的近邻序列，不同的是node2vec采用的是一种有偏的随机游走。

node2vec的游走策略（已经由节点$t$游走到节点$v$，下一步如何抉择），根据下面公式，计算出每个每个邻近节点的“值”，然后折算成概率，最后别名采样算法最终游走到的目标节点（$p$越小，embedding越倾向于表达同质性；$q$越小，embedding越倾向于表达结构性）。

假设上一步在顶点$t$，当前在顶点$v$，接下来需要计算走到顶点$x$的“权重”。$d_{tx}=0,1,2$分别表示下一步走回$t$，走到$x_1$，走到$x_2$或$x_3$的权重。（对应距离上一步位置t与下一步位置x的距离分别是0,1，2）

def next_step(graph, previous, current, p, q):
    neighbors = list(graph.neighbors(current))

    weights = []
    # Adjust the weights of the edges to the neighbors with respect to p and q.
    for neighbor in neighbors:
        if neighbor == previous:
            # Control the probability to return to the previous node.
            weights.append(1 / p)
        elif graph.has_edge(neighbor, previous):
            # The probability of visiting a local node.
            weights.append(1)
        else:
            # Control the probability to move forward.
            weights.append(1 / q)

    # Compute the probabilities of visiting each neighbor.
    weight_sum = sum(weights)
    probabilities = [weight / weight_sum for weight in weights]

    if len(neighbors) == 0:
        return None

    # Probabilistically select a neighbor to visit.    
    next = np.random.choice(neighbors, size=1, p=probabilities)[0]
    return next


def random_walk(graph, num_walks, num_steps, p, q):
    walks = []
    nodes = list(graph.nodes())
    # Perform multiple iterations of the random walk.
    for walk_iteration in range(num_walks):
        random.shuffle(nodes)

        for node in tqdm(nodes):
            # Start the walk with a random node from the graph.
            walk = [node]
            # Randomly walk for num_steps.
            while len(walk) < num_steps:
                current = walk[-1]
                previous = walk[-2] if len(walk) > 1 else None
                # Compute the next node to visit.
                next = next_step(graph, previous, current, p, q)
                if next:
                    walk.append(next)
                else:
                    break
            # Add the walk to the generated sequence.
            walks.append(walk)

    return walks

# Random walk return parameter.
p = 1

# Random walk in-out parameter.
q = 4

# Number of iterations of random walks.
num_walks = 5

# Number of steps of each random walk.
num_steps = 100

# 游走结果
walks = random_walk(g, num_walks, num_steps, p, q)

# 可视化、模型训练与验证，准确率0.555

任务5：图节点嵌入算法：LINE/SDNE
- 步骤1：使用LINE对Wiki数据集节点嵌入，维度为50维
- 步骤2：每个group中20%的节点作为验证集，剩余的作为训练集
- 步骤3：使用节点嵌入向量 + 逻辑回归进行训练，并记录验证集准确率
- 步骤4：使用SDNE重复上述操作
- 步骤5：使用t-SNE将节点的LINE/SDNE特征降维，绘制散点图，节点颜色使用group进行区分

2015 LINE: Large-scale Information Network Embedding, PDF

LINE保留了对一阶相似性和二阶相似性的敏感度。LINE考虑了二阶关系，即两个点也许不直接相连，但是如果它们的一阶公共好友比较多那么它们也被认为是比较相似的。

The first-order proximity in a network is the local pairwise proximity between two vertices. If no edge is observed between u and v, their first-order proximity is 0.

The second order proximity between a pair of vertices (u, v) in a network is the similarity between their neighborhood network structures. If no vertex is linked from/to both u and v, the second-order proximity between u and v is 0.

LINE需要定义了节点嵌入矩阵，然后去通过节点嵌入向量的内积得到相似度，并将相似度与一阶相似性和二阶相似性之间计算的KL散度，本质是让嵌入矩阵去模拟原始节点的相似性。

LINE参考资料：

first-order similariy between vertex $v_i$ and $v_j$ as follows:

$$p_1\left(v_i, v_j\right)=\frac{1}{1+\exp \left(-\vec{u}_i^T \cdot \vec{u}_j\right)}$$

2016 SDNE: Structural Deep Network Embedding, PDF

SDNE使用一个自动编码器结构来同时优化1阶和2阶相似度(LINE是分别优化的)，学习得到的向量表示能够保留局部和全局结构，并且对稀疏网络具有鲁棒性。

任务6：图节点嵌入算法：GraphGAN
- 步骤1：使用GraphGAN对Wiki数据集节点嵌入，维度为50维
- 步骤2：每个group中20%的节点作为验证集，剩余的作为训练集
- 步骤3：使用节点嵌入向量 + 逻辑回归进行训练，并记录验证集准确率
- 步骤4：使用t-SNE将节点的GraphGAN特征降维，绘制散点图，节点颜色使用group进行区分

2017 GraphGAN: Graph Representation Learning with Generative Adversarial Nets, PDF

GraphGAN是一种结合了生成模型和判别模型的框架。其中生成器拟合$P_{true}$，判别器尝试去判别两个点之间是否有边。