孫維智 鄧 嬋

（長(zhǎng)沙師范學(xué)院 長(zhǎng)沙 410100）

1 引言

粒概念的提出最先是在1979 年由Zadeh 提出的，之后1997年T.Y.Lin正式提出了粒計(jì)算，所謂的粒計(jì)算其實(shí)就是一種方法——看待客觀世界的方法［1］。粒計(jì)算就是將一個(gè)復(fù)雜的問(wèn)題通過(guò)某種方式劃分了若干個(gè)不等粒子，然后對(duì)這些不等粒子進(jìn)行分析解決。其本質(zhì)就是將一個(gè)復(fù)雜的問(wèn)題通過(guò)某種手段分割成若干個(gè)相對(duì)簡(jiǎn)單的問(wèn)題，然后對(duì)分開(kāi)解答這些簡(jiǎn)單問(wèn)題后有助于解答原有的復(fù)雜問(wèn)題。隨著粒計(jì)算的發(fā)展，現(xiàn)今粒計(jì)算的理論分三個(gè)方向延伸：模糊邏輯方向、粗糙集方向和商空間方向［2］。其中商空間方向的粒計(jì)算理論相對(duì)于其他兩個(gè)方向的粒計(jì)算理論有著其獨(dú)特的優(yōu)勢(shì)，所以商空間方向的粒計(jì)算理論相對(duì)發(fā)展迅速。從20 世紀(jì)90 年代起，由安徽大學(xué)張鈴教授基于人類智能的特點(diǎn)最先提出了商空間理論，建立了完整的一套理論——粒度世界模型［3］。引入結(jié)構(gòu)的概念通過(guò)結(jié)構(gòu)層分析解決問(wèn)題是商空間與其他粒技術(shù)理論的最大區(qū)分點(diǎn)。2003 年張鈴教授在這基礎(chǔ)上又推出了模糊商空間理論［4］，2012年張鈴教授最商空間理論做出了進(jìn)一步的研究，在模糊商空間理論中增加了非隸屬度函數(shù)，通過(guò)該函數(shù)對(duì)模糊的客觀世界更加細(xì)膩描述［5］。商空間理論的特性與互聯(lián)網(wǎng)海量資源特性具有一定的相似性，據(jù)此本文提出了基于商空間粒度計(jì)算的檢索技術(shù)，將商空間理論與資源檢索相結(jié)合，在確保檢索結(jié)果的準(zhǔn)確性的同時(shí)，進(jìn)一步降低檢索時(shí)間和檢索成本。

2 資源檢索

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)資源的爆炸式增漲，人類的知識(shí)汲取方式也隨著發(fā)生了改變。從最初的課堂教學(xué)的知識(shí)汲取模式慢慢轉(zhuǎn)變?yōu)閺木W(wǎng)絡(luò)資源中汲取知識(shí)，而面對(duì)互聯(lián)網(wǎng)上海量的資源數(shù)，如何從眾多同類型的資源中提取中最優(yōu)秀資源成為了使用者面臨的迫切需要解決的問(wèn)題。如何快速高效地從中檢索出使用者所急需的學(xué)習(xí)資源，成為現(xiàn)今資源檢索方向的研究熱點(diǎn)。最初我們?cè)谏暇W(wǎng)的時(shí)候登錄網(wǎng)頁(yè)首頁(yè)都設(shè)置了一個(gè)導(dǎo)航網(wǎng)站，其實(shí)這個(gè)導(dǎo)航網(wǎng)站就是第一代的資源檢索階段，我們稱之為分類目錄階段［6］；隨著資源檢索技術(shù)的發(fā)展，耳熟目詳?shù)膅oogle 成為第二代資源檢索階段的代表，通過(guò)檢索引擎結(jié)合網(wǎng)頁(yè)內(nèi)容相似度和重要性來(lái)提高使用者的檢索效率和質(zhì)量。并在二代的基礎(chǔ)上改進(jìn)鏈接分析算法發(fā)展到第三代檢索引擎［7］。現(xiàn)如今檢索引擎所使用的以谷歌為例，谷歌的檢索引擎使用的PageRank Algorithm 算法，谷歌就是通過(guò)這種算法從雜亂無(wú)章的250 億份文件中高質(zhì)高效地找到你所要檢索的結(jié)果，PageRank Algorithm算法最先是由Sergey Brin 和Lawrence 提出的［8］，它的主要指導(dǎo)思想是鏈接到該網(wǎng)頁(yè)的網(wǎng)頁(yè)數(shù)量和質(zhì)量決定其重要性。通過(guò)PageRank Algorithm 算法，現(xiàn)有的檢索引擎能檢索出使用者的檢索要求，但隨著互聯(lián)網(wǎng)資源的爆炸式增漲，檢索資源的海量增加，通過(guò)PageRank Algorithm 算法檢索資源速度也越來(lái)越慢，資源服務(wù)器硬件成本也越來(lái)越高昂，針對(duì)這一特點(diǎn)，本文提出基于商空間粒度計(jì)算的資源檢索技術(shù)，通過(guò)對(duì)資源庫(kù)分層遞階，從粗到細(xì)、逐步求精的檢索方式，相對(duì)于傳統(tǒng)檢索方式——檢索資源總庫(kù)的檢索方式，大大提高了使用者的檢索效率。

