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

曾志勇，閆亞麗

（1.云南財(cái)經(jīng)大學(xué)信息管理中心，昆明　650221；2.云南財(cái)經(jīng)大學(xué)信息學(xué)院，昆明　650221）

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

曾志勇1，閆亞麗2

（1.云南財(cái)經(jīng)大學(xué)信息管理中心，昆明650221；2.云南財(cái)經(jīng)大學(xué)信息學(xué)院，昆明650221）

0　引言

XBRL是一種網(wǎng)絡(luò)報(bào)告語(yǔ)言，全稱為eXtensible Business Reporting Language，它融合了計(jì)算機(jī)技術(shù)與企業(yè)財(cái)務(wù)會(huì)計(jì)準(zhǔn)則，該語(yǔ)言是在XML語(yǔ)言基礎(chǔ)上擴(kuò)展而來(lái)。XBRL有自己的技術(shù)規(guī)范和分類標(biāo)準(zhǔn)來(lái)定義文檔的語(yǔ)法格式，數(shù)據(jù)之間的關(guān)系，運(yùn)算方法等，并根據(jù)技術(shù)規(guī)范和分類標(biāo)準(zhǔn)生成實(shí)例文檔將數(shù)據(jù)展示出來(lái)，形成可閱讀的文件形式，供用戶分析使用。它可以降低用戶的使用成本，提高數(shù)據(jù)的使用率，提高客戶的服務(wù)準(zhǔn)確率，也可以跨平臺(tái)使用，不受任何應(yīng)用程序的限制。XBRL提供了靜態(tài)數(shù)據(jù)轉(zhuǎn)變?yōu)閯?dòng)態(tài)數(shù)據(jù)的途徑，不僅使數(shù)據(jù)搜集更加流暢，而且讓信息搜尋人員的搜索、分析更加快速準(zhǔn)確，在財(cái)政，金融等社會(huì)領(lǐng)域和企業(yè)內(nèi)部有著廣泛的應(yīng)用。

由于XBRL獨(dú)特的網(wǎng)絡(luò)語(yǔ)言報(bào)告形式，XBRL語(yǔ)言特定的表示方法，并且它的使用不受任何應(yīng)用程序的限制，并且有統(tǒng)一的標(biāo)準(zhǔn)格式，這些特點(diǎn)方便了數(shù)據(jù)挖掘技術(shù)的應(yīng)用，提高了數(shù)據(jù)挖掘的共享度以及精確度，完成了數(shù)據(jù)在計(jì)算機(jī)程序之間的集成，極大地方便了用戶的使用，進(jìn)一步提高了數(shù)據(jù)挖掘的效率。而關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘技術(shù)中的一個(gè)比較重要的分類，它在一個(gè)比較大的數(shù)據(jù)庫(kù)中發(fā)掘不同項(xiàng)目之間的一些相關(guān)關(guān)系，也就是說(shuō)把那些頻繁出現(xiàn)的項(xiàng)集從數(shù)據(jù)庫(kù)中發(fā)掘出來(lái)。自從在上個(gè)世紀(jì)90年代，Agrawal和他的同事在處理市場(chǎng)上購(gòu)物籃的問(wèn)題時(shí)提出了關(guān)聯(lián)規(guī)則算法Apriori后，世界上有非常多的科研人員就該算法提出了改進(jìn)，但在XBRL數(shù)據(jù)格式上的研究還不多。

本文首先在XBRL數(shù)據(jù)集上實(shí)現(xiàn)Apriori算法，并通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證其不足，然后再實(shí)現(xiàn)DC-Apriori算法，并對(duì)這兩種算法在頻繁項(xiàng)集的生成效果上通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1　傳統(tǒng)Apriori算法

Apriori算法的主要思想是：給定一個(gè)交易數(shù)據(jù)集合，根據(jù)指定的最小支持度和最小可信度，挖掘數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則。一般來(lái)說(shuō)，Apriori算法的挖掘過(guò)程分為兩個(gè)內(nèi)容：

（1）挖掘出事務(wù)數(shù)據(jù)庫(kù)中所有的頻繁項(xiàng)集，也就是說(shuō)，在事務(wù)數(shù)據(jù)庫(kù)中，所有支持度大于最小支持度的項(xiàng)集都要能夠挖掘出來(lái)。

（2）在生成頻繁集的基礎(chǔ)上，生成所有的關(guān)聯(lián)規(guī)則。也就是說(shuō)，利用第一步生成的頻繁集，挖掘出可信度大于等于用戶指定的最小可信度的規(guī)則，找出不同項(xiàng)之間的關(guān)聯(lián)規(guī)則。

作為一種挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，Apriori算法使用逐層搜索的迭代方法，通過(guò)K-頻繁項(xiàng)集來(lái)搜索（k+l）-頻繁項(xiàng)集。Apriori算法首先找出頻繁1-項(xiàng)集的集合，用于產(chǎn)生頻繁2-項(xiàng)集集合，然后再使用頻繁集合來(lái)產(chǎn)生頻繁集合，如此下去，一直到不能夠再找到頻繁k-項(xiàng)集為止。

