大規(guī)模數(shù)據(jù)集高效數(shù)據(jù)挖掘算法研究.pdf

1、信息技術(shù)的飛速發(fā)展以及廣泛應(yīng)用使得企業(yè)、政府部門以及其他各種形式的組織積累了大量的數(shù)據(jù)。過去簡(jiǎn)單的查詢、統(tǒng)計(jì)技術(shù)僅僅能對(duì)數(shù)據(jù)進(jìn)行基本的處理，不能進(jìn)行更高層次的分析，從而自動(dòng)和智能地將待處理的數(shù)據(jù)轉(zhuǎn)化為有用的知識(shí)。數(shù)據(jù)挖掘正是在這樣的背景之下得到廣泛重視和深入研究并取得重大進(jìn)展的重要研究領(lǐng)域。數(shù)據(jù)挖掘(DataMining)是一個(gè)從數(shù)據(jù)中提取隱含在其中的、人們事先不知道的、具有潛在價(jià)值的知識(shí)的過程。數(shù)據(jù)挖掘被稱為未來信息處理的骨干技術(shù)之一

2、。目前，數(shù)據(jù)挖掘不僅被許多研究人員看作是模式識(shí)別以及機(jī)器學(xué)習(xí)等領(lǐng)域的重要研究課題之一，而且被許多產(chǎn)業(yè)界人士看作是一個(gè)能帶來巨大回報(bào)的重要研究領(lǐng)域。數(shù)據(jù)是相當(dāng)龐雜的，但是從中發(fā)現(xiàn)的模式、知識(shí)卻是非常有意義的，并能產(chǎn)生一定的經(jīng)濟(jì)效益。
　　 隨著信息技術(shù)更進(jìn)一步的發(fā)展，數(shù)據(jù)庫應(yīng)用的規(guī)模、范圍不斷地?cái)U(kuò)大，加之?dāng)?shù)據(jù)采集技術(shù)的更新，企業(yè)和政府利用計(jì)算機(jī)管理事務(wù)能力的增強(qiáng)，產(chǎn)生了更加龐大的大規(guī)模數(shù)據(jù)集。大規(guī)模數(shù)據(jù)集的出現(xiàn)使得有些原本有效的數(shù)

3、據(jù)挖掘算法在處理這樣的數(shù)據(jù)集時(shí)出現(xiàn)了很多新的問題，有待進(jìn)一步研究加以解決。比如原本很多數(shù)據(jù)挖掘算法在數(shù)據(jù)集規(guī)模較小時(shí)尚能取得不錯(cuò)的挖掘結(jié)果。但是針對(duì)大規(guī)模數(shù)據(jù)集，計(jì)算量太大以至于不能在可接受的時(shí)間內(nèi)獲得挖掘結(jié)果。甚至?xí)霈F(xiàn)由于大規(guī)模數(shù)據(jù)集無法整體讀入內(nèi)存或者是算法執(zhí)行過程中對(duì)內(nèi)存的占用超過系統(tǒng)可用內(nèi)存，而使得許多原本有效的挖掘算法不能成功執(zhí)行的情況。為了提高挖掘效率而采用的一些技術(shù)手段比如采樣、特征概括等等又使挖掘結(jié)果的質(zhì)量產(chǎn)生了一定程

4、度的下降。本文在對(duì)現(xiàn)有數(shù)據(jù)挖掘算法相關(guān)研究進(jìn)行總結(jié)的基礎(chǔ)之上，著重針對(duì)在處理大規(guī)模數(shù)據(jù)集時(shí)關(guān)聯(lián)規(guī)則挖掘算法的內(nèi)存瓶頸問題以及聚類算法的挖掘質(zhì)量和效率較低的問題進(jìn)行了詳細(xì)的分析和研究。論文的研究工作主要包含以下幾個(gè)方面:
　　 (1)介紹了數(shù)據(jù)挖掘領(lǐng)域的聚類以及關(guān)聯(lián)規(guī)則挖掘的重要研究成果。追蹤了現(xiàn)有大規(guī)模數(shù)據(jù)集挖掘的聚類以及關(guān)聯(lián)規(guī)則挖掘研究的最新進(jìn)展、現(xiàn)存的關(guān)鍵問題以及發(fā)展方向。在研究總結(jié)的基礎(chǔ)之上，對(duì)比了現(xiàn)有算法的特點(diǎn)以及各自的

