网络资源的名字特征及其在资源组织中的应用研究博士毕业论文.doc

《网络资源的名字特征及其在资源组织中的应用研究博士毕业论文.doc》由会员分享，可在线阅读，更多相关《网络资源的名字特征及其在资源组织中的应用研究博士毕业论文.doc（131页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 博士研究生学位论文题目:网络资源的名字特征及其在资源组织中的应用研究研究方向： 搜索引擎与网络信息挖掘d 导师姓名： d On the Name Characteristics of Digital Resources and Their Applications in Resource Organization Dissertation Submitted toPeking Universityin partial fulfillment of the requirement for the degree of Doctor of Philosophy in Science摘 要本文中，网

2、络资源指在含义上相对独立且完整的非网页类互联网信息资源，通常由一到多个文件按照一定的目录结构组织，常见于FTP服务器和P2P系统的节点中。它们广泛分布在互联网上，是网络用户所关心的重要对象。同时，这些网络资源不仅数量巨大，而且发布、传播和共享都比较自由，呈现出“混乱”和“无序”的特点。广泛收集并重新组织这类网络资源，是许多应用中的一项根本需求。在这项工作中，资源名称是最基本的依据；人们一方面需要根据名称来理解得到的资源，另一方面也要通过对资源命名来标识资源。本文首先考察各类网络资源的命名状况，研究其中蕴含的用户命名行为一般规律；进而研究了如何从资源名中切分出语义片段的方法；并考察了名字信息在资

3、源自动分类中的作用，分析分类性能的影响因素等问题。注意到网络上存在着许多以目录树的形式组织得相当好的资源集合，本文研究了依据目录树信息进行资源整合的效率问题，并针对这类资源整合的任务，设计了一个可扩展性好的资源增量存储与组织方案。作为对上述研究的应用，实现了一个支持海量网络资源存储组织的库藏系统，并为相关领域的研究提供数据和系统平台。本文主要贡献包括：(1) 考察网络资源命名的无序状况，分析用户对资源命名行为的一般规律。通过考察总体与各类别的名字长度、字符构成、片段频度分布、文件后缀对资源类别的互信息、语义种类及位序关系等方面，分析资源的名字无序混乱表象及所蕴含的规律。例如从字符类型熵来看，资

4、源名是用户表达各种资源相关信息的渠道，而其中娱乐类资源名的字符类型熵大于工作学习类的资源名，这体现了用户对娱乐内容的融入感较强，倾向于参与修改名字来反映自己的意见和评价。从符号的出现上看，用户倾向于将多种意思通过显式或隐式分隔信息浓缩在简短的名字中。这些是本文后续名字切分、资源分类等工作的基础。(2) 基于错误驱动转换学习思想和字符类型突变分割假设，提出一种能对资源名按照语义信息切分、且不依赖于词典的方法。这一研究也适用于其他具有多种文字符号混杂、浓缩表达多种语义类型特点的文本环境。该方法优点是能充分利用上下文特征学习，且不要求大规模训练数据。例如给800个训练样本，得到的语义片段的切分精度为

5、81%、召回率为83%。所得的切分结果有助于从混乱的原始命名状态中获取对资源描述有用的信息。(3) 提出一种利用资源及其成员的名字所产生的特征进行资源自动分类的方法，研究了特征分布、概率估算、样本数量等因素对分类性能的影响。发现大量低频特征（例如只在一个资源中出现过）对分类正确率的贡献在于帮助合理估算未观测到的特征的概率；因此也得出在低频特征占优、且使用Simple Good-Turing平滑策略下无需进行特征选择的推论。在使用所有特征情况下，总体分类正确率可达80%。还应用该方法实现了一个资源半自动分类工具，在人工给定资源粒度条件下，进行资源分类的时间是基准时间的45%-50%。(4) 针对

