第二次作业

计算题

1. 给定图 $G$（如图 1，图中数值为边权值），图切割将其分割成多个互不连通的⼦图。请使⽤谱聚类算法将图 $G$ 聚类成 $k=2$ 类，使得：

   (a) RatioCut 最⼩；

   (b) NormalizedCut 最⼩。

   并给出计算过程，以及对应的 RatioCut 值和 NormalizedCut 值。

   

【解】

该图的邻接矩阵表示为：
$$W=\left[\begin{array}{cccccc}0& 0.5& 0.4& 0& 0& 0\\ 0.5& 0& 0.6& 0& 0& 0\\ 0.4& 0.6& 0& 0.9& 0& 0\\ 0& 0& 0.9& 0& 0.2& 0.1\\ 0& 0& 0& 0.2& 0& 0.7\\ 0& 0& 0& 0.1& 0.7& 0\end{array}\right]$$
度矩阵为：
$$D=\left[\begin{array}{cccccc}0.9& 0& 0& 0& 0& 0\\ 0& 1.1& 0& 0& 0& 0\\ 0& 0& 1.9& 0& 0& 0\\ 0& 0& 0& 1.2& 0& 0\\ 0& 0& 0& 0& 0.9& 0\\ 0& 0& 0& 0& 0& 0.8\end{array}\right]$$
（a）RatioCut 最⼩

拉普拉斯矩阵为：
$$L=D-W=\left[\begin{array}{cccccc}0.9& -0.5& -0.4& 0& 0& 0\\ -0.5& 1.1& -0.6& 0& 0& 0\\ -0.4& -0.6& 1.9& -0.9& 0& 0\\ 0& 0& -0.9& 1.2& -0.2& -0.1\\ 0& 0& 0& -0.2& 0.9& -0.7\\ 0& 0& 0& -0.1& -0.7& 0.8\end{array}\right]$$
其特征值为：
$$\lambda =\left[\begin{array}{c}0\\ 0.16611\\ 0.87866\\ 1.49543\\ 1.55934\\ 2.70047\end{array}\right]$$
对应的特征向量为：
$$X=\left[\begin{array}{cccccc}0.40825& 0.40239& 0.48507& 0.64252& 0.11036& -0.10542\\ 0.40825& 0.38254& 0.26567& -0.71241& -0.18567& -0.27279\\ 0.40825& 0.2601& -0.30622& -0.06593& 0.05017& 0.81551\\ 0.40825& 0.06722& -0.7402& 0.15974& 0.09372& -0.4966\\ 0.40825& -0.53361& 0.0817& 0.14535& -0.71975& 0.05253\\ 0.40825& -0.57865& 0.21398& -0.16927& 0.65116& 0.00678\end{array}\right]$$
对应 ${\lambda }_2$ 的特征向量 $x_2$ 进行聚类，显然 1、2、3、4 为一类，5、6 为一类。

则
$$RatioCut=\frac{1}{2}(\frac{0.3}{4}+\frac{0.3}{2})=\frac{9}{80}$$

（b）NormalizedCut 最小

归一化的 Laplacian 矩阵 $D^{-1/2}L{D}^{-1/2}$ 为：
$$\left[\begin{array}{cccccc}1& -0.50251891& -0.30588765& 0& 0& 0\\ -0.50251891& 1& -0.41502868& 0& 0& 0\\ -0.30588765& -0.41502868& 1& -0.59603956& 0& 0\\ 0& 0& -0.59603956& 1& -0.19245009& -0.10206207\\ 0& 0& 0& -0.19245009& 1& -0.82495791\\ 0& 0& 0& -0.10206207& -0.82495791& 1\end{array}\right]$$

特征值:
$$\lambda =\left[\begin{array}{c}0\\ 0.16610702\\ 0.87866007\\ 1.49542669\\ 1.55933786\\ 2.70046837\end{array}\right]$$

特征向量:
$$X=\left[\begin{array}{cccccc}0.36380344& 0.32111434& 0.46859317& -0.73715774& -0.03109895& 0.02417422\\ 0.40219983& 0.34555671& 0.41895846& 0.63385743& -0.36350558& 0.09689228\\ 0.52859414& 0.29700834& -0.33377341& 0.14238799& 0.67065213& -0.22565677\\ 0.42008403& 0.00503849& -0.66179385& -0.18039115& -0.54411556& 0.23860055\\ 0.36380344& -0.58690394& 0.13587453& -0.00424251& -0.18874965& -0.68489744\\ 0.34299717& -0.58718018& 0.19250083& 0.04460851& 0.29229112& 0.64272217\end{array}\right]$$

