基于 SQL分層抽樣的數據挖掘算法的改進＊

謝笑盈, 邢君飛

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

0 引 言

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

1 方法分析

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

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

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

2 實證分析

2.1 模型設計

為了讓上述的數據挖掘思想得以實現,本文采用 SQL Server 2005的基于數據挖掘的工具 B I(Business Intelligence)來實現.根據浙江工商大學對杭州經濟開發區健身情況的調查表模擬建立數據庫,并以此為基礎進行聯機分析挖掘研究.

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

2.2 模型建立

由于該數據庫中存在的記錄數很大,若直接對數據庫進行關聯規則的數據挖掘,則需要進行大量的計算.SQL Server 2005根據工作性質對網民情況表進行聚類,下面是實現的 SQL語句:

至此,網民情況表根據工作性質被分成了 6個結構相同的子表,分別按職業保存為:公務員表、教師表、民營表、外資表、國企表、自由職業表,這就相當于把網民情況表按工作性質分成了 6個層,對每個層進行隨機抽樣.

以公務員表為例,用 SQL語句實現如下:

將從 6個子表中等比例抽樣的結果保存到同一個表中,表名為網民情況抽樣,至此,實現了對網民情況表的降維.將網民情況抽樣表與健身事實表和運動情況表進行連接處理,就實現了對整個數據庫的降維,后續的關聯規則分析將在降維后的數據庫中進行.

為了調查職業、省份、性別、年齡對運動時間、運動項目的影響,要對降維后的數據庫進行深入的挖掘分析.以前面的數據庫為基礎創建一個以健身事實表為事例表,以網民情況抽樣表和運動情況表作為嵌套表的挖掘結構,然后將所需分析的居住省份、年齡、性別作為輸入列,以運動時段和運動項目作為預測列,具體建模如圖 1所示.

將最低支持度設置為 0.5,最小項集設置為 1,最小置信度分別設置為 0.95,0.96,0.97,0.98,0.99,1.00,即挖掘結構采用支持度-置信度評估框架來選擇關聯規則.

圖 1 基于Microsoft算法關聯規則的挖掘模型

2.3 模型分析

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

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

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

表 1 不同算法下關聯分析效果比較

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

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

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

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

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

刪減規則 3:X→Y,Y→Z,X→Z,則 X→Z規則可以刪除.

表 2是對健身數據集的抽樣子集在各個支持度閥值下經過刪減前后的關聯規則數比較.

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

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

3 結 語

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

[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].統計與預測,1999(5):1-2.