一种大规模开源软件标签层次自动构建方法

摘要

一种开源软件标签层次自动化构建方法，包括利用已有的抽取工具将项目标签信息抽取出来，抽取得到的项目标签任意两两之间匹配，形成若干个无向标签对，然后统计出根据所有记录计算出的标签对信息计算出的标签对出现频次，并根据标签频次关系为标签对加上方向，形成边；将有向边相互连接起来就可以形成若干个连通图而得到初步构建的标签层次；获取站点已有分类层次，进行边的比较，对已有分类层次进行优化。具有对开源社区中大规模开源资源进行层次化组织，提高开源软件定位准确性和效率的效果。

说明书

技术领域

本发明涉及一种标签层次自动化构建方法，尤其涉及针对由于互联网上存在大量的开源软件而带来的检索困难问题而提供的开源软件的标签层次自动化构建方法。

背景技术

近年来，随着开源运动的蓬勃发展，大量的开源软件源源不断地融入到各个开源社区(Github，Sourceforge，Openhub等)中，带来了丰富的可重用软件资源，但同时也为资源检索带来了挑战。为了更好地管理如此庞大数量的开源软件，一些社区引入了标签系统，鼓励用户对开源软件进行标注，其中一些社区更是使用了自由的标签系统，允许用户给软件打标签，有些项目可能达到数十个标签。这种标签机制一方面可能会导致标签质量的下降，但是也大大丰富了标签数据，能够从不同的角度对软件进行全面描述。

这些社区借助标签实现了对软件的分类，一定程度上缓解了大规模资源检索的问题。但是由于标签本身的局限性，形成的结构趋于扁平化，没有充分考虑标签之间的关联性，导致基于标签的资源定位效果不理想。如果能够将标签间关系纳入考虑，建立标签层次，将大大提高资源定位的准确性和效率。

目前，构建软件标签层次的方法主要分为两种：人工方法和自动化方法。人工方式(Sourceforge)一般是通过聘请领域专家，利用他们的领域知识，分析、研究、综合处软件标签的层次结构，但是这种方式需要消耗大量的人力、物力。自动化的方式通常利用开源软件的标签进行构建，一般的方法是首先需要度量两个标签标签间的关系；然后依据标签间的关系构建成软件分类层次。一般来说，度量标签间关系方式有两种：广义度和相似度。广义度表示的是在类别层次上，每个标签的通用程度，广义度值越大的标签表示它所代表的类别更宽泛，包含的内容越多，在层次中的位置也就越高。而相似度则说明了两个标签的相似程度。一般采用集合论或者是主题模型去度量标签的广义度或者相似度。就目前我们掌握的资料来看，已有的自动化构建方法只可见于实验条件下，但难以运用在真实场景中。

因此，如何高效地利用已有的标签信息以及已有的分类层次等领域知识，自动化地构建出软件标签的层次结构，从而提高软件检索效率，是本领域技术人员极为关注的重要问题。

发明内容

本发明的目的在于针对现有技术的不足，充分利用已有的分类层次，结合标签语义度量方法，提出一种自动化的软件标签层次构建方法，提高开源软件分类层次结构的质量以及软件检索效率。

本发明的技术方案包括以下步骤：

步骤101、利用通用的爬虫技术将各大开源社区的项目信息页面抓取下来，并利用已有的抽取工具将项目标签信息抽取出来，每一个项目页面可以形成一条字段为<项目名，标签集合>的记录，其中标签集合可以用<标签1><标签2>…<标签n>格式存储，其中n大于等于1，形成一系列项目标签记录，存储到本地数据库A中。

步骤102、对本地数据库A中的每一条记录做如下操作：标签集合中的项目标签任意两两之间匹配，形成若干个无向标签对，然后统计出根据所有记录计算出的标签对信息计算出的标签对出现频次，形成<标签对，频次>关系；同时统计出所有标签的出现频次，作为标签广义度度量。

步骤103、将<标签对，频次>关系按频次进行降序排列，取前N(N大于等于1，其决定层次结构的大小)个关系中的标签对作为层次结构中的边，然后根据标签广义度为这些选中的边加上方向，由广义度大的标签指向广义度小的标签。

步骤104、形成的若干条有向边是若干个连通图的边表示法，将这些边相互连接起来就可以形成若干个连通图，这样连接形成的图都保留，据此，构建出初步的软件标签分类层次结构。之后的优化方法有可能将这若干个图连接起来。

步骤105、根据已有的标签分类层次对初步软件标签分类层次进行优化。

步骤106、定期对各大开源社区的项目信息检查更新信息，如果项目标签有更新，则将页面爬取、抽取，更新到本地数据库A中，执行步骤102及后续步骤，如果没有更新，则睡眠，等待下一次检查。

进一步地，其中步骤105根据已有的标签分类层次进行优化包括：

步骤105.1、利用通用爬虫将同一开源社区中的包含分类层次的页面爬取下来，对所述包含分类层次的页面进行爬取是以某一个包含顶层节点的页面开始，依次爬取包含下层节点结构的页面，然后利用通用抽取工具将其中的分类层次信息提取出来，格式化成起点-＞终点形式的有向边，存储到本地数据库B中。

步骤105.2、对已经初步构建出来的分类层次中的每一条有向边进行检查，如果此边对应的两个顶点在数据库B中出现过，并且两个点由若干条边连接起来路径的方向与初步的分类层次中的路径方向相同，那么，继续检查上述连接起来的路径上的其他点是否在初步分类层次中出现过，如果出现过，则将出现的所述其他点与所述两个顶点形成所有的路径都添加到初步的标签层次结构中；如果两个点由若干条边连接起来路径的方向与初步的分类层次中的路径方向不同，则将此边从初步的标签层次中删除。如果此边对应的两个顶点中的至少一个顶点在数据库B中没有出现，则不做任何处理并保留在当前初步标签层次中。