6、原始质量较好的资源集合，提出一种利用原始组织知识的目录归并模型整合资源，刻画粗分类和精细检查两阶段工作模式并评估模型效率。粗分类阶段有精度损失，但完成任务的时间为基准做法的1/2a（a为批量处理的资源数，a1）；精细检查阶段在第一阶段基础上进行，能保证精度无损，且完成任务的时间约为基准做法的1/2。(5) 持续从互联网收集、并运用目录归并模式高效低代价地构建一个容量为7.5TB的海量网络资源库藏系统。通过分类体系和文件目录的映射，并在服务器和磁盘两级用模块化思想设计存储、组织功能，该系统能很好地应对增量式存储、组织和服务需求。系统还基于Ontology思想从互联网上为热点门类的资源扩展相关描述

7、信息。关键词：网络资源，命名分析，组织，自动分类，目录归并On the Name Characteristics of Digital Resources and Their Applications in Resource Organization AbstractIn this dissertation, the term “Digital resource” refers to the non-web page data that is: 1) usually composed by one or more files of various data types, and existin

8、g within some directory structures; 2) representing a single independent topic; 3) widely shared and distributed through FTP sites or P2P file systems; 4) organized by Internet users at will more than well-defined styles. Internet users concern about digital resources more and more. At the same time

9、, digital resources are characterized with mass, disorder and confusion. It is a fundamental demand to widely collect and organize digital resources for many applications. In this work, what is the most basic is the resource names. On the one hand, they provide the clue of meaning of resources. On t

10、he other hand, they are used to identify the resources. This paper first studies the disorder naming status of digital resources, and tries to find out generally naming manners of Internet users. Secondly, the paper studies the method of how to segment the resources names based on semantic meanings.

11、 Thirdly, we study how to make use of resource names in automatic resource classification, and analyze the impact factors on the performance. Noting that there are many well-organized digital resources on the Web, we propose a method to reorganize the resources in different file directories to a coh

12、erent classification framework. And we also evaluate the efficiency of the integration process. As practice to all above mentioned research, we designed and implemented a scalable digital resource library which can support massive volume of digital resources and is capable of providing data and serv

13、ices for many academic institutions. In this paper, contributions are listed as follows:1) Study the disorder naming status of digital resources, and find out the generally naming manners of Internet users. By examining the name length, the character type, the fragment frequency distribution, the po

14、int mutual information of file extensions with resources categories and the semantic information, we get an overall knowledge on the disorder and chaos of resource names. For example, from the information entropy of character type, the resource names act as expression medium where the Internet users

15、 are apt to add information about digital resource, such as short description, personal viewpoints, etc. From the symbol appearance, we can know the Internet users often use explicit or implicit separators among name texts to designate the transition of different semantic meanings. These studies are

16、 the base of the later research of this dissertation.2) Propose a segmentation approach which is able to detect the semantic snippets in the digital resource names without any lexicons. The approach is based on the idea of Transformation-Based Error-Driven Learning and the assumption of splitting na

17、me strings at the position of char-type transition. This way of practice can also be applied to similar problems where texts are composed of various symbols and letters, and concentrated expression of a variety of types of semantic information. The method takes full advantage of context and does not

18、 require large-scale training data. Training on 800 samples, we get a performance of 81% in precision and 83% in recall of all the semantic fragmentations.3) Propose a method using the name of resources and theirs members for automatic resource category. We study on the performance factors such as f

19、eature distribution, the smoothing method on probability estimation, and the number of samples. We found that a large quantity of low-frequency features, especially those which only appears in one resource, contribute to the classification accuracy by helping to get reasonable probability estimation

20、 on the unobserved features. Based on this knowledge, the usual feature selection procedures in text categorization are not necessary in this circumstance. When employing all features acquired from the name strings, the overall accuracy of the classification method proposed here can reach 80%. As an

21、 application of this method, we implemented a semi-automatic classification tool which classified the resources with only 45% to 55% in time cost comparing with the benchmark method. 4) Propose a tree-merge model to map the resources originally organized in file system directories and dispersing in

22、the Internet to a coherent classification architecture. The model performs well when the original organization quality is good and usable enough. There are two phases defined by the model, the first phase is a roughly classification with a little precision loss but rapid committing, and the second i

