李 雪

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211100)

0 引 言

日常生活中可以見到很多模糊現(xiàn)象，比如有一個古老的希臘悖論是這樣說的：一顆豌豆不叫一堆，兩顆也不叫，這是大家都公認(rèn)的，但是可不可以說10 000顆豌豆不叫一堆而10 001顆叫一堆呢？肯定不能這樣定義，但是適當(dāng)?shù)慕缦拊谀睦铮窟@是一個漸進(jìn)的過程，沒有明確的范圍，不能用精確的數(shù)值進(jìn)行描述。然而，研究者們一直忽略這些不確定性，并且所有的數(shù)據(jù)庫管理系統(tǒng)都是基于精確的數(shù)據(jù)。直到20世紀(jì)60年代，Zadeh教授發(fā)起了關(guān)于模糊性的研究。

查詢操作是數(shù)據(jù)庫的重要操作之一，而現(xiàn)有的絕大多數(shù)查詢操作都要求指定某個屬性位于某個具體區(qū)間的所有記錄。但是可以發(fā)現(xiàn)，在日常生活中，人們想要得到某種結(jié)果時，并不能很明確地表達(dá)他們的查詢要求。比如某個人需要租房子，需要找到價格便宜并且離市中心近的房子，當(dāng)在數(shù)據(jù)庫中進(jìn)行查詢時，“離市中心近”以及“價格便宜”這樣的查詢語句就是模糊的概念。但是一般的數(shù)據(jù)庫管理系統(tǒng)并不能對這樣的模糊語句進(jìn)行查詢，在網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大的今天，數(shù)據(jù)庫的查詢次數(shù)以指數(shù)級別在增長，精確的查詢則要求數(shù)據(jù)庫的操作者對數(shù)據(jù)庫中的數(shù)據(jù)有很清楚的了解，例如DBA(database administrator，數(shù)據(jù)庫管理員)。這直接使得對數(shù)據(jù)庫內(nèi)容不熟悉的人很難去獲得其想要的查詢結(jié)果，其大概率查詢到空的結(jié)果集或者過多的數(shù)據(jù)記錄從而難以篩選。而模糊查詢則為該問題提供了解決思路。然而不論是傳統(tǒng)的關(guān)系數(shù)據(jù)庫還是圖數(shù)據(jù)庫都只能對精確的條件進(jìn)行查詢，無法查詢形如上文提到的“價格便宜并且離市中心近的房子”這樣帶有模糊語句的查詢條件，因此急需一種合適有效的方法將模糊的查詢條件轉(zhuǎn)化成精確的查詢區(qū)間，使其可以在數(shù)據(jù)庫管理系統(tǒng)中執(zhí)行。

1 相關(guān)研究工作

1.1 模糊查詢

1.1.1 關(guān)系數(shù)據(jù)庫模糊查詢

國內(nèi)外對模糊查詢進(jìn)行了大量研究，例如，文獻(xiàn)[1-4]均說明了如何使用正向法和反向法對查詢條件進(jìn)行處理，將其轉(zhuǎn)化成精確的查詢區(qū)間；文獻(xiàn)[5]定義了一種模糊數(shù)據(jù)庫查詢語言，它可以處理數(shù)據(jù)庫中遇到的模糊的或者精確的查詢條件；文獻(xiàn)[6]設(shè)計(jì)了一個樣本數(shù)據(jù)庫，可以在上面進(jìn)行模糊查詢或者精確查詢，對比傳統(tǒng)數(shù)據(jù)庫，在樣本數(shù)據(jù)庫上進(jìn)行模糊查詢的時間花費(fèi)大大降低；文獻(xiàn)[7-8]在現(xiàn)有關(guān)系數(shù)據(jù)庫上對查詢語言進(jìn)行模糊擴(kuò)展，同時引入了權(quán)重的概念。

1.1.2 云數(shù)據(jù)庫模糊查詢

關(guān)于NoSQL模糊查詢，國內(nèi)并沒有相關(guān)研究，國際上此類研究也并不是很多。文獻(xiàn)[9]對NoSQL圖數(shù)據(jù)庫的Cypher語言進(jìn)行擴(kuò)展得到Cypherf語言使其可以進(jìn)行模糊查詢；文獻(xiàn)[10]提出了一個基于圖的模糊NoSQL模型，稱FNoSQL，用來處理大數(shù)據(jù)庫的同時也擴(kuò)展了NoSQL；文獻(xiàn)[11]提出使用合適的工具用來在Neo4j的cypher語言中表達(dá)模糊查詢，用模糊性來幫助解決模糊模式匹配。

