论文部分内容阅读
张波1，姜旭2
摘要：为了从语义层次上解决P2P资源匹配问题，本体论被引入，试图通过采用可扩展的信息建模工具使得网络资源发现系统能够高效、精确地发现P2P网络资源，同时获得良好的灵活性。然而当前采用的技术要求网络节点共享一个集中的网络资源本体，这种技术不适合高度动态性和分散性的P2P网络。提出一种基于局部本体的P2P网络全局知识视图构建方法，提供了网络资源的全局描述，同时保持了对资源语义的揭示，这种方法不需要网络节点维护一个共享的集中的本体，可扩展性强，对资源的描述更灵活，更适合用于P2P网络资源匹配。
关键词：本体；P2P， 本体映射；知识视图
中图分类号：TP301 文献标识码：A 文章编号：1007-9599 （2012） 19-0000-03
1 介绍
随着P2P（对等网络）技术的飞速发展，对网络节点的信息存储、传输和处理能力的要求迅速增长，对海量信息的搜索与利用成为当前P2P网络资源搜索技术的一个重要研究和应用领域。目前实用化的P2P资源搜索技术主要是基于关键字的匹配，其对资源信息的语义的揭示上有局限性。本体论[5]作为一种能够在语义和知识层次上描述资源信息系统概念模型的建模工具，自提出以来就引起国内外众多科研工作者的广泛关注。本文提出一种基于P2P网络局部本体概念聚类，构建网络全局知识视图的方法，全局知识视图为分散在网络中的节点提供了网络资源全局视图的结构化描述，为在P2P网络中进行基于局部本体的分布式资源匹配提供了有效途径。
2 相关技术
2.1 本体
本体[5] （ontology）是用于描述或表达某一领域知识的一组概念或术语，既可用于组织知识库较高层次的知识抽象，也可用来描述特定领域的知识。本体通过知识来表示元语，从而捕获某个领域的语义，使得机器能够（部分）理解该领域中概念间的关系，通过公理或规则，还可以捕获其他知识，如领域背景知识等。本文中将本体定义为 ，其中C表示概念集合；P表示属性集合；R表示关系集合；A表示公理集合。概念表示特定领域中的一组或一类实体或者事物，每个概念可以由属性分别描述其不同方面的特点；关系描述了概念与概念之间或者属性与属性之间的关系。关系主要可以分为两类：分类关系（taxonomic relationship）和关联关系（associative relationship）。分类关系表示概念与概念之间的父类，子类等上下位的层次关系；关联关系表示除了上下位层次关系以外的其它关系。属性是从不同方面，不同角度对概念的描述。公理用来表示概念或者实例的约束。
3 全局知识视图的构造
在P2P网络中，每个节点的资源由它自己的本体来描述语义，即局部本体。通过对底层局部本体的分析后建立一个共享的全局知识视图。局部本体的每一个概念和属性都将映射到全局视图对应的视图元素上。当增加新的资源时，只需要增加新的映射关系，而不需要对原有的映射和全局知识视图进行过多的更改。
全局知识视图从宏观上对P2P网络中的数据源的信息进行了统一的描述；相对于全局知识视图而言，微观上，局部本体除了定义概念、属性等基本部分之外，还可以定义局部数据源的位置，类型等信息，供下一步查询调用时使用。本文构建全局知识视图的步骤如下：
（1）分析P2P网络各局部资源本体中的概念间的相似关系；
（2）基于局部本体之间概念的相似关系生成知识视图元素；
（3）建立局部本体中概念、属性与全局知识视图元素的映射关系。
3.1 局部本体间的概念聚类
构建全局知识视图的一个重要内容是发现不同局部本体中存在的语义级的概念关联，通过语义的联系将不同本体内的概念映射到全局知识视图元素上，其中最基本的步骤是分析概念之间的相似关系，随后提取出概念间的共性的部分将其映射到全局知识视图中。假设在一个P2P网络中存在n个节点分别提供自身资源的局部本体描述： ，对应第i个局部本体的概念集 中所包含的概念数为 ，那么理想情况下，全局知识视图中对应于概念的视图元素的数量是 ；实际情况中，由于局部本体间的异构性造成具有等价或者相似的概念在全局视图中有多个知识视图与之对应，这种冗余造成知识视图的体积过于庞大，最差情况下，如果概念集中的每个概念都对应于一个全局视图元素，那么全局概念视图元素的数量将达到 ，假定相似度计算为基本运算，整个网络中本体的概念相似度计算的复杂度将达到 。因此，本文考虑将局部本体中的概念进行聚类，从而降低概念间关系分析的复杂性。
3.2 全局视图元素的构造
知识视图元素是对本体中实体的抽象，视图元素的构造过程正是对本体中实体的抽象过程，3.1节中描述的概念聚类算法是进行这一抽象过程的基础。
在本体中，概念间主要包括四类主要关系：等价关系（equivalentClass），继承关系（subClassof），关联关系（associateWith），不相交关系（disjointWith）。在构造视图时，视图元素之间的关系也应当体现概念间的这些主要关系，并且由于不相交关系的普遍性，在知识视图中不考虑元素的不相交关系，在构造视图元素之前，基于由概念聚类算法所得到的类簇，通过本体推理机（如RacerPro）和领域本体得到类簇内各概念之间的等价关系。对于相互等价的概念，在知识视图中用一个视图元素表示，因此，类簇 中的每个等价类对应于知识视图中的一个视图元素。基于此，将概念间等价关系简记作 ，概念 所属等价类记作 ，即若概念 满足 ，记作 ，对类簇 进行等价划分并且对应每个等价类创建相应的视图元素。
3.3 全局视图元素间关系构造
视图元素间的关系反映了本体中实体之间的关系，例如，概念间的等价关系使得概念由同一个视图元素表示，概念间的继承关系也应该在相应视图元素之间体现。简记概念 对应的视图元素为 ，构建全局视图元素间的关系规则如下： （1）对于概念 ，若其满足 ，则 ，即概念 在视图中对应的视图元素相同：3.2节中，视图元素的构造已经保证了这一点，概念 若满足 ，则它们属于相同的等价类，因此可以保证 。
（2）对于概念 ，若其满足 即若概念 是概念 的子概念，则构建关系 ，其中 是对应于 的二元关系：该规则保证，若概念 是概念 的子概念，那么它们在知识视图中对应的视图元素也具有联系。
（3）对于概念 ，若它们的类层次体系中有公共的祖先概念，即若 使得 ，那么 有关联关系。
3.4 全局知识视图的维护
对于P2P节点资源的更新（包括添加，删除）如果引起了局部本体变化，全局知识视图要做相应的变化如下：
添加规则：如果被添加概念 ， 使得 ，其中 是类簇 的等价类，那么知识视图不作变化，否则新增视图元素 ，根据 与其他概念的关系，调整 在视图中的位置。
删除规则：如果对于被删除概念 ， 使得 ，其中 是类簇 的等价类，仅删除视图元素 及其联系，否则将等价类 一并删除。
4 分析及实验
4.1 概念聚类效果分析
如果直接在P2P网络局部本体的概念之间进行相似度计算，假定局部本体中概念总数是N，那么计算相似度的复杂性是 。本文采取先对概念进行聚类再进行相似度计算，假定每个类簇概念树相当，那么存在k个类簇的情况下，相似度计算的总次数是： 次，平均复杂度是： ，但是在实际情况中，局部本体中的概念所属于的领域本体数量并不多，通常只有少数几个，所以实际上并不能达到 的复杂度。但是对先对概念进行聚类可以有效的减少相似度的计算次数。
4.1.1 相似度计算次数比例随类簇数变化分析
图4.1.1中，横坐标为类簇数量 ，纵坐标为相似度计算次数比例 ，其中， 表示对概念进行聚类后所进行的相似度计算次数， 表示对概念进行聚类后所进行的相似度计算次数。假设，概念数为1000，初始类簇数量 少于20个，并且每个类簇中的概念数量服从随机分布，图5.1.1显示了随类簇数量变化，聚类前后实际计算次数的比例变化。随着类簇数量的增多，相似度计算次数有效得到减少，当 增加到一定程度之后，r减少的速度减缓。说明 增大到一定数量后继续在增大并不能有效使r减小，应当把 控制在合理范围内，在实际聚类过程中， 的大小取决于网络中的概念所涉及的领域本体数量的大小。
图4.1.1聚类后相似度计算次数比例随类簇数量变化图
4.1.2 相似度计算次数比例随类簇数量变化分析
图4.1.2中，横坐标为概念数量 ，纵坐标为相似度计算次数比例 ，其中， 表示对概念进行聚类后所进行的相似度计算次数， 表示对概念进行聚类后所进行的相似度计算次数，图线L1、L2、L3分别对应类簇数为4、8、12。途中显示，当类簇数一定时，相似度计算次数比例r随概念数量 没有明显变化，即相似度计算次数比例r与概念数量 ，无关。同时，相似度计算次数比例r随类簇数量 的增大而减少，和图4.1.1的结果相符。
4.1.3 视图构造效果分析
构造全局知识视图的作用是代替全局本体对网络中的资源语义进行描述，而构造全局知识视图的目标是：收集从不同节点得到的局部本体后，尽量减少对资源语义的重复描述。具体而言，是尽量减少局部本体之间的等价概念在全局知识视图中所对应的视图元素的冗余。因此，本实验分析文本所提出的全局知识视图构造算法减少视图元素冗余的效果。实验参数如表4.1所示：
表4.1 实验参数
由图4.1.3可知，当概念数增多时，视图元素和概念书的比例也相应的增多了。但是这种增多的趋势同时也随概念数的增多而相对变得平缓。并且视图元素和概念数的比例保持在一个比较低的比例，相当于1个视图元素对应3.3个概念。因此，本算法对减少视图元素的冗余是有效的。
5 总结与展望
本文提出了一种基于概念相似度聚类的P2P网络资源语义全局知识视图构造的方法。试图通过按照所属领域不同对概念进行划分，降低在全局知识视图元素构造过程中的概念相似度计算量。基于此的全局知识视图元素构造的规则和方法能够有效地用于全局知识视图的构造。并且实验证明，本视图构造算法有效的减少了视图中视图元素的冗余。
在本文的方法中，相似度的计算与概念聚类、视图元素的构造具有一定相对独立性。相似度计算方法也是当前研究的一个重要内容。相似度计算的准确性间接影响到了视图构造的效果，而相似度计算的速度直接影响到了视图构造的速度。因此，适合于P2P网络资源局部本体间的概念相似度计算方法也非常值得进一步的研究。
参考文献：
[1]Pantel， P.，& Lin， D. K. Discovering Word Senses from Text. Proceeding of ACM SIGKDD Conf. on Knowledge Discovery and Data Mining， Edmonton， Canada， 2002， 613-619.
[2]Do H H， Rahm E. COMA - A system for flexible combination of schema matching approaches[C]. Porceedings of Very Large Data Bases Conference. Roma， Italy. 2001：610-621.
[3]Maedche A， Staab S. Measuring Similarity between Ontologies [C]. Proceedings of the European Conference on Knowledge Acquisition and Management EKAW-2002. 2002：251-263.
[4]C. Felbaum. （1998） WordNet： An Electronic Lexical Database. MIT Press， Cambridge， Massachusetts， 1998.
[5]Gruber T R. A translation approach to portable ontology specifications： [Tech Rep]. Stanford University， Logic-92-1.1993.
[6]Maedche A， Motik B， Silva N， etc. MAFRA – a mapping framework for distributed ontologies [C]： In 13th European Conference on Knowledge Engineering and Knowledge Management EKAW. Madrid， Spain：[s.n.]， 2002.
摘要：为了从语义层次上解决P2P资源匹配问题，本体论被引入，试图通过采用可扩展的信息建模工具使得网络资源发现系统能够高效、精确地发现P2P网络资源，同时获得良好的灵活性。然而当前采用的技术要求网络节点共享一个集中的网络资源本体，这种技术不适合高度动态性和分散性的P2P网络。提出一种基于局部本体的P2P网络全局知识视图构建方法，提供了网络资源的全局描述，同时保持了对资源语义的揭示，这种方法不需要网络节点维护一个共享的集中的本体，可扩展性强，对资源的描述更灵活，更适合用于P2P网络资源匹配。
关键词：本体；P2P， 本体映射；知识视图
中图分类号：TP301 文献标识码：A 文章编号：1007-9599 （2012） 19-0000-03
1 介绍
随着P2P（对等网络）技术的飞速发展，对网络节点的信息存储、传输和处理能力的要求迅速增长，对海量信息的搜索与利用成为当前P2P网络资源搜索技术的一个重要研究和应用领域。目前实用化的P2P资源搜索技术主要是基于关键字的匹配，其对资源信息的语义的揭示上有局限性。本体论[5]作为一种能够在语义和知识层次上描述资源信息系统概念模型的建模工具，自提出以来就引起国内外众多科研工作者的广泛关注。本文提出一种基于P2P网络局部本体概念聚类，构建网络全局知识视图的方法，全局知识视图为分散在网络中的节点提供了网络资源全局视图的结构化描述，为在P2P网络中进行基于局部本体的分布式资源匹配提供了有效途径。
2 相关技术
2.1 本体
本体[5] （ontology）是用于描述或表达某一领域知识的一组概念或术语，既可用于组织知识库较高层次的知识抽象，也可用来描述特定领域的知识。本体通过知识来表示元语，从而捕获某个领域的语义，使得机器能够（部分）理解该领域中概念间的关系，通过公理或规则，还可以捕获其他知识，如领域背景知识等。本文中将本体定义为 ，其中C表示概念集合；P表示属性集合；R表示关系集合；A表示公理集合。概念表示特定领域中的一组或一类实体或者事物，每个概念可以由属性分别描述其不同方面的特点；关系描述了概念与概念之间或者属性与属性之间的关系。关系主要可以分为两类：分类关系（taxonomic relationship）和关联关系（associative relationship）。分类关系表示概念与概念之间的父类，子类等上下位的层次关系；关联关系表示除了上下位层次关系以外的其它关系。属性是从不同方面，不同角度对概念的描述。公理用来表示概念或者实例的约束。
3 全局知识视图的构造
在P2P网络中，每个节点的资源由它自己的本体来描述语义，即局部本体。通过对底层局部本体的分析后建立一个共享的全局知识视图。局部本体的每一个概念和属性都将映射到全局视图对应的视图元素上。当增加新的资源时，只需要增加新的映射关系，而不需要对原有的映射和全局知识视图进行过多的更改。
全局知识视图从宏观上对P2P网络中的数据源的信息进行了统一的描述；相对于全局知识视图而言，微观上，局部本体除了定义概念、属性等基本部分之外，还可以定义局部数据源的位置，类型等信息，供下一步查询调用时使用。本文构建全局知识视图的步骤如下：
（1）分析P2P网络各局部资源本体中的概念间的相似关系；
（2）基于局部本体之间概念的相似关系生成知识视图元素；
（3）建立局部本体中概念、属性与全局知识视图元素的映射关系。
3.1 局部本体间的概念聚类
构建全局知识视图的一个重要内容是发现不同局部本体中存在的语义级的概念关联，通过语义的联系将不同本体内的概念映射到全局知识视图元素上，其中最基本的步骤是分析概念之间的相似关系，随后提取出概念间的共性的部分将其映射到全局知识视图中。假设在一个P2P网络中存在n个节点分别提供自身资源的局部本体描述： ，对应第i个局部本体的概念集 中所包含的概念数为 ，那么理想情况下，全局知识视图中对应于概念的视图元素的数量是 ；实际情况中，由于局部本体间的异构性造成具有等价或者相似的概念在全局视图中有多个知识视图与之对应，这种冗余造成知识视图的体积过于庞大，最差情况下，如果概念集中的每个概念都对应于一个全局视图元素，那么全局概念视图元素的数量将达到 ，假定相似度计算为基本运算，整个网络中本体的概念相似度计算的复杂度将达到 。因此，本文考虑将局部本体中的概念进行聚类，从而降低概念间关系分析的复杂性。
3.2 全局视图元素的构造
知识视图元素是对本体中实体的抽象，视图元素的构造过程正是对本体中实体的抽象过程，3.1节中描述的概念聚类算法是进行这一抽象过程的基础。
在本体中，概念间主要包括四类主要关系：等价关系（equivalentClass），继承关系（subClassof），关联关系（associateWith），不相交关系（disjointWith）。在构造视图时，视图元素之间的关系也应当体现概念间的这些主要关系，并且由于不相交关系的普遍性，在知识视图中不考虑元素的不相交关系，在构造视图元素之前，基于由概念聚类算法所得到的类簇，通过本体推理机（如RacerPro）和领域本体得到类簇内各概念之间的等价关系。对于相互等价的概念，在知识视图中用一个视图元素表示，因此，类簇 中的每个等价类对应于知识视图中的一个视图元素。基于此，将概念间等价关系简记作 ，概念 所属等价类记作 ，即若概念 满足 ，记作 ，对类簇 进行等价划分并且对应每个等价类创建相应的视图元素。
3.3 全局视图元素间关系构造
视图元素间的关系反映了本体中实体之间的关系，例如，概念间的等价关系使得概念由同一个视图元素表示，概念间的继承关系也应该在相应视图元素之间体现。简记概念 对应的视图元素为 ，构建全局视图元素间的关系规则如下： （1）对于概念 ，若其满足 ，则 ，即概念 在视图中对应的视图元素相同：3.2节中，视图元素的构造已经保证了这一点，概念 若满足 ，则它们属于相同的等价类，因此可以保证 。
（2）对于概念 ，若其满足 即若概念 是概念 的子概念，则构建关系 ，其中 是对应于 的二元关系：该规则保证，若概念 是概念 的子概念，那么它们在知识视图中对应的视图元素也具有联系。
（3）对于概念 ，若它们的类层次体系中有公共的祖先概念，即若 使得 ，那么 有关联关系。
3.4 全局知识视图的维护
对于P2P节点资源的更新（包括添加，删除）如果引起了局部本体变化，全局知识视图要做相应的变化如下：
添加规则：如果被添加概念 ， 使得 ，其中 是类簇 的等价类，那么知识视图不作变化，否则新增视图元素 ，根据 与其他概念的关系，调整 在视图中的位置。
删除规则：如果对于被删除概念 ， 使得 ，其中 是类簇 的等价类，仅删除视图元素 及其联系，否则将等价类 一并删除。
4 分析及实验
4.1 概念聚类效果分析
如果直接在P2P网络局部本体的概念之间进行相似度计算，假定局部本体中概念总数是N，那么计算相似度的复杂性是 。本文采取先对概念进行聚类再进行相似度计算，假定每个类簇概念树相当，那么存在k个类簇的情况下，相似度计算的总次数是： 次，平均复杂度是： ，但是在实际情况中，局部本体中的概念所属于的领域本体数量并不多，通常只有少数几个，所以实际上并不能达到 的复杂度。但是对先对概念进行聚类可以有效的减少相似度的计算次数。
4.1.1 相似度计算次数比例随类簇数变化分析
图4.1.1中，横坐标为类簇数量 ，纵坐标为相似度计算次数比例 ，其中， 表示对概念进行聚类后所进行的相似度计算次数， 表示对概念进行聚类后所进行的相似度计算次数。假设，概念数为1000，初始类簇数量 少于20个，并且每个类簇中的概念数量服从随机分布，图5.1.1显示了随类簇数量变化，聚类前后实际计算次数的比例变化。随着类簇数量的增多，相似度计算次数有效得到减少，当 增加到一定程度之后，r减少的速度减缓。说明 增大到一定数量后继续在增大并不能有效使r减小，应当把 控制在合理范围内，在实际聚类过程中， 的大小取决于网络中的概念所涉及的领域本体数量的大小。
图4.1.1聚类后相似度计算次数比例随类簇数量变化图
4.1.2 相似度计算次数比例随类簇数量变化分析
图4.1.2中，横坐标为概念数量 ，纵坐标为相似度计算次数比例 ，其中， 表示对概念进行聚类后所进行的相似度计算次数， 表示对概念进行聚类后所进行的相似度计算次数，图线L1、L2、L3分别对应类簇数为4、8、12。途中显示，当类簇数一定时，相似度计算次数比例r随概念数量 没有明显变化，即相似度计算次数比例r与概念数量 ，无关。同时，相似度计算次数比例r随类簇数量 的增大而减少，和图4.1.1的结果相符。
4.1.3 视图构造效果分析
构造全局知识视图的作用是代替全局本体对网络中的资源语义进行描述，而构造全局知识视图的目标是：收集从不同节点得到的局部本体后，尽量减少对资源语义的重复描述。具体而言，是尽量减少局部本体之间的等价概念在全局知识视图中所对应的视图元素的冗余。因此，本实验分析文本所提出的全局知识视图构造算法减少视图元素冗余的效果。实验参数如表4.1所示：
表4.1 实验参数
由图4.1.3可知，当概念数增多时，视图元素和概念书的比例也相应的增多了。但是这种增多的趋势同时也随概念数的增多而相对变得平缓。并且视图元素和概念数的比例保持在一个比较低的比例，相当于1个视图元素对应3.3个概念。因此，本算法对减少视图元素的冗余是有效的。
5 总结与展望
本文提出了一种基于概念相似度聚类的P2P网络资源语义全局知识视图构造的方法。试图通过按照所属领域不同对概念进行划分，降低在全局知识视图元素构造过程中的概念相似度计算量。基于此的全局知识视图元素构造的规则和方法能够有效地用于全局知识视图的构造。并且实验证明，本视图构造算法有效的减少了视图中视图元素的冗余。
在本文的方法中，相似度的计算与概念聚类、视图元素的构造具有一定相对独立性。相似度计算方法也是当前研究的一个重要内容。相似度计算的准确性间接影响到了视图构造的效果，而相似度计算的速度直接影响到了视图构造的速度。因此，适合于P2P网络资源局部本体间的概念相似度计算方法也非常值得进一步的研究。
参考文献：
[1]Pantel， P.，& Lin， D. K. Discovering Word Senses from Text. Proceeding of ACM SIGKDD Conf. on Knowledge Discovery and Data Mining， Edmonton， Canada， 2002， 613-619.
[2]Do H H， Rahm E. COMA - A system for flexible combination of schema matching approaches[C]. Porceedings of Very Large Data Bases Conference. Roma， Italy. 2001：610-621.
[3]Maedche A， Staab S. Measuring Similarity between Ontologies [C]. Proceedings of the European Conference on Knowledge Acquisition and Management EKAW-2002. 2002：251-263.
[4]C. Felbaum. （1998） WordNet： An Electronic Lexical Database. MIT Press， Cambridge， Massachusetts， 1998.
[5]Gruber T R. A translation approach to portable ontology specifications： [Tech Rep]. Stanford University， Logic-92-1.1993.
[6]Maedche A， Motik B， Silva N， etc. MAFRA – a mapping framework for distributed ontologies [C]： In 13th European Conference on Knowledge Engineering and Knowledge Management EKAW. Madrid， Spain：[s.n.]， 2002.