面向XBRL的DC-Apriori挖掘算法研究

曾志勇，闫亚丽

（1.云南财经大学信息管理中心，昆明　650221；2.云南财经大学信息学院，昆明　650221）

面向XBRL的DC-Apriori挖掘算法研究

曾志勇1，闫亚丽2

（1.云南财经大学信息管理中心，昆明650221；2.云南财经大学信息学院，昆明650221）

0　引言

XBRL是一种网络报告语言，全称为eXtensible Business Reporting Language，它融合了计算机技术与企业财务会计准则，该语言是在XML语言基础上扩展而来。XBRL有自己的技术规范和分类标准来定义文档的语法格式，数据之间的关系，运算方法等，并根据技术规范和分类标准生成实例文档将数据展示出来，形成可阅读的文件形式，供用户分析使用。它可以降低用户的使用成本，提高数据的使用率，提高客户的服务准确率，也可以跨平台使用，不受任何应用程序的限制。XBRL提供了静态数据转变为动态数据的途径，不仅使数据搜集更加流畅，而且让信息搜寻人员的搜索、分析更加快速准确，在财政，金融等社会领域和企业内部有着广泛的应用。

由于XBRL独特的网络语言报告形式，XBRL语言特定的表示方法，并且它的使用不受任何应用程序的限制，并且有统一的标准格式，这些特点方便了数据挖掘技术的应用，提高了数据挖掘的共享度以及精确度，完成了数据在计算机程序之间的集成，极大地方便了用户的使用，进一步提高了数据挖掘的效率。而关联规则是数据挖掘技术中的一个比较重要的分类，它在一个比较大的数据库中发掘不同项目之间的一些相关关系，也就是说把那些频繁出现的项集从数据库中发掘出来。自从在上个世纪90年代，Agrawal和他的同事在处理市场上购物篮的问题时提出了关联规则算法Apriori后，世界上有非常多的科研人员就该算法提出了改进，但在XBRL数据格式上的研究还不多。

本文首先在XBRL数据集上实现Apriori算法，并通过实验来验证其不足，然后再实现DC-Apriori算法，并对这两种算法在频繁项集的生成效果上通过实验进行验证。

1　传统Apriori算法

Apriori算法的主要思想是：给定一个交易数据集合，根据指定的最小支持度和最小可信度，挖掘数据之间的关联规则。一般来说，Apriori算法的挖掘过程分为两个内容：

（1）挖掘出事务数据库中所有的频繁项集，也就是说，在事务数据库中，所有支持度大于最小支持度的项集都要能够挖掘出来。

（2）在生成频繁集的基础上，生成所有的关联规则。也就是说，利用第一步生成的频繁集，挖掘出可信度大于等于用户指定的最小可信度的规则，找出不同项之间的关联规则。

作为一种挖掘布尔关联规则频繁项集的算法，Apriori算法使用逐层搜索的迭代方法，通过K-频繁项集来搜索（k+l）-频繁项集。Apriori算法首先找出频繁1-项集的集合，用于产生频繁2-项集集合，然后再使用频繁集合来产生频繁集合，如此下去，一直到不能够再找到频繁k-项集为止。

对于XBRL数据的关联规则挖掘，由于其半结构化的特点，所以难以直接使用传统的高级语言实现，而XQuery以其简单支持多种表达式和构造函数等特点，得到了很多人的应用，因此本文将其作为XBRL数据挖掘算法的实现工具。

2　DC-Apriori算法

由于需要扫描整个数据库，支持度大于最小支持度的候选频繁k项集才可以入选频繁项集k，所以Apriori算法的计算时间很大一部分都是用在计算频繁项集的支持度上。在频繁项集中的每一个项都需要计算支持度，而且每次都需要读取数据库。因此通过降低对整个数据库的扫描次数以及扫描数据库时对每个数据项所做的比较次数就可以获得一个运行效率比较高的算法。

鉴于此，可以在算法中通过加入删除计数（Delete Counter）的方式来减少扫描数据库的次数以及扫描数据库时对每个数据项所做的比较次数，我们称该种算法为DC-Apriori。在该算法中，对每一个候选项集，只需对数据库进行一次扫描就可以了。然后通过删除那些不能生成频繁项集的项的方式来去除数据的冗余，从而提高运行效率。

在改进的删除计数DC-Apriori算法中，寻找频繁项集的思想是：通过第一次数据库扫描，统计出所有只包含一个元素项集出现的概率，然后找出概率大于等于最小支持度的项集，由两部分项集组成频繁项集 。从第二次数据库扫描开始，对频繁项集的项进行循环计算，直至最高维数项集生成为止。

在循环计算频繁项集的过程中，第k步时，在上一层生成的频繁K-1项集基础上生成候选K项集。在频繁K-1项集的生成过程中，要对所有该候选集中的项进行统计，得到每一个项所出现的次数。对于其他项，如果它的计数小于K-1则表明包含项的项集已经对生成的频繁项集不再有任何作用，删除该项，从而减少了由该项参与生成的项集组合。然后再对新生成的K维频繁项集进行检测，查看所有的K-1维频繁项是否都已经在K-1维频繁项集中。如果有频繁项没有被包含，就要删除该频繁项，从而得到一个只包含K维频繁项集的候选频繁项集。

