基于 SQL分層抽樣的數(shù)據(jù)挖掘算法的改進(jìn)＊

謝笑盈, 邢君飛

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江金華 321004)

0 引 言

關(guān)聯(lián)規(guī)則挖掘是知識發(fā)現(xiàn)中的一個重要問題,它是由 Agrawal,I mielinski和 Swami[1]于 1993年提出的.關(guān)聯(lián)規(guī)則挖掘用于發(fā)現(xiàn)數(shù)據(jù)庫中不同項目集之間的關(guān)系,從而得出有意義的規(guī)則和模式.自關(guān)聯(lián)規(guī)則挖掘這一概念被提出以來,諸多研究人員對其進(jìn)行了廣泛的研究,包括對原有的算法進(jìn)行優(yōu)化,如引入隨機抽樣、并行的思想等,以提高算法挖掘規(guī)則的效率.Mannila等[2]首先考慮了這一點,認(rèn)為抽樣是發(fā)現(xiàn)規(guī)則的一個有效途徑.引入隨機抽樣的基本思想是在給定數(shù)據(jù)的一個子集上挖掘,對前一遍掃描得到的信息進(jìn)行仔細(xì)地組合分析,可以得到一個改進(jìn)的算法.隨后,Toivonen[3]進(jìn)一步發(fā)展了這個思想,先使用從數(shù)據(jù)庫中抽取出來的樣本得到一些在整個數(shù)據(jù)庫中可能成立的規(guī)則,然后再用數(shù)據(jù)庫中的剩余數(shù)據(jù)驗證這個結(jié)果.Toivonen的算法相當(dāng)簡單且顯著減少了 I/O代價,但一個很大的缺點就是產(chǎn)生的結(jié)果不精確,即存在所謂的數(shù)據(jù)扭曲.分布在同一頁面上的數(shù)據(jù)時常是高度相關(guān)的,可能不能表示整個數(shù)據(jù)庫中模式的分布.為了減少抽樣產(chǎn)生的不精確性,本文利用聚類分析方法先對數(shù)據(jù)庫進(jìn)行分層,并在此基礎(chǔ)上抽樣,結(jié)合 SQL Server 2005實現(xiàn)了這一算法.

1 方法分析

數(shù)據(jù)挖掘是從存放在數(shù)據(jù)庫或其他信息庫的海量數(shù)據(jù)中挖掘有趣知識的過程.數(shù)據(jù)挖掘技術(shù)自興起以來一直是研究的熱點,現(xiàn)己有大量的實現(xiàn)算法.但隨著需要處理的數(shù)據(jù)規(guī)模越來越大,以及數(shù)據(jù)內(nèi)部的復(fù)雜性,許多算法在進(jìn)行大規(guī)模數(shù)據(jù)分析時還需要消耗大量的時間和物理資源.如何減少大規(guī)模數(shù)據(jù)分析所消耗的資源問題就不可避免地擺在了我們面前.在提高數(shù)據(jù)挖掘算法效率的同時,很自然地會引進(jìn)統(tǒng)計中的抽樣思想[4],首先對大規(guī)模數(shù)據(jù)集的部分?jǐn)?shù)據(jù)進(jìn)行數(shù)據(jù)分析,然后根據(jù)相應(yīng)的結(jié)果進(jìn)行下一步處理,以提高數(shù)據(jù)分析的效率,這是一種行之有效的方法.為了使抽出的樣本對原數(shù)據(jù)集的數(shù)據(jù)扭曲盡可能地小,用什么樣的抽樣策略,以及如何實現(xiàn)抽樣,又成了研究的焦點.

假設(shè)事物數(shù)據(jù)集合 T={t1,t2,…,ti,…,tN},其中每個事物 ti均由變量集 A={a1,a2,…,ak}來描述.若屬性 ai的取值為有限的且構(gòu)成對降維有決定意義的小集合{ai1,ai2,…,aim},根據(jù) ai的取值可將T分成m個子集,每個子集的事物個數(shù)分別為N1,N2,…,Ni,…,Nm,易知在每個子集中的事物在某方面有很大的相似性,且這種相似性對后面的數(shù)據(jù)分析有重要的意義.這就實現(xiàn)了對數(shù)據(jù)集按某個屬性的聚類,并自然而然地將數(shù)據(jù)集分成了 m個層,為對數(shù)據(jù)集進(jìn)行分層抽樣奠定了基礎(chǔ).例如,在人口普查中考察比較各省的老齡化進(jìn)程時,按事物 ti所處的省份將集合 T分成 23個子集,這種聚集操作只需對數(shù)據(jù)庫進(jìn)行一次掃描就能完成.

