随着网络技术、存贮器技术和处理器技术的提高,整个世界的信息总量正以惊人的速度急剧膨胀,从事数据分析和处理的数据挖掘专家们所面对和处理的数据库或数据仓库的规模也随之不断增长。现有的数据挖掘算法在性能上难以满足处理海量数据库或数据仓库的要求。人们陷入了“数据越来越丰富但知识越来越缺乏”的困境。关联规则挖掘作为数据挖掘的核心任务之一,由于其任务本身的复杂性,使得从原始的大规模数据集中抽取一小部分样本,在样本集上寻找用户感兴趣的近似模式或规则的取样方法成为目前提高算法效率和可扩展性的一种简单、有效的现实可行方法。但是,取样方法必须在算法的效率和结果的精确性之间进行很好的折衷,如何确定合适的样本大小使得运行于样本集上的算法满足精确性的要求,即“关联规则挖掘的取样复杂性”的确定成为使用这一方法必须面对的关键、难解问题。本文主要针对“关联规则挖掘的取样复杂性”的确定这一难解问题,对与之相关的几个亟需解决的重要问题进行分析和研究。包括取样误差的量化模型和快速估计算法;提高取样精确性的方法;确定取样复杂性的新途径;关联规则挖掘取样复杂性PAC(Probably Approximate Correct)理论的本质;PAC理论下的最优取样复杂性;取样复杂性PAC理论在关联规则挖掘领域的进一步推广;关联规则挖掘取样复杂性相关结果的现实应用等等。本文的创新性研究工作主要包括以下几个方面。1)取样误差量化模型和快速估计算法:给出了一种有效的取样误差量化模型:取样误差量化三元组模型;给出了确定主误差产生范围的阈值松驰定理,并利用阈值松驰定理给出了一种主误差的快速估计算法:主误差区间估计法。实验结果表明,取样误差量化三元组模型可以灵活、有效地度量出由于取样所产生的误差,主误差区间估计法在取样误差的估计上具有快速、精确的优点。这一部分的研究为我们下一步优良的取样方法的设计和合理的评估样本集上所获结果的精确性奠定了基础。2)自适应多尺度取样算法:在信号处理中的多分辨分析理论和Shannon取样定理的启发下,给出了一种根据数据库特性在给定的精确性要求下动态选取样本大小的、自适应、在线、增量式、快速取样方法—多尺度取样,并将主误差区间估计法嵌入多尺度取样算法中。实验结果表明,多尺度取样方法在有限的几步内就可以快速地得到满足用户给定的精确性要求的样本大小和样本集,并且由于取样误差的主误差近似量化方法和快速估计方法的嵌入使得本文给出的多尺度取样算法可以克服已有的经典自适应取样算法(如自适应渐近取样算法)的诸多不足。3)取样集成模型和理论:首次提出利用取样集成方法提高取样精确性的新思想,给出了取样集成模型并借助机器学习中的Monte Carlo理论和Bias-variance分解从理论上分析了模型的有效性;给出了一种解决关联规则挖掘取样复杂性的全新方法:自适应