权限

以超级管理员的身份执行命令：sudo ;

切换成kytolly用户：su kytolly ;

切换超级管理员用户: su ;

为password.txt添加可执行权限：chmod +x password.txt;

进程号/端口号

1. 查看端口占用
   • lsof -i <pid>:
   • netstat -ntulp |grep <pid>:
2. 杀死进程
   • kill <pid>:

拨号上网

1. 配置拨号连接:sudo pppconf
2. 启动拨号连接：pon dsl-provider
3. 断开拨号连接：sudo poff dsl-provider
4. 检查网络通畅：ping 39.156.66.14 ping 8.8.8.8
5. 检查DNS：ping www.baidu.com

重定向

一般情况下，每个 Unix/Linux 命令运行时都会打开三个文件：

• 标准输入文件(stdin)：stdin的文件描述符为0，Unix程序默认从stdin读取数据。
• 标准输出文件(stdout)：stdout 的文件描述符为1，Unix程序默认向stdout输出数据。
• 标准错误文件(stderr)：stderr的文件描述符为2，Unix程序会向stderr流中写入错误信息。

默认情况下，command > file 将 stdout 重定向到 file，command < file 将stdin 重定向到 file。

Shell字符串测试

Shell文件测试

Shell关系运算符

Shell函数参数

Git架构

在任何当前工作的 Git 仓库中，每个文件都是这样的：

• 追踪的（tracked）-：这些是 Git 所知道的所有文件或目录。这些是新添加（用 git add 添加）和提交（用 git commit 提交）到主仓库的文件和目录。
• 未被追踪的（untracked） ：这些是在工作目录中创建的，但还没有被暂存（或用 git add 命令添加）的任何新文件或目录。
• 被忽略的（ignored）：这些是 Git 知道的要全部排除、忽略或在 Git 仓库中不需要注意的所有文件或目录。本质上，这是一种告诉 Git 哪些未被追踪的文件应该保持不被追踪并且永远不会被提交的方法。

查看Git本地配置

设置账号，密码

1
2

git config --global user.name "Your Name"
git config --global user.email "your.email@example.com"

.gitignore详解

所有被忽略的文件都会被保存在一个 .gitignore 文件中;

.gitignore 文件是一个纯文本文件，包含了项目中所有指定的文件和文件夹的列表，这些文件和文件夹是 Git 应该忽略和不追踪的;

一个 .gitignore 文件会被放在仓库的根目录下，也可以放在仓库的任何文件夹下，一个仓库可以有多个.gitignore;

名字前面有点（.）的文件默认是隐藏的;

为什么要忽略某些文件上传？

忽略某些文件上传是因为这些文件通常是本地环境特有的，或者是没有必要被版本控制的文件。以下是一些常见的原因：

• 本地配置文件：开发者的本地配置文件（如编辑器配置、环境变量配置等）通常因人而异，不应该上传到公共仓库。
• 编译或生成的文件：编译生成的文件（如*.class文件、dist/目录等）可以通过源代码重新生成，上传它们既浪费空间，也会让仓库变得臃肿。
• 敏感信息：如API密钥、数据库密码等敏感信息不应该上传到公共仓库，以防泄露。
• 依赖库：如node_modules/、vendor/等第三方依赖库不需要放在版本控制系统中，通常会通过包管理工具（如npm、composer等）自动下载和安装。
• 日志文件和临时文件：如*.log文件、*.tmp文件等，是开发过程中的临时数据，不需要上传到仓库中。

什么文件应该被忽略？

根据项目类型和开发环境，以下是一些常见的需要忽略的文件和目录：

• 操作系统生成的文件
  • .DS_Store（macOS）
  • Thumbs.db（Windows）
• 依赖库和包
  • node_modules/（Node.js）
  • vendor/（PHP Composer）
  • Pods/（iOS Cocoapods）
• 编译输出文件
  • *.class（Java）
  • *.o, *.so（C/C++）
  • dist/, build/（前端项目）
• 环境配置文件
  • .env
  • *.local（环境特定的配置）
• IDE和编辑器生成的文件
  • .vscode/, .idea/
  • *.suo, *.user（Visual Studio）
• 日志文件
  • *.log
• 其他临时文件
  • *.tmp
  • *.swp（Vim）
  • *.bak（备份文件）

.gitignore中格式是怎样的？

.gitignore 文件的格式简单且灵活。以下是一些常见的规则：

• 每行一个模式，表示要忽略的文件或目录。
• 可以使用通配符 * 来匹配任意字符。
• # 用于注释说明，不会影响规则。
• 以斜杠 / 结尾表示目录。
• 可以使用 ! 前缀来否定一个忽略规则。
• 可以指定文件的完整路径或使用相对路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 忽略所有 .log 文件
*.log

# 忽略目录
node_modules/
dist/

# 忽略特定文件
config/database.yml

# 忽略所有的 .env 文件，但不忽略 .env.example
.env
!.env.example

# 忽略 IDE 生成的文件夹
.idea/
.vscode/

# 忽略系统生成的文件
.DS_Store
Thumbs.db

推荐系统

[TOC]

概念

推荐系统的任务：联系用户和物品，解决信息过载的问题；

• 好友（社会化推荐）
• 用户的历史兴趣记录（协同过滤推荐）
• 用户的注册信息

为什么推荐系统收到欢迎：

• 用户：可以帮助用户发现喜欢的新事物
• 商家：提高用户信任度和粘性，增加营收

信息过滤技术比较

• 搜索引擎满足用户有目的地主动查找需求；
• 推荐系统能够在用户没有明确目的时帮助发现感兴趣的新内容；

评测方法

一个推荐算法最终上线，必须完成

• 离线实验：在离线指标上优于现有算法
• 用户调查：确定用户满意度较优
• 在线AB测试：确定在关心的指标上较优

离线实验

步骤

1. 通过日志系统获得用户行为数据，并按照一定格式生成一个标准的数据集；
2. 将数据集按照一定的规则分成训练集和测试集；
3. 在训练集上训练用户兴趣模型，在测试集上进行预测；
4. 通过事先定义的离线指标评测算法在测试集上的预测结果。

优点

• 实验都是在数据集上完成的，不需要一个实际的系统来供它实验
• 不需要用户参与实验，成本低
• 速度快，可以测试大量算法

缺点：

• 无法计算商业上关心的指标
• 离线实验的指标和商业指标存在差距

用户调查

步骤

1. 用户调查需要一些真实的用户，让他们在需要测试的推荐系统上完成一些任务。
2. 在他们完成任务时，需要观察和记录用户的行为，并让他们回答一些问题。
3. 最后，我们通过分析他们的行为和答案，了解测试系统的性能。

优点：

• 可以获得用户的主观感受指标，出错后容易弥补

缺点：

• 招募测试用户代价较大
• 无法组织大规模的测试用户，统计意义不足

在线实验

在完成离线实验和用户调查之后，可以将系统上线做AB测试，将它和旧算法进行比较。
AB测试通过一定的规则将用户随机分成几组，对不同组的用户采用不同的算法，然后通过统计不同组的评测指标，比较不同算法的好坏。

• 多个方案并行测试；
• 每个方案采用不同的推荐算法；
• 以某种规则优胜劣汰。

优点：

• 可以公平获得不同算法实际在线的性能指标，包括商业上关注的指标；

缺点：

• 周期长，必须进行长期的实验才能得到可靠的结果
• 设计比较复杂

评测指标

• 用户满意度：描述用户对推荐结果对的满意程度，是最重要的指标，问卷调查/监测用户线上行为数据
• 预测准确度：描述推荐系统预测用户行为的能力。对用户$u$，推荐的物品集合为$R(u)$,在测试集上喜欢物品的集合$T(u)$，可用$Precision=\frac{\sum_u |R(u)\cap T(u) |}{\sum_u |R(u)| }$计算
• 覆盖率：描述推荐系统对长尾物品的发掘能力。一般通过所有推荐物品占总物品的比例来计算。比例越大，则覆盖率越大。
• 多样性：描述推荐系统中推荐结果能否覆盖用户不同的兴趣领域。一般用不相似度描述；
• 新颖性：如果用户没有听说过推荐列表中的大部分物品，则说明该推荐系统的新颖性较好，需要做用户调查；
• 惊喜度：如果推荐结果和用户的历史兴趣不相似，但让用户很满意，则可以说这是一个让用户惊喜的推荐。可以用历史兴趣和用户满意度来衡量；
• 信任度：描述用户对推荐系统的信任程度。只能问卷调查了解；
• 实时性：时效性强的物品在进行推荐时必须考虑推荐系统处理物品冷启动的能力，可以采用人工推荐。
• 健壮性：衡量推荐系统抗作弊能力；
• 商业目标：平均一个用户是否能为公司带来盈利；

模块

用户

对象：单用户建模/群组建模
功能：能获取、表示、存储和修改用户兴趣爱好，能够进行推理对用户进行分类和识别，帮助系统更好地理解用户特征和类别，理解用户的需求和任务，从而更好地实现用户所需要的功能

推荐对象

基于内容的方法：从对象本身抽取信息来表示对象，常见TF-IDF方法和加权关键词矢量。
基于分类的方法：将推荐对象放入不同类，这样可以把同类文档推荐给该类文档感兴趣的用户了。分类常用算法Naive-Bayes,KNN,SVM;
潜在问题：

• 文本等对象特征提取技术相对比较成熟，但是网络上广泛存在的多媒体数据等的提取技术不够成熟，自动化的特征提取方法需要结合多媒体内容分析领域的相关技术。
• 推荐系统推荐给用户的对象首先不能与用户看过的对象重复，其次也不能与用户刚刚看过的太相似或是不相关，这就是所谓的模型过拟合问题。
• 推荐系统中出现新的对象时，新对象必须等待一段时间才会有用户查看并进行评价，在此之前推荐系统无法对此对象进行分析和推荐，这就是冷启动问题。

推荐算法

推荐算法很大程度上决定了推荐系统类型和性能的优劣；

基于内容推荐

物品的特征表示

为每个物品抽取出一些特征来表示此物品

• 结构化特征：属性意义比较明确，取值限定在某个范围，一般可以直接使用，如年龄、性别等。
• 非结构化特征：属性意义不明确，取值也没有什么限制，往往要先把它转化为结构化数据后才能在模型里使用。
  文章特征表示：
  相似度计算：

用户特征学习

利用一个用户过去喜欢（及不喜欢）的物品的特征数据，来学习出此用户的喜好特征。

生成推荐列表

通过比较上一步得到的用户喜好特征与候选物品的特征，为此用户推荐一组相关性最大的物品；

协同过滤推荐

用户行为数据

基于邻域的方法

基于用户（人以群分）

• 特点：社会化，着重于反应和用户相似度相似的小群体热点；

• 思路：

  1. 找到目标用户兴趣相似的用户集合
  2. 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户；

• 余弦相似度计算:定义用户$u$对所有物品的评价向量$r_u$
  $$
  s(u,v)=\frac{r_ur_v}{|r_u||r_v|}
  $$

• 皮尔逊相关系数：对于用户可能对某些物品的打分缺省的情况，定义如下
  $$
  s(u,v)=\frac{\sum_{i\in I_u\cap I_v}(r_u^{(i)}-\overline{r_u})(r_v^{(i)}-\overline{r_v})}{\sqrt{\sum_{i\in I_u\cap I_v}(r_u^{(i)}-\overline{r_u})^2}\sqrt{\sum_{i\in I_u\cap I_v}(r_v^{(i)}-\overline{r_v})^2}}
  $$

• 预测分值:记邻居集中对物品$i$有过评分记录的用户集为$N$;
  $$
  p_{u,i}=\overline{r_u}+\frac{\sum_{v\in N}s(u,v)(r_v^{(i)}-\overline {r_v})}{\sum_{v\in N} |s(u,v)|}
  $$

• 生成推荐列表：按照预测的评分进行降序排序
  基于物品（物以类聚）

• 特点：更个性化，着重于维护用户的历史兴趣，反映了用户兴趣的历史传承。

• 思路：

  1. 计算物品间的相似度。
  2. 根据物品的相似度和用户的历史行为生成推荐列表。

• 物品相似度计算：
  用$N(i)$表示喜欢物品$i$的人数；
  两个物品相似度越高，说明两个物品被很多人共同喜欢，但是要惩罚热门物品以挖掘长尾信息；
  $$
  w_{ij}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}}
  $$

• 预测分数：
  用$N_u$表示用户$u$已评分过的物品集合,以此预测那些未评分的物品的分数
  $$
  r_{ui}=\frac{\sum_{j\in N_u} w_{ij}r_{uj}}{\sum_{j\in N_u} w_{ij}}
  $$

