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

0 引 言

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

1 模糊OLAP查詢(xún)及操作的形式化描述

本文對(duì)OLAP的模糊查詢(xún)中使用的相關(guān)概念及其計(jì)算公式進(jìn)行詳細(xì)的形式化描述。

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

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

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

由定義可知，模糊OLAP查詢(xún)是對(duì)傳統(tǒng)OLAP查詢(xún)定義的擴(kuò)展，從而可以用統(tǒng)一的觀(guān)點(diǎn)來(lái)處理傳統(tǒng)的OLAP查詢(xún)與模糊OLAP查詢(xún)。同時(shí)在形式化定義模糊值、維模糊值及模糊OLAP查詢(xún)后，可以定義維值、維層次值及單元格與概念的匹配關(guān)系。

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

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

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

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

定義6(模糊OLAP查詢(xún)的隸屬度與匹配關(guān)系=Q)對(duì)于某個(gè)單元格cell，其與某個(gè)模糊OLAP查詢(xún)fuzzy_q的隸屬度定義為:

其與fuzzy_q 匹配，記做cell=Qfuzzy_q，當(dāng)且僅當(dāng)對(duì)于這個(gè)單元格cell所有的維值dDi，均有dDi=Dfuzzy_Di。

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

2 聚類(lèi)策略選擇及優(yōu)化查詢(xún)算法描述

2.1 聚類(lèi)策略的選擇

傳統(tǒng)的聚類(lèi)分析種類(lèi)繁多，但由于數(shù)據(jù)挖掘的處理對(duì)象是海量的高維數(shù)據(jù)集，又有許多相適應(yīng)的新聚類(lèi)算法被提出，如基于網(wǎng)格的聚類(lèi)算法，基于密度的聚類(lèi)算法以及模糊聚類(lèi)算法等。實(shí)際上，在數(shù)據(jù)挖掘中，特別是在模糊OLAP查詢(xún)中，大多數(shù)對(duì)象并沒(méi)有嚴(yán)格的類(lèi)屬性和隸屬關(guān)系，它們?cè)趯傩缘确矫娲嬖谥丿B性、交叉性，比較適合進(jìn)行模糊劃分，因此數(shù)據(jù)挖掘中的聚類(lèi)分析主要為模糊聚類(lèi)分析。

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

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

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

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

(1)初始化聚類(lèi)中心點(diǎn)值Vi，確定迭代停止閾值ε;

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

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

(4)重復(fù)第2步，直至聚類(lèi)中心值滿(mǎn)足停止閾值ε的條件，則迭代停止。

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

2.2 模糊OLAP查詢(xún)算法

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

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

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

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

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

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

(6)把m1+m2+…+mp個(gè)聚類(lèi)中心進(jìn)行一次性聚類(lèi)。

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

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

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

3 實(shí)驗(yàn)結(jié)果與性能分析

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

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

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

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

圖2 不同模糊查詢(xún)下執(zhí)行時(shí)間對(duì)比

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

4 結(jié)束語(yǔ)

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

[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]孟祥福，馬宗民，嚴(yán)麗.數(shù)據(jù)庫(kù)模糊查詢(xún)結(jié)果自動(dòng)排序方法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，29(7):960-964.