0

问题：
我想通过将他/她的“兴趣”与所有其他人的兴趣进行比较，为特定用户推荐前 10 个最兼容的匹配项。我正在用户之间构建一个无向加权图，其中权重 = 两个用户之间的匹配分数。

我已经有一组 N 个用户：S。对于 S 中的任何用户 U，我都有一组兴趣 I。经过很长时间（一周？）我创建一个具有一组兴趣的新用户 U，并将其添加到S. 为了为这个新用户生成一个图表，我将新用户的兴趣集 I 与 S 中所有用户的兴趣集迭代地进行比较。问题在于这个“所有用户”部分。

我们来谈谈比较兴趣的功能。对一组兴趣 I 的兴趣是一个字符串。我正在使用 WikipediaMiner 比较两个字符串/兴趣（它使用 Wikipedia 链接来推断两个字符串的相关程度。例如，Billy Jean & Thriller ==> 高匹配，Brad Pitt & Jamaica ==> 低匹配等等）。我也问过一个关于这个的问题（看看是否有比我目前使用的更好的解决方案。

因此，上述功能花费的时间不可忽略，总的来说，当我们比较数千（可能是数百万？）用户及其数百个兴趣时，将花费大量时间。对于 100,000 个用户，我无法以这种方式在短时间内（<30 秒）进行 100,000 个用户比较。但是，我必须在 30 秒内给出前 10 条建议，可能是初步建议，然后在接下来的 1 分钟左右对其进行改进，计算改进的建议。简单地按顺序比较 1 个用户和 N 个用户太慢了。

问题：
请提出一种算法、方法或工具，我可以使用它来改善我的情况或解决我的问题。

4

3 回答 3

2

我只能想到一种解决问题的方法，因为以下内容的结果取决于利益之间相互关系的性质。

=>步骤：1正如你的标题所说。构建一个无向加权图，以兴趣作为顶点，将它们之间的加权匹配作为边。

=> 步骤：2 - 聚集兴趣。（最复杂的）

Kmeans 是一种常用的聚类算法，但基于 K 维向量空间。请参阅 wiki 以了解 K-means 的工作原理。它最小化所有集群的（每个点的距离总和 ^ 2 并说集群的中心）的总和。在您的情况下，没有可用的尺寸。所以尝试是否可以通过创建某种规则来应用最小化逻辑，对于两个顶点之间的距离，更高的匹配 => 更小的距离，反之亦然（wiki-miner 提供的不同匹配级别是什么？）。选择集群的平均值作为所选集中连接最多的顶点，页面排名听起来是“计算最连接的顶点”的好选择。

“配对计数 F-Measure”听起来很适合您的需要（加权图），请检查其他可用选项。

（注意：不断修改这一步，直到找到正确的聚类算法并找到正确的距离规则校准，没有找到聚类等。）

=>步骤：3 - 评估集群

从这里开始，它就像校准一些东西以满足您的需要。检查集群，重新评估：集群数量，集群间距离，集群内顶点之间的距离，集群大小，时间\精度权衡（比较最终 - 没有任何集群的匹配结果）转到：步骤 2 直到这次评估是令人满意的。

=>步骤：4 - 检查新的兴趣

遍历所有集群，计算每个集群中的连通性，根据高连通性对集群进行排序，对于排序前 x% 的集群，排序并过滤掉高度连通的兴趣。

=>step:5 - 匹配用户

使用步骤 4 中获得的兴趣反向查找所有用户的集合，比较两个用户的所有兴趣，生成分数。

=>step:6 - 除了上述之外，您还可以根据流量和内容将负载（多台机器可用于集群 machine-n 集群）分配到多个系统\处理器。

这个问题的应用是什么，预期的流量是多少？

找到新兴趣和“集群中的一组兴趣”之间的连接的另一种解决方案 C. Wiki-Miner 在一组 wiki 文档上运行，我称之为 UNIVERSE。

1：对于每个集群获取和维护（索引，lucene 可能很方便）UNIVERSE 中的“一组高相关文档”（我称之为 HRDC）。所以如果你有'N'个集群，你就有'N'个HRDC。

2：当新的兴趣出现时，为每个 HRDC 找到“与集群的连接”=“HRDC 中的兴趣命中率/UNIVERSE 中的兴趣命中率”。

3：对“Conectivity with Cluster”进行排序并选择高度连接的集群。

4：根据适合您的时间\精度权衡，将集群中的所有顶点与新兴趣或高度连接的顶点（使用页面排名）进行比较。

于 2013-01-10T21:15:50.570 回答
1

一个缺陷是您将算法复杂性建立在错误的事情上。真正的问题是您必须将每个独特兴趣与其他所有独特兴趣（以及该兴趣与自身）进行比较。

如果所有的兴趣都是独一无二的，那么您可能无能为力。但是，如果您有很多重复的兴趣，您也许可以通过以下方式加速算法。

  1. 创建一个图表，将每个兴趣与具有该兴趣的用户相关联。以允许快速查找的方式。

  2. 创建一个图表，显示每个兴趣与其他兴趣之间的关系，同时以允许快速查找的方式。

因此，当添加新用户时，会将他们的兴趣与所有其他兴趣进行比较并存储在图表中。然后，您可以使用该信息来构建具有相似兴趣的用户列表。然后需要以某种方式过滤该用户列表以将其降到前 10 名。

最后，将该用户及其兴趣添加到用户和兴趣图表中。这是最后完成的，因此具有最密切匹配兴趣的用户不是用户自己。

注意：可能有一些统计捷径，您可以这样做：A 与 B 相关，B 与 C 相关，C 与 D 相关，因此 A 与 B、C 和 D 相关。使用这些捷径可能需要更好地了解您的比较功能的工作原理，这有点超出我的专业知识。

近似解决方案：

我之前忘了提，但是你在比较用户或兴趣时看到的是更高维度的“最近邻搜索”。这意味着，对于精确的解决方案，线性搜索通常比数据结构更有效。因此，如果您需要更快，近似值可能是最好的方法。

为了获得一个快速的近似解（不保证它有多接近），您需要一个允许快速确定哪些用户可能与新用户相似的数据结构。

构建该结构的一种方法：

  1. 选择 300 个随机用户。这些将是 300 个集群的种子用户。理想情况下，您会使用最不密切相关的 300 个用户，但这可能不切实际，仍然可能明智的做法是确保无种子用户与其他用户的关系过于密切（作为比较的总和或平均值）其他用户）。
  2. 然后由每个加入其代表用户与其最匹配的集群的用户填充集群。
  3. 然后可以通过从该集群中挑选最密切相关的前 10 个用户来确定前 10 个用户。

如果您确保集群的数量和每个集群的用户始终非常接近 sqrt（用户数），那么您只需检查集群内的点即可获得 O(sqrt(N)) 的公平近似值。您可以通过将用户包含在其他集群中并检查每个集群的代表用户来改进该近似值。你检查的集群越多，你就越接近 O(N) 和一个精确的解决方案。虽然，可能没有办法说当前的解决方案与确切的解决方案有多接近。在检查超过总数的 log(sqrt(N)) 集群后，您可能会开始遇到递减的回报。这会让你进入 O(sqrt(N) log(sqrt(N)))。

于 2013-01-08T21:09:46.563 回答
0

几个想法...

不完全是图论解决方案。

假设一组有限的兴趣。为每个用户维护一个位序列，其中每个兴趣是一个位，表示用户是否有该兴趣。对于新用户，只需将比特序列与现有用户的比特序列相乘，然后找到结果中的比特数，即可了解他们的兴趣匹配程度。

于 2013-01-10T07:40:49.667 回答