發(fā)布時間：2018-05-06 12:10

  本文選題：頻繁項(xiàng)集 + 事務(wù)約簡��； 參考：《華僑大學(xué)》2017年碩士論文

【摘要】：關(guān)聯(lián)規(guī)則最早是挖掘頻繁項(xiàng)集,以支持度為度量,挖掘數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集模式�？紤]到數(shù)據(jù)庫中每個項(xiàng)目在事務(wù)中可以出現(xiàn)多次,并且不同項(xiàng)目可以有不同的權(quán)重,頻繁項(xiàng)集被擴(kuò)展到高效用項(xiàng)集挖掘,高效用項(xiàng)集挖掘能使用用戶期望的效用度量方式挖掘出更符合用戶需求的結(jié)果。本文主要圍繞關(guān)聯(lián)規(guī)則中的頻繁項(xiàng)集挖掘算法與高效用項(xiàng)集挖掘算法的時間效率提升展開,具體內(nèi)容包括以下2個方面:1)基于事務(wù)約簡和2-項(xiàng)集支持度矩陣快速剪枝的Apriori改進(jìn)算法。首先自定義了保存頻繁1-項(xiàng)集的數(shù)據(jù)結(jié)構(gòu),計(jì)算候選項(xiàng)集支持度時,依據(jù)這個自定義的數(shù)據(jù)結(jié)構(gòu)決定掃描的事務(wù),之后引入事務(wù)約簡優(yōu)化,進(jìn)一步對數(shù)據(jù)庫中項(xiàng)目和事務(wù)進(jìn)行約簡,提出改進(jìn)的MR-Apriori算法。隨后,定義一種2-項(xiàng)集支持度矩陣,對候選項(xiàng)集進(jìn)行快速剪枝,提出了改進(jìn)后的MP-Apriori算法。再次,結(jié)合MR-Apriori和MP-Apriori算法改進(jìn)策略,提出了改進(jìn)的MRP-Apriori算法。最后,在mushroom和T10I4D100K進(jìn)行實(shí)驗(yàn),結(jié)果表明:改進(jìn)的MRApriori算法和改進(jìn)的MP-Apriori算法,運(yùn)行時間都比原Apriori算法減少,而結(jié)合這兩種改進(jìn)策略的MRP-Apriori算法運(yùn)行時間最短,從而最終驗(yàn)證了三種算法改進(jìn)的時間效率。2)基于數(shù)組偽投影和事務(wù)合并的頻繁高效用項(xiàng)集挖掘算法。在分析了單獨(dú)考慮支持度或效用值的缺陷后,本文提出一種基于數(shù)組偽投影數(shù)據(jù)結(jié)構(gòu)、遞歸構(gòu)造前綴項(xiàng)集的投影數(shù)據(jù)庫挖掘頻繁高效用項(xiàng)集的算法。算法將支持度和效用值這兩種度量手段同時考慮,挖掘數(shù)據(jù)庫中那些出現(xiàn)次數(shù)頻繁且效用值高的項(xiàng)目集合。為減小算法的搜索空間,提出了局部效用剪枝和子樹效用剪枝兩種剪枝方案,基于算法模型和上述剪枝方案提出FUIM-P算法。隨后,觀察到數(shù)據(jù)庫中有許多可以合并的事務(wù),根據(jù)FUIM-P算法的特點(diǎn),將這種合并被擴(kuò)展到投影數(shù)據(jù)庫,引入了事務(wù)(投影事務(wù))合并技術(shù)。同時,提出了一種自定義排序規(guī)則,以在線性時間內(nèi)找到滿足可以快速合并的條件的事務(wù),提出最終的FUIM-MP算法。最后在mushroom、chess和accident數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),結(jié)果表明:FUIM-P算法的運(yùn)行時間相比對比的FHIMA-ALL算法縮短,而加入了事務(wù)(投影事務(wù))合并技術(shù)的FUIM-MP算法則較前兩者時間效率有非常大的提升;另外,實(shí)驗(yàn)中mushroom、chess和accident數(shù)據(jù)集中大量可合并事務(wù)(投影事務(wù))數(shù)目也很好地證明了事務(wù)(投影事務(wù))合并提高算法運(yùn)行時間的有效性。
[Abstract]:Association rules are the earliest mining frequent itemsets, which are measured by support degree, and mining itemsets patterns that occur frequently in database. Considering that each item in the database can occur multiple times in a transaction and that different items can have different weights, frequent itemsets are extended to highly effective itemsets mining, High utility itemsets mining can use the expected utility metrics to extract the results that are more suitable to the users' needs. This paper mainly focuses on the time efficiency improvement of frequent itemset mining algorithm and high effective itemset mining algorithm in association rules. The specific contents include the following two aspects: 1) an improved Apriori algorithm based on transaction reduction and 2-item set support matrix fast pruning. Firstly, the data structure with frequent 1-itemsets is defined, and when the support degree of candidate itemsets is calculated, the scanned transactions are determined according to this self-defined data structure, and then the optimization of transaction reduction is introduced. Furthermore, the project and transaction in the database are reduced, and an improved MR-Apriori algorithm is proposed. Then, a 2-item set support matrix is defined, and the candidate item set is pruned quickly, and an improved MP-Apriori algorithm is proposed. Thirdly, an improved MRP-Apriori algorithm is proposed based on the improved strategy of MR-Apriori and MP-Apriori algorithm. Finally, the experiments on mushroom and T10I4D100K show that both the improved MRApriori algorithm and the improved MP-Apriori algorithm have less running time than the original Apriori algorithm, but the MRP-Apriori algorithm with these two improved strategies has the shortest running time. Finally, the improved time efficiency. 2) algorithm based on array pseudo projection and transaction merging for mining frequent and high effective itemsets is verified. After analyzing the defect of considering support degree or utility value separately, this paper presents an algorithm of mining frequent and high-utility item sets in projection database based on array pseudo projection data structure and recursively constructing prefix item set. The algorithm takes both support and utility measures into account to mine the set of items in the database that occur frequently and have high utility value. In order to reduce the search space of the algorithm, two kinds of pruning schemes, local utility pruning and sub-tree utility pruning, are proposed. The FUIM-P algorithm is proposed based on the algorithm model and the above pruning schemes. Then, it is observed that there are many transactions in the database that can be merged. According to the characteristics of the FUIM-P algorithm, the merging is extended to the projection database, and the technology of transaction merging is introduced. At the same time, a custom collation rule is proposed to find the transaction satisfying the condition of fast merging in linear time, and the final FUIM-MP algorithm is proposed. Finally, experiments are carried out on the mush roomless and accident datasets. The results show that the running time of the accident / FUIM-P algorithm is shorter than that of the contrast FHIMA-ALL algorithm, while the FUIM-MP algorithm which adds the transaction (projection transaction) merging technique has a great improvement on the time efficiency of the former two algorithms. In addition, the number of merge transactions (projection transactions) in mush room ess and accident datasets also proves the effectiveness of transaction merging to improve the running time of the algorithm.
【學(xué)位授予單位】：華僑大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.13

