代码之家 › 专栏 › 技术社区 › Magnar Myrtveit

满足条件的子集选择算法

subset algorithm

Magnar Myrtveit · 技术社区 · 7 年前

当它被添加时。
解决方案(例如人力资源、医疗保健、控制等)。
工业(例如运输、能源、电子等)。
是否来自强势品牌。

现在我想选择一个子集的参考显示在我的主页上。引用应该随机选择,这样每次有人访问我的主页时它们都是不同的。同时,我希望选定的参考资料满足以下条件:

最近添加的参考文献被选中的概率更高。
行业应该多种多样。
参考资料是否来自强势品牌,应该有多种多样性。

如何创建这样的选择算法?

编辑2018-09-08

数据库结构

| Column           | Type   | Key type    |
|------------------|--------|-------------|
| ReferenceId      | int    | Primary key |
| AuthorName       | string |             |
| OrganisationName | string |             |
| Content          | string |             |
| AddedDate        | date   |             |
| SolutionId       | int    | Foreign key |
| IndustryId       | int    | Foreign key |
| BrandIsStrong    | bool   |             |
| RegionId         | int    | Foreign key |

解决方案

总体思路:为引用指定权重,并根据它们的组合权重选择引用。例如:

DateWeight 每一个参考。参考值越老,权重越低。
SolutionWeight . 对于每个迭代,减少指定的权重。最后,每个解决方案中都会有一个参考值 溶液重量 ,一个参考值略低 溶液重量 ,等等,如果您现在按递减顺序遍历所有引用 溶液重量 ,溶液的变化会很大。
按照第2步中的步骤操作,但对于行业而不是解决方案,我们称之为权重 IndustryWeight .
按照第二步做,但是对于强势品牌和非强势品牌,我们称之为权重 BrandWeight 而不是 溶液重量 .
RegionWeight 而不是 溶液重量 .
n 选择要在主页上显示的引用。例如,可以通过以下方式实现:
2. 一种迭代过程,其中在每次迭代中选择一个参考,每个参考的被选择概率与其组合权重有关。

2迭代选择

总体思路:遍历每个约束,一次选择一个引用。

Unselected 是尚未选定的引用集。
选择中最近的引用 .
对于每个解决方案,请在中选择一个随机引用 未选定 ,属于该解决方案。
对于每个行业,请在中随机选择一个参考 未选定 ,属于那个行业。
从强势品牌和非强势品牌中选择一个参考。
对于每个区域,在中选择一个随机引用 未选定 ,属于那个地区。
重复步骤2到6直到 n 已选择引用。

此解决方案的一个缺点是,如果其中一个约束包含许多选项(例如,如果不同行业的数量大于 n

三。调整重量

总体思路:对于选定的每个引用,减少指定给与选定引用具有相同特性的引用的权重。

为每个引用指定相同的权重。
使用加权随机选择选择参考。
使用与所选引用相同的解决方案减小所有引用的权重。
减少与所选引用具有相同行业的所有引用的权重。
如果所选参考来自某个强势品牌,则减少所有强势品牌参考的权重。如果所选的参考文献不是来自某个强势品牌,请减少所有非强势品牌参考文献的权重。
减小与选定参照具有相同区域的所有参照的权重。
重复步骤2至7直到 n

1 回复 | 直到 7 年前

Alex M 7 年前

我认为这主要取决于如何量化一个可接受的解决方案,以及如何定义诸如 There should be a variety in [...] . 当你的数据高度相关时,你还必须决定该怎么做:例如,如果大多数“强势品牌”参考来自一个“行业”,那么由于你希望代表多个行业,你的数据集中就只有一小部分“强势品牌”元素。那样的话你就不能两者兼得了。

假设您需要显示 n 页面上的项目。这是一个外部约束,可能由包含项列表的web元素的大小定义;其余的约束由您选择。

跳到 太长,读不下去了 在底部的部分跳过细节。

解决方案1:便宜且(通常)有效:100%随机

你可以选择 n 随机引用,并让宇宙决定哪些项目进入您的页面。如果您的数据大致均匀地分布在各个列上 n

现在这并没有解决问题

最近添加的参考文献被选中的概率更高

分开,这样我们可以做得更好一点

这是第一个解决方案的一个稍微修改的版本。在本例中,您沿着数据集进行迭代,从最新的“ReferenceId”开始,按照“ReferenceId”的降序进行。每一项都有一个概率 p n N n 元素,只需从顶部重新开始(或增加 p ).

在Java中,这看起来像:

for (Object item : items) {
    if (random.nextDouble() < p) {
        result.add(item);
    }
    if (result.size() == n) {
        break;
    }
}

但是如果你的数据不均匀分布(这可能是因为你在问这个问题),你不能仅仅依靠随机性来生成你的项目集。在继续解决方案3之前,请检查此解决方案是否适用于您。如果没有,

解决方案3:制定约束条件并试图满足它们,贪婪的方法

n 以满足有关全局数据集的要求。

你必须知道,由于你在调整每一个特定项目在最后一盘中被选中的几率,你可能无法真正做到这一点

每次有人访问我的主页,他们都不一样

所以你现在很平静,不一定总是有随机性和 n/10 在最后一个子集中与此列不同的元素”。将约束的状态评估为对函数“满意”或“不满意” (S, n, k) -> {true, false} 哪里:

S 是当前选定项目集
n
k 是列的基数

说“给定元素的当前子集,这个约束满足了吗?”。您还可以评估一个元素是否有助于满足约束,例如“给定元素的当前子集,如果添加此项,是否更接近于满足此约束?”。

Set 限制条件。满足约束后,将其从约束集中移除。

如果没有实现细节,您将得到如下结果:

for (Object item : items) {
    // every item still has some probability of being chosen or not
    if (random.nextDouble() < p && helpsSatsfyAtLeastOne(remainingConstraints, item, result, n)) {
        result.add(item);                       
    }
    for (/* Appropriate data structure */ constraint : remainingConstraints) {
        if (constraint.isSatisfied(result, n)) {
            constraints.remove(constraint);
        }
    }
    if (result.size() == n) {
        break;
    }
}
System.out.println("Unsatisfied constraints: " + remainingConstraints);

helpsSatsfyAtLeastOne(...) 如果您需要对某些约束进行优先级排序,或者只是让它不按特定顺序遍历约束,则可以强制执行约束的顺序。

这是一个贪婪的方法,你不能保证最终的结果将是100%完美。如果某些约束在最后仍然没有得到满足,那么尝试在约束中强制优先。

太长,读不下去了

这种方法很简单,应该给你够了

量化满足你的约束意味着什么(根据基数,表示 (列等)
按日期(最近)的降序迭代引用
每一项都有一个概率 p 被选中的感觉
1. 如果选择了某个项目(使用概率过程),请检查是否添加它增加了 someColumn ?). 如果是,则将其添加到结果。
2. 已添加(即“我是否 足够地 属于在我的结果中