多关系数据挖掘是近年来快速发展的重要的数据挖掘领域之一。高效性和可扩展性一直是数据挖掘领域的重要研究课题。考虑多关系数据挖掘,这个问题尤为重要。多关系数据挖掘任务的复杂性对算法的性能提出了更高的要求。与传统的数据挖掘算法相比,多关系数据挖掘算法的搜索空间变得更复杂,更大。对于多关系数据学习算法,提高算法效率的主要瓶颈在于假设空间。针对以上问题,本文主要做了以下工作:首先,本文对数据挖掘理论、关系数据挖掘理论进行了研究,尤其是多关系数据挖掘的分类算法-多关系决策树算法及多关系数据挖掘的最新技术-元组传播技术进行了深入的研究。其次,本文提出了多关系决策树的改进算法。多关系决策树主要从两方面进行改进:1为了提高多关系决策树算法可扩展性,本文将虚拟连接元组传播技术应用到改进的多关系决策树算法中;2为了减少系统独自摸索的时间、减少系统搜索有用属性的时间和提高用户的满意程度,本文提出了在用户指导下完成分类任务的背景属性传递技术,并将该技术应用到改进的多关系决策树中。最后,本文对改进的多关系决策树算法进行了理论证明和实验验证。本文的实验主要利用了PKDD CUP’99中的Loan、Account、Transaction三个关系,采用两种方法对一般多关系决策树算法和改进的对关系决策树算法进行比较实验。第一种方法,固定三个关系的记录数不变,每个关系分别增加属性个数进行实验,第二种方法,固定三个关系中的属性个数不变,改变关系记录条数进行实验。通过上面的实验结果,本文研究认为,当改进的多关系决策树在搜索数据项未达到背景属性传递阀值时,改进多关系决策树算法的运行效率较低;当改进的多关系决策树在搜索数据项达到背景属性传递阀值时,改进的多关系决策树算法的效率相对很高且受属性个数增加(或记录数增加)影响较小。