Python课堂笔记&课堂作业

episode8 图论

文章目录

系列文章目录
前言
一、pandas是什么？
二、使用步骤
- 1.引入库
- 2.读入数据
总结

前言

提示：这里可以添加本文要记录的大概内容：

例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

最短路径、网络流、二分图算法，Lingo

一、概念

1.什么是图？

每个图对应一个矩阵，反过来，某些矩阵可以表示成一个图。

2.网络搜索🔍？

谷歌浏览器的网页排序算法PageRank Algorithm：从250亿份网页中找到与搜索条件匹配的结果；

搜索引擎本质：不断运行计算机程序群；

搜索引擎价值：能否提供给用户无偏见的搜索结果；

PageRank Algorithm 基本思想：重要性取决于①链接到这个page的数量（代表其他网页对其认可度）②链接到它的网页的重要性。

3.求网页重要性？

任意一个网页P,I(p)表述其重要性，并称之网页排序。

假设网页 $P_{j}$ 有 $I_{j}$ 个链接。这些链接中的一个链接到网页 $P_{i}$ ，那么网页 $P_{j}$ 将把其重要性的 $1/I_{j}$ 赋给 $P_{i}$ 。故网页 $P_{i}$ 的重要性为链接到自身的其他网页所赋给的重要性家和。设链接到网页 $P_{i}$ 的其他所有网页集合为 $B_{i}$

$I(P_{I})=\sum_{P_{j}\in B_{i}}^{}\frac{I(P_{j})}{I_{j}}$

4.改写为一个数学化问题？

首先，建立一个矩阵，称之为超链矩阵(hyperlink matrix)， $H = [H_{ij}]$ ，第i行第j列元素代表第j个网页分给第i个网页的重要性为：

同时H为随机矩阵：所有元均非负且列和为1，矩阵中有一个元素满足随机分布，这个矩阵就可称为随机矩阵。

其次，定义向量 $I =[I(P_{i})]$ ，它的元素为所有网页的网页排序。

网页排序还可表示为I=HI，向量I是矩阵H对应特征值为1的特征向量，也称之为矩阵H的平稳向量（stationary vector）。

5.如何得到超链矩阵呢？

采取网络爬虫，采用随机行走，并记录下爬过的所有节点信息

二、理解

1.网页重要性排序

网页1，其指向了网页2和3，网页2和3从网页1得到的重要性均为1/2（满足列和为1），对应矩阵第一列第2、3个元素值为1/2；

网页2，其指向了网页4，网页4从网页2得到的重要性为1，对应矩阵第二列第四个元素值为1；

网页3，其指向了网页2和5，网页2和5从网页3得到的重要性均为1/2，对应矩阵第三列第2、5个元素值为1/2；

同理可得，网页4，5，6，7，8。

重要性：8>6>7>5>4=2>1>3

import numpy as np
#构造一个矩阵
A = np.array([[0,0,0,0,0,0,1/3,0],
[1/2,0,1/2,1/3,0,0,0,0],
[1/2,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0],
[0,0,1/2,1/3,0,0,1/3,0],
[0,0,0,1/3,1/3,0,0,1/2],
[0,0,0,0,1/3,0,0,1/2],
[0,0,0,0,1/3,1,1/3,0]])
print('打印矩阵A：\n{}'.format(A))
a, b = np.linalg.eig(A)
print('打印特征值a：\n{}'.format(a))
print('打印特征向量b：\n{}'.format(b))

对目前打印出来的结果并不满意：

2.阴影化处理

重要性：8>6>7>5>4=2>1>3

网页排序值越高的网页阴影越浅

三、举例应用

1.求超链矩阵的平稳向量的方法？

超链矩阵H的每一列对应谷歌检索到的一个网页，也就是说H大约有n=250亿行和列。

$H_{ij}$ 矩阵中的第i行第j列，代表第j个网页分给第i行的重要性值。

其中大多数为0，因为每个网页只链接到有限的网页。

方法：幂法

幂法是一种计算矩阵主特征值（矩阵按模最大的特征值）及对应特征向量的迭代方法，特别是用于大型稀疏矩阵。（由实际生活中信息抽象出的矩阵大多是稀疏矩阵）