文獻(xiàn)[12]實(shí)現(xiàn)了可視化模糊查詢生成器AskFuzzy，它是前端的可視化界面和后端的數(shù)據(jù)庫之間的一個中間層，可以在where中基于概念而不是數(shù)據(jù)來使用模糊謂詞進(jìn)行查詢。

文獻(xiàn)[13-14]提出了一個可以靈活查詢模糊數(shù)據(jù)庫的系統(tǒng)SUGAR，該系統(tǒng)建立在Neo4j圖數(shù)據(jù)庫管理系統(tǒng)中，支持Cypher查詢，由transcriptor模塊和分?jǐn)?shù)計(jì)算器模塊組成，并且引進(jìn)了Fudge語言來實(shí)施，該語言可以靈活處理模糊的或者精確的數(shù)據(jù)，可以用來處理模糊圖數(shù)據(jù)庫中的偏好查詢。

1.2 相關(guān)理論知識

生活中經(jīng)常會有很多無法用精確的數(shù)值表達(dá)的不確定性，比如人們交談時的口語，各種形容詞以及副詞，各個領(lǐng)域主觀的意見以及判斷等等，這些都是模糊性表達(dá)。所有的模糊性都是一種主觀的衡量，需要用隸屬函數(shù)對這些模糊性進(jìn)行轉(zhuǎn)換，明確這些模糊性的隸屬規(guī)律，找到合適的隸屬函數(shù)，這樣就可以在充滿不確定性的現(xiàn)實(shí)生活中和必須使用精確數(shù)據(jù)進(jìn)行計(jì)算的數(shù)學(xué)中找到一個很好的平衡點(diǎn)[15-16]。

1.2.1 模糊集理論

(1)模糊集。

模糊集A可以用元素x和它的隸屬函數(shù)μA(x)的集合表示，其中x是論域U中的一個元素,也就是：

A={(x,μA(x))|x∈U}

一般可以通過模糊集合所對應(yīng)的隸屬函數(shù)來對模糊集合進(jìn)行劃分，因此如果知道論域U上的模糊集合，就能通過模糊集合中的元素x來確定元素x所對應(yīng)的隸屬函數(shù)μA(x)。

(2)α截集。

α截集可以認(rèn)為是論域U中所有元素x所對應(yīng)的隸屬函數(shù)μA(x)的值都不小于α的一個集合：

Aα={x|μA(x)≥α, ?x∈U}

其中，α為置信水平(閾值)。

1.2.2 正態(tài)分布

如果有隨機(jī)變量X服從參數(shù)為μ,σ(σ>0)的概率分布，那就稱隨機(jī)變量X服從正態(tài)分布，記為X～N(μ,σ2)，它的概率密度函數(shù)表示為：

圖1是一個正態(tài)分布概率密度函數(shù)。從圖中可以得知，平均數(shù)周圍的數(shù)的取值概率明顯大于兩邊的，通常生活中很多的大樣本數(shù)據(jù)都服從正態(tài)分布，比如學(xué)生的成績大都比較集中，中等的偏多，成績特別好或者特別差的人總是占少數(shù)的；人的身高在某個中等范圍的占大多數(shù)，特別高的人以及特別矮的屬于少數(shù)等。基于這個特點(diǎn)，考慮使用正態(tài)分布密度函數(shù)作為隸屬函數(shù)對模糊屬性進(jìn)行區(qū)間匹配。

圖1 正態(tài)分布密度函數(shù)

2 基于正態(tài)分布密度函數(shù)的模糊化匹配方法

傳統(tǒng)的模糊化查詢主要是采用Zadeh在1965年提出的模糊數(shù)學(xué)理論，通過對論域中不同模糊集設(shè)置相應(yīng)隸屬函數(shù)來計(jì)算某具體數(shù)值的隸屬度，從而進(jìn)行查詢。然而在實(shí)際的圖像數(shù)據(jù)庫中，采用預(yù)設(shè)的隸屬函數(shù)會面臨諸多問題，如：

(1)很難對所有的模糊集都設(shè)置一個相對較為準(zhǔn)確的隸屬函數(shù)；

(2)忽視數(shù)據(jù)庫中已有樣本的信息利用；

(3)對數(shù)據(jù)庫中節(jié)點(diǎn)作屬性增加的代價較大；

(4)很難確定最終的匹配區(qū)間。

為了將模糊化查詢應(yīng)用于圖形數(shù)據(jù)庫，文中提出了一種基于正態(tài)分布密度函數(shù)的模糊化自動匹配方法，克服了上述問題，并結(jié)合實(shí)例作了性能分析。

