Kenway's Blog

【实战】TPL推荐笔记

发表于 更新于 分类于

目录

TPL部分

推荐部分

当前工作

TPL部分

推荐部分

1.协同过滤算法(CF)

  • 两种思路
    • 基于用户UBCF：以用户为主体，挖掘用户与用户之间的相似性，将与某用户相似的用户购买的物品推荐给该用户
    • 基于物品IBCF：寻找与该用户购买的物品相似的物品来之间推荐
  • 核心步骤：计算相似度，一般用余弦相似度或皮尔逊相似度
  • 针对协同过滤构建的共现矩阵稀疏度较高的缺点，用矩阵分解来解决
    • 通过分解共现矩阵为每一个用户和每一个商品生成一个隐向量
    • 向用户推荐距离近的商品
    • 具体步骤
      • 矩阵分解就是把一个mxn的共现矩阵，用梯度下降分解成一个mxk的用户矩阵和kxn的物品矩阵相乘的形式，
      • 用户隐向量和物品隐向量就分别是对用户矩阵的行向量和物品矩阵的列向量

2.基于主题模型的推荐算法LDA：

  • 针对对象是文本描述
  • 通过LDA计算出两个app描述文本的主题相似度，然后根据主题相似度列出推荐列表

3.关联规则挖掘

1
2
3
4
5
6
7
8
9
10
11
12
13
t1: 牛肉、鸡肉、牛奶

t2: 牛肉、奶酪

t3: 奶酪、靴子

t4: 牛肉、鸡肉、奶酪

t5: 牛肉、鸡肉、衣服、奶酪、牛奶

t6: 鸡肉、衣服、牛奶

t7: 鸡肉、牛奶、衣服
  • 假如有一条规则：牛肉—>鸡肉
    • 则这条规则的支持度就是同时购买牛肉和鸡肉的顾客比例3/7(t1、t4、t5比t1~t7)，表示在所有顾客当中有3/7同时购买牛肉和鸡肉，其反应了同时购买牛肉和鸡肉的顾客在所有顾客当中的覆盖范围
    • 而规则的置信度就是购买牛肉的顾客当中也购买了鸡肉的顾客比例是3/4(t1、t4、t5比t1、t2、t4、t5)，表示在买了牛肉的顾客当中有3/4的人买了鸡肉，其反应了可预测的程度，即顾客买了牛肉的话有多大可能性买鸡肉
  • 支持度很小，则表明它在事务集合中覆盖范围很小，很有可能是偶然发生的；如果置信度很低，则表明很难根据X推出Y
  • 关联规则挖掘则是从事务集合中挖掘出满足支持度和置信度最低阈值要求的所有关联规则，这样的关联规则也称强关联规则

