专利排名算法——运用引用次数与引文网络计算美国专利的研究
顾立平
国立台湾大学图书资讯系 台北 10617
摘要

在网页排名和论文排名基础上,采用引用频次标准和引文网络计算排名数值,建立专利排名算法。分析美国专利和商标局的数据库中的数字图书馆相关专利,研究结果显示专利排名算法能够区分相同引用次数的专利排名。该研究是网页排名算法的一种新型应用。

关键词: 专利检索; 专利分析; 专利计量; 专利评估; 专利表现; 专利质量
中图分类号:G312
PatentRank Algorithm——A Study of Using Cited Time and Citation Network to Calculate U.S. Patents
Ku Liping
Department of Library and Information Science, National Taiwan University, Taipei 10617, China
Abstract

Based on the PageRank and ArticleRank, the paper uses the times cited criterion and citation network to calculate the rank scores,thus establishes the PatentRank Algorithm. Then it analyzes the relevant digital library patents of the USPTO patent database and the results show that the PatentRank Algorithm can differentiate patents which of the same number of citations. The originality is a novel application of the PageRank Algorithm.

Keyword: Patent retrieval; Patent analysis Patentmetrics; Patent evaluation; Patent performance; Patent quality
1 引 言

在SCI和SSCI的科学计量学研究领域中,有许多正在发展中的研究前沿,其中,利用网页排名算法来进行论文质量计算的算法研究与政策应用目前主要有两个方面:

(1)对作者、机构、国别的影响力评估,例如:基于引文的评价模型[ 1]、对档案学报(Journal of Documentation)最有影响力的论文排名[ 2],以及对单一作者的科学影响力评估[ 3]等;

(2)观测学者的科学合作网络,例如:领域内的作者合作关系[ 4]、以引用频次和作者合作改良的网页算法在科学论文中的应用[ 5]、对图书情报学重要作者的计量研究[ 6],以及对信息检索领域内的引文关系研究[ 7]等。

这两种分流事实上是一体两面,即:采用相同的网页排名原理来进行论文排名研究,它可以作为评估科研经费投入效果的一种方法,也可以是一种了解某些领域的部分学者的社会网络现象的解读方式。

本文并不研究网页排名、论文排名或者论文排名的用处,而是研究另一种适合于专利排名的算法。由于论文和专利都是一种有明确目的的信息交流内容,因此,开发专利排名算法,有助于促进信息检索系统、产业竞争情报、科技资源投入产出评估、国家科技政策制定等诸多方面的应用。本文的研究目的是在已有的网页排名算法和论文排名算法的基础上,开发专利排名算法,以期未来能够成为决策支持系统(Decison Support System, DSS)的一项核心技术。

2 需求及技术思路

(1)国内外的应用现状

作为10种最普遍的数据挖掘技术之一[ 8],网页排名或称佩奇算法,其核心思想是:反向链接的排名总和越高,其网页排名越靠前(A page has high rank if the sum of the ranks of its backlinks is high)[ 9]。搜索引擎Google设计之初,参考了情报学中文献计量的引文网络的概念,并且针对以图书馆学的分面分类法为信息组织的第一代Yahoo搜索引擎进行改良(紧接着两者又相互借鉴和融合)[ 10, 11]。之后,许多研究又针对网页排名的不足之处进行改良[ 12],例如,以用户行为实现个性化网页排名为算法改进[ 13, 14]等。

尽管网页排名来自引文网络[ 15]的概念,并通过马科夫链予以矩阵方程化[ 16];但是反过来网页排名又对于引文网络具有影响[ 17],并且这种影响遍及文献计量、信息计量、科学计量与网络计量,相关定义参见文献[18]和[19],例如用来评量期刊与作者排名的链接分析排名(Link Analysis Rank)[ 20]、文章排名(PaperRank)[ 21]、个人网页排名[ 22]等。

(2)工作中的应用需求

专利计量是运用文献计量、信息计量与科学计量的研究方法与一些数学运算方式,进行专利信息的分析与研究[ 23, 24]。专利计量与其他计量方法的最大不同在于专利数据的格式和规范与一般论文和网页不同,常使用基本统计、引用分析和连接指标等三类计算方式[ 24]。所以,利用网页排名的公式算法和论文排名的研究取向,可以丰富专利计量的分析技术和研究内容。本项研究不仅可以在工业工程的专利评估中应用,也为国家科技政策的决策提供了一种专利分析的基本工具。

(3)技术思路

