代码之家 › 专栏 › 技术社区 › stagas

如何使用MySQL和PHP比较数字集并获得最相关的结果?

relevance comparison algorithm mysql php

2

stagas · 技术社区 · 15 年前

考虑一下:

set A: 1 2 3 4
set B:     3 4 5 6
set C:       4 5 6 7
set D: 1

我想将d与其余的比较,得到一组最相关的数字。结果应该是这样的:4(因为D与A有一个公共数,4在A中,也在B和C中),3(因为D与A有一个公共数,3在A和B中),2(因为D与A有一个公共数,2也在A中),然后5,6,7。

在php/mysql中,是否有一些有效的算法可以做到这一点?我不想重新发明轮子,而且数据库最终会有大量的集合。

2 回复 | 直到 15 年前

1

Community CDub 8 年前

在SQL中,我假设您有一个名为集合的表,其中有2列,元素为E,集合名称为S。

select e,count(*) as c from sets where s in
(select s from sets where e in (select e from sets where s='D') group by s)
group by e order by c desc

说明:

(select e from sets where s='D')

选择D组的元素。

(select s from sets where e in (select e from sets where s='D') group by s)

选择与先前选定的组具有共同成员的所有组。

然后从这些集合中选择所有元素,并按外观数量对它们进行排序(如 joel 建议)

2

joel.neely 15 年前

有一个例子不能给出完整的规范。例如,如果还包括集合,您的答案会有什么不同?

set E: 1 2 3
set F: 1   3

这将使3在具有非空交集的集合中成为最常见的值 D ?所以我的假设是:

给定目标集( D 在您的原始示例中):

“重叠集”(与目标集有非空交叉点的集)中的值与那些重叠集中的值更相关。
在语句1的约束下,相关性由出现的频率决定。

在您最初的示例中, A 与…重叠 D 所以宇宙1,2,3,4,5,6,7被划分为重叠1,2,3,4和不重叠5,6,7。数值频率为1:2、2:1、3:2、4:3、5:2、6:2、7:1。结合这些事实得出重叠频率1:2、2:1、3:2、4:3和非重叠频率5:2、6:2、7:1,从而产生顺序4、3、1、2,然后是5、6、7。(我注意到你没有给1指定相关性。如果经过深思熟虑,这可能是从最终排序中删除目标集值的最后一步。)

在我调整后的示例中,频率变为1:4、2:3、3:4、4:3、5:2、6:2、7:1。它给出重叠频率1:4、2:3、3:4、4:3和非重叠频率5:2、6:2、7:1,从而产生顺序1、3、2、4,然后是5、6、7。

此算法的伪代码为:

初始化 overlapping 和 universe 为空集和 frequency 为空哈希。

每一组 s 在集合中(除 t ,目标集):

2.1。集合 宇宙 对工会 S 和 宇宙

2.2。如果 S 与…相交 T 至少有一个元素:

2.2.1. Set `overlapping` to the union of `overlapping` and `s`

2.3。对于每个元素 e 在里面 S 以下内容:

2.3.1. If 'e' is a key in `frequency`

    2.3.1.1. Then increase the value (count) for `e` in `frequency` by 1
    2.3.1.2. Else initialize the value (count) for `e` in `frequency` to 1

集合 nonOverlapping 不同于 宇宙 和 重叠
对的元素排序 宇宙 以他们的价值观 频率 作为结果的第一部分。
在结果中附加 不重叠 ,也按其值排序 频率 .

(如果你确实打算 T 为了被淘汰,我会在第4步中做一个后处理步骤。)