基于商空间粒度计算的资源检索技术研究∗

孙维智 邓 婵

（长沙师范学院 长沙 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 结语

针对现今互联网海量资源数，资源检索速度越来越慢，资源库服务器硬件成本越来越高昂的特点，本文提出基于商空间粒度计算的资源检索技术，通过对资源库分层递阶，从粗到细、逐步求精的检索方式，相对于传统检索方式——检索平台总资源库的检索方式，大大提高了使用者的检索效率。实验结果表明，基于商空间粒度计算的资源检索模式能更加高效高质地完成使用者的资源检索需求。本文主要研究了商空间粒度计算在资源库检索中的应用，随着互联网资源库资源总量的飞速增涨，利用商空间粒度计算的相关特性来提高资源检索效率，降低平台资源库的硬件成本。在今后的研究中，进一步深入研究商空间粒度计算并将其应用到移动学习平台、碎片化学习中去，进一步提高资源检索时间与检索效率，让我们未来的学习环境更加宽松，学习手段更加多样化。