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

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

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

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

【部分圖文】：

類別樹示例

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

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


本文編號(hào)：3244153