对 ${\lambda }_2$ 对应的特征向量进行聚类，易知 1、2、3、4 为一类，5、6 为一类。
$$NormalizedCut=\frac{1}{2}(\frac{0.3}{5.1}+\frac{0.3}{1.7})=\frac{2}{17}$$

2. 参数未知的正态分布⽣成了如下 4 个数据：-12.2119174, 7.62328757, 9.60884573, -8.36968016。请使⽤极⼤似然估计⽅法估计出正态分布的参数，写出计算过程。（注：若数值计算过程较为复杂，可以使⽤ python 相关库进⾏计算，但仍需给出计算推导过程。）

【解】

设总体服从正态分布：
$$f(x)=\frac{1}{\sqrt{2\pi }\sigma }{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}}$$

有一组观测值为 $X_1,X_2,...,X_n$，似然函数以及对数函数为：
$$\begin{array}{rl}L(\mu ,{\sigma }^2)& =\prod _{i=1}^n\frac{1}{\sqrt{2\pi }\sigma }{e}^{-\frac{(X_i-\mu {)}^2}{2{\sigma }^2}}\\ \ln L(\mu ,{\sigma }^2)& =-\frac{n}{2}\ln (2\pi )-n\ln (\sigma )-\frac{1}{2{\sigma }^2}\sum _{i=1}^n(X_i-\mu {)}^2\end{array}$$
分别对两个参数求导数：
$$\begin{gathered} \frac{\partial \ln L(\mu ,{\sigma }^2)}{\partial \mu }=\frac{{\sum }_{i=1}^n(X_i-\mu )}{{\sigma }^2}=0 \\ \frac{\partial \ln L(\mu ,{\sigma }^2)}{\partial {\sigma }^2}=-\frac{n}{2{\sigma }^2}+\frac{{\sum }_{i=1}^n(X_i-\mu {)}^2}{2{\sigma }^4}=0 \end{gathered}$$
解得：

$$\begin{gathered} \hat{\mu }=\overline{X} \\ {\hat{\sigma }}^2=\frac{n-1}{n}{S}^2 \end{gathered}$$
经计算：

$$\begin{gathered} \hat{\mu }=-0.8373660650000001 \\ {\hat{\sigma }}^2=91.70554362393045 \end{gathered}$$

3. HITS 全称是 Hyperlink-Induced Topic Search，即超链接诱导主题搜索，是⼀个链接分析⽅法，由康奈尔⼤学的 Kleinberg 教授提出。HITS 算法中有 2 个⽐较重要的概念，⼀个是“Authority”⻚⾯，另⼀个是“Hub”⻚⾯。“Authority”，即权威，所有权威⻚⾯，是指⻚⾯本⾝的质量⽐较⾼，⽐如，百度搜索或者⾕歌搜索⾸⻚。“Hub”，即枢纽，表示本⻚⾯指向的其他很多⾼质量的“Authority”⻚⾯。⼀个好的“Authority”会被很多好的“Hub”⻚⾯指向。⼀个好的“Hub”⻚⾯会指向很多好的“Authority”⻚⾯。权威值和枢纽值是互相依存、互相影响的。⽹⻚的权威值是所有指向它的⽹⻚的枢纽值之和：
   a u t h ( p ) = ∑ q ∈ { 指向 p 的网页 } h u b ( q ) auth(p)=\sum_{q\in\{指向p的网页\}}hub(q) auth(p)=q∈{指向p的网页}∑​hub(q)
   ⽹⻚的枢纽值是所有它指向⽹⻚的权威值之和：
   h u b ( p ) = ∑ q ∈ { p 指向的网页 } a u t h ( q ) hub(p)=\sum_{q\in\{p指向的网页\}}auth(q) hub(p)=q∈{p指向的网页}∑​auth(q)
   HITS 算法流程如下：

   1. 初始化：将各节点的权威值和枢纽值均设为 1。

   2. 更新节点的权威值；

   3. 更新节点的枢纽值；

   4. 将权威值和枢纽值归⼀化，即权威值和枢纽值分别和为 1；

   5. 重复 2-4 步骤，直⾄最终收敛。

      （a）根据如图 2 所示的⽹络关系，每个节点的 PageRank 初始值都是 1 写出 PageRank 算法前两轮迭代的过程。

      （b）根据如图 2 所示的⽹络关系，每个节点的初始权威值和枢纽值均设为 1，写出 HITS 算法前两轮迭代的过程。
      