4.带精英策略的非支配排序的遗传算法NSGA-II

  • 假设种群为P，则该算法需要计算P中的每个个体p的两个参数np和Sp，其中np,为种群中支配个体p的个体数，Sp为种群中被个体p支配的个体集合。遍历整个种群，这两个参数的总计算复杂度是O(mN2)。
  • 算法的主要步骤为:
    • (1）找到种群中所有np=0的个体，并保存在当前集合Fl中;
    • (2)对于当前集合F中的每个个体i，其所支配的个体集合为Si，遍历Si中的每个个体l，执行nl=nl-1，如果nl=О则将个体l保存在集合H中;
    • (3)记Fl中得到的个体为第一个非支配层的个体，并以H作为当前集合，重复上述操作，直到整个种群被分级。

5.余弦相似度的计算

当前工作

收集文献

1.确定研究范围和明确研究目标
关于Android开发的第三方库（TPL）和相关的推荐算法

2.确定搜索的关键字

  • Android、app、apk
  • Third party libraries(第三方库)
  • recommendation(推荐系统)

3.执行搜索过程。搜索常用的出版物存储库，包括会议和期刊

  • 相关领域的部分会议期刊：EASE、ASE、ESE、FSE
  • paper来源：主要在ACM Digital Library、IEEE Xplore Digital Library和ScienceDirect进行检索
  • 搜索方式：用步骤二确定的关键词组合成搜索条件，对以上数据全文库进行检索，然后通过手动浏览论文标题进行初步筛选，对于不能通过标题判断是否符合本次研究内容的论文，进一步使用谷歌学术进行搜索阅读其摘要来进行筛选

4.对搜索结果应用排除标准以提高分析精度

  • 在基于关键字的搜索过程中，不可避免地会获得一些相关程度较低的论文。为了缓解这种情况，根据定义的排除标准评估搜索结果。
    • 去除非英文和中文的论文
    • 考虑到使用Andriod搜索会使结果较少，采用去除掉含有ios和windows关键字的论文
    • 去除掉与第三方库无关的论文（例如第三方交易、第三方安卓手机等）
    • 本文研究的工作内容应该是比较完整的，去除掉一些仅描述想法的短文，去掉页数少等于三的文章
    • 去除掉基于同一工作的重复论文

5.在剩余的文件上进行反向滚雪球，以防遗漏

  • 对五次筛选后的结果再以（5）到（1）的顺序进行一次筛选，由于此时的论文数目较少，对于被排除掉的论文可以人工进一步识别

6.合并结果

  • 将得到的论文的引用文献再用过滤规则筛选一遍，以增加论文总数

实际操作过程

  • 第一次筛选
    • 操作内容：检索含有third party libraries 及recommender且不含windows或ios的论文
    • 来源：ACMDigitalLibrary、IEEEXploreDigital Library、ScienceDirect、万方、知网
    • 结果：289篇
  • 第二次筛选
    • 操作内容：手动对论文标题进行翻译，仅下载与本次研究内容相关的论文
    • 来源：第一次筛选出的289篇论文
    • 结果：69篇
  • 第三次筛选
    • 操作内容：使用谷歌学术查看其摘要，保留第三方库推荐系统相关的论文
    • 来源：第二次筛选出的69篇论文
    • 结果：30篇
  • 去重
    • 操作内容：去除来自不同源的同一论文
    • 来源：第三次筛选出的30篇论文
    • 结果：20篇
  • 扩展
    • 操作内容：找出20篇论文的引用文献中未收录的第三方库推荐系统相关的论文
    • 来源：去重后的20篇论文里后附的引用文献
    • 结果：32篇
  • 最终筛选出相关论文32篇，其中完整论述第三方库推荐系统方面的有13篇

文献总结(按年份排序)

对收集到的文献全文阅读，其中得到十篇具有参考研究价值的、质量较高的论文，对其算法模型、优缺点等进行了详细归纳

一、《Embedding App-Library Graph for Neural Third Party Library

Recommendation》(2021，ESEC/FSE)
模型名G-Rec
1.数据来源：MALib
2.第三方库表示方式：图
3.推荐算法：图神经网络GNN
具体步骤：

  • 以app和tpl作为节点，app-tpl互动作为边构造图
  • 在图上用GNN来挖掘低阶和高阶信息(用多跳引申到邻居节点而利用其信息等方式)

4.特点： 采用图和GNN的方法能使用到协同过滤忽略的信息，挖掘出app和tpl更深层的关系，文章21年发布的，对之前的大部分方法都进行了概括和比较，前沿性很强
5.评估标准: MP MR MF MAP COV

二、《AndroLib: Third-Party Software Library Recommendation for Android Applications》(2020，ICSR)

模型名AndroLib
1.数据来源：Github、F-Droid库和AndroidTimeMachine库
2.第三方库表示方式：
3.推荐算法：将tpl推荐视作多目标组合问题，使用非支配排序遗传算法(NSGA-II)来搜索和推荐tpl，有权重机制
具体步骤：

  • 数据编码模块：先构建app和tpl的交互矩阵，然后用基于图的方式进行编码，然后计算图中节点的相似性(如果两个图节点指向具有相同边的相同节点，就认为它们是相似的)
  • 库推荐模块：用元启发式算法中的非支配排序遗传算法(NSGA-II)在考虑的多目标之间找到最优的一组库进行推荐
  • 库排名模块：对NSGA-II返回的最优解里包含的各个库进行统计，按出现次数进行排名，排名越高表示该库与正在开发的app相关性越高

4.特点：研究对象是Android的tpl，使用多目标机制，最终推荐的一组库之间是互相有联系的，而不会像之前模型一样虽然也是推荐一组库但库之间没有联系，只是按相似度高低进行推荐而已。是第一次将搜索用于tpl的尝试
5.评估标准:用十倍交叉验证(将数据集分成十个相等的部分，9个部分用于训练，1个部分进行评价，评价部分的app随机取出一半的tpl，然后用这一半去与推荐结果验证)
成功率SuccessRate、准确率、召回率、MRR、NDCG
提到的相关工作：CrossRec、LibRec、LibFinder、LipCUP

三、《Diversified Third-Party Library Prediction for Mobile App Development》(2020，IEEE TRANSACTION ON SOFTWARE ENGINEERING)

模型名Libseek
1.数据来源：google play、github、maven
2.第三方库表示方式：
3.推荐算法： 协同过滤、矩阵分解、自适应权重
具体步骤：

  • 建立交互矩阵
  • 矩阵分解

rui是共现矩阵用户u对物品i的评分，qi是物品向量，pu是用户向量

  • 训练模型的过程加权重

4.特点：引入一种自适应的权重机制，抵消了库的流行造成的偏差(即过于流行的库相应权重要降低，不流行的库权重提高)，考虑到了领域信息
5.评估标准:
测试时：对已有数据中对某app随机去除1、3、5个库，然后给它推荐5、10个库，用召回率来评估推荐的库中有没有包含去除的库
实验时：平均编码差异COV、MAP、平均均度MP、平均召回率MR

四、《CrossRec: Supporting software developers by recommending third-party libraries》(2020，The Journal of Systems and Software)

模型名CrossRec
1.数据来源：github、maven
2.第三方库表示方式：非结构化文本信息和转换成特征向量
3.推荐算法：协同过滤的混合方法
具体步骤：

  • 将app使用的第三方库转换成特征向量，其实就是是否使用的交互矩阵

4.特点：只使用协同过滤
5.评估标准：召回率

五、《基于知识图谱的移动应用第三方库的混合推荐方法研究》(2020，武汉大学硕士论文)

1.数据来源：APPBrain、github
2.第三方库表示方式：主题模型和知识图谱特征学习
3.推荐算法：LDA建立主题模型 + 基于知识图谱的推荐方法MKR
具体步骤：

  • 对app和tpl中非结构化的文本信息，用LDA来进行推荐
  • 输入某app的描述信息和与TPL的交互矩阵
  • 输出评分S1
  • 对结构化的信息，用知识图谱MKR进行处理
  • 输入某app和与TPL的交互矩阵
  • 输出评分S2
  • 聚合单元将S1与S2相结合，得到该app对各个TPL的最终评分，里面的参数α由多次实验比较来确定(本文实验得出α为0.5时效果最佳)

4.特点：两种方法混合，一个基于知识图谱一个基于LDA主题模型，结构化和非结构化信息都利用到了，且方法都比较复杂，最终融合比较简单
5.评估标准：准确率、召回率、F1值、MAP、NDCG

六、《一种面向移动应用开发的第三方库混合推荐方法》(2019，小型微型计算机系统)

1.数据来源：APPBrain
2.第三方库表示方式：简单地用某app是否使用某第三方库来表示，表示主要在app层面
3.推荐算法：使用贝叶斯定理将基于用户的协同过滤方法与基于内容的TF-IDF方法融合来实现推荐任务
具体步骤：

  • （基于协同过滤UBCF）我们首先将该app已经要使用的第三方库作为对该其的隐式反馈,基于这些隐式数据我们可以计算出与该app相似的app并将这些app调用的第三方库作为候选集，原理是构建一个是否交互矩阵横坐标是TPL、纵坐标是app，用0表示该app没有使用该TPL，，用1表示该app使用该TPL。然后用下列公式计算第i个app与第j个app的余弦相似度

再根据结果构建出一个app的相似度矩阵，横坐标、纵坐标都是app。
之后再根据

计算出第i个app与TPL的相似度，并构建相似度矩阵，其中I是第j个app与某个TPL的交互矩阵的值

  • （基于app描述内容LDA）此外,通过该app的描述文本挖掘出与其他app的语义相似度并生成另一个候选集，使用TF-IDF计算文本相似度作为两个app的相似度矩阵.
  • 最后,通过贝叶斯定理将这两个候选集融合得到最终的推荐列表.原理是新的app使用某TPL的概率与上述两种方法求出的TPL与APP的相似度的乘积成正比

然后就比较得到最大的P(app|lib)的lib就是该app最有可能使用的TPL
4.特点：两种方法混合，比较简单
5.评估标准：平均均值精度MAP和NDCG

七、《Combining Collaborative Filtering and Topic Modeling for More

Accurate Android Mobile App Library Recommendation》(2017，Internetware)
1.数据来源：github
2.第三方库表示方式：非结构化文本信息和转换成特征向量
3.推荐算法：结合主题建模LDA和协同过滤的混合方法
具体步骤：

  • 用非结构化文本信息LDA训练模型进行主题建模
  • 将app使用的第三方库转换成特征向量，其实就是是否使用的交互矩阵

4.特点：可以只给一个新的应用程序而不给它已有的库，也能进行推荐
5.评估标准：

八、《Search-based software library recommendation using multi-objective optimization》(2017，Information and Software Technology)

模型名LibFinder
1.数据来源：Maven、Github
2.第三方库表示方式：
目标是：如果一个库对该app有潜在的用处，或一个库与该app正在使用的其他库普遍被人们共同采用或具有相同标识符，则将这个库推荐给该软件
3.推荐算法：非支配排序遗传算法(MSR)和基于多目标优化的搜索算法(SBSE)
具体步骤：

  • 数据提取：从pom.xml文件里爬取app和第三方库的依赖关系，然后提取库的标识符来计算语义相似度
  • 使用搜索和遗传算法获得最优解集

4.特点：第一次采用搜索的方法来解决第三方库推荐的问题，方法和之前的推荐完全不一样，结构和原理复杂
5.评估标准: Hypervolume (HV)、Spread (△)、Generational distance (GD)

九、《SimilarTech: Automatically Recommend Analogical Libraries across Different Programming Languages》(2016，ASE)

模型名SimilarTech
1.数据来源：stack overflow
2.第三方库表示方式：库标签作词嵌入
3.推荐算法：对帖子问题的标签进行关联规则挖掘
具体步骤：

  • 对帖子问题的标签进行关联规则挖掘学习标签的关系
  • 用NLP从标签定义句(S.O.官方规定的)中识别出标签，然后用标签信息进行词嵌入学习(用连续跳图模型)
  • 建立类比tpl知识库，当输入一个程序时，先检测它的语言然后识别标签，作词嵌入，然后给它推荐最相似的库标签(余弦相似度)

4.特点：研究对象不局限于java，甚至研究python和java中同一个库的表示这种问题，尝试为多种语言推荐tpl
5.评估标准: 无，该文专注于工具开发而不是模型效果
演示视频 https://www.youtube.com/watch?v=ubx8h4D4ieE

十、《Automated Library Recommendation》(2013，IEEE)最早的协同过滤尝试

模型名LibRec
1.数据来源：github
2.第三方库表示方式： 关联规则挖掘和基于协同过滤UBCF
3.推荐算法：结合关联规则挖掘和协同过滤的混合方法
具体步骤：关联规则挖掘组件通过挖掘出一个程序使用的TPL内在关系推荐库，协作过滤组件则根据其他类似程序使用的库推荐(基于用户的UBCF)
4.特点： 两种方法混合，一个基于挖掘同一app使用的TPL之间的内在模式，一个基于协同过滤UBCF
5.评估标准：召回率  

个人总结

  • 从13年第一次提出将协同过滤用于tpl推荐任务上后，往后几年的研究大多采用xx与协同过滤相结合的混合推荐方式，常见的有LDA建模与协同过滤、关联规则挖掘与协同过滤，直到最近(20年)ccfb类中文期刊和IEEE上还有人用这种方式做tpl推荐。说明该方式是可行的、效果好的，仍然可以进行扩展研究的。
    协同过滤存在的问题：利用的信息太少，仅使用的是二维矩阵，AlikeB，BlikeC，其实就可以用C来为A推荐，但是协同过滤不行。
    除了协同过滤以外，17年的文献八首次采用搜索的思想进行tpl推荐，20年的文献二也是采用搜索的方式，值得注意的是这两篇文章都使用了元启发式算法中的非支配排序遗传算法(NSGA-II)。
    另外今年(21年)的文献一也提出了将深度学习神经网络GNN应用到tpl推荐中。
    综上所述，含有协同过滤的混合推荐是传统方法，近几年兴起了搜索和深度神经网络进行tpl推荐的新方法。
  • 数据集：来源于github、maven等，以自行搭建为主，也有利用公开的数据集例如文献一使用的MALib。
  • 数据的表示方法，有构建app与第三方库图模型的、也有转换成特征向量等。
  • 评估标准大多采用准确率、召回率、平均均值精度MAP、平均均度MP、平均召回率MR等等，各不相同但有一定重合度。
  • 目前初步想法是使用文献一的公开数据集MALib，采用知识图谱+协同过滤的方法尝试做一些初步的实践，如果实现不或效果不佳了考虑仿照21年最新的方法用深度学习模型做，暂不考虑搜索方式。