3 基于商空間粒度計(jì)算的資源檢索技術(shù)實(shí)現(xiàn)

3.1 基于商空間粒度計(jì)算的資源檢索結(jié)構(gòu)圖

傳統(tǒng)檢索手段的資源檢索均通過(guò)對(duì)資源總庫(kù)所有領(lǐng)域資源查詢某關(guān)鍵字詞檢索，在現(xiàn)今資源總庫(kù)數(shù)據(jù)信息量飛速增漲的時(shí)候，不僅是資源檢索時(shí)間延長(zhǎng)，設(shè)備的配置要求也越來(lái)越高［9］。傳統(tǒng)資源總庫(kù)分本體、地域、主題等多種類型分層遞階的資源庫(kù)結(jié)構(gòu)，上述是其應(yīng)用最廣泛的類型［10］。雖然傳統(tǒng)資源總庫(kù)分多種類型的拓?fù)浣Y(jié)構(gòu)，但這些類型都有同樣的缺點(diǎn)：各層次結(jié)構(gòu)節(jié)點(diǎn)之間不能做相互的計(jì)算比較，各節(jié)點(diǎn)與查詢關(guān)鍵字詞之間不能比較。而本文提出的基于商空間粒度計(jì)算的資源檢索相對(duì)于傳統(tǒng)手段資源檢索就有了很大的提高，如圖1所示。

圖1 基于商空間粒度計(jì)算的資源結(jié)構(gòu)圖

3.2 商空間粒度計(jì)算

說(shuō)到商空間粒度計(jì)算，首先我們要談到粒計(jì)算［11］。粒計(jì)算其實(shí)分兩部分：一是如何對(duì)問(wèn)題進(jìn)行?；?，二是?；蟮膯?wèn)題如何計(jì)算求解。首先，我們可以通過(guò)個(gè)人理解將問(wèn)題通過(guò)近似性、松散耦合性等分解成若干個(gè)不同層次的具體問(wèn)題粒子；然后，通過(guò)同一層次不同粒子或者不同層次粒子相互間推理轉(zhuǎn)換或者用映射代表不同層次的粒子層的相互聯(lián)系以及不同層次的粒子層出現(xiàn)同樣問(wèn)題的表示［12］。

粒子是粒計(jì)算中最小單元，是通過(guò)某種手段從整個(gè)復(fù)雜問(wèn)題中剝離出來(lái)的最小單元問(wèn)題［3］，其形式化如下所示。

設(shè)W 為論域，W 上所有公式的集合為L(zhǎng)ine（W），i元公式為α∈Line（W），α 的語(yǔ)義集|α|是Wi中所有滿足α的i元組構(gòu)成的集合。

設(shè)W 為論域，W 上所有公式的集合為L(zhǎng)ine（W），論域W 的粒子空間對(duì)應(yīng)為＜W，Line（W）＞。α∈Line（W），α 的語(yǔ)義集|α|稱之為公式α在粒子空間上相對(duì)應(yīng)得粒子。

