发表于 | 更新于 | 分类于
字数统计: 368

卡拉兹(Callatz)猜想：

对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1？

阅读全文 »

发表于 | 更新于 | 分类于
字数统计: 203

在c++中，当char * 指向字符常量时（以下面的程序为例）

1
2
3
4
5
6
7
#include <cstdio>

int main() {
	char *a = "I love China!";
	printf("%s\n",a);
	return 0;
}

编译时，将产生如下warning：

1
2
3
4
5
ProblemC.cpp:4:12: warning: conversion from string literal to 'char *' is
      deprecated [-Wc++11-compat-deprecated-writable-strings]
        char *a = "I love China!";
                  ^
1 warning generated.
阅读全文 »

发表于 | 更新于 | 分类于
字数统计: 847

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（$A_0 A_1⋯A_{N−1}$）变换为（$A_{N-M}⋯A_{N−1} A_0 A_1⋯A_{N−M−1}$）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

阅读全文 »

发表于 | 更新于 | 分类于
字数统计: 1.9k

推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣，因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。

如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，就是冷启动问题（cold start）。

阅读全文 »

发表于 | 更新于 | 分类于
字数统计: 1.2k

基于物品的协同过滤算法（item-based collaborative filtering，以下简称ItemCF）算法思想：给用户推荐那些和他们之前喜欢的物品相似的物品。

不过，ItemCF算法并不利用物品的内容属性计算物品之间的相似度，它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为，物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。

基于物品的协同过滤算法可以利用用户的历史行为给推荐结果提供推荐解释，比如给用户推荐《天龙八部》的解释可以是因为用户之前喜欢《射雕英雄传》。

ItemCF算法主要分为两步。
(1) 计算物品之间的相似度。
(2) 根据物品的相似度和用户的历史行为给用户生成推荐列表。

阅读全文 »

发表于 | 更新于 | 分类于
字数统计: 1.3k

在推荐系统研究领域中，应用问题主要有评分预测和TopN推荐。

评分预测

预测用户对物品评分的行为称为评分预测（rating prediction）。

评分预测的预测准确度一般通过均方根误差(Root Mean Squared Error，简称RMSE)和平均绝对误差(Mean Absolute Error，简称MAE)计算。

对于测试集中的一个用户u和物品i，令$r_{ui}$是用户对物品i的实际评分，而$\hat{r}_{ui}$是推荐算法给出的预测评分。

RMSE

$$
RMSE = \sqrt{
\frac {
\sum_{(u,i)\in Test} (r_{ui}-\hat{r}_{ui})^2
}{
\left \vert Test \right \vert
}
} \tag{1}
$$

MAE

MAE采用绝对值计算预测误差，它的定义为:
$$
MAE = \frac {
\sum_{(u,i) \in Test}{|r_{ui}-\hat{r}_{ui}|}
}{
\left \vert Test \right \vert
} \tag{2}
$$

TopN推荐

网站在提供推荐服务时，一般是给用户一个个性化的推荐列表，这种推荐叫做TopN推荐。

在推荐系统的论文中，经常可以看到xx@N，它是xx at rank N的缩写。意为在TopN推荐中，该指标的值。

Precision/Recall

TopN推荐的预测准确率一般通过准确率(precision)/召回率(recall)度量。

令R(u)是根据用户在训练集上的行为给用户作出的推荐列表，而T(u)是用户在测试集上的行为列表。那么，推荐结果的召回率定义为:
$$
\mathrm{Recall}@N = \frac {
\sum_{u \in U}|R(u) \cap T(u)|
} {
\sum_{u \in U}|T(u)|
} \tag{3}
$$
推荐结果的准确率定义为：
$$
\mathrm{Precision}@N = \frac {
\sum_{u \in U}|R(u) \cap T(u)|
} {
\sum_{u \in U}|R(u)|
} \tag{4}
$$
F1值
$$
\mathrm{F1} = \frac{
2 \times Precision \times Recall
}{
Precision + Recall
} \tag{5}
$$

AP/MAP

精度均值（Average Precision，简称AP)
$$
AP@N = \frac{
\sum_{k=1}^N
\mathrm{Precision@k \times rel(k)}
}{
\min \{
N, \left \vert C_{\mathrm{adopted}} \right \vert
\}
} \tag{6}
$$
其中，rel(k)是指示函数，表示第k个物品是否被采纳
$$
\mathrm{rel(k)} =
\begin{cases}
1, & I_k \in C_{\mathrm{adopted}} \\
0, & \mathrm{otherwise}
\end{cases}
$$
平均精度均值（Mean Average Precision，简称MAP)
$$
\mathrm{MAP}@N = \frac{1}{
\left \vert U \right \vert
}
\sum_{u \in U} \mathrm{AP}@N \tag{7}
$$

Hit Ratio

命中率（Hit Ratio, 简称HR）
$$
\mathrm{HR}@N = \frac{
\mathrm{hits}
}{
\left \vert U \right \vert
} \tag{8}
$$

ARHR

