用Python实现协同过滤算法
本文分享两种经典协同过滤算法的Python实现：
基于物品的协同过滤算法
基于用户的协同过滤算法
代码来自Github开源项目：fun-rec.
在开始之前，先导入用到的库：
1234567import pandas as pdimport numpy as npimport warningsimport random, math, osfrom tqdm import tqdmfrom sklearn.model_selection import train_test_splitwarnings.filterwarnings('ignore')
数据准备本次使用的数据是一份电影评分数据：
::将数据集划分成4列，从左到右分别代表：用户id，电影id，评分值，时间戳。
首先将原始数据转换成pandas的数据框表示：
然后提取每个用户评价过的电影，格式如下：
稍后的ItemCF和UserCF都将使用这个表。
数据处理完整代码如下：
12345678910111213141516171819202122232425262728def get_data(root_p ...
经典推荐模型:FNN，DeepFM
之前我们已经介绍了FM模型，在进入深度学习时代后，通过将FM模型与深度学习模型进行结合，产生了许多有用的新模型，本文将介绍其中的两种：FNN和DeepFM.
FNNFNN的结构如下：
结构很简单，在底层将多个特征域中的稀疏向量进行了Embedding，然后将Embedding的结果输入到全连接层进行特征交叉，最后输出预测结果。
FM模型为每一个特征学习了一个隐向量，两个特征交叉得到的新特征的系数等于这两个特征对应隐向量的内积。
而FNN直接将训练好的FM的权重(一阶特征权重+隐向量)拿了过来，作为自己的Embedding层的初始化权重。
只考虑隐向量，假设某特征域的总类别数为n，隐向量(Embedding的维度)是k，那么在 FM中，每一个类别特征对应一个长度为k的隐向量，因此总的隐向量可以用一个n*k的矩阵来表示；在FNN的Embedding层中，某特征域的总类别数为n，Embedding层的神经元个数为k，于是Embedding层的参数也可以用一个n*k的矩阵来表示。
具体对应关系如下图：
注意，虽然箭头指向了神经元，但表示的是被指向的神经元与输入神经元之间的权重。
自底向上，用数 ...
基于NeuralCF的图书推荐系统
本文将对CCF《图书推荐系统竞赛》官方baseline进行详细解读，并修正一些错误，修正后的jupyter notebook文件可以在公众号”南极Python”后台回复图书推荐自行获取。
赛题地址：https://www.datafountain.cn/competitions/542
题目介绍背景随着新型互联网的发展，人类逐渐进入了信息爆炸时代。新型电商网络面临的问题也逐渐转为如何让用户从海量的商品中挑选到自己想要的目标。推荐系统正是在互联网快速发展之后的产物。为帮助电商系统识别用户需求，为用户提供其更加感兴趣的信息，从而为用户提供更好的服务，需要依据真实的图书阅读数据集，利用机器学习的相关技术，建立一个图书推荐系统。用于为用户推荐其可能进行阅读的数据，从而在产生商业价值的同时，提升用户的阅读体验，帮助创建全民读书的良好社会风气。
任务依据真实世界中的用户-图书交互记录，利用机器学习相关技术，建立一个精确稳定的图书推荐系统，预测用户可能会进行阅读的10本书籍。
数据包含训练集和测试集，以及提交示例文件。
训练集中存储了用户与图书之间的交互信息，比如第一行: (user_id=0, i ...
跨考小白学刷题(下)
第八章：回溯8-3排列问题
我自己(在看了答案后默)写的AC代码：
12345678910111213141516171819class Solution: def permute(self, nums: List[int]) -> List[List[int]]: if not nums: return [] def back_track(nums,index): if index==len(nums): res.append(p[:])#必须加这个:，因为path之后还会变 return for num in nums: if num not in p: p.append(num) back_track(nums,index+1) p.pop() ...
跨考小白学刷题(上)
第一章1-1
对一组数据进行排序时，要考虑这组数据有什么样的特征。
包含大量重复元素->三路快排
近乎有序->插入排序
取值范围有限->计数排序
要求稳定排序->归并排序
使用链表存储-> 归并排序
数据量很大->外部排序
1-4
当没有思路时
尝试简单测试用例
暴力法
第二章2-1O(f(n))表示算法执行的上界
最后一项，nlog(n)是数组全部元素比较的次数，s指的是确定两个字符串的字典序需要O(s).
因此，最终的时间复杂度是：O(nslog(s)+snlog(n))
2-2
第一个，只需要ret和i
第二个，递归深度为n
2-3
reverse函数的时间复杂度是O(m/2)=O(m)，其中m指的是s的长度，又由于s的长度和while中执行次数是一样的(每执行一次，s多一位)，因此也是s的长度也是logn，从而整体的时间复杂度是O(2logn)=O(logn).
可见，log的底并不重要。
第一重循环log(n)次，因此整体时间复杂度是O(nlogn).
2-4
2-6动态数组
添加/删除一个元素的均摊复杂度是O(1 ...
Spark编程基础-Python版本
第一章、基础概念目前的主流大数据技术：Hadoop、Spark、Flink、Beam.
Hadoop
MapReduce像写单机任务一样.
使用前提：任务必须满足可以分而治之.
YARNHadoop2.0出现.
统一调配资源，实现底层数据无缝共享.
Spark全能选手.
Hadoop的缺点
有些不能转成Map和Reduce的业务无法使用Hadoop.
需要反复迭代，磁盘IO开销大.
磁盘IO，任务之间的衔接延迟高.
衔接延迟：3个Map任务全部结束才能执行REduce任务.因此难以胜任多阶段的复杂任务.
Spark的优势Spark本质上也属于MapReduce，但是不再局限于Map和Reduce这两个操作，还可以执行其它操作，比如groupby，filter，join等等，因此具有更强大的表达能力.
Spark可以将数据读到内存中进行操作，提升了迭代时的运行效率.
Spark使用了有向无环图的调度机制，使得相关的操作可以优化，从而很多操作可以进行流水线化处理.
对比Hadoop和Spark的读取和查询：Hadoop每次都要读写磁盘，而Spark可以直接在内存中完成，所以性能更好.
S ...
经典推荐模型:Deep&Cross
本文介绍Deep&Cross模型，它沿用了Wide&Deep模型的设计思路，并且将Wide&Deep的Wide部分使用Cross Network进行了替换，解决了Wide&Deep需要人工选取交叉特征的麻烦。
Deep&Cross模型结构如下：
从下往上看。
将稀疏特征进行Embedding，将得到的结果与稠密特征(一般指的是数值型特征)进行拼接，这就是网络的输入$x_0$.
$x_0$再往上兵分两路，左路是Cross Network部分，右路是Deep部分。
先看左路。它是由多个Cross Layer构成的，Cross Layer执行的前向运算如下：
该运算可视化如下：
可以看到 ，$x_0$在每一层中都有参与。
事实上，随着Cross Layer的层数增加，原始输入$x_0$各个位置元素交叉的阶数也在增加，具体参见如下推导：
正因如此，Cross Network相比于Wide&Deep中的Wide部分拥有更强的特征交叉能力，而且，每一个Cross Layer的参数只有$w$和$b$，它们的维度和$x_0$的维度一致，因此参数量是线 ...
经典推荐模型:Wide&Deep
本文介绍谷歌于2016年提出的Wide&Deep模型，它兼具记忆能力与泛化能力，在谷歌商店的app推荐中效果显著。
Wide&Deep由记忆能力较强的Wide部分和泛化能力较强的Deep部分组成，接下来我们分别介绍这两部分，然后将它们组合起来，得到Wide&Deep.
WideWide部分是一个(广义)线性模型，比如逻辑回归，具有较强的记忆能力。
输入这种模型的特征可以通过交互产生新的有用特征，然后将这些新的特征与原始特征共同输入模型进行预测。
举个栗子，假设输入逻辑回归模型的特征中含有”已安装应用，在应用商店看到的应用”这俩特征，那么我们可以根据这俩特征得到一个新的交互特征：”已安装应用=xxx 并且 在应用商店看到的应用=yyy”.
使用上述方法构造特征，训练模型。当待预测的样本特征中也含有类似上述交互特征时，由于在训练集中存在相同特征，那么模型就能很快定位到训练集中出现相同模式时的标签。
假设训练集中出现”已安装应用=Youtube 并且 在应用商店看到的应用=facebook”这一交互特征，也就是说，用户安装了Youtube，并且在应用商店中看到了Fac ...
经典推荐模型:PNN
之前介绍的NeuralCF使用神经网络代替了协同过滤中的点积操作，并取得了一定的进步。但是，它只使用了用户-物品的共现矩阵进行建模，而忽略了其它特征，比如用户的性别、年龄等。
本文将要介绍PNN在模型中加入了更多的特征，并设计了更为精细的特征交叉方式。
PNN简介PNN，全称是Product-based Neural Networks，这里的Product特指PNN中的Product层。如果将Product层所做操作替换成简单的拼接(concat)，那么就变成了我们之前介绍的Deep Crossing。因此，PNN最大的创新就在于Product层。
PNN总体结构PNN的结构如下图所示：
从下往上看。
Input Layer：Input层的输入是一些类别特征，它们一般是One-Hot编码的形式，比如第一个特征域Field1表示性别，如果当前输入样本性别为男，则Field1对应特征的值是”10”，若是女则为”01”，其余特征域同理。
举个栗子，假设共2个类别变量，分别为’性别，星期几’，那么对于如下样本：
1男，星期2
输入网络的数字为：
1100100000
最开始的10表示男，后面的 ...
经典推荐模型:NeuralCF
之前，我们在协同过滤的基础上，引入了矩阵分解技术，将用户-物品的共现矩阵分解得到用户的隐向量和物品的隐向量。由于隐向量的维度一般是低于其在共现矩阵中的维度的，从而加强了协同过滤模型对于稀疏矩阵的处理能力，提升了模型的泛化性能。具体可以看这篇：
https://hans0809.github.io/2021/08/31/%E5%BD%93SVD%E9%81%87%E8%A7%81CF/
这样，在获得用户和物品的隐向量后，求解用户的某一隐向量与物品的某一隐向量之间的内积，就得到了对应的评分。
这其中的原理是：两个向量求内积，相当于求解两者之间的余弦相似度，因此该操作可以度量两个向量之间的相似性。
内积操作的缺点假设隐向量所在空间维度为$K$，则第$u$个用户$p_u$对于第$i$个物品$q_i$的预测评分通过内积计算如下：从计算公式可以看出，内积操作是一种线性运算。
下图左侧是用户-物品的共现矩阵，右侧是相应的用户隐向量空间。
在左侧的共现矩阵中，$u_4$与$u_1$最相似，其次是$u_3$，最后是$u_2$。
而在右侧的隐空间中，$p_4$与$p_1$最相似，其次是$p_2$，最后是$ ...
