[發(fā)明專利]數(shù)據(jù)流中帶權(quán)值頻繁項(xiàng)挖掘方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 200910092805.2
• 申請(qǐng)日: 2009-09-08
• 公開(kāi)（公告）號(hào): CN101650730A
• 公開(kāi)（公告）日: 2010-02-17
• 發(fā)明（設(shè)計(jì)）人: 張玉;張永錚
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京泛華偉業(yè)知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 王 勇

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

本發(fā)明涉及數(shù)據(jù)挖掘領(lǐng)域，特別涉及一種數(shù)據(jù)流中帶權(quán)值頻繁項(xiàng)挖掘 方法和系統(tǒng)。

背景技術(shù)

數(shù)據(jù)流是一個(gè)隨時(shí)間演化的無(wú)窮的數(shù)據(jù)序列，在日常生活的各個(gè)方面 都有廣泛的應(yīng)用，而帶權(quán)值頻繁項(xiàng)挖掘則是數(shù)據(jù)流的其中一種典型應(yīng)用。 所謂的帶權(quán)值頻繁項(xiàng)是指在數(shù)據(jù)集合中超過(guò)一定閾值的數(shù)據(jù)項(xiàng)，假設(shè)一個(gè) 數(shù)據(jù)集合中所有數(shù)據(jù)項(xiàng)的權(quán)值總和N，給定支持度s∈(0，1)，則所有權(quán)值 超過(guò)sN的數(shù)據(jù)項(xiàng)被稱為頻繁項(xiàng)。帶權(quán)值頻繁項(xiàng)挖掘則是指從某一數(shù)據(jù)集 合(如數(shù)據(jù)流)的諸多數(shù)據(jù)項(xiàng)中找出滿足一定條件的帶權(quán)值頻繁項(xiàng)。在數(shù) 據(jù)流中實(shí)現(xiàn)帶權(quán)值頻繁項(xiàng)挖掘具有廣泛的應(yīng)用前景，尤其用于解決有限計(jì) 算資源條件下頻繁項(xiàng)的近似統(tǒng)計(jì)和挖掘問(wèn)題。例如，傳感器網(wǎng)絡(luò)中監(jiān)測(cè)信 號(hào)、互聯(lián)網(wǎng)中IP數(shù)據(jù)包流量、Web服務(wù)器上用戶點(diǎn)擊記錄、電信公司通 話記錄等的統(tǒng)計(jì)與挖掘。

與傳統(tǒng)的數(shù)據(jù)庫(kù)不同，數(shù)據(jù)流具有數(shù)據(jù)無(wú)窮性的特點(diǎn)。數(shù)據(jù)流的這一特 點(diǎn)導(dǎo)致其數(shù)據(jù)無(wú)法得到全部保存，因此對(duì)數(shù)據(jù)流數(shù)據(jù)的處理只能一次完 成，無(wú)法反復(fù)進(jìn)行。這也為帶權(quán)值頻繁項(xiàng)挖掘在數(shù)據(jù)流中的實(shí)現(xiàn)較在傳統(tǒng) 數(shù)據(jù)庫(kù)環(huán)境的實(shí)現(xiàn)帶來(lái)了更大的挑戰(zhàn)。近年來(lái)，研究者對(duì)數(shù)據(jù)流中帶權(quán)值 頻繁項(xiàng)挖掘技術(shù)展開(kāi)了大量研究工作，并取得了積極成果。