23、s a refine phase which remedies the incorrect classification to the required quality. In the first phase, the time cost is only 1/2a of the baseline (a is the average number of resources classified in one judgement, a 1). And in the refine phase, the time is only half of that of the baseline. 5) Con

24、tinuously collect digital resources from the Internet and built a 7.5TB resource library system based on the directory tree-merge scheme with low-cost and high-efficient approach. By mapping the classification architecture with the file system directory tree, we implemented the system with modular d

25、esign strategy. Our scheme satisfies the need of incremental storage, organization and service demands. Additionally, we get resource descriptions from the Web based on the aid of purified resource names, the information of categories and the expansion terms of each category.Keywords: Digital resour

26、ce, Naming analyse, Resource organization, Classification, Directory tree-merge - 119 -目 录第1章 绪论11.1研究背景11.2研究目的21.2.1困难与挑战31.2.2研究路线41.3网络资源的概述41.3.1资源在本文中的定义41.3.2资源的数据模型61.3.3网络资源的存储组织模型71.4网络资源的组织及本文研究的意义91.5本文主要工作101.6本文主要贡献121.7本文内容结构13第2章 网络资源名字无序特征与用户命名行为162.1引言162.2基本概念172.3资源命名混乱程度的量化评估172

27、.3.1名字长度分布规律192.3.2通过名字表达资源信息的互补性212.3.3文件名的后缀232.3.4文件后缀和资源类别的关系262.3.5字符构成282.3.6名字片段频度312.3.7语义片段332.4相关研究352.5本章小结36第3章 网络资源名字中语义片段的切分373.1引言373.2语义信息切分概述383.2.1两级映射策略383.2.2字符类型突变分割假设393.2.3自动切分方法相关研究413.3基于错误驱动转换学习的自动切分423.3.1自动学习的基本思想423.3.2切分比较模型443.3.3初始切分器463.3.4规则模板473.3.5规则学习与错误驱动转换493.3

28、.6评估指标503.4实验与分析513.5相关研究533.6本章小结54第4章 网络资源类别自动判定554.1引言554.2如何找到适合的特征554.2.1产生特征的属性554.2.2基本定义564.2.3训练集和测试集574.2.4特征频度分布状况分析584.3分类方法及平滑策略594.3.1分类方法的选择594.3.2平滑策略614.3.3评估指标634.4基于朴素贝叶斯的分类与影响因素634.4.1切分方法、特征数量对性能的影响644.4.2不同类别的精度664.4.3平滑对性能的影响674.5基于支持向量机的分类684.6相关工作714.7本章小结73第5章 目录归并模型与组织效率比较

29、755.1引言755.2目录归并模型755.2.1什么是目录归并755.2.2模型表述765.2.3基于目录归并的资源组织效率评估785.3目录归并模型的局限785.3.1资源原始组织质量可用性795.3.2实验795.3.3异构知识体系合并相关工作835.4网络资源半自动分类工具845.4.1基本思想845.4.2网络资源标注855.4.3设计865.5本章小结86第6章 网络资源组织相关研究886.1资源组织方法886.2网络资源库藏相关工作896.2.1Ibiblio906.2.2Internet Archive916.2.3Wikimedia926.2.4Chinese Digital

30、 Assets Library926.3本章小结93第7章 CDAL的设计与实现957.1引言957.2系统概况957.3系统设计977.3.1系统结构图977.3.2可扩展的存储组织方案987.4网络资源描述信息获取1007.4.1Ontology概述1007.4.2描述信息获取机制1017.4.3改进查询的方法1027.4.4改进排序的方法1027.5一种基于局部聚类思想的共现词汇算法1047.5.1基本定义1057.5.2FDC共现词汇算法1057.6相关研究1067.7本章小结107第8章 总结及展望1088.1总结1088.2未来工作111参考文献113博士期间提交和发表的论文119

