基于商空間粒度計算的資源檢索技術研究?

孫維智 鄧 嬋

（長沙師范學院 長沙 410100）

1 引言

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

2 資源檢索

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

3 基于商空間粒度計算的資源檢索技術實現

3.1 基于商空間粒度計算的資源檢索結構圖

傳統檢索手段的資源檢索均通過對資源總庫所有領域資源查詢某關鍵字詞檢索，在現今資源總庫數據信息量飛速增漲的時候，不僅是資源檢索時間延長，設備的配置要求也越來越高［9］。傳統資源總庫分本體、地域、主題等多種類型分層遞階的資源庫結構，上述是其應用最廣泛的類型［10］。雖然傳統資源總庫分多種類型的拓撲結構，但這些類型都有同樣的缺點：各層次結構節點之間不能做相互的計算比較，各節點與查詢關鍵字詞之間不能比較。而本文提出的基于商空間粒度計算的資源檢索相對于傳統手段資源檢索就有了很大的提高，如圖1所示。

圖1 基于商空間粒度計算的資源結構圖

3.2 商空間粒度計算

說到商空間粒度計算，首先我們要談到粒計算［11］。粒計算其實分兩部分：一是如何對問題進行粒化，二是粒化后的問題如何計算求解。首先，我們可以通過個人理解將問題通過近似性、松散耦合性等分解成若干個不同層次的具體問題粒子；然后，通過同一層次不同粒子或者不同層次粒子相互間推理轉換或者用映射代表不同層次的粒子層的相互聯系以及不同層次的粒子層出現同樣問題的表示［12］。

粒子是粒計算中最小單元，是通過某種手段從整個復雜問題中剝離出來的最小單元問題［3］，其形式化如下所示。

設W 為論域，W 上所有公式的集合為Line（W），i元公式為α∈Line（W），α 的語義集|α|是Wi中所有滿足α的i元組構成的集合。

設W 為論域，W 上所有公式的集合為Line（W），論域W 的粒子空間對應為＜W，Line（W）＞。α∈Line（W），α 的語義集|α|稱之為公式α在粒子空間上相對應得粒子。

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

粒計算中最常用的方法即為商空間粒計算［13］，本文研究的資源檢索是通過商空間粒度計算來實現的。在商空間理論中研究對象用（X，f，T）這個三元組來表示。問題的論域用X 表示，論域的屬性函數用f 表示，論域的拓撲結構用T 表示。設R 為從不同層次或角度考察問題（X，f，T）中定X 的一個等價關系，其對應的商空間（X′，f′，T′），X′為等價關系R 從不同層次或角度考察問題而產生的商集，f′為商集X′對應的商屬性，T′為商集X′對應的商結構。其形式化如下所示：

問題為（X，f，T），R 為等級關系，（X，f，T）的商空間為（X′，f′，T′）：

X′：等價關系R 從不同層次或角度考察問題（X，f，T）而產生的商集，對應論域X；

f′：設f：X→Z 為論域的屬性函數，f′則為X′→Z；

T′：設論域的拓撲結構為T，商空間拓撲則為T′定義為：X→X′的自然投影為Q，｛w|Q-1（w）∈T，w∈X′｝。

商空間粒計算過程中最核心的部分是商空間粒度的獲取［14］，即將問題分解到不同的粒度層次中，在每個不同的粒度層次中又有各不相同粒度的粒子，對這些最小單元的粒子分析和求解問題，將使得復雜問題簡單化，最后綜合不同粒度層各不同粒子的結果得出最終原復雜問題的答案。我們可以從三個不同的方向來獲取適當的商空間粒度：論域方向、屬性函數方向和結構的顆粒化方向［15］。

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

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

從結構的方向可以設問題（X，f，T），取較粗拓撲Ta，構造問題（X，f，Ta），新構造的問題即為原問題的粗粒度分析。

3.3 商空間粒度計算在資源檢索中的應用

根據商空間粒度計算理論，從粗到細，逐步求精的檢索方式是對圖1 所示分層遞階資源庫的最佳檢索手段。如：假設通過查詢語句來檢索資源庫，資源庫共有i 層，每層節點數為im個，用Teamm表示第m 個元素，學習者的檢索等階用集合Team?Set保存，中間結果的保存處理為TeamSetL，則該商空間粒度計算在學習平臺資源檢索的具體執行步驟如下：

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

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

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

第3步：如Level=i+1，則轉第6步；

第4步：TeamSetL=NULL；

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

對于Teamm的每個子節點Teamc，執行以下操作：

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

如Teamc與S一致，則Teamc=TeamSet，轉第6步；

如S≠0，則Teamc加入TeamSetL；

第5步：TeamSetL=TeamSet，Level值+1，轉第3步；

第6 步：按照傳統排序檢索方法對集合TeamSet 內的等價類結果集反饋給學習者；

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

4 實驗及結果分析

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

表1 實驗資源庫兩種檢索方式用時

可以從實驗結果看出，本實驗分別用傳統檢索方式和商空間粒度計算算法檢索方式對不同資源庫進行檢索，如表1 所示。由于傳統檢索方式是對整個資源庫進行檢索，而商空間粒度計算采用了從粗到細逐步求精的檢索方式，相對比商空間粒度計算在資源庫中的檢索區域高度縮減，明確了所需檢索內容的檢索區域。在該實驗資源庫檢索實例中，基于商空間粒度計算的資源檢索效果相對于傳統檢索方式所需檢索時間來說，有了明顯的提高。

5 結語

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