隨著信息技術(shù)的飛速發(fā)展,數(shù)據(jù)達(dá)到前所未有的規(guī)模體量。大規(guī)模的數(shù)據(jù)在給人們的日常生活、工作來了便利的同時也產(chǎn)生了許多問題,這主要體現(xiàn)在人類的數(shù)據(jù)收集、數(shù)據(jù)組織能力和數(shù)據(jù)處理能力之間存在非常大的差距,缺乏行之有效的數(shù)據(jù)分析和挖掘方法,人們無法充分利用收集到的數(shù)據(jù),從而導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。頻繁模式挖掘通常是大規(guī)模數(shù)據(jù)分析的第一步,多年以來都是數(shù)據(jù)挖掘領(lǐng)域里非�；钴S的一個研究主題。頻繁項集挖掘是頻繁模式挖掘中的一個重要任務(wù),頻繁項集挖掘是在給定數(shù)據(jù)集中挖掘支持度滿足預(yù)定義的最小支持度閾值的項集,通過挖掘數(shù)據(jù)集中的頻繁項集,能夠分析數(shù)據(jù)的關(guān)聯(lián)規(guī)則。傳統(tǒng)的頻繁項集挖掘方法存在一個問題是頻繁項集的數(shù)量非常龐大,計算和存儲這些頻繁項集都是一個不小的挑戰(zhàn),而且挖掘如此大量的頻繁項集通常是沒有必要的。針對這個問題不少科研學(xué)者提出了很多基于條件約束的頻繁項集,如閉頻繁項集挖掘、最大頻繁項集挖掘等。本論文通過對大量文獻(xiàn)的研究整理,詳細(xì)的介紹了頻繁項集挖掘的背景、發(fā)展以及研究現(xiàn)狀,分析了目前頻繁項集研究領(lǐng)域的熱點問題。論文在現(xiàn)有的研究基礎(chǔ)上提出了一種最大多樣頻繁項集的概念,最大多樣頻繁項集滿足最... 

【文章來源】：深圳大學(xué)廣東省

【文章頁數(shù)】：63 頁

【學(xué)位級別】：碩士

【部分圖文】：

類別樹示例

最大多樣頻繁項集挖掘算法研究18集中所有的最大頻繁項集（MFIs），F(xiàn)PMax算法挖掘到的最大頻繁項集存儲在候選集中（MFIscandidateset）。然后系統(tǒng)會使用輸入的類別樹CT數(shù)據(jù)來計算候選集中每一個最大頻繁項集的多樣性，關(guān)于項集的多樣性計算方法在2.2.1節(jié)中有詳細(xì)的介紹，計算出來的帶有多樣性的最大頻繁項集將放入結(jié)果隊列（ResultQueue）中。結(jié)果隊列是一個優(yōu)先隊列，它始終保持在隊列中的候選結(jié)果是按照其多樣性降序排列的。在計算出所有的最大頻繁項集的多樣性之后，就能夠取得所需要挖掘的Top-k最大多樣頻繁項集了，只需要取出在結(jié)果隊列中處于隊列前面的k個最大頻繁項集即可。從圖2所示的使用基礎(chǔ)算法挖掘最大多樣頻繁項集的架構(gòu)圖可知，基礎(chǔ)算法在挖掘最大多樣頻繁項集的時候會首先挖掘出給定交易數(shù)據(jù)集中所有的最大頻繁項集，然后會計算所有的最大頻繁項集的多樣性，進(jìn)而對所有的最大頻繁項集按照多樣性排序。在這一系列步驟中基礎(chǔ)算法均需要處理數(shù)據(jù)集中所有的最大頻繁項集，而事實上最終用戶關(guān)注的只是其中的k個最大頻繁項集，這就導(dǎo)致了基礎(chǔ)算法在挖掘最大多樣頻繁項集時效率不高，這也是本論文研究的基于邊界檢測的最大多樣頻繁項集挖掘算法需要解決的問題，該算法將在第3章中進(jìn)行詳細(xì)介紹。圖2最大多樣頻繁項集挖掘系統(tǒng)架構(gòu)2.5本章小結(jié)本章首先在2.1節(jié)中簡單地介紹了頻繁項集挖掘的一些基本概念，包括頻繁項集挖

最大多樣頻繁項集挖掘算法研究21當(dāng)用戶給定的最小支持度閾值σ=2，那么根據(jù)FP-tree的構(gòu)建算法，能夠得到如圖3所示的FP-tree。圖3FP-tree示例為了實現(xiàn)基于邊界檢測的最大多樣頻繁項集挖掘算法，本論文研究設(shè)計了一種FP*-tree的索引結(jié)構(gòu)，它是對FP-tree的一種改進(jìn)和擴(kuò)展。FP*-tree在原有的FP-tree的基礎(chǔ)上為headertable中的每一個項增加了一個倒排表(PostingList)，記headertable中項i的倒排表為L(i)。倒排表L(i)是在FP*-tree創(chuàng)建過程中動態(tài)生成的，它是由數(shù)據(jù)集中的某些項item及其出現(xiàn)次數(shù)counter構(gòu)成的二元組(item，counter)組成的集合；在該二元組中，item是和項i同時出現(xiàn)在同一交易記錄中的一個項，counter是表示在數(shù)據(jù)集中項item和項i同時出現(xiàn)的次數(shù)。因此，項i的倒排表L(i)中記錄了數(shù)據(jù)集中與項i同時出現(xiàn)的各個項及其同時出現(xiàn)的次數(shù)。例如，在圖5所示的FP*-tree中，項a的倒排表L(a)={(c,8),(e,6)}，表示項c與項a同時出現(xiàn)在8個交易數(shù)據(jù)集中，項e與項a同時出現(xiàn)在6個數(shù)據(jù)集中。這里需要說明的是當(dāng)項a與項b同時出現(xiàn)在一些交易記錄中時，項a與項c同時出現(xiàn)同時意味著項c與項a同時出現(xiàn)，但是FP*-tree不會同時在兩個項的倒排表中同時記錄另外一個項的出現(xiàn)，而是只在一個項中記錄另一個項的出現(xiàn)，例如在項a的倒排表中記錄二元組（c,8）。如果數(shù)據(jù)集中的項i′出現(xiàn)在項i的倒排表中，那么必然滿足以下兩個條件：I：rank(i′)<rank(i)II：T(i′)∩T(i)≠。其中，rank(i)表示headertable中的一個項i在headertable中的位置。headertable中


本文編號：3244153