對(duì)于XBRL數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘，由于其半結(jié)構(gòu)化的特點(diǎn)，所以難以直接使用傳統(tǒng)的高級(jí)語(yǔ)言實(shí)現(xiàn)，而XQuery以其簡(jiǎn)單支持多種表達(dá)式和構(gòu)造函數(shù)等特點(diǎn)，得到了很多人的應(yīng)用，因此本文將其作為XBRL數(shù)據(jù)挖掘算法的實(shí)現(xiàn)工具。

2　DC-Apriori算法

由于需要掃描整個(gè)數(shù)據(jù)庫(kù)，支持度大于最小支持度的候選頻繁k項(xiàng)集才可以入選頻繁項(xiàng)集k，所以Apriori算法的計(jì)算時(shí)間很大一部分都是用在計(jì)算頻繁項(xiàng)集的支持度上。在頻繁項(xiàng)集中的每一個(gè)項(xiàng)都需要計(jì)算支持度，而且每次都需要讀取數(shù)據(jù)庫(kù)。因此通過(guò)降低對(duì)整個(gè)數(shù)據(jù)庫(kù)的掃描次數(shù)以及掃描數(shù)據(jù)庫(kù)時(shí)對(duì)每個(gè)數(shù)據(jù)項(xiàng)所做的比較次數(shù)就可以獲得一個(gè)運(yùn)行效率比較高的算法。

鑒于此，可以在算法中通過(guò)加入刪除計(jì)數(shù)（Delete Counter）的方式來(lái)減少掃描數(shù)據(jù)庫(kù)的次數(shù)以及掃描數(shù)據(jù)庫(kù)時(shí)對(duì)每個(gè)數(shù)據(jù)項(xiàng)所做的比較次數(shù)，我們稱該種算法為DC-Apriori。在該算法中，對(duì)每一個(gè)候選項(xiàng)集，只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描就可以了。然后通過(guò)刪除那些不能生成頻繁項(xiàng)集的項(xiàng)的方式來(lái)去除數(shù)據(jù)的冗余，從而提高運(yùn)行效率。

在改進(jìn)的刪除計(jì)數(shù)DC-Apriori算法中，尋找頻繁項(xiàng)集的思想是：通過(guò)第一次數(shù)據(jù)庫(kù)掃描，統(tǒng)計(jì)出所有只包含一個(gè)元素項(xiàng)集出現(xiàn)的概率，然后找出概率大于等于最小支持度的項(xiàng)集，由兩部分項(xiàng)集組成頻繁項(xiàng)集 。從第二次數(shù)據(jù)庫(kù)掃描開始，對(duì)頻繁項(xiàng)集的項(xiàng)進(jìn)行循環(huán)計(jì)算，直至最高維數(shù)項(xiàng)集生成為止。

在循環(huán)計(jì)算頻繁項(xiàng)集的過(guò)程中，第k步時(shí)，在上一層生成的頻繁K-1項(xiàng)集基礎(chǔ)上生成候選K項(xiàng)集。在頻繁K-1項(xiàng)集的生成過(guò)程中，要對(duì)所有該候選集中的項(xiàng)進(jìn)行統(tǒng)計(jì)，得到每一個(gè)項(xiàng)所出現(xiàn)的次數(shù)。對(duì)于其他項(xiàng)，如果它的計(jì)數(shù)小于K-1則表明包含項(xiàng)的項(xiàng)集已經(jīng)對(duì)生成的頻繁項(xiàng)集不再有任何作用，刪除該項(xiàng)，從而減少了由該項(xiàng)參與生成的項(xiàng)集組合。然后再對(duì)新生成的K維頻繁項(xiàng)集進(jìn)行檢測(cè)，查看所有的K-1維頻繁項(xiàng)是否都已經(jīng)在K-1維頻繁項(xiàng)集中。如果有頻繁項(xiàng)沒(méi)有被包含，就要?jiǎng)h除該頻繁項(xiàng)，從而得到一個(gè)只包含K維頻繁項(xiàng)集的候選頻繁項(xiàng)集。

得到k維候選頻繁項(xiàng)集后，掃描事務(wù)數(shù)據(jù)庫(kù)D的每一個(gè)事務(wù)，如果該事務(wù)中包含有候選頻繁項(xiàng)集中的項(xiàng)，則保留該項(xiàng)事務(wù)，否則刪除該事務(wù)。在每生成一次高緯度的頻繁項(xiàng)集時(shí)，都會(huì)刪除一些事務(wù)和頻繁項(xiàng)集，從而減少下一維度的事務(wù)掃描I/O的開銷，直至生成最高維度的項(xiàng)集，則數(shù)據(jù)庫(kù)中的事務(wù)記錄量降至最少，由此可以提高算法的計(jì)算效率。

帶有刪除計(jì)數(shù)的DC-Apriori算法的偽代碼可以描述如下：

輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度$minsupport。

輸出：D中的頻繁項(xiàng)集L。