【相似文獻(xiàn)】

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

1 馬安光;;棋子問題的算法分析——2003年第11期題解[J];程序員;2004年01期

2 馮舜璽;;新書推薦:《算法分析導(dǎo)論》[J];計(jì)算機(jī)教育;2006年05期

3 張力,慕曉冬;計(jì)算機(jī)算法分析淺談[J];武警工程學(xué)院學(xué)報(bào);2002年04期

4 馬安光;;飛彈問題的算法分析——2003年第10期題解[J];程序員;2003年12期

5 蘇運(yùn)霖;;《算法分析導(dǎo)論》評介[J];計(jì)算機(jī)教育;2006年07期

6 朱力強(qiáng);;培養(yǎng)學(xué)生創(chuàng)新思維與能力的算法分析案例[J];計(jì)算機(jī)與信息技術(shù);2007年11期

7 汪菊琴;;幾種常見特殊方陣的算法分析與實(shí)現(xiàn)[J];無錫職業(yè)技術(shù)學(xué)院學(xué)報(bào);2009年05期

8 李涵;;“算法分析與設(shè)計(jì)”課程教學(xué)改革和實(shí)踐[J];中國電力教育;2010年16期

9 劉寧;管濤;;淺析案例教學(xué)法在算法分析與設(shè)計(jì)課程中的應(yīng)用[J];科技風(fēng);2011年07期

10 胡峰;王國胤;;“算法分析與設(shè)計(jì)”教學(xué)模式探索[J];當(dāng)代教育理論與實(shí)踐;2011年12期

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

1 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