設(shè)粒子空間為＜W，Line（W）＞，O=｛|α||α∈Line（W）｝。從Oi到O的i元函數(shù)為f：Oi→O，則＜W，Line（W）＞中的i元算子是f，i大于或等于1時(shí)，確定Oi到O的對(duì)應(yīng)為f，并稱之為粒計(jì)算。

粒計(jì)算中最常用的方法即為商空間粒計(jì)算［13］，本文研究的資源檢索是通過(guò)商空間粒度計(jì)算來(lái)實(shí)現(xiàn)的。在商空間理論中研究對(duì)象用（X，f，T）這個(gè)三元組來(lái)表示。問(wèn)題的論域用X 表示，論域的屬性函數(shù)用f 表示，論域的拓?fù)浣Y(jié)構(gòu)用T 表示。設(shè)R 為從不同層次或角度考察問(wèn)題（X，f，T）中定X 的一個(gè)等價(jià)關(guān)系，其對(duì)應(yīng)的商空間（X′，f′，T′），X′為等價(jià)關(guān)系R 從不同層次或角度考察問(wèn)題而產(chǎn)生的商集，f′為商集X′對(duì)應(yīng)的商屬性，T′為商集X′對(duì)應(yīng)的商結(jié)構(gòu)。其形式化如下所示：

問(wèn)題為（X，f，T），R 為等級(jí)關(guān)系，（X，f，T）的商空間為（X′，f′，T′）：

X′：等價(jià)關(guān)系R 從不同層次或角度考察問(wèn)題（X，f，T）而產(chǎn)生的商集，對(duì)應(yīng)論域X；

f′：設(shè)f：X→Z 為論域的屬性函數(shù)，f′則為X′→Z；

T′：設(shè)論域的拓?fù)浣Y(jié)構(gòu)為T，商空間拓?fù)鋭t為T′定義為：X→X′的自然投影為Q，｛w|Q-1（w）∈T，w∈X′｝。

商空間粒計(jì)算過(guò)程中最核心的部分是商空間粒度的獲?。?4］，即將問(wèn)題分解到不同的粒度層次中，在每個(gè)不同的粒度層次中又有各不相同粒度的粒子，對(duì)這些最小單元的粒子分析和求解問(wèn)題，將使得復(fù)雜問(wèn)題簡(jiǎn)單化，最后綜合不同粒度層各不同粒子的結(jié)果得出最終原復(fù)雜問(wèn)題的答案。我們可以從三個(gè)不同的方向來(lái)獲取適當(dāng)?shù)纳炭臻g粒度：論域方向、屬性函數(shù)方向和結(jié)構(gòu)的顆粒化方向［15］。

從論域的方向可以通過(guò)功能、結(jié)構(gòu)、約束條件、取上確界或取下確界等方面劃分論域，將以上方面中某一方面相似度高的元素劃為同一類，這樣將形成一個(gè)樹(shù)形結(jié)構(gòu)的結(jié)果［16］。

從屬性的值域方面劃分屬性函數(shù)，再通過(guò)屬性函數(shù)形成論域的劃分實(shí)現(xiàn)商空間粒度的獲取。屬性函數(shù)設(shè)為f=（f1，f2，f3，…，fi），fa：X→Za，a=1，2，3…，i，值域的商集X′為對(duì)Za取粒度所得，設(shè)Ra為相對(duì)應(yīng)的等價(jià)關(guān)系，定義Oa：x～z ?fa（x）Rafa（z）為X上的等價(jià)關(guān)系，以上我們得到一個(gè)論域X 上的Ga，更進(jìn)一步得出一個(gè)商空間與之相對(duì)應(yīng)。

從結(jié)構(gòu)的方向可以設(shè)問(wèn)題（X，f，T），取較粗拓?fù)銽a，構(gòu)造問(wèn)題（X，f，Ta），新構(gòu)造的問(wèn)題即為原問(wèn)題的粗粒度分析。

