Apriori算法改進(jìn)及其在資產(chǎn)管理中的應(yīng)用

鄭 斌

(福建江夏學(xué)院電子信息科學(xué)學(xué)院， 福州 350108)

企業(yè)資產(chǎn)管理工作涉及多種資產(chǎn)項(xiàng)目和資產(chǎn)數(shù)據(jù)，應(yīng)用數(shù)據(jù)挖掘技術(shù)挖掘資產(chǎn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則，從而為管理決策提供反映企業(yè)資產(chǎn)運(yùn)營(yíng)實(shí)際的數(shù)據(jù)信息，有助于企業(yè)實(shí)行科學(xué)決策，提高資產(chǎn)利用率，節(jié)約企業(yè)經(jīng)費(fèi)，提升企業(yè)經(jīng)濟(jì)效益。本次研究，結(jié)合軌道交通工程建設(shè)單位資產(chǎn)數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的需要，對(duì)Apriori算法進(jìn)行了優(yōu)化。

1 關(guān)于數(shù)據(jù)挖掘的關(guān)聯(lián)算法

1.1 Apriori算法簡(jiǎn)介

Apriori算法是關(guān)聯(lián)規(guī)則挖掘中的經(jīng)典算法，為基于兩階段頻集思想的遞推算法。該算法的基本思想是：首先，應(yīng)用描述的方法找出所有的頻繁項(xiàng)集(即所有支持度大于最小支持度的項(xiàng)集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣)，由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則；然后，應(yīng)用關(guān)聯(lián)規(guī)則挖掘出頻繁項(xiàng)集中每個(gè)大于等于最小可信度的項(xiàng)集。

Apriori算法的實(shí)現(xiàn)過(guò)程是：首先對(duì)數(shù)據(jù)庫(kù)進(jìn)行全集掃描，將包含所有項(xiàng)為n階的項(xiàng)集作為初始值；然后在此項(xiàng)集中進(jìn)行i階迭代，直至項(xiàng)集為空，得到i階的候選項(xiàng)集Ci；接下來(lái)繼續(xù)在數(shù)據(jù)庫(kù)中掃描，獲得相對(duì)應(yīng)的支持?jǐn)?shù)，找到Ci中大于等于最小支持?jǐn)?shù)的i階項(xiàng)集[4]。該算法的偽代碼如下：

輸入：數(shù)據(jù)集D以及最小的支持度min_up

輸出：最大的頻繁項(xiàng)集Ii，事務(wù)t0=D

1)I1=D

2)for(i=2;Ii-1≠φ;i++)

3)Ci=Apriori(Ii-1)

4)while(t∈D)

5)Ct=subset(Ci,t)

6)while(C∈Ct)

7)C.sup++

8)Ii={C∈Ck|C.sup≥min.up}

Apriori算法的優(yōu)勢(shì)是：在支持度較低的情況下，掃描數(shù)據(jù)庫(kù)的次數(shù)較少，空間復(fù)雜度較低。它的缺點(diǎn)是：會(huì)產(chǎn)生大量的候選集，需要多次迭代掃描數(shù)據(jù)庫(kù)，從而導(dǎo)致搜索速度降低，占用過(guò)多的內(nèi)存空間。

1.2 Apriori算法的改進(jìn)

針對(duì)Apriori算法的不足對(duì)其進(jìn)行改進(jìn)。首先將數(shù)據(jù)挖掘的研究對(duì)象劃分為n個(gè)數(shù)據(jù)規(guī)模的部分，然后將挖掘得到的結(jié)果進(jìn)行合并?；玖鞒虨椋?/p>

1)將要挖掘的數(shù)據(jù)劃分為n個(gè)部分；

2)對(duì)每一個(gè)模塊部分都進(jìn)行頻繁項(xiàng)目集，存儲(chǔ)在一個(gè)頻繁項(xiàng)目集中；

3)將存儲(chǔ)的頻繁項(xiàng)目集進(jìn)行合并，形成全局候選的頻繁項(xiàng)目集；

4)針對(duì)全局的頻繁項(xiàng)目集掃描數(shù)據(jù)庫(kù)，計(jì)算該頻繁項(xiàng)目集的實(shí)際支持度，從而實(shí)現(xiàn)對(duì)頻繁項(xiàng)的確定。

改進(jìn)后的算法具有如下特點(diǎn)：