2.幂法的实现

首先选择 $I$ 的备选项 $I^{0}$ ,进而按下式产生向量序列 $I^{k}$

如下图所示的表格，表中数字表征网页的重要性，但并不是绝对的度量，只是有比较的比例度量。这样我们可以用固定量乘以所有重要性排序，使受欢迎程度和为1，而不影响排序。

2.1如何处理悬挂点？

没有任何链接的网页称为悬挂点

3.H的概率化解释

跳转网页是随机的，假设停留在网页 $P_{j}$ 上的时间为 $T_{j}$ ，从网页 $P_{j}$ 跳转到网页 $P_{i}$ 的时间为 $T_{j}/I_{j}$ 。

如果我们转到了网页 $P_{i}$ ，那么我们必然是从一个指向它的网页而来。则有：

$T_{i}=\sum_{P_{j}\in B_{i}}^{}\frac{T_{j}}{I_{j}}$

其中，是对所有链接到 $P_{i}$ 网页的网页 $P_{j}$ 进行求和的。

我们会发现这个方程与定义网页排序值的方程相同，于是有 $I(P_{j})= T_{j}$ 。

一个网页的排序值可以解释为随机跳转时花费在这个网页上的时间。

在搜索某一信息时，它们重要性靠前，随机跳转累计在这些网页上时间就多。

4.H的概率化解释存在的问题（疑点）

随机跳转网页到一定程度，我们会被困在某个悬挂点上，这个网页没有给出任何链接。

为了能够继续进行，我们需要随机选取下一个网页；换言之，我们假定悬挂点可以链接到任何一个网页。对超链接矩阵做修正：将其中所有元都为0的列替换为所有元均为1/n的列，修正后不存在悬挂点。

eg:

修正后:

5.幂法如何实现？

幂法一般用来寻找矩阵对应于绝对值最大的特征值的特征向量。此时我们需要寻找矩阵S对应于特征值为1的特征向量。则最好的情形就行，其他特征值的绝对值都小于1，即其他|λ|<1 。

假定矩阵S的特征值为λj，且存在：1=λ1>|λ2|≥|λ3|≥⋯≥|λn|，对于矩阵s，假设对于特征值λj 的特征向量存在一个基向量

一、pandas是什么？

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

二、使用步骤

1.引入库

代码如下（示例）：

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import warnings
warnings.filterwarnings('ignore')
import  ssl
ssl._create_default_https_context = ssl._create_unverified_context

2.读入数据

代码如下（示例）：

data = pd.read_csv(
    'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())

该处使用的url网络请求的数据。

总结

提示：这里对文章进行总结：

例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

8.pagerank算法图论算法随机算法

Python课堂笔记&课堂作业

文章目录

前言

一、概念

1.什么是图？

2.网络搜索🔍？

3.求网页重要性？

4.改写为一个数学化问题？

5.如何得到超链矩阵呢？

二、理解

1.网页重要性排序

2.阴影化处理

三、举例应用

1.求超链矩阵的平稳向量的方法？

方法：幂法

2.幂法的实现

2.1如何处理悬挂点？

3.H的概率化解释

4.H的概率化解释存在的问题（疑点）

5.幂法如何实现？

一、pandas是什么？

二、使用步骤

1.引入库

2.读入数据

总结

网站公告

今日签到

热门文章

最新发布

8.pagerank算法 图论算法 随机算法

Python课堂笔记&课堂作业

文章目录

前言

一、概念

1.什么是图？

2.网络搜索🔍？

3.求网页重要性？

4.改写为一个数学化问题？

5.如何得到超链矩阵呢？

二、理解

1.网页重要性排序

2.阴影化处理

三、举例应用

1.求超链矩阵的平稳向量的方法？

方法：幂法

2.幂法的实现

2.1如何处理悬挂点 ？

3.H的概率化解释

4.H的概率化解释存在的问题（疑点）

5.幂法如何实现？

一、pandas是什么？

二、使用步骤

1.引入库

2.读入数据

总结

网站公告

今日签到

热门文章

最新发布

8.pagerank算法图论算法随机算法

2.1如何处理悬挂点？