• 生成推荐列表：按照预测的评分降序排序

基于模型的方法/隐语义模型（不考）

对于海量的物品，让用户子集给音乐分类并给出子集的偏好不现实，我们需要对用户行为数据分析获得评分矩阵$R$;

在实际应用中，评分矩阵可能相当稀疏，传统的矩阵分解代价太大;

我们需要从评分矩阵中抽取一组潜在的（隐藏的）因子，并通过这些因子向量描述用户和物品；

SVD将评价矩阵分解为3个低秩的矩阵，这3个矩阵的乘积能对原始矩阵进行某种程度的复原，从而可以评估出缺失值。

假设有$n$个用户，$m$个物品，设定$k$个潜在因子

• 用户-潜在因子矩阵$P_{n\times k}$:表示不同用户对于不同因子的偏好程度
• 物品-潜在因子矩阵$Q_{m\times k}$:每种物品含有各种因子的成分

则用户$u$对物品$i$的评分为
$$
p_u\cdot q_i^T = \sum_{j = 1}^k p_{uj}q_{ji}
$$
这样作近似
$$
R \leftarrow \hat{R} = P\cdot Q^T
$$

随机初始化$P,Q$,划分训练集$S$,测试集$T$

误差函数$e(u,i)$,损失函数$l(p,q)$，正则项$r(p,q)$, 目标函数为$C(p,q)$;
$$
e(u,i)=R_{ui}-p_u\cdot q_i^T\
C(p,q)=l(p,q) + \lambda\cdot r(p,q)\
l(p,q)=\sum_{(u,i)\in S}e^2(u,i)\
r(p,q)=\sum_{(u,i)\in S}||p_u||^2+||q_i||^2
$$
引入正则化项的目的是防止过拟合；

引入损失函数的目的用户$u$对物品$i$的真实喜爱程度与推算喜爱程度的均方根误差

测试集的评估也是MSE指标；

在深度学习中一般采用随机梯度下降(SGD)学习
$$
\frac{\part C}{\part p_u}=-2e(u,i)q_i\
\frac{\part C}{\part q_i}=-2e(u,i)p_u\
p_u\leftarrow p_u+\alpha \frac{\part C}{\part p_u}\
q_i\leftarrow q_i+\alpha \frac{\part C}{\part q_i}\
$$
估计出得分矩阵后，将用户已经使用的物品剔除，选择分数最高的物品推荐给用户；

缺点：

• 难以做到实时推荐，隐语义模型的训练需要在用户行为记录上反复迭代才能获得比较好的性能
• 模型的每次训练都很耗时，一般在实际应用中只能每天训练一次，并且计算出所有用户的推荐结果。

冷启动问题

使用协同过滤推荐算法时，新用户或新物品刚加入系统时、系统刚上线时，会因为行为数据的匮乏导致冷启动问题。

用户冷启动

• 利用用户注册信息：尽管是粗粒度的非个性化推荐，但是知道一些基本信息已经可以大大提高精度了；
  • 人口统计学信息：年龄，性别，职业，民族，居住地
  • 用户兴趣的描述：许多网站会在用户注册时让用户勾选部分感兴趣的标签
  • 从其他网站导入的用户站外行为数据
• 选择合适的物品启动用户兴趣：
  • 热门：要让用户对一个物品进行反馈的前提是用户知道这个物品是什么东西。
  • 区分度强：启动用户兴趣的物品不能是老少皆宜的，这样的物品对用户的兴趣没有区分性。
  • 多样性好：用户兴趣的可能性很多，我们需要提供具有很高覆盖率的启动物品集合，这些物品能覆盖大部分主流的用户兴趣。

物品冷启动

网站中时时刻刻都有新加入的物品，而且每个物品必须能够在第一时间展现给用户，否则经过一段时间后，物品的价值就大大降低了。

• 利用物品内容信息的表示
  • 物品的内容可以通过向量空间模型表示
  • 不过在绝大多数应用中，向量空间模型对于文本的分类、聚类、相似度计算已经可以给出令人满意的结果。

系统冷启动

系统冷启动的解决办法：专家标注

很多系统在建立的时候，既没有用户的行为数据，也没有充足的物品内容信息来计算物品相似度。这种情况下，很多系统都利用专家进行标注。

个性化推荐的挑战

数据稀疏

现在待处理的推荐系统规模越来越大，用户和商品数目动辄上亿，两个用户之间选择的重叠非常少，淘宝网的数据稀疏度在百万分之一以下。

数据非常稀疏导致绝大部分基于关联分析的算法效果都不好。这个问题本质上是无法完全克服的。

多样性与精确性的两难困境

如果要给用户推荐他喜欢的商品，最“保险”的方式就是给他特别流行的商品，因为这些商品有更大的可能性被喜欢。

• 盲目崇拜精确性指标可能会导致用户的视野变得越来越狭窄，难以激发用户新的购物需求。
• 推荐多样的商品与推荐的精确性之间存在矛盾，因为前者风险很大。

一种可行之策是直接对推荐列表进行处理，从而提升其多样性。

一些心怀不轨的用户通过提供一些虚假恶意的行为，故意增加或者压制某些商品被推荐的可能性，需要推荐系统提升鲁棒性；

譬如通过分析对比真实用户和疑似恶意用户之间打分行为模式的差异，提前对恶意行为进行判断，从而阻止其进入系统或赋予疑似恶意用户比较低的影响力。

第二章-搜索引擎

[TOC]

技术架构

网络爬虫：搜索引擎的信息源来自于互联网网页，通过网络爬虫将整个互联网获取到本地。
网页去重：互联网页面中有相当大比例的内容是完全相同或者近似重复的，网页去重模块会对此做出检测，并去除重复内容。
倒排索引：网页内容通过倒排索引这种高效查询数据结构来保存，网页之间的链接关系也会保存。
链接分析：链接关系在网页相关性排序阶段是可利用的，通过链接分析可以判断页面的相对重要性，对于为用户提供准确的搜索结果帮助很大。

云存储与云计算平台：网页数量非常多，搜索引擎不仅需要保存网页原始信息，还需要保存一些中间结果，单台或少量机器是不现实的。优秀的云存储和云计算平台已经称为大型商业搜索引擎的核心竞争力。
查询分析：当搜索引擎接收到用户的查询词后，首先需要对查询词进行分析，推导用户的真正搜索意图。
Cache系统：搜索引擎的缓存系统存储了不同的查询意图对应的搜索结果，如果能够在缓存系统中找到满足用户需求的信息，则可以直接将搜索结果返回给用户。

网页排序：根据用户的查询实时实时计算哪些网页满足用户信息需求，并排序输出作为搜索结果。网页排序最重要的两个参考因素：内容相似性因素、网页重要性因素。
反作弊：作弊将网页的搜索排名提高到与其网页质量不相称的位置，这会严重影响用户的搜索体验。自动发现作弊网页并对其处罚，是搜索引擎非常重要的一部分。

网络爬虫

网络爬虫是通过网页的链接地址来寻找网页，从网站某一个页面开始，读取网页的内容，找到在网页中的其他链接地址，然后通过这些链接地址寻找下一个网页，如此循环下去，直到把这个网站所有网页抓取完为止。

• 作用：为搜索引擎抓取大量数据；
• 对象：整个互联网上的网页；

工作原理

基本过程：

• 为爬虫输送表示起始位置的URL列表；
• 从种子列表出发，不断爬行发现新的URL
• 根据某种抓取策略爬行发现新的URL，如此重复

类型：

• 批量性爬虫：有明确的抓取范围和目标，当爬虫达到这个抓取目标之后，即停止抓取过程。
• 增量型爬虫：会保持持续不断的抓取，对于抓取到的网页，定期更新
• 垂直型爬虫：关注特定主题内容或者特定行业的网页

抓取策略

深度优先

依据深度优先的原则，先下载当前网页所链接的URL，追加到待抓取URL队列末尾。

宽度优先

将新下载的网页包含的链接直接追加到待抓取URL队列末尾。

Partial PageRank

• 对于已经下载的网页，加上待抓取URL队列中的URL一起，形成网页集合
• 在此集合内进行PageRank计算，将待抓取URL队列里的网页按照PageRank得分降序排列
• 形成的序列就是爬虫接下来应该依次抓取的URL列表。
• 一个性能折衷方案是每新下载$K$个网页时，将所有网页重新计算非完全PageRank，对产生的新网页赋临时Pagerank值，若值比较大则优先下载；

OPIC策略(Online Page Importance Computation)

每个互联网页面都给予相同的现金，每当下载了某个页面P之后，P将自己拥有的现金平均分配给P所包含的链接页面，把自己的现金清空。

对于待抓取的URL队列中的网页，则根据手头拥有的现金金额进行排序，优先下载现金最充裕的网页。

• 不同于Pagerank的迭代计算，OPIC是在线策略，适合实时计算，
• PageRank需要考虑无连接关系的网页远程跳转的过程，OPIC没有这一计算因子

大站优先策略(Lager Sites First)

以网站为单位来衡量网页重要性，对于待抓取的URL队列中的网页，如果哪个网站等待下载的页面最多，则优先下载这些链接

网页更新策略

互联网的内容具有动态性，网页更新策略的任务就是决定何时重新抓取已经下载过的网页，使得本地下载的网页和互联网的原始网页内容保持一致；

历史参考策略

假设：过去频繁更新的网页，那么将来也会频繁更新。该策略通过参考其历史更新情况来预估某个网页何时进行更新。

利用泊松过程对网站的变化建模，通过历史的变动情况，利用模型进行预测网页内容何时发生变化；

用户体验策略

更新网页取决于网页的内容变化带来的搜索质量变化；

影响越大的网页，则越快更新；

用户体验策略保存网页的多个历史版本，并根据过去每次内容变化对搜索资料的影响，得出一个平均值，以此作为判断爬虫更新该网页时机的参考依据，影响越大的网页则优先调度进行更新。

聚类抽样策略

具有相似属性的网页，其更新周期也是类似的，只需计算某个类别的更新周期；

对同一类别的网页进行采样，以被采样的网页更新周期作为其他网页的更新周期；

无需保留网页的历史信息。对于新网页也只需要找到其聚类就能进行更新；

与网页更新周期相关的属性有两大类：

• 静态：页面内容，链接深度，PageRank；
• 动态：图片数量的变化情况，入链出链的变化情况；

分布式爬虫

分布式技术将抓取任务分布到不同的节点以提高抓取的性能和可拓展性；

层级划分：分布式数据中心，分布式抓取服务器。分布式爬虫程序；

主从式分布爬虫

不同服务器承担不同的角色分工。

• URL服务器维护待抓取URL队列，获得待抓取网页的URL，分配给不同的抓取服务器，分配使得各抓取服务器负载均衡。
• 抓取服务器之间没有通信联系，每个抓取服务器只和URL服务器进行消息传递。

URL服务器承担很多管理任务，同时，待抓取队列数量巨大，因此，URL服务器容易成为整个系统的瓶颈。

对等式分布爬虫

在对等式分布爬虫体系中，服务器之间不存在分工差异，每台服务器承担相同的功能，各自负担一部分URL的抓取工作。
该架构中没有URL服务器，则需要服务器自己判断某个URL是否需要自己抓取，或者将读取到的URL传递给其他服务器。

许多对等式分布爬虫通过哈希取模的方法进行任务的分工；

暗网抓取

暗网：目前搜索引擎按常规方式很难抓取到的互联网页面

典型的暗网是垂直领域的网站，通常是网站提供组合查询界面，用户输入查询才能获取数据的页面；

难点：模拟人的行为，填写内容并提交表单，获取数据；

技术：组合查询问题，文本框填写问题；

组合查询问题

查询模板：如果在向搜索引擎提交查询的时候，部分属性被赋予值，其他属性不赋值，则这几个赋值的属性称为查询模板。

对于固定的查询模板，如果给模板内的每个属性都赋值，形成不同的查询组合，提交给搜索引擎，获得的返回结果，如果内容相差甚大，则这个查询模板是富含信息的查询模板。

对于一个固定的垂直搜索来说，其查询模板组合起来有很多，抓取的任务是找到富含信息的查询模板。

ISIT算法：减少提交的查询模板数量

• 先从1维开始，判断是否是富含信息模板，如果是的话，将该1维模板拓展到2维，再次依次考察对应的二维模板；
• 如此类推，逐渐增加维数，直到再也找不到富含信息模板为止。

文本框填写问题

对于输入中的文本框，需要爬虫自动生成查询。

• 可以通过人工观察对网站进行定位，提供一个初始种子查询关键词表，以此作为爬虫工作的基础条件。
• 通过人工启发结合递归迭代的方式，尽可能覆盖数据库里的记录。

