[發(fā)明專利]一種快速發(fā)現(xiàn)效用模式的數(shù)據(jù)挖掘方法

無效

• 申請?zhí)枺?/td>: 201210042570.8
• 申請日: 2012-02-23
• 公開（公告）號: CN102662948A
• 公開（公告）日: 2012-09-12
• 發(fā)明（設(shè)計）人: 劉君強;蔣曉寧;甘志剛;余斌霄
• 申請（專利權(quán)）人: 浙江工商大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及智能化信息處理領(lǐng)域。本發(fā)明設(shè)計了一種能從海量數(shù)據(jù)中發(fā)現(xiàn)既具有顯著統(tǒng)計特征又符合用戶期望與目標(biāo)的效用模式挖掘方法，在海量數(shù)據(jù)挖掘特別是網(wǎng)絡(luò)信息搜索與知識發(fā)現(xiàn)，包括Web挖掘、文本挖掘、多媒體挖掘中，有著廣泛應(yīng)用前景。

背景技術(shù)

傳統(tǒng)數(shù)據(jù)挖掘技術(shù)，特別是頻繁模式挖掘技術(shù)[1][2]，主要根據(jù)統(tǒng)計顯著性來進(jìn)行數(shù)據(jù)分析，比如從超市銷售數(shù)據(jù)中挖掘出購買頻率較高的產(chǎn)品組合等，沒有考慮到用戶的期望或目標(biāo)，比如用戶可能對利潤回報較高的產(chǎn)品組合感興趣。也就是說，在數(shù)據(jù)挖掘中不僅要考慮數(shù)據(jù)的統(tǒng)計顯著性，還要考慮用戶的興趣或目標(biāo)[3]。效用模式挖掘技術(shù)作為頻繁模式挖掘技術(shù)的新發(fā)展應(yīng)運而生[4][5][6][7][8].

然而，效用模式挖掘技術(shù)還不成熟，只有很少量成果，均采用兩階段法。兩階段法TP首先是由Liu等[4]提出。第一階段根據(jù)事務(wù)加權(quán)效用TWU向下閉合性質(zhì)，先找出具有較高TWU的模式從而生成候選模式集合，第二階段再次掃描數(shù)據(jù)庫來計算各個候選模式的實際效用從而找出效用高于給定閥值的模式。Li等[5]提出了孤立項剔除策略，用于逐層挖掘候選模式的第一階段，以減少多余候選模式，這樣也能提高效率，因為每一層候選模式的計算都可以在一個遞減的數(shù)據(jù)集上進(jìn)行。

最近，為避免逐層生成候選模式時多遍掃描數(shù)據(jù)庫[4][5]的缺點、以使第一階段能高效率地生成候選模式，多個研究小組提出基于樹的效用模式挖掘方法[6][7][8]。Erwin等[6]提出CTU-PROL挖掘方法，運用事務(wù)加權(quán)效用TWU向下閉合性質(zhì)[4]、基于效用模式樹CUP-tree和FP-Growth[2]來進(jìn)行挖掘。Ahmed等[7]提出IHUP挖掘方法，采用IHUP-tree來存儲各個事務(wù)的TWU信息，改進(jìn)FP-Growth[2]來挖掘效用模式的候選模式集。CTU-PROL挖掘方法[6]和IHUP挖掘方法[7]在第一階段生成的候選模式數(shù)量和TP[4]相同。Tseng等[8]設(shè)計出另一個基于樹的UPG挖掘方法，利用UP-tree壓縮表達(dá)事務(wù)的效用信息，提出樹結(jié)點效用剔除/遞減策略來改進(jìn)事務(wù)加權(quán)效用TWU向下閉合性質(zhì)，因而生成較少數(shù)量的候選模式。

然而，現(xiàn)有成果都沒有跳出兩階段法的框架，盡管也有工作[5][8]試圖降低第一階段生成的候選模式數(shù)量。當(dāng)數(shù)據(jù)庫存在較長的事務(wù)記錄或給定效用閥值較小時，候選模式的數(shù)量還是巨大的。這不僅造成存儲空間開銷過大，導(dǎo)致第一階段的可伸縮性瓶頸，對于第二階段也是如此，并最終導(dǎo)致運行的時間效率低下。

為克服以往挖掘方法的缺陷，本發(fā)明提出以下三項創(chuàng)新技術(shù)，以擺脫兩階段法的框架，并設(shè)計出“一種快速發(fā)現(xiàn)效用模式的數(shù)據(jù)挖掘方法”，從而解決可伸縮性與效率的瓶頸問題。

第一項是基于稀疏矩陣和虛擬投影的數(shù)據(jù)表示。具體講，提出稀疏矩陣來表達(dá)各個事務(wù)效用的完整信息，使得單階段挖掘成為可能。這種稀疏矩陣表示方法比基于FP-tree[2]的表示方法[6][7][8]更緊湊，避免多遍掃描數(shù)據(jù)庫[4][5]。采用虛擬投影，在不增加任何存儲開銷的情況下，計算任意模式的效用值。

第二項是前綴生長策略與前綴生長樹及其剪裁方法。前綴生長策略與相應(yīng)的前綴生長樹，用于引導(dǎo)效用模式的挖掘過程，并得到效用模式搜索空間剪裁技術(shù)的支撐，即通過估算任意子空間的效用值上界，可以有效地剪裁前綴生成樹。

第三項是深度優(yōu)先的動態(tài)搜索法。在搜索前綴生長樹來發(fā)現(xiàn)效用模式的過程中，采用深度優(yōu)先法來構(gòu)造當(dāng)前搜索的分枝，無需在內(nèi)存中存留完整的前綴生長樹、也無需在內(nèi)存中儲存效用模式，因而能進(jìn)一步降低存儲開銷。

本發(fā)明挖掘方法的時間效率比三個參照挖掘方法[4][7][8]高1至3個數(shù)量級，并且內(nèi)存使用量少40％到90％。本發(fā)明挖掘方法具有高性能，可在海量Web挖掘、多媒體挖掘、文本挖掘等各種應(yīng)用中廣泛使用。

參考文獻(xiàn)：

[1]R.Agrawal?and?R.Srikant.Fast?algorithms?for?mining?association?rules[A].In?Proc.of?VLDB?1994[C].1994，487-499..

[2]J.Han，J.Pei，Y.Yin.Mining?frequent?patterns?without?candidate?generation[A].In?Proc.of?ACM?SIGMOD2000[C].Dallas，USA，2000，1-12.