設(shè)某一類節(jié)點(diǎn)N擁有k個實(shí)體，即：{N}={n1,n2,…,nk}。

其某個屬性attr是連續(xù)的，第i個實(shí)體對應(yīng)attr的值用ni.attr表示，一般地，可以預(yù)計(jì)算{N}在屬性attr的均值E(N)與方差D2(N)，即

E(N,attr)=(n1.attr+n2.attr+…+nk.attr)/k

D2(N,attr)=((n1.attr-E(N,attr))2+(n2.attr-E(N,attr))2+…+(nk.attr-E(N,attr))2)/k

則假設(shè){N}的attr屬性值服從正態(tài)分布，即N.attr～N(E(N,attr),D2(N,attr))。為了簡便，所有的E(N,attr))用E表示，D(N,attr)用D表示。其概率密度函數(shù)為：

由概率論可知，函數(shù)f(x)的線下面積為1，其定義域?yàn)?-∞,+∞)。

根據(jù)具體模糊集的內(nèi)容對定義域進(jìn)行劃分。一般地，對于模糊集A其均為論域U的子集，根據(jù)具體的A可將論域進(jìn)行t個劃分，即：

d(U)={d1,d2,…,dt}

且A屬于第s個劃分，即A=ds。例如：

如果U是年齡[0,100]，可將其分為“年幼”、“年輕”、“中年”，“老年”4個劃分，“年輕”為第2個劃分；

如果U是考試成績[0,100]，可將其分為“差”、“普通”、“優(yōu)異”3個劃分，“普通”是第2個劃分。

論域的每個劃分di都可以賦之一個權(quán)重wi，滿足：w1+w2+…+wt=1。

為了描述方便，設(shè)所有的權(quán)重是一樣的，即

wi=1/t(1≤i≤t)

給出模糊區(qū)間的定義：

若模糊集A可將論域進(jìn)行t個劃分，且A屬于第s個劃分，則A的模糊區(qū)間表示為：

farea(A)=[fmin(A),fmax(A)]

若s=1，則fmin(A)=-∞；若s=t，則fmax(A)=+∞。

若A'屬于第s+1個劃分，則fmax(A)=fmin(A')，且滿足：

令Y=(X-E)/D，則Y服從標(biāo)準(zhǔn)正態(tài)分布：

設(shè)Φ(x)為標(biāo)準(zhǔn)正態(tài)分布的累積分布函數(shù)，即：

且Φ(x)在定義域R上單調(diào)遞增。

則有：

若Φ(x)的反函數(shù)為Φ-1(x)，則有：

fmin(A)=Φ-1((s-1)/t)·D+E

fmax(A)=Φ-1(s/t)·D+E

一般地，函數(shù)Φ(x)的定義域?yàn)閇0,+∞)，值域?yàn)閇0.5,1)，且Φ(-x)=1-Φ(x)。有Φ-1(x)的定義域?yàn)閇0.5,1)，值域?yàn)閇0,+∞)。由Φ(-x)=1-Φ(x)，有-Φ-1(x)=Φ-1(1-x)。

所以上式可化為：

fmin(A)=

根據(jù)上式可以計(jì)算fmin(A)和fmax(A)。為了避免對“無窮”的計(jì)算操作，利用論域U=[Umin,Umax]的上下限對正負(fù)無窮進(jìn)行取代，即：

fmin(A)=

對區(qū)間farea(A)進(jìn)行求平均操作，即均值：

定義：

若s=(t+1)/2，則E(N,attr)為模糊集A的隸屬函數(shù)的極大值點(diǎn)max(A)；否則，均值ave與正態(tài)分布曲線的交點(diǎn)的橫坐標(biāo)為模糊集A的隸屬函數(shù)的極大值點(diǎn)max(A)。

若f(x)在x≥E(N,attr)區(qū)間的反函數(shù)為f-1(x)，則有：

求得模糊集A的隸屬函數(shù)的極大值點(diǎn)max(A)。若論集U共有t個劃分，其每個劃分的模糊集A1,A2,…,At對應(yīng)的極大值點(diǎn)分別為max1，max2，…，maxt。不妨令max0=Umin，maxt+1=Umax，則用正、余弦曲線描述每個模糊集的隸屬函數(shù)：

若2≤i≤t-1，則

至此完成了基于正態(tài)分布的模糊集對應(yīng)隸屬函數(shù)的自動生成。設(shè)置閾值ε，令A(yù)i(x)>ε，得到的不等式的解即為Ai(x)所對應(yīng)模糊集的區(qū)間匹配。

