基于立方體的復(fù)雜查詢聚集方法研究.pdf

1、數(shù)據(jù)挖掘（Data Mining）是二十世紀(jì)九十年代新興發(fā)展起來的一門交叉學(xué)科，它是指從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其它信息庫中的大量數(shù)據(jù)中挖掘有趣知識的過程，因此又稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KDD: Knowledge Discovery in Database）。 數(shù)據(jù)挖掘的一個(gè)主要特點(diǎn)就是其數(shù)據(jù)對象是大型數(shù)據(jù)集或信息庫，如數(shù)據(jù)倉庫或大型交易數(shù)據(jù)庫等。數(shù)據(jù)（倉）庫的基本特點(diǎn)是數(shù)據(jù)的多維特性，即用多個(gè)維屬性描述數(shù)據(jù)對象的多個(gè)特征。根

2、據(jù)數(shù)據(jù)挖掘任務(wù)對數(shù)據(jù)分析的復(fù)雜程度，可以分為單維數(shù)據(jù)分析技術(shù)和多維數(shù)據(jù)分析技術(shù)。單維數(shù)據(jù)分析是只取數(shù)據(jù)庫中某個(gè)屬性進(jìn)行分析，如傳統(tǒng)的關(guān)聯(lián)規(guī)則就是只對交易數(shù)據(jù)庫中的商品ID 進(jìn)行分析，得出購買商品之間的關(guān)聯(lián)特性。而多維數(shù)據(jù)分析是對數(shù)據(jù)庫中的多個(gè)維屬性同時(shí)進(jìn)行分析，得出潛在有趣的知識和規(guī)則。由于多維屬性潛藏著比單維屬性更豐富的信息，因此多維數(shù)據(jù)分析已成為數(shù)據(jù)挖掘技術(shù)的一個(gè)重要研究課題，許多重要的數(shù)據(jù)分析工具和決策支持系統(tǒng)都建立在多維數(shù)據(jù)之上

3、，如聯(lián)機(jī)分析處理（OLAP: On-Line Analytic Processing）和聯(lián)機(jī)分析挖掘（ＯLAM：On-Line AnalyticMining），多維數(shù)據(jù)挖掘（MDDM：Multi-dimensional Data Mining）。而且，越來越多的數(shù)據(jù)挖掘任務(wù)也從最初的單維數(shù)據(jù)分析發(fā)展到了多維數(shù)據(jù)分析，如多維關(guān)聯(lián)規(guī)則，多維聚類，多維數(shù)據(jù)的孤立點(diǎn)分析等。 眾多的多維分析技術(shù)中，建立在多維數(shù)據(jù)模型——立方體之上的多粒度

4、聚集方法研究從一開始就受到了廣泛的關(guān)注。立方體是多維數(shù)據(jù)的有效模型，用于對多維數(shù)據(jù)建模和數(shù)據(jù)聚集（匯總）?；诹⒎襟w的查詢實(shí)現(xiàn)是決策支持系統(tǒng)的核心功能，其主要通過對多維數(shù)據(jù)不同角度不同層次的數(shù)據(jù)分析為實(shí)現(xiàn)快速信息獲取提供支持。立方體查詢技術(shù)中的核心部分就是多粒度上的有效聚集。因此，目前國際國內(nèi)都對立方體上多粒度聚集的查詢實(shí)現(xiàn)進(jìn)行了相關(guān)的研究，產(chǎn)生了許多基于立方體的聚集計(jì)算的有效實(shí)現(xiàn)算法。 但是，較多的研究只是集中于僅含簡單查詢?nèi)?/p>

