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

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

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

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

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

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

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

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

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

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

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