左利云

0 引言

隨著數(shù)據(jù)庫(kù)技術(shù)應(yīng)用領(lǐng)域的不斷擴(kuò)大，信息檢索要求的不斷提高，模糊信息越來(lái)越多，精確查詢范疇已不能滿足各種應(yīng)用領(lǐng)域?qū)?shù)據(jù)庫(kù)查詢的要求。更重要的是,隨著電子計(jì)算機(jī)、控制論、系統(tǒng)科學(xué)的迅速發(fā)展，要使計(jì)算機(jī)能像人腦那樣對(duì)復(fù)雜事物具有識(shí)別能力，就必須研究和處理模糊性。因此對(duì)模糊查詢技術(shù)的研究顯得越來(lái)越重要。

現(xiàn)有關(guān)于模糊查詢的研究也不少，但大多是側(cè)重其應(yīng)用和模糊數(shù)據(jù)庫(kù)的構(gòu)建，而對(duì)其查詢效率提高優(yōu)化的研究卻比較少，較新的研究有郭喜平[1]等交互式給出各種模糊查詢優(yōu)化建議，但并未提出具體能提高查詢效率的算法；金宗安[2]等通過(guò)設(shè)置隸屬函數(shù)的參數(shù)、直方圖的值調(diào)整模糊范圍的大小，通過(guò)設(shè)置不同的可信度查詢不同可靠性的數(shù)據(jù)，由于隸屬函數(shù)的定義包括很多主觀性的因素，因此通用性不是很好，更重要的是他并未對(duì)模糊查詢的效率進(jìn)行研究。而本文是在模糊查詢的基礎(chǔ)上結(jié)合相似查詢，提出的一種可以明顯提高查詢效率的智能查詢優(yōu)化算法。

1 基于模糊數(shù)學(xué)模型的模糊查詢

人的自然語(yǔ)言具有模糊性，為了實(shí)現(xiàn)用自然語(yǔ)言跟計(jì)算機(jī)進(jìn)行直接對(duì)話，必須把人的語(yǔ)言及思維過(guò)程提煉成數(shù)學(xué)模型，才能給計(jì)算機(jī)輸入指令，因此模糊數(shù)學(xué)模型應(yīng)運(yùn)而生。而模糊查詢實(shí)現(xiàn)的理論基礎(chǔ)就是模糊數(shù)學(xué)模型。

1.1 模糊數(shù)學(xué)模型的建立

首先給出模糊集合及其α截集的定義。

定義1 設(shè)在論域U上給定了一個(gè)映射：A：U→[0,1] ，u∣→A(u)

則稱A為U上的模糊集，A(u)稱為A的隸屬函數(shù)（或稱u對(duì)A的隸屬度）。

定義2α截集：設(shè)A論域U上的模糊集合，隸屬函數(shù)為A(u)：U→[0,1] ，在A中隸屬度大于或等于α值的元素集合，其中 0≤α＜1(0＜α≤1)，分別稱為A的強(qiáng)（弱）α-截集，表示為：Aα+={u∣u∈U,A(u) ＞ α},Aα={u∣u∈U,A(u)≥α}。

一個(gè)模糊集的α-截集對(duì)應(yīng)一個(gè)區(qū)間，其中α稱為閾值，可以利用α-截集將一個(gè)模糊集合轉(zhuǎn)化為普通集合。

1.2 模糊查詢的實(shí)現(xiàn)

模糊查詢的實(shí)現(xiàn)原理，是根據(jù)模糊模型將模糊的輸入條件精確化，轉(zhuǎn)換為標(biāo)準(zhǔn)的 SQL語(yǔ)句，去數(shù)據(jù)庫(kù)中檢索出相應(yīng)結(jié)果集?；谇懊嬉呀?jīng)建立好的數(shù)據(jù)模型和模糊模型，進(jìn)行模糊查詢的設(shè)計(jì)。要實(shí)現(xiàn)此類模糊查詢，有兩種方式：

(1) 建立模糊數(shù)據(jù)庫(kù)模型

