【摘要】：模式挖掘是數(shù)據(jù)挖掘技術(shù)中的一個(gè)重要的研究方向。對(duì)于傳統(tǒng)的頻繁模式挖掘和高效用模式挖掘,它們只能分別用來挖掘頻繁模式和高效用模式。在許多實(shí)際應(yīng)用場(chǎng)景下,這些傳統(tǒng)的單純的頻繁模式挖掘和效用模式挖掘模型的范疇會(huì)比較狹窄,不能滿足實(shí)際應(yīng)用中的多樣化分析需求,人們往往對(duì)頻繁度和效用值都感興趣,不單單只是頻繁度或者效用值。為了解決這個(gè)問題,本文提出同時(shí)考慮支持度和效用值,進(jìn)而挖掘更有價(jià)值的模式,其中一種就是高頻繁度低效用模式,并提出了一個(gè)新穎的算法 HFLUP(High Frequency and Low Utility Patterns Mining Algorithm)。挖掘高頻繁度低效用模式的最簡(jiǎn)單直接的方法就是分為兩階段來挖掘,首先利用頻繁模式挖掘算法來挖掘出所有的高頻繁度模式,然后再?gòu)倪@些高頻繁度模式中找出效用值低于用戶指定的最大效用閾值的模式,即最終得到高頻繁度低效用模式。但是這種兩階段的挖掘方式會(huì)產(chǎn)生大量的候選集,且需多次遍歷數(shù)據(jù)庫(kù),磁盤I/0開銷大,挖掘效率低。因此,為了避免這些問題,本文提出的高頻繁度低效用模式挖掘算法HFLUP是一個(gè)不產(chǎn)生候選集的單階段算法,并且只需要遍歷數(shù)據(jù)庫(kù)兩次。本文還提出了一個(gè)新的數(shù)據(jù)結(jié)構(gòu),叫做FUL,用來存儲(chǔ)模式的效用信息以及裁剪搜索空間的信息,通過FULs,算法可以高效地直接挖掘出高頻繁度低效用模式且無需產(chǎn)生候選模式。為了減小搜索空間,提高挖掘效率,提出了有效的且規(guī)模可控的效用下界裁剪策略以及通過lookahead策略預(yù)先確定高頻繁度低效用模式而無需遞歸枚舉。大量實(shí)驗(yàn)表明:所提出的兩個(gè)裁剪策略是有效且高效的,HFLUP算法在運(yùn)行時(shí)間和內(nèi)存消耗上大大優(yōu)于兩階段的高頻繁度低效用模式挖掘方法。本文的第二項(xiàng)工作是將所提出的算法并行化,以適應(yīng)海量大數(shù)據(jù)處理的要求,以克服單機(jī)的物理內(nèi)存局限所造成單機(jī)挖掘的低效率。本文采用云計(jì)算模式下的基于內(nèi)存的分布式計(jì)算框架Spark來實(shí)現(xiàn)算法的并行化,提出了基于Spark的并行高頻繁度低效用模式挖掘算法PHFLUPS(Parallel High Frequency and Low Utility Patterns Mining Algorithm Based on Spark),以便利用大規(guī)模分布式集群來并行挖掘大數(shù)據(jù)。對(duì)比實(shí)驗(yàn)表明,PHFLUPS算法比基于MapReduce的并行高頻繁度低效用模式挖掘算法效率更高,并且在大規(guī)模數(shù)據(jù)集上并行化算法要比單機(jī)HFLUP算法效率高。本文的思路和所提出的相關(guān)技術(shù)同樣適用于挖掘其他類型的模式,比如低頻繁度高效用模式。
【圖文】：

一個(gè)父ＲＤＤ的分區(qū)被多個(gè)子ＲＤＤ分區(qū)所使用。比方，ｆｉｌｔｅｒ操作是窄依賴，逡逑ｒｅｄｕｃｅＢｙＫｅｙ操作是寬依賴，而當(dāng)父ＲＤＤ不是基于Ｈａｓｈ策略分區(qū)的時(shí)候，ｊｏｉｎ操作逡逑也是寬依賴。圖４－２表示一些常見的窄依賴和寬依賴。圖中的每個(gè)圓角矩形表示一個(gè)逡逑ＲＤＤ，內(nèi)部每個(gè)實(shí)體矩形表示ＲＤＤ的一個(gè)分區(qū)。逡逑邐ｆｒ＝ｆｉ逡逑ｊ逡逑ｍａ邋ｐ，ｆｉｌｔｅｒ邐ｇｒｏｕ邋ｐＢｙ邋Ｋｅｙ／ｒｅｄｕ邋ｃｅＢｙ邋Ｋｅｙ逡逑—－ａ逡逑—邐—Ｅｍｕｉｒ逡逑、邐＾邋ｕｎｉｏｎ邐ｊ0ｉｎ逡逑窄依賴逡逑圖４－２常見的窄依賴和寬依賴逡逑窄依賴和寬依賴的的區(qū)別主要有兩個(gè)方面。首先，窄依賴可以在集群中的一個(gè)節(jié)逡逑點(diǎn)上以流水線的方式執(zhí)行多個(gè)轉(zhuǎn)換操作，這個(gè)節(jié)點(diǎn)可以單獨(dú)地計(jì)算出ＲＤＤ的一個(gè)分逡逑區(qū)，無需依賴其它的節(jié)點(diǎn)。比如，依次執(zhí)行ｍａｐ和ｕｎｉｏｎ操作，這兩個(gè)操作都是窄依逡逑１８逡逑

