算法 - 根据最相似的偏好对用户进行分组
Algorithm - group users based on most similar preferences
我正在开发一个应用程序，其中根据用户回答的一组问题将用户分组为 'n' 个小组。这组问题是基本的多项选择，每个用户都必须回答每个问题。
这些是硬性标准：
- 每个组最多可以有 'n' 个用户
- 每个用户只能分配给 1 个团队
- 每组由相似度高的用户组成
我正在使用的数据集如下所示（我可以更改它）
{
1: { 1: 'a', 2: 'b', 3: 'a', 4: 'c' },
2: { 1: 'b', 2: 'c', 3: 'b', 4: 'd' },
3: { 1: 'b', 2: 'a', 3: 'c', 4: 'd' },
...
}
在我的第一次尝试中：我创建了一个函数，当给定一个初始用户时，return 一组用户按相似度排序。这工作正常，但不提供可靠的组。
在我的第二次尝试中：我试图定义一个较低和较高的精度。
然后我递归地遍历所有用户并将他们推到团队中，成员的加入相似度高于最高精确度。如果不是，我会在下一次迭代中调整精度。这给了我坚实的群体，但每个群体中的用户并不像它那样准确 should/could？是。
我现在正在研究实际算法，特别是 Gale-Shapely 算法
为了解决我的问题。然而，鉴于我是一名开发人员而不是数据科学家，我不知道细节。
非常感谢对我的问题提出任何建议或解决方案。
这是一个非常难的问题，但这里的形式化可能会对您有所帮助。
假设您有 N 个用户。您可以将它们视为 N 个节点的完整图，其中边 (i, j) 的权重是用户 i 和 j 的 "similarity"（例如常见答案的数量）。然后，您正在寻找将顶点划分为大小为 n 的组，以最大化分区内边缘权重，即分区 P maximizing
%3D%5Csum_%7Bi%3D1%7D%5Ek%20%5Csum_%7Bu%2Cv%5Cin%20P_i%7D%20w%5Cleft(%20u%2Cv%20%5Cright))
这可以证明与最小化分区间权重相同
此转换使您的问题归结为找到 (k, nu)-平衡图划分。这是一个难题，但是 Balanced Graph partitionning，Andreev 和 Räcke，ACM 2004 提供了一种近似算法及其详细的复杂性分析。
您可以将该算法与 nu 的松散值一起使用，得到一个近似答案，然后重新平衡用户以在每个组中准确地得到 n 个。这有望给出接近最佳的结果，但很难达到最佳状态。
我正在开发一个应用程序，其中根据用户回答的一组问题将用户分组为 'n' 个小组。这组问题是基本的多项选择，每个用户都必须回答每个问题。
这些是硬性标准：
- 每个组最多可以有 'n' 个用户
- 每个用户只能分配给 1 个团队
- 每组由相似度高的用户组成
我正在使用的数据集如下所示（我可以更改它）
{
1: { 1: 'a', 2: 'b', 3: 'a', 4: 'c' },
2: { 1: 'b', 2: 'c', 3: 'b', 4: 'd' },
3: { 1: 'b', 2: 'a', 3: 'c', 4: 'd' },
...
}
在我的第一次尝试中：我创建了一个函数，当给定一个初始用户时，return 一组用户按相似度排序。这工作正常，但不提供可靠的组。
在我的第二次尝试中：我试图定义一个较低和较高的精度。 然后我递归地遍历所有用户并将他们推到团队中，成员的加入相似度高于最高精确度。如果不是，我会在下一次迭代中调整精度。这给了我坚实的群体，但每个群体中的用户并不像它那样准确 should/could？是。
我现在正在研究实际算法，特别是 Gale-Shapely 算法 为了解决我的问题。然而，鉴于我是一名开发人员而不是数据科学家，我不知道细节。
非常感谢对我的问题提出任何建议或解决方案。
这是一个非常难的问题，但这里的形式化可能会对您有所帮助。
假设您有 N 个用户。您可以将它们视为 N 个节点的完整图，其中边 (i, j) 的权重是用户 i 和 j 的 "similarity"（例如常见答案的数量）。然后，您正在寻找将顶点划分为大小为 n 的组，以最大化分区内边缘权重，即分区 P maximizing
这可以证明与最小化分区间权重相同
此转换使您的问题归结为找到 (k, nu)-平衡图划分。这是一个难题，但是 Balanced Graph partitionning，Andreev 和 Räcke，ACM 2004 提供了一种近似算法及其详细的复杂性分析。
您可以将该算法与 nu 的松散值一起使用，得到一个近似答案，然后重新平衡用户以在每个组中准确地得到 n 个。这有望给出接近最佳的结果，但很难达到最佳状态。