网络协议

• URL规范：统一资源定位符,<协议>://<主机>:<端口>/<路径>;
• HTTP协议:超文本传输协议,定义了浏览器怎样向万维网服务器请求万维网文档，以及服务器怎样把文档传送给浏览器。
• Robots协议:是Web站点和搜索引擎爬虫交互的一种方式，robots.txt是存放在站点根目录下的一个纯文本文件。该文件可以指定搜索引擎爬虫只抓取指定的内容，或者禁止搜索引擎爬虫抓取网站的部分或全部内容。

索引技术

基础

搜索引擎索引是实现单词-文档矩阵的具体的数据结构；

单词词典

单词词典：用来维护文档集合中出现过的所有单词相关信息，记载某个单词对应的倒排列表在倒排文件中的位置信息；

哈希+链表

主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。

冲突链表：两个不同单词获得相同的哈希值，这在哈希方法里称为一次冲突，可将相同哈希值的单词存储在链表里，以供后续查找。

建立词典：

1. 对于某个文档出现的单词T，利用Hash函数获取其哈希值；
2. 根据哈希值对应的哈希表项读取并保存其中的指针，找到对应的冲突链表；
3. 若冲突链表中已经存在单词T，则说明该单词之前解析的文档中已经出现过；若未发现该单词，则将其加入冲突链表中。

响应用户请求：

1. 先计算请求的哈希值
2. 定位对应的哈希槽中，获取冲突链表
3. 将查询和链表中的每一个单词进行比较；

树形词典结构

利用B树可以进行高效的查找，前提是字典项具有顺序；

倒排列表

一个倒排索引项描述一个单词和文档相关的信息,形成列表结构，也就是倒排列表；

• 每一个文档维护一个文档编号DocID
• 单词在在这个文档出现的次数TF
• 单词在文档出现的位置…

在实际实现中，并不存储实际的文档编号，二十存储文档编号差值(D-Gap)

• 相邻两个倒排索引项文档编号的插值
• 文档编号一般是大数值，这样的作法可以增加数据的压缩率；
• 文档通常递增，因此通常为大于0的整数；

倒排文档

倒排文档的组成：

• 关键字（作者，主题词，分类号）
• 目长：含有关键字记录的条数
• 记录号集合：所有和该关键字有关的记录号；

倒排文档建立在顺排文档的基础上，它是从主文档中提取可检索字段内容，也有采取自动从标题、文摘或全文中提取关键词，利用所得到的这些属性词来建立倒排文档。

索引建立

两遍遍历文档法

在内存里完成索引的创建过程的，需要对文档进行两遍扫描。

1. 第一次遍历：获得统计信息，根据统计信息分配内存，建立好单词的倒排列表在内存的位置；
2. 第二遍文档遍历：建立每个单词的倒排列表信息；

一个空间上的优化是：始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果，当分配的空间消耗完时，把中间结果写进磁盘，清空内存里中间结果所占空间，以用做下一轮存放索引中间结果的存储区。

排序法

排序法是指对中间结果在内存中排序；

基本步骤：

1. 读入一个文档后，给文档进行编号，赋予唯一的文档ID，并对文档内容解析；
2. 对于文档中出现的单词，通过查词典将单词转换为对应的单词ID，如果词典中没有这个单词，说明是第一次检测到，则赋予单词唯一的单词ID并插入词典中。
3. 对该文档内每个单词建立一个（单词ID，文档ID，单词频率）三元组，这个三元组就是单词对应文档的倒排列表项，将这个三元组追加进入中间结果存储区末尾。
4. 对文档内的所有单词都经过如此处理，形成三元组序列的形式，处理完成以后，开始依次序处理下一文档，如此循环。
5. 当分配的内存空间被占满时，对三元组中间结果进行排序。排序的原则：
   • 主键是单词ID，即首先要按照单词ID由小到大排序；
   • 次键是文档ID，即在相同单词ID的情况下，按照文档ID由小到大排序。
6. 然后将排好序的三元组写入临时文件中，空出内存来进行后续文档的处理。

注意，在建立索引的过程中，词典一直存储在内存中，每次清空内存只是将中间结果写入磁盘；

最终的文档处理完毕后，需要对中间结果进行合并，由于每个中间结果都是有序的

1. 在合并中间结果的过程中，系统为每个中间结果文件在内存中开辟一个数据缓冲区，用来存放文件的部分数据。
2. 将不同缓冲区中包含的同一个单词ID的三元组进行合并。
3. 如果某个单词ID的所有三元组全部合并完成，说明这个单词的倒排列表已经构建完成，则将其写入最终索引中，同时将各个缓冲区中对应这个单词ID的三元组内容清空，这样缓冲区就可以继续从中间结果文件中读入后续的三元组来进行下一个单词的三元组合并。

归并法

分两个阶段进行

• 在内存中维护中间结果，当内存占满后，将内存数据写入磁盘临时文件
• 对临时文件进行归并，形成最终索引，

需要在内存建立索引结构，描述目前处理的文档子集；

在将中间结果写入磁盘临时文件时，将整个内存的倒排索引写入临时文件。依次将单词和对应的倒排列表写入磁盘文件，随后彻底清空所占内存。

动态索引

组成：

• 倒排索引：在磁盘中已经存在的索引；
• 临时索引：在内存中实时建立的倒排索引
• 已删除文档列表：用来存储已被删除的文档的相应的文档ID，形成一个文档ID列表。

动态索引的处理办法：

1. 当系统发现有新文档进入时，立即将其加入到临时索引结构中。
2. 当文档被删除时，则将其加入删除文档队列。
3. 当文档被更改时，则将原始文档放入已删除队列，解析更改后的文档内容，并将其加入临时索引中。

对于查询请求，如何形成准确的搜索结果？

• 同时从倒排索引和临时索引中读取对应的倒排列表；
• 找到的文档集合进行合并；
• 在文档删除列表过滤；

索引更新

完全重建策略

当新增文档达到一定数量，将新增文档和原先的老文档进行合并，然后利用建立静态索引的方式，对所有文档重新建立索引。

新索引建立完成后，老的索引被遗弃释放，之后对用户查询的相应完全由新的索引来负责。

由于重建索引需要较长的时间，在进行索引重建过程中，内存中仍然需要维护老的索引来应对用户的查询请求。只有当新索引建立完成后，才能释放旧的索引，将用户查询请求切换到新索引上。

再合并策略Re-Merge

当新增文档进入搜索系统时，搜索系统在内存维护临时倒排索引来记录信息，当新增文档达到一定数量，或者指定大小的内存被消耗完，则把临时索引和老文档的倒排索引进行合并，以生成新的索引。

步骤如下：

1. 当新增文档进入系统，解析文档，之后更新内存中的临时索引，文档中出现的每个单词，在其倒排列表末尾追加倒排列表项，这个临时索引可称为增量索引。
2. 增量索引将指定的内存消耗光后，此时需要进行一次索引合并，即将增量索引和旧文档的倒排列表索引进行合并。
3. 在合并过程中，需要一次遍历增量索引和老索引单词词典中包含的单词及其对应的倒排列表，可以用两个指针分别指向两套索引中的目前需要合并的单词：
   • 如果这个单词在词典序中小于老索引的单词指针指向的单词，说明这个单词在旧索引中未出现过，则直接将这个单词对应的倒排列表写入新索引的倒排文件中，同时增量索引单词指针后移指向下一个单词。
   • 如果两个单词指针指向的单词相同，说明这个单词同时在增量索引和旧索引中同时出现，则将老索引中这个单词的倒排列表写入新索引的倒排列表，然后把增量索引中这个单词的倒排列表追加到其后，这样就完成了这个单词所有倒排列表的合并。
   • 如果某个单词仅在老索引中出现过，即发现老索引的单词指针指向的单词，其词典序小于增量索引单词指针指向的单词，则直接将老索引中对应的倒排列表写入新索引倒排文件中。新索引的单词指针后移指向下一个单词，继续合并。

由于在磁盘的老索引(倒排文档对应的倒排列表，保存为文件)是顺序的，增量索引在遍历词典的时候也按照字典顺序由低到高排列，可以只对倒排文件进行一遍扫描，顺序读取，减少了IO开销(文件操作中比较耗时的磁盘寻道时间)，提高合并效率。

这个再合并策略类似于归并排序；

• 优点：老的倒排索引是顺序结构，遍历时可以顺序读取文件内容，减少磁盘寻道时间，高效更新。
• 缺点：需要生成新的倒排索引文件，但是老索引很多单词的倒排列表其实没发生什么变化，也需要从老索引中读取出来并写入新索引文件中，这一操作非常耗时，带来大量的IO开销；

原地更新策略In-Place

在索引合并时，并不生成新的索引文件，而是直接在老的索引文件里进行追加操作，将增量索引里单词的倒排列表项追加到老索引相应位置的末尾。即只更新增量索引里出现的单词相关信息，其他单词相关信息不做变动。

策略步骤如下：

1. 老索引中每个单词的倒排列表末尾都预留出空余磁盘空间，以作为信息追加的存储区域。
2. 在对新增索引进行合并时，按照词典序，依次遍历新增索引中包含的单词，并对新增倒排列表的大小和老索引中相应预留空间大小进行比较：
   • 如果预留空间足够大，则将新增列表追加到老索引后面即可；
   • 如果预留空间不足以容纳新增倒排列表，则在磁盘中找到一块完整的连续存储区，这个存储区足以容纳这个单词的倒排列表，然后，将老索引中的倒排列表读出并写入新的磁盘位置，并将增量索引对应的倒排列表追加到其后。

缺点：

对于倒排文件中的相邻索引单词，其倒排列表顺序一般是按照相邻单词的词典序存储的，但是由于原地更新策略对单词的倒排列表做数据迁移，某些单词及其对应倒排列表会从老索引中移出

• 这样就破坏了这种单词连续性，导致在进行索引合并时不能进行顺序读取，必须维护一个单词到其倒排文件相应位置的映射表
• 一方面降低了磁盘读取速度，另外一方面需要大量的内存来存储这种映射信息。

混合策略

混合策略的出发点是能够结合不同索引更新策略的长处，将不同的索引更新策略混合，以形成更高效的方法。
常用的混合策略是根据单词的倒排列表长度进行区分：

• 对于经常在不同的文档中出现的单词，其对应的倒排列表较长，称为长倒排列表单词，采取原地更新策略；
• 对于少见的一些单词，其倒排列表较短，称为短倒排列表单词，则采取再合并策略。

查询处理

一次一文档(Doc at a time)

以倒排列表中包含的文档为单位，每次将其中某个文档与查询的最终相似性得分计算完毕，然后开始计算另外一个文档的最终得分，直到所有的文档的得分都计算完毕为止。

步骤

1. 找到和查询相关的所有文档；
2. 按照文档顺序，计算每个文档和用户查询的相似性得分
   • 对每个查询单词，若文档包含单词，计算文档和单词的相似性得分
   • 将查询出现的单词对应的得分，累加得到最终相似性得分；
3. 根据文档得分进行大小排序，输出得分Top K作为搜索结果输出，即可完成一次用户查询的响应。

一次一单词(Term at a Time)

将某个单词对应的倒排列表中的每个文档ID，都计算一个部分相似性得分，在计算完毕某个单词倒排列表中包含的所有文档之后，接着计算下一个单词的倒排列表中包含的文档。若发现某个文档ID已经有了得分，则在原先得分上进行累加。

步骤

1. 找到和查询相关的所有文档；
2. 按照查询单词顺序， 计算每个文档和用户查询的相似性得分
   • 对每个文档，若文档包含单词，计算文档和单词的相似性得分
   • 将文档的所有部分得分累加得到最终相似性得分；
3. 根据文档得分进行大小排序，输出得分Top K作为搜索结果输出，即可完成一次用户查询的响应。

跳跃指针(Skip Pointer)

对于某些搜索引擎，认为文档必须包含所有的查询词，才认为文档是相关的；

文档ID是以文档编号差值（D-Gap）形式存储，且这个差值是以压缩后的方式编码的；

note: 若倒排列表直接包含文档ID，而不是差分，只需要通过归并排序能获得倒排列表集合的交集；

跳跃指针基本思想：将一个倒排列表数据化整为零，切分为若干个固定大小的数据块，一个数据块为一组，对于每个数据块，增加元信息来记录关于这个块的一些信息。

• 设置数据块大小，将一个倒排列表分成若干块
• 每个块前加入管理信息<idx, Pos j>表示第j个块的首个文档ID为idx

在一个具有跳跃指针的倒排列表中查找某个文档(已知文档ID)：

1. 先根据跳跃指针，确定文档在哪一个块中；
2. 连续顺序解压，恢复该块中所有的文档ID，进行比较；

