如何在这个简单的数据集中找到最大的集群？

Question

我有关于用户及其兴趣的数据。有些用户比其他用户有更多的兴趣。数据如下所示。

如何找到具有最多共同兴趣的最大用户群？形式上，我正在尝试最大化（集群中的用户数量 * 集群中的共享兴趣数量）

在下面的数据中，最大的簇是：

正确答案

用户：[1,2,3]

兴趣：[2,3]

集群值：3 个用户 x 2 个共同兴趣 = 6

数据

用户 1：{3,2}

用户 2：{3,2,4}

用户 3：{2,3,8}

用户 4：{7}

用户 5：{7}

用户 6：{9}

如何找到具有最多共同兴趣的最大用户群？

下面是一个假设的数据生成过程：

import random 


# Generate 300 random (user, interest) tupples
def generate_data():
  data = []
  while len(data) < 300:
    data_pt = {"user": random.randint(1,100), "interest":random.randint(50)}
    if data_pt not in data:
      data.append(data_pt)
  return data

def largest_cluster(data):
  return None

更新：正如有人指出的，数据过于解析。在实际情况下，用户会多于兴趣。所以我更新了数据生成过程。

Answer 1

在我看来，这像是属于 NP-Hard 复杂性的组合优化问题 class，这当然意味着要为超过 ~ 的实例找到精确的解决方案是很棘手的30 个用户。

动态编程将是您想要使用的工具，如果您要为这样的指数搜索 space 问题找到一个可用的算法（这里的解决方案 space 就是全部2^n 个用户子集），但我没有看到 DP 在这里帮助我们，因为缺少重叠的子问题。也就是说，为了 DP 的帮助，我们必须能够在多项式时间内使用和组合更小的子问题的解决方案，成为一个整体的解决方案，我看不出我们如何才能解决这个问题。

假设您有一个 size=k 问题的解决方案，使用有限的用户子集 {u1, u2,...uk} 并且您想使用该解决方案在添加另一个解决方案时找到新的解决方案用户 u(k+1)。问题是在逐渐变大的实例中的解决方案集可能与之前的解决方案完全不重叠（它可能是完全不同的一组 users/interests），因此我们无法有效地组合子问题的解决方案以获得整体解决方案。如果不是尝试仅使用大小 k 问题的单一最优解来推理大小 k+1 问题，而是存储较小实例中所有可能的用户组合及其分数，您当然可以很容易地设置这些组的利益与新用户的利益相交，以找到新的最佳解决方案。然而，这种方法的问题当然是你必须存储的信息会随着迭代而加倍，从而产生一个指数时间算法，并不比蛮力解决方案好。如果您尝试将您的 DP 建立在逐渐增加兴趣而不是用户的基础上，您运行会遇到类似的问题。

因此，如果您知道您只有几个用户，则可以使用蛮力方法：生成所有用户组合，取每个组合的兴趣的集合交集，评分并保存最高分。处理更大实例的最佳方法可能是通过搜索算法使用近似解决方案（除非有我看不到的 DP 解决方案）。您可以迭代 add/subtracts/swap 个用户来提高分数并朝着最佳方向攀升，或者使用 b运行ch-and-bound 算法系统地探索所有用户组合但停止探索任何用户子集 b运行具有空兴趣交集的车（因为向该子集添加其他用户仍会产生空交集）。您可能有很多具有空兴趣交叉点的用户组，因此后一种方法实际上可以相当快地通过它 p运行关闭搜索的大部分 space，并且如果您运行它没有深度限制，它最终会找到确切的解决方案。

B运行ch-and-bound 会像这样工作：

def getLargestCluster((user, interest)[]):
  
  userInterestDict := { user -> {set of user's interests} } # build a dict

  # generate and score user clusters
  users := userInterestDict.keys() # save list of users to iterate over
  bestCluster, bestInterests, bestClusterScore := {}, {}, 0
  generateClusterScores()
  
  return [bestCluster, bestInterests bestClusterScore]

# (define locally in getLargestCluster or pass needed values
def generateClusterScores(i = 0, userCluster = {}, clusterInterests = {}):
  curScore := userCluster.size * clusterInterests.size
  if curScore > bestScore:
    bestScore, bestCluster, bestInterests  := curScore, curCluster, clusterInterests

  if i = users.length: return

  curUser := users[i]
  curInterests := userInterestDict[curUser]
  newClusterInterests := userCluster.size = 0 ? curInterests : setIntersection(clusterInterests, curInterests)

  # generate rest subsets with and without curUser (copy userCluster if pass by reference)
  generateClusterScores(i+1, userCluster, clusterInterests)
  if !newClusterInterests.isEmpty(): # bound the search here
    generateClusterScores(i+1, userCluster.add(curUser), newClusterInterests)

您也许可以进行更复杂的界定（例如，如果您可以计算出当前集群得分不会超过您当前的最佳得分，即使所有剩余用户都已添加到集群和兴趣交集保持不变），但是检查空的兴趣交叉点很简单。这适用于 100 个用户，50 个兴趣，最多约 800 个数据点。您还可以通过遍历 |interests| 的最小值来提高效率和|用户| （生成更少的递归calls/combinations）并且只是反映兴趣较低的情况的逻辑。此外，您可以用更少的 users/interests

获得更多有趣的集群

如何在这个简单的数据集中找到最大的集群？

How do I find the largest cluster in this simple dataset?

algorithm

graph

dataset

graph-algorithm