第一，在第一次掃描數(shù)據(jù)庫(kù)的時(shí)候就生成一組頻繁項(xiàng)目集。以這些可能的頻繁項(xiàng)目集為基礎(chǔ)來(lái)確定數(shù)據(jù)庫(kù)的實(shí)際支持度，進(jìn)而得到所需的最終頻繁項(xiàng)目集數(shù)目，并獲取最可能存在的關(guān)聯(lián)規(guī)則。

第二，將數(shù)據(jù)庫(kù)中的劃分為n個(gè)部分，首先將每個(gè)部分都產(chǎn)生一個(gè)頻繁項(xiàng)目集，然后再將這些頻繁項(xiàng)目集合并為一個(gè)全局候選頻繁項(xiàng)目集。這種方式在信息量增加迅速的情況下，能夠盡可能地降低頻繁項(xiàng)數(shù)量對(duì)數(shù)據(jù)挖掘效率的影響，但不能降低對(duì)數(shù)據(jù)庫(kù)掃描的次數(shù)，即當(dāng)頻繁項(xiàng)目集的最大值長(zhǎng)度為K，則需要對(duì)數(shù)據(jù)庫(kù)掃描K次。

第三，把要挖掘的數(shù)據(jù)劃分為n個(gè)部分(子模塊)，對(duì)各部分的每個(gè)事務(wù)都添加一個(gè)屬性，并記錄該事務(wù)所包含的項(xiàng)目數(shù)。

2 資產(chǎn)管理中的數(shù)據(jù)挖掘

資產(chǎn)管理數(shù)據(jù)往往來(lái)自多個(gè)部門(mén)，數(shù)量龐大而繁雜。比如城市軌道交通工程建設(shè)單位，其資產(chǎn)管理涉及的資產(chǎn)數(shù)據(jù)包含：設(shè)備采購(gòu)與管理部門(mén)購(gòu)買(mǎi)和維護(hù)設(shè)備的有關(guān)數(shù)據(jù)，土建部門(mén)組織各種施工產(chǎn)生的相關(guān)數(shù)據(jù)，拆遷部門(mén)開(kāi)展各種拆遷項(xiàng)目產(chǎn)生的有關(guān)數(shù)據(jù)，運(yùn)營(yíng)移交部門(mén)在各個(gè)階段進(jìn)行資產(chǎn)移交產(chǎn)生的數(shù)據(jù)[1]，等等。要給管理和決策層提供可靠的數(shù)據(jù)信息，就需要對(duì)資產(chǎn)數(shù)據(jù)進(jìn)行挖掘分析。

2.1 資產(chǎn)數(shù)據(jù)庫(kù)設(shè)計(jì)

根據(jù)軌道交通工程建設(shè)單位對(duì)資產(chǎn)數(shù)據(jù)分析的需要，設(shè)計(jì)資產(chǎn)數(shù)據(jù)庫(kù)時(shí)，確定資產(chǎn)、用戶、資金共3個(gè)主題域維度，并以資產(chǎn)主題為核心?？紤]到隨著軌道交通行業(yè)的快速發(fā)展，對(duì)資產(chǎn)數(shù)據(jù)分析的需求也在不斷變化，且資產(chǎn)數(shù)據(jù)量也會(huì)逐步增加，設(shè)計(jì)了2級(jí)粒度數(shù)據(jù)層次，即詳細(xì)數(shù)據(jù)和高度綜合數(shù)據(jù)[2]。詳細(xì)數(shù)據(jù)包括單位各部門(mén)每天的數(shù)據(jù)流動(dòng)和明細(xì)；高度綜合數(shù)據(jù)包括各部門(mén)每月、每年的資產(chǎn)數(shù)據(jù)集合，以統(tǒng)計(jì)數(shù)據(jù)報(bào)表的形式長(zhǎng)期存儲(chǔ)。

資產(chǎn)數(shù)據(jù)庫(kù)的邏輯模型采用雪花模型[3-4]。雪花模型可以將各個(gè)維度的表格拓展為實(shí)時(shí)表，由此構(gòu)成局部層次區(qū)域(見(jiàn)圖1)。構(gòu)建好的多維主題表，數(shù)據(jù)冗余度較低，可以確保數(shù)據(jù)的一致性，可以實(shí)現(xiàn)較好的數(shù)據(jù)粒度，規(guī)則泛化能力較強(qiáng)。數(shù)據(jù)庫(kù)構(gòu)建完成后，需要裝填數(shù)據(jù)。具體流程是：首先抽取源數(shù)據(jù)，按構(gòu)建的邏輯數(shù)據(jù)模型轉(zhuǎn)換相關(guān)的數(shù)據(jù)；然后從物理數(shù)據(jù)模型中提取相關(guān)的資產(chǎn)數(shù)據(jù)變化特征，將其填補(bǔ)到資產(chǎn)數(shù)據(jù)庫(kù)中；最后應(yīng)用改進(jìn)的Apriori算法實(shí)現(xiàn)數(shù)據(jù)挖掘。