為了既能發(fā)現(xiàn)集合中不同項目集之間的關(guān)系,又能避免多次重復(fù)掃描處理全體數(shù)據(jù)集,因此考慮用從數(shù)據(jù)集 T中抽取出來的樣本得到一些在整個事物集中可能成立的規(guī)則,然后再用數(shù)據(jù)集的剩余數(shù)據(jù)驗證這個結(jié)果.顯然,如果抽出來的樣本能兼顧到m個子集的取值,那么這個樣本對整體數(shù)據(jù)集就有較好的體現(xiàn).因此,引入了分層抽樣,即將 m個子集看成是集合 T的 m個層,對每個層進(jìn)行隨機抽樣,設(shè)抽比例抽樣的結(jié)果保存到同一個集合 P={p1,p2,…,pj,…,pn}中.至此,實現(xiàn)了對原數(shù)據(jù)集 T的降維,后續(xù)的關(guān)聯(lián)規(guī)則分析將在降維后的數(shù)據(jù)庫中進(jìn)行.

2 實證分析

2.1 模型設(shè)計

為了讓上述的數(shù)據(jù)挖掘思想得以實現(xiàn),本文采用 SQL Server 2005的基于數(shù)據(jù)挖掘的工具 B I(Business Intelligence)來實現(xiàn).根據(jù)浙江工商大學(xué)對杭州經(jīng)濟(jì)開發(fā)區(qū)健身情況的調(diào)查表模擬建立數(shù)據(jù)庫,并以此為基礎(chǔ)進(jìn)行聯(lián)機分析挖掘研究.

首先通過 SQL ServerManagement Studio建立一個數(shù)據(jù)庫,導(dǎo)入模型所需要挖掘分析的表,然后創(chuàng)建數(shù)據(jù)庫關(guān)系圖.創(chuàng)建好數(shù)據(jù)庫關(guān)系圖后,再打開 SQL Server Business Intelligence Development Studio,新建一個數(shù)據(jù)庫關(guān)系圖 Analysis Services項目,然后新建一個數(shù)據(jù)源連接剛在 SQL ServerManagement Studio中建立的數(shù)據(jù)庫,接著創(chuàng)建數(shù)據(jù)源視圖 DSV.為了分析職業(yè)、性別、年齡、省份、運動項目、運動時間等屬性之間的關(guān)聯(lián)情況,建立 1張事實表和 2張維度表.事實表的結(jié)構(gòu)如下:運動情況 (登記 I D、周運動時間、設(shè)施收費);網(wǎng)民情況表 (登記 I D、性別、年齡、工作性質(zhì)、居住省份);健身事實表 (登記 I D、運動時段、運動項目).

2.2 模型建立

由于該數(shù)據(jù)庫中存在的記錄數(shù)很大,若直接對數(shù)據(jù)庫進(jìn)行關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘,則需要進(jìn)行大量的計算.SQL Server 2005根據(jù)工作性質(zhì)對網(wǎng)民情況表進(jìn)行聚類,下面是實現(xiàn)的 SQL語句:

至此,網(wǎng)民情況表根據(jù)工作性質(zhì)被分成了 6個結(jié)構(gòu)相同的子表,分別按職業(yè)保存為:公務(wù)員表、教師表、民營表、外資表、國企表、自由職業(yè)表,這就相當(dāng)于把網(wǎng)民情況表按工作性質(zhì)分成了 6個層,對每個層進(jìn)行隨機抽樣.

以公務(wù)員表為例,用 SQL語句實現(xiàn)如下:

將從 6個子表中等比例抽樣的結(jié)果保存到同一個表中,表名為網(wǎng)民情況抽樣,至此,實現(xiàn)了對網(wǎng)民情況表的降維.將網(wǎng)民情況抽樣表與健身事實表和運動情況表進(jìn)行連接處理,就實現(xiàn)了對整個數(shù)據(jù)庫的降維,后續(xù)的關(guān)聯(lián)規(guī)則分析將在降維后的數(shù)據(jù)庫中進(jìn)行.