5、優(yōu)缺點(diǎn)，得出了現(xiàn)在該領(lǐng)域所面臨的新挑戰(zhàn)。
　　 (2)針對(duì)大規(guī)模數(shù)據(jù)集關(guān)聯(lián)規(guī)則挖掘時(shí)的內(nèi)存瓶頸問題，提出了一種基于磁盤表存儲(chǔ)FPTREE的大規(guī)模數(shù)據(jù)集關(guān)聯(lián)規(guī)則挖掘算法（disktableresidentfptreegrowth，簡(jiǎn)稱DTRFP—GROWTH）。該算法改進(jìn)FP-GROWTH,借助于輕量級(jí)數(shù)據(jù)庫在挖掘過程中對(duì)中間過程的FPTREE進(jìn)行了存儲(chǔ)，降低了內(nèi)存的占用，實(shí)現(xiàn)對(duì)大規(guī)模數(shù)據(jù)集、低用戶支持度的關(guān)聯(lián)規(guī)則挖掘。
　

6、　 (3)進(jìn)一步優(yōu)化存儲(chǔ)機(jī)制、提高挖掘效率，直接利用B+樹對(duì)磁盤FPTREE進(jìn)行部分存儲(chǔ)，提出了一種基于B+樹磁盤存儲(chǔ)部分FPTREE的大規(guī)模數(shù)據(jù)集關(guān)聯(lián)規(guī)則挖掘算法（diskresidentB+treefptreemining，簡(jiǎn)稱DRBFP_MINE）。該算法實(shí)現(xiàn)了部分FPTREE的B+樹索引，提高了FPTREE結(jié)點(diǎn)的存取效率，可在內(nèi)存不夠時(shí)進(jìn)行FPTREE的部分存儲(chǔ)，降低挖掘過程中的內(nèi)存占用。除此之外，該算法還進(jìn)一步優(yōu)化了FPTR

7、EE的存儲(chǔ)機(jī)制和存儲(chǔ)策略，不再對(duì)整個(gè)FPTREE進(jìn)行存儲(chǔ)，而是采用后進(jìn)先出的方式，自下而上地對(duì)FPTREE進(jìn)行部分存儲(chǔ)，進(jìn)一步提高了算法的執(zhí)行效率。
　　 (4)針對(duì)大規(guī)模數(shù)據(jù)集聚類挖掘結(jié)果質(zhì)量不高、不穩(wěn)定以及收斂較慢的問題，提出了一種基于標(biāo)記集指導(dǎo)的半監(jiān)督一遍掃描K均值聚類算法(semi-supervisedlabelsonescankmeans，簡(jiǎn)稱SSLOKmeans)。以往處理大規(guī)模數(shù)據(jù)集的聚類算法，由于受到核心算法的內(nèi)

8、在局限性以及為了處理大規(guī)模數(shù)據(jù)集而采用的特征概括以及采樣等技術(shù)的限制，往往會(huì)存在聚類結(jié)果質(zhì)量不高、聚類結(jié)果質(zhì)量不穩(wěn)定以及算法收斂較慢等問題，本研究工作吸收半監(jiān)督學(xué)習(xí)的思想，把LABELS標(biāo)記集和大規(guī)模數(shù)據(jù)集聚類框架進(jìn)行整合，提出了SSLOKmeans算法。該算法利用駐留主存的標(biāo)記集輔助指導(dǎo)整個(gè)聚類過程，使得大規(guī)模數(shù)據(jù)集的聚類效率以及聚類結(jié)果的質(zhì)量得到了進(jìn)一步的提高。
　　 (5)在前面的研究基礎(chǔ)之上，針對(duì)大規(guī)模數(shù)據(jù)集的概率聚類展

9、開研究，提出了一種基于部分約束信息的大規(guī)模數(shù)據(jù)集EM概率聚類算法(ScalableEMprobabilityclusteringalgorithmformassivedatasetsbasedonpartialconstraintsinformation，簡(jiǎn)稱PC—SEM)。前期的研究工作主要針對(duì)確定性聚類，即某個(gè)數(shù)據(jù)僅能唯一歸屬于某一個(gè)類別。但在實(shí)際工作的聚類過程中，很多情況下某一個(gè)對(duì)象會(huì)以一定的概率同時(shí)歸屬于幾個(gè)類別。反映到對(duì)應(yīng)的數(shù)

10、據(jù)集中往往表現(xiàn)為數(shù)據(jù)集分離得不是很明顯，存在一定程度的重疊。以往的概率聚類研究主要針對(duì)較小規(guī)模的數(shù)據(jù)集，在處理大規(guī)模數(shù)據(jù)集時(shí)往往會(huì)出現(xiàn)聚類結(jié)果質(zhì)量不穩(wěn)定、聚類結(jié)果質(zhì)量不高等問題，且算法收斂較慢，算法性能有待進(jìn)一步的提高。融入半監(jiān)督學(xué)習(xí)的思想，提出了PC_SEM算法。該算法利用可以通過數(shù)據(jù)集自動(dòng)獲取的部分約束信息指導(dǎo)聚類過程，使得大規(guī)模數(shù)據(jù)集概率聚類的效率以及聚類結(jié)果的質(zhì)量得到了進(jìn)一步的提高。
　　 本文對(duì)大規(guī)模數(shù)據(jù)集挖掘進(jìn)行的研