圖1 資產(chǎn)數(shù)據(jù)庫(kù)的邏輯模型

2.2.1 資產(chǎn)指標(biāo)選擇

在數(shù)據(jù)挖掘過(guò)程中規(guī)約屬性和分類(lèi)數(shù)據(jù)，能夠降低屬性值，簡(jiǎn)化挖掘規(guī)則。我們通過(guò)設(shè)計(jì)屬性約束方式來(lái)降低候選項(xiàng)集數(shù)量，提升關(guān)聯(lián)規(guī)則效率[5]。軌道交通工程建設(shè)單位的資產(chǎn)管理涉及一系列資產(chǎn)，資產(chǎn)數(shù)據(jù)的數(shù)量龐大而繁雜。從中選擇下列較有代表性的資產(chǎn)指標(biāo)。

A. 資產(chǎn)建設(shè)費(fèi)用。這是固定資產(chǎn)，包含建設(shè)資產(chǎn)的原始費(fèi)用。

B. 資產(chǎn)剩余使用年率。資產(chǎn)使用年限反映著資產(chǎn)的折舊費(fèi)用，這是資產(chǎn)管理的關(guān)鍵指標(biāo)。

C. 資產(chǎn)年使用率。在使用過(guò)程中，各種資產(chǎn)都會(huì)由于損耗而降低價(jià)值。

D. 資產(chǎn)質(zhì)量評(píng)估值。在資產(chǎn)管理過(guò)程中要對(duì)每個(gè)指標(biāo)進(jìn)行質(zhì)量評(píng)估，以此確定資產(chǎn)的價(jià)值。

2.2.2 數(shù)據(jù)處理方法

(1) 數(shù)據(jù)泛化。這是對(duì)數(shù)據(jù)庫(kù)中與任務(wù)相關(guān)的大量數(shù)據(jù)進(jìn)行抽象概述的一個(gè)分析過(guò)程。未通過(guò)泛化的數(shù)據(jù)，通常在屬性值的表達(dá)中沒(méi)有規(guī)律可尋，且表述復(fù)雜，沒(méi)有一個(gè)明顯的特點(diǎn)[6]。

(2) 數(shù)據(jù)離散化。對(duì)非連續(xù)的數(shù)據(jù)，通常應(yīng)用泛化技術(shù)來(lái)進(jìn)行處理；對(duì)連續(xù)性數(shù)據(jù)則采用離散化處理方式。將連續(xù)的數(shù)據(jù)分成若干個(gè)合理的區(qū)間，設(shè)置一個(gè)區(qū)間線來(lái)表示各數(shù)據(jù)匯總值，并計(jì)算得到該區(qū)間范圍的各個(gè)統(tǒng)計(jì)值，以特定的離散符號(hào)表示。步驟是先確定分割離散點(diǎn)，然后對(duì)分段區(qū)間進(jìn)行統(tǒng)計(jì)[7]。

2.3 改進(jìn)算法的規(guī)則生成

對(duì)資產(chǎn)數(shù)據(jù)進(jìn)行挖掘時(shí)，在關(guān)聯(lián)規(guī)則中添加約束，可以顯著提升挖掘效率。為了研究資產(chǎn)的共性，對(duì)資產(chǎn)信息數(shù)據(jù)進(jìn)行約束。I=。其中，tid為資產(chǎn)類(lèi)別編號(hào)；name指資產(chǎn)名稱(chēng)；A表示購(gòu)置的資產(chǎn)信息；purchasetiame即購(gòu)買(mǎi)時(shí)間；categories表示不同類(lèi)型的資產(chǎn)類(lèi)別。

對(duì)于每個(gè)單項(xiàng)事務(wù)，T=。其中，rid是一個(gè)全局事務(wù)變量；itemsets為該事務(wù)的項(xiàng)目集合。

