基于聚類優(yōu)化的模糊OLAP查詢技術研究

(麗水學院工學院，浙江麗水，323000)

0 引 言

聯(lián)機分析處理(On Line Analytical Processing，OLAP)是一種多維的分析查詢方法，它能在數(shù)據(jù)倉庫的基礎上，提供“What if”的分析功能[1、2]。然而實際的分析過程中，用戶可能關心的是某一個范圍內(nèi)的聚集值，并不僅僅是某些具體維度的聚集值，對于超市海量數(shù)據(jù)的分析人員來說，對于不同年齡段的顧客購物情況進行分析，可能比根據(jù)每個年齡生成對應的顧客購物情況的報表更有意義;同樣，對于銀行貸款數(shù)據(jù)分析人員來說，按企業(yè)規(guī)模與利潤規(guī)模來進行分析更有意義[3，4]。這些查詢帶有一定的模糊性，無法直接在數(shù)據(jù)庫或多維數(shù)據(jù)集上實現(xiàn)，通過引入模糊查詢來解決這一問題，引起了研究者的廣泛關注。但是，在目前的研究中，對于模糊OLAP查詢的常用處理方法是先進行聚類，然后根據(jù)隸屬度函數(shù)進行計算[5]，但由于在計算的過程中對于許多隸屬度低的單元格也進行了聚類計算，導致效率不高，特別是在多個維與層次上都有模糊性的查詢要求時，其影響更加明顯?；谝陨戏治?，本文提出了基于過濾機制的模糊OLAP查詢優(yōu)化算法，其基本思路是在進行聚類計算時，對數(shù)據(jù)元組進行模糊隸屬度函數(shù)動態(tài)計算，盡早的發(fā)現(xiàn)并淘汰隸屬度過低的元組，從而提高查詢的整體效率。

1 模糊OLAP查詢及操作的形式化描述

本文對OLAP的模糊查詢中使用的相關概念及其計算公式進行詳細的形式化描述。

定義1(模糊值)模糊值fuzzy_v可用一個三元組＜VName，μ，λ ＞表示。其中VName為模糊值的概念，μ為隸屬度函數(shù)，λ為隸屬度閾值。

定義2(維模糊值)對于OLAP 多維數(shù)據(jù)集上的維D，假設其有k個層次，則這個維上的維模糊值fuzzy_D形式化描述如下:(v0，v1，…，vk)，其中vi(0≤i≤k)或者為一個確定的數(shù)值，或者為一個模糊值。

定義3(模糊OLAP查詢)對于某個OLAP 多維數(shù)據(jù)集，假設其有d個維，則這個OLAP 多維數(shù)據(jù)集上的模糊OLAP查詢fuzzy_v可以形式化描述為[fuzzy_D0，fuzzy_D1，…fuzzy_Dd]，其中fuzzy_Di(0≤i≤d)為維Di上的維模糊值。

由定義可知，模糊OLAP查詢是對傳統(tǒng)OLAP查詢定義的擴展，從而可以用統(tǒng)一的觀點來處理傳統(tǒng)的OLAP查詢與模糊OLAP查詢。同時在形式化定義模糊值、維模糊值及模糊OLAP查詢后，可以定義維值、維層次值及單元格與概念的匹配關系。

定義4(模糊值的匹配關系=f)對于某一個確定的值dv，其與模糊值fuzzy_v 匹配，記做dv=ffuzzy_v，，當且僅當μ(dv)≥λ，即隸屬度值大于閾值。

例如，對于上述的模糊值“兒童”概念，年齡值“15”與模糊值具有匹配關系(隸屬度為1)，而年齡值20 則與模糊值不具有匹配關系(隸屬度為0.67)。

定義5(維模糊值的隸屬度ud與匹配關系=D)對于某個確定的維值dD=(dv0，dv1，…，dvk)，其與某個維模糊值的隸屬度定義為:

如fuzzy_D中的某一個層次為確定值，則定義u(dvi)=1。其與fuzzy_D 匹配，記做dD=Dfuzzy_D，當且僅當μD≥min(λi)，即維模糊值的隸屬度大于維中模糊值的最小閾值。

定義6(模糊OLAP查詢的隸屬度與匹配關系=Q)對于某個單元格cell，其與某個模糊OLAP查詢fuzzy_q的隸屬度定義為:

其與fuzzy_q 匹配，記做cell=Qfuzzy_q，當且僅當對于這個單元格cell所有的維值dDi，均有dDi=Dfuzzy_Di。

由上面的定義可知，某個單元格與模糊OLAP查詢之間的隸屬度可以通過一系列的隸屬度函數(shù)進行運算得到，而單元格與模糊OLAP查詢之間的匹配與否可以根據(jù)隸屬度高低進行計算。

2 聚類策略選擇及優(yōu)化查詢算法描述

2.1 聚類策略的選擇

傳統(tǒng)的聚類分析種類繁多，但由于數(shù)據(jù)挖掘的處理對象是海量的高維數(shù)據(jù)集，又有許多相適應的新聚類算法被提出，如基于網(wǎng)格的聚類算法，基于密度的聚類算法以及模糊聚類算法等。實際上，在數(shù)據(jù)挖掘中，特別是在模糊OLAP查詢中，大多數(shù)對象并沒有嚴格的類屬性和隸屬關系，它們在屬性等方面存在著重疊性、交叉性，比較適合進行模糊劃分，因此數(shù)據(jù)挖掘中的聚類分析主要為模糊聚類分析。

