关于itemcf的topk问题，我们看下Mohammad Khabbaz的paper《TopRecs: Top-k Algorithms for Item-based Collaborative Filtering》：
介绍
现代信息系统的items数增长很快。对普通用户来就，浏览大量collections并发现合适感兴趣的item很重要。推荐系统可以帮助用户发现个性化兴趣它们可以利用用户评分来做出预测。大多数流行的推荐会使用CF。CF方法会输入一个巨大的稀疏矩阵（它包含了在items上的用户评分），接着通过在candidate items上预测它的未知评分，来为current user或active user输出最相关的items。大多数CF的研究主要关注提升预测的accuracy。很明显，在accuracy之外，可扩展性(scability)也是很重要的一点，因为在当今推荐系统中用户数和items数增长很快。举个例子，Google News这样的系统每天都有上百万用户，每秒都会增长许多news feeds数。Netflix和Amazon则具有大量items和users。新的ratings、items、users会不断被添加到ratings matrix中，并需要对top-k推荐做出影响。为所有users、或者登陆的active user重复计算top-k items的列表开销是很大的，因此需要高效的top-k算法。
CF的最流行方法是itemCF。它可以提供高质量的top-k结果。它的主要思想是：计算一个similarity matrix，相应的entries对应于pairwise item相似度（Person相关系数是一种流行选择）。为active users从头到尾计算推荐开销很大，因此，CF-based推荐通常会预计算好item-wise相似度，并以一种可快速检索的方式存储它们。根据该方法，预测active user (\(u_i\))在item (\(v_j\))上的得分的任务包含了以下steps：
- 1.为\(v_j\)寻找N个最相似的items（被\(u_i\)评分过），这被称为\(v_j\)在\(u_i\) profile中的N个最近邻。
- 2.基于在这N个items上的用户评分，通过相似度计算一个加权平均
一旦item scores被预测，那些带有最高预测得分的items会提供服务给用户。寻找top-k items的高效算法是项大挑战。在经典top-k settings中，对于m个features每个feature上的items得分可以从m个score-sorted lists中得到。这个问题的挑战是：设计一种可以访问最小数目items的top-k算法。该挑战可以通过TA/NRA算法族以及它的许多后代变种来解决。对比起经典的settings，在item-based CF中寻找top-k会有两个主要挑战：
- (1) 我们需要处理：每个candidate item的聚合得分必须通过来自一个不同的lists集合(set)的entries来决定。这是因为：在一个给定user profile中，每个candidate item的N个最相似items可能不同
- (2) 加权平均并不是一个单调聚合函数（monotone aggregate function），该特性会在经典top-k算法中常使用. 在top-k算法中有一些工作是使用非单调聚合函数的[10,18,21]，据我们所知，在top-k问题上还没有工作是使用非单调聚合函数来解决lists的多个集合的组合。
我们的目标是，设计一种可扩展的CF方法，它仍具有已知CF的accuracy。我们展示了一种基于将TA/NRA思想扩展到CF框架的直接方法，它需要非实时的预处理以及存储需求，否则会导致算法像naive算法一样不能访问尽呆能多的entries。因而，我们提出了一种新方法：它会通过两步操作（probe和explore）抽取CF中的核心计算逻辑。Probe是identifying的过程：为一个给定candidate item聚合N个lists；explore是finding的过程：在聚合的lists中寻找top-k items进行推荐。我们的方法会通过使用一个相似度阀值（similarity threshold）来让probe过程更高效。我们提出了一种probabilistic cost-based方法，将我们top-k算法的整体期望开销表示成一个关于相似度阀值的函数，并通过最小化cost来决定阀值的最佳值。
我们在核心的itemCF之上提出了一种可扩展的推荐系统，架构包含以下层（见图1）：
- (i) 数据层（Data layer）: 包含了user/item rating matrix
- (ii) 中间层（Intermediate layer）: 由item-item matrix组成，需要让similarity matrix时刻保持最新
- (iii) 应用层（Application layer）: 在中间层数据之上运行的高效运行topk算法。该层会使用相似度阀值(通过cost-based最优化得到)来调用probe操作，并通过explore操作寻找top-k items
图1
top-k算法可以独立于中间层（intermediate layer），并可以访问中间层最新的数据结构。我们提出了一个two-phase top-k算法。在第一阶段，我们会基于相似度值计算一个阀值。该阀值以这样的方式进行寻找：最大化（最小化）相似度值更大（更小）的items的概率，接着该阀值会介于items的N个最近邻之间。在第一phase后，相似度矩阵的大部分会被过滤，size问题会极大缩减。第二个phase会使用剩下的值来计算要预测的ratings。我们会定义一个目标函数，它是两个phases的期望cost的一个上限，会寻找关于threhold的最优值来最小化该cost。我们会使用概率分布来建模相似度矩阵，以便进行概率分析。我们提出了一种高效算法来寻找top-k推荐。我们的贡献如下：
- 1.为itemCF提出了一种分层系统。
- 2.提出了两种naive算法，作为baseline来校准算法效果。
- 3.我们展示了基于TA/NRA算法扩展的方法
- 4.为itemCF设计了一种新的top-k算法
- 5.根据运行时间和top-k结果质量来评估算法
2.相关工作
ItemCF和可扩展性：User-CF算法会基于N个最近邻用户(对该item评过分)来预测未知评分. 它需要计算和维护一个n x n的user-user相似度矩阵。用户数n通常大于items数m。Item-CF可以克服这个缺限。除了对可扩展性改进外，它会寻找pairwise相似度来产生更好的accuracy。在ItemCF中，一个active user在一个candidate item上的rating会基于与该用户在该candidate item相似的N个items上的rating进行预测。
top-K算法：topK算法被广泛研究。大多数相关工作构建在经典的TA/NRA算法之上。这些算法假设有一个单调聚合函数，以及一个关于多个列表的集合，在这之上执行聚合是事先知道的。对比这些算法，在我们的问题中，面临着两个主要挑战：
- i) 我们的聚合函数不是单调的(monotone)
- ii) 列表集合中被聚合的值是不固定的，可能会随着item间相互变化
据我们所知，许多最近工作表明，通过处理不同列表集合来聚合分值的解决非单调聚合函数的问题，在这之间没有发表过。这些情况下，主要思想是定义对于未见item（unseen objects）分值的一个上界，以及在top-k items得分上的一个下界。当前者不再大于后者时，该算法会停止。在本文中，会采用一种类似TA／RNA的方法来处理会变化列表集合中的聚合分值，。作为对比，我们提出了一种非常不同的算法来计算top-k items。
3.先决条件与Naive算法
在CF中，数据被表示成：
- R：稀疏的\(n \times m\)矩阵
- \(r_{ij}\)：为entry（表示在第i个user上对第j个item的评分(rating)），值采用\(\lbrace 1, 2, \cdots, C \rbrace, C>1\)来表示
主要挑战是：在R中预测missing ratings。此后，我们使用\(r_{ij}\)来表示第i个user在第j个item上已存在评分（exsiting ratings)。
- \(u_i\)：表示第i个user(row)。注意，从行为角度看，我们可以使用row \(u_i\)表示第i个user（列也如此）
- \(v_j\)：表示第j个item(column)
- \(r \in u_i\)：表示一个在user \(u_i\)的row上的已存在评分（existing rating）
- \(\hat{r}_{ij}\)：来做为active user \(u_i\)在一个candidate item \(v_j\)上的未知评分(unknown rating)的预测值。
- \(\mu_i\)：作为被\(u_i\)评分过的items数目
- \(\mu\)：表示被任意user评分过的items平均数目
在ItemCF中\(\hat{r}_{ij}\)的预测通常通过采用对\(u_i\)在\(v_j\)上最相似的N个items的ratings进行加权平均来求得。更正式的，我们可以使用以下公式，其中，\(N(v_j, u_i)\)表示由\(u_i\)评分的与\(v_j\)最相似的N个items的集合(其中：s为相似度)：
\[\hat{r}_{ij} = (\sum\limits_{x=1}^N s_{xj} \times r_{ix}) / ( \sum\limits_{v_y \in N(v_j,u_i)} s_{yj})\]…(1)
待研究的问题：给定一个active user \(u_i\)，高效找出具有最高预测评分(predicted rating)的top-k个items。我们称该问题为：寻找top-k推荐。对一个candidate item \(v_j\)预测rating需要找到由\(u_i\)评分过的与\(v_j\)最相似的N个items，接着将它们的ratings使用等式(1)进行聚合。
首个天然问题是，（在top-k算法的TA/NRA family中给出了主体），我们是否采用这些算法并设计高效的top-k算法来寻找top-k推荐。我们会在第4节解决该问题。在下一节，我们会叙述两个naive算法，它们作为top-k算法的baseline。出于便利，对于一个给定item \(v_j\)，\(v_j\)的N个最近邻（nearest neighbors）意味着N个最相似的items。
3.1 Naive-1算法
对于Naive-1和Naive-2算法，我们假设：pair-wise item相似度是已知的。对于\(u_i\)来说寻找top-k items的过程如下：
- 1.使用等式(1)为每个单独的candidate item \(v_j\)预测score。
这通常涉及到在\(u_i\)的profile中为\(v_j\)寻找N个最相似的items（例如：\(N(v_j,u_i)\)集合）。在一个关于m个items的list中找到具有最高值的K个items被称为“K-select problem”。这里，由于N的值在实际上范围是10-30，我们可以通过对该list做一个简单扫描、并维护一个优先级队列的方式来执行该任务。它的复杂度为\(O (m logN)\)。由于N通常是一个较小的数，该方法通常比一般K-select problem的最佳判断式算法（采用median of medians算法的复杂度为\(\Theta(10m)\)）更高效。
在为每个item（被\(u_i\)进行评分）找到N个最近邻后，将它们的ratings进行聚合，并计算\(\hat{r}_{ij}\)会花费\(O(N)\)的时间。因而，为单个candidate item预测得分的总开销为\(O(m logN + N)\)，为所有candidate items预测scores的开销为\(O(m^2 logN + mN)\)。实际上，通过只在由该user评分过的items list内为\(v_j\)搜索N个最近邻，可以提升性能，可以产生\(O(m \mu_i logN + mN)\)的开销，其中\(\mu_i\)是user \(u_i\)评分过的items数目。由任意给定user评分过的items的list所提供的该提升，会与评分矩阵（ratings matrix）独立进行存储。存储这样的信息会在存储上增加一个\(O(n\mu)\)的开销，其中\(\mu\)是由一个user评分过的items的平均数目。这与高效存储稀疏评分矩阵的开销同阶。我们假设可以访问该禾目禾已。
- 2.一旦每个item的score在前一步被计算，寻找具有最高scores的k个items的时间复杂度为\(O(m logk)\)
上述算法的总运行时间为\(O([\mu_i log N + N + logk] \times m])\)。
我们可以看到，为一个给定user寻找top-k items进行推荐，会涉及到两步：
- (i) 探测(Probe)：探测每个candidate item，以便寻找在user profile中的最相似的N个items。
- (ii) 探索(Explore)：探索关于candidate items的list，并计算它们的scores，接着寻找具有最高scores的top-k items。
step (ii)是必要的，以便寻找到具有最好得分的k个items。对于任意item，决定它的score需要我们知道与它最相似的N个items（由step(i)得到）。
probe阶段涉及到\(O(m\mu_i logN)\)个操作，而explore阶段需要\(O(m(logk + N)))\)个操作。实际上，N的值通常为30或更小。另外，logk通常不超过5, 主要原因是我们不希望用户被太多的推荐所淹没。在probe开销中\(\mu_i\)因子的存在，表明：Naive1算法的probe部分的开销占支配地位。例如，在MovieLens数据集中，有100w个ratings，\(\mu_i\)的平均值为165. 而在Netflix数据集中，100M的ratings、500k users，每个user的ratings平均数目为200.
3.2 Naive-2算法
我们定义了一个数据结构L，除相似矩阵外的一个有序列表集合(sorted lists)，每个item各一个。L的一个schematric如图2所示。
图2
\(L_i \in L\)表示与item \(v_i\)相关的list。
- \(L_i\)的elements：是形如(item_pointer, similarity)的pairs
- lists以非增的相似度(与\(v_i\))进行排序；
- item_pointer：是一个指向item所在的实际内存位置的指针，或者简化为item id。所使用的pointers在ratings matrix R以及相似列表L间的具有一个统一的items表示。
- \(L_{ij}\)：表示list \(L_i\)的第i个entry。\(L_{ij}\)的similarity表示对于\(v_i\)的第j个最相似item。
在L中的每个有序列表通过一个优先级队列进行维护，当item相似度随时间变化时有效更新。Naive-2的算法如下：
- 1.标记由\(u_i\)评分的所有\(\mu_i\)个items，时间复杂度为\(O(\mu_i)\)
- 2.对于每个candidate item \(v_j\)，从该list的头部头取\(L_j\)，直到发现N个已标记items。
- 3.计算聚合得分，并发现具有最高得分的k个items，时间复杂度为\(O(m log k)\)
总共有m个items，在它之外有\(\mu_i\)个被标记。因此，一个随机选中的item在该list上的任何位置都具有相同的概率。因此，我们可以假设：\(\mu_i\)个被标记的items被划分成\(\mu_i+1\)个buckets中。在每个bucket中的未标记items的期望数字是\((m-\mu_i)/(\mu_i+1)\)，待访问的items（直到N个已标记items被观察到）的期望数目是\(N + N \times \frac{(m-\mu_i)}{(\mu_i+1)}\) 或 \(O(Nm/\mu_i)\)，它会让算法的期望运行时间为\(O(mN(m/\mu_i) + m logk)\)。
。。。
4.经典的top-k算法
由于TA/NRA风格的算法依赖于：聚合函数是单调的，使用这样的算法的一个简单方法是：将该问题转化成单调聚合函数的问题。在等式(1)中，定义由用户\(u_i\)评分过的item \(v_x\)，对item \(v_j\)的预测评分的贡献是：\(e_j^x = s_{xj} r_{ix} / \sum_{v_y \in N(v_j,u_i)} s_{yj}\)。很容易看到预测评分是：\(\hat{r}_{ij} = \sum\limits_{v_x \in N_{(v_j,u_i)}} e_j^x\)。TA/NRA算法族可以被使用是因为：sum是一个单调聚合函数。然而，为了实现这一点，对于每个user \(u_i\)，我们需要维护N个lists来保储每个candidate item \(v_j\)的相似度以及它各自被\(u_i\)评分过的N个最近邻。为每个被评分过的candidate item发现N个最相似的items，需要\(O(nmN)\)的存储，这是过高的。除了存储之外，它还需要为每个用户的每个item保存一个最新时间的关于N个最近似的list，这在计算上开销很大。实际上，我们只需要为每个用户在进入到系统后找到top-k个推荐。
在该paper中，我们会探索高效的top-k算法，并满足高效存储需求。更特别的，最低存储需求是，评分矩阵 以及 pairwise item相似度。由于我们不想为每个user basis存储该信息，我们通常需要提供所有pairwise相似度。对应于每个item，会有一个由lists组成的数据结构，以非递增的顺序存储与其它items的相似度，可以高效存储相似度信息，我们假设：top-k算法可以访问该信息。该数据结构称为L，如图2所示，其中active user \(u_i\)会对前\(\mu_i\)个items评过分。我们会讨论关于TA/NRA算法的两种不同实现，并展示TA/NRA算法，可以访问之前通过其中一种naive算法可访问的所有entries。这可以为开发更高效算法做好准备。
更特别的，我们会考虑这样的算法：以相似度排序的方式访问在L中的columns的entries。一旦他们读取在一个candidate item和被该用户评过分的\(\mu_i\)个items其中之一个item之间的相似度时，他们会等待直到可以决定该评过分的item是否在candidate item是N个最近邻内。在为一个candidate item寻到到一个新neighbor之后，他们会更新上界和下界。最后，一旦top-k items得分的下界不低于部分观察到的objects的score的上界时，搜索停止。我们称这样的算法为“经典算法”。考虑两种类型的经典算法：
- (i) 这种算法可以以有序方式访问L的列，对应于\(u_i\)评过分的items
- (ii) 这种算法可以访问L的列，对应于candidate items
我们不要假设：被选中进行探测的lists的顺序，以及它们中的每个被探测到的depth。对于任意经典算法，存在许多示例：算法可以访问和naive算法一样多的实例。
定理1
假设CA表示以下方式的任意经典算法（Classic Algorithm）：它可以从L（对应被\(u_i\)评过分的items）的columns中读取相似度值。在这样的CA上的示例，可以访问同Navie-1算法一样多的entries。
证明：略
定理2
假设CA是以下方式的任意经典算法：可以从L的那些列（对应于candidate items）读取相似度值。在这样的CA上存在实例：可以访问如Naive-2一样多的entries。
证明：略
5. two-phase算法
在第3节中，在probe step和explore step之间，probe过程开销更大。为了实现高效的probe，我们描述了一个two-phase过程，它是我们的高效top-k算法的基础。
5.1 two-phase算法
使用第3节的数据结构L，并为每个entry增加第三个element进行扩展。我们将该新数据结构称为LP。特别的，在LP中，一个entry \(LP_{ij}\)是一个三元组，其中(item_pointer, similarity)与L中的elements相当。第3个element为prob，表示在L中任意比similarity高的其它相似度值的概率。尽管在相似度矩阵中提供了所有相似度，但读取所有相关相似度的开销很大。我们使用这样的概率可以在执行期间做出概率决策。做出这样的决策，我们可以避免对评过分的items的所有相似度进行访问（或者对candidate items的所有相似度），直到找到N个最近邻（与Naive-2算法不同）。因此，我们首先只读取candidate items的N个最相似items间的具有一个高概率的值（values）。通过寻到一个阀值(threshold)并使用上述prob values来过滤所有entries。接着，我们会在剩余的values间为candidate items寻找N个最近邻。对某些items来说，有可能缺失一些或所有最近邻。在这样的cases中，我们只会为这些items探测(prob)剩余的neighbors。很明显，选择合适的threhold值是很重要的。我们通过cost-based的最优化来这样做。
\(LP_{ij}.prob\)值可以通过对具有一个合适分布的similarity matrix建模来估计，后续会介绍。当我们使用一个分布来建模similarity matrix时，不需要提供prob values。作为替代，threshold可以被直接转化成一个相似度threshold。出于简洁性，我们假设给定这样的概率。注意：LP的elements包含的similarity值越高，prob值越低。因此，保持LP的列以similarities的非递增顺序进行排序，等同于保持以prob值的非递减顺序进行排序。
图3展示了two-phase过程，对于一个active user (\(u_i\))，他在/7的items评分。在图3中，最顶行的左侧，LP的三列对应于\(u_i\)评分过的items，所有entries都带有prob值低于\(\theta=0.19\)。这些lists只包含了余下的similarity值。假设N=2, 我们可以通过寻找\(v_4\)和\(v_7\)的neighbors来完成。我们已经发现\(v_5\)的最近邻，只需要在被\(u_i\)评分过的余下items（比如：\(v_1\)和\(v_2\)）上寻找第二个最近邻。对比起Naive-1算法，可以为3/4个candidate items减小以下执行时间：在被\(u_i\)评分过的所有\(\mu_i\)个items间，为所有items搜索最近邻所需要时间。然而，注意，该two-phase方法仍需要花费读取一些不相关similarity值的开销（比如：\(s_{13}\)）。另外，为\(v_5\)寻找其余neighbors需要至少需要对由用户评分过的\(\mu_i\)个items进行一次扫描。为了进行剪枝，强调选择合适的threshold很重要。我们可以通过cost-based optimization来完成。
图3也展示了Naive-2算法是如何工作的。在特别的示例中，被评分过的几乎一半items赞同该算法。然而，该two-phase过程只会访问11个entries，而Naive-2为16, Naive-1为12. 在该示例中，我们只是展示了该two-phase过程是如何工作的，以及需要为cost-base optimization选择概率阀值。5.2节中我们会比较two-phase算法与Naive-1和Naive-2的期望开销。
根据probe step的两个phases，expore step则用于寻找top-k items。
为了对two-phase过程与经典top-k算法进行比较。在图3中，假设\(v_5\)是top-k items之一。同时假设\(u_i\)已经为\(v_5\)的最近邻提供了最大评分(C)。在这种情况下，在部分观察到items（partially observed）的得分的上界不会被丢谟，直到我们已经发现\(v_5\)的最近邻。更进一步，我们需要确信，不存在在\(v_5\)和由该user评分过的其它items间的其它相似度，会大于已经读取的。这样做很容易验证，需要读取至多5个entries或者它需要读取超过3个entries，并执行严格的内务操作来跟踪：哪个lists已经被观察到每个item。最坏情况下，读取所有entries可能还要比Naive-1算法差。因此，我们提出一种新方法，它基于two-phase过程，并基于cost-based optimization来选择阀值(thhreshold)。
5.2 Prob值\(\theta\)的阀值选择
略