5

假设我们有一家香水店，里面有 100 种不同的香水。

假设有 10,000 名顾客以每款香水一到五颗星的价格出现。

假设问题是：“如何最好地构建一包 5 种香水，以便 95% 的客户至少对其中一种给予 4 星以上的评价”

如何在算法上做到这一点？

注意：我可以看到即使问题没有正确形成；不能保证这样的结构甚至存在。在 2 个参数之间进行权衡。

注意：另外，（这使得香水类比变得有点人为），我们得到一个好的匹配还是三个好的匹配并不重要。所以 {4.3, 0, 0, 0, 0} 将等价于 {4.3, 4.2, 4.2, 4.2, 4.2} - 在这两种情况下，分数都是 4.3。

假设为了论证的目的，香水 0-19 是甜的，香水 20-39 是酸的，等等（sim. salt, 苦味，unami）

所以0-19之间会有非常高的互相关。

如果你用 100 个空间点来建模，那么 0-19 都会非常强烈地相互吸引，它们会形成一个集群。

同样，对于其他四种口味，您将获得 4 个其他集群。

因此，仅从一个指标中，我们就分离出了 5 种不同的口味。

但是这种技术会扩展吗？

π

PS 只是给出相关技术的名称会非常有帮助，因为这可以让我在谷歌上获取更多信息。因此，任何仅在行业接受的术语中重申问题的答案都会很有用！

4

2 回答 2

2

该算法应该找到问题的解决方案：

  1. 根据给予 4+ 评分的顾客数量订购香水
  2. 从列表中选择第一款尚未考虑的香水
  3. 从现在满意的客户中删除评级。
  4. 对包装中的香水 2 - 5 重复该过程。

必要时回溯以获得满足标准的选择。

于 2013-10-26T14:35:27.150 回答
1

真正的问题是 NP-hard，但您可以使用贪心算法：

  1. 让 C 成为您的全部客户。
  2. 为每种香水分配一个覆盖率，该覆盖率由 C 中对每种香水给予 4+ 的客户数量给出
  3. 按覆盖率降序排序。如果 C 为空且所有覆盖率都为零，则随机选择一种香水（实际上，如果 C 非零但 < 原始值的 5%，则满足您的要求）
  4. 从 C 中删除所有对刚刚选择的香水感到满意的顾客（不是评分）
  5. 从 2 开始重复，除非您已经有 5 种香水。

这会自动处理口味聚类：给甜味香水打高分的顾客将被投票最多的甜味香水满足，然后他将被从 C 中剔除，忽略他所有进一步的评分，算法将继续满足其他顾客。

此外，您应该注意到，即使您不能满足五种香水的要求（95%，4+），香水相似性将确保该算法最大化覆盖率和标记 - 所以您最终可能会得到，比如说， （93%，3.9）。

另外，假设 10% 的用户没有给出任何高于 3 的分数。您不可能 4-满足 95% 的客户，因为最多 10% 的客户可以满足 3-。您可能希望与实际上确实给出至少一个 4+ 评级的客户一起构建 C。

或者您可以更改算法，而不是您问题中的算法，决定使用背包：您想获得最高的累积评分。这也提高了客户对整体包装感到满意的可能性（因为几乎可以保证他非常喜欢一种香水，但他可能非常不喜欢其他四种）。

于 2013-11-04T07:46:24.783 回答