得到k维候选频繁项集后，扫描事务数据库D的每一个事务，如果该事务中包含有候选频繁项集中的项，则保留该项事务，否则删除该事务。在每生成一次高纬度的频繁项集时，都会删除一些事务和频繁项集，从而减少下一维度的事务扫描I/O的开销，直至生成最高维度的项集，则数据库中的事务记录量降至最少，由此可以提高算法的计算效率。

带有删除计数的DC-Apriori算法的伪代码可以描述如下：

输入：事务数据库D；最小支持度$minsupport。

输出：D中的频繁项集L。

3　实验结果

实验的硬软件环境如下所示：①硬件配置：酷睿i5 2.5G双核CPU，4G内存。②操作系统：Win2000。③数据库：X-Hive6.0/DB。④编译环境：JDK 1.6.7。

为了测试对XBRL实例文档的数据挖掘的支持以及验证改进后的Apriori算法通过XQuery实现后的数据挖掘效率，我们采用了互联网上上市公司披露XBRL实例文档组成的数据库做为数据集，分别进行了以下两组实验：

（1）针对包含有不同事务数量的数据库，在最小支持度、最小信任度一样的情况下，测试两种算法的运行时间。

表1　不同事务数的运行时间

图1　有不同事务数目数据集的挖掘效率

通过图1可知，两种算法的运行时间上，针对同数量的事务数据库，在数据量大于15000条时，DC-Apriori算法的运行时间要比Apriori算法减少了一半左右。由此可知，DC-Apriori算法针对大规模的数据库处理时有着较好的优势。

（2）针对包含有不同最小支持度，在同一数据库的条件下，测试两种算法的运行时间。

表2　不同支持度的算法运行时间

通过图2可知，总体上来讲，针对不同的支持度，Apriori算法的运行时间都要比DC-Apriori算法要长，而且DC-Apriori在不同的支持度下的运行效率比较稳定，没有随着支持度不同而在运行时间上出现大幅度的变化。Apriori算法在支持度比较低的情况下，运行时间比较长，随着支持度的增加，运行时间会出现一些比较大的变化，算法不太稳定。

4　结语

从上节的实验数据结果来看，通过XQuery实现DC-Apriori算法对XBRL文档进行关联规则数据挖掘是可行的。针对时间方面的对比来看，改进后的算法运行时间有了明显提高，该算法在对XBRL文档挖掘中运行时间有了明显的改善。

图2　相同事务数目不同支持度的挖掘效率

［1］Amnon Meisels，Michael Orlov and Tal Maor.Discovery Associations in XML Data［C］.Proceedings of the Third International Conference on Web Information Systems Engineering（Workshops），Singapore，2002.

［2］许渊.面向xbrl的数据挖掘［J］.中国管理信息化（综合版），2005（10）：45-46.

［3］姚靠华，洪昀.XBRL层次结构与财务信息数据挖掘［J］.会计之友，2009，1：60-62.

［4］亓文娟，晏杰.数据挖掘中关联规则Apriori算法.计算机系统应用［J］，2013，04：121-124.

XBRL；Association Rules；DC-Apriori Algorithm

Research on DC-Apriori Algorithm Facing XBRL

ZENG Zhi-yong1，YAN Ya-li2

（1．The Information Management Center，Yunnan University of Finance and Economics，Kunming 650221；2．The Information Department，Yunnan University of Finance and Economics，Kunming 650221）

1007-1423（2015）26-0027-04

10.3969/j.issn.1007-1423.2015.26.007

2015-07-28

2015-08-15

XBRL作为一种基于XML的可扩展性商业报告语言，目前已广泛应用于财务系统中。因企业财务数据越来越多，利用数据挖掘方法挖掘出我们需要的信息显得极为重要。实现一种面向XBRL的DC-Apriori挖掘算法，实验表明：在X-Hive数据库中采用DC-Apriori算法进行XBRL关联规则挖的方法是行之有效的，并且挖掘效率高于传统Apriori算法的效率。

XBRL；关联规则；DC-Apriori算法

教育部人文社会科学研究青年基金（No.10YJCZH004）、云南财经大学校科研基金重点项目（No.YC10A003）

曾志勇，男（汉族），贵州贞丰人，教授，博士，研究方向为数据挖掘

闫亚丽，女（汉族），山东菏泽人，硕士，研究方向为数据挖掘

XBRL is a kind of extensible business reporting language which based on XML，it has been widely used in the financial system.More and more enterprise financial data bring us to use the method of data mining to dig out the important information we need.Puts forward a DCApriori algorithm facing XBRL，the experiment shows that using DC-Apriori algorithm in X-Hive to excavate XBRL data is feasible and effective，and the efficiency of DC-Apriori algorithm is higher than Apriori algorithm.