基于周期采樣的數(shù)據(jù)流頻繁項集挖掘算法研究.pdf

《基于周期采樣的數(shù)據(jù)流頻繁項集挖掘算法研究.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、高技術(shù)通訊年第卷第期：：基于周期采樣的數(shù)據(jù)流頻繁項集挖掘算法研究!侯偉!楊炳儒吳晨生!周諄（北京科技大學(xué)信息工程學(xué)院北京）（!北京市科學(xué)技術(shù)情報研究所北京）摘要針對用于數(shù)據(jù)流頻繁項集挖掘的現(xiàn)有方法存在引入過多次頻繁項集以及時空性能與輸出精度較低的問題，利用不等式，構(gòu)造了項集頻度周期采樣的概率誤差邊界，給出了動態(tài)檢測項集支持度變化方法。提出了一種基于周期采樣的數(shù)據(jù)流頻繁項集挖掘算法，該算法通過跟蹤項集支持度變化確定項集支持度的穩(wěn)定性，并以此作為調(diào)整窗口大小以及采樣周期的依據(jù)，從而以一個較大的概率保證項集支持度誤差有上界。理論分析及實驗證明該算法有效，在保證挖掘結(jié)果準(zhǔn)確度相對較好的條件

2、下，可獲得較優(yōu)執(zhí)行性能。關(guān)鍵詞數(shù)據(jù)挖掘，數(shù)據(jù)流，頻繁項（）集，周期采樣（）而會降低性能及整體精度，后一類算法的設(shè)計基于引言項集支持度穩(wěn)定的假設(shè)條件，該假設(shè)過于嚴(yán)格，在概念遷移（）較頻繁時誤差較大。本文在研隨著信息技術(shù)的發(fā)展，數(shù)據(jù)庫中知識發(fā)現(xiàn)究分析現(xiàn)有方法的基礎(chǔ)上，提出了一種基于周期采（，）技術(shù)應(yīng)運而樣的數(shù)據(jù)流頻繁項集挖掘算法———（表示生。作為中的重要過程，數(shù)據(jù)挖掘（頻繁項集（），表示周期采樣（，）采用智能算法從數(shù)據(jù)中提取有益的數(shù)據(jù)模）），作為一種新的具有概率誤差邊界的挖掘式［］。事實上，大量數(shù)據(jù)以數(shù)據(jù)流的形式產(chǎn)生［］，如方法，該算法跟蹤項集支持度變化，它以項集支持度日志數(shù)據(jù)、交易

3、數(shù)據(jù)等。數(shù)據(jù)流與傳統(tǒng)的靜態(tài)數(shù)據(jù)的穩(wěn)定性作為調(diào)整采樣窗口大小和采樣周期的依不同，它具有連續(xù)性、無序性、無界性及實時性的特據(jù)，從而以一個較大的概率保證項集支持度誤差有點［］，要求挖掘算法能夠?qū)崟r地反映模式的變化。上界。面向數(shù)據(jù)流的頻繁項集挖掘已成為研究熱點之一。與靜態(tài)環(huán)境不同，數(shù)據(jù)流自身特點通常迫使挖掘算問題背景與定義法對數(shù)據(jù)最多掃描一遍，且不能保存全部歷史數(shù)據(jù)，同時對其處理速度的要求也較為嚴(yán)格，而且項集組設(shè)IU={x，x，?，xI}為由全體項目x（i

4、理集。具有I個項目的項集稱為I-項集。事務(wù)為一速度之間取得平衡。二元組（tid，Y），其中tid為事務(wù)索引，Y為一項集。相關(guān)算法基本可以分為兩類，即以若事務(wù)T的項集Y為項集X的超集，即Y#X，則［］、［］為代表的具有確定誤差邊界的算稱事務(wù)T支持項集X。法，以及以［］、［］為代表的利用概率邊界數(shù)據(jù)流由不斷到達的事務(wù)構(gòu)成，一般假設(shè)它是（如邊界），在一定概率下具有誤差邊界的無限的。一事務(wù)流可視為一個窗口W=算法。這些算法在一定程度上緩解了時空復(fù)雜性，［T，T，?，T!］，其中!為當(dāng)前時刻。一個項集X然而前一類算法通常會引入過多的次頻繁項集，從在窗口W內(nèi)的頻度Fre（gX）是指W內(nèi)支持X的

5、事"國家自然科學(xué)基金（），國家科技成果重點推廣計劃（）和北京市自然科學(xué)基金（）資助項目。!男，年生，博士生；研究方向：數(shù)據(jù)挖掘；聯(lián)系人，：（收稿日期：）——高技術(shù)通訊年月第卷第期務(wù)數(shù)。項集在窗口內(nèi)的支持度定義為（）小，當(dāng)負荷過載時算法根據(jù)過載情況確定采樣率，以（），其中為中的事務(wù)總數(shù)。若采樣集代替事務(wù)流，直到負載下降。這類方法試圖（），則稱為中的頻繁項集，其中（以部分樣本代表數(shù)據(jù)流整體，然而項集支持度一般）為用戶預(yù)設(shè)的最小支持度閾值。是不穩(wěn)定的，因此難以設(shè)計合理的采樣方法，從而輸給定事務(wù)流與最小支持度閾值，數(shù)據(jù)流頻繁出結(jié)果精度較低。項集挖掘可以歸結(jié)為盡可能準(zhǔn)確地找出窗口中的所有頻繁

6、項集及其支持度。大量理論分析與實踐算法理論基礎(chǔ)證明，在數(shù)據(jù)流中無法設(shè)計高效且精確的頻繁項集挖掘方法。因此一般采取輸出近似結(jié)果的變通方!"周期采樣概率誤差邊界式，即算法僅給出項集支持度的估計值（），而為應(yīng)對數(shù)據(jù)流環(huán)境中高速、持續(xù)產(chǎn)生的事務(wù)，一該項集的真實支持度是（），兩者一般不同。目些算法采取隨機采樣等策略，并利用，前有兩類方法：（）估計支持度滿足（）等概率邊界，以部分事務(wù)近似數(shù)據(jù)流整體。（）!，即其具有確定邊界!；（）估計支持度為方便討論，在此給出下列引理使用的部分假設(shè)：設(shè)滿足{（）（）!}"，即誤差（，，?，）為一系列獨立的服從分布超過邊界!的概率具有確定下界"。由于項集頻的隨機

7、變量，概率｛｝，隨機變量繁性不穩(wěn)定，算法不僅需要維護當(dāng)前頻繁項集的支服從二項分布。實數(shù)!，"是常量，這里分別持度，還要維護支持度大于!的項集，即次頻繁表示支持度誤差上界與失敗概率上屆，為估計項集，其很可能變?yōu)轭l繁。支持度。［］是第一類方法中最具代表性引理"（邊界［］）對任意!（，），的。它將事務(wù)流劃分為一系列桶，每個桶包含下列不等式成立：「!個事務(wù)，!為誤差上界，結(jié)構(gòu)維護項集信{(!)}!（）息，項集的信息由三元組（，（），（））表達，其中（）為插入后的頻度，（）{(