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

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

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

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

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