為了調(diào)查職業(yè)、省份、性別、年齡對運動時間、運動項目的影響,要對降維后的數(shù)據(jù)庫進(jìn)行深入的挖掘分析.以前面的數(shù)據(jù)庫為基礎(chǔ)創(chuàng)建一個以健身事實表為事例表,以網(wǎng)民情況抽樣表和運動情況表作為嵌套表的挖掘結(jié)構(gòu),然后將所需分析的居住省份、年齡、性別作為輸入列,以運動時段和運動項目作為預(yù)測列,具體建模如圖 1所示.

將最低支持度設(shè)置為 0.5,最小項集設(shè)置為 1,最小置信度分別設(shè)置為 0.95,0.96,0.97,0.98,0.99,1.00,即挖掘結(jié)構(gòu)采用支持度-置信度評估框架來選擇關(guān)聯(lián)規(guī)則.

圖 1 基于Microsoft算法關(guān)聯(lián)規(guī)則的挖掘模型

2.3 模型分析

通過對原數(shù)據(jù)集、隨機抽樣、分層抽樣前后數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘結(jié)果進(jìn)行對比,結(jié)果如表 1所示 (支持度為 0.5,以運動項目為后件).

從挖掘結(jié)果來看,在支持度相同的前提下,分層抽樣挖掘的結(jié)果與原數(shù)據(jù)集的挖掘結(jié)果最為近似.在相同的置信度水平下(minconf≥0.95),分層抽樣算法能發(fā)現(xiàn)原數(shù)據(jù)集下的所有的關(guān)聯(lián)規(guī)則,且規(guī)則的前后件都分別相同.這說明分層抽樣的樣本數(shù)據(jù)與原數(shù)據(jù)集的分布較為接近,且保留了原數(shù)據(jù)集的大部分信息.隨機抽樣的挖掘算法在相同的置信度水平下都發(fā)現(xiàn)了比原數(shù)據(jù)集下更多的關(guān)聯(lián)規(guī)則,這可能是因為隨機抽樣下的樣本數(shù)據(jù)出現(xiàn)了數(shù)據(jù)扭曲,即隨機抽取了具有較強關(guān)聯(lián)度的數(shù)據(jù),使得樣本數(shù)據(jù)中出現(xiàn)了更多的關(guān)聯(lián)規(guī)則,而有些關(guān)聯(lián)規(guī)則在原數(shù)據(jù)集下是達(dá)不到相應(yīng)的置信度水平的.此結(jié)果能從支持度-置信度框架下說明基于分層抽樣的關(guān)聯(lián)規(guī)則算法的可行性,以及與隨機抽樣相比下的優(yōu)勢性.

本文在創(chuàng)建挖掘結(jié)構(gòu)后,用支持度-置信度框架來選擇關(guān)聯(lián)規(guī)則.但是,用支持度-置信度框架決定關(guān)聯(lián)規(guī)則的可接受程度存在局限性,因為支持度的限制可能會使許多潛在的有意義的模式因為包含了支持度小的項而被刪除,而置信度的度量可能會忽略了規(guī)則后件中出現(xiàn)的項集的支持度.因此,研究人員已經(jīng)開始用提升度 (lift)來彌補支持度-置信度評估的缺點,它計算了規(guī)則置信度和規(guī)則后件中項集的支持度之間的比率.下面是提升度度量的統(tǒng)計定義 (提升度也常被稱為興趣因子):

表 1 不同算法下關(guān)聯(lián)分析效果比較

然而,在某些情形下,用提升度評估關(guān)聯(lián)規(guī)則也會存在局限性.例如,當(dāng) A,B項集同時出現(xiàn)的概率水平較高時,lift(A→B)的值會接近于 1,這表明 A,B之間是相對獨立的.但事實上,當(dāng) A,B同時出現(xiàn)的概率水平高時,會使得 A→B的置信度水平較高,即 A,B之間存在著較強的關(guān)聯(lián),這就產(chǎn)生了悖論.此時,結(jié)合數(shù)據(jù)集本身的特點 (主要是數(shù)據(jù)集所表示的實際意義,而不全是它的統(tǒng)計特點),即所謂的領(lǐng)域的知識來解決這一悖論問題.本文結(jié)合領(lǐng)域知識,引入數(shù)據(jù)庫系統(tǒng)中的范式理論,對關(guān)聯(lián)規(guī)則的評估作進(jìn)一步的探討.

