我建议您尝试以下方法。我没有数学证明它会产生绝对最佳的“分数”,或者其他“好度量标准”,但我相信它可能会帮助您,除非当然,情况需要您真正证明并找到最佳结果。
我不会说Python,但策略和随后的实现足够简单,甚至不需要伪代码来解释。虽然我会用很多话,但不是因为它非常复杂,而是为了清晰(我希望如此)。
您需要一种对矩阵进行对角化的方法,或者至少找到与最大特征值对应的特征向量。并非每种语言都本地提供这种方法。在C ++中,您可以使用Eigen库。在我用于测试的C#中,我连接了MathNet。在Python中,我不知道。对于对角化/特征向量设施的要求有限:矩阵始终是实数、对称的,所有元素都是正数。但是,尽管对角线元素至少与其行/列中的任何其他元素一样大,但该矩阵肯定不是“对角线优势”的。
您提出的问题可以抽象地表示为整数,而不是单词,这使得它更方便(对我而言...)来制定和实现(但否则,它是相当无关紧要的)。实际上,我们只需要您的“common_words”,因此100个整数[0..99],您只需将单词放入数组或列表中并使用其索引即可一次性设置单词和整数之间的映射。
顺便说一句:该策略可能比完全通用的整数问题更适合您的语言应用程序,因为我们基本上利用了成对相关性(如果有的话)在项(同一句子中的单词)之间,而三元组、四元组等的主导强相关性可能会使其效率降低(但我们将为三元组做一些事情)。显然,在格式良好的语言中,您期望存在相关性:“am”经常与“I”一起出现,而尽管“have”的总量可能比“has”多,但一旦您找到“he”,您可能更有可能在同一句子中获得“has”而不是“have”。等等。
需要一些定义。
NCommon是您的common_words中的元素数量(i.c. 100)。common_words是整数[0..NCommon-1]。
NMaxSet是您的问题限制(i.c. 20),最终可以使用的“单词”的最大数量。
F是一个过滤器:您使用它来定义哪些句子包含在某个集合中。最后,您必须调整您的过滤器,使F.Count不超过NMaxSet。
M(N)是一个NxN方阵;行和列索引在[0..N-1]中。
S(F)是满足过滤器F的句子集合(来自问题输入)。在此,“句子”始终是在[0..NCommon-1]范围内的整数集合,详见上文。同一句子中的重复单词无关紧要(问题描述),因此这种重复会从我们的整数句子中移除。
开始准备。
初始化一个矩阵MCommon = M(NCommon)。
创建包含所有common_words的FCommon过滤器。
过滤输入,删除句子中的重复单词。
这将产生一个句子集合S0 = S(FCommon),这是您的“真实”输入:所有不相关的内容都已被删除。
在接受句子到S0时,即时填充矩阵MCommon: {for (j in sentence): for(k in sentence): M(j,k)+=1}。
该矩阵是对称的,因此您可以只填写右上方三角形,然后在结束时将其反映到左下角三角形中。
扫描完成后,M[j,k]是包含j的"句子"中k出现次数的数量(反之亦然:矩阵是对称的)。
M[k,k]是S中所有句子中k的总计数。
M是(成对)相关矩阵,告诉您{j,k}组合在底层句子集S中出现的可能性有多大。
(始终如此,在处理这样的矩阵时:如果最终存在空列(因此也是行):
同时删除支持矩阵的相应条目,因为显然它不起作用。
从现在开始,我们将假定已经完成了这个步骤(除非另有说明),即矩阵中没有列/行为空。)
计算结果(主要方法,我们将在下面进行精化):
计算与最高特征值对应的MCommon的特征向量E: E是一个具有NCommon系数的数组(向量)。
设置NTarget=NSetMax
确定E中NTarget最大系数的索引,我们不关心它们的值,而是它们的索引。
将这些索引放在一起:它们定义了一个新的过滤器F(NTarget)。
通过新的过滤器运行S0,以生成STarget。
计算所有“单词”出现次数,找到它们的最小值: 这就是您的“集合质量”值。
例如,您可以通过计算相关的MTarget并扫描对角线值MTarget[k,k]来执行此操作。
这似乎涉及不必要的额外工作,因为您还计算了离对角线的元素,但我们将看到MTarget可以在后续精化中派上用场。
精化。
A) 我们需要验证删除过滤器F(NsetMax)中一个或多个项目,将其缩小到一些NTarget小于NSetMax的值,是否会获得更好的分数价值。
这需要一些小心:很可能删除两个(或3个,…)项目将改善分数,但删除它们中的任何一个都会恶化分数。
让我们首先(并且是相当合理的)尝试解决这个问题。
在生成STarget的同时,您还会像之前使用MCommon一样填充一个新矩阵MTarget(看到了吗,它很方便...)。大小为NTarget。
获取最大特征值的特征向量。确定最小系数。从过滤器中删除对应的索引。
再次过滤(当然,现在可以使用STarget集合作为输入),并计算分数。
如果更好:标记/记住。
无论如何(是否改进),都要以同样的方式继续,一次减少一个过滤器,直到没有任何东西。
B)人们可能预期,如简要解释的原因,在将过滤器进一步降低到NSetMax以下 - 一次一个 -
可能也在某种程度上适用于第一步,即我们通过一次大规模打击将F(NCommon)降低到F(NTarget = NMaxSet)。
为了适应这一点,我们可能希望从NCommon向下到NMaxSet进行步骤。为了不产生太多的计算开销,我们不会
采取大小为1的步骤,而是每次减少约10%或类似数量。
因此,在上面的II中,不要立即将NTarget设置为NSetMax,而是(例如)设置NTarget = 90。
构造相应的过滤器,将其应用于S0,给出S1,还要生成矩阵M1,获取其特征向量(最大特征值)。
重复:将NTarget设置为80、70、60等。在后期阶段,您可能会变得更加谨慎,将40降低到35、30、28、26......
在每个步骤中,您都建立并使用以前的结果,以最优化地利用大小和计算工作量的减少。
一直要监视是否始终使用相同的索引作为最大NSetMax(该算法部分的最终值)系数。
这将提供关于最终结果是否可靠的一些信息:预期的最终过滤器对算法路径的稳定性或不稳定性。
C)考虑情况,我们已将其减少到NSetMax,并调查是否应该进一步以一个接一个的方法进行减少。
(如果在接近NSetMax时您采用“一次一个”的方式,那么在(B)的最后阶段也可能适用。)
假设在算法的此阶段,在您的(第一个或稍后的)STarget集合中存在某些“单词”对,
删除这种特定对将改善事情,
而它们各自的特征向量中的任何一个系数都不是最小的。
我不确定这是否可能或甚至可能,但让我们看看如何处理它。
如果(您的)测试表明这是无关紧要的,则可以在最终实现中从算法中删除此功能。
假设我们有一些NTarget,以及相关的过滤器FTarget和矩阵MTarget。(过滤器中的项目('words')顺序始终等于矩阵中的行和列的顺序。)
从MTarget中,我们可以直接推断出如果我们从过滤器中删除第j个项目会发生什么。
当然,矩阵中的第j行和第j列变为空(全部为零)。
更有趣的是,M[j,k] 表示在包含项目j的所有句子中,项目k出现的次数。
因此,当消除所有j(通过将其从过滤器中删除)时,我们预先知道在结果新矩阵MReduced中,元素MReduced[k,k]将恰好减少该M[j,k]值。
(顺便说一下,这提供了一种确定要删除哪个项目的替代方法(如果您选择仅删除一个):最小{j:M[j,j]}是关联集S的分数,而从M中我们可以计算出在删除特定项目j后所有对角线元素将如何改变,从而预先计算出所得分数)
然而,在这里,我们想知道如果删除某对项目j和k,分数将受到影响。
现在,我们需要确定不是j或k的所有p的M[p,p]如何受到影响。
这不能直接从M中计算出来:
删除j会影响行k,虽然我们知道它将如何改变[k.k]和任何其他[p,p],但我们不知道它将如何改变[k,p],这是计算同时删除k也将如何改变[p,p]所需的。
顺便说一下,最终结果对于先删除j再删除k或反之亦然或同时删除两者应该没有影响。
为此,我们需要某种“导数”。
幸运的是,我们可以在不太费计算的情况下计算和处理它(假设NTarget已经相当小,大约20个左右)。
考虑与当前过滤器F相关的“reductionfilter”G(F;j),简单地定义为处理F但忽略其中的项目j。
使用G,我们按照通常的方式计算出“reductionmatrix”N(G),为方便起见,在讨论(和实现)中保持相同的大小(不删除空列/行)。
当然,在这样的N矩阵中,第j行和第j列为空。
其对角线元素将具有上述值(我们可以直接从M中计算出这些值)。
但是,现在我们还有所有由于删除j而导致的非对角线元素。
现在,我们可以从N(G{F;j})中确定如果我们同时删除项目k会发生什么,关于如何从当前矩阵获得预期分数,请参见上面的阐述。
因此,这允许计算删除一对{j,k}时的分数。
如果集合大小为20,则需要计算20个N(G(F;j))矩阵,这相对较小,我认为(现在你的句子集合也比最初变得更小了)。然后,对于20*19/2个唯一的对,计算其结果对-移除分数,并确定从筛选器中删除哪个对(而不是单个元素)。您可以动态比较它与“逐个减少”的减少方法,并根据具体情况做出选择以系统地减少过滤器以获得更好的得分。有很多方法来进行此比较。一个相对简单的方法是:先计算从一对开始,然后再计算单个的减少(总共3个元素)。将其与先删除单个,然后再删除一对进行比较。选择其中较好的,但仅执行第一步(单个或一对),并重复该过程。
请注意,使用这些“派生”的筛选器G、矩阵N和随后的预计算分数,您实际上引入了项目三元组之间的相关性:您确定在同时删除j和k时,所有{j,k,p}对于p的频率会发生什么。当然,这个想法可以扩展到包括四元组及以上,但(a)我不认为它实际上会帮助很多,(b)你走得越远,计算工作量就会增加得越快。我甚至怀疑在此处解释的“三元组”是否相关,但我不是语言专家,除了一些额外的编程工作外,没有什么主要缺点。
D)该策略的核心是依赖具有最大特征值的特征向量来指向随后过滤的相关项。当然,可能会出现两个或多个特征值“几乎”相同,并且相应的特征向量在分析它们的最大分量时可能指向完全不同的项目集。在这种情况下,值得“分支”,即选择其中一个,进行完所有工作,然后重新对其竞争者进行所有操作,并查看它们是否产生更好的结果。如果在解决问题的过程中遇到很多分支,就会出现问题。虽然这不太可能发生,但实现应该有一些策略来以实用的方式处理它。我建议您首先排除任何分支,但是监视“竞争”最大特征值的出现,以便向用户输出警告。或者,您可以实现这样的分支管理,但在程序认为“几乎相等”的情况下非常严格,或者在总共要研究的分支数量上设置某些限制,从而减少计算时间过长的机会。
由于时间不足,我只能在这里结束,希望我已经充分解释了想法以及需要考虑的一些细节和改进。
我还没有花时间为自己整理相关的“真实语言”句子作为输入,并测试那些句子。我在C#中编写了基本步骤,针对随机整数“句子”进行了测试,同时有一些偏见来强制某些“单词”比其他单词更频繁出现,但没有关注“句子”内“单词”之间的相关性。对我来说,结果似乎相当合理,但我没有时间对其进行深入分析。
考虑到我所使用的“随机”序列缺乏结构,而真正的语言预计会展示重要的成对相关性,该策略利用了这一点。我有很大的希望,您能看一下它可能是一个有用的东西。
[编辑]添加说明:在上面,我偶尔不小心谈到“j”,“k”等内容,我很抱歉。有时,“j”指的是某物的第j个条目(矩阵行,过滤器列表中的索引),有时它指的是(通常)过滤器中的相应值。例如,过滤器可能包含18个项目,编号(索引)为0..17,但它们的值始终与原始Common_words列表相关,因此它们可以是{3, 15, 29, 30, 31, 40,...}。然后,当它说“从过滤器中删除j”时,通常会意味着“从过滤器中删除第j个条目(该条目可能具有[0..NCommon-1]中的任何值)”。将过滤器应用于句子时,将过滤器中的值与句子中的值进行比较。我希望上下文 - 结合对推理线路的公平理解 - 总是清楚地表明真正的含义。
[编辑:一些测试结果]
我运行了我的C#实现,使用上述算法(或多或少地:大多数但不是所有的细化/细节被描述)以获得一些印象,看看它会产生什么。
作为输入,我选取了古登堡计划中的4本书(纯文本)。总共有27k个句子,380k个单词(20k个不同的单词),因此是一个相当小的样本。
从这个输入中确定的常用词列表以“the”,“of”,“and”,“to”…(按出现频率排序)开始。
该算法过滤了14个单词(“i”,“what”,“do”,“you”,“it”,“yes”等),以产生8个“集合质量值”的“最佳”结果(只有这些14个单词的139个句子被找到)。
由于我对只使用100个“常用单词”的假设感到怀疑,我预先允许了500个常用单词,而不是100个,果然在成功过滤的单词中,有4个频率编号超过100个(“yes”,“know”,“say”,“think”):“yes”例如,在所有输入中按出现顺序排序,如果您要根据“常用单词”进行排序,则可能是#224。