多采样策略下的强精度近似频繁模式挖掘

The approximate frequent patterns mining with tight guarantee extends the traditional frequent pattern mining. In some applications of big data, if the quality of hardware, timeliness of data and high operation cost are not available, the approximate mining with tight guarantee exchanges little controlled precision loss for a significant increase in efficiency. .This project studies a multi-sampling based approximate frequent patterns mining technique, which offers tight guarantee. It is proposed to solve two problems of the current techniques, which are the overestimation and inefficient estimation of sample size. (1) Firstly, the project studies the decoupling of data mining task. In approximate frequent patterns mining, the project creatively uses a fact that the solution space of a sub-knowledge of frequent pattern can be collapsed when another sub-knowledge is known, so the objects which needs to be approximated with tight guarantee can be reduced. (2) Then, the project studies the decoupling of the approximation with tight guarantee. Through setting specific sub-guarantee for every sub-knowledge of frequent pattern, many redundant guarantees can be avoided. (3) Finally, when estimating the sample size, the project creatively introduces the modelling of the conditional distribution of the knowledge to be mined under the condition of its approximate value, which adds a new method besides those relations between the scale of sample and the stability of frequency. The technology studied in the project can make the frequent pattern mining under big data really get rid of the high performance hardware dependence, the data scale timeliness dependence and the high operation cost dependence. It has high theoretical significance and application prospect, and can provide technical and theoretical support for information construction in a series of fields, such as national defense.

强精度近似频繁模式挖掘是频繁模式挖掘的延伸，其内涵为：在无法保证硬件条件、数据时效及运行成本的大数据应用中，以可控的微量误差换取挖掘性能大幅度提升。.项目研究多采样策略下的强精度近似频繁模式挖掘，以解决现有强精度近似对样本规模的过估计和估计效率低下问题。（1）首先，项目研究挖掘任务解耦，首次在近似挖掘中利用了频繁模式子知识间的解空间塌缩关系，避免了大量冗余的强精度近似对象。（2）其次，项目研究强精度近似解耦，针对频繁模式不同侧面分别设置精度需求，避免了统一精度下，大量冗余的精度要求。（3）最后，项目在估计样本规模下限中首次引入了近似值条件下的待挖知识分布建模，在样本规模与频率稳定性的关系外增加了新手段，降低了样本规模估计难度。项目所研技术可使大数据下的频繁模式挖掘真正摆脱高性能、数据时效及高运行成本的依赖。具有较高的理论意义及应用前景，能为国防等一系列领域的信息化建设提供技术及理论支撑。

采样是一种常用的大规模数据频繁模式（FP）挖掘技术。针对采样挖掘中结果质量的强精度理论保证问题，现有算法均在数学上保证随机样本中所有模式的支持度问题。然而，在实际挖掘过程中，算法所关心的仅仅是那些频繁模式。因此，对所有模式的支持度进行理论保证会导致极大的样本过估计。项目提出了一种多采样策略下的频繁模式挖掘算法（MSFP）。算法首先生成不带支持度的近似频繁项（AFI）集合，再利用AFI生成不带支持度的近似频繁模式（AFP*）。在生成AFI与AFP*的过程中，算法不对项和模式的支持度稳定性进行理论保证，进对其支持度相较于最小支持度的 >= 或 <= 关系进行理论保证。因此，项目可基于较少的样本将解空间中大量非频繁的模式剔除，获得AFI与AFP*。之后，项目基于贝叶斯统计思想估计样本规模，通过采样估计AFP*中模式的支持度，其中，项目将某一模式在数据集中的未知支持度视为随机变量，通过渐进采样，利用不断获取的先验知识更新其概率分布，以更好地在理论上限制其误差。实验表明，项目所研算法具有较高的可靠性与效率。