, ,

(福建工程學(xué)院 管理學(xué)院, 福建 福州 350118)

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中主要的技術(shù)之一，其所挖掘的頻繁項(xiàng)集主要是以1994年的Agrawal等人所提出的Apriori算法最具代表性[1]。然而Apriori算法在執(zhí)行時(shí)會產(chǎn)生龐大數(shù)量的候選項(xiàng)目集合以及多次重復(fù)掃描數(shù)據(jù)庫等缺點(diǎn)，進(jìn)而造成算法效能不佳。因此許多學(xué)者都提出了許多改進(jìn)的方式，其目的主要是減少數(shù)據(jù)庫的掃描與增加執(zhí)行上的效率。例如DHP算法可減少候選項(xiàng)目集，來生成關(guān)聯(lián)規(guī)則[2]；DIC算法可同時(shí)掃描多個(gè)階段，并降低掃描數(shù)據(jù)庫的次數(shù)，提高整體效率[3]；FP-Growth算法是利用FP-tree的樹狀結(jié)構(gòu)來將事務(wù)數(shù)據(jù)壓縮在內(nèi)，且在整個(gè)挖掘的過程中，只須掃描數(shù)據(jù)庫兩次。在過程中不須產(chǎn)生候選項(xiàng)目集，除了大幅的加快挖掘的速度外，還可節(jié)省大量的儲存空間，因而整體的效率相當(dāng)不錯(cuò)[4]。

其次，對于一個(gè)決策問題而言，需要考慮到使用者的認(rèn)知與主觀判斷所產(chǎn)生的認(rèn)知不確定性。Zadeh所提出的模糊理論可用來處理包含含糊性與意義不明確的認(rèn)知不確定性[5]。再加上語意變數(shù)與語意值[6-8]所描述的模糊概念較符合決策者在主觀上的認(rèn)知，有助于決策分析的進(jìn)行，因此近來的模糊數(shù)據(jù)挖掘則成為一項(xiàng)重要議題。

一般在對交易項(xiàng)目描述時(shí)，除了可用實(shí)體名稱來表示外，交易項(xiàng)目之間還能透過抽象化的階層方式來進(jìn)行分類。也就是說，從較高階層上來尋找項(xiàng)目間的關(guān)聯(lián)性是個(gè)重要的研究。Han與Fu提出類似圖1關(guān)于“食品”的樹狀結(jié)構(gòu)的概念階層結(jié)構(gòu)圖[9]，該結(jié)構(gòu)模型有4個(gè)遞階層次，階層編號由最上層開始編為層次0，直到產(chǎn)品最底層為層次3，而階層越高名稱越是廣泛化(General)。例如在層次1的”Bread”在層次2里具有”White”與”Wheat”的廣泛化概念。此外，由根節(jié)點(diǎn)到最低層次的某一節(jié)點(diǎn)則形成一條具有父子關(guān)系的路徑。例如”Black tea”是”Beverage”的繼承者，而”Linton”是”Black tea”的繼承者。

圖1 關(guān)于“食品”的概念層次Fig.1 Conceptual hierarchy for “Food”

基于概念層次的挖掘，本文提出一項(xiàng)模糊數(shù)據(jù)挖掘方法。首先將架構(gòu)的每個(gè)節(jié)點(diǎn)視為一個(gè)語意變量并以適當(dāng)?shù)臄?shù)量來加以分割，接著采用FP-growth方式在多層次間挖掘模糊關(guān)聯(lián)規(guī)則；并透過表格結(jié)構(gòu)的方式來儲存高頻模糊格，這做法比傳統(tǒng)交集方式更加快速，且在挖掘的過程中無需產(chǎn)生過多的候選項(xiàng)目集，即可完成整體挖掘任務(wù)。

1 相關(guān)文獻(xiàn)研究

1.1 產(chǎn)生編碼表