3.3 商空間粒度計(jì)算在資源檢索中的應(yīng)用

根據(jù)商空間粒度計(jì)算理論，從粗到細(xì)，逐步求精的檢索方式是對(duì)圖1 所示分層遞階資源庫(kù)的最佳檢索手段。如：假設(shè)通過(guò)查詢語(yǔ)句來(lái)檢索資源庫(kù)，資源庫(kù)共有i 層，每層節(jié)點(diǎn)數(shù)為im個(gè)，用Teamm表示第m 個(gè)元素，學(xué)習(xí)者的檢索等階用集合Team?Set保存，中間結(jié)果的保存處理為TeamSetL，則該商空間粒度計(jì)算在學(xué)習(xí)平臺(tái)資源檢索的具體執(zhí)行步驟如下：

算法1（商空間粒度計(jì)算資源檢索）：

第1步：初始化：TeamSet=bottom；

第2 步：向量化處理查詢語(yǔ)句；如成功向量化，則Lev?el=1，查詢向量=H，轉(zhuǎn)第3步；如不成功向量化，則轉(zhuǎn)第6步；

第3步：如Level=i+1，則轉(zhuǎn)第6步；

第4步：TeamSetL=NULL；

For（m=1；m ≤Num（TeamSet）；m++）

對(duì)于Teamm的每個(gè)子節(jié)點(diǎn)Teamc，執(zhí)行以下操作：

S=Teamc的屬性向量andH查詢向量；

如Teamc與S一致，則Teamc=TeamSet，轉(zhuǎn)第6步；

如S≠0，則Teamc加入TeamSetL；

第5步：TeamSetL=TeamSet，Level值+1，轉(zhuǎn)第3步；

第6 步：按照傳統(tǒng)排序檢索方法對(duì)集合TeamSet 內(nèi)的等價(jià)類結(jié)果集反饋給學(xué)習(xí)者；

分析算法1 的檢索效率，先考察圖1 中資源庫(kù)的結(jié)構(gòu)，假設(shè)資源庫(kù)共i層，每個(gè)內(nèi)節(jié)點(diǎn)均有d 個(gè)子節(jié)點(diǎn)（d ≥2），第i 層的每個(gè)節(jié)點(diǎn)有k 個(gè)最小單元子資源。我們可以得出：第i層的總節(jié)點(diǎn)數(shù)是di，整個(gè)資源庫(kù)里擁有的最小單元子資源數(shù)為B=k×di。資源庫(kù)Y=｛X，B，E，V（ba，xt）｝，傳統(tǒng)手段檢索資源集X時(shí)，檢索一次所需時(shí)間為K（I）。而算法1 中假設(shè)TeamSet中元素?cái)?shù)≤c 個(gè)，則執(zhí)行K（c×d）次第4 步，執(zhí)行K（i×c×d）次第3步到第5步。因資源庫(kù)層次給定，i 和d 均為常數(shù)，從時(shí)間復(fù)雜度的角度計(jì)算第3到5步為K（c），第6步為K（c×k）。綜上所述，算法1的總時(shí)間復(fù)雜度為K（c+ck）。由上得c 的理論取值范圍為［0，di］，估計(jì)c的平均取值，假定匹配中每次約有一半的幾率類別節(jié)點(diǎn)與查詢相關(guān)，則第i層的c值為di/2i，得出的平均時(shí)間復(fù)雜度為K（（di/2i+di/2ik）× di（1-d）/（1-di））。而相對(duì)于傳統(tǒng)手段資源檢索的平均時(shí)間復(fù)雜度為K（I），即K（k×di×di（1-d）/（1-di））。將算法1 與傳統(tǒng)手段資源檢索的平均時(shí)間復(fù)雜度相對(duì)比，算法1 即商空間層次檢索的時(shí)間復(fù)雜度約為傳統(tǒng)手段檢索的1/2i。由此得出，本文所述將商空間粒度計(jì)算應(yīng)用到學(xué)習(xí)平臺(tái)資源檢索中可極大提高檢索效率，相對(duì)于傳統(tǒng)的資源檢索方式，應(yīng)用了商空間粒度計(jì)算后檢索時(shí)間大大降低，檢索平臺(tái)硬件應(yīng)該也相應(yīng)地降低成本。