為了使有意義的關(guān)聯(lián)規(guī)則不被刪除掉,可以通過設(shè)置較低的支持度閥值 (minsup)而保留大部分的關(guān)聯(lián)規(guī)則.這樣的設(shè)置會使所產(chǎn)生的規(guī)則數(shù)量呈幾何數(shù)量級遞增,如果直接在這些規(guī)則上再使用其他評估方法,如置信度、提升度等對規(guī)則進(jìn)行進(jìn)一步的刪減,工作量會很大.但是,如果在這之前先進(jìn)行一輪刪減,將會大大減輕后面的工作量.本文借鑒數(shù)據(jù)庫理論中關(guān)系數(shù)據(jù)庫的范式理論,并對之作部分改進(jìn)以實現(xiàn)對規(guī)則的刪減.

關(guān)系數(shù)據(jù)庫第 2范式 (2NF)要求關(guān)系模式 R(U,F)中的所有非主屬性都完全依賴于任意一個候選碼,第 3范式 (3NF)要求關(guān)系模式 R(U,F)中的所有非主屬性對任何候選碼都不存在傳遞依賴,剔除非主屬性和候選碼的限制,將這 2個范式進(jìn)行如下改進(jìn):

刪減規(guī)則 1:X→Z且 Y→Z,其中,Y?X,則 X→Z規(guī)則可以刪除;

刪減規(guī)則 2:X→Z且 X∧Y→Z,則 X∧Y→Z規(guī)則可以刪除;

刪減規(guī)則 3:X→Y,Y→Z,X→Z,則 X→Z規(guī)則可以刪除.

表 2是對健身數(shù)據(jù)集的抽樣子集在各個支持度閥值下經(jīng)過刪減前后的關(guān)聯(lián)規(guī)則數(shù)比較.

從表 2可以看出,經(jīng)過刪減規(guī)則處理后,產(chǎn)生的關(guān)聯(lián)規(guī)則已經(jīng)大大減少了,在此基礎(chǔ)上再對規(guī)則集進(jìn)行置信度和提升度的處理將變得更加有效.當(dāng)然,這其中是否刪減了一些在實際領(lǐng)域中有一定意義的關(guān)聯(lián)規(guī)則,還有待于進(jìn)一步檢驗,或許還會有更好的剔除方法.

表 2 基于范式理論的刪減規(guī)則作用前后對比表

3 結(jié) 語

數(shù)據(jù)挖掘軟件憑借高性能的硬件設(shè)備為數(shù)據(jù)挖掘工作帶來了越來越多的便利和越來越高的速度,但若不從算法和實現(xiàn)方法上作改進(jìn),再好的硬件設(shè)備在面對龐大的數(shù)據(jù)海洋時也會一籌莫展.此時,統(tǒng)計思想和統(tǒng)計方法的靈活運用將會為數(shù)據(jù)挖掘工作帶來事半功倍的效果.本文在關(guān)聯(lián)規(guī)則挖掘算法改進(jìn)中作了一定的嘗試,但限于篇幅,沒有對數(shù)據(jù)庫的剩余部分驗證挖掘結(jié)果.另外,對于如何為抽樣選擇合適的樣本容量也有待于進(jìn)一步研究.

[1]Agrawal R,I mielinski T,SwamiA.Mining association rules between sets of items in large databases[C]//Proceedings of the ACM SIG MOD Conference onManagement of data.New Bruns wick:Publishiing House ofW illey,1993:207-216.

[2]Mannila H,Toivonen H,Verkamo A.Efficient algorithm for discovering association rules[C]//AAA IWorkshop on Knowledge Discovery inDatabases of Technology.Swizerland:Publishiing House of 21stVLDB Conference Zurich,1994:181-192.

[3]Toivonen H.Sampling large databases for association rules[C]//Proceedings of the 22nd International Conference on Very Large Database.Bombay:Publishiing House ofODB,1996:134-145.

[4]李金昌.分層抽樣估計精度控制方法的研究[J].統(tǒng)計與預(yù)測,1999(5):1-2.