若一個(gè)階層架構(gòu)有h個(gè)層次，則每個(gè)節(jié)點(diǎn)能被編成h-1的序列。當(dāng)一個(gè)節(jié)點(diǎn)編在層次j時(shí)，則節(jié)點(diǎn)將被轉(zhuǎn)換成c1c2…cj-1cj…*，其j≤h-1且*的數(shù)量為h-j-1。其次，cu(u=1,2,…,j)為一個(gè)整數(shù)時(shí)，其值會由父節(jié)點(diǎn)的分支點(diǎn)來決定。以圖1為例，階層為4，故h= 4且節(jié)點(diǎn)的序列長為3。而“Bread”與“Plain”分別為根節(jié)點(diǎn)與“Milk”的第2個(gè)分支，因此“Bread”與“Plain”可被編成“2**”與“12*”。因此，通過此方法來進(jìn)行編碼后的結(jié)果如表1-表3所示。

表1 在階層3所進(jìn)行的編碼轉(zhuǎn)換Tab.1 Transcoding on Level 3

表2 在階層2所進(jìn)行的編碼轉(zhuǎn)換Tab.2 Transcoding on Level 2

表3 在階層1所進(jìn)行的編碼轉(zhuǎn)換Tab.3 Transcoding on Level 1

1.2 模糊切割法

語意變量的概念是由Zadeh所提出[5]，而一個(gè)語意變量的值可由自然語言的形式來表達(dá)[6-8]。因此，模糊分割系就是把每個(gè)語意變數(shù)以其所給予的語意值加以切割。例如{Small, Medium, Large}是一個(gè)定義在數(shù)量上的語意值集合。如圖2所示，在2個(gè)二維空間上分別在x1與x2上定義了3個(gè)語意值，因此共有9個(gè)模糊格產(chǎn)生，其中的灰色陰影區(qū)則是所對應(yīng)到的模糊格(A11,A23)。圖2亦為使用模糊切割后的結(jié)果。

(1)

圖2 關(guān)于x1與x2的模糊分割法Fig.2 Fuzzy partitions for x1 and x2

2 算法的提出及其原理步驟

首先簡要介紹算法所使用到的符號表示。而表4是用來說明使用算法的交易事務(wù)數(shù)據(jù)集。圖3則是此例用到的隸屬函數(shù)。

2.1 符號表示

n: 交易事務(wù)數(shù)據(jù)的數(shù)量；

m: 使用來描述每一筆交易事務(wù)項(xiàng)的數(shù)量，其中1≤m；

xk: 第k個(gè)項(xiàng)，其中1≤k≤m；

K: 語意值在交易數(shù)據(jù)庫里的每個(gè)量化項(xiàng)的語意值，其中K≥2；

tp: 第p筆的交易數(shù)據(jù)，其中1≤p≤n；

α: 預(yù)先指定的最小模糊支持度值；

β: 預(yù)先指定的最小模糊信賴度值；

h: 概念階層的總層次，其中h≥ 1；

圖3 此例所用到的量化隸屬函數(shù)Fig.3 Quantization membership function used in this example

2.2 算法的提出

輸入值：

(1)n筆的交易事務(wù)數(shù)據(jù)；

(2)每個(gè)語意變數(shù)有著K個(gè)語意值；

(3)概念層次的總層次；

(4)預(yù)先指定的最小模糊支持度值，α。

(5)預(yù)先指定的最小模糊信賴度值，β。

輸出值：

模糊關(guān)聯(lián)規(guī)則集。

步驟1：概念層次編碼。概念層次有h層，則每個(gè)節(jié)點(diǎn)則被編成h-1個(gè)序列。如果編碼的類型相同，數(shù)量則被合并。在表4的范例里以層次3進(jìn)行處理，其結(jié)果如表1所示。

步驟3：建構(gòu)表格FGTTFS并以由下步驟來生成高頻模糊格。其范例格式如表6所示。

(1)模糊格(Fuzzy grid, FG)：每列表示一個(gè)模糊格與每行表示著語意值。

表4此例所使用的交易事務(wù)數(shù)據(jù)集
Tab.4Transactiondatasetusedinthisexample