2 周顥;劉振華;趙保華;;構(gòu)造型的D~2FA生成算法[A];中國通信學(xué)會通信軟件技術(shù)委員會2009年學(xué)術(shù)會議論文集[C];2009年

3 賴桃桃;馮少榮;張東站;;一種基于劃分和密度的快速聚類算法[A];第二十五屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（一）[C];2008年

4 劉遠(yuǎn)新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺下物流運(yùn)輸配送系統(tǒng)算法分析[A];第二十六屆中國控制會議論文集[C];2007年

5 王樹西;白碩;姜吉發(fā);;模式合一的“減首去尾”算法[A];第二屆全國學(xué)生計(jì)算語言學(xué)研討會論文集[C];2004年

6 王萬青;張曉輝;;改進(jìn)的A~*算法的高效實(shí)現(xiàn)[A];2009全國測繪科技信息交流會暨首屆測繪博客征文頒獎?wù)撐募痆C];2009年

7 孫煥良;邱菲;劉俊嶺;朱葉麗;;IncSNN——一種基于密度的增量聚類算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報(bào)告篇）[C];2006年

8 韓建民;岑婷婷;于娟;;實(shí)現(xiàn)敏感屬性l-多樣性的l-MDAV算法[A];第二十七屆中國控制會議論文集[C];2008年

9 張悅;尤楓;趙瑞蓮;;利用蟻群算法實(shí)現(xiàn)基于程序結(jié)構(gòu)的主變元分析[A];第五屆中國測試學(xué)術(shù)會議論文集[C];2008年

10 王旭東;劉渝;鄧振淼;;正弦波頻率估計(jì)的修正Rife算法及其FPGA實(shí)現(xiàn)[A];全國第十屆信號與信息處理、第四屆DSP應(yīng)用技術(shù)聯(lián)合學(xué)術(shù)會議論文集[C];2006年

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

1 科文;VIXD算法分析Web異常[N];中國計(jì)算機(jī)報(bào);2008年

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

1 魏哲學(xué);樣本斷點(diǎn)距離問題的算法與復(fù)雜性研究[D];山東大學(xué);2015年

2 劉春明;基于增強(qiáng)學(xué)習(xí)和車輛動力學(xué)的高速公路自主駕駛研究[D];國防科學(xué)技術(shù)大學(xué);2014年

3 張敏霞;生物地理學(xué)優(yōu)化算法及其在應(yīng)急交通規(guī)劃中的應(yīng)用研究[D];浙江工業(yè)大學(xué);2015年

4 李紅;流程挖掘算法研究[D];云南大學(xué);2015年

5 卜晨陽;演化約束優(yōu)化及演化動態(tài)優(yōu)化求解算法研究[D];中國科學(xué)技術(shù)大學(xué);2017年

6 陳拉明;基于非凸優(yōu)化的稀疏重建理論與算法[D];清華大學(xué);2016年

7 劉新旺;多核學(xué)習(xí)算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

8 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學(xué);2006年

9 曾國強(qiáng);改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問題中的應(yīng)用研究[D];浙江大學(xué);2011年

10 肖永豪;蜂群算法及在圖像處理中的應(yīng)用研究[D];華南理工大學(xué);2011年

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

1 黃廈;基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題研究[D];昆明理工大學(xué);2015年

2 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學(xué);2015年

3 趙官寶;基于位表的關(guān)聯(lián)規(guī)則挖掘算法研究[D];昆明理工大學(xué);2015年

4 殷文華;移動容遲網(wǎng)絡(luò)中基于社會感知的多播分發(fā)算法研究[D];內(nèi)蒙古大學(xué);2015年

5 徐翔燕;人工魚群優(yōu)化算法及其應(yīng)用研究[D];西南交通大學(xué);2015年

6 李德福;基于小世界模型的啟發(fā)式尋路算法研究[D];華中師范大學(xué);2015年

7 鄭海彬;一種面向MAPREDUCE的DATASHUFFLE的優(yōu)化方法[D];蘇州大學(xué);2015年

8 趙曉寒;輪換步長PSO算法及SMVSC參數(shù)優(yōu)化[D];沈陽理工大學(xué);2015年

9 安豐洋;基于無線網(wǎng)絡(luò)的廣播算法研究[D];曲阜師范大學(xué);2015年

10 李智明;基于改進(jìn)FastICA算法的混合語音盲分離[D];上海交通大學(xué);2015年

，

本文編號：1852262