31、博士期间参与的科研项目和所获奖励120致 谢121图 示图 11 网络资源样例1图12 Kahn/Wilensky定义的数字对象微观结构6图13 Kahn/Wilensky定义的digital object collection结构6图 14 网络资源的树状存储组织模型8图 15 网络资源所在原始目录树结构示例8图 16 网络资源有序化流程11图 17 各章内容关联14图 21 名字长度分布19图 22 资源名、文件名、子目录名的箱型四分位图20图 23 子目录名长度与资源名长度的关系22图 24 扩展名的文件数频度分布24图 25 前缀后缀特征分布32图 31 资源名字语义片段切分38图 3

32、2 基于错误驱动转换学习方法的资源名语义片段切分过程42图 33 一次迭代中规则自动学习与错误驱动转换实现过程49图 34 基于TBL在不同规模训练样本集上语义片段切分精度、召回率51图 35 不同语义类型对应的切分召回率52图 41 各类别中文件扩展名rm对应的文件大小分布56图 42 SVM分类中对ext_fsize组的特征计算选取权重值70图 51 目录包含公共文件的示例82图 71 CDAL提供的资源访问方式96图 72 CDAL系统结构图98图 73 基于Ontology的网络资源描述信息获取101图 74 概念的属性及其词汇扩展（以电影类资源为例）103图 75 获得描述信息的改进

33、排序算法104图 76 网络资源描述信息展示104表 格表 21 各类别资源80%的名字长度位于的区间上界21表 22 不同名字长度区间的资源中包含的子目录数23表 23 文件后缀长度在后缀集合与文件集合中的概率23表 24 按出现频度和对应文件字节数找到的top5扩展名25表 25 各类别top3扩展名（按照FF、RF）26表 26 后缀特征的频度排序与互信息排序之间的相关度27表 27 总体数据中字符类型出现的混乱程度29表 28 各类别字符类型的熵30表 29 各类别条件概率Top100片段的种类31表 210 语义类型及含义34表 31切分的状态表示与比较运算45表 32 依据触发点状

34、态修正错误45表 33 语义片段切分规则模板47表 34状态真值表与相关运算50表 35 最佳规则序列（前10个）52表 41 各类别先验概率58表 42 前缀特征数与资源频度和64表 43 不同特征集合上朴素贝叶斯分类的总体正确率(AC)65表 44 朴素贝叶斯基于特征集snip10_ext_seg2在各类别中的性能67表 45 不同特征集合RF=0和RF=1特征的概率估计均值和标准差68表 46 不同特征集合上支持向量机分类的总体正确率（AC）70表 47各类别编号、先验概率71表 48 SEWM2008网络资源自动分类评测f1值72表 51 对目录归并模型基础假设的估算检验77表 52

35、S_set中As_set节点的深度与数量比重80表 61资源组织方式对比88表 62 网络资源库藏系统特点89表 71 CDAL主要类别资源量96表 72 两种关联词典的比较107第1章 绪论第1章 绪论1.1 研究背景网络上的信息资源可以分为网页和非网页两大类，非网页类资源是指在网络上传播的除网页之外的各类文本、音视频、图形图像、软件等文件。本文所提及的“网络资源”或“数字资源”是指后者。它们多数是生来数字化的（“born-in-digital”），也有不少传统媒体资源经数字化加工，通过网络共享成为网络资源。图1-1所示“20050108.研究vs开发.rm”就是一个资源，被组织在目录“RE

36、C.录像”中。资源包含2个成员文件分别是报告的讲义和录像，虽然格式和内容不同但它们都是服务于资源的。图 11 网络资源样例从本质上，资源与文件系统中的目录和文件并无区别，但是当它们大量地通过网络在ftp、p2p等平台上传播共享时，就引发了一个值得关注的重要问题：海量资源的有效组织与利用。因为：(1) 共享者都是按照自己的方式组织资源，组织方式的异构性不利于访问者查找所要的内容。如果能将不同来源的内容整合到统一框架中，则会改善资源访问、利用。(2) 共享者可以修改资源的名字，添加便于自己或他人理解的信息，大量共享资源的命名口语化或个性化，也给计算机检索带来不便。如果能识别名字中有效的信息去除噪音