將模糊理論直接引入傳統(tǒng)數(shù)據(jù)庫(kù)，對(duì)數(shù)據(jù)表示和數(shù)據(jù)庫(kù)進(jìn)行模糊處理，并建立相應(yīng)的查詢語(yǔ)言。如有些字段的值是模糊化的，在進(jìn)行數(shù)據(jù)庫(kù)錄入時(shí)，首先進(jìn)行數(shù)據(jù)模糊化處理．將精確數(shù)據(jù)轉(zhuǎn)化為模糊數(shù)據(jù)，而在數(shù)據(jù)查詢時(shí)，直接進(jìn)行模糊值的匹配。這種方法雖然查詢簡(jiǎn)單，但在數(shù)據(jù)錄入時(shí)需要進(jìn)行額外計(jì)算工作，且模糊字段值的確定并不容易。

(2) 基于傳統(tǒng)精確數(shù)據(jù)庫(kù)

將 SOL語(yǔ)言本身進(jìn)行模糊化擴(kuò)展，將查詢條件通過(guò)模糊計(jì)算，轉(zhuǎn)化為一個(gè)模糊范圍，再進(jìn)行精確的 SQL查詢。這種方法無(wú)需增加數(shù)據(jù)錄入人員的負(fù)擔(dān)，原有數(shù)據(jù)庫(kù)無(wú)須修改，查詢過(guò)程與一般查詢相一致。操作簡(jiǎn)單，結(jié)果清晰明了，并且查詢的模糊閾值易于動(dòng)態(tài)修正變更。

由于目前的數(shù)據(jù)庫(kù)還是以傳統(tǒng)的精確關(guān)系數(shù)據(jù)庫(kù)為絕大多數(shù)，而且無(wú)論從可操作性還是兼容性來(lái)看，方式(2)無(wú)疑是最合適的選擇，因此模糊查詢的實(shí)現(xiàn)，通過(guò)模糊理論模型，將模糊查詢條件精確化來(lái)實(shí)現(xiàn)。即當(dāng)用戶輸入自然語(yǔ)言的查詢條件時(shí)，只要將其中關(guān)鍵模糊詞的隸屬函數(shù)找到，用它去匹配數(shù)據(jù)庫(kù)中所有記錄相應(yīng)的字段，計(jì)算出隸屬度,隸屬度大于或等于給定的閾值的記錄，就是用戶要查詢的數(shù)據(jù)。

2 基于模糊數(shù)據(jù)模型的智能查詢優(yōu)化算法

根據(jù)模糊查詢的特點(diǎn)可知，模糊查詢要比精確查詢的花費(fèi)更多，因此如何能發(fā)展出更快更高效的模糊查詢算法顯得十分重要。在此結(jié)合模糊查詢及相似查詢的優(yōu)點(diǎn)，提出一種智能查詢優(yōu)化算法（Intelligent Inquire Optimization簡(jiǎn)稱IIOP算法）。

2.1 特征極值點(diǎn)的提取

對(duì)于給定的一組數(shù)據(jù)序列A、一個(gè)模糊查詢查詢序列Q及一個(gè)距離閾值ε，智能查詢要做的是如何有效的找出所有與查詢序列Q的距離小于ε的序列。研究發(fā)現(xiàn)，如果直接對(duì)查詢的數(shù)據(jù)序列進(jìn)行相似查詢，不但存儲(chǔ)和計(jì)算效率低下，而且還會(huì)影響算法的準(zhǔn)確性和可靠性，因此在進(jìn)行相似查詢之前，先對(duì)數(shù)據(jù)序列進(jìn)行特征極值點(diǎn)提取，這樣會(huì)大大提高查詢速度。

IIOP算法采用的征極值點(diǎn)提取方法，是結(jié)合特征點(diǎn)提取法FPS算法[3]和極值點(diǎn)提取法IPS算法[4]來(lái)實(shí)現(xiàn)。其實(shí)現(xiàn)思路簡(jiǎn)單概括如下：特征極值點(diǎn)的選取，用極值法選擇原始序列中對(duì)序列形態(tài)影響最大的點(diǎn)作為特征點(diǎn)，通過(guò)依次連接這些特征點(diǎn)實(shí)現(xiàn)序列的線段化。數(shù)據(jù)突變序列中用IPS算法的距離閾值ε作為選取轉(zhuǎn)折點(diǎn)的依據(jù)，當(dāng)數(shù)據(jù)序列中某個(gè)數(shù)據(jù)點(diǎn)ai與前后數(shù)據(jù)ai-1、ai+1平均值的距離大于，即時(shí)，ai為轉(zhuǎn)折極值點(diǎn)。具體實(shí)現(xiàn)過(guò)程如圖1所示。