采用本发明可以达到以下技术效果：

该方法针对构建开源软件层次难度大，成本高等问题，根据软件的标签信息，挖掘出软件标签层次，并充分利用已有的分类层次对结果进行优化，进一步提升分类层次的质量，从而提高软件检索效率，并实现了分类层次的自动化更新，节约了大量的资源，能够满足用户对软件检索质量、效率的需求。

附图说明

图1为本发明自动化的构建软件标签层次流程图；

图2为构建的初步分类层次结构图；

图3为本发明中对初步的分类层次进行优化的流程图。

具体实施方式

如图1所示，为本发明自动化的构建软件标签层次流程图，具体执行以下步骤：

步骤101、利用爬虫(如开源爬虫Webmagic，也可以是通用的其他爬取技术)将各大开源社区的项目信息页面抓取下来，并利用已有的抽取工具(例如XPath)将项目标签信息抽取出来，每一个项目页面可以形成一条字段为<项目名，标签集合>的记录，其中标签集合可以用<标签1><标签2>…<标签n>格式存储，其中n大于等于1，形成一系列项目标签记录，存储到本地数据库A中。

步骤102、对本地数据库A中的每一条记录做如下操作：标签集合中的标签任意两两之间匹配，比如某个项目的标签集合为<tag1><tag2><tag3>，那么标签匹配形成的标签对为<tag1，tag2>、<tag1，tag3>、<tag2，tag3>，由此形成若干个标签对，标签对是无向的。然后统计出根据所有记录计算出的标签对信息计算出的标签对出现频次，形成<标签对，频次>关系；同时统计出所有标签的出现频次，作为标签广义度度量。

步骤103、将<标签对，频次>关系按频次进行降序排列，取前N(N大于等于1，其决定层次结构的大小)个关系中的标签对作为层次结构中的边，然后根据标签广义度为这些选中的边加上方向，所述方向是由广义度大的标签指向广义度小的标签。

步骤104、上述形成的若干条有向边可以认为是若干个连通图的边表示法，将这些边相互连接起来就可以形成若干个连通图，例如图2所示，共有5条边A-＞B，A-＞C，B-＞C，B-＞D，E-＞F那么就可以构建出如图2所示的结构图。这样连接形成的图都保留，之后的优化方法有可能将这若干个图连接起来，据此，构建出初步的软件标签分类层次结构。

步骤105、根据已有的标签分类层次对初步软件标签分类层次进行优化，如图3所示。

利用爬虫将同一开源社区(例如Sourceforge)中的包含分类层次的页面爬取下来(一般是以某一个包含顶层节点的页面开始，依次爬取包含下层节点结构的页面)。然后利用通用抽取工具如XPath将其中的分类层次信息提取出来，这些分类信息原始格式存在在链接中，类似于http：//sourceforge.net/directory/system-administration/distributed-computing/。SystemAdministration就是DistributedComputing的父节点，我们利用爬虫从顶层将页面中的类似链接迭代爬下来，然后将分类层次提取出来。

，格式化成起点-＞终点形式的有向边，例如Communications-＞Email的形式，存储到本地数据库B中。在抽取时就能确定上层节点和下层节点，将上册节点作为起点，下层节点作为终点，形成有向边。

步骤105.2、对已经初步构建出来的分类层次中的每一条有向边进行检查，如果此边对应的两个顶点在数据库B中出现过，并且两个点由若干条边连接起来路径的方向与初步的分类层次中的路径方向相同，那么，继续检查上述连接起来的路径上的其他点是否在初步分类层次中出现过，如果出现过，则将出现的所述其他点与所述两个顶点形成所有的路径都添加到初步的标签层次结构中。例如：假设此边为A-＞D，在数据库B中有A，D连个点，并且有A-＞B-＞C-＞D将A，D连接起来，其中B在初步的分类层次中出现过，而C没有，那么将A-＞B，B-＞D添加到初步的分类层次中。

如果两个点由若干条边连接起来路径的方向与初步的分类层次中的路径方向不同，则将此边从初步的标签层次中删除。如果此边对应的两个顶点中的至少一个顶点在数据库B中没有出现，则不做任何处理并保留在当前初步标签层次中。

步骤106、定期对各大开源社区的项目信息检查更新信息，如果项目标签有更新，则将页面爬取、抽取，更新到本地数据库A中，执行步骤102及后续步骤，如果没有更新，则睡眠，等待下一次检查。

该方法针对互联网上开源软件信息进行自动化的获取，简化了繁琐重复的手工获取过程，以自动化更新分类层次，并充分利用已有的分类层次优化结果。

如图3所示，本发明中对初步的分类层次进行优化的流程图，具体执行以下步骤：

步骤201、爬取包含分类层次的开源社区，获取分类层次，格式化成<起点，终点>的格式后存储到本地数据库B中；

步骤202、循环遍历本发明初步构建的分类层次中的每一条边；

步骤203、检查此边是否出现本地数据库B中，如果出现了，执行步骤204；否则，保留此边，然后进入下一次循环；

步骤204、检查此边的方向是否与本地数据库B中的方向一致，如果一致，则将路径上出现的且在本地数据库A中出现的标签对应的路径添加到初步的软件标签层次中，否则，将此边从初步的软件标签层次中删除；

步骤205循环完毕后，结束优化过程。

通过本发明方案的处理，可以根据开源软件的标签属性，自动构建标签层次，并利用该层次对开源社区中大规模开源资源进行层次化组织，从而提高开源软件定位准确性和效率。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。