运用引用频次标准和引文网络计算同一关键词下的美国专利的先后排名顺序。对美国专利和商标局(United States Patent and Trademark Office)的USPTO数据库,以ABST/“digital library”进行检索,共得46个相关专利。数据源(http://patft.uspto.gov/netahtml/PTO/search-bool.html)是支持Open Access的机构网址,采集日期为2011年3月10日(数据库的更新日期为2011-03-08),后续研究人员可重复验证。

(4)技术实现方法

设计一套专利排名算法,并与被引频次进行比较,可区分出专利排名算法的效果。以被引频次(Times Cited,TC)为控制组,以专利排名(PatentRank,PR)为对照组,进行实验研究。

3 具体解决方案
3.1 技术架构与实现方案

按照计算公式,针对实验对象,进行逐步计算分析。步骤如下:

(1)数据收集:下载实验所需的USPTO的专利数据。

(2)数据清理:根据USPTO专利元数据,用Ruby对TXT文档进行格式整理。

(3)数据分析:根据PatentRank公式,用Ruby编写程序进行分析。

(4)数据分析:拆解PatentRank公式,用Calc产生数值人为计算和分析。

(5)资料比对:对比两种分析结果,确定计算无误,汇编表格。

(6)排名产出:针对表格内容,验证计算公式。

(7)验证公式:根据TC组和PR组的结果,进行讨论。

3.2 关键的技术性问题与解决

在PageRank和ArticleRank的基础上,设计PatentRank 算法如下:

PatentRank(P)=(1-d)+d× ×

其中,PatentRank(P)表示专利P的排名数值;d表示随机几率,以PageRank的经验数据,数值设为0.85;c表示本专利族群中的引用次数; 表示c的平均值;Pi表示引用P的n个专利中的其中一个专利;c(Pi)表示在Pi引文网络中的参考文献数量。

4 应用效果
4.1 实现环境与应用测试

应用PageRank的PatentRank在实际操作时,需要进行迭代(Iterate)才能得到最终Rank结果。处理方式有两种:用Open Office的Calc试算表(类似Microsoft Excel)计算,人为操作多次后,进行人工计算;用计算机编程,在多次调适程序确定无误后,可以重复使用。因此,采用Ruby语言,对Patent Rank进行编写,并与人工计算进行对照。

在数据清理的阶段,其USPTO专利可被汇整以方便计算,如表1所示。可知,在USPTO数据库中,文摘中有Digital Library的专利,其被引频次有高有低,其中又有若干被引频次相同的专利。

表1 在USPTO的Digital Library专利
4.2 实验结果与应用效果分析

根据PatentRank公式,进行Ruby迭代15次后,得到计算结果,对比引用次数(Times Cited)的排名和PatentRank的排名,如表2所示:

表2 比较Times Cited和PatentRank的排名情况

表2可知,由于Times Cited和PatentRank数值不同,若干专利号所代表的专利在被引排名和PR排名中也有所不同。

(1)专利号5835667和6611840的TC排名和PR排名皆为第一和第二;专利号6243853、7441192、7513424、7613336、7613704、7716589、7895243和7895288皆为第39至46的末尾位。所以,在极大极小值上的TC和PR并没有明显不同。如同数学证明PageRank迭代多次能够有效收敛[ 25, 26, 27],在PatentRank上也能有效合理地收敛,并且赋予零项数值合理的随机参数。

(2)专利号6449627、6260040、5940594、6338044和6035303同属一个区间(第3至第7顺位),但是根据TC和PR它们的排名顺序各有不同。所以在标准差前四分之一中的排名对象相同,而考虑引文网络后的排名顺序则优化了单纯以被引频次来计算的排名。

(3)专利号6005969和7340481、专利号5966454和6986102、专利号6021410和6748382、专利号6256636和7346844,以及专利号7356766、7401097、7613993等,在TC计算之中无法区分排名,而在PR计算中,可在被引频次相同的情况下,根据引文网络的计算而区分出排名顺序。

5 结 语

(1)研究成果

本研究在PageRank和ArticleRank的基础上发展PatentRank技术,这项初探性研究仍有许多发展空间,特别是从专利用户行为来进行改良。在理论方面,理解用户行为是未来发展该技术的关键;在实践方面,本项研究成果可以直接转化为工业工程应用,利用开源软件进行大规模专利数据运算,为国家科技政策的决策提供支持。

(2)研究贡献

PageRank网页排名技术,在1998年发布后的10余年间,Google对其进行了算法改进,而许多研究也环绕在这项技术上[ 28]。其中,最近三年开始有学者把PageRank改为一种ArticleRank算法,用来计算期刊文献的被引和排名,同时比较个人、机构和各国的科技竞争力排名。但是,目前鲜少有人将PageRank改为一种PatentRank算法来予以进行文献计量、信息计量、科学计量乃至专利计量的应用。

直接将PageRank算法套用在其他文献载体的排名计算上并不妥当。由于参考文献较少的文本会给予其他引用文本较大的影响数值,因此,在ArticleRank的建模过程中,曾经使用过开平方、指数、最大最小值差等方式处理权重问题[ 2]。与ArticleRank相同,经过实验,目前PatentRank也需要运用引文平均值作为计算公式的参数之一,然而,这并不代表该参数是唯一一种可以去除规模谬误的规范化(Normalization)的合理参数。

(3)未来研究

除了需要考虑网页、论文和专利本身的数据结构不同,尚需深入研究“专利信息行为”而从专利排名的用途来进行研究[ 29]。比如,若以用户文档(User Profile)建立用户兴趣层次(UIH),则可发展个性化排名方法[ 30]。网页搜索引擎必需考量网址和网页成长数、网页内容、链接结构和用户搜索需求等因素[ 31],而如果用户意向被更好地运用,则能够一般化文本片段抽取(Text Snippet Extraction),比方使用统计语言模型捕获文档和用户意向的共性[ 32]。采用类似网页排名(PageRank)的实例算法(InstanceRank)能减少实例集的大小,从学习库中选择最有代表性的实例[ 33]。伴随网页排名和论文排名的技术进步,可预见专利排名的突破性发展;如何将在信息系统、大学评量或者科技政策等的各种应用研究开发成为一套有用工具,以及如何规范化地优化这套算法,仍然出自于用户行为。

The authors have declared that no competing interests exist.

作者已声明无竞争性利益关系。

参考文献
[1] Corso G M D, Romani F, Binii D A. Versatile Weighting Strategies for a Citation-based Research Evaluation Model[ED/OL]. [2010-10-27]. http://www.dmi.unipg.it/lmc/galn/data/talk/delcorso.pdf. [本文引用:1]
[2] Li J, Willett P. ArticleRank: A PageRank-based Alternative to Numbers of Citations for Analyzing Citation Networks[J]. Aslib Proceedings: New Information Perspectives, 2009, 61(6): 605-618. [本文引用:2] [JCR: 0.432]
[3] Yan E, Ding Y. Discovering Author Impact: A PageRank Perspective[J]. Information Processing & Management, 2011, 47(1): 125-134. [本文引用:1] [JCR: 0.488]
[4] Liu X, Bollen J, Nelson M L, et al. Co-authorship Networks in the Digital Library Research Community[J]. Information Processing & Management, 2005, 41(6): 1462-1480. [本文引用:1] [JCR: 0.488]
[5] Fiala D, Rousselot F, Jezek K. PageRank for Bibliographic Networks[J]. Scientometrics, 2008, 76(1): 135-158. [本文引用:1] [JCR: 2.133]
[6] Yan E, Ding Y. Applying Centrality Measures to Impact Analysis: A Co-authorship Network Analysis[J]. Journal of the American Society for Information Science and Technology, 2009, 60(10): 2107-2118. [本文引用:1] [JCR: 2.005]
[7] Ding Y, Yan E, Frazho A, et al. PageRank for Ranking Authors in Co-citation Networks[J]. Journal of the American Society for Information Science and Technology, 2009, 60(11): 2229-2243. [本文引用:1] [JCR: 2.005]
[8] Wu X, Kumar V, Quinlan J R, et al. Top 10 Algorithms in Data Mining[J]. Knowledge and Information System, 2008, 14(1): 1-37. [本文引用:1] [JCR: 2.225]
[9] Page L, Brin S, Motwani R, et al. The PageRank Citation Ranking: Bringing Order to the Web [ED/OL]. [2010-10-27]. http://ilpubs.stanford.edu:8090/422/. [本文引用:1]
[10] Brin S, Page L. The Anatomy of a Large-scale Hypertextual Web Search Engine[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117. [本文引用:1]
[11] Uddin M N, Janecek P. A Framework for Integrating Faceted Classification Within a Content Management System[ED/OL]. [2011-04-07] . http://kst.buu.ac.th/proceedings/JCSSE2005/pdf/a-702.pdf. [本文引用:1]
[12] Berlt K, Moura E S, Carvalho A, et al. Modeling the Web as a Hypergraph to Compute Page Reputation[J]. Information Systems, 2010, 35(5): 530-543. [本文引用:1] [JCR: 1.768]
[13] Eirinaki M, Vazirgiannis M. Web Site Personalization Based on Link Analysis and Navigational Patterns[J]. ACM Transactions on Internet Technology, 2007, 7(4): 1-27. [本文引用:1] [JCR: 0.792]
[14] Witten I H. Searching … in a Web[J]. Journal of Universal Computer Science, 2008, 14(10): 1739-1762. [本文引用:1]
[15] Pinskis G, Narin F. Citation Influence for Journal Aggregates of Scientific Publications: Theory, with Application to the Literature of Physics[J]. Information Processing and Management, 1976, 12(5): 297-312. [本文引用:1] [JCR: 0.817]
[16] Boldi R, Santini M, Vigna S. PageRank: Functional Dependencies[J/OL]. ACM Transactions on Information Systems. [2010-09-22]. http: //vigna. dsi. unimi. it/ftp/papers/PageRankFunctional. pdf. [本文引用:1]
[17] Ma N, Guan J, Zhao Y. Bringing PageRank to the Citation Analysis[J]. Information Processing and Management, 2008, 44(2): 800-810. [本文引用:1] [JCR: 0.817]
[18] Tague-Sutcliffe J. An Introduction to Informetrics[J]. Information Processing and Management, 1992, 28(1): 1-3. [本文引用:1] [JCR: 0.817]
[19] Björneborn L, Ingwersen P. Perspectives of Webometrics[J]. Scientometrics, 2001, 50(1): 78-79. [本文引用:1] [JCR: 2.133]
[20] Sidiropoulos A, Manolopoulos Y. Generalized Comparison of Graph-based Ranking Algorithms for Publications and Authors[J]. Journal of Systems and Software, 2006, 79(12): 1679-1700. [本文引用:1] [JCR: 1.135]
[21] Krapivin M, Marchese M, Casati F. Exploring and Understand ing Citation-based Scientific Metrics [EB/OL]. [2010-09-22]. http://disi.unitn.it/~krapivin/acs-2009-metrics.pdf. [本文引用:1]
[22] Yang W S, Jan Y S. Increasing the Authoritativeness of Web Recommendations Using PageRank-based Approaches[J]. Online Information Review, 2009, 33(2): 362-375. [本文引用:1] [JCR: 0.939]
[23] 罗思嘉. 专利计量分析与应用[J]. 国立成功大学图书馆馆刊, 2007(16): 43-54. [本文引用:1]
[24] 陈达仁, 黄慕萱. 专利资讯-检索、分析与策略[M]. 台北: 华泰文化, 2009. [本文引用:2]
[25] Lin Y, Shi X, Wei Y. On Computing PageRank via Lumping the Google Matrix[J]. Journal of Computational and Applied Mathematics, 2009, 224(2): 702-708. [本文引用:1] [JCR: 0.989]
[26] Gleich D F, Gray A P, Chen G, et al. An Inner-outer Iteration for Computing Pagerank[J]. Society for Industrial and Applied Mathematics, 2010, 32(1): 349-371. [本文引用:1] [JCR: 5.952]
[27] Andersson F K, Silvestrov S D. The Mathematics of Internet Search Engines[J]. Acta Applicand ae Mathematicae, 2008, 104(2): 211-242. [本文引用:1] [JCR: 0.985]
[28] Wills R S, Ipsen I C F. Ordinal Ranking for Google’s PageRank[J]. Matrix Annual, 2009, 30(4): 1677-1696. [本文引用:1]
[29] Liu Y, Liu T Y, Gao B, et al. A Framework to Compute Page Importance Based on User Behaviors[J]. Information Retrieval, 2010, 13(1): 22-45. [本文引用:1] [JCR: 0.63]
[30] Kim H, Chan P. Personalized Search Results with User Interest Hierarchies Learnt from Bookmarks[J]. Advances in Web Mining and Web Usage Analysis, 2006, 4198: 158-176. [本文引用:1]
[31] Ke Y, Deng L, Ng W, et al. Web Dynamics and Their Ramifications for the Development of Web Search Engines[J]. Computer Networks, 2006, 50(10): 1430-1447. [本文引用:1] [JCR: 1.231]
[32] Li Q, Chen Y P. Person樢ed Text Snippet Extraction Using Statistical Language Models[J]. Pattern Recognition, 2010, 43(1): 378-386. [本文引用:1] [JCR: 2.632]
[33] Vallejo C G, Troyano J A, Ortega F J. InstanceRank: Bringing Order to Datasets[J]. Pattern Recognition Letters, 2010, 31(2): 133-142. [本文引用:1] [JCR: 1.266]