37、，则可用于资源的标识、检索和描述。可以说在互联网环境下，作为一种重要的信息流通媒介，资源的组织和命名都具有很大的无序性。这种无序性给资源的整合利用造成了极大障碍。目前，越来越多的数字资源通过互联网共享和传播，并已经全面影响到人们的工作、娱乐和生活。从2007年12月的中国互联网信息中心（CNNIC）发布的中国互联网络发展状况统计报告CNNIC,2008，我们可以看出与网络资源的使用、传播有关的4个方面趋势：(1) 用户使用网络资源的积极性很高，对网络资源的访问已经超过电子邮件和网页搜索，成为居于首位的互联网应用。(2) 网络资源数量和种类飞速增长，全面影响到人们的工作、学习和娱乐。仅2007年

38、下半年，71.2%的大陆用户下载过音乐，40.5%下载过电影。在澳门地区用户从网络下载的音乐占75.3%、电影占72.1%、工作和学习的资料占66.3%、游戏占42.7%、图片占42.1%、除杀毒软件之外的各类工具软件占38.9%、杀毒软件占37.4%、电视节目占24.7%、小说占23.5%、其他内容占0.9%。(3) 用户参与网络资源的传播共享和创建。Web2.0时代，个人更成为互联网上主动的传播者和生产者，在中国大陆范围内，31.8%的用户上传过图片,17.5%的用户上传过影视节目或者其他视频，用户产生的内容（User Generated Content, UGC）占了其中相当一部分比例。

39、(4) 越来越多的网络资源开始被组织并纳入专门的库藏，用来提供服务。综上，可以看出一方面是日益剧增的资源量和应用需求，一方面是网络资源原始的无序混乱状况，这促使我们关注如何消除网络资源无序性、改善对资源组织利用等问题的研究与技术。我们的研究对象是可以从网络上获得的公开共享的网络资源，多数是用户创建、发布和组织的。这些数字对象的构成、命名表述、原始目录结构等都体现了互联网用户对它们的组织知识，也是我们可以利用的信息。1.2 研究目的本文的研究目的是：(1) 通过考察网络资源的外部、内部属性，发掘可用于组织资源的信息；(2) 在这一过程中提出一套分析和解决相关问题的技术，用较少的人工代价、高效地使

40、海量资源从无序过渡为有序，在资源类别标识、命名准确性、相关描述信息的丰富程度上达到便于访问资源的要求；(3) 作为对上述研究结果的应用，实现一个支持资源增量组织、存储、利用的库藏系统。作为一种重要的互联网精神财富，网络资源是数字图书馆、网络教学资源库藏、专题内容管理系统应用的重要内容来源。当构建上述系统时，本文所探讨的方法、技术能够帮助减轻初期资源组织整理过程中的巨大人工投入、缩短建设周期，促成快速上线的服务。1.2.1 困难与挑战这一工作面临的最大困难来自网络资源的无序性命名随意、版本混乱、一般以单体传播，很少附带元数据和相关描述信息，甚至内容不完整、质量不受控。具体表现在：（一）从内容上，

41、网络资源以非文本的多媒体内容为主，一个资源可能包括音视频、文字等多种数据格式。迄今为止，没有一个适于各种媒体类型的内容分析技术能够在海量数据环境下达到实用性。（二）从命名上，网络资源不同于传统媒体那样有规范的命名和用词。由于发布和传播相对自由，很多资源名字需要有背景知识才知道其含义。此外，用户可以修改资源名把与内容有关的信息甚至自己的看法精简地附加在资源名中，以便于让其他访问者一目了然地“望名知意”，但却给计算机理解造成了极大困惑。例如下面几个资源名，在不长的文本串中浓缩了多种含义包括：别名、发布日期、完整性、客观说明、主观评价等：1. 第三类接触 (Close Encounters of t

42、he Third Kind)The Collectors Edition(特别收藏版) 2. 瑞典 JAS39 (瑞典JAS-39“鹰狮”战斗机)3. 2002.11.14平成狸合战from211.71.57未4. 墨西哥空军雷达拍摄Mexico UFO（非常珍贵，绝不是某些所谓专家所说的球状闪电，也不是流星）（三）从构成上，资源的粒度是依内容而定的，无法依照资源所包含的文件大小、目录层深、成员个数等量化指标决定的。（四）从组织形式上，资源位于目录树中，没有超链接结构 虽然文件系统支持软链接，但由于软链接的对象没有统一定位地址URL，一旦资源被复制、这种链接关系就容易丢失。而互联网上信息的复制