4 實(shí)驗(yàn)及結(jié)果分析

為了有效驗(yàn)證本文3.3 章節(jié)中的算法1，我們專門利用圖書(shū)館部分資源構(gòu)建了一個(gè)小型的資源庫(kù)實(shí)驗(yàn)，利用商空間粒度計(jì)算算法實(shí)現(xiàn)資源庫(kù)檢索系統(tǒng)引擎的檢索。分別設(shè)定整個(gè)資源總庫(kù)分為4、5、6層，每層分別對(duì)應(yīng)為9、10、11個(gè)子節(jié)點(diǎn)，最底層的每個(gè)節(jié)點(diǎn)分別對(duì)應(yīng)為6、7、8 個(gè)最小子資源。根據(jù)本文3.3章節(jié)中傳統(tǒng)檢索方式的公式和基于商空間粒度計(jì)算的算法可得，傳統(tǒng)檢索方式所需平均時(shí)間 復(fù) 雜 度 分 別 為K（39366）、K（700000）、K（14172488），而基于商空間粒度計(jì)算的檢索方式所需的平均時(shí)間復(fù)雜度分別為K（2870）、K（25000）、K（249126）。通過(guò)實(shí)驗(yàn)資源庫(kù)兩種檢索方式得出最終檢索所需時(shí)間結(jié)果如表1所示。

表1 實(shí)驗(yàn)資源庫(kù)兩種檢索方式用時(shí)

可以從實(shí)驗(yàn)結(jié)果看出，本實(shí)驗(yàn)分別用傳統(tǒng)檢索方式和商空間粒度計(jì)算算法檢索方式對(duì)不同資源庫(kù)進(jìn)行檢索，如表1 所示。由于傳統(tǒng)檢索方式是對(duì)整個(gè)資源庫(kù)進(jìn)行檢索，而商空間粒度計(jì)算采用了從粗到細(xì)逐步求精的檢索方式，相對(duì)比商空間粒度計(jì)算在資源庫(kù)中的檢索區(qū)域高度縮減，明確了所需檢索內(nèi)容的檢索區(qū)域。在該實(shí)驗(yàn)資源庫(kù)檢索實(shí)例中，基于商空間粒度計(jì)算的資源檢索效果相對(duì)于傳統(tǒng)檢索方式所需檢索時(shí)間來(lái)說(shuō)，有了明顯的提高。

5 結(jié)語(yǔ)

針對(duì)現(xiàn)今互聯(lián)網(wǎng)海量資源數(shù)，資源檢索速度越來(lái)越慢，資源庫(kù)服務(wù)器硬件成本越來(lái)越高昂的特點(diǎn)，本文提出基于商空間粒度計(jì)算的資源檢索技術(shù)，通過(guò)對(duì)資源庫(kù)分層遞階，從粗到細(xì)、逐步求精的檢索方式，相對(duì)于傳統(tǒng)檢索方式——檢索平臺(tái)總資源庫(kù)的檢索方式，大大提高了使用者的檢索效率。實(shí)驗(yàn)結(jié)果表明，基于商空間粒度計(jì)算的資源檢索模式能更加高效高質(zhì)地完成使用者的資源檢索需求。本文主要研究了商空間粒度計(jì)算在資源庫(kù)檢索中的應(yīng)用，隨著互聯(lián)網(wǎng)資源庫(kù)資源總量的飛速增漲，利用商空間粒度計(jì)算的相關(guān)特性來(lái)提高資源檢索效率，降低平臺(tái)資源庫(kù)的硬件成本。在今后的研究中，進(jìn)一步深入研究商空間粒度計(jì)算并將其應(yīng)用到移動(dòng)學(xué)習(xí)平臺(tái)、碎片化學(xué)習(xí)中去，進(jìn)一步提高資源檢索時(shí)間與檢索效率，讓我們未來(lái)的學(xué)習(xí)環(huán)境更加寬松，學(xué)習(xí)手段更加多樣化。