對(duì)給定的資產(chǎn)，定義其中兩個(gè)單項(xiàng)事務(wù)為I1和I2。當(dāng)其存在關(guān)聯(lián)屬性時(shí)，例如是在同一個(gè)時(shí)間段內(nèi)購(gòu)置的資產(chǎn)，則認(rèn)為這兩者之間存在屬性連接，將共同屬性作為事務(wù)標(biāo)號(hào)。如此，逐步增加新事務(wù)的數(shù)量。

3 算法實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)開(kāi)發(fā)語(yǔ)言為C#語(yǔ)言，數(shù)據(jù)庫(kù)為SQL 2008。使用聯(lián)想電腦，內(nèi)存為2 GB，CPU采用Intel i5，主頻大小為1.6 GHz。實(shí)驗(yàn)數(shù)據(jù)集為某市五條地鐵運(yùn)營(yíng)過(guò)程中購(gòu)置的資產(chǎn)事務(wù)數(shù)據(jù)集，數(shù)據(jù)量為313 MB，包含資產(chǎn)記錄86.2萬(wàn)條，屬于海量數(shù)據(jù)集。

確定數(shù)據(jù)庫(kù)結(jié)構(gòu)后，首先規(guī)約數(shù)據(jù)屬性，并根據(jù)量化規(guī)則將其轉(zhuǎn)換為相同的格式，應(yīng)用約束規(guī)則來(lái)預(yù)處理相同格式的數(shù)據(jù)；然后引用SQL語(yǔ)句統(tǒng)計(jì)功能來(lái)完成數(shù)據(jù)統(tǒng)計(jì)；最后運(yùn)用改進(jìn)的Apriori算法完成對(duì)候選項(xiàng)集的計(jì)算，由此構(gòu)建強(qiáng)關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集。

軌道交通工程建設(shè)單位的資產(chǎn)數(shù)據(jù)量較大，且資產(chǎn)屬性量也較多，挖掘出來(lái)的關(guān)聯(lián)規(guī)則數(shù)量比較多。為了驗(yàn)證算法的挖掘效率和精確性，將傳統(tǒng)的Apriori算法在不同支持度下的挖掘時(shí)間與改進(jìn)算法進(jìn)行了比較，結(jié)果如圖2所示。

圖2 在不同支持度下新舊算法所需的挖掘時(shí)間

傳統(tǒng)Apriori算法和改進(jìn)算法都是隨著支持度的上升，所消耗時(shí)間越來(lái)越少；但改進(jìn)后的Apriori算法所需的時(shí)間明顯少很多，它具有更好的時(shí)間效率。

在資產(chǎn)數(shù)據(jù)挖掘中，分別設(shè)置兩種最小支持度和最小信任度，即(0.1，0.3)和(1.6，1.5)，對(duì)資產(chǎn)數(shù)據(jù)進(jìn)行遍歷處理。結(jié)果顯示，改進(jìn)后的Apriori算法能夠快速獲取到關(guān)聯(lián)規(guī)則(見(jiàn)表1)。在支持度不同的情況下，改進(jìn)算法計(jì)算頻繁項(xiàng)的速度非?？?。當(dāng)選擇支持度為0.1時(shí)，運(yùn)用改進(jìn)算法計(jì)算得到頻繁項(xiàng)用時(shí)為45 min，約為傳統(tǒng)算法用時(shí)的15。運(yùn)用改進(jìn)算法獲取到的關(guān)聯(lián)規(guī)則數(shù)量也較多。隨著支持度的上升，關(guān)聯(lián)規(guī)則數(shù)量有明顯降低。最小支持度增加過(guò)大，會(huì)導(dǎo)致一些正確的規(guī)則數(shù)降低，從而降低不同數(shù)據(jù)之間的關(guān)聯(lián)性。

表1 在不同的最小支持度和信任度下算法的效率對(duì)比

說(shuō)明：提升效率=(傳統(tǒng)算法-改進(jìn)算法)÷傳統(tǒng)算法×100%。

4 結(jié) 語(yǔ)

根據(jù)軌道交通工程建設(shè)單位資產(chǎn)管理的需要，應(yīng)用數(shù)據(jù)挖掘技術(shù)挖掘資產(chǎn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則。聯(lián)系資產(chǎn)數(shù)據(jù)的特點(diǎn)，改進(jìn)Apriori算法，構(gòu)建了頻繁項(xiàng)生成優(yōu)化模型，應(yīng)用數(shù)據(jù)屬性規(guī)約方式優(yōu)化約束關(guān)聯(lián)規(guī)則。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的Apriori算法具有更好的時(shí)間效率，可適用于海量數(shù)據(jù)集。