数据块的大小一般设置为$\sqrt L$,其中倒排列表长度为$L$,效果比较好

• 数据块越小，则使用跳跃指针向后进行跳跃的可能性越大，其缺点是增加了比较操作的次数；
• 数据块越大，则可以有效减少指针比较次数，其缺点是使用跳跃指针向后跳跃的可能性越小。

获得查询词的对应的倒排列表交集：反复在两个倒排列表中查找某个文档是否存在，将同时存在两个倒排列表中的文档ID作为计算结果。

跳跃指针的优点

• 相对不包含跳跃指针的索引来说，只需对其中一个数据块进行解压缩和文档编号查找即可获得结果，不用将所有索引数据都进行解压缩和比较操作。这明显加快了查找速度，并节省内存空间。

索引压缩

索引压缩则可以利用数据压缩算法，有效减少数据量，并且可以减少磁盘读/写数据量，加快用户查询的响应速度。

倒排索引包含两个部分：单词词典、单词对应的倒排列表。

词典压缩

词典组织方式，一般存储单词+DF+指向倒排列表的指针

• 哈希加链表
• B树形词典结构

结构优化

• 将单词连续存储在某个内存区域，原来存储单词内容的部分由指向这个存储区对应单词起始位置的指针代替；
• 单词结尾可以采用下一个单词的指针所指向位置判断。

进一步的优化技术：

• 将连续词典分块，动态调整分块大小，以获取最优压缩效果；
• 原来每个词典项需保留一个指向连续词典区的指针，分块之后，每个块中的词典项共享同一个指针。
• 每个分块内包含多个单词，则为每个单词增加单词长度信息，以在提取单词时对块内不同单词予以区分。

倒排列表压缩

采用二进制编码：由二进制数字0和1表示实际数据，不同的比特宽度代表了不同的数字表示范围。

倒排列表压缩算法举例：

• Elias Gamma算法:利用分解函数将待压缩的数字分解为两个因子，然后分别用一元编码和二进制编码来表达这两个因子。

  将分解数字表示为$x=2^e+d$,因子$e+1$用一元编码表示，因子$d$采用长度为$e$的二进制编码表示

• Elias Delta算法：利用了两次Elias Gamma算法，将待压缩的数字分解为3个因子，之后利用一元编码和二进制编码来进行数值压缩。

  将分解数字表示为$x=2^e+d$,因子$e+1$用Elias Gamma算法继续分解为个因子，因子$d$采用长度为$e$的二进制编码表示

• PForDelta算法：PForDelta算法是目前解压速度最快的一种倒排文件压缩算法，其主要思想是尽可能一次性压缩和解压多个数值。设定连续压缩$K$个数值，取一定比例作为异常大数；

  压缩的数据分为3部分：异常数据存储区、常规数据存储区、异常链表头。

  压缩过程

  1. 确定小数的最大者，进而确定比例宽度；
  2. 对原始数据循环遍历，处理异常大数。遇到大数则逆序放置到静态数据尾端，并将异常大数转换为链表结构。
  3. 将小数一次性快速压缩，存入常规数据存储区，压缩按照先前得到的比例宽度

  解压过程

  一次性将常规存储区的数据进行解压，根据异常链表头、依次顺序读出异常大数的位置，结合尾部存储的异常大数恢复原始数值序列。

  

文本处理

一般来说，名词是最能表达文档内容的。因此，对文档进行预处理是必要的。

文本处理过程：

• 文本的词法分析：主要是对文本中的数字、连接符、标点符号和字符的大小写进行处理；
• 无用词汇的删除：主要是过滤掉那些对于信息获取过程来说区分能力低的词汇；
• 词干提取：主要是去除词缀（前缀和后缀），这样可以允许所获取的文档包含一些查询词条的变换形式；
• 索引词条/词干的选择：在选择时，通常按照单词的习惯用法，实际上名词往往要比形容词、副词和动词包含更多的语义；
• 构造词条的分类结构：例如词典或者结构抽取，利用它可以进行查询的扩展。

词法分析

将字符串（文档中的文本）转换成词条的过程，这些词条可能被用来作为索引词条。因此词法分析的主要目的是识别文本中的词条。

• 英文：在对英文进行分词的过程中，除了空格分隔符，还需要处理：数字、连字符、标点符号和字母的大小写。
• 数字：数字一般不适合用作索引词条，因为对于数字来说，如果不参考上下文，它就没有明确的含义。
• 连字符：对于连字符的处理，目前常用的是方法是，首先采用一定的规则选出那些对词义有影响的连字符号，然后将其他的连字符都过滤掉。
• 标点符号：在词法分析过程中，标点符号将被全部去除。但是，对于那些成为单词中一部分的标点符号来说，一般不可以去除。
  字母的大小写：可以将文本中的所有词条都转换成大写或者小写。但是在某些特殊情况下，也需要对大小写进行区分。

中文分词技术

对于中文来说，词与词之间没有分隔符，且存在许多歧义现象；

• 单字切分：是指按照中文一个字、一个字地进行分词。按此方式切分出来的词进入索引，称为字索引。
• 二分法：是指每两个字进行一次切分。
• 词库分词：是指用一个已经建立好的词的集合去匹配目标，当遇上集合中已经存在的词时，就将之切分出来。

系统评价：

• 用户相应度：主要指用户对这项技术的满意度。

• 兼容性：要求能在不同的系统中都可以毫无障碍地使用，而且能给各行各业都带来方便。

• 准确率：是分词系统性能的核心指标，系统的准确率越高越好，应尽可能接近100%。
  $$
  p=\frac{\rm 切分结果中正确分词数}{\rm 切分结果中所有分词数}\times 100%
  $$

• 运行效率：在分词系统中分词的工作消耗的时间应尽量少，使用户没有等待的感觉。

• 适用性：好的分词系统具有良好的适用性，可以方便地集成在各种各样的汉语信息处理系统中。

• 通用性：中文分词系统必须具有很好的通用性。应能适应不同地区的不同用字、用词，不同的语言风格，不同的专用名构成方式等；支持不同的应用目标，包括语音合成、校对、翻译等；支持不同领域的应用，包括社会科学、新闻、办公等。

中文分词算法：基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法。

中文分词难题：

• 歧义识别：歧义是指同样的一句话，可能有两种或者更多的切分方法。
• 新词识别：在字典中都没有收录过，但又确实能称为词的那些词。

基于字符串匹配的分词

机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。

最大匹配法（Forward Maximum Matching method, FMM）:FMM算法是正向最大匹配算法，它是基于字符串匹配的一种分词方法。

算法思想：选取包含6~8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从左向右。

**逆向最大匹配法（Backward Maximum Matching method，BMM）：基于字符串匹配的一种分词方法，基本算法和正向最大匹配法相似，只是匹配的方向是从右到左，该算法比FMM的精确度高一些。

双向匹配法（Bi-direction Matching method，BM）：将FMM法和BMM法结合起来的算法称为双向匹配法，这种算法通过比较两者的切分结果，来决定正确的切分，而且可以识别出分词中的交叉歧义。

最少匹配算法（Fewest Words Matching，FWM）：FWM实现的分词结果中含词数最少，它和在有向图中搜索最短路径很相似。控制首先要对所选的语料进行分段，然后逐段计算最短路径，得到若干个分词结果，最后进行统计排歧，确定最理想的分词结果。

网格分词算法：基于统计性的一种分词算法，它的算法思想是：首先构造候选词网格，利用词典匹配，列举输入句子所有可能的切分词语，并且以词网格形式保存；然后计算词网格中的每一条路径的权值，权值通过计算图中每一结点得一元统计概率和结点之间的二元统计概率的相关信息；最后根据搜索算法在图中找到一条权值最大的路径，作为最后的分词结果。

基于理解的分词方法

基于理解的分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。
基本思想：在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。
通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。

基于统计的分词技术

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。
基本思想：定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典。

无用词汇删除

在信息库的文档中太频繁出现的单词将不会成为具有良好区分能力的词汇。
实际上，如果一个单词出现在信息库中80％的文档中，该单词对于信息获取过程来说没用，这些词统称为无用词汇。在选择索引词条的时候，这些词条常常被过滤掉。
一般来说，冠词、介词、连词都可以算作无用词汇。
删除无用词汇对于信息获取来说具有重要意义，它可以大大缩小索引空间的大小，而且空间的缩小一般可以在40％左右。

信息获取系统通常会设置一个无用词汇列表。删除无用词汇将影响系统的查全率，因此，一些搜索引擎采用了全文索引，对无用词汇也会建立索引。

英文词干提取

用户输入词汇是信息库中某个相关文档中词汇的一种变形，词汇的变形可以是该词的复数、动名词或过去分词形式等。在这种情况下，则可以将文档中的词汇用它们的词干来代替。
词干：是单词的一部分，是去除词的前缀和后缀后剩下的部分。

波特算法基本思想：对文本中单词的后缀应用一系列的规则，是目前公认最好的算法。该算法使用了560个后缀，上千条规则。

索引词选择

一些名词常常是两个或者三个同时出现，可以将这些词汇作为一个整体建立索引。在实际操作中，可以先设置一个阈值，计算文本中词汇之间的距离，如果该距离小于阈值，则将这些词汇放在一起构成名词词组。

搜索排序

搜索结果排序是搜索引擎最核心的构成部分，很大程度上决定了搜索引擎的质量好坏与用户接受与否。

相关计算框架

搜索引擎的核心是判断哪些文档和用户需求相关，并按照相关程度排序输出。相关度计算是将用户查询和文档内容进行匹配的过程，而检索模型是用来计算内容相关度的理论基础。

机器学习排序

利用机器学习技术对搜索结果进行排序，是非常热门的一个研究领域。
基本思路：提供训练数据，机器自动学习获得排序公式（传统检索模型由人工拟合排序公式）。

• 人工标注训练数据：对于某个查询Q，人工标出哪些文档是和这个查询相关的，并标出相关程度，或者利用用户点击记录来模拟这种人工打分机制。
• 文档特征抽取：每个文档是由若干特征构成的，通过特征抽取算法抽取文档特征，常用特征有文档长度、网页PageRank值、网页入链数量等。
• 学习分类函数：通过多个训练实例，采用机器学习技术对系统进行训练，生成分类函数。
• 在实际搜索系统中采用机器学习模型：利用生成的分类函数对与查询相关的网页进行排序。

机器学习排序可分为三类方法：单文档方法（Pointwise Approach）、文档对方法（Pairwise Approach）、文档列表方法（Listwise Approach）。

检索质量评价

混淆矩阵如下：

查全率：衡量系统在实施某一作业时检出相关文献能力的一种测度指标，是对检索遗漏程度的度量。
$$
{\rm precision}=\frac {A}{A+B}
$$
查准率：衡量系统在实施某一检索作业时检索精度的一个测度指标，是对检索噪音程度的度量。
$$
{\rm recall}= \frac{A}{A+C}
$$

链接分析

搜索引擎在查找能够满足用户请求的网页时，主要考虑两方面的因素：一方面是用户发出的查询与网页内容的内容相似性得分，即网页和查询的相关性，另一方面是通过链接分析方法计算获得的得分，即网页的重要性。

PageRank算法

取万维网链接结构图$G$，$G$的规模为$N$;

对于$G$中的每一个节点，设$PR(n)$是其PageRank值，而向量$\overline {PR}$为G对应的PageRank结果向量,分量和为1,预先设定参数$\alpha$;

Simplified Version

初始化向量$PR=(\frac1N, \frac1N,\cdots,\frac1N)$;

每一步迭代，$PR$向量获得更新如下：
$$
PR^{(k)}(n)\leftarrow \alpha\frac1N + (1-\alpha)\sum_{i\to n}\frac{PR(i)}{Outdeg(i)}
$$
算法充分迭代，直到向量$PR$收敛；

Standard Version

初始化向量$PR=(\frac1N, \frac1N,\cdots,\frac1N),I=(\frac\alpha N, \frac\alpha N,\cdots,\frac\alpha N)$;

遍历每一个结点$n$:

• 若$Outdeg(n)>0$,则遍历$n$的出度顶点$i$,更新
  $$
  I(i)\leftarrow I(i)+(1-\alpha)\frac{PR(n)}{Outdeg(n)}
  $$

• 若$Outdeg(n)=0$,则对所有顶点$i$更新：
  $$
  I(i)\leftarrow I(i)+(1-\alpha)\frac{PR(n)}{N}
  $$

遍历完成后，更新向量$PR\leftarrow I$;算法充分迭代，直到向量$PR$收敛；

HITS算法