TIDItems1(Milk?Chocolate?Dairland，5)，(Bread?White?Oldmills，5)，(Bread?White?Wonder，7)，(Bread?Wheat?Oldmills，2)，(Cookies?Chocoate?Present，9)，(Beverage?Greentea?Nestle，8)2(Milk?Chocolate?Dairland，5)，(Milk?Plain?Dairland，6)，(Milk?Plain?Foremost，3)，(Bread?Wheat?Wonder，7)，(Cookies?Lemon?Present，10)，(Cookies?Lemon?77，3)3(Bread?White?Wonder，7)，(Bread?Wheat?Wonder，3)，(Cookies?Chocolate?Present，5)，(Cookies?Lemon?77，6)4(Milk?Chocolate?Dairland，6)，(Milk?Chcoclate?Foremost，1)，(Bread?White?Oldmills，5)，(Bread?White?Wonder，6)，(Cookies?Chocolate?Present，7)，(Cookies?Lemon?Present，3)，(Beverage?Blacktea?Nestle，3)，(Beverage?Greentea?Linton，1)5(Milk?Chcoclate?Dairland，3)，(Milk?Chocolate?Foremost，10)，(Bread?White?Oldmills，2)，(Bread?Wheat?Wonder，4)，(Beverage?Blacktea?Linton，3)，(Beverage?Blacktea?Nestle，9)

表5 將交易事務(wù)數(shù)據(jù)集轉(zhuǎn)換成模糊集

表6 建構(gòu)于階層3的表格FGTTFSTab.6 Table FGTTFS for items on Level 3

(3)模糊支持度(Fuzzy support, FS)：其存放所對應(yīng)模糊格的模糊支持度，其計(jì)算方式為下式。

(2)

Small、211.Small、212.Middle、222.Small與311.Middle等6個(gè)1維高頻模糊格。

步驟7：計(jì)算每個(gè)1維高頻模糊格值的總和并構(gòu)建一個(gè)遞減名為Header Table的表格，如表7所示。接著就進(jìn)行模糊FP-growth。

表7 階層3的Tab.7 Header table of Level 3

步驟8：在掃描模糊集時(shí)首先要重新建構(gòu)模糊集表，如圖4所示，其模糊集是按照Header Table來排序。

表8 階層3的新模糊集Tab.8 New fuzzy sets of Level 3

圖4 階層3的模糊FP-treeFig.4 Fuzzy FP-tree of Level 3

步驟9：在模糊FP-tree(FFP-tree)的根節(jié)點(diǎn)上設(shè)置{ROOT}。在第2次掃描時(shí)新的模糊集就能在樹里的模糊格基于相同的交易事務(wù)來連接節(jié)點(diǎn)，以建構(gòu)出模糊FP-tree。其結(jié)果如圖4所示。

步驟10：在模糊FP-tree里挖掘可能的高頻樣式。從Header Table最底端開始掃描并從中取得模糊FP-tree從每個(gè)項(xiàng)所建構(gòu)的路徑里的條件式模式基底。其次，每個(gè)項(xiàng)的條件隸屬函數(shù)FP-tree能由條件模式基礎(chǔ)來建構(gòu)起來。則每個(gè)項(xiàng)可能的全部集將從條件模糊FP-tree里生成出來。在此例子里，其結(jié)果如表9所示。

步驟11：使用下列步驟來找出所符合的高頻樣式。

(1)把所生成的高頻樣式放入表格FGTTFS計(jì)算其模糊支持度，其結(jié)果如表10所示。

(2)檢查每個(gè)高頻樣式的模糊支持度是否大于或等于預(yù)先指定的最小模糊支持度值。

表9 階層3所生成的所有可能樣式Tab.9 All possible generated patterns of Level 3

表10 階層3的所有路徑的表格FGTTFSTab.10 Table FGTTFS for all paths on Level 3

(3)

在此范例里，候選關(guān)聯(lián)規(guī)則是:

212.Middle→311.Middle；311.Middle→212.Middle；

21*.Middle→31*.Middle；31*.Middle→21*.Middle；

2**.Middle→3**.Middle；3**.Middle→2**.Middle。

它們的模糊信賴度值分別為0.750, 0.708, 0.694, 0.694, 0.611與0.660。

