左利云

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 特征極值點的提取

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

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

圖1 特征極值點提取過程框圖

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

2.2 特征極值點序列的相似查詢

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

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

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

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

圖2 相似查詢過程示意圖

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

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

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

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

圖3 三算法查詢時間比較

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

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

4 結(jié)束語

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

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

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

[3] 肖輝,胡運發(fā).基于分段時間彎曲距離的時間序列挖掘[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] 周大鐲,吳曉麗,閆紅燦.一種高效的多變量時間序列相似查詢算法[J] .計算機應(yīng)用,2008.10:2541-2543.