3　實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)的硬軟件環(huán)境如下所示：①硬件配置：酷睿i5 2.5G雙核CPU，4G內(nèi)存。②操作系統(tǒng)：Win2000。③數(shù)據(jù)庫(kù)：X-Hive6.0/DB。④編譯環(huán)境：JDK 1.6.7。

為了測(cè)試對(duì)XBRL實(shí)例文檔的數(shù)據(jù)挖掘的支持以及驗(yàn)證改進(jìn)后的Apriori算法通過(guò)XQuery實(shí)現(xiàn)后的數(shù)據(jù)挖掘效率，我們采用了互聯(lián)網(wǎng)上上市公司披露XBRL實(shí)例文檔組成的數(shù)據(jù)庫(kù)做為數(shù)據(jù)集，分別進(jìn)行了以下兩組實(shí)驗(yàn)：

（1）針對(duì)包含有不同事務(wù)數(shù)量的數(shù)據(jù)庫(kù)，在最小支持度、最小信任度一樣的情況下，測(cè)試兩種算法的運(yùn)行時(shí)間。

表1　不同事務(wù)數(shù)的運(yùn)行時(shí)間

圖1　有不同事務(wù)數(shù)目數(shù)據(jù)集的挖掘效率

通過(guò)圖1可知，兩種算法的運(yùn)行時(shí)間上，針對(duì)同數(shù)量的事務(wù)數(shù)據(jù)庫(kù)，在數(shù)據(jù)量大于15000條時(shí)，DC-Apriori算法的運(yùn)行時(shí)間要比Apriori算法減少了一半左右。由此可知，DC-Apriori算法針對(duì)大規(guī)模的數(shù)據(jù)庫(kù)處理時(shí)有著較好的優(yōu)勢(shì)。

（2）針對(duì)包含有不同最小支持度，在同一數(shù)據(jù)庫(kù)的條件下，測(cè)試兩種算法的運(yùn)行時(shí)間。

表2　不同支持度的算法運(yùn)行時(shí)間

通過(guò)圖2可知，總體上來(lái)講，針對(duì)不同的支持度，Apriori算法的運(yùn)行時(shí)間都要比DC-Apriori算法要長(zhǎng)，而且DC-Apriori在不同的支持度下的運(yùn)行效率比較穩(wěn)定，沒(méi)有隨著支持度不同而在運(yùn)行時(shí)間上出現(xiàn)大幅度的變化。Apriori算法在支持度比較低的情況下，運(yùn)行時(shí)間比較長(zhǎng)，隨著支持度的增加，運(yùn)行時(shí)間會(huì)出現(xiàn)一些比較大的變化，算法不太穩(wěn)定。

4　結(jié)語(yǔ)

從上節(jié)的實(shí)驗(yàn)數(shù)據(jù)結(jié)果來(lái)看，通過(guò)XQuery實(shí)現(xiàn)DC-Apriori算法對(duì)XBRL文檔進(jìn)行關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘是可行的。針對(duì)時(shí)間方面的對(duì)比來(lái)看，改進(jìn)后的算法運(yùn)行時(shí)間有了明顯提高，該算法在對(duì)XBRL文檔挖掘中運(yùn)行時(shí)間有了明顯的改善。

圖2　相同事務(wù)數(shù)目不同支持度的挖掘效率

［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的數(shù)據(jù)挖掘［J］.中國(guó)管理信息化（綜合版），2005（10）：45-46.

［3］姚靠華，洪昀.XBRL層次結(jié)構(gòu)與財(cái)務(wù)信息數(shù)據(jù)挖掘［J］.會(huì)計(jì)之友，2009，1：60-62.

［4］亓文娟，晏杰.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則Apriori算法.計(jì)算機(jī)系統(tǒng)應(yīng)用［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的可擴(kuò)展性商業(yè)報(bào)告語(yǔ)言，目前已廣泛應(yīng)用于財(cái)務(wù)系統(tǒng)中。因企業(yè)財(cái)務(wù)數(shù)據(jù)越來(lái)越多，利用數(shù)據(jù)挖掘方法挖掘出我們需要的信息顯得極為重要。實(shí)現(xiàn)一種面向XBRL的DC-Apriori挖掘算法，實(shí)驗(yàn)表明：在X-Hive數(shù)據(jù)庫(kù)中采用DC-Apriori算法進(jìn)行XBRL關(guān)聯(lián)規(guī)則挖的方法是行之有效的，并且挖掘效率高于傳統(tǒng)Apriori算法的效率。

XBRL；關(guān)聯(lián)規(guī)則；DC-Apriori算法

教育部人文社會(huì)科學(xué)研究青年基金（No.10YJCZH004）、云南財(cái)經(jīng)大學(xué)?？蒲谢鹬攸c(diǎn)項(xiàng)目（No.YC10A003）

曾志勇，男（漢族），貴州貞豐人，教授，博士，研究方向?yàn)閿?shù)據(jù)挖掘

閆亞麗，女（漢族），山東菏澤人，碩士，研究方向?yàn)閿?shù)據(jù)挖掘

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.