平均命中排序倒数（Average Reciprocal Hit Rank，简称ARHR)
$$
\mathrm{ARHR}@N = \frac{1} {
\left \vert U \right \vert
}
\sum_{i=1}^{hits} \frac{1}{
pos_i
} \tag{9}
$$
其中，$pos_i$表示第i次命中时，测试物品在推荐列表中的位置。

NDCG

NDCG源自于信息检索领域，用于评估排序质量。在理解NDCG前，需要弄明白CG、DCG以及IDCG的概念。

  • CG

累计收益（Cumulative Gain，简称CG）
$$
\mathrm{CG}@N = \sum_{i = 1}^N rel_i \tag{10}
$$
其中，$rel_i$是将物品i推荐给用户得到的“收益”。

  • DCG

直观的想法：“收益”越高的物品，在列表中的位置应该越靠前。

折扣累计收益（Discounted Cumulative Gain，简称DCG)在CG的基础上，加入了对物品位置的考虑：
$$
\mathrm{DCG}@N = \sum_{i =1}^N
\frac{
rel_i
}{
\log_2 (i + 1)
} \tag{11}
$$
DCG的另一种形式：
$$
\mathrm{DCG}@N = \sum_{i =1}^N
\frac{
2^{rel_i} - 1
}{
\log_2 (i + 1)
} \tag{12}
$$

DCG的第二种形式更常用。当$rel_i \in$ {0,1}时，公式(11)等价于(12)。

  • IDCG

理想的折扣累计收益（Ideal Discounted Cumulative Gain，简称IDCG）：在理想情况下，推荐列表中的物品应按照最终收益从高到低排序。
$$
\mathrm{IDCG}@N = \sum_{i =1}^{\left \vert REL_N \right \vert}
\frac{
2^{rel_i} - 1
}{
\log_2 (i + 1)
} \tag{13}
$$
其中，$REL_N$表示按照收益从高到低排序后的N个物品；$rel_i \in$ {0,1}。

  • NDCG

当采用DCG时，不同N下的结果无法直接进行比较。

为了解决该问题，可以对DCG进行归一化，得到归一化折扣累计收益（Normalized Discounted Cumulative Gain，简称NDCG)：
$$
\mathrm{NDCG}@N = \frac{DCG@N} {IDCG@N} \tag{14}
$$
$NDCG \in [0,1]$，其值越大，表示排序的质量越高。

当$rel_i \in$ {0,1}且采用留一法进行评估时，待测物品的收益rel=1，其理想位置j=1
$$
\mathrm{DCG}@N = \frac{1}{\log_2 (j + 1)} \\
\mathrm{IDCG}@N = \frac{1}{\log_2 (1 + 1)} = \frac{1}{\log_2 (2)}
$$
从而：
$$
\mathrm{NDCG}@N = \frac{DCG@N} {IDCG@N} = \frac{ \log 2 }{ \log(j + 1) } \tag{15}
$$

  • 示例

为了便于理解，下面举个例子（源自于维基百科）：

假设系统给用户u推荐了6部电影，推荐列表为：M1、M2、M3、M4、M5、M6，

用户u对这些电影的评分依次为：3, 2, 3, 0, 1, 2。

如果将用户的评分作为推荐该电影获得的收益，那么，该推荐列表的CG值为：
$$
\mathrm{CG}@6 = \sum_{i=1}^6 rel_i = 3 + 2 + 3 + 0 + 1 + 2 = 11
$$

i $rel_i$ $\log_2 (i + 1)$ $\frac{rel_i}{\log_2 (i + 1)}$
1 3 1 3
2 2 1.585 1.262
3 3 2 1.5
4 0 2.322 0
5 1 2.585 0.387
6 2 2.807 0.712

根据上表，计算得到：
$$
\mathrm{DCG}@6 = \sum_{i =1}^6
\frac{
rel_i
}{
\log_2 (i + 1)
} = 6.861
$$

理想情况下，推荐列表中的电影按照评分从高到低排序：3, 3, 2, 2, 1, 0。从而：
$$
\begin{align}
\mathrm{IDCG}@6 &= \sum_{i =1}^6
\frac{
rel_i
}{
\log_2 (i + 1)
} \\
&= \frac{3}{1} + \frac{3}{1.585} + \frac{2}{2} + \frac{2}{2.322} + \frac{1}{2.585} + \frac{0}{2.807} \\
&= 7.141
\end{align}
$$
因此：
$$
\mathrm{NDCG}@6 = \frac{DCG@6} {IDCG@6} = \frac{6.861}{7.141} = 0.961
$$

参考资料

  1. https://en.wikipedia.org/wiki/Discounted_cumulative_gain

发表于 | 更新于 | 分类于
字数统计: 383

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
阅读全文 »

发表于 | 更新于 | 分类于
字数统计: 228

2018年双十一期间，博主在京东入手了一台17版256G的MacBook Pro。由于一些外在原因，直到最近一段时间才真正使用上。经过最初的磨合，现在已经比较熟练了。这里总结下MacOS中的一些常用快捷键。

阅读全文 »