(1)若Bread White Wonder的購買量為中等量時(shí)，則Cookies Chocolate Present的購買量為中等量。

(2)若Cookies Chocolate Present的購買量為中等量時(shí)，則Bread White Wonder的購買量為中等量。

(3)若Bread White的購買量為中等量時(shí)，則Cookies Chocolate的購買量為中等量。

(4)若Cookies Chocolate的購買量為中等量時(shí)，則Bread White的購買量為中等量。

(5)若Cookies的購買量為中等量時(shí)，則Bread的購買量為中等量。

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

本實(shí)驗(yàn)就所提出的方法在不同的數(shù)據(jù)庫大小(包含隨機(jī)產(chǎn)生的10 000與20 000筆交易事務(wù))與最小模糊支持度的設(shè)定下來探討運(yùn)行時(shí)間與關(guān)聯(lián)規(guī)則的生成所造成的影響。算法是以C#.Net設(shè)計(jì)，并在配備為3.07GHz的Intel Core i3的個(gè)人計(jì)算機(jī)上執(zhí)行，其使用Windows Server 2003 R2的作業(yè)系統(tǒng)與SQL Server 2008的數(shù)據(jù)庫上執(zhí)行。所使用的概念階層如圖1所定義，而在每筆交易事務(wù)中，所購買的項(xiàng)及其數(shù)量由隨機(jī)產(chǎn)生，但購買數(shù)量不超過17單位，且購買項(xiàng)不會重復(fù)產(chǎn)生。所使用的模糊集如圖3所示。

將最小模糊支持度設(shè)為0的情況下，所得到的結(jié)果如表11與表12所示。在表11與表12的實(shí)驗(yàn)結(jié)果則包含了Hong等的方法[10]與Hu的方法[11]得到的數(shù)據(jù)來比較。從中能發(fā)現(xiàn)到最小模糊支持度設(shè)定得越小，所產(chǎn)生的關(guān)聯(lián)規(guī)則就越多。在運(yùn)行時(shí)間上，所提的方法明顯優(yōu)于Hang等與Hu的方法，尤其當(dāng)最小模糊支持度越小就越明顯。這也顯示出本文所提出的方法在使用FP-growth與運(yùn)用表格FGTTFS于階層架構(gòu)下來產(chǎn)生高頻模糊格及關(guān)聯(lián)規(guī)則下，可有效的提升整體的執(zhí)行效率。且較小的最小模糊支持度也不會嚴(yán)重影響到所提出方法的運(yùn)行時(shí)間。

另外，在關(guān)聯(lián)規(guī)則的產(chǎn)出數(shù)量上，Hong等方法的特點(diǎn)是選取了每一個(gè)量化屬性上最大模糊支持度的一維模糊格；而Hu的方法特點(diǎn)則是考慮所有的高頻一維模糊格。至于本文所提出的方法，把上述兩項(xiàng)特點(diǎn)結(jié)合，進(jìn)而使所產(chǎn)生的高頻模糊格數(shù)量能在每一量化屬性上有著最大的模糊支持度并能把所有的高頻一維模糊格作整體的挖掘。因此，能獲得較優(yōu)的效能。

表11 10 000筆交易的實(shí)驗(yàn)結(jié)果Tab.11 Experimehtal results of 10 000 transactions

表12 20 000筆交易的實(shí)驗(yàn)結(jié)果Tab.12 Experimental results of 20 000 transactions

4 結(jié)論

本文應(yīng)用模糊分割法與FP-Growth算法的手段，提出一種在階層概念里來找尋模糊關(guān)聯(lián)規(guī)則的方法，該方法使用編碼方式將階層里的項(xiàng)逐一編碼，然后使用模糊分割法來找出1維模糊格，再使用FP-Growth算法，在各階層找尋可生成的模糊關(guān)聯(lián)規(guī)則。最后，通過與Hong等及Hu的方法進(jìn)行比較，驗(yàn)證本方法的有效性，由于FP-Growth之特性在于不用產(chǎn)生候選項(xiàng)集、且將數(shù)據(jù)庫給壓縮在FP-tree中，故本文的方法有著較佳的執(zhí)行效率。

