面向数据集覆盖问题的优化算法研究

发布时间：2021-10-16 08:19

　　数据科学时代,基于某些数据集训练机器学习算法是常见的。通过调查或科学实验,可以前瞻性地收集到数据集。最近,已经认识到训练数据集只具有代表性是不够的,如果受训练的系统要很好地处理一些不太流行的类别,则必须包括来自这些类别的足够的例子,这便是数据集覆盖问题。本文在已有的处理数据集覆盖问题的方法的基础上,结合关联规则挖掘相关算法的思想,提出了获取MUP的优化算法,提高了获取MUP的运行效率;另外还提出了计算coverage算法面对数据稀疏问题以及位图过大、内存不足问题的解决思路,最后通过理论分析以及对实际数据集的综合实验,验证了获取MUP优化算法的优越性。 

【文章来源】：智能计算机与应用. 2020,10(06)

【文章页数】：7 页

【部分图文】：

3个二元属性的模式图

自顶向下算法利用单调性过滤掉部分子模式图，来减少获取MUP所消耗的时间，但是这个算法在它找到未覆盖模式前，需要遍历模式图中的已覆盖区域的节点，计算这些节点的coverage，它的运行时间取决于模式图中已覆盖区域的大小。因此，如果模式图中一大片区域都是已覆盖的，那么自顶向下的算法运行时间就很长，性能较差。1.2.2 自底向上算法(Pattern-Combiner)分析

自底向上算法参考频繁项集挖掘中从特殊到一般的思路，它自底向上地遍历模式图，同样用单调性来避免遍历整个模式图，一旦找到了一个已覆盖模式，就可以过滤掉这个分支。自底向上算法将模式图转化为一个森林，并通过相应的规则，来保证每个候选节点只生成一次，如图3所示。自底向上算法先遍历未覆盖区域的节点，所以如果模式图中大部分节点都是未覆盖的，那么该算法的性能较差。同时，由于它最开始需要通过倒排索引的方式计算第d层的各个节点的coverage，而对d-1层到第0层的节点的coverage，只需要根据其子节点得到。所以，自底向上算法适用于属性基数较小，且阈值较小(大部分节点都是已覆盖的)的情况。自底向上的算法对于属性基数较大的数据集，运行性能差。原因:(1)属性基数大，第d层的模式节点很多。(2)根据子节点计算自身的coverage，所以基数变大后每个节点的计算时间也会增加(可能造成严重哈希冲突)。对于属性个数多，属性基数小的数据集，使用自底向上的算法比较好，当然也得综合考虑阈值。


本文编号：3439462