HITS是Hyperlink-Induced Topic Search（基于超链接推演的主题搜索算法）的简称，其核心思想是对网页两个方面的权威程度进行评价，一个是内容权威度（Authority Value），即网页本身内容的受欢迎程度，另一个是链接权威度（Hub Value），即网页链接到其他受欢迎资源的程度。

对用户输入的查询的主题而言，首先是通过文本搜索过程与此查询主题内容相关的网页集合，并适当扩展该网页集合，以包括尽可能多的结果候选网页，同时使结果集合网页间的链接结构关系更加完整；

随后则是通过一个“迭代-收敛”的过程计算网页集合中每个页面对应的链接权威度与内容权威度数值，算法最后输出的是分别按照链接权威度与内容权威度排序的结果列表，用户可以根据需求的不同，选择其中的结果页面进行浏览。

记$R$为网络信息检索结果集合，找到和$R$有关链接的网页形成结构图$G$

对于图$G$中每一个结点$n$，维护$H(n),A(n)$为其链接权威度和内容权威度；

初始化$H=A=(1,1,\cdots,1)$;

每一步迭代，进行I操作和O操作，对每一个结点$n$

• I操作：
  $$
  A(n)\leftarrow \sum_{i\to n}H(i)
  $$

• O操作：
  $$
  H(n)\leftarrow \sum_{n\to j}A(j)
  $$

• 规范化处理：每个分量除以某数，使得
  $$
  \sum_{n\in G}A^2(n)=\sum_{n\in G}H^2(n)=1
  $$

算法充分迭代直到收敛，或者到达迭代次数上限；

P的内容权威度与链向P网页的链接权威度相关（O操作）。链向P的网页的链接权威度越高，说明P的内容权威度越高。
链接权威度与内容权威度之间具有相互增强的关系。

缺点：

• 计算效率较低：HITS是与查询相关的算法，所以必须在接收到用户查询后实时进行计算，而其本身需要进行很多轮迭代计算才能获得最终结果，导致计算效率变低。
• 主题漂移问题：如果在扩展网页集合里包含部分与查询主题无关的页面，而且这些页面之间有较多的相互链接指向，那么使用HITS算法很可能会给予这些无关网页很高的排名，导致搜索结果发生主题漂移，这种现象称为紧密链接社区现象。
• 易被作弊者操纵结果：HITS算法从机制上很容易被作弊者操纵，比如作弊者可以建立一个网页，页面内容增加很多指向高质量网页或者著名网站的网址，这就是一个很好地Hub页面，之后再将这个网页链接指向作弊网页，于是可以提升作弊网页的内容权威度。
• 结构不稳定：如果在原有的扩展网页集合内，添加删除个别网页或者改变少数链接关系，则HITS算法的排名结果会有非常大的改变。

比较

网页去重

搜索引擎是在网络爬虫阶段进行近似重复检测（网页去重）的。

框架

• 特征提取：对于给定文档，首先需要进行特征抽取，从文档中抽取出一系列能够表征文档主体内容的特征集合。
• 文档指纹生成：在将文档转换为特征集合后，对信息进一步压缩，采用信息指纹相关算法，将特征集合压缩为新的数据集合。
• 相似性计算：通过相似性计算来判断哪些网页是近似重复页面。

Shingling算法

Shingling算法以Shingles作为文档的特征。

Shingles，即将文档中出现的连续单词作为一个整体，对这个单词片段进行哈希计算，形成一个数值，每个单词片段对应的哈希值称为一个Shingle。文档的特征集是由多个Shingle构成的。

以一个固定大小的移动窗口从文档第一个单词（单字）开始依次移动，每次向后移动一个单词（单字），直到文本末尾。

步骤：

1. 从文档中抽取出能代表文档内容的特征
2. 根据两个文档对应的特征集合的重叠程度来判断是否近似重复；

用Jaccard相似性计算文档特征集的重合程度：

对于特征集合$A,B$,Jaccard相似性计算为
$$
{\rm Jaccard}=\frac{|A\cap B|}{|A|+|B|}
$$
Shingling算法在运用过程中，计算效率不高，如果网页数量大，运行时间会过长。

原因在于把一个文档转换为以Shingles表示的特征集合形式后，这个文档对应的特征集合很大。

SuperShingle Trick

对于不同的网页，将其转换为固定大小的特征集合，这个特征集合的大小远小于原始Shingling算法转换后特征集合的大小，以此方法来提高运算效率。

一个改进的Shingleing算法步骤如下：

1. 将文档转换为由shingles构成的特征集合；
2. 通过引入m个不同的哈希函数，将文档映射为固定大小，形成哈希函数簇；
3. 对于某个特定的哈希函数F，对每个shingle都计算出一个对应的哈希数值，取最小的那个哈希值作为代表；
4. m个哈希函数便获得了m个哈希值，如此便将文档的特征集合转换为了固定大小m。

在SuperShingle Trick中，取$m=84$​,对84个数值进一步压缩，以14个连续数值作为一块，即分为6块，在采用另一个哈希函数对每一块的14个数值进行哈希计算，进一步将文档转换为6个哈希值；若任意两个文档有两个以上的哈希值是相同的，即可认为是近似重复文档；

SimHash算法

实践表明，SimHash是目前最优秀的去重算法之一,属于局部敏感哈希算法(Locality-Sensitive Hashing)的一种；

1. 文档指纹计算：将一篇文本文档转换为固定大小的二进制数值，以此作为文档的信息指纹；
2. 文档指纹计算：将一篇文本文档转换为固定大小的二进制数值，以此作为文档的信息指纹；

文档指纹计算是指：通过适当的抽取方法，从文档中抽取一批能表征文档的特征，获得文档的特征及其权值w，利用一个哈希函数将每个特征映射成固定长度的二进制表示，利用权值改写特征的二进制向量，将权重融入向量中，形成一个实数向量。对每个特征向量完成改写之后，累加所有实数向量，获得一个文档整体的实数向量。累加规则，即将对应位置的数值相加即可，最后将得到的实数向量重新妆化成二进制向量。

这里二进制向量和实数向量转换规则是

• 若二进制的某个比特位是数值1，则实数向量中对应位置改写为w；反之，若实数向量位对应大于0，则二进制向量的比特位为1；
  若二进制的某个比特位是数值0，则实数向量中对应位置改写为-w，即权值的负数；反之，若实数向量位对应小于等于0，则二进制向量的比特位为0；

在实践中一般文档转换为64比特的二进制数值，内容相似性通过海明距离的大小衡量；

对于64位二进制数来说，判断两个文档是否近似重复的标准是：海明距离是否小于等于3，若两个文档的二进制数值小于等于3位不同，则判定为近似重复文档。

对于动态出现新网页，找出其近似重复的内容，可采用以下分组算法，将索引网页根据文档指纹进行分组，新网页只在部分分组内进行匹配，以减少新文档和索引网页的比较次数。

1. 对64位长度的二进制数值进行分块，没16位为一块，则每个二进制数值被划分为4块，分别以A、B、C、D命名。
2. 对于海量的索引网页，依据分块进行聚类：对于A块来说，根据该块内16位二进制聚类，若16位二进制都相同，则将这些网页看作一个聚类，依据此规则，可将索引网页分为若干组数据。对B、C、D按照相同方法聚类。
3. 对于新抓取的网页，同样将64比特二进制数据分为4块：Q1、Q2、Q3、Q4。
4. 在索引网页的分组中，找到对应A块16位和Q1完全相同的分组，然后与分组内的网页一一匹配，查找哪些网页是近似重复的。对Q2、Q3、Q4作同样处理。

将新网页与分组内的索引网页一一匹配：若两者二进制数值的海明距离小于等于3，则判定为近似重复文档。

网页反作弊

作弊方法

内容作弊

内容作弊是指通过精心更改或者调控网页内容，使得网页在搜索引擎中获得与其网页不相称的高排名。

搜索引擎排名包含了内容相似性和链接重要性计算，内容作弊针对的是内容相似性计算部分。

内容作弊方式：关键词重复、无关查询词作弊、图片alt标签文本作弊、网页标题作弊、网页重要标签作弊、网页元信息作弊。

链接作弊

链接作弊是指网站拥有者通过操纵页面之间的链接关系，或者操纵页面之间的链接锚文字，以此来增加链接排序因子的得分，影响结果排名。

链接作弊方式：链接农场、Google轰炸、交换友情链接、购买链接、购买过期域名、“门页”作弊

页面隐藏作弊

页面隐藏作弊是指通过一些手段欺骗搜索引擎爬虫，使得搜索引擎抓取的页面内容和用户点击查看到的页面内容不同，从而影响搜索引擎的搜索结果。

页面隐藏作弊方式：IP地址隐形作弊、HTTP请求隐形作弊、网页重定向、页面内容隐藏。

Web2.0作弊

Web2.0作弊是指通过以用户为中心的一些应用产品来作弊。
Web2.0作弊方式：博客作弊、点评作弊、标签作弊、SNS作弊、微博作弊。

反作弊技术

信任传播模型

在海量的网页数据中，通过一定的技术手段或者人工半人工手段，从中筛选出部分完全值得信任的页面，也就是一定不会作弊的页面（可理解为白名单）；

算法以这些白名单内的页面作为出发点，赋予白名单内的页面节点较高的信任度分值，其他页面是否作弊，根据其和白名单内节点的链接关系来确定。

白名单内节点通过链接关系将信任度分值向外扩散传播，如果某个节点最后得到的信任度分值高于一定阈值，则认为没有问题，而低于这一阈值的网页则被认为是作弊网页。

不信任传播模型

从技术框架上来讲，不信任传播模型和信任传播模型是相似的，两者区别在于：初始的页面子集不是值得信任的页面节点，而是确认存在作弊行为的页面集合，即不值得信任的页面集合（可理解为黑名单）。

赋予黑名单内节点不信任分值，通过链接关系将这种不信任关系传播出去，如果最后页面节点的不信任分值大于设定的阈值，则会被认为是作弊网页。

异常发现模型

异常发现模型基本假设：作弊网页必然存在有异于正常网页的特征，这种特征有可能是内容方面的，也有可能是链接关系方面的。

该模型具有两种子模型：一种是直接从作弊网页包含的独特特征来构建算法；另一种是将不正常的网页视为作弊网页。

反内容作弊

针对内容作弊，通常采用一些启发规则或者内容统计分析地方式进行识别。
对于重复出现关键词这种作弊方式，可以判断文本内一定大小的窗口中是否连续出现同一关键词，如果是，则消除重复出现的内容。

对于标题关键词作弊，可以判断标题词在文本正文出现的比例和权重，如果达到一定条件，则判断为标题关键词作弊。

反链接作弊

通用链接反作弊方法，是指这种反作弊方法不需要针对某种具体的作弊方式来做特征分析，并根据分析结果构建有针对性的算法。

例如TrustRank算法属于信任传播模型中的反链接作弊技术：采取信任分值均分策略：即将网页获得的信任分值按照出链个数平均分配，如果一个网页有K个出链，则每个出链分配得到1/K的信任分值，并将这个分值传递给出链指向的页面。

BadRank属于不信任传播模型的反链接作弊技术：首先构建作弊网页集合，之后利用链接关系来将不信任分值传递到其他网页，和TrustRank计算类似；

SpamRank算法是一种符合异常发现模型的反作弊方法。计算思路：

• 计算网页的PageRank值；
• 计算出网页的支持页面；
• 判断支持页面的PageRank分布是否违反Power-Law统计分布，若违反则作为作弊页面处理。

反隐藏作弊

常见的隐藏作弊方式有页面隐藏、网页重定向。

识别页面隐藏：对网页进行两次抓取，第一次是正常的搜索引擎爬虫抓取，第二次以模拟人工访问页面的方式抓取，如果两次抓取到的内容差异较大，则认为是作弊页面。

识别网页重定向：收集一批作弊页面，据其进行扩展，检测到经常与这些作弊页面链接一起出现的链接，则扩充进可疑页面集合。依次访问这些页面，若某个页面被诸多可疑链接重定向指向，或者重定向到作弊网页的可疑链接，均被认为作弊网页。

绪论

[TOC]

什么是信息检索

• 给定用户需求返回满足该需求信息的一门学科。通常涉及信息的获取、存储、组织和访问。
• 从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。
• 通常需要定义并计算某种匹配“相似度”的学科。
• 应用：搜索系统，推荐系统

分类

1. 第一类是广义的，把“信息检索”当作“信息存储与检索”的简称，信息存储是指将有用信息按照一定的方式组织和存放起来，信息检索是指查找或提取所需信息。本课程介绍广义的信息检索。

   第二类是狭义的，是指按照一定的方式从现有的信息集合或数据库中，找出并提取所需要的信息。