3 實(shí)例分析

第二節(jié)敘述的方法可以用在很大的數(shù)據(jù)量上，利用正態(tài)分布函數(shù)直接計(jì)算出每個模糊集對應(yīng)的區(qū)間匹配。為了方便起見，選擇一個班的成績作為研究對象，分別計(jì)算出成績偏低、中等以及優(yōu)秀三個模糊集的隸屬函數(shù)，設(shè)置合適的ε值，得到區(qū)間匹配。

3.1 區(qū)間匹配實(shí)現(xiàn)一般流程

圖2描述了模糊集區(qū)間匹配的一般實(shí)現(xiàn)過程。

圖2 模糊集區(qū)間匹配的實(shí)現(xiàn)過程

3.2 區(qū)間匹配計(jì)算過程

(1)確定模糊集以及s,t。

由表1計(jì)算出學(xué)生成績的平均值E≈77.6，標(biāo)準(zhǔn)差D≈15.3，方差D2≈234。將學(xué)生成績[0,100]劃分為“低”、“中等”、“優(yōu)異”三個模糊區(qū)間，由此可知t=3，s取1，2，3。

表1 學(xué)生成績

(2)計(jì)算fmin(A)、fmax(A)。

15.3+77.6≈71

當(dāng)s=2時，因?yàn)槿鬉'屬于第s+1個劃分，則fmax(A)=fmin(A')，所以

fmin(A)=71

當(dāng)s=3時，fmin(A)=84.2，fmax(A)=+∞。

根據(jù)上式可以計(jì)算出fmin(A)和fmax(A)。

為了避免對“無窮”的計(jì)算操作，利用論域U=[Umin,Umax]的上下限對正負(fù)無窮進(jìn)行取代，即

當(dāng)s=1時，fmin(A)=0，fmax(A)=71；

當(dāng)s=2時fmin(A)=71，fmax(A)=84.2；

當(dāng)s=3時，fmin(A)=84.2，fmax(A)=100。

(3)根據(jù)fmin(A)、fmax(A)計(jì)算ave。

s=2時，ave=(1/3)*(1/13.2)=1/39.6。

s=3時，ave=(1/3)*(1/15.8)=1/47.40。

(4)計(jì)算模糊集的隸屬函數(shù)的極大值點(diǎn)max(A)。

s=2時，max(A)=E(N,attr)=77.6。

s=3時，max(A)=f-1(x)=E+

(5)確定A的隸屬函數(shù)。

模糊集A1、A2、A3對應(yīng)的極大值點(diǎn)分別為max1=49.3，max2=77.6，max3=87.6，max0=Umin=0，max4=Umax=100。

A1(x)=

Ai=2(x)=

At(x)=

3.3 在不同的ε下計(jì)算區(qū)間匹配

要查找成績優(yōu)秀的學(xué)生，取ε=0.5，使A3(x)>0.5，得x的區(qū)間為[77.6,100]，查表將成績按升序排序可知對應(yīng)的結(jié)果如表2所示。

表2 ε=0.5時所得結(jié)果

取ε=0.87，使A3(x)>0.87，得x區(qū)間為[82.6,100]，查表將成績按升序排序可知對應(yīng)結(jié)果如表3所示。

表3 ε=0.87時所得結(jié)果

由上可知，ε越大，所得的結(jié)果區(qū)間越小，準(zhǔn)確度越高。

4 結(jié)束語

以模糊集理論為基礎(chǔ)，通過正態(tài)分布函數(shù)的密度函數(shù)的某些特性設(shè)定了一個總的模糊化自動匹配算法，可以利用樣本中已有的信息對所有的模糊集都設(shè)置一個相對較為準(zhǔn)確的隸屬函數(shù)，可以通過該隸屬函數(shù)對模糊集進(jìn)行自動匹配，減少了用戶自己設(shè)定隸屬函數(shù)的主觀性，大大提高了結(jié)果的準(zhǔn)確度。該算法很大程度上增加了用戶友好性，能夠滿足用戶對模糊查詢的需求，但是也存在一定的局限性。比如需要計(jì)算出所有數(shù)據(jù)的平均值和方差，數(shù)據(jù)量越大時，需要的內(nèi)存越多，計(jì)算的效率會相應(yīng)降低，這是今后需要改進(jìn)的地方。但是當(dāng)數(shù)據(jù)量越大時，數(shù)據(jù)的一般性越能體現(xiàn)出來，所得結(jié)果的準(zhǔn)確度也會相應(yīng)提高。