43、、转载是非常普遍的，所以软链接不是解决之道。，所以和自己的成员之间只能通过包含与被包含表示，最多通过子目录表达包含的层次。资源之间即使有相同的文件，也难以共享成员内容。（五）从相关信息的找寻上，也存在很多困难。文本处理中常用的知识扩展手段（如利用语义词典、搜索引擎）在本问题中都不便于直接应用。例如，如果将资源名作查询词提交搜索引擎，用返回结果提取与资源相关的文本内容的话，当资源名不规范或者资源不是流行内容的时候，这种方法往往找到的是噪音而不是有用的文本；同样利用词典对资源名或者资源所属的目录进行语义扩展的时候，也很难找到匹配的信息。因为很多网络资源命名或其所在的原始目录名都是非常个性化的。1.

44、2.2 研究路线网页的大规模利用是从内容分析开始飞速发展的，那是因为信息检索领域对文本的处理和技术相对成熟，也容易适应数据的规模和增长速度。但是对包含多种媒体类型的网络资源而言，基于内容分析的技术对多种视频、音频等数据格式的处理能力和效果是无法满足其海量特性和发展需要的。我们关注整个Web中的多种形式和类别的网络资源，因此着眼点就有所不同。人们发布网页的时候通过超链接表达其相互关联，网络资源则通常会被放入目录结构中，通过目录的名字、层次展现出的组织线索体现它和其他内容的区别联系。因此我们会利用到资源的原始组织、目录名等信息进行资源的再组织。结合1.2.1节对所面临困难的认识，本文认为一个可行的

45、办法是利用资源的可见文本和原始结构做为再组织的线索，如：资源及其成员的名字、原始所在的目录结构及目录名、文件的大小、扩展名等信息。包括：资源混乱命名模式的统计分析；网络资源组织的方法、效率研究；资源名字中的语义信息切分；利用网上丰富的网页文本，对热门类别的资源进一步整合其相关文字，扩充资源的描述，提高有序程度等。在使用网页检索工具的过程中，人们已经体会到，对海量信息的检索利用，不能苛求像数据库检索一样返回精确匹配的答案，而且文本的丰富语义也不能被计算机完全识别判断。就像人们利用搜索引擎查询时，会根据自己的常识判断返回结果的相关性，并可能反馈给系统做进一步改善。本文所探讨的针对海量网络资源有序化

46、的工作也将是渐进发展和完善的，结合部分人工工作达到优化目的。1.3 网络资源的概述1.3.1 资源在本文中的定义在本文中，我们这样表述研究的对象网络资源是指一个表达独立主题、完整内容的文件集合。资源可包括一到多个文件，可以有子目录，通常存储在文件系统中，包含多种格式的数据，如文本、图像、视频、音频。也就是说，并非所有的网络资源都是收藏组织的对象，质量差、内容残缺的资源不在关注范围内。习惯上，我们认为一个资源可以是一本书、一部电影、一首歌曲或一个歌曲专辑、一篇文章或一个作品集、具有同主题的多个图片。由于我们关注的研究对象是原生态的互联网资源，其粒度、组成结构是不受控的，取决于内容的需要和原始拥有者的领域知识及组织观点。这里按照对资源原始状况的观察给出其特征，也可以作为判断一个或一组文件、目录是否一个资源的定性标准：(1) 能独立表达一个实体、事件或意思，内容相对完整。例如事件类资源“20040424北京大学106周年暨北京大学首届国际文化节”中包括文化节这个事件的文字宣传报道、表演节目的照片、视频和音频。通过浏览这样一个资源能够较为全面地了解该事件的背景、盛况和生动细节。(2) 粒度不易量化，资源尺寸要依赖于内容而定，而不是文件数、字节数这样的指标。