5、務(wù)（如1 個(gè)查詢）的立方體（稱簡單立方體）聚集技術(shù)實(shí)現(xiàn)；而含復(fù)雜查詢?nèi)蝿?wù)（如多個(gè)查詢）的立方體（又稱復(fù)雜立方體或多特征方）聚集的實(shí)現(xiàn)技術(shù)則研究得較少。信息是競爭取勝的武器，基于立方體的復(fù)雜查詢能夠給用戶同時(shí)提供更詳盡更全面的信息，因此將成為用戶查詢需求的趨勢，基于立方體的復(fù)雜查詢的聚集技術(shù)也將是立方體技術(shù)發(fā)展的方向所在。 目前，僅有少量的研究文獻(xiàn)涉及復(fù)雜立方體查詢的實(shí)現(xiàn)。文獻(xiàn)[1]提出了復(fù)雜立方體查詢的擴(kuò)展SQL 語言實(shí)現(xiàn)，[2

6、]中提出分布和代數(shù)型復(fù)雜立方體查詢的計(jì)算算法，算法基于相應(yīng)的分布型(代數(shù)型)簡單立方體查詢算法。涉及復(fù)雜立方體查詢的其他少量文獻(xiàn)，同樣只涉及分布型。國內(nèi)外的研究中尚沒有整體型復(fù)雜立方體查詢的有效算法，同時(shí)也沒有能充分利用復(fù)雜立方體查詢的內(nèi)在特點(diǎn)提出更有效的復(fù)雜立方體查詢聚集方法。 目前，立方體技術(shù)中涉及部分粒度的聚集計(jì)算的也還是集中在簡單立方體查詢，但還沒有復(fù)雜立方體查詢中的部分粒度研究。完全粒度計(jì)算優(yōu)點(diǎn)是對數(shù)據(jù)能全方位多角度地

7、觀察和分析，缺點(diǎn)是計(jì)算代價(jià)太大，沒有給用戶選擇的余地。相對于完全粒度計(jì)算，部分粒度上的聚集計(jì)算和查詢實(shí)現(xiàn)是適應(yīng)用戶個(gè)性化查詢的要求，符合信息查詢的多樣化趨勢。 新的多數(shù)據(jù)庫挖掘思想保持了數(shù)據(jù)的分布式存儲(chǔ)特性，局部挖掘，綜合分析，已經(jīng)成為數(shù)據(jù)挖掘技術(shù)發(fā)展的一個(gè)新熱點(diǎn)?；谶@個(gè)趨勢，為多數(shù)據(jù)庫挖掘服務(wù)的多立方體聯(lián)合聚集的思想應(yīng)運(yùn)而生，這也是數(shù)據(jù)挖掘技術(shù)和數(shù)據(jù)庫技術(shù)發(fā)展的要求。 基于以上所述，以基于立方體的復(fù)雜查詢的聚集計(jì)算方

8、法為研究重點(diǎn)，具體工作包含以下幾點(diǎn)： 第一，提出一種整體型復(fù)雜立方體查詢的計(jì)算方法，以部分分布聚集特性為主，結(jié)合冰山查詢（Iceberg Query）技術(shù)和Cache 重用技術(shù)，并綜合此三策略生成PDIC 算法。該算法能有效實(shí)現(xiàn)整體型復(fù)雜立方體查詢的聚集計(jì)算，與樸素方法相比，效率提高顯著。實(shí)驗(yàn)在模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)集上進(jìn)行，實(shí)驗(yàn)結(jié)果顯示了提出方法的可行性和高效性。 第二，提出了基于Cache 重用的有依賴聚集的復(fù)雜立方體查

9、詢實(shí)現(xiàn)方法。對復(fù)雜查詢中存在的三種依賴聚集，相應(yīng)提出以Cache 重用技術(shù)為主的三種解決方法，提出的方法與傳統(tǒng)計(jì)算方法相比，能有效節(jié)省內(nèi)存空間，有效提高聚集速度。而且，提出的方法對分布、代數(shù)和整體型三類復(fù)雜立方體查詢均適用。 第三，提出兩種復(fù)雜立方體查詢進(jìn)一步發(fā)展的研究內(nèi)容，包含部分（可選）粒度的復(fù)雜立方體查詢聚集方法研究框架和為多數(shù)據(jù)庫挖掘服務(wù)的多立方體聯(lián)合聚集的研究框架。 部分粒度的聚集計(jì)算方法以用戶的不同需求為前提