在參考文獻(xiàn)1“Approximate?frequency?counts?over?data?streams.In： Proceedings?of?the?28th?international?conference?on?Very?Large?Data?Bases. Hong?Kong，China，2002.346-357”中，G.Manku等人提出了一種被稱為 Lossy?Counting的頻繁項(xiàng)挖掘算法。該算法把數(shù)據(jù)流分成若干個(gè)連續(xù)到來(lái) 的、且數(shù)據(jù)項(xiàng)個(gè)數(shù)相等的數(shù)據(jù)塊，并根據(jù)數(shù)據(jù)項(xiàng)所屬數(shù)據(jù)類型的不同進(jìn)行 分別統(tǒng)計(jì)。數(shù)據(jù)項(xiàng)到來(lái)時(shí)，首先查詢是否有計(jì)數(shù)器監(jiān)視該數(shù)據(jù)項(xiàng)所屬數(shù)據(jù) 類型，有則相應(yīng)計(jì)數(shù)器值加1，沒(méi)有就創(chuàng)建新的計(jì)數(shù)器來(lái)監(jiān)視該數(shù)據(jù)項(xiàng)所 屬數(shù)據(jù)類型；然后判斷是否到達(dá)數(shù)據(jù)塊邊界，到達(dá)邊界則釋放部分計(jì)數(shù)器， 這些計(jì)數(shù)器滿足計(jì)數(shù)值與計(jì)數(shù)器創(chuàng)建時(shí)所在數(shù)據(jù)塊編號(hào)之和小于當(dāng)前數(shù) 據(jù)塊編號(hào)的限制條件。因?yàn)樾枰€性掃描一遍所有的計(jì)數(shù)器，因此，參考 文獻(xiàn)1所披露方法對(duì)單數(shù)據(jù)項(xiàng)的最壞更新時(shí)間將會(huì)達(dá)到當(dāng)誤差ε較小 時(shí)，更新時(shí)間會(huì)較長(zhǎng)，影響處理性能。

在參考文獻(xiàn)2“An?integrated?efficient?solution?for?computing?frequent?and top-k?elements?in?data?streams.ACM?Transactions?on?Database?Systems (TODS)，2006，31(3)：1095-1133”中，A.Metwally等人提出了一種被稱為Space Saving的頻繁項(xiàng)挖掘算法。在該算法中，對(duì)于數(shù)據(jù)流中到達(dá)的每個(gè)數(shù)據(jù)項(xiàng)， 若有相應(yīng)的計(jì)數(shù)器，則更新計(jì)數(shù)值；否則若沒(méi)有空閑的計(jì)數(shù)器，則代替計(jì)數(shù) 估計(jì)值最小(min)的數(shù)據(jù)項(xiàng)，并設(shè)其計(jì)數(shù)值為min+1，誤差為min。在 Stream-Summary中，所有具有相同計(jì)數(shù)值的項(xiàng)組成一個(gè)鏈表，這些項(xiàng)指向 共同的桶(parentBueket)，且parentBucket的值為指向它的所有項(xiàng)的計(jì)數(shù)值 的和，并按值排序。該方法始終需要維護(hù)計(jì)數(shù)值最小的數(shù)據(jù)項(xiàng)以便替換，即 便采用最快的數(shù)據(jù)結(jié)構(gòu)heap，每來(lái)一個(gè)數(shù)據(jù)項(xiàng)需要次操作，因此， 雖然該方法較參考文獻(xiàn)1方法對(duì)單數(shù)據(jù)項(xiàng)的最壞更新時(shí)間有所降低，可以達(dá) 到但當(dāng)誤差ε較小時(shí)，更新時(shí)間仍然會(huì)較長(zhǎng)，依然會(huì)對(duì)處理性能 產(chǎn)生影響。

發(fā)明內(nèi)容

本發(fā)明的目的是克服現(xiàn)有的帶權(quán)值頻繁項(xiàng)挖掘方法對(duì)單數(shù)據(jù)項(xiàng)的最壞 更新時(shí)間較長(zhǎng)，處理性能較低的缺陷，從而提供一種對(duì)單數(shù)據(jù)項(xiàng)的最壞更新 時(shí)間較短、處理性能較高的帶權(quán)值頻繁項(xiàng)挖掘方法。

為了實(shí)現(xiàn)上述目的，本發(fā)明提供了一種數(shù)據(jù)流中帶權(quán)值頻繁項(xiàng)挖掘方 法，數(shù)據(jù)流中的帶權(quán)值頻繁項(xiàng)動(dòng)態(tài)存儲(chǔ)在部分排序的流概要數(shù)據(jù)結(jié)構(gòu)中； 所述部分排序的流概要數(shù)據(jù)結(jié)構(gòu)包括多個(gè)按開(kāi)始值順序排列的桶，所述桶 還包括有由條目通過(guò)雙向循環(huán)鏈表所構(gòu)成的組；所述桶中的條目包括數(shù)據(jù) 項(xiàng)名稱、計(jì)數(shù)器值以及計(jì)數(shù)器的最大可能誤差，所述條目的計(jì)數(shù)器值大于 所在桶的開(kāi)始值而小于或等于所在桶的開(kāi)始值與桶范圍系數(shù)之和；該方法 包括：