推荐系统多样性算法解析：从MMR思想到C++工程实现

1. 项目概述从一道机试题看推荐系统的核心挑战最近在技术社区里看到不少朋友在讨论华为OD的机试题目尤其是C卷里那道关于“推荐多样性”的题。作为一个在推荐系统领域摸爬滚打了多年的工程师我第一眼看到这个标题就觉得很有意思。这绝不仅仅是一道简单的编程题它背后触及的是现代推荐系统无论是电商、内容平台还是社交应用都在面临的一个核心痛点如何在保证推荐准确性的同时避免信息茧房给用户带来更丰富、更有惊喜感的体验这道题用“推荐多样性”作为考点非常精准。它考察的不仅仅是你会不会写C代码更重要的是你是否理解推荐系统的基本逻辑以及如何用算法思维去解决一个实际的业务问题。很多新手一提到推荐就只想到“用户喜欢什么就推什么”但真正的工业级系统远非如此简单。过度的精准推荐会导致内容同质化用户很快会感到厌倦平台生态也会失去活力。因此“多样性”不是一个可选项而是一个必选项。这道题非常适合两类朋友来深入琢磨一类是正在准备类似华为OD这类企业机试的求职者通过这道题可以窥见大厂对候选人算法和工程结合能力的考察点另一类是对推荐系统感兴趣想从零开始理解其核心概念的开发者。接下来我就结合自己多年的经验把这道题掰开了、揉碎了从问题本质、解题思路到C实现细节完整地走一遍。你会发现它不只是几行代码更是一套解决问题的思维框架。2. 核心需求解析什么是“推荐多样性”在动手写代码之前我们必须先把问题定义清楚。题目通常不会直接给出明确的数学公式而是以一个业务场景描述呈现。我们需要从中抽象出关键约束和目标。2.1 业务场景抽象典型的题目描述可能类似于这样假设有一个推荐系统已经为某个用户生成了一份初始的推荐物品列表比如20个商品或文章。每个物品都属于一个或多个类别例如数码、服饰、美妆、体育等。系统评估发现这份列表的“多样性”不足过于集中在某几个类别。现在我们需要设计一个算法对这个初始列表进行重新排序或筛选使得最终呈现给用户的Top N个物品比如前10个在满足一定相关性要求的前提下类别尽可能分散从而提升整体多样性。从描述中我们可以提炼出几个核心要素输入一个初始的物品列表vectorItem每个物品至少包含item_id物品ID和categories所属类别集合两个属性。通常还会有一个score字段代表模型预测的用户对该物品的喜爱程度点击率、购买概率等即“相关性分数”。目标输出一个新的物品列表通常是输入列表的一个子集或重排序结果要求这个新列表的“多样性”尽可能高。约束在提升多样性的同时不能过分牺牲整体的相关性。不能为了多样性把用户最可能喜欢的物品都排到后面去。2.2 多样性量化如何衡量“不一样”这是解题的关键。多样性不是一个模糊的概念需要有可计算的指标。常见的量化方式有类别覆盖度最终列表中所包含的不同类别的总数。总数越多通常认为多样性越好。但单纯追求数量可能让一些冷门类别里的低质量物品入选。类别分布均匀度计算最终列表中各类别物品数量的分布情况。理想状态是每个类别都有物品且数量相对均衡。可以用信息熵、基尼系数等指标来衡量。物品间相似度计算列表中每对物品之间的相似度基于类别、标签、内容特征等并求平均或最大相似度。相似度越低多样性越好。在机试这种有限时间和空间的场景下最常用、最直观的指标是基于类别的贪心优化。我们的目标可以具体化为从初始列表中按顺序挑选出K个物品使得这K个物品所属的类别集合尽可能大同时这K个物品的累计相关性分数尽可能高。这其实是一个多目标优化问题最大化类别数 vs 最大化总分数。我们需要一个策略来平衡二者。2.3 解题思路总览一个行之有效且易于实现的思路是“贪心优先级队列”。预处理读取初始列表按相关性分数score从高到低排序。这是我们保底的相关性基础。核心迭代选择我们准备一个最终的结果列表result。然后我们尝试从排序后的初始列表中按照某种“性价比”最高的原则依次选取物品放入result。“性价比”的定义这是算法的灵魂。一个物品的“性价比”可以定义为它能为当前结果列表带来的“多样性增益”与其“相关性分数”的权衡。如果一个物品的类别在当前的result中还没有出现过那么引入它的“多样性增益”就很大。如果一个物品的类别已经出现过了那么它的增益就较小除非它的相关性分数特别高。实现工具我们可以维护一个优先级队列最大堆堆中的元素是待选物品。堆的排序规则即优先级就是我们定义的“性价比”函数。每一轮我们从堆顶取出当前“性价比”最高的物品加入结果然后更新堆中剩余物品的“性价比”因为结果列表的类别状态改变了。这个思路清晰且时间复杂度可以控制在O(n log n)级别非常适合机试。下面我们就进入具体的C实现环节。3. 数据结构设计与算法实现详解有了思路我们就要用C把它精确地表达出来。良好的数据结构设计是算法高效且清晰的基础。3.1 定义核心数据结构首先我们需要定义物品Item结构体。为了处理一个物品属于多个类别的情况我们用vectorstring或unordered_setstring来存储类别。#include iostream #include vector #include string #include unordered_set #include queue #include algorithm using namespace std; // 定义物品结构体 struct Item { string id; // 物品ID double score; // 相关性分数假设为0-1之间的浮点数 vectorstring categories; // 物品所属的类别列表 // 构造函数方便初始化 Item(string i, double s, vectorstring c) : id(i), score(s), categories(c) {} };这里使用vectorstring存储类别是考虑到输入可能以列表形式给出。如果后续需要频繁判断类别是否存在可以将其转换为unordered_set以提高效率。3.2 贪心算法核心MMRMaximal Marginal Relevance思想我们采用的算法思想非常接近信息检索领域经典的MMR最大边界相关算法。其核心公式可以简化为MMR argmax [ λ * Score(i) - (1-λ) * max_similarity(i, Result) ]其中Score(i)是物品i的相关性。max_similarity(i, Result)是物品i与当前结果集Result中最相似物品的相似度。λ是一个权衡参数λ1时只考虑相关性λ0时只考虑多样性。在我们的场景中“相似度”可以用“类别是否重复”来简单衡量。如果物品i的某个类别已经在结果集中出现则相似度高否则低。我们可以做如下简化每一轮我们选择能最大化以下公式的物品优先级 θ * score (1-θ) * is_novel这里is_novel是一个0/1值表示该物品是否引入了新的类别即至少有一个类别不在当前结果集的类别集合中。θ是一个超参数例如0.7表示更偏向相关性。但这个简化版在实现上每一轮都需要遍历所有剩余物品计算is_novel效率不高。更工程化的做法是使用优先级队列动态更新。3.3 基于优先级队列的动态实现我们实现一个更高效的版本初始化一个最大堆优先级队列堆中每个元素是一个pair优先级分数, 物品索引。初始时每个物品的优先级分数就是其自身的score。维护一个集合selected_categories记录当前结果集中已出现的所有类别。每一轮循环 a. 从堆顶取出优先级最高的物品。 b. 检查这个物品计算它有多少个类别是selected_categories中没有的即新类别数量novel_count。 c. 如果novel_count 0说明它能增加多样性将其加入结果集并更新selected_categories。 d. 如果novel_count 0说明它不能增加新的类别此时我们有两种策略 *策略一直接丢弃简单地丢弃这个物品继续从堆顶取下一个。这可能导致高相关性的物品因类别重复而被永久丢弃不够公平。 *策略二惩罚后重排我们给这个物品的优先级分数一个大的惩罚例如减去一个固定值或乘以一个小于1的衰减因子然后将其重新插入堆中。接着继续从堆顶取下一个物品。这样可以给其他物品机会同时这个被惩罚的物品在后续轮次中仍有可能被选中如果它的相关性分数足够高。 策略二更加合理我们采用策略二。循环直到结果集数量达到K或者堆为空。这里有一个关键点当一个物品被重新插入堆时它的“潜力”已经变了因为它没能提供新类别所以它的优先级应该被降低让其他可能提供新类别的物品有机会上来。代码实现如下vectorItem diversified_recommendation(const vectorItem items, int K, double theta 0.7) { int n items.size(); if (n 0 || K 0) return {}; // 初始化将每个物品及其初始优先级即score放入最大堆 // 使用pair优先级分数, 物品索引 优先级分数大的在前 auto cmp [](const pairdouble, int a, const pairdouble, int b) { return a.first b.first; // 最大堆 }; priority_queuepairdouble, int, vectorpairdouble, int, decltype(cmp) pq(cmp); for (int i 0; i n; i) { pq.push({items[i].score, i}); } vectorItem result; unordered_setstring selected_categories; // 用于记录物品是否已被最终选中 vectorbool selected(n, false); while (result.size() K !pq.empty()) { auto [current_priority, idx] pq.top(); pq.pop(); // 如果这个物品已经被选中过由于重新入堆可能被重复处理跳过 if (selected[idx]) continue; const Item candidate items[idx]; // 计算该候选物品能带来的新类别数量 int novel_count 0; for (const string cat : candidate.categories) { if (selected_categories.find(cat) selected_categories.end()) { novel_count; } } // 计算当前候选物品的“综合得分”用于决定是否在本轮选中它 // 这里采用一个简单的线性加权综合得分 θ * score (1-θ) * 新类别比例 // 新类别比例 novel_count / candidate.categories.size() 防止类别多的物品占优 double category_novelty_ratio candidate.categories.empty() ? 0.0 : (double)novel_count / candidate.categories.size(); double combined_score theta * candidate.score (1 - theta) * category_novelty_ratio; // 定义一个阈值例如0.3。如果综合得分太低说明既没相关性又没多样性可以考虑严格丢弃。 // 但为了简单我们使用动态惩罚如果能带来新类别或者综合得分尚可则选中。 if (novel_count 0 || combined_score 0.3) { // 0.3是一个经验阈值可调整 // 选中该物品 result.push_back(candidate); selected[idx] true; // 更新已选类别集合 for (const string cat : candidate.categories) { selected_categories.insert(cat); } // 选中后堆中剩余物品的优先级需要更新因为selected_categories变了。 // 但为了效率我们不立即更新整个堆而是依赖下一轮pop时重新计算novel_count。 // 被选中的物品类别更新后其他物品的novel_count只可能减少或不变不会增加。 // 所以我们的算法是一种近似贪心但效率很高。 } else { // 未能选中给予惩罚后重新入堆 // 惩罚将优先级降为原score的一半或其他衰减因子 double new_priority candidate.score * 0.5; pq.push({new_priority, idx}); // 注意这里没有标记selected[idx]true所以它未来还可能被再次弹出评估。 // 但由于优先级降低了它需要等其他高优先级物品处理完后才有机会。 } } // 如果因为堆空而退出但结果未达到K可以考虑将剩余物品按原score排序补足极端情况 if (result.size() K) { // 收集未被选中的物品 vectorpairdouble, int remaining; for (int i 0; i n; i) { if (!selected[i]) { remaining.push_back({items[i].score, i}); } } // 按score降序排序 sort(remaining.begin(), remaining.end(), [](const pairdouble, int a, const pairdouble, int b) { return a.first b.first; }); // 补足到K个 for (int i 0; i remaining.size() result.size() K; i) { result.push_back(items[remaining[i].second]); } } return result; }3.4 参数选择与算法分析权衡参数thetatheta控制了相关性与多样性的权重。theta1退化为按纯相关性排序theta0则只考虑物品是否能带来新类别可能选出相关性很低的物品。通常需要根据业务反馈在0.5到0.8之间调整。在机试中如果题目没有明确要求可以设定为0.7或0.6。惩罚因子代码中对于未选中物品将其优先级降为原score的一半0.5。这个因子可以调整比如0.7惩罚轻一些0.3惩罚重一些。惩罚越重类别重复的物品越难被选中。阈值代码中设定了一个combined_score 0.3的阈值用于防止选中那些既无相关性又无多样性的“废品”。这个阈值需要根据score的分布来设定。如果score普遍在0.1以下这个阈值就不合适。时间复杂度每个物品最多被弹出和重新插入堆中常数次因为每次惩罚优先级都会降低。假设平均每个物品被处理c次则时间复杂度约为O(c * n log n)其中c是一个较小的常数。空间复杂度为O(n)。注意上述实现是一种工程上的近似优化并非严格的每一轮全局最优。严格的MMR需要每一轮都计算所有剩余物品与当前结果集的相似度复杂度是O(K * n * C)C是平均类别数对于机试可能过高。我们的方法通过优先级队列和惩罚机制在效率和效果之间取得了很好的平衡这也是面试官希望看到的“工程思维”。4. 完整代码示例与测试用例设计理论说得再多不如跑一遍代码来得实在。下面提供一个完整的、可编译运行的示例并设计几个有代表性的测试用例。4.1 完整可运行代码#include iostream #include vector #include string #include unordered_set #include queue #include algorithm #include iomanip using namespace std; struct Item { string id; double score; vectorstring categories; Item(string i, double s, vectorstring c) : id(i), score(s), categories(c) {} }; vectorItem diversified_recommendation(const vectorItem items, int K, double theta 0.7) { int n items.size(); if (n 0 || K 0) return {}; auto cmp [](const pairdouble, int a, const pairdouble, int b) { return a.first b.first; }; priority_queuepairdouble, int, vectorpairdouble, int, decltype(cmp) pq(cmp); for (int i 0; i n; i) { pq.push({items[i].score, i}); } vectorItem result; unordered_setstring selected_categories; vectorbool selected(n, false); while (result.size() K !pq.empty()) { auto [current_priority, idx] pq.top(); pq.pop(); if (selected[idx]) continue; const Item candidate items[idx]; int novel_count 0; for (const string cat : candidate.categories) { if (selected_categories.find(cat) selected_categories.end()) { novel_count; } } double category_novelty_ratio candidate.categories.empty() ? 0.0 : (double)novel_count / candidate.categories.size(); double combined_score theta * candidate.score (1 - theta) * category_novelty_ratio; if (novel_count 0 || combined_score 0.3) { result.push_back(candidate); selected[idx] true; for (const string cat : candidate.categories) { selected_categories.insert(cat); } } else { double new_priority candidate.score * 0.5; pq.push({new_priority, idx}); } } if (result.size() K) { vectorpairdouble, int remaining; for (int i 0; i n; i) { if (!selected[i]) { remaining.push_back({items[i].score, i}); } } sort(remaining.begin(), remaining.end(), [](const pairdouble, int a, const pairdouble, int b) { return a.first b.first; }); for (int i 0; i remaining.size() result.size() K; i) { result.push_back(items[remaining[i].second]); } } return result; } void printResult(const vectorItem items, const string title) { cout \n title endl; cout left setw(8) ID setw(10) Score Categories endl; cout string(40, -) endl; for (const auto item : items) { cout left setw(8) item.id setw(10) fixed setprecision(3) item.score; for (const auto cat : item.categories) { cout cat ; } cout endl; } unordered_setstring all_cats; for (const auto item : items) { all_cats.insert(item.categories.begin(), item.categories.end()); } cout 【总计 items.size() 个物品覆盖 all_cats.size() 个类别】 endl; } int main() { // 测试用例1基础功能测试 vectorItem all_items { {A, 0.95, {数码, 手机}}, {B, 0.90, {数码, 笔记本}}, {C, 0.88, {数码, 手机}}, {D, 0.85, {服饰, 上衣}}, {E, 0.82, {美妆, 口红}}, {F, 0.80, {体育, 篮球}}, {G, 0.78, {数码, 耳机}}, {H, 0.75, {服饰, 裤子}}, {I, 0.72, {美妆, 粉底}}, {J, 0.70, {体育, 足球}}, {K, 0.65, {家居}}, {L, 0.60, {数码, 相机}} }; cout 初始列表按score排序:; vectorItem sorted_by_score all_items; sort(sorted_by_score.begin(), sorted_by_score.end(), [](const Item a, const Item b) { return a.score b.score; }); printResult(sorted_by_score, 纯相关性排序 Top 10); int K 6; vectorItem result diversified_recommendation(all_items, K, 0.6); // 使用theta0.6 printResult(result, 多样性推荐结果 Top to_string(K)); // 测试用例2极端情况 - 所有物品类别相同 cout \n\n*** 测试极端情况所有物品同属一个大类 *** endl; vectorItem same_cat_items { {M1, 0.99, {手机}}, {M2, 0.97, {手机}}, {M3, 0.96, {手机}}, {M4, 0.95, {手机}}, {M5, 0.94, {手机}}, }; vectorItem result2 diversified_recommendation(same_cat_items, 3, 0.5); printResult(result2, 同类别多样性推荐 Top 3); // 测试用例3物品带多个类别 cout \n\n*** 测试多类别物品 *** endl; vectorItem multi_cat_items { {X1, 0.90, {科技, 编程}}, {X2, 0.88, {科技, 编程, 算法}}, {X3, 0.85, {生活, 美食}}, {X4, 0.83, {科技, 硬件}}, {X5, 0.80, {生活, 旅行, 摄影}}, }; vectorItem result3 diversified_recommendation(multi_cat_items, 4, 0.65); printResult(result3, 多类别物品推荐 Top 4); return 0; }4.2 测试用例设计与预期结果分析设计测试用例是验证算法鲁棒性的关键。基础功能测试使用包含多个类别的物品列表。预期结果是算法不会简单地选择分数最高的前K个如A, B, C, D, E, F因为A、B、C都属于“数码”大类。算法应该会从“数码”中挑选一两个最具代表性的高分物品如A然后优先选择其他类别的物品如D-服饰E-美妆F-体育最后再回头补充一些高分的“数码”类物品如G。这样最终列表的类别覆盖会更广。极端情况类别单一所有物品都属于同一类别。此时多样性增益为0算法应该退化为按相关性分数score从高到低选择。我们的算法中由于novel_count始终为0且combined_score完全由theta * score决定只要score不是特别低高于阈值0.3物品还是会按优先级初始为score被选中。但因为我们加入了惩罚机制未选中物品优先级减半可能会出现一些顺序上的微小扰动但总体趋势仍是高分优先。这个测试用于验证算法的退化情况是否符合预期。多类别物品测试一个物品属于多个类别如X2属于科技、编程、算法。这增加了算法的复杂度。当选中X1科技编程后selected_categories包含了科技和编程。对于X2它的新类别只有算法novel_count1其category_novelty_ratio 1/3 ≈ 0.333。如果X2的分数足够高它仍然可能因为带来了新类别算法而被选中。这测试了算法处理复杂类别关系的能力。运行上面的代码你可以直观地看到算法输出与纯按分数排序输出的区别理解多样性是如何被引入的。5. 性能优化与边界情况处理在机试或实际工程中除了核心逻辑正确面试官和考官同样看重代码的健壮性和效率。5.1 时间与空间复杂度优化我们实现的算法时间复杂度约为O(c * n log n)空间复杂度O(n)对于机试场景n通常在几百到几千是完全足够的。但如果n非常大例如百万级我们可以考虑以下优化类别集合的快速判断我们使用unordered_setstring来存储已选类别判断一个类别是否存在是O(1)操作这已经是很快的。如果类别是固定的、有限的枚举值例如只有几十个可以考虑用bitset位图来表示判断和插入操作都是O(1)且空间效率极高。避免重复计算在每一轮弹出物品时我们都遍历其所有类别来计算novel_count。如果物品平均类别数很多这可能成为瓶颈。一种优化思路是预先计算每个物品的类别集合unordered_setstring并缓存。但这样会增加空间开销。在机试中通常不需要此优化。优先级更新的优化我们的算法在选中一个物品后并没有立即更新堆中所有物品的优先级而是依赖下一轮弹出时重新计算。这是一种“惰性更新”虽然可能不是绝对最优但大大减少了每轮的操作。对于大规模数据这种近似是值得的。5.2 关键边界情况与防御性编程空输入或K值非法函数开头必须检查if (n 0 || K 0) return {};。K大于物品总数我们的代码最后一部分处理了这种情况当堆耗尽但结果未满K时会将剩余未选中的物品按分数排序补足。这是一个合理的降级策略。物品分数为负数或大于1题目通常假设分数在合理范围内如0-1。如果可能异常需要在读取数据时进行钳制clamp或过滤。类别列表为空代码中通过candidate.categories.empty()的判断来避免除以零错误。对于没有类别的物品其多样性增益为0。权衡参数theta和惩罚因子的影响在注释中应说明这些参数需要根据实际数据分布进行A/B测试调整没有银弹。稳定性当两个物品优先级完全相同时priority_queue的出队顺序是不确定的取决于底层实现。如果要求稳定排序即分数相同时按输入顺序需要在pair中加入原始索引作为第三比较要素。5.3 一个更简洁的“两阶段”实现思路对于机试如果时间非常紧张还有一个更取巧但也有效的“两阶段”实现更容易写对第一阶段保证多样性。遍历按分数排序的物品列表依次选取物品放入结果集但仅当该物品能带来至少一个新的类别时才选取。直到结果集大小达到K或者遍历完所有物品。第二阶段保证数量。如果第一阶段结束后结果集大小不足K则从剩余物品中即那些未能带来新类别的物品直接按分数从高到低选取补足到K个。这种方法的优点是逻辑极其清晰代码简单不易出错。缺点是第一阶段可能过于“贪婪”地追求新类别而忽略了一些分数极高但类别重复的物品。但在很多情况下这已经是一个很好的baseline方案。你可以将其作为备选方案或者在解释思路时提及。6. 从解题到面试如何展现你的思考深度如果你在机试或面试中遇到此类问题写出正确的代码只是第一步。如何向面试官阐述你的思考过程往往更能体现你的能力。明确问题本质首先说明你理解这不是简单的排序而是一个“在约束条件下固定列表大小K优化多目标相关性多样性”的问题。阐述算法选择解释为什么选择贪心算法MMR思想——因为这是一个NP-hard问题的有效近似解在效率和效果间取得平衡。提及“边际收益递减”的概念即越往后新增一个重复类别的物品带来的多样性收益越小。分析复杂度主动分析时间、空间复杂度并讨论其可扩展性。讨论参数与调优指出算法中的超参数theta, 惩罚因子阈值需要在实际业务中通过线上实验A/B测试来调整没有固定最优值。思考边界与扩展扩展性如果物品数量极大百万级可以提到分批处理、分布式计算如MapReduce的思路。多样性度量可以提及除了类别还可以考虑标签、作者、主题等多维度的多样性算法框架可以扩展。实时性如果推荐列表需要实时更新如用户交互后可以讨论增量更新的策略而不是每次都全量重算。业务结合最终参数的设定需要结合业务目标。是更看重用户点击率相关性还是更看重生态健康多样性这需要与产品经理共同决定。把这道题吃透你收获的不仅仅是一个机试的答案更是一套解决推荐系统多样性问题的通用思维模型和工程实现方法。在实际工作中无论是做搜索、推荐还是信息流排序这种平衡“准确”与“多样”、“短期收益”与“长期价值”的思想都是至关重要的。