在模糊聚類分析中，主要的聚類算法是模糊C-均值算法(FCM)。FCM算法是基于對目標函數(shù)的優(yōu)化基礎上的一種數(shù)據(jù)聚類方法，是通過目標函數(shù)的迭代優(yōu)化算法來實現(xiàn)對給定樣品集合的劃分，在本文提出的算法中采用FCM 聚類算法，其主要內(nèi)容如下所述。

對于一個給定的S 維數(shù)據(jù)集x={x1，x2，…，xn}，其函數(shù)定義為:

式中，c表示分類數(shù)，n為樣本數(shù)，uij表示Xj隸屬到類Ci的隸屬度，Vi為第i類的聚類中心，同是權重系數(shù)，d2(Xj，Vi)是樣本Xj到聚類中心Vi的歐氏距離的平方。

聚類結(jié)果是每一個數(shù)據(jù)點對聚類中心的隸屬程度，該隸屬程度用一個數(shù)值來表示。FCM算法的主要步驟可分為:

(1)初始化聚類中心點值Vi，確定迭代停止閾值ε;

(2)計算由隸屬度的值組成的劃分矩陣U;

(3)利用劃分矩陣更新聚類中心值;

(4)重復第2步，直至聚類中心值滿足停止閾值ε的條件，則迭代停止。

由以上步驟可以看出，算法的過程就是不斷地修正聚類中心值Vi和由隸屬度值所組成的劃分矩陣U，屬于動態(tài)聚類過程。

2.2 模糊OLAP查詢算法

基于模糊的聚類優(yōu)化OLAP算法的詳細步驟:

(1)給定數(shù)據(jù)集A={a1，a2，…，an};

(2)根據(jù)定義1 將數(shù)據(jù)集A 過濾并分成若干個“概念”子集A1，A2，…，Ap;

(3)if(數(shù)據(jù)集的維數(shù))＞2;then 將每個高維樣本的子集樣本映射到二維平面，然后對得到的二維樣本用FCM算法聚類;else 直接用FCM算法聚類;

(4)對p個子集聚類后分別得到的聚類中心數(shù)為m1，m2，…，mp;

(5)if|m1+m2+…+mp|＞=n0(n0為問題規(guī)模的閾值);then 將m1+m2+…+mp個聚類中心看成集合A，轉(zhuǎn)到(2);else 轉(zhuǎn)到第(6)。

(6)把m1+m2+…+mp個聚類中心進行一次性聚類。

(7)if 聚類中心x1和x2聚為一類，且第(4)步結(jié)束后c1和c2分別是以x1和x2為聚類中心的類;then 將類c1和c2合并為一類;else 結(jié)束。

(8)if數(shù)據(jù)集是高維樣本;then 將第(7)步的聚類結(jié)果還原到原始的高維樣本中;

(9)在已聚類數(shù)據(jù)中按照定義6 進行查詢匹配，向用戶提交查詢結(jié)果。

3 實驗結(jié)果與性能分析

測試所采用的數(shù)據(jù)集為TPC-R，實驗是在一臺Intel Pentium IV 2.6GHz，512M 內(nèi)存，運行Windows 2000 Server的PC 機上執(zhí)行。

實驗一是采用優(yōu)化方法的模糊OLAP查詢執(zhí)行時間與未優(yōu)化查詢執(zhí)行時間進行對比，其結(jié)果如圖1所示。由圖1可以看出，由于本文提出的優(yōu)化方法需要在查詢時計算隸屬度函數(shù)，耗費不少的CPU時間，因此在OLAP查詢較少的情況下，可能執(zhí)行時間比未優(yōu)化的情況還要更長，但隨著OLAP查詢的增長，執(zhí)行時間比未優(yōu)化的情況顯著減少。

實驗二是分析模糊OLAP查詢對于系統(tǒng)整體效率的影響，隨機生成了1 000個OLAP查詢，并不斷提高其中模糊OLAP查詢的比例，其執(zhí)行時間如圖2所示。

圖1 優(yōu)化前后執(zhí)行時間對比

圖2 不同模糊查詢下執(zhí)行時間對比

由圖2可以看出，隨著模糊查詢的比例增加，總體花費的執(zhí)行時間顯著下降，因此在整個系統(tǒng)中實現(xiàn)對模糊OLAP查詢的支持，對于整體效率的影響明顯。

4 結(jié)束語

本文在對模糊OLAP查詢進行形式化描述的基礎上，利用模糊邏輯生成元組、單元格與模糊OLAP查詢的匹配度，判斷出隸屬度低的元組或單元格，使其不參與聚類計算;將高維數(shù)據(jù)映射到二維平面，再用FCM算法聚類，從而減少整個查詢系統(tǒng)的耗費代價，實驗證明，本算法確實改善了系統(tǒng)的性能。今后的工作將繼續(xù)對模糊OLAP查詢的匹配度進行研究，并改進FCM算法，以進一步提高模糊OLAP查詢的效率。

[1]Codd E F，Codd S B，Salley C T.Providing on-line analytical processing to user-analysts[J].An IT mandate，1993，25(3):45-49.

[2]Nigel Pendse，What is O L A P.OLAP report[EDOL].http://www.olapreport.com/about.htm，2000-03-10.

[3]Jerbi H，Ravat F，Teste O，etal.Applying recommen-dation technology in OLAP systems[C].Beijing:International Conference on Enterprise Information Systems，2009:220-233.

[4]Jerbi H，Ravat F，Teste O，etal.Management of con-text-aware preferences in multidimensional databases[C].London:International Conference on Digital Information Management，2008:669-675.

[5]孟祥福，馬宗民，嚴麗.數(shù)據(jù)庫模糊查詢結(jié)果自動排序方法[J].東北大學學報(自然科學版)，2008，29(7):960-964.