【解】

（a）PageRank

PageRank 转移矩阵为：
$$M=\left[\begin{array}{ccccc}0& 0& 0& 0& 1\\ 1/2& 0& 0& 0& 0\\ 1/2& 1/2& 0& 0& 0\\ 0& 1/2& 0& 0& 0\\ 0& 0& 1& 1& 0\end{array}\right]$$
每个节点的 PageRank 初始值都是 1 ，即
$$P{R}^0(n_1)=1,P{R}^0(n_2)=1,P{R}^0(n_3)=1,P{R}^0(n_4)=1,P{R}^0(n_5)=1$$

$$\left[\begin{array}{c}{n}_1\\ n_2\\ n_3\\ n_4\\ n_5\end{array}\right]=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\\ 1\end{array}\right]$$

第一次迭代：
$$\left[\begin{array}{ccccc}0& 0& 0& 0& 1\\ 1/2& 0& 0& 0& 0\\ 1/2& 1/2& 0& 0& 0\\ 0& 1/2& 0& 0& 0\\ 0& 0& 1& 1& 0\end{array}\right]\left[\begin{array}{c}1\\ 1\\ 1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}1\\ 1/2\\ 1\\ 1/2\\ 2\end{array}\right]$$
即 $P{R}^1(n_1)=1,P{R}^1(n_2)=1/2,P{R}^1(n_3)=1,P{R}^1(n_4)=1/2,P{R}^1(n_5)=2$；

第二次迭代：
$$\left[\begin{array}{ccccc}0& 0& 0& 0& 1\\ 1/2& 0& 0& 0& 0\\ 1/2& 1/2& 0& 0& 0\\ 0& 1/2& 0& 0& 0\\ 0& 0& 1& 1& 0\end{array}\right]\left[\begin{array}{c}1\\ 1/2\\ 1\\ 1/2\\ 2\end{array}\right]=\left[\begin{array}{c}2\\ 1/2\\ 3/4\\ 1/4\\ 3/2\end{array}\right]$$
即 $P{R}^2(n_1)=2,P{R}^2(n_2)=1/2,P{R}^2(n_3)=3/4,P{R}^2(n_4)=1/4,P{R}^2(n_5)=3/2$。

（b）HITS

网页的初始权威值和枢纽值如下：
$$AUT{H}^0=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\\ 1\end{array}\right],HU{B}^0=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\\ 1\end{array}\right]$$

更新权威值规则如下：
$$\begin{array}{rl}aut{h}^{t+1}(n_1)& =hu{b}^t(n_5)\\ aut{h}^{t+1}(n_2)& =hu{b}^t(n_1)\\ aut{h}^{t+1}(n_3)& =hu{b}^t(n_1)+hu{b}^t(n_2)\\ aut{h}^{t+1}(n_4)& =hu{b}^t(n_2)\\ aut{h}^{t+1}(n_5)& =hu{b}^t(n_3)+hu{b}^t(n_4)\end{array}$$

更新枢纽值规则如下：
$$\begin{array}{rl}hu{b}^t(n_1)& =aut{h}^t(n_2)+aut{h}^t(n_3)\\ hu{b}^t(n_2)& =aut{h}^t(n_3)+aut{h}^t(n_4)\\ hu{b}^t(n_3)& =aut{h}^t(n_5)\\ hu{b}^t(n_4)& =aut{h}^t(n_5)\\ hu{b}^t(n_5)& =aut{h}^t(n_1)\end{array}$$
第一次迭代：
$$AUT{H}^1=\left[\begin{array}{c}1\\ 1\\ 2\\ 1\\ 2\end{array}\right],HU{B}^1=\left[\begin{array}{c}3\\ 3\\ 2\\ 2\\ 1\end{array}\right]$$
进行归一化，
$$AUT{H}^1=\left[\begin{array}{c}\frac{1}{7}\\ \frac{1}{7}\\ \frac{2}{7}\\ \frac{1}{7}\\ \frac{2}{7}\end{array}\right],HU{B}^1=\left[\begin{array}{c}\frac{3}{11}\\ \frac{3}{11}\\ \frac{2}{11}\\ \frac{2}{11}\\ \frac{1}{11}\end{array}\right]$$
第二次迭代：
$$AUT{H}^2=\left[\begin{array}{c}\frac{1}{11}\\ \frac{3}{11}\\ \frac{6}{11}\\ \frac{3}{11}\\ \frac{4}{11}\end{array}\right],HU{B}^2=\left[\begin{array}{c}\frac{9}{11}\\ \frac{9}{11}\\ \frac{4}{11}\\ \frac{4}{11}\\ \frac{1}{11}\end{array}\right]$$
进行归一化，
$$AUT{H}^2=\left[\begin{array}{c}\frac{1}{17}\\ \frac{3}{17}\\ \frac{6}{17}\\ \frac{3}{17}\\ \frac{4}{17}\end{array}\right],HU{B}^2=\left[\begin{array}{c}\frac{1}{3}\\ \frac{1}{3}\\ \frac{4}{27}\\ \frac{4}{27}\\ \frac{1}{27}\end{array}\right]$$