2. 按对象性质划分：

   文献检索：对象是文献。
   数值检索：对象是以数字形式表示的具体数值。
   事实检索：对象是某一特定的客观事实。

3. 按计算机检索技术划分

   脱机检索：计算机检索的最早技术。
   联机检索：功能较强、数据库质量较好。
   光盘检索：分光盘单机系统和联机系统。
   网络检索：基于搜索引擎技术，是信息检索的主要途径。

原理

核心问题

如何计算查询式与文档的相似度？

逻辑结构

两大基本功能：存储，检索

按功能分解子系统：采选子系统、词语子系统、标引子系统、查询子系统、匹配子系统、交互子系统。

• 采选子系统：从外部的各种信息源向系统进行输入操作；
• 标引子系统：使用系统规定的规范化词语，对输入的信息中具有检索价值的特征进行表示和描述；
• 词语子系统：对采用规范化词语的系统在标引和查询时所使用的词语进行规范化的控制和处理；
• 匹配子系统：完成对用户询问与数据库的匹配过程，并与词语子系统共同实现对信息检索系统的存储与检索两大基本功能的协同和沟通。
• 查询子系统：使用系统规定的规范化词语描述用户的检索询问，包括对用户询问进行概念分析和概念转换两个过程，也包括按照系统的既定规则指定检索策略和构建检索式。
• 交互子系统：保证系统与用户之间能够进行良好的沟通。一方面，要全面、准确地反映用户的真实需求，形成明确的检索目标；另一方面，把与用户查询全部或部分匹配的检索结果及时地反馈给用户。

研究内容

• 信息检索理论研究：主要集中在四个方面：检索模型、标引理论、信息组织理论、相关性理论。
• 信息检索方法研究：检索方法是指查找信息时所采用的具体方法，例如，布尔检索法、截词检索法、加权检索法。
• 信息检索技术研究：检索技术是实现信息检索有效性的手段和保障。
• 信息检索语言研究：检索语言是信息检索系统不可缺少的工具，是用户与系统交流、互动、沟通的媒介。
• 信息检索系统研究：主要包括信息检索系统的结构、功能、类型、分析、开发、运行、维护、管理及评价。
  信息检索服务研究：通常包括用户及其需求的类型以及用户认知、心理行为等特征的调查、分析、研究，各种服务方式和模式的开发及对其实际效果和用户满意度的评价，用户认知和行为模型的建立等。
  信息检索评价研究：
• 通常包括检索性能评价、检索效益评价、检索评价方法与步骤、检索评价指标体系以及评价实例研究等。

A web service recommendation algorithm based on BaisSVD

Source

Da Sun ,Tong Nie Beijing Engineering Research Center for IoT Software and Systems, Information Department, Beijing University of Technology

Abstract

随着网络技术和网络服务的发展，Web服务的数量也将呈爆炸式增长，能够提供类似功能的Web服务的数量也将迅速增加。

服务质量(Quality of Service，QoS)被广泛用于描述和评价Web服务的非功能性能，并已成功地应用于服务推荐。

然而，目前的Web服务建议大多仍局限于传统的协同过滤，没有考虑用户和Web服务本身的偏向。

本文首先介绍了Web服务推荐的现状，然后分析了存在的问题和数据集的特点。最后，应用BiasSVD算法预测服务质量，并推荐给用户，将实验结果与传统的协同过滤算法进行了比较，得出了该算法在Web服务推荐场景中的可行性和优越性。

Keywords

Web服务;推荐;服务质量预测;协同过滤;矩阵分解;

Introduction

随着互联网技术的发展，Web服务的便利性导致了用户对Web服务的需求不断增加。如今，大量的Web服务充斥着互联网，用户的选择越来越多。同时，它们也提出了更高的要求：在相同的业务类型和条件下，用户除了满足功能需求外，还希望获得更高的服务质量(Qos)。

目前，通过预测服务质量并推荐给用户已经成为解决Web服务信息过载的一种方法。协同过滤是一种广泛使用的推荐技术，已被证明是最准确的预测方法。基于历史数据的经典协同过滤主要从三个方面进行研究。

• 第一种是从用户的角度出发，即基于用户的算法(UPCC)。
• 第二种是从项目的角度，即基于项目的算法(IPCC)。
• 第三种算法结合了用户和项目两个方面，即基于用户和项目的算法(UIPCC)。

UPCC的前提是，在现有数据中，两个用户之间的相似度越高，那些无法访问该项目的用户出现类似结果的可能性就越大。

IPCC正在从项目的角度寻找类似的项目进行预测。

UIPCC是UPCC和IPCC的加权结果。

一般来说，用户与项目之间的相似度可以通过余弦相似度或皮尔逊相关系数来获得。然而，传统的协同过滤Web服务推荐算法也存在一些不足：

• 如果项目之间存在相关性，信息量不会随着向量维度的增加而线性增加；
• 评分矩阵元素稀疏，计算结果不稳定，向量维度的增加或减少都会导致近邻结果的较大差异。

针对这些问题，本文使用BiasSVD来解决这些问题，从而提高推荐结果的准确性和用户体验。

RELATED WORK

A. Traditional collaborative filtering

目前，协同过滤推荐算法有两种：

• 基于用户的协同过滤推荐算法
• 基于项目的协同过滤推荐算法。

前者是基于这样的假设：如果用户对某些项目具有相似的分数，那么他们对其他项目也具有相似的分数，基于目标用户的最近邻居（最相似的用户），算法逼近目标用户对项目的分数。

对于后者，用户对不同项目的评分是相似的，要估计用户对某个物品的评分，可以估计用户物品的几个类似物品的评分。

协同过滤的关键步骤是计算用户之间的相似度。协同过滤算法中使用了多种方法来计算用户之间的相似度。其中大多数是基于用户对具有共同偏好的产品的评级。两种最常用的方法是Pearson correlation和included angle cosine；

这两种方法都将用户$x$和$y$频繁使用(overplay)的产品集定义为：
$$
S_{xy}=S_x\bigcap S_y
$$
用户$X$和$Y$之间的Pearson correlation定义为：
$$
{\rm Sim}(x,y)=\frac{\sum_{i\in S_{xy}}(r_{xi}-\overline{r_x})(r_{yi}-\overline{r_y})}{\sqrt{\sum_{i\in S_{xy}}(r_{xi}-\overline{r_x})^2 \sum_{i \in S_{xy}}(r_{yi}-\overline{r_y})^2}}
$$
在included angle cosine方法中，用户$x$和$y$由$m$维载体表示。两个载体之间的相似度可以通过以下方式获得

$$
{\rm Sim}(x,y)=\frac{\sum_{i\in S_{xy}}r_{xi}r_{yi}}{\sqrt{\sum_{i\in S_{xy}}r_{xi}^2\sum_{i\in S_{xy}}r_{yi}^2}}
$$
基于用户的方法利用来自类似用户的历史Qos体验进行个性化Qos预测，而基于服务的方法使用来自类似服务的方法进行预测。混合方法是前两种方法的结合，因此可以达到更高的预测准确率。

基于传统的协同过滤算法，UPCC和IPCC预测和推荐服务质量的基本步骤如下：

1. 准备数据集;
2. 计算用户（Web服务）的相似度并获取用户（Web服务）的相似度;
3. 选择最近的邻居用户（Web Service）获取相似用户（Web Service）的集合;
4. 服务质量预测并获取预测结果;
5. 推荐

不同的系统使用不同的相似度计算来使预测分数尽可能准确。协同过滤推荐系统虽然已得到广泛应用，但也面临着推荐效果不佳、系统扩展性弱等诸多问题。

B. Matrix factorization in Recommendation System

基于模型的协同过滤算法一般基于定义的随机参数模型。根据已有的Qos数据集，通过机器学习的方法训练预测模型来预测个性化QOS值，推荐系统的得分预测问题可以看作是一场补全矩阵的游戏，这是推荐系统的任务，而矩阵分解是为了实现其目标。

矩阵分解算法应用于个性化推荐的核心思想是将用户评分矩阵分解为一个低秩矩阵(low rank)，使产品尽可能接近原始评分矩阵，并使预测矩阵与原始矩阵之间的误差平方最小。

奇异值分解(SVD)由于既可以用于降维算法的特征分解，也可以用于推荐算法的特征分解，因此在机器学习中得到了广泛的应用。我们把$m$个用户和$n$个项目的得分作为一个矩阵$M$，然后用矩阵分解来解决推荐问题。

低秩矩阵为什么有用？

在矩阵论中，矩阵满秩当且仅当其各行各列线性无关，也就是说，矩阵的秩衡量矩阵内部的相关性；

在机器学习领域，矩阵往往表示图像，用户-物品推荐表等结构性信息，若行列间的相关性很低，意味着矩阵可以被降维，投影到更低维度的子空间，用较少的线性无关的向量表示，以表达矩阵其余的冗余信息；

在图像处理领域，如果图像的秩比较高，这意味着图像的噪声严重，低秩的矩阵往往被用于恢复图像；

注意到，对于矩阵$M_{s\times t}$，其秩$R(M)\le \min{s,t}$;

经验表明，对于海量的用户和项目的集合，决定用户对项目的打分往往和看起来只和若干指标有关，我们用这些指标构建低秩的矩阵，用于还原和近似原先的评分矩阵，换句话说，我们将评分矩阵近似分解成这些低秩矩阵的乘积；

1).FunkSVD

原始的奇异值矩阵分解(PureSVD)需要先填充矩阵，然后分解降维，由于逆运算$O(N^3)$，具有复杂度高的缺点。因此，Simon提出了FunkSVD的方法。他没有将矩阵分解为三个矩阵，而是将其分解为两个低等级用户项目矩阵，这降低了计算复杂性。
$$
M_{m\times n}=P^T_{m\times k}Q_{k\times n}
$$
对于用户评分，FunkSVD用于矩阵分解，相应的表示为$q_j^T p_i$;

FunkSVD使用线性回归(linear regression)的思想，通过最小化观察数据的平方来找到用户和项目的最佳隐式载体表示(the optimal implicit vector representation)。如果我们考虑所有物品和样本的组合，最小化以下公式:
$$
\sum_{i,j}(m_{ij}-q_j^T p_i)^2
$$
如果上述公式被最小化并找到相应的极端值(extreme value)$p_i,q_j$，则将得到矩阵$P$和$Q$;

对于矩阵$M$的任何空白分数，分数可以通过以下公式计算。同时，为了避免过度匹配观察数据(overfitting)，提出了带$L2$正则项的FunkSVD;
$$
\arg \min \sum_{i,j}(m_{ij}-q_j^Tp_i)^2+\beta(||p_i||^2+||q_j||^2)
$$
因此，使用FunkMVD进行推荐的步骤如下：

1. 通过梯度下降法求出$P$和$Q$，使损失函数最小化;
2. 通过$P$和$Q$完成矩阵;
3. 对于用户$i$，找到上一个值缺失的位置，并根据完成值从大到小进行推荐。

2).BiasSVD

基于FunkSVD算法有很多改进版本，其中BiasSVD是最受欢迎的一个。

提出的算法基于以下假设：一些用户或项目会带来自己的特征。BiasSVD推荐系统由三个部分组成：

• 有些与用户项目无关，称为用户偏向项;
• 有些与项目中的用户无关，称为项目偏向项。

假设评分系统的平均得分为$μ$，则添加偏差项后的优化目标函数如下：
$$
\arg \min \sum_{i,j}(m_{ij}-\mu-b_i-b_j-q_j^Tp_i)^2+\beta(||p_i||^2+||q_j||^2+||b_i||^2+||b_j||^2)
$$
在Web服务推荐中，有很多有关Web服务调用历史的偏好信息。例如，Web服务本身的服务质量一般较高，因此当需要预测Web服务的服务质量值时，预测的服务质量值应该包含Web服务的偏差信息。另一个用户可能更喜欢质量方面的吞吐量或响应时间。这些是用户或网络服务包含的偏见信息。将这些偏差信息添加到服务质量预测中可以提高预测准确率并具有更好的推荐效果。

与FunkSVD和BiasSVD相比，BiasSVD的最终推荐效果优于FunkSVD;本文中，作者还使用了BiasSVD算法作为Web服务的推荐模型。

RESULT OF EXPERIMENTS

首先介绍实验中使用的数据集，然后说明传统协同过滤算法和BiasSVD算法的真实算法流程、评估指标和实验结果。

A. DataSet

本文中的所有实验都基于来自香港中 文大学的郑先生收集的Web服务数据集。来自30个国家/地区的339名服务用户在73个国家/地区的5825个现实世界Web服务上总共执行了1974675次现实世界Web服务调用。每条记录还包含响应时间和吞吐量。

B. Algorithm flow

Input

