海量數(shù)據(jù)上基于抽樣的模式挖掘研究.pdf

1、隨著云計(jì)算和移動(dòng)互聯(lián)網(wǎng)等概念越來(lái)越深入到普通人的生活當(dāng)中，大數(shù)據(jù)也隨著變得越來(lái)越深入人心。在當(dāng)今競(jìng)爭(zhēng)激烈的商業(yè)戰(zhàn)場(chǎng)上，誰(shuí)能掌握破解大數(shù)據(jù)的鑰匙，誰(shuí)就能在商業(yè)領(lǐng)域占得先機(jī)。然后，對(duì)于大數(shù)據(jù)算法的探索和研究還遠(yuǎn)遠(yuǎn)無(wú)法滿足人們想要從大量的信息中挖掘出有價(jià)值的知識(shí)的需求。因此，針對(duì)于大數(shù)據(jù)的數(shù)據(jù)挖掘算法的研究極為重要。
　　頻繁模式的挖掘是一個(gè)擁有大量研究群體的課題，同時(shí)也是非常有價(jià)值的研究課題。在過(guò)去的20年中，各種各樣的頻繁模式挖掘算

2、法存在，簡(jiǎn)而言之包括三類(lèi)，基于“候選集產(chǎn)生-測(cè)試”模式的Apriori算法及其擴(kuò)展算法，基于FP樹(shù)的模式增長(zhǎng)模式的FP-Growth算法及擴(kuò)展算法，垂直挖掘算法。然而，現(xiàn)存的這些頻繁模式挖掘算法存在的共同的短板，就是在數(shù)據(jù)量急劇增長(zhǎng)的今天，已經(jīng)無(wú)法滿足大數(shù)據(jù)量的挖掘需求，一個(gè)方面在內(nèi)存上無(wú)法存儲(chǔ)大數(shù)據(jù)量的信息，另一個(gè)方面數(shù)據(jù)量的提升會(huì)快速提升算法的運(yùn)行時(shí)間，無(wú)法滿足人們的實(shí)際要求。挖掘算法的效率依然有待提高，而針對(duì)大數(shù)據(jù)上的模式挖掘算法

3、還很少，探索大數(shù)據(jù)上的高效率的、有效的模式挖掘算法是有意義的。
　　本文改進(jìn)了直接抽樣算法，對(duì)抽樣結(jié)果做驗(yàn)證更新處理，同時(shí)改進(jìn)了兩步隨機(jī)抽樣過(guò)程，通過(guò)對(duì)概率閾值的控制來(lái)調(diào)節(jié)挖掘模式的長(zhǎng)度，從而達(dá)到在不明顯增大時(shí)間復(fù)雜度的情況下顯著提升其挖掘模式的有效性。通過(guò)只掃描一遍數(shù)據(jù)庫(kù)，挖掘有限條的頻繁模式。不再局限于以往數(shù)據(jù)挖掘算法中對(duì)模式空間中大于支持度閾值的頻繁模式進(jìn)行完整挖掘的思路，由此大大的提升了挖掘的效率。該方法不再滿足特定的支持

4、度閾值。通過(guò)實(shí)驗(yàn)我們可以看到，增強(qiáng)的直接抽樣方法能夠很好的改善算法的挖掘效果。
　　同時(shí)，我們提出了基于Map-Reduce的分布式的增強(qiáng)的兩步隨機(jī)抽樣算法，該算法通過(guò)A-RES/A-ExpJ算法來(lái)解決帶權(quán)值的抽樣問(wèn)題（WAS問(wèn)題），解決了在Map-Reduce框架下的抽樣問(wèn)題；通過(guò)Lossy Counting算法解決低頻項(xiàng)集的求解問(wèn)題，用以方便模式的驗(yàn)證過(guò)程。如此，通過(guò)兩個(gè)經(jīng)典的算法，將算法很好的移植到到Map-Reduce框架