圖1 特征極值點(diǎn)提取過(guò)程框圖

該方法僅需一次掃描序列數(shù)據(jù)集，就可以保留反映數(shù)據(jù)序列變化模式的主要特征極值點(diǎn)，獲得特征極值點(diǎn)集合Ae，極大減少了數(shù)據(jù)存儲(chǔ)量。

2.2 特征極值點(diǎn)序列的相似查詢

在數(shù)據(jù)序列的相似查詢中，重要的是對(duì)于相似距離的度量。比較有名的有，通過(guò)歐幾里德距離(Euclidean Distance) 的ED方法和動(dòng)態(tài)時(shí)間彎曲距離(Dynamic Time Warping) 的DTW算法[5]，比較序列間的相似。由于原始數(shù)據(jù)序列的DTW距離計(jì)算比較費(fèi)時(shí)，而一般情況下序列都很長(zhǎng)，因此計(jì)算距離需要比較長(zhǎng)的時(shí)間。如果能從序列中抽取少量的、主要的特征則可以顯著提高序列的查找速度。

故IIOP算法在2.1的基礎(chǔ)之上，利用特征極值點(diǎn)序列代替原始的數(shù)據(jù)序列，采用基于DTW距離的相似性度量方法，比較序列之間的相似程度。

首先給出DTW距離的相似性度量公式。對(duì)于之前2.1中提取的特征極值點(diǎn)集合中的兩個(gè)序列Ae=＜a1e,a2e,…,aie,…,ame,＞(0＜i＜m),Be=＜b1e,b2e,…,bje,…bne,＞(0＜j＜n)，二者特征極值點(diǎn)DTW相似距離D的計(jì)算公式如下：

其中m、n為特征極值點(diǎn)個(gè)數(shù)。對(duì)數(shù)據(jù)序列執(zhí)行 2.1中特征提取獲得特征極值點(diǎn)后，得到的特征極值點(diǎn)序列中特征極值點(diǎn)個(gè)數(shù)可能不盡相同。由于特征極值點(diǎn)是反映數(shù)據(jù)序列變化趨勢(shì)的重要標(biāo)志，因此當(dāng)兩個(gè)數(shù)據(jù)序列的特征極值點(diǎn)個(gè)數(shù)差異超過(guò)閾值ε(ε≥1)后，IIOP算法認(rèn)為兩個(gè)數(shù)據(jù)序列不相似。只有當(dāng)特征極值點(diǎn)個(gè)數(shù)差異小于ε時(shí)，才進(jìn)行下一步DTW相似距離D的計(jì)算。具體步驟見(jiàn)圖2。

圖2 相似查詢過(guò)程示意圖

近幾年有關(guān)相似查詢的算法，有基于分段多項(xiàng)式表示的PPR算法[6] 和利用主成分分析對(duì)MTS數(shù)據(jù)降維，聚類分析構(gòu)造B+-樹(shù)的Dbis算法[7] 等。本文提出的IIOP算法在相似查詢的整個(gè)DTW度量過(guò)程中僅保留數(shù)據(jù)序列中的特征極值點(diǎn)，極大減少了數(shù)據(jù)存儲(chǔ)量，提高了查詢計(jì)算速度。

3 智能查詢優(yōu)化算法的仿真實(shí)驗(yàn)及結(jié)果分析

為了檢驗(yàn)所提出智能查詢優(yōu)化算法——IIOP算法的性能，設(shè)計(jì)了仿真實(shí)驗(yàn)系統(tǒng)，實(shí)驗(yàn)運(yùn)行環(huán)境為4個(gè)AMD皓龍2.4GHZ CPU（雙核），16GB內(nèi)存和840GB硬盤(pán)，軟件環(huán)境是Microsoft Windows XP操作系統(tǒng)和ORACLE 10G數(shù)據(jù)庫(kù)管理系統(tǒng)，算法使用的開(kāi)發(fā)工具為Visual C++。因 IIOP算法查詢效率主要表現(xiàn)在其相似查詢方面，故將其分別與同類相似查詢算法ED算法及經(jīng)典DTW算法進(jìn)行比較，觀察它們?cè)诓樵儠r(shí)間和查詢準(zhǔn)確率方面的表現(xiàn)。

