构件是软件的基本构成成分, 也是软件体系结构的基本构成要素。目前, 软件构件技术已经比较成熟。如何从规模庞大的构件库中快速准确地检索到软件开发者所需的软件构件仍是一个值得研究的问题。构件的检索与构件的描述和分类有着非常密切的关系, 对构件进行合理的描述和分类, 在构件检索时能够简化检索过程、提高检索效率。目前, 大部分的构件检索方法都基于刻面分类方法。刻面分类法被广泛应用于欧洲和印度的图书馆[1], Prieto-Díaz[2]将其引入到软件复用和构件检索领域[2]。国外系统工程领域的专家在其提出的3C(Concept, Content, Context)构件模型中对构件描述时采用了刻面分类表示方法,Srinivas等[3]采用聚类分析的方法提高构件检索的效率;Vodithala等[4]使用遗传算法优化构件检索;Dutta等[5]基于图的方法在构件库中进行构件检索。在国内, 王渊峰等[6]基于刻面分类描述构件并结合树匹配思想进行了构件检索的实验;陆敬筠等[7]针对刻面描述构件检索方法的不足, 结合领域本体相关知识, 采用领域本体和刻面描述相结合的方法进行了构件检索研究;张雷等[8]也针对构件的描述提出了构件的标识表示与自动提取算法, 并采用功能倒排索引检索构件库中的构件;童浩等[9]在蚁群算法的基础上提出了基于数据挖掘的构件决策模型, 辅助构件的检索工作;姚全珠等[10]基于树匹配的思想, 通过计算叶子节点亲和度进行构件匹配, 提出了云端构件匹配模型。
本文结合刻面分类和构件的标识对构件进行描述, 通过构件标识集合从构件描述文本中提取功能术语, 利用向量表示文本, 构建构件的向量空间模型, 使构件检索匹配问题转化为向量空间中向量计算的问题, 实现构件间的松弛匹配。同时使用基于语义相似度的构件聚类算法, 建立一棵构件聚类索引树, 从而增大了构件检索的查全率和查准率, 提高了构件的检索效率。
1 构件的标识表示与向量化 1.1 构件的标识表示构件的标识用来表示构件的主要信息。考虑到构件检索的特点和词频权重等因素, 构件的标识集合应包括领域术语集合和刻面术语集合。本文对构件的标识表示基于刻面分类法, 采用多面分类机制并结合Web服务需求, 将构件的属性划分为层次、应用领域、操作系统和形态四个主刻面, 每个主刻面下包含若干子刻面。其中, 每个刻面都由一组基本的术语构成[11]。根据构件标识集合对构件进行特征词提取, 其提取过程如图 1所示。
对构件描述文本分词时, 导入手工输入的停用词集, 过滤停用词; 根据语义库的内容对分词结果扩展, 结合构件标识集合得到构件特征词。采用特征词集对构件进行标识表示, 能够更加准确地描述构件的特征, 方便了构件向量模型的建立, 从而简化了构件相似度的计算。
1.2 构件标识向量化对构件进行标识表示时, 构件的特征词间相互独立, 利用向量来表示构件标识文本, 构造构件向量, 建立向量空间模型。在构件向量空间模型中, 构件是由构件标识(特征词)组成的集合, 并且每个特征词都有其相应的权重, 将权重值作为向量值构成构件向量。例如, 构件Comp表示为C={t1, t2, …, ti, …, tn}, 其中,ti(1≤i≤n)为第i个特征词, n为特征词的个数; 同时, 对ti给定其权重wi, 即CW =(w1, w2, …, wi, …, wn)。特征词权重的计算方法通常是使用词频-逆向文件频率(Term Frequency-Inverse Document Frequency, TFIDF)算法, 该算法最早由Salton等在文献[12]中提出, 并随着不同研究人员的研究不断改进。本文对构件进行标识表示时, 一个构件可能没有某些子刻面(构件库中存在构件含有这些子刻面)。因此, 本文中计算特征词权重值的公式采用文献[13]中使用的特征词加权公式, 公式形式如下:
$ C{W_i} = \left\{ {\begin{array}{*{20}{c}} {\frac{{{f_i} \times {\rm{lb}}\left( {\frac{n}{{{n_i}}} + 1} \right)}}{{\sqrt {\sum\limits_j^t {f_j^2{{\left( {{\rm{lb}}\left( {\frac{n}{{{n_i}}} + 1} \right)} \right)}^2}} } }}, {t_i} \in C}\\ {\frac{{-{\rm{lb}}\left( {\frac{n}{{n-{n_i}}} + 1} \right)}}{{\sqrt {\sum\limits_k^{m-d} {{{\left( {{\rm{lb}}\left( {\frac{n}{{n - {n_k}}} + 1} \right)} \right)}^2}} } }}, {t_i} \notin C} \end{array}} \right. $ | (1) |
其中: CWi为构件的第i个特征词ti的权重值;fi表示ti在构件库中出现的频率;n为构件库中构件总数;ni为构件库中含有ti的构件数;m为采用刻面分类描述构件标识得到的特征值(子刻面)的总数;d为构件Comp的标识描述中含有的特征词的个数。使用词频来代替传统用0和1表示向量, 完成构件的向量化表示, 有利于体现特征词在构件描述中的作用程度。
2 构件聚类树 2.1 构件聚类树的结构聚类树是一种数据集聚类分层表示的树结构[14-15]。聚类树将数据划分为层次结构, 从而成为一个高效检索的索引结构。本文中的构件聚类树是一棵非空的5层结构的聚类树, 其结构如图 2所示。
该聚类树有且只有一个根节点, 代表构件库中所有构件组成的构件集, 根节点为聚类树的第一层; 第二层为主刻面层, 粗略地对构件进行划分; 第三层为子刻面层, 对主刻面下的构件进行细致的划分, 将构件划分到某个子刻面; 第四层为类层, 对属于同一子刻面的构件进行聚类, 得到若干聚类中心; 第五层为构件层即叶子节点层, 该层的节点包含构件的特征词并指向具体的构件。
2.2 构件聚类树的构造过程构件库中所有构件组成的集合构成了该聚类树的根节点, 得到构件聚类树的第一层。按照刻面分类划分的主刻面粗略地将构件划分到各个主刻面下, 形成第二层。然后, 根据主刻面下的子刻面对构件进行详细划分, 同一主刻面下, 构件只属于某一个子刻面, 形成第三层。第四层为类层, 是对子刻面下的构件聚类得到的, 本文采用K近邻聚类算法对构件进行语义相似聚类。文中通过计算两个构件向量的余弦相似度来表示这两个构件的相似程度, 计算公式如下:
$ Sim({C_1}, {C_2}) = \frac{{\sum\limits_{i = 1}^m {\pmb{C}{\pmb{W}_{1i}} \times \pmb{C}{\pmb{W}_{2i}}} }}{{\sqrt {\sum\limits_{i = 1}^m {\pmb{C}{\pmb{W}_{1i}}^2 \times \sum\limits_{i = 1}^m {\pmb{C}{\pmb{W}_{2i}}^2} } } }} $ | (2) |
其中:Sim(C1, C2)是构件Comp1和构件Comp2的余弦相似度;CW1i是构件Comp1的第i个子刻面的向量权重;CW2i是构件Comp2的第i个子刻面的向量权重;m是采用刻面分类描述构件标识得到的特征词(子刻面)的总个数。子刻面下构件聚类的步骤如下:
Step1 初始化聚类中心。将构件库中的构件按照式(1) 向量化, 从子刻面下的构件中选取k个构件作为初始聚类中心, 在选择聚类中心时尽量使得k个作为中心的构件的相似度很小, 得初始聚类中心Cl =(Cl1, Cl2, …, Clk)。
Step2 根据式(2), 分别计算当前子刻面下其他构件与这k个作为类中心的构件的相似度, 并归类于与其相似度最大的那个聚类中心。
Step3 分别对得到的k个类取新的聚类中心。根据中位数的思想来更新聚类中心, 依次对k个类进行如下操作:按照相似度大小对构件排序, (假如当前子刻面下有n个构件)取第
Step4 判断新得到的聚类中心Cl′与原聚类中心Cl是否完全相同, 若完全相同则结束聚类, 跳到Step7;否则判断count的值是否小于1000, 若不小于则跳到Step7, 否则继续向下执行。
Step5 对所有构件与其所在类的聚类中心的相似度累加到一起, 记为SumSim, 表示相似度总和, 即
Step6 根据新得到的聚类中心, 按照Step2的方式进行聚类, 得到k个新的类。按照Step5的方式计算相似度总和, 得到SumSim′。若SumSim < SumSim′, 则表示新得到的k各类的聚类效果优于之前的, 将聚类中心Cl'赋予Cl, 让Cl记录有最好聚类效果的聚类中心, 然后跳转到Step3执行; 否则, 直接按照Step3的方式得到新的聚类中心Cl'=(Cl'1, Cl'2, …, Cl'k), 并让count=count+1, 跳转到Step4继续执行。
Step7 聚类完成, 结束聚类算法。
对每个子刻面下的构件都按照上述聚类算法进行聚类, 于是得到构件聚类树第四层的节点。聚类树第五层为构件层, 属于同一类的构件被分在一个类下, 构件层的节点直接指向其对应的具体的构件。
3 基于刻面标识和聚类树的构件检索 3.1 构件检索机制构件检索与构件的分类和描述密切相关, 不同的分类方法对应着不同的检索机制。通过刻面分类标识关联的特征词集合, 多角度标识待检索构件。另外, 匹配松散度也是构件检索中得一个重要参数。检索条件与检索结果精确匹配是所有研究人员最为想要的, 但在实际实验过程中, 这种精准匹配的机会并不多, 大多数情况下还是寻找能够最大相似匹配的构件。目前, 基于刻面描述的构件的检索主要采用的还是以传统的数据库检索技术为主, 并结合同义词词典和刻面术语间的层次结构来实现构件的松弛匹配[6]。
本文的检索方法基于语义相似度, 具备一定的模糊匹配功能; 另外, 用户对要检索的构件的描述可能不完整, 不能包含所有刻面分类标识集合中的特征词, 本文的检索方法为用户设置默认值, 使其具备一定的张弛能力, 从而使检索结果具有良好的查准率与查全率。
3.2 构件检索过程经过构件的向量化处理, 构件检索最终转化为构件相似度的计算。其基本思想如下:在建立了构件聚类树的基础上, 根据采用刻面分类法划分得到的刻面分类标识集合提取待检索构件(用户的检索条件QU)描述中的特征词, 根据构件向量模型将待检索构件向量化。
$\pmb{Q}{\pmb{W}_i} = \left\{ \begin{array}{l} \frac{{{f_i} \times {\rm{lb}}\left( {\frac{n}{{{n_i}}} + 1} \right)}}{{\sqrt {\sum\limits_j^t {f_j^2{{\left( {{\rm{lb}}\left( {\frac{n}{{{n_i}}} + 1} \right)} \right)}^2}} } }}, \;\;{t_i} \in QU\\ - \frac{1}{{\sqrt {m - d} }}, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{t_i} \notin QU \end{array} \right.$ | (3) |
待检索构件的特征词的权重值计算公式与式(1) 略有不同, 采用式(3) 进行计算。其中, QWi为检索构件Query的第i个特征词ti的权重值, fi为ti在构件库中出现的频率, n为构件库中的构件总数, ni为构件库中含有ti的构件数, m为基于刻面分类描述构件标识得到的特征值(子刻面)的总个数, d为检索构件Query的标识描述中含有的特征词的个数。依次计算检索构件与构件聚类树第四层的类层中的各个节点(表示聚类中心的构件)的相似度, 相似度计算公式类似于式(2), 即
$ Sim(C, QU) = \frac{{\sum\limits_{i = 1}^m {\pmb{C}{\pmb{W}_i} \times \pmb{Q}{\pmb{W}_i}} }}{{\sqrt {\sum\limits_{i = 1}^m {\pmb{CW}_i^2 \times \sum\limits_{i = 1}^m {\pmb{QW}_i^2} } } }} $ | (4) |
其中:Sim(C, QU)是作为聚类中心的构件Comp与检索构件Query的余弦相似度;CWi是构件Comp的第i个子刻面的向量权重;QWi是检索构件Query的第i个子刻面的向量权重;m是基于刻面分类描述构件标识得到的特征词(子刻面)的总个数。在每个子刻面的多个聚类中心中选取与检索构件相似度最大的聚类中心, 记录该类中的所有构件。根据刻面划分原理, 一个主刻面下不同子刻面包含的构件不同, 与检索构件拥有较高相似度的聚类中心下的所有构件都可作为检索结果候选构件, 于是对同一主刻面不同子刻面下被记录的构件求并集; 由于一个构件含有多个刻面值(特征词), 故同一个构件会出现在不同主刻面下, 因此再对不同主刻面下满足条件的所有构件求交集, 使得到的检索结果中的构件不重复。计算所得构件集合中的构件与检索构件的相似度, 满足要求的构件与检索构件的相似度记为S1(0≤S1≤1);上述构件集合中的构件在不同主刻面下都有其与所属类的聚类中心的相似度, 为了体现聚类中心在计算检索构件与检索结果中的构件的最终相似度的作用, 将构件在不同主刻面下的相似度求和取平均数, 记为S2(0≤S2≤1), 于是可以得到检索构件与上述构件集中构件的最终相似度记为S(0≤S≤1), S=(S1+S2)/2。通过在不同阈值下进行的实验测试, 发现阈值取为0.7, 即构件相似度S≥0.7时, 检索结果的查准率和查全率较好, 故在本文中阈值设为0.7, 第5章的实验也是在此默认值下进行的。最后, 对相似度S≥0.7的构件进行排序, 得到最终检索结果。
算法流程描述如下。
输入 检索构件Query描述文本; 构件聚类树T; 构件刻面标识集合FT。
输出 相似度从大到小的N个构件。
1) for FT中的所有特征词
2) if (FT的特征词i在检索构件的描述中出现)
3) array_Qi=1;
4) else
5) array_Qi=0;
6) array_QWi= QWi;
7) end for;
8) for T的类层中的所有节点
9) Sim_QC=Sim(C, QU);
10) end for;
11) for T的子刻面层的所有节点
12) maxSim=max(Sim_QC, k);
13) 相似度最大类中的所有构件保存到maxSim_C;
14) end for;
15) for T的主刻面层的所有节点
16) unionCQ=Union(maxSim_C, n);
17) unionCQ中的构件与聚类中心的相似度的值保存到unionCQ_Sim;
18) end for;
19) array_mixCQ=Mix(unionCQ, n);
20) array_mixCQ_Sim记录array_mixCQ中的构件与所属类中心的相似度;
21) for array_mixCQ中的所有构件
22) S1=Sim(C, QU);
23) S2=n个主刻面下的相似度的平均值;
24) if ((S1+S2)/2≥0.7)
25) result=(array_mixCQi, (S1+S2)/2);
26) end for
27) sort(result);
算法说明:步骤1)~7) 是将检索构件进行向量化表示, 步骤6) 按式(3) 进行计算; 步骤8)~10) 用式(4) 计算检索构件与聚类树类层各节点(即作为聚类中心的构件)的相似度; 步骤11)~14) 是选取与检索构件相似度最大的节点作为聚类中心, 步骤12) 中的k为聚类个数; 步骤15)~18) 是对同一主刻面下不同子刻面中所有构件求并集; 步骤19) 和步骤20) 是对不同主刻面下得到的构件集合求交集同时记录构件与所属聚类中心的相似度; 步骤21)~26) 是计算检索构件与符合要求构件的总相似度; 步骤27) 是将得到的检索结果中的构件排序呈现给用户。该检索算法的空间复杂度取决于构件的个数; 由于构件库的刻面数一般不超过8个, 在本文算法中相对于构件的个数可以忽略不计, 故算法的时间复杂度为O(n)。
4 实验结果及分析为验证本文所提出的构件检索方法能提高检索的效率, 本文使用模拟构件库进行构件检索实验。通过对开源中国(www.oschina.net)的开源软件库中的部分开源组件和控件(视为构件)信息进行采集处理得到实验数据集, 构建了一个包含Web应用、程序开发、图像处理、数据库、手机/移动开发等领域共2559个构件的本地构件库。
检索效果通过评测查准率P、查全率R和F-measure[16]三个指标来体现。三个指标的计算公式分别为P=nr/Nq, R=nr/Nr, F-measure=2PR/(P+R), 其中:nr是检索结果中满足检索条件的构件个数; Nq是检索得到的构件的总个数; Nr是构件库中满足检索条件的构件个数。F-measure是对检索结果的查准率和查全率的一个综合评价, 能够有效地评价检索的查准和查全效果。只有当P和R相近且都较大时, F-measure才会较高。
4.1 实验结果对比实验分别根据文献[8]和文献[17]的思想实现了基于构件标识自动提取的功能倒排索引构件检索方法和分级聚类索引构件检索方法, 并与本文提出的检索方法在相同的数据集和实验平台上进行对比实验。为突出聚类树在本文所提出的检索方法的作用, 本文还实现了基于刻面分类标识和聚类分析的构件检索方法, 这种方法类似于文献[13]中提出的检索方法, 不使用聚类树思想, 在构件向量化表示之后直接对构件库中的构件聚类, 检索时采用第3章中描述的检索方法。因此, 对比实验共分为4组, 各组对应检索方法如表 1所示。
通过Matlab 8.5实验仿真平台和MyEclipse10对上述算法进行实现。分别对这4组方法进行10次检索实验, 每次实验使用30个检索构件, 计算得到查准率和查全率的平均值, 再计算F-measure的值。各组检索结果如表 2所示。
从表 2中的4组实验检索结果可以明显看出D组的查准率、查全率和F-measure的值都要比C组的高很多, 说明在检索方法中采用了聚类树比单纯使用聚类分析得到的效果较好。另外, 也可看出相对于A组和B组的检索方法, 使用本文提出的检索方法(D组)得到的查准率和查全率有明显提高, 而且F-measure的值也比其他两种方法得到的要大。
4.2 扩大构件库规模实验考虑到构件库的规模正逐渐扩大, 为验证本文方法在大规模构件库中检索时的效果依然良好, 采用随机抽取本地构件库中的构件重复入库的方法[8], 增加本地构件库中构件的数量。分别在7677个、12795个、17913个以及23031个构件的模拟构件库中重新进行检索实验, 依然进行10次、每次30个检索构件的检索实验。查准率、查全率和F-measure值的实验结果分别如图 3~5所示。
另外, 为说明构件库规模增大后算法的检索效率情况, 给出不同算法查询响应时间, 如图 6所示。
实验结果表明,构件库的规模增大后, 本文算法的查准率和查全率仍在87%以上, F-measure值保持在0.90左右, 比其他三种算法的检索结果要好; 而且查询响应时间的增加在对数级别以下。所以,本文方法是行之有效的, 而且拥有较好的检索效果, 同时也可在规模较大的构件库中使用。
5 结语本文提出的基于刻面分类标识和聚类树的构件检索方法对构件进行刻面分类标识描述, 并通过构件向量模型将构件向量化表示, 建立构件聚类树, 在检索构件时直接计算检索构件与聚类中心的语义相似度, 将具有较高相似度的构件提供给用户供用户选择。实验结果表明,本文的检索方法有着较高的查准率与查全率, 并且在构件库规模的扩大后依然有较好的检索效果。本文方法的检索效果依赖于构件的描述和构件聚类, 因此后续工作将对构件的描述方法和构件聚类算法进行重点研究, 结合Web服务发现领域的相关知识, 完善构件描述方法、优化构件聚类, 从而进一步提高检索效果。
[1] | RANGANATHAN S R, GOPINATH M A. Prolegomena to Library Classification[M]. 3rd ed. Madras: Madras Library Association, 1967. |
[2] | PRIETO-DÍAZ R. Implementing faceted classification for software reuse[J]. Communications of the ACM, 1991, 34(5): 88-97. DOI:10.1145/103167.103176 |
[3] | SRINIVAS C, RADHAKRISHNA V, RAO C. Clustering and classification of software component for efficient component retrieval and building component reuse libraries[J]. Procedia Computer Science, 2014, 31(1): 1044-1050. |
[4] | VODITHALA S, PABBOJU S. A dynamic approach for retrieval of software components using genetic algorithm[C]//Proceedings of the 2015 IEEE International Conference on Software Engineering and Service Science. Piscataway, NJ: IEEE, 2015: 406-410. http://ieeexplore.ieee.org/document/7339085/ |
[5] | DUTTA S, SENGUPTA S. Retrieval of software component version from a software version database: a graph based approach [C]//Proceedings of the 2015 International Conference on Advances in Computer Engineering and Applications. Piscataway, NJ: IEEE, 2015: 255-259. http://ieeexplore.ieee.org/document/7164706/ |
[6] | 王渊峰, 张涌, 任洪敏, 等. 基于刻面描述的构件检索[J]. 软件学报, 2002, 13(8): 1546-1551. (WANG Y F, ZHANG Y, REN H M, et al. Retrieving components based on faceted classification[J]. Journal of Software, 2002, 13(8): 1546-1551.) |
[7] | 陆敬筠, 宋培钟. 领域本体和刻面描述相结合的构件检索研究[J]. 计算机应用与软件, 2013, 30(8): 36-38. (LU J Y, SONG P Z. On component retrieval method based on the combination of facets description and domain ontology[J]. Computer Applications and Software, 2013, 30(8): 36-38.) |
[8] | 张雷, 陈立潮, 潘理虎, 等. 构件的标识表示与检索方法研究[J]. 小型微型计算机系统, 2013, 34(5): 1076-1079. (ZHANG L, CHEN L C, PAN L H, et al. Study on tags representation of components and tags based components retrieval[J]. Journal of Chinese Computer Systems, 2013, 34(5): 1076-1079.) |
[9] | 童浩, 孙航, 李晶, 等. 基于改进蚁群算法的构件检索方法[J]. 计算机应用研究, 2015, 32(7): 2057-2059, 2064. (TONG H, SUN H, LI J, et al. Method based on improved ant colony algorithm for component retrieving[J]. Application Research of Computers, 2015, 32(7): 2057-2059, 2064.) |
[10] | 姚全珠, 冯欢, 田琳, 等. 基于云端的构件库检索模型[J]. 计算机应用, 2016, 36(增刊1): 262-264. (YAO Q Z, FENG H, TIAN L, et al. Retrieval model based on cloud component library[J]. Journal of Computer Applications, 2016, 36(Supp1): 262-264.) |
[11] | 王映辉. 构件式软件技术[M]. 北京: 机械工业出版社, 2012: 86. (WANG Y H. Component-Based Software Technology[M]. Beijing: China Machine Press, 2012: 86.) |
[12] | SALTON G, CLEMENT T Y. On the construction of effective vocabularies for information retrieval[C]//SIGPLAN 1973: Proceedings of the 1973 Meeting on Programming Languages and Information Retrieval. New York: ACM, 1973: 11. http://dl.acm.org/ft_gateway.cfm?id=951766&ftid=238938&dwn=1 |
[13] | 刘大昕, 赵磊, 王卓, 等. 一种基于刻面分类和聚类分析的构件分类检索方法[J]. 计算机应用, 2004, 24: 89-90. (LIU D X, ZHAO L, WANG Z, et al. A method of component classification retrieval based on facet classification and cluster analysis[J]. Journal of Computer Applications, 2004, 24(Supp1): 89-90.) |
[14] | YU D T, ZHANG A D. Cluster tree: integration of cluster representation and nearest neighbor search for large datasets with high dimensions[J]. IEEE Transections on Knowledge and Data Engineering, 2003, 15(5): 1316-1337. DOI:10.1109/TKDE.2003.1232281 |
[15] | 田晓珍, 任姚鹏, 王春红, 等. 一种改进的构件聚类索引树的研究[J]. 现代计算机, 2014(8): 12-15, 25. (TIAN X Z, REN Y P, WANG C H, et al. Research on an improved component cluster index tree[J]. Modern Computer, 2014(8): 12-15, 25.) |
[16] | RIJSBERGEN C J. Information Retrieval[M]. London, UK: Butterworths Press, 1979: 120. |
[17] | 王文霞. 基于分级策略和聚类索引树的构件检索方法[J]. 计算机技术与发展, 2016, 26(4): 110-11. (WANG W X. A component retrieval method based on classified policy and cluster index tree[J]. Computer Technology and Development, 2016, 26(4): 110-11.) |