QoS矩阵、正规化参数$β$,学习率$\alpha$;

Process

1. 根据相应的稀疏度对QoS矩阵进行稀疏化;

2. 考虑用户偏见信息和Web服务的偏见信息部分，并设置偏见;
   $$
   b_{ij}=\mu + b_i + b_j
   $$

   • $\mu$:所有记录的总体平均值
   • $b_i$:用户补偿信息(user offset information)
   • $b_j$:web服务补偿信息(web service offset information)

3. 在迭代过程中，可以将$b_i,b_j$的初始值设置为$0$，然后进行迭代;
   $$
   b_i\leftarrow b_i+\alpha(m_{ij}-\mu-b_i-b_j-q_j^Tp_i-\beta b_i)\
   b_j\leftarrow b_j+\alpha(m_{ij}-\mu-b_i-b_j-q_j^Tp_i-\beta b_j)\
   $$

4. 优化目标函数：
   $$
   \arg \min \sum_{i,j}(m_{ij}-\mu-b_i-b_j-q_j^Tp_i)^2+\beta(||p_i||^2+||q_j||^2+||b_i||^2+||b_j||^2)
   $$

output

服务质量预测值$p(u,i)$,构成矩阵QoS的预测值；

C. Evaluation indices

协同过滤推荐算法的评估方法有多种，两个主要的评估标准是MAE和RMSE，以及精确率、召回率等指标。本文使用了MAE和RMSE；

MAE的定义如下：
$$
{\rm MAE}=\frac 1n \sum_{u\in U,i\in I}|p_{ui}-r_{ui}|
$$
RMSE的定义如下：
$$
{\rm RMSE}= \sqrt{\frac 1n \sum_{u\in U,i\in I}|p_{ui}-r_{ui}|^2}
$$
从上面的公式可以看出，MAE重点关注预测误差的绝对值，无论误差的大小如何，其对所有误差的权重都是相同的;

RSSE对预测值与实际值的差进行平方运算，然后将差相加，差异大的结果赋予更大的权重，结果也会相应改变

Mae和RSSE的值与预测的准确性成正比，即值越小，预测越准确。

D. Experimental results and analysis

在本文中，作者比较了UPCC、IPCC、UPICC和FunkDID作为最终的比较算法，以验证该算法的效果。

UPCC、IPCC和UIPCC是基于用户、基于项目的混合协作过滤算法。FunkSVD是一种没有偏差的矩阵分解算法。 在经验中，我们主要验证在相同稀疏数据下，BiasDID算法是否能够与传统协同过滤算法相比提高预测准确率。

Fig.1显示了使用5%、15%和25%训练矩阵密度在不同响应时间和吞吐量预测方法下的MAE和RSSE结果。

总而言之，依靠平均值预测效果最差，而基于传统的协同过滤方法，包括UPCC、IPCC和UPICC，预测效果优于平均值预测，但仍然不理想。

关键是，在数据稀疏的情况下，基于矩阵分解的方法明显优于传统的协同过滤。随着密度的增加，所有方法的性能都有所提高，这表明更高质量的信息可以提高预测准确率，而且Bias奇异值在预测准确率方面更具优势。

CONCLUSION AND FUTURE WORK

传统的基于用户的协同过滤推荐算法在计算用户相似度时往往面临数据稀疏性和可扩展性差的缺点。然而，在矩阵分解中使用BiasSVD来计算用户相似度可以改善数据稀疏性的缺点，而且本身的可扩展性也很好。

因此，作者提出了一种基于BiasSVD的推荐算法。该算法在考虑用户偏好的同时，利用FunkSVD分解相似度矩阵。通过郑收集的数据集表明，与传统算法相比，该算法有效地克服了数据稀疏性的缺点，提高了服务质量预测的准确性。

但是，在计算相似度的过程中，迭代的时间复杂度需要进一步优化。此外，当面临冷启动时，BiasSVD的性能仍然较弱。因此，下一步需要寻找解决方案，优化时间复杂度，改善冷启动问题。

同时，对于近几年的热点技术，比如深度学习也可以应用到推荐算法中，以后的研究也会考虑深度学习在推荐算法中的应用。

Remember

• Write a report: 描述看到的图表
• No opinions：不应该具有主观描述
• No conclusion:任务是写一个Overview

Parts

1. Introduction: 一句话解释问题
2. Overview：两句话main or general things
3. Details:两段有助于段落的衔接,第一段描述起点
4. Details：第二段描述趋势

Types

Line Graph

• 比较这些曲线，而不是单独描述它们
• 不要单独写一段
• 两种类型的比较：总体上的(overview) + 特定点上的曲线(details)
• 图例上的单词往往不能用作句子动词的主体；

Introduction例句

• The graph below shows electricity production(in terawatt hours) in France between 1980 and 2012.（图片上方原题）
• The line graph compares the amount of electricity produced in France using 4 different sources of power over a period of 32 years.（优化）

Overview例句

• It is clear that nuclear power was by far the most important means of electricity generation over the period shown.(最高者)
• Renewables provided the lowest amount of electricity in each year.(最低者)

Details1例句

• In 1980, thermal power stations were the main source of electricity in France, generating around 120 terawatt hours of power. (比较起点最高值)
• Nuclear and hydroelectricity power stations produced just under 75 terawatt hours of electricity each, and renewable provided a negligible amount. (比较起点其他值)

Details2例句

• Just one year later, nuclear power overtook thermal power as the primary source of electricity.
• Between 1980 and 2005, electricity production from nuclear power rose dramatically to a peak of 430 terawatt hours.
• By contrast, the figure for thermal power fell to only 50 terawatt hours in 1985, and remained at this level for the rest of the period.
• Hydroelectricity power generation remained relatively stable, at between 50 and 80 terawatt hours, for whole 32-year period.
• But Renewable electricity production saw a small rise to approximately 25 terawatt hours by 2012.

Bar Chart

这类横轴为时间的柱状图和线形图类似；描述changes over all months;

这类横轴为Item的柱状图需要compare bars；

Introduction例句

• The bar chart compares the number of mobile phone sold worldwide by the five most popular manufactures in the years 2009, 2011, and 2013.

Overview例句

• It is clear that Nokia sold the most mobile phones between 2009 and 2011, but Samsung became the best selling brand in 2013.
• Samsung and Apple saw the biggest rises in sales over the 5-year period.

Details1例句

• In 2009, Nokia sold close 450 million mobile phones, which was almost double the number of handsets sold by Samsung, the second most sucessful manufacture.
• Over the following 5 years, however, Nokia’s sale figures fell by approximately 200 million units, whereas Samsung saw sales rise by a similar amount.
• By 2013, Samsung had become the market learder with sales reaching 450 million.

Details2例句

• The other three top selling mobile phone brands between 2009 and 2013 were LG, ZTE and Apple.
• In 2009, these companies sold around 125 million, 50 million and 26 million mobile handsets respectively, but Apple overtook the other two vendors in 2011.
• In 2013, purchases of Apple handsets reached 150 million units, while LG saw declining sales and the figures for ZTE rose only slightly.

Pie Chart

• pie chart可以表示数字，可以表示百分比，当看不见数字或比例时，依然可以进行大约的估计；
• pie chart 可以比较随时间的变化；

Table

• Table可以表示任何一种数字，也可以表示时间的变化
• 表示和line，bar，pie表一样的信息
• 需要做出数字的比较，但是难以描述所有的信息

Introduction

• The table compares the five highest ranking countries in terms of the number of tourists and tourists spending over a period of 2 years.

Overview

• Overall, it is clear that France was the world’s most popular tourists destination in the years 2012 and 2013.
• However, the USA earned by far the most revennue from tourism over the same period.

Details

• In 2012, 83 million tourists visited France, and the USA was the second most visited country, with 66.7 million tourists.
• Spain and China each receiveed just under 58 million tourists, while Italy was ranked of bettwen 1 and 4 million tourists.
• 2013 saw a rise of bettwen 1 and 4 million tourist visits to each country, with the exception of China, which recieve 2 million fewer visitors than in the previous year.
• Spending by tourists visiting the USA increaseed from $126.2 billion in 2012 to 139.6 billion in 2013, and these figures were well over twice as high as these for any other country.
• Spain received the second highest amounts of tourist revenue, rising from $56.3 billion to $ 60.4 billion, follow by France, CHina and Italy.
• Interestingly, despite falling number of tourists, Chinese revenue from tourism rose by $1.7 billion in 2013.

Comparing Diagram

Process Diagram

Remember

• Task2一般的任务是写一篇essay，40分钟内不少于250字；
• 通常有一个Universal topics
• Task response 一定要回答问题
• Coherence and cohesion 衔接和连贯
• Vocaburary 词汇
• Grammar 避免语法错误

Parts and Timing

• (Planning:5分钟)
• Introduction： 2句话，5分钟；
• Main Paragraph 1: 5句话，10分钟
• Main Paragraph 2：5句话，10分钟
• Conclusion: 1句话，5分钟
• (Check words:5分钟)

Example1

Discussion

Some people think that it more effective for students to study in groups, while others believe that it is better for them to study alone.

Discuss both views and give your own opinion.

People have different views about the pffedctiveness of group study as opposed to working working alone. While there are some benefits to studying independently, I believe that group work is usually more productive.

Opinion

Some people believe that unpaid commuinity service should be a compulsory part of high school programmes.

To what extent do you aggress or disagree?

It is sometimes argued that high school students should be made to do some work in their local communities. In my opinion, it would be wrong to force teenagers to do any kind of unsalaried work.(/ I completely aggree that this kind of scheme would be a good idea.)

There several reasons why I would argue against having compulsory community service for secondary scholl students. Firstly, the school curriculum is already full with important academic subjects., such as maths, sicence, and languages. For example, I remember having an extremely busy timetable when I at high shcool, and it would nmot have been possible to add it. Secondly, students’ performance in other subects would be affected if valuable study time were taken by charity work or neighbourhood improvement schemes. Finally, I believe that teenager students would be reluctant to take part in any programme of obligatory work, and this could lead to poor motivation and even bad behavior.

On the other hand, the opportunity to do voluntary community service could be extremely positive for high school students. By making these programme optional, schools would ensure that only motivated students took apart. These young people would gain valuable experience in an adult working envoironment, which could help to build their self confidence and enhance their skills. Having such experience and skills on their CVs could greatly improve school leavers’ career prospects. For example, a period of voluntary work experience might imporess a university admission officer ir a future employer.

In conclusion, unpaid commuinity service should not be a compulsory part of high school programmes.

Problem and Solution

Many criminal reoffend after they have been punished.Why do some people continue to cimmit crimes after they have bben punished, and what measures can be taken to tackle this problem?

It is true that punishments do not always deter criminals from committing more crimes.There are various reasons why offenders repeateedly break the law. but governments could certianly take steps to address this issue.

Two-part question

As most people spend a major part of their adult life at work, job satisfaction is an important element of indivisual well-being. What factors contribute to job satisfaction? How realistic is the expression of job satisfaction for all workers?

Work plays a cental role in our lives, and we world all like to feel fulfilled professionally.While a variety of factors may lead to job satisfaction. It would be unrealistic to expect everyone to be happyt at work.

Model Essay

Line Graph

The line graph compares the amount of electricity produced in France using 4 different sources of power over a period of 32 years.

It is clear that nuclear power was by far the most important means of electricity generation over the period shown.Renewables provided the lowest amount of electricity in each year.

In 1980, thermal power stations were the main source of electricity in France, generating around 120 terawatt hours of power. Nuclear and hydroelectricity power stations produced just under 75 terawatt hours of electricity each, and renewable provided a negligible amount.

Just one year later, nuclear power overtook thermal power as the primary source of electricity. Between 1980 and 2005, electricity production from nuclear power rose dramatically to a peak of 430 terawatt hours. By contrast, the figure for thermal power fell to only 50 terawatt hours in 1985, and remained at this level for the rest of the period. Hydroelectricity power generation remained relatively stable, at between 50 and 80 terawatt hours, for whole 32-year period. But Renewable electricity production saw a small rise to approximately 25 terawatt hours by 2012.

The table illustrates participation trends in five recreational activities at a Melbourne social center over two decades. Overall, while table tennis and musical performances saw substantial growth, amateur dramatics experienced a dramatic decline, with other activities showing more modest fluctuations.

Film club participation fluctuated between 60-67 members, initially dropping from 64 (2000) to 60 (2010) before rebounding to 67 by 2020. Similarly, martial arts maintained relative stability, hovering between 31-38 participants despite intermittent dips. The most striking trend emerged in amateur dramatics, which plummeted from 26 to just 6 participants - a decrease of over 75% - with the steepest decline occurring between 2010-2015.