實(shí)驗(yàn)數(shù)據(jù)源自2009年12月18日滬深股市的200家上市公司的交易數(shù)據(jù)集，數(shù)據(jù)序列數(shù)據(jù)點(diǎn)為1 258 953個(gè)，由于對(duì)原始數(shù)據(jù)序列進(jìn)行特征極值點(diǎn)序列分段后獲得的特征極值點(diǎn)序列中數(shù)據(jù)個(gè)數(shù)各不相同，因此在IIOP算法中進(jìn)行相似性查詢時(shí)，從200個(gè)樣本序列中隨機(jī)抽取10個(gè)樣本序列作為查詢目標(biāo)序列，樣本序列數(shù)據(jù)點(diǎn)個(gè)數(shù)平均為100 000。實(shí)驗(yàn)中DTW算法和IIOP算法閾值分別選取2和2.5，因其表現(xiàn)類似故只做出閾值取2的情況，3個(gè)算法在查詢時(shí)間和準(zhǔn)確率方面的表現(xiàn)如圖3、4所示。

圖3 三算法查詢時(shí)間比較

圖4 三算法查詢準(zhǔn)確率比較

通過(guò)實(shí)驗(yàn)數(shù)據(jù)圖比較不難發(fā)現(xiàn)，盡管ED算法的相似性聚類算法速度較快，但計(jì)算所得距離基本相似，分類效果較差，故準(zhǔn)確率表現(xiàn)很差。IIOP算法的查詢時(shí)間略高于ED算法，但查詢質(zhì)量遠(yuǎn)遠(yuǎn)優(yōu)于ED算法，與經(jīng)典DTW算法基本一致，而且IIOP算法的查詢時(shí)間與樣本數(shù)據(jù)的特征極值點(diǎn)個(gè)數(shù)緊密相關(guān)，特征極值點(diǎn)個(gè)數(shù)越少，運(yùn)行速度越快。。

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

為了使數(shù)據(jù)庫(kù)能處理現(xiàn)實(shí)世界中廣泛存在的不精確的、模糊的數(shù)據(jù),進(jìn)一步擴(kuò)展數(shù)據(jù)庫(kù)的查詢功能，提出基于模糊數(shù)學(xué)模型的模糊查詢，但是有關(guān)模糊查詢的查詢效率的研究一直比較少，本文提出一種將模糊查詢和相似查詢完美結(jié)合起來(lái)的智能查詢優(yōu)化算法。該算法中模糊匹配查詢符合人腦思維特性，因而更合理、更有效，同時(shí)為了提高查詢效率提出首先對(duì)原始數(shù)據(jù)序列進(jìn)行特征極值點(diǎn)的提取，極大減少了數(shù)據(jù)存儲(chǔ)量，提高了查詢計(jì)算速度。經(jīng)實(shí)驗(yàn)驗(yàn)證該算法查詢質(zhì)量要優(yōu)于同類ED、DTW算法。

[1] 金宗安,楊路明,謝東.關(guān)系數(shù)據(jù)庫(kù)模糊查詢的研究[J] .計(jì)算機(jī)工程,2009.7:63-65.

[2] 郭喜平,蒙應(yīng)杰.模糊查詢中的策略優(yōu)化[J] .計(jì)算機(jī)工程與應(yīng)用,2008.44(34):152-154.

[3] 肖輝,胡運(yùn)發(fā).基于分段時(shí)間彎曲距離的時(shí)間序列挖掘[J] .計(jì)算機(jī)研究與發(fā)展.2005.42(l):72-78.

[4] Th. Pavlidis,SL Horwitz.SegmentationofPlane Curves[J] .IEEE Transactions on Computer.1974.23(8):860-870.

[5] Vlachos M,Hadjieleftheriou M,Gunopulos D, Keogh E.Indexing multi-dimensional time-series with support for multi-ple distance measures.In:Proceedings of the 9th ACM Inter-national Conference on Knowledge Discovery and Data Mining,Washington DC, USA,2003,216-225.

[6] 周大鐲,吳曉麗,閆紅燦.一種高效的多變量時(shí)間序列相似查詢算法[J] .計(jì)算機(jī)應(yīng)用,2008.10:2541-2543.