考虑开发者兴趣迁移的开源项目推荐方法
2021-03-21赵佳斌赵海燕陈庆奎
赵佳斌，赵海燕，曹 健，陈庆奎
1(上海理工大学 光电信息与计算机工程学院 上海市现代光学系统重点实验室光学仪器与系统教育部工程研究中心，上海 200093) 2(上海交通大学 计算机科学与技术系，上海 200030)
1 引 言
开源软件已经成为软件开发与应用中的重要模式.随着开源项目托管系统如GitHub等的发展和普及，使得开源项目的数量大幅增加，开源社区也随之受益.在开源项目托管系统中，开发者可以对感兴趣的项目关注、分叉[1]，在完成了一个功能的开发或者漏洞的修复后可进行提交.开源社区通过分叉和pull-request将项目的修改与整合功能分开，这样的模式吸引了大量的开发者，也便于他们参与贡献[2，3].开发者也可以创建自己的公共仓库，吸引其他的开发者参与贡献.因此，开发者的积极参与造就了许多繁荣的开源社区.
开发者参与开源项目有着不同的需求和目的，例如专业的软件开发人员会寻找新的编程挑战或者是商业机会，而初学者会利用社区中的优质资源来学习新的技能、提高能力等[4].为了寻找适合自己并有兴趣的项目，开发者需要花费时间在大量的项目中进行寻找和决策.为了给这些开发者提供帮助，开源项目推荐系统，它能帮助开发人员有效地发现那些潜在的、他们感兴趣的开源项目.近年来，不少研究者提出了针对开源项目的推荐方法，如基于协同过滤的方法[6].然而，区别于传统的电子商务推荐系统，开发者通常不会对大量的开源项目贡献，这就使得开发者-项目的关联矩阵较为稀疏.因此，研究者提出了根据开发者的行为对开发者的兴趣进行建模的方法[7，8]，考虑项目的编程语言、主题等对开发者兴趣建模的方法[9，10]等.这些方法的核心是基于开发者的历史项目来对开发者进行兴趣建模.
然而，开发者在开源社区中的兴趣是发生变化的.例如，出于能力拓展的需要，开发者可能会在小规模的开源项目中得到锻炼后，切换到更大规模的项目.又如，新的编程语言出现后，开发者可能会进入该语言的开源项目.目前提出的方法通过对一个开发者的历史项目进行分析难以反映其兴趣迁移.
本文提出了一种混合方法来揭示开发者群体中存在的兴趣迁移，首先对开源项目采用概率主题模型的方法进行主题建模，其次对其中存在的主题顺序模式进行挖掘从而形成开发者群体的兴趣迁移模式.在此基础上，可以根据开发者的历史项目信息预测其感兴趣的项目，然后结合开发者的社交关系及项目流行度这两项特征对候选池中的项目做排序进而实现最相关的前N个开源项目的推荐.
2 相关工作
推荐系统已经存在了很长一段时间了，软件工程中的推荐系统近年来也逐渐得到了重视，为开发者推荐开源项目也引起了研究者的兴趣.
协同过滤是推荐系统的重要算法之一，它基于如下假设：如果两个用户执行相似的操作，那么他们也更有可能以相同的方式执行其他操作.文献[5]就采用了协同过滤的推荐思想，他们根据开发者行为构建了用户行为矩阵，如果开发者参与过该项目则评分为1，否则为0.然后，基于项目协同过滤方法进行TopN推荐.由于该矩阵的高度稀疏性，其实际性能不高.
为了揭示什么类型的行为数据适合用于项目推荐，文献[6]中分析了在GitHub开源社区中开发者的多种不同行为，这些行为主要包括了分叉、关注、问题评论、推拉请求、成员等.在经定量和定性的实验分析后，他们发现分叉行为适合推荐相关项目.文献[7]进一步研究了开发者的分叉行为.分叉行为主要用于对原项目进行贡献，调查结果显示42%的开发者表示自动化推荐功能能够有效帮助他们选择项目进行分叉操作；分叉的主要原因是开发者想要修改项目发起推拉请求并对项目做贡献；分叉行为不会产生不正当竞争以及版本兼容性问题.他们的工作为开源社区中的项目个性化推荐提供了新的见解.文献[8]采用了一种结合开发人员行为以及项目特征的推荐方法，从项目所包含的描述文件在内的多种不同文件中提取项目特征进而构建项目相似矩阵，通过开发者行为构建开发者项目关联矩阵，同时还考虑了开发者反馈来提高推荐的准确率.
开源项目的内容特征也可以用于揭示开发者的兴趣.文献[9]使用了协同主题回归的方式即结合用户矩阵的传统协同过滤与文本语料库上的概率主题建模.文中提到的方法还为开发者和项目提供了高度可解释的潜在结构.文献[10]考虑了开源项目中出现的编程语言、主题和自述文档，提出了一种混合方法来生成开源项目的推荐，最终的项目相似性为3种不同相似性的线性组合.具体做法是分别构建语言向量、主题向量和项目自述文件向量，同时也为开发者构建在这3个特征上的向量，然后计算得到最终的项目排序.文献[11，12]主要关注项目的描述及源代码来推荐开源项目，忽略了开发者的个性化需求.文献[13]则用到了关联规则挖掘的思想并结合了协同过滤，使用关联规则挖掘共同参与的项目，而协同过滤被用于确定相似的项目.文献[14]提出了一种基于深度学习的项目推荐方法，采用自动编码器来学习开发者与开源项目的向量表示.
不同于上述的工作，本文关注开发者在参与不同开源项目中存在的兴趣迁移模式，提出了一种基于项目主题迁移频繁模式挖掘的推荐算法.
3 基于项目主题迁移频繁模式挖掘的推荐算法
3.1 算法思想
本文提出的算法关注了开发者参与不同开源项目的行为序列，在选择项目的过程中会存在一定的规律和模式，通过主题建模的方式将开发者所参与的开源项目映射到不同的主题，由此开发者参与的项目序列转化为主题序列；对不同的主题序列进行顺序模式挖掘，找到社区中开发者在选择项目时的顺序频繁主题模式；然后用一种打分机制对产生的候选项目进行打分，具体来说就是融合开发者社交关联和项目流行度对项目进行综合打分，最后将得分最高的前N个项目作为最终的推荐结果.方法框架如图1所示.
图1 算法框架Fig.1 Algorithm framework
3.2 项目主题抽取
在该方法中，首先对开源项目的主题进行挖掘，将类似的项目映射到同一个主题.用到的方法是LDA(Latent Dirichlet Allocation)概率主题模型，它是对文本隐含主题的一种建模方法，其主要功能是将文档-词汇矩阵转化成文档-主题分布和主题-词汇分布.3层贝叶斯主题模型通过无监督的学习方法发现文本所含主题，其基本思想就是文档可以表示成一系列主题的混合分布.LDA模型的生成过程如图2所示：1)对每篇文档，从主题分布中提取一个主题；2)从该主题所对应的单词分布中抽取一个单词；3)重复上述操作，直至遍历整篇文档.算法的输入：分词后为文档集，超参数α，η.算法的输出为：1)文档中每个词被分配的主题编号；2)文档的概率概率主题分布；3)每个主题下词的概率分布；4)每个主题下概率从高到低排序的特征词.
图2 LDA概率主题生成模型Fig.2 LDA probabilistic topic generation model
图2中α，η为分布的超参数，θd表示对于任意文档d的主题分布，βk对任意主题k的词分布，文档主题的先验分布和主题中词的先验分布均为Dirichlet分布.Zd，n表示对文档d中的第n个词在θd下得到的主题编号，wd，n表示在Zd，n主题编号下词的概率分布.其中的核心公式如公式(1)所示，公式中以主题t作为中间层，通过当前的θd和βk给出了文档d中出现单词w的概率，用θd计算得到p(t|d)，用βk计算得到p(w|t).
p(w|d)=p(w|t)*p(t|d)
(1)
为了抽取开源项目的主题，对融合了开源项目描述、标签和开发语言的文本文档做基于LDA的概率主题建模，从而将项目对应的文本转化成了若干主题的分布.首先对文本做预处理，包括分词、去除标点、去停用词、词干还原等；其次，将经过预处理的文本用TF-IDF做文本向量化，然后进行LDA主题建模，输出项目对应的概率主题分布.
LDA是一个概率主题模型，为了更多地保留项目的特征信息，本文在选出了每个项目最贴切的一个主题的基础上，设置了一个阈值.具体做法是，将项目所对应的多个主题分布按概率大小做排序保留大于该阈值的主题.如此，一个项目可能只对应一个主题，也可能对应多个主题.
3.3 主题顺序频繁模式挖掘
数据集中频繁出现的项集、序列或子结构称之为频繁模式，经常被用于购物篮分析、网页日志分析等.本文采用顺序频繁模式挖掘的方法对项目的主题的序列模式进行挖掘.开发者的偏好变化通过参与项目的行为序列来凸显，通过对开发者参与项目序列的主题的挖掘可以预计开发者在参与了某一主题的项目后会接着参与哪个主题对应的项目.
对开源项目完成主题建模后，开发者原本参与项目的行为序列由
图3 GSP算法流程Fig.3 GSP algorithm flow
挖掘.顺序频繁模式挖掘的主要任务是找到数据库中存在的所有顺序模式，即在序列集合中出现频率超过最小支持度的子序列.常用到的算法是GSP(Generalized Sequential Pattern mining algorithm)[16]算法，该算法增加了扫描过程中的条件约束包括时间、滑动窗口和分类层次，是一种基于优先级原则的算法，其中用来存储的数据结构为哈希树.算法的输入是主题序列数据、最小支持度阈值，输出是顺序频繁模式.
GSP算法的主要流程如图3所示.
但是，本文需要挖掘的序列是由数量不等的主题构成的集合序列.因此，结合本文所涉及问题的特点，对GSP算法进行修改.在其基础上本文提出了GSP-SS(GSP for Set Sequences)算法.在主题建模的过程中，一个项目对应了多个主题，例如项目i，在经阈值筛选后它的第1主题为topic52，第2主题为topic16，第3主题为topic44，采用GSP-SS算法在得到顺序频繁模式的同时也会得到该频繁模式所对应的重要度.
GSP-SS算法伪代码如下：
输入：项目所对应的主题序列数据，最小支持度阈值；
输出：主题顺序模式Li及其重要度.
1.C1←init-pass(S)；//遍历输入数据并产生1频繁模式
2.topicSupportArray=[repo1：[0，0，…，0k1]，repo2：[0，0， …，0k2]， … ，repon：[0，0，…，0kn].]
//空数组topicSupportArray保存重要度
3.L1←{<{l}>|l∈C1，Count(l)/n≥min_sup}；
//最小支持度阈值的判断
4.for(i=2，Li-1≠Φ，i++)do
5.Ci←generate-candidate-SPM(Ci-1)
//产生k-频繁序列模式
6.foreachs∈Sdo
7.foreachc∈Cido
8.ifcis contained insthen
9. Count(c)++；//c的支持度
10.fortopicinc：
11.topicSupportArray[s.index][c′sindexins]++ //每出现一次重要度计数加1
12.endfor
13.endfor
14.Li={c∈Ci|Count(c)≥min_sup}；
15.endfor
16. sort(topicSupportArray[data sequence index：])
//交换key，value；key填回topic
函数generate-candidate-SPM(Ci-1)伪代码如下：
To generateCk//产生大小为k的候选项
1. Join step.
si′=si-1st //-1st，表示去掉第一个元素项
sj′=sj-Last //-Last，表示去掉最后一个元素项
ifsi′==sj′do
s←Joinsi′ andsj′ // 做连接操作
2. Prune step
ifany subsequence ofck-1is not infrequent
deleteck-1//做剪枝操作
S为主题序列数据，Ck为候选k-频繁序列模式，Lk为候选k-频繁序列模式.
GSP-SS算法说明：对产生的主题序列S数据库进行扫描，得到长为1-主题顺序模式L1并做最小支持度判断将其作为初始种子集；对L1做连接操作并判断是否满足最小支持度，产生2-主题顺序模式；用L2做连接操作产生3-主题顺序模式，其中会有剪枝操作和最小支持度判断；然后用3-顺序主题模式L3挖掘直到不产生候选项.在挖掘的过程中设置了数组topicSupportArray来存放所挖掘出主题模式的重要度，最后在得到主题顺序模式的同时附带将其重要度一并输出.其中完成连接操作和剪切操作的generate-candiate-SPM是该算法的核心.连接阶段：对于两个顺序模式Si和Sj，如果删除Si的第一个项目得到序列与删掉Sj的最后一个项目所得序列相同.那么对Si和Sj做连接操作.剪切阶段：对于任意一个序列模式，如若它的子序列不是序列模式，那么这个序列模式就不可能成为序列模式，将其剪切即删除掉.
3.4 开发者社交特征及项目流行度建模
3.4.1 开发者社交关联
不同于企业有组织的软件开发团队，开源软件团队具有多样性和流动性，通常以自组织[17]的方式参与到软件项目开发中.Github开源社区提供了包括@、关注和评论等多种方式方便开发人员沟通和交流.
通过使用关注功能，开发者能关注自己感兴趣的开发者，关注开发者能看到他们以往及近期的实践工作，了解他们在相关领域的贡献以及研究.通过评论功能，开发者们能够在不同问题下展开讨论进而解决问题.对自组织网络的研究表明，相较于新的合作，人们更喜欢重复合作，因为他们认为这样的合作往往更有凝聚性.文献[18]研究了社会化因素对GitHub这个新兴生态系统的影响，包括开发团队的形成已经开发人员的迁移等.其中社交关系的强度会影响开发者的选择，开发人员会优先加入存在社交联系的项目.有社交关联的开发者们往往具有类似的兴趣点，同时基于先前的互动或合作，开发人员对彼此的技能和社交习惯都有更多地了解.因此，本文将开发者的社交关系作为开源项目推荐过程中考虑的因素之一.
GitHub中所提供的项目issue功能是一种轻量级的协作系统，在issue comment下可以进行内容丰富的交流，主要针对问题解决、项目存在的Bug和下一项功能的增加等展开讨论.GitHub定义了pull-request为一种通知机制即你修改了他人的代码希望原作者能合并你的修改，用pull-request来通知作者.它是一种软件开发合作方式，将不同功能的代码通过这一流程纳入到项目主干.通过其自带的评论功能对所提交的修改进行讨论、测试并决定是否将其合并.根据社区中的参与同一个issue问题评论、同一个pull-request评论来构建每位开发者的社交关系.对于开发者u，其候选项目池中的项目i的社交关系计算如公式(2)所示：
Social(u，i)=n(uinteract)
(2)
其中n(uinteract)表示在项目i中与之有过互动的开发者数量.
3.4.2 项目流行度
在开源社区中，也存在“马太效应”，相比于那些冷门的项目，活跃的、受关注度高的开源项目更容易吸引开发者.在每个GitHub项目页面的右上方有watch、star、fork这3个不同的按钮.其中的star更像是“点赞”，因此本文选择了关注和分叉的数量来评价一个项目的流行与否.
Watch(关注)的数量，对于他人的项目默认都是Not watching的状态，当开发者对该项目感兴趣时就能选择关注该项目的所有动态，例如该项目有开发者提交pull request、提出了issue等，便能从系统推送中了解该项目发生的一切动态变化.所以项目拥有的关注者数量能反应其受用户关注程度.
Fork(分叉)的数量，当你有了对一个项目做贡献的想法包括增加新功能、漏洞修复或者在该项目的基础上开发一个自己的版本，可以点击fork按钮得到一份原项目的副本.
结合关注和分叉这两者的数量来计算项目的流行度，对两者者的数量归一化后进行求和.对于项目i的流行度，计算公式如公式(3)所示：
pop(i)=nor(n(iwatch))+nor(n(ifork))
(3)
其中n(iwatch)表示项目i关注者的数量，n(ifork)表示项目i分叉者的数量，nor()表示归一化计算函数.
3.5 推荐方法
通过概率主题建模的方法将开发者参与的开源项目映射成主题序列，将训练集中的开发者参与主题序列事务集记作C={C1，C2，C3，…，Cu}其中u为开发者人数，Cu表示开发者参与项目经过主题泛化后得到的主题序列.将主题顺序模式记作P，min_supp是最小支持度阈值，当模式P的支持度大于min_supp则P为顺序主题模式.采用GSP-SS算法对顺序主题序列模式做挖掘，将开发者参与的主题序列事物集作为GSP-SS算法的输入，设置min_supp，运行GSP-SS程序输出主题频繁顺序模式项，记作P={P1，P2，P3，…，Pj}其中j为产生的模式数量.
采用一个多叉树的数据结构来存储主题模式与模式库中的模式项的对应关系.将模式的候选集记作H={HP1，HP2，HP3， …，HPj}.
对于测试集中的数据，给定开发者参与的历史项目
S(u，ri)=α*nor(pop(i))+(1-α)*nor(social(u，i))
(4)
其中pop(i)表示项目的流行度，social(u，i)表示社交关联度，α表示权重参数，nor()表示归一化函数.
算法描述如下：
输入：开发者参与的历史项目集合X，顺序模式P；
输出：Top-N推荐项目列表.
1.使用LDA主题模型将X转化为C={C1，C2，C3，…，Cu}；
2.forj=1 tojdo
3.foreachCu∈Cdo
4.ifPjinCudo
5.Pj在Cu中的末尾位置记作l，从X中的第l+1个位置得到ri
6.endif
7.endfor
8.H←H∪HPj
9.endfor
10.用公式(4)为H中的项目打分并做降序排序
11.returnTop-N 推荐项目列表
4 实验与讨论
4.1 数据集
本文使用的数据集是从GHTorrent[15]中转储得到的，GHTorrent项目提供了GitHub 的API数据的镜像，可以离线查询.它旨在用于与软件存储仓库有关的研究与发现.本文选取了2016-2018年间的数据，为了让实验数据更具有代表性，筛选出的开发者和开源项目满足如下条件：1)开发者至少参与了5个不同的开源项目；2)与其他开发者有过互动即在同一个问题或推拉请求下有过讨论；3)开源项目为原始项目即不是从其他项目分叉而来；4)开源项目至少有5名开发者参与过.开发者参与项目数据格式如：开发者编号-项目编号-时间戳.开源项目信息包含：项目编号、项目开发语言、项目描述和项目标签.经筛选后得到了开发者数量18399个，开源项目数量23076个.根据开发者参与项目的时间戳的先后顺序来创建开发者参与项目序列数据，根据项目开发语言、项目描述和项目标签来创建项目文档数据用作主题建模.
关于训练集和测试集的划分.本文将开发者近一年参与的项目作为测试集用作实验的预测数据，剩余的其他数据用作实验模型的训练数据.
4.2 评价指标采用召回率
考虑到本文的推荐场景为Top-N的前N个项目的推荐即向开发者提供一个推荐的列表让其进行选择，故采用了召回率Recall来评价所提算法的推荐效果.召回率表示用户感兴趣的项目被推荐系统成功推荐的概率，计算公式如公式(5)所示：
(5)
其中R(u)为根据开发者u在训练集上的表现向其推荐的项目集，T(u)为开发者u在测试集上参与过的项目集.
4.3 基准推荐算法
本文选择了3种常见的推荐算法作为对比方法.
1)基于项目流行度的推荐方法，该方法围绕项目“热度”展开，将对用户有着强吸引力的项目推荐给其他开发者.采用这一方法做推荐的主要工作就是计算每个项目的流行度，推荐列表为开发者未曾参与过的流行的Top-N个开源项目；
2)基于用户的协同过滤推荐[19]，这个算法通常分为两个步骤，首先找到与目标开发者相似的若干开发者，然后将这个集合中开发者参与过的但目标开发者未曾参与的项目作为推荐列表.设置最相似的开发者数量K=20，相似度计算采用余弦相似性；
3)基于内容的推荐算法，根据开发者做过的项目描述、开发语言及标签来推荐类似的开源项目，采用文本处理方法：词频-逆文档频率(TF-IDF)将文本向量化随后计算项目之间的余弦相似度，推荐列为与其最相似的Top-N个项目.
本文所提推荐的推荐算法，将主题个数K设置为90，主题模式挖掘中的最小支持度min_supp设置为5.
4.4 实验结果分析
不同推荐方法下实验结果如表1所示，采用的评价方法为召回率.
表1 实验结果表Table 1 Experiment resultTable
开发者社交特征及项目流行度建模中的公式(4)，不同α的取值对推荐结果的影响如图4所示.实验中本文将α值设置为0.3.
图4 α的取值对推荐结果的影响Fig.4 Value of α versus the recommended result
实验结果表明，当推荐项目数量N值增大的时候，四种不同推荐方法的召回率均逐渐增大，说明在推荐列表中开发者感兴趣的项目数量增多了.本文提出的基于主题模式挖掘的推荐方法在召回率上优于其余3种对比方法，对项目的主题模式挖掘考虑到了开源项目的内容特征，引入的评分机制兼顾了开发者的社交情况以及项目自身的流行度特点，进而提高了推荐效果.
5 总结与展望
近年来，分布式软件开发与社交化编程得到了人们的广泛认可，GitHub开源社区更是引领了新的开源文化.GitHub“去中心化”的开源模式，不断彰显和强调作为个体的开发者的作用，鼓励他们对他人的项目做修复和改进.开源社区的壮大也使得开源项目的数量大幅增加，开源项目推荐系统能帮助开发者找到他们有意愿参与的项目.
本文提出了一种基于项目主题模式挖掘的推荐方法，关注了开发者在项目迁移过程中存在的规律，用开源项目的内容特征为项目进行主题建模，开发者参与项目的项目序列转化为主题序列；随后对其中存在的主题顺序模式进行挖掘；接着融合开发者的社交关联和项目自身的流行度这两个特点实现了Top-N个开源项目推荐；最后在实验数据集上与传统推荐方法进行对比，推荐效果得到了有效的提升.未来的工作可以关注对项目的主题建模和开发者在项目迁移过程中是选择下一个项目的其他因素，考虑更多的文本内容比如代码所蕴含的注释、函数名等，有助于提高项目与主题的契合程度.