（ａ）邋Ｐｕｍｓｂ邐（ｂ）邋Ｃｏｎｎｅｃｔ逡逑圖７－２邋ＨＦＬＵＰＢａｓｅ、ＨＦＬＵＰＢａｓｅＡｎｄＬＢｕ在不同數(shù)據(jù)集中的運(yùn)行時(shí)間對(duì)比逡逑圖７－１表示ＨＦＬＵＰＢａｓｅ、ＨＦＬＵＰ—ｌｂｕ在不同數(shù)據(jù)集中構(gòu)造ＦＵＬ的次數(shù)，圖逡逑７－２表示ＨＦＬＵＰＢａｓｅ、ＨＦＬＵＰＢａｓｅＡｎｄＬＢＵ在不同數(shù)據(jù)集中的運(yùn)行時(shí)間。逡逑在圖７－１和圖７－２中，對(duì)于Ｐｕｍｓｂ數(shù)據(jù)集設(shè)置的最大效用閾值為０．９５５％，對(duì)于逡逑Ｃｏｎｎｅｃｔ數(shù)據(jù)集設(shè)置的最大效用閾值為１．８４３％。從圖７－１邋（ａ）的Ｐｕｍｓｂ數(shù)據(jù)集中，可逡逑以發(fā)現(xiàn)當(dāng)最小支持度閾值ＯＴ＞ｍ／ｐ；７邋＝邋７５％時(shí)，ＨＦＬＵＰＢａｓｅＡｎｄＬＢＵ構(gòu)造ＦＵＬ的次數(shù)為逡逑１１５０６８
【學(xué)位授予單位】：浙江工商大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 賴娟;金澎;洪艷偉;;一種改進(jìn)的壓縮頻繁模式挖掘算法[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年07期

2 劉君強(qiáng),潘云鶴;一種基于樹的頻繁模式挖掘算法[J];系統(tǒng)工程理論與實(shí)踐;2003年05期

3 李清勇 ,秦亮曦 ,施智平 ,史忠植;最大目標(biāo)頻繁模式挖掘算法研究[J];計(jì)算機(jī)工程與應(yīng)用;2004年33期

4 申展,江寶林,唐磊,胡運(yùn)發(fā);基于互關(guān)聯(lián)后繼樹的頻繁模式挖掘研究[J];計(jì)算機(jī)工程;2004年21期

5 戰(zhàn)立強(qiáng);劉大昕;;小波濾波在時(shí)間序列頻繁模式挖掘中的應(yīng)用[J];哈爾濱工程大學(xué)學(xué)報(bào);2008年01期

6 何海濤;張世玲;;基于矩陣的頻繁模式挖掘及更新算法[J];計(jì)算機(jī)科學(xué);2008年03期

7 高琳;覃桂敏;周曉峰;;圖數(shù)據(jù)中頻繁模式挖掘算法研究綜述[J];電子學(xué)報(bào);2008年08期

8 孟凡榮;宋春景;張磊;;一種新的多層頻繁模式挖掘算法[J];微計(jì)算機(jī)信息;2009年03期

9 孟彩霞;;頻繁模式挖掘的約束算法[J];智能系統(tǒng)學(xué)報(bào);2009年02期

10 潘立福;朱利晶;敖富江;杜靜;;基于樹搜索方式的頻繁模式挖掘綜述[J];計(jì)算機(jī)與信息技術(shù);2009年05期

相關(guān)會(huì)議論文 前10條

1 侯俊杰;李春平;;一種基于內(nèi)存索引的頻繁模式挖掘算法[A];第二十二屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2005年

2 任家東;孫亞非;郭盛;;基于約束的交互式頻繁模式挖掘算法[A];第二十四屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2007年

3 袁晴晴;樓宇波;周皓峰;汪衛(wèi);施伯樂;;基于圖論的頻繁模式挖掘[A];第十九屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2002年

4 史東輝;蔡慶生;張春陽(yáng);;一種新的數(shù)據(jù)挖掘多策略方法研究[A];第十七屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2000年

5 張弦;;數(shù)據(jù)挖掘在農(nóng)業(yè)中的應(yīng)用[A];紀(jì)念中國(guó)農(nóng)業(yè)工程學(xué)會(huì)成立30周年暨中國(guó)農(nóng)業(yè)工程學(xué)會(huì)2009年學(xué)術(shù)年會(huì)（CSAE 2009）論文集[C];2009年

6 魏順平;;教育數(shù)據(jù)挖掘:現(xiàn)狀與趨勢(shì)[A];信息化、工業(yè)化融合與服務(wù)創(chuàng)新——第十三屆計(jì)算機(jī)模擬與信息技術(shù)學(xué)術(shù)會(huì)議論文集[C];2011年

7 關(guān)清平;沉培輝;;概率網(wǎng)絡(luò)在數(shù)據(jù)挖掘上的應(yīng)用[A];科技、工程與經(jīng)濟(jì)社會(huì)協(xié)調(diào)發(fā)展——中國(guó)科協(xié)第五屆青年學(xué)術(shù)年會(huì)論文集[C];2004年

8 丁瑾;;基于Web數(shù)據(jù)挖掘的綜述[A];山西省科學(xué)技術(shù)情報(bào)學(xué)會(huì)學(xué)術(shù)年會(huì)論文集[C];2004年

9 聶茹;田森平;;Web數(shù)據(jù)挖掘及其在電子商務(wù)中的應(yīng)用[A];中南六省（區(qū)）自動(dòng)化學(xué)會(huì)第24屆學(xué)術(shù)年會(huì)會(huì)議論文集[C];2006年

10 李菊;王軍;;數(shù)據(jù)挖掘在客戶關(guān)系管理的應(yīng)用[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展·2007——全國(guó)第18屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集[C];2007年

相關(guān)重要報(bào)紙文章 前10條

1 本報(bào)記者褚寧;數(shù)據(jù)挖掘如“挖金”[N];解放日?qǐng)?bào);2002年