4. 假设机器⼈必须越过迷宫并到达终点。有地雷，机器⼈⼀次只能移动⼀个地砖。 如果机器⼈踏上地雷，机器⼈就死了。机器⼈必须在尽可能短的时间内到达终点。请给出第 1 轮之后和第 2 轮之后 Q-table 中每个位置的值。并对第⼀列的所有值写出计算过程。学习率设为 0.2，折扣因⼦为 0.1。

【解】

$Q$ 函数，$Q^{new}(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \cdot (r_t+\gamma \cdot ma{x}_{a}Q(s_{t+1},a)-Q(s_t,a_t))$

其中，$\alpha =0.2,\gamma =0.1$。

Step1. 初始化 Q-Table：

state \ action	上	右	下	左
START	0	0	0	0
BLANK	0	0	0	0
CAKE	0	0	0	0
SUN	0	0	0	0
BOMB	0	0	0	0
EXIT	0	0	0	0

Step2. 更新 Q_table，其中 $ϵ=0.1$。

两轮如下：

第一轮中第一列计算过程：

$$Q^{new}(BLANK,UP)=0+0.2\ast (-1+0.1\ast 1.44-0)=-0.171$$
第二轮第一列计算过程：
$$\begin{array}{rl}{Q}^{new}(SUN,UP)& =0+0.2\ast (-1+0.1\ast 3.152-0)=-0.137\\ Q^{new}(BLANK,UP)& =-0.171+0.2\ast (-1+0.1\ast 1.239+0.171)=-0.312\end{array}$$

5. 假设有四个观测点，分别为(-4，-0.55), (1, 0.45) , (-0.5, 0.22)和(5，1.25)，⽤最⼩⼆乘法求解直线 $y=ax+b$ 使其最佳拟合这些散点。给出求解过程。

【解】

方法一：

建立模型如下，
$$mi{n}_{a,b}f(a,b)=\sum _{i=1}^n(a{x}_i+b-y_i{)}^2$$
分别对 $a,b$ 进行求偏导数，并令其为 0，
$$\{\begin{array}{l}\frac{\partial f}{\partial a}=2{\sum }_{i=1}^n{x}_i(a{x}_i+b-y_i)=0\\ \frac{\partial f}{\partial b}=2{\sum }_{i=1}^n(a{x}_i+b-y_i)=0\end{array}$$
化简可得解为：
$$\begin{array}{rl}\hat{a}& =\frac{n{\sum }_{i=1}^n{x}_i{y}_i-{\sum }_{i=1}^n{x}_i{\sum }_{i=1}^n{y}_i}{n{\sum }_{i=1}^n{x}_i^2-({\sum }_{i=1}^n{x}_i{)}^2}\\ \hat{b}& =\frac{({\sum }_{i=1}^n{y}_i)-a({\sum }_{i=1}^n{x}_i)}{n}\end{array}$$
将以下值代入上述公式，
$$\begin{array}{rl}\sum _{i=1}^4{x}_i& =-4+1-0.5+5=1.5\\ \sum _{i=1}^4{y}_i& =-0.55+0.45+0.22+1.25=1.37\\ \sum _{i=1}^4{x}_i{y}_i& =(-4)(-0.55)+1\times 0.45+(-0.5)\times 0.22+5\times 1.25=8.79\\ \sum _{i=1}^4{x}_i^2& =(-4{)}^2+(1{)}^2+(-0.5{)}^2+(5{)}^2=42.25\end{array}$$
得，
$$\begin{array}{rl}\hat{a}& =\frac{4\times 8.79-1.5\times 1.37}{4\times 42.25-1.5^2}=0.1985\\ \hat{b}& =\frac{1.37-0.1985\times 1.5}{4}=0.2681\end{array}$$
方法二：

$$\theta =({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^{T}y$$

编程题

说明：建议使⽤开源⼯具包，例如 scikit-learn 中有朴素⻉叶斯、⾼斯混合模型等函数实现， sknetwork 中有 PageRank 函数实现。

Node2vec 数据集：PageRank_Dataset.csv。

任务描述：利⽤ Node2vec 计算每个节点的 embedding 值。

要求输出：

1）每个节点的 embedding 值列表（csv ⽂件）；

2）随机挑选 10 个 node pair，对⽐他们在 embedding 上的相似度和在 betweenness centrality 上的相似度（使⽤ Jaccard similarity）。

代码如下：

import pandas as pd
import networkx as nx
from node2vec import Node2Vec
from sklearn.metrics.pairwise import cosine_similarity
from sklearn.preprocessing import MinMaxScaler

# Load the dataset
data = pd.read_csv('PageRank_Dataset.csv')

# Create a graph from the dataset
graph = nx.from_pandas_edgelist(data, source='node_1', target='node_2')

# Run Node2Vec to compute node embeddings
node2vec = Node2Vec(graph, dimensions=128, walk_length=30, num_walks=200, workers=4)
model = node2vec.fit(window=10, min_count=1, batch_words=4)

# Get embeddings for all nodes
embeddings = {}
for node in graph.nodes:
    embeddings[node] = model.wv[node]

# Save the embeddings to a CSV file
df = pd.DataFrame.from_dict(embeddings, orient='index')
df.to_csv('node_embeddings.csv')

# Randomly select 10 node pairs
node_pairs = data.sample(n=10)[['node_1', 'node_2']]

# Compute similarity based on embeddings
similarity_embeddings = []
for _, row in node_pairs.iterrows():
    source_embedding = embeddings[row['node_1']]
    target_embedding = embeddings[row['node_2']]
    similarity = cosine_similarity([source_embedding], [target_embedding])[0][0]
    similarity_embeddings.append(similarity)

# Compute similarity based on betweenness centrality
betweenness_centrality = nx.betweenness_centrality(graph)
similarity_betweenness = []
for _, row in node_pairs.iterrows():
    source_betweenness = betweenness_centrality[row['node_1']]
    target_betweenness = betweenness_centrality[row['node_2']]
    jaccard_similarity = len(set(nx.neighbors(graph, row['node_1'])).intersection(nx.neighbors(graph, row['node_2']))) / \
                         len(set(nx.neighbors(graph, row['node_1'])).union(nx.neighbors(graph, row['node_2'])))
    similarity_betweenness.append(jaccard_similarity)

# Print the similarities
for i in range(len(node_pairs)):
    print(f"Node Pair {i+1}:")
    print(f"Similarity based on embeddings: {similarity_embeddings[i]}")
    print(f"Similarity based on betweenness centrality: {similarity_betweenness[i]}")
    print()

每个节点的 embedding 值列表（csv ⽂件）见附件 Node_Embeddings.csv。

10 个 node pair 的相似度如下：

Node Pair 1:
Similarity based on embeddings: 0.2817123532295227
Similarity based on betweenness centrality: 0.0

Node Pair 2:
Similarity based on embeddings: 0.15493448078632355
Similarity based on betweenness centrality: 0.0

Node Pair 3:
Similarity based on embeddings: 0.20358529686927795
Similarity based on betweenness centrality: 0.022099447513812154

Node Pair 4:
Similarity based on embeddings: 0.15917743742465973
Similarity based on betweenness centrality: 0.0

Node Pair 5:
Similarity based on embeddings: 0.20524653792381287
Similarity based on betweenness centrality: 0.02702702702702703

Node Pair 6:
Similarity based on embeddings: 0.09693200141191483
Similarity based on betweenness centrality: 0.15517241379310345

Node Pair 7:
Similarity based on embeddings: 0.1875799596309662
Similarity based on betweenness centrality: 0.2608695652173913

Node Pair 8:
Similarity based on embeddings: 0.24301061034202576
Similarity based on betweenness centrality: 0.0

Node Pair 9:
Similarity based on embeddings: 0.5237224102020264
Similarity based on betweenness centrality: 0.23529411764705882

Node Pair 10:
Similarity based on embeddings: 0.20514701306819916
Similarity based on betweenness centrality: 0.26785714285714285