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

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

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

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

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

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

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

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

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