In contrast, table tennis demonstrated remarkable growth, surging from 15 to 54 participants (260% increase), particularly accelerating after 2015 when numbers jumped from 20 to 35 within five years. Musical performances, starting from near-zero participation (1 in 2000), gradually gained popularity reaching 18 participants by 2020, with its most significant growth phase (from 12 to 16) occurring between 2010-2015.

Notably, while table tennis and musical performances showed consistent upward trajectories, other activities displayed cyclical patterns, suggesting shifting preferences in community leisure activities over the period.

Bar Chart

The bar chart compares the number of mobile phone sold worldwide by the five most popular manufactures in the years 2009, 2011, and 2013.

It is clear that Nokia sold the most mobile phones between 2009 and 2011, but Samsung became the best selling brand in 2013. Samsung and Apple saw the biggest rises in sales over the 5-year period.

In 2009, Nokia sold close 450 million mobile phones, which was almost double the number of handsets sold by Samsung, the second most sucessful manufacture. Over the following 5 years, however, Nokia’s sale figures fell by approximately 200 million units, whereas Samsung saw sales rise by a similar amount. By 2013, Samsung had become the market learder with sales reaching 450 million.

The other three top selling mobile phone brands between 2009 and 2013 were LG, ZTE and Apple. In 2009, these companies sold around 125 million, 50 million and 26 million mobile handsets respectively, but Apple overtook the other two vendors in 2011. In 2013, purchases of Apple handsets reached 150 million units, while LG saw declining sales and the figures for ZTE rose only slightly.

Table

The table compares the five highest ranking countries in terms of the number of tourists and tourists spending over a period of 2 years.

Overall, it is clear that France was the world’s most popular tourists destination in the years 2012 and 2013. However, the USA earned by far the most revennue from tourism over the same period.

In 2012, 83 million tourists visited France, and the USA was the second most visited country, with 66.7 million tourists. Spain and China each received just under 58 million tourists, while Italy was ranked of bettween 1 and 4 million tourists.

2013 saw a rise of bettwen 1 and 4 million tourist visits to each country, with the exception of China, which recieve 2 million fewer visitors than in the previous year. Spending by tourists visiting the USA increaseed from $126.2 billion in 2012 to 139.6 billion in 2013, and these figures were well over twice as high as these for any other country. Spain received the second highest amounts of tourist revenue, rising from $56.3 billion to $ 60.4 billion, follow by France, CHina and Italy. Interestingly, despite falling number of tourists, Chinese revenue from tourism rose by $1.7 billion in 2013.

Opiniion

It is sometimes argued that high school students should be made to do some work in their local communities. In my opinion, it would be wrong to force teenagers to do any kind of unsalaried work.(/ I completely aggree that this kind of scheme would be a good idea.)

There several reasons why I would argue against having compulsory community service for secondary scholl students. Firstly, the school curriculum is already full with important academic subjects., such as maths, sicence, and languages. For example, I remember having an extremely busy timetable when I at high shcool, and it would nmot have been possible to add it. Secondly, students’ performance in other subects would be affected if valuable study time were taken by charity work or neighbourhood improvement schemes. Finally, I believe that teenager students would be reluctant to take part in any programme of obligatory work, and this could lead to poor motivation and even bad behavior.

On the other hand, the opportunity to do voluntary community service could be extremely positive for high school students. By making these programme optional, schools would ensure that only motivated students took apart. These young people would gain valuable experience in an adult working environment, which could help to build their self confidence and enhance their skills. Having such experience and skills on their CVs could greatly improve school leavers’ career prospects. For example, a period of voluntary work experience might impress a university admission officer in a future employer.

In conclusion, unpaid community service should not be a compulsory part of high school programmes.

The debate between embracing competition and prioritizing cooperation permeates various aspects of life. While competition drives individuals to excel, cooperation fosters collective progress. This essay will analyze both perspectives before concluding that a balanced approach yields optimal outcomes.
Proponents of competition argue that it cultivates excellence. In academic settings, for instance, standardized examinations rank students, motivating them to surpass peers. Similarly, workplace promotions often hinge on outperforming colleagues, which incentivizes innovation. A study by Harvard Business Review revealed that sales teams with performance-based bonuses achieved 23% higher revenue than those without. Such evidence underscores competition’s role in enhancing productivity.

Conversely, cooperation emphasizes shared goals. Scientific breakthroughs, like the discovery of DNA’s structure, resulted from collaborative efforts between Watson, Crick, and Franklin. In daily life, community projects—such as neighborhood clean-ups—rely on collective action to address issues beyond individual capacity. Moreover, multinational corporations like Apple and Google increasingly adopt cross-industry partnerships to develop sustainable technologies, demonstrating cooperation’s scalability.

While both approaches have merits, their applicability depends on context. Competition suits scenarios requiring rapid individual growth, whereas cooperation excels in complex, interdisciplinary challenges. For example, schools could balance group projects (to nurture teamwork) with individual assessments (to recognize personal merit). Ultimately, societies thrive not by choosing one over the other but by strategically integrating both.

In conclusion, competition and cooperation are complementary forces. By judiciously deploying each where most effective, individuals and organizations can maximize their potential while fostering social harmony.

The traditional five-day workweek has become increasingly incompatible with contemporary societal demands. I firmly concur that shortening the working week while extending weekends would yield substantial benefits for both individuals and organizations.

Primarily, compressed work schedules remarkably enhance productivity. Microsoft Japan’s groundbreaking experiment in 2019 demonstrated this vividly, where implementing a four-day workweek resulted in 40% productivity growth alongside reduced electricity consumption. This phenomenon stems from the Parkinson’s Law principle - work expands to fill the time available. When temporal constraints tighten, employees instinctively eliminate redundant procedures and prioritize essential tasks.

Furthermore, extended weekends significantly improve population health. The World Health Organization’s alarming statistics reveal 745,000 annual deaths from stroke and heart disease attributed to overwork. Longer rest periods enable working professionals to engage in preventive healthcare measures like regular medical checkups and fitness routines. From a macroeconomic perspective, this could alleviate pressure on public health systems while boosting leisure industry revenues.

Skeptics may argue that reduced working hours jeopardize economic output. However, the UK government’s 2022 pilot program disproves this assumption, showing 2.1% GDP growth in participating sectors. This paradox can be explained by the replacement of protracted presenteeism with task-oriented efficiency. Modern workflow management systems allow precise performance tracking, rendering prolonged office hours obsolete.

In conclusion, restructuring the conventional workweek represents an inevitable evolution in labor practices. By embracing this paradigm shift, societies can achieve sustainable progress through optimized productivity, enhanced workforce well-being, and stimulated economic diversification. The correlation between reasonable working hours and comprehensive social development has become irrefutable in the post-industrial era.

The debate over working hours has gained momentum in recent years. I strongly support the implementation of shorter workweeks with extended weekends, as this approach benefits both employees’ well-being and organizational efficiency.

From an productivity perspective, condensed work schedules often yield better results. Numerous tech companies have reported increased output after adopting four-day work models. A notable case involves a European IT firm that maintained 100% productivity levels despite reducing office hours by 20%. This success can be attributed to employees focusing on essential tasks rather than unproductive “face time” in offices. Such evidence contradicts traditional beliefs about linear relationships between working hours and results.

Health considerations further validate this approach. Medical studies consistently show that chronic overwork leads to elevated stress hormones and weakened immune systems. The WHO has identified long working hours as a significant risk factor for cardiovascular diseases. Extended weekends provide crucial recovery time, allowing workers to engage in physical exercise and mental relaxation. For instance, Sweden’s trial with six-hour workdays demonstrated 15% reduction in stress-related sick leaves.

Critics highlight potential economic drawbacks, particularly for service industries. However, innovative scheduling solutions can mitigate these concerns. New Zealand’s tourism sector successfully implemented staggered three-day weekends across different employee groups, maintaining 24/7 operations while granting each worker extended breaks. Modern workforce management tools enable such flexible arrangements without compromising service quality.

In conclusion, shortening the standard workweek represents a necessary evolution in employment practices. While implementation challenges exist, particularly in customer-facing industries, technological advancements and creative scheduling make this transition feasible. Both governments and corporations should collaborate to develop phased implementation strategies, ensuring this reform enhances rather than hinders economic performance. The accumulated evidence from various pilot programs worldwide makes a compelling case for this structural change in labor markets.

图表

• the figure for
• line graph

描述

• It is clear that
• compare / paraprase / summarize / illustrate
• by the contrast, in comparison with
• the trend of

时间

• over a period of 30 years， over two decades
• over the following 4 years
• just one year later
• for the rest of the period
• throughout the period

数量

• as the main/primary source
• a negligible amount
• overtook
• become the market learder

连词

• however
• whereas, while

极端值

• a peak of / peaking at 67
• by far the most/highest important

趋势

1. 形容缓慢增长
   • saw only a small rise
   • rise only slightly
   • rise by a similar amount
   • gradually gained popularity reaching
2. 形容快速增长
   • saw substantial growth
   • saw demonstrated remarkable growth
   • surging from … to … (surged 飙升)
3. 形容缓慢下降
   • dropping from … to …
4. 形容快速下降
   • fell by 200 units
   • experienced a dramatic decline
   • plummeted 暴跌
5. 形容平稳波动
   • perform stable
   • remained at this level
   • showing modest fluctuations
   • maintained relative stability
6. 达到某个值/某个区间
   • reach 500 units
   • fell to only
   • rebounding to 反弹到某个值
   • despite temporary dips around 2005 and 2015. 除了2005年和2015年的短暂下跌
   • within a 31-38 units range

程度

1. 夸张/急剧的变化
   • dramatically
   • a catastrophic decline
2. 相对变化
   • relatively 相对
   • respectively (分别)
3. 近似
   • 大约 approximately
   • close to
   • around
   • almost
   • Similarly

总结句

• The most striking trend emerged in…
• Overall， …
• Notably

连接词

firstly, for example, secondly, finally，

to begin with, for a start,

描述词

negatives, bad effects,

impaired, damaged,

Part1

Part3

注意以下四种逻辑连贯

1. 举例子/平行列举: 上义词—>下义词;
2. 对比;
3. 假设论证：if/ if not;
4. 因果论证: 因为什么造成什么结果，进一步又造成什么结果：eg. take a gap year to travel

What can children learn from their parents?

Children can learn so many aspects of life from their parents:

for starters, they can pick up essential life skills: eg. cooking, cleaning, doing laundry and other types of housework/house chores from their parents—>foster/cultivate/nurture v.培养, help sb grow to be independent people/self-reliant individuals who can take good care of themselves as well as other family members;

decent values(关注在morals and virtues): —> eg. follow certain social norms and code of conducts that are promoted in a community (eg. how to behave well in the public places)+ good qualities like helping others in need/ respecting the old and protecting the young;

why (good-mannered/ virtuous people, and in the future they are going to good members of the society who can be well accepted and even respected by other others

parents usually attach great importance to teaching their children about interpersonal skills: eg. how to establish sound relationships with others (自问自答the key is to foster themselves into sincere, considerate/compassionate, and helpful individuals) —> in this case, children will grow to be such people who can thrive in the interpersonal relationships and easily get emotional support or inner satisfaction from their families and friends.

general knowledge通识/common sense: eg. art/science subjects—>not only serves to lay a solid foundation for their future studies/career, but also increase their knowledge of the world, as well as arouse their interests into exploring the world;

master/pick up/develop/enhance/promote critical soft skills: eg. communication skill, cooperation skill, problem-solving ability…+ by engaging in various kinds of in-class and extra-curricular activities that are well designed to cater for their needs, the interactions with their classmates and teachers allow them to be more confident;

it is their parents who keep their children company since they were born +黄金窗口期during the critical stages of children’s development, parents would take every opportunity to give them proper guidance in regards to/ in respective of so many aspects of life including decent morality, independent life skills, and anything they know about. Thus/hence/therefore/so it’s fair to say that parents exert more profound/long-lasting influences on sb;

teachers wouldn’t interact with their students until those children turn to school age; at the same time, in most cases, teachers would have to take in charge of so many students in a class but they only have limited time and energy, which means that they can merely focus on imparting knowledge and some job-related skills. In all, teachers would have much less impact on children’s well-rounded development in this sense

peer pressure: compare to sb.; loser, feel left/lagged behind, feel stressed out, be under huge/great pressure from…; 但也可turn into a kind of motivation, to catch up, drive sb to do sth;

a sea/wealth of information, different sources of information, serve to broaden horizon/expand outlook, increase their knowledge of this world;

-expand one’s social circle, enrich one’s life;

-for relaxation: browse short videos…;

hide behind a false identity, lure sb to fall into online frauds—>do damage to one’s personal safety and property;

*