一种基于线性回归的WEB 服务识别方法#
帖晶,陈行益*
基金项目:下一代电信网络融合业务支撑环境基金项目(国家863)
作者简介:帖晶,(1985-),女,硕士,下一代网络与智能网。
通信联系人:陈行益,男,高级工程师,下一代网络与智能网。E-mail: tiejingjing@126.com
(北京邮电大学网络技术研究院,北京 100876)
5 摘要:对于互联网上出现的大量WEB 服务,如何识别这些WEB 服务是当前服务计算领域研究
的一个热点问题。本文提出了一种新型的基于线性回归的非结构化WEB 服务识别方法,主要
包括基于线性回归的目标拟合曲线的构造算法和基于线性回归的非结构化WEB 服务识别算
法,并通过实验从服务的召回率和准确率等方面分析,证实了算法的正确性。
关键词:线性回归;网页去噪;REST;WEB 服务;WEB API
25 0 引言
随着互联网上WEB 应用的增多,越来越多的WEB 服务被企业发布到互联网上,WEB
服务在企业之间及企业内部开发基于构件的松散耦合系统中起着重要的作用。现有WEB 服
务从使用规模和数量上主要分为两大类:1)以WSDL 为代表的结构化WEB 服务,这类服务
主要使用SOAP 协议,数据传输格式为XML;2) 以RESTful[1][2]为代表的非结构化WEB 服
30 务。RESTful WEB 服务遵循REST(Representational State Transfer:表示性状态转移)风格,这
类服务在整个WEB 服务中占大多数份额;其他非结构化WEB 服务可以归结为其他形式的
WEB API[3][4]。传统使用SOAP 协议的结构化WEB 服务有被现在广泛使用的RESTful WEB
服务逐步取代的趋式。主要原因是后者在URL 链接的设计, 协议的选择和消息的传输上都
比前者简单。现在许多著名的WEB 站点(如Google,Amazon,Facebook,Flickr 等)都提供
35 了容易使用的,免费访问它们资源的RESTful WEB 服务及APIs。
以RESTful 为代表的非结构化WEB 服务在互联网上是广泛存在的,查找和搜索这类服
务为企业间信息互通和服务集成有着非常重要的意义。非结构化WEB服务的开发是自治的,
没有统一标准或规则,服务文档通常不是一个类似于WSDL 的接口描述文件,而是一个普
通的HTML 网页。非结构化WEB 服务的这些固有特性的存在使得现有的服务爬虫引擎难以
40 识别和抓取这类服务。国外的Seekda 对结构化WEB 服务提供了很好的支持。对于非结构
种新型的基于多元线性回归[6]的非结构化WEB 服务识别算法。
本文第一部分是引言;第二部分提出了本文应用的多元线性回归公式;第三部分是基于
多元线性回归的非结构化WEB 服务的识别算法,主要包括网页去噪及算法的描述;第四部
45 分是相关实验及实验结果分析,第五部分总结了全文并给出了将来的工作。
1 回归公式的提出
回归是数据挖掘[5]中一种基于统计的求解分类问题和预测问题的方法,回归方法一般是
通过一条曲线来拟合一组点的方式来实现由已知值预测未知值。一般的线性回归公式[6]采用
如下形式:
0 11 2 2 ... ... i i n n y=β +βx+βx+ +βx+ +βx+ε 50
其中n 表示输入变量的个数, i x 称为解释变量或回归变量,1 2 , ,..., n x x x称为输出变量(要
预测的变量),ε 表示误差项, 0
β
表示回归常量。通过确定回归系数0 1 2 , , ,..., n β β β β 及ε ,
可以估计输出变量y 和回归变量1 2 , ,..., n x x x之间的关系。
本文使用多元线性回归来预测一个HTML 网页是不是WEB 服务,本文提出的多元目标
55 线性回归公式为:
代表非结构化WEB 服务的特征项单词,m 代表样本文档集合的文件个数,
( ) j i g x 表示单文档中i x 的评估系数, ( ) i freq x 表示单文档中i x 出现的频率,max Freq 60 表
示单文档中出现频率最大的单词的频率, ( ) i i f x 表示i x 的拟合系数,
0
( )
m
j i
j
g x
m
= Σ
表示样本文
档集合所有文档中i x
的评估系数的均值。对于要预测的HTML 网页,使用下面的预测公式
拟合化:
1 1 1 2 2 2 ' ' ( ) ' ( ) ... ' ( ) ... ' ( ) i i i n n n y = f x x +f x x + +f x x+ +f x x (4)
' ( ) ( )
max
i
i i
f x freq x
Freq
=
65 (5)
各参数及函数的定义于(1),(2)公式类似,有了线性回归的目标函数及预测函数,对HTML
网页的非结构化WEB 服务的识别就转化为计算各个预测函数y ' 与目标函数y 的临近空间
2 基于多元线性回归的WEB 服务识别算法
70 2.1 网页去噪
由于本文提取的算法处理的是HTML 网页,我们必须结合HTML 网页的特性(HTML
网页一般包含导航条,广告栏,版权等与网页主体内容无关的信息)有效构造线性回归函数,
算法的初始准备工作就是必须对HTML 网页进行网页去噪处理,因为一个文本中对分类有
用的单词只占小部分,而大部分单词与要判断的文本类无关,属于“噪音单词”,如果不进
75 行网页去噪,使用公式(1)构造的回归函数在n 维空间拟合的曲线可能不能很好的代表或者
接近于真实曲线,如果网页的噪音过多,完全可能淹没有用信息,从而导致基于线性回归的
算法的精度极低。
本文提出的基于多元线性回归的WEB 服务[7-9]识别算法中的网页去噪部分主要过滤了
网页中与网页主体无关的内容,如导航栏,版权信息,广告栏,友情广告链接等等。网页去
80 噪有助于回归函数中拟合系数计算的准确性,同时也减少了拟合函数的维度,加快算法运算
速度。本文在网页去噪方面首先是预提取HTML 网页中TITLE, H1 到H6,STRONG 等标签
的内容,赋予这些内容较高权重(通过给提取的内容乘以一定的增倍因子,实验中
TITLE:10,H1:6,… ,H6:1,STRONG:2),然后使用一定算法除去导航条,版权,广告等噪音
信息以及一些img, script, style, !doctype, base 等与主体内容无关的标签的来净化网页。为了
85 不丢失主体信息,本文去噪算法比较保守的过滤了网页主体内容部分的比较集中并短小的
URL 链接,本文认为短链接并且比较集中更可能是广告或相关友情链接,长链接更可能体现
出与网页主体的相关性。由于网页去噪本身就是一个比较复杂的研究热点,超出了本文的范
围,故不再此详细说明。
2.2 基于多元线性回归的WEB 服务识别算法
90 本文方法的核心是使用上文提出的目标线性回归公式来生成目标拟合曲线,只有目标拟
合曲线构造得当,并使用类似的方法构造预测曲线,才能正确的预测要识别的HTML 网页
是不是非结构化WEB 服务。因此首先给出目标拟合曲线的生成算法CreateFittingCurve 的
伪代码实现及关键步骤的说明:
Algorithm: CreateFittingCurve
Input: S (Training Pages set);
Output: M(An Pages-Tokens-Map: present a fitting curve);
1. FOR(int i=0;i<S.size;i++){
2. get a page P from S;
3. String T= Parse P’s TITLE, H1 to H6,STRONG…content,
4. T+=P’s denoising and extract the P’s content;
5. Partition of T ;
6. Read T and remove stop words;
7. Map<String, Integer> M1= Statistic the frequency of different words of T;
8. Find T’s words max frequency, calculate each word assessment factor ;
9. Save M to Fi;
10. }
11. Map<String, Float> M2;
12. FOR(int i=0;i<F.size;i++){
13. get a page Fi from temp files set F;
14. Read each line :Word and the Word assessment factor of Fi,do{
15. if( Word not exist in M2){
16. set Word’s assessment factor and file Frequency =1;
17. M2.PUT(Word’s name, assessment factor);
18. }
19. else{
20. Word = get Word from M2;
21. Word’s assessment factor+= assessment factor;
22. Word’s file Frequency+=1;
23. M2.PUT(Word’s name, the Word’s assessment factor);
24. }
25. }
26. }
27. FOR(int i=0;i<M2.size();i++){
28. if(M2.getValue(i). file Frequency <given threshold)
29. M2.remove(i);
30. M2.getValue(i). set assessment factor =
31. M2.getValue(i).get assessment factor/ F.size;
32. }
33. Delete F;
34. RETURN M2;
算法的输入为样本集合,算法的输出为代表构建好的目标拟合曲线的对象容器,算法的
95 1-4 表示对样本集合中的一个网页进行网页去噪,5-9 表示对进行去噪的网页分词并去除停
用词,统计分词后每个单词的出现频率,并计算每一个单词的拟合系数,并将该单词的相关
信息(包括单词名称,出现的频率,拟合系数)保存到对应的临时文件中。12-26 用于统计各
个临时文件中各个单词的总的出现次数,出现该单词的文件个数,及各个单词的拟合系统的
累加,27-32 行主要对统计后的单词进行过滤,如果单词的出现文件个数小于给定的阈值,实
100 验中取20,删除该单词(不能作为目标拟合曲线的特征项)。
下面给出基于线性回归的WEB 服务识别算法WSRA-BALR(WEB services recognition
algorithm based on linear regression)的伪代码描述:
Algorithm: WSRA-BALR
Input: P (A HTML Page);
Output: Boolean value;
1. If y not exits{
2. Map<String, Float> M= call CreateFittingCurve algorithm;
3. build y which present the aim target fitting curve;
4. }
5. build y ’ which present the compare fitting curve;
6. result = Math.abs(y’/y);
7. if(result < given threshold && result > given threshold’)
8. RETURN false;
9. RETURN true;
算法的输入是要预测的HTML 网页,输出是预测为真或假的布尔值,其中算法
WSRA-BALR 第3 步目标拟合曲线y 的构造是使用本文提出的公式(1)来计算的,第5 步类似
105 CreateFittingCurve 算法流程:对于预测的网页进行网页去噪,分词,剔除停用词,统计单
词的出现频率,计算拟合系数,并使用本文提出的公式(4)来构造比较拟合曲线,第7 步中
阈值实验选取为0.6 与1.4,如果计算结果不在0.6 与1.4 的范围内,算法预测该HTML 网
页不是非结构化WEB 服务的网页。
3 实验及实验结果分析
110 3.1 实验数据来源
本文实验的数据来源主要是从programmableWEB 网站的http://www.programmable
WEB.com/apis/directory/1?protocol=REST 提供满足REST 协议的服务查询列表作为下载来源
构建实验的训练集。programmableWEB 中当前收集RESTful 服务有2160 个,本文从该目录
列表中随机下载了100 个RESTful WEB 服务网页作为训练的样本集合。
115 3.2 实验结果及结果分析
为分析本文提出的网页预测算法的可行性,本文首先使用训练集中的100 个服务网页作
学术论文网Tag:代写论文 电子论文代写 代写代发论文 代写毕业论文 论文发表 代发论文
|