2 周蓉蓉;數(shù)據(jù)挖掘需要點(diǎn)想像力[N];計(jì)算機(jī)世界;2004年

3 □中國(guó)電信股份有限公司北京研究院 張舒博 □北京郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 牛琨;走出數(shù)據(jù)挖掘的誤區(qū)[N];人民郵電;2006年

4 《網(wǎng)絡(luò)世界》記者 王瑩;數(shù)據(jù)挖掘保險(xiǎn)業(yè)的新藍(lán)海[N];網(wǎng)絡(luò)世界;2012年

5 劉俊麗;基于地理化的網(wǎng)絡(luò)數(shù)據(jù)挖掘與分析提升投資有效性[N];人民郵電;2014年

6 本報(bào)記者 連曉東;數(shù)據(jù)挖掘：金融信息化新熱點(diǎn)[N];中國(guó)電子報(bào);2002年

7 本報(bào)記者 鳳小華 朱仁康;“數(shù)字挖掘軟件”引領(lǐng)中國(guó)信息化新浪潮[N];中國(guó)電子報(bào);2003年

8 本報(bào)記者　史延廷;“成功企業(yè)數(shù)據(jù)挖掘暨數(shù)量化管理論壇”在京舉辦[N];中國(guó)旅游報(bào);2002年

9 朱小寧;數(shù)據(jù)挖掘：信息化戰(zhàn)爭(zhēng)的基礎(chǔ)工程[N];解放軍報(bào);2005年

10 本報(bào)記者 王小平;從“大集中”走向數(shù)據(jù)挖掘[N];金融時(shí)報(bào);2002年

相關(guān)博士學(xué)位論文 前10條

1 屈盈飛;基于統(tǒng)計(jì)推理的復(fù)雜網(wǎng)絡(luò)廣義社團(tuán)檢測(cè)算法研究[D];重慶大學(xué);2017年

2 宋天恒;強(qiáng)化學(xué)習(xí)問題中的正則化最小二乘策略評(píng)價(jià)算法的研究[D];北京化工大學(xué);2016年

3 張麗娜;螢火蟲算法研究及其在船舶運(yùn)動(dòng)參數(shù)辨識(shí)中的應(yīng)用[D];哈爾濱工程大學(xué);2017年

4 申國(guó)偉;面向社會(huì)網(wǎng)絡(luò)的關(guān)系挖掘算法研究[D];哈爾濱工程大學(xué);2015年

5 趙嬪姣;混合信號(hào)的波達(dá)方向估計(jì)算法研究[D];哈爾濱工程大學(xué);2017年

6 潘果;混合智能算法及其在優(yōu)化問題中的應(yīng)用[D];湖南大學(xué);2017年

7 崔建華;基于消息傳遞算法的無線傳感器網(wǎng)絡(luò)定位算法研究[D];解放軍信息工程大學(xué);2017年

8 夏穎;WLAN室內(nèi)半監(jiān)督定位及指紋更新算法研究[D];哈爾濱工業(yè)大學(xué);2016年

9 于文杰;基于人工蜂群算法的無線傳感器網(wǎng)絡(luò)部署問題研究[D];電子科技大學(xué);2018年

10 黃小童;基于改進(jìn)蟻群算法的降質(zhì)圖像盲評(píng)價(jià)方法[D];武漢科技大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 常仲民;高頻繁度低效用模式挖掘算法及其在云計(jì)算下的實(shí)現(xiàn)研究[D];浙江工商大學(xué);2018年

2 施方林;人工蜂群算法的改進(jìn)及在空間聚類中的應(yīng)用[D];解放軍信息工程大學(xué);2017年

3 董琦t，

本文編號(hào)：2671480