流式鲁棒子模覆盖算法的图集覆盖问题的研究

田 歌，王耀力，常 青，孙永明

（1.太原理工大学信息与计算机学院，山西晋中 030600；2.山西省林业科学研究院，山西太原 030000）

数据汇总是机器学习中的一个主要挑战，它的任务是从大型数据集中找到可管理大小的代表性子集。包括图像摘要、文档和语料库摘要、推荐系统和非参数学习等许多应用程序。获得数据汇总的一般方法是：首先选择数据元素的子集，然后对所选集合的“代表性”进行量化，以构成优化效用函数。通常，用于汇总的效用函数表现出子模性，即自然递减的收益性质[1]。换句话说，子模性意味着随着摘要中包含更多数据点，数据集中任何元素的增加值都会减少收益。因此，可以将数据汇总问题自然地归结为子模覆盖问题[2]。数据汇总通常采用集中式算法，但集中式算法对于大型数据集来说不切实际。因为顺序选择单个机器上的元素在速度和内存方面受到很大的限制。因此，为了大规模地解决上述子模优化问题，需要利用MapReduce式的并行计算模型，或借助于流算法[3]。

而在实际应用当中，应用程序往往受限于数据存储容量与数据存取速度等因素，流算法往往是其可行的选择。流算法来源于大数据。自1987 年以来，世界人均存储信息的能力每40 个月翻一番。算法面临着存储、通信、分析等挑战。流算法仅需存储少量可用数据，而且内存大小可以远小于输入数据的大小。流算法不仅可以避免对内存的大量随机访问，而且可根据当前数据及时提供数据预测，从而促进实时数据分析[4]。……