其次，在語意值的設(shè)定上，使用者可依據(jù)本身的偏好、過去的使用經(jīng)驗(yàn)來主觀設(shè)定語意值個(gè)數(shù)及其形狀，如高斯分布或梯形隸屬函數(shù)，如此能更符合使用者在主觀上的認(rèn)知。且Pedrycz也提到在模糊系統(tǒng)上使用三角形隸屬函數(shù)是具有實(shí)用性及有效性[12]，故本研究采用三角隸屬函數(shù)作為模糊計(jì)算的隸屬度函數(shù)。

本研究不足之處是實(shí)行時(shí)忽略了語意值個(gè)數(shù)與交易事務(wù)記錄筆數(shù)會影響到FGTTFS表格的使用空間。當(dāng)語意值個(gè)數(shù)越大時(shí)，F(xiàn)G則需要越多的使用空間；當(dāng)交易事務(wù)記錄筆數(shù)越多時(shí)，TT所設(shè)定的使用空間就越大。若能節(jié)省FGTTFS的使用空間，勢必能讓算法的效能更加提升。至于在未來的研究展望上，對于設(shè)定使用者所給定的參數(shù)上，遺傳算法(Genetic algorithm)可考慮作為自動(dòng)決定適合參數(shù)的工具，這是由于遺傳算法具有自動(dòng)搜尋的特性。至于最小模糊支持度以及在每個(gè)量化屬性上所設(shè)定的個(gè)數(shù)K，Hong等[13]建議可透過遺傳算法的方式來自動(dòng)取得。而這些建議也是未來繼續(xù)使用數(shù)據(jù)挖掘的方法來解決各類型問題的重要參考。

[1] Agrawal R, Srikant R. Fast algorithm for mining association rules in large database[C]∥. Proceeding of 20th International Conference on Very Large Databases. Santiago:[s.n.],1994:478-499.

[2] Park J S, Chen M S, Yu P S. An effective hash based algorithm for mining association rules[C]∥. Proceeding of the 1995 ACM SIGMOD International Conference on Management of Data. San Jose: ACM Press,1995:175-186.

[3] Brin S,Motwani R, Ullman J D, et al. Dynamic itemset counting and implication rules for market basket data[C]∥. ACM SIGMOD International Conference on Management of Data. New York: ACM Press,1997:255-264.

[4] Han J, Pei J, Yin Y. Mining frequent patterns without candidate generation[C]∥. Proceeding 2000 ACM SIGMOD International Conference Management of Data. Dallas: ACM Press,2000:1-12.

[5] Zadeh L A. Fuzzy sets[J].Information and Control,1965,8(3):338-353.

[6] Zadeh L A. The concept of a linguistic variable and its application to approximate reasoning-Ⅰ[J].Information and Science,1975,8(3):199-249.

[7] Zadeh L A. The concept of a linguistic variable and its application to approximate reasoning-Ⅱ[J].Information and Science,1975,8(4):301-357.

[8] Zadeh L A. The concept of a linguistic variable and its application to approximate reasoning Ⅲ[J].Information and Science,1976,9(1):43-80.

[9] Han J W, Fu Y J. Discovery of multiple-level association rules from large database [C]. In Proceedings of International Conference on Very Large Data Bases. Zurich, 1995: 420-431.

[10] Hong T P， Lin K Y, Chien B C. Mining fuzzy multiple-level association rules from quantitative data[J].Applied Intelligence,2003,18(1):79-90.

[11] Hu Y C. Mining association rules at a concept hierarchy using fuzzy partition [J]. Journal of Information Management,2006,13(3):63-80.

[12] Pedrycz W. Triangular membership functions[J].Fuzzy Sets and Systems,1994,64(1):21-30.

[13] Hong T P, Chen C H, Lee Y C, et al. Genetic-fuzzy data mining with divide-and-conquer strategy[J].IEEE Transactions on Evolutionary Computation,2008,12(2):252-265.