《一种区间型支持向量回归算法及其在网络信息挖掘中的应用》由会员分享，可在线阅读，更多相关《一种区间型支持向量回归算法及其在网络信息挖掘中的应用（5页珍藏版）》请在金锄头文库上搜索。
1、 thProceedings of the 25 Chinese Control Conference 7-11 August, 2006, Harbin, Heilongjiang 一种区间型支持向量回归算法及其在网络信息挖掘中的应用 1 引引 言言(Introduction) 随着互联网的快速发展，越来越丰富的信息呈现在用户面前， 网络信息挖掘(Web Mining)技术成为近年来一个新的研究课题，它是数据挖掘技术在网络信息处理中的应用。网络信息挖掘是指在大量训练样本的基础上，得到数据对象间的内在特征，并以此为依据进行有目的的信息提取。根据挖掘的对象不同，网络信息挖掘可分为网络内容挖掘(W
2、eb Content Mining) ， 网 络 结 构 挖 掘 (Web Structure Mining)以及网络用法挖掘(Web Usage Mining).。其中网络用法挖掘又称为Web用户使用记录挖掘，其IEEE Catalog Number: 06EX1310 此 项 工 作 得 到 宁 波 博 士 基 金 资 助 项 目 资 助 , 项 目 批 准 号 : 2005A610002. 主要目标是从Web的访问记录中抽取感兴趣的模式， WWW中的每个服务器都保留了访问日志 （Web access log），它记录了关于用户访问和交互的信息。因此可以通过挖掘Web日志记录来了解用户的网
3、络行为数据所具有的意义，分析和探究Web日志记录中的规律，可以识别电子商务的潜在客户，增强对最终用户的因特网信息服务的质量和交付。但在Web使用记录挖掘中经常会遇到这样的情况即我们所得到的日志信息由于部分数据丢失而是不完整的，例如当我们试图挖掘某客户的浏览兴趣取向时发现在其使用记录日志对某些信息只有一个大致的范围，传统的Web日志挖掘方法对这部分数据往往不能很好地处理，进而会影响到最终的挖掘效果。 赵英刚1，刘仰光2，何钦铭1,21. 浙江大学 计算机科学与技术学院, 杭州 310027 E-mail: 2. 浙江大学宁波理工学院 信息科学与工程分院, 宁波 315100 E-mail:
4、摘 要：传统的支持向量回归（SVR）算法不能很好地处理含有不确定信息的训练数据, 为解决这一问题,本文 引入数学中区间知识的概念, 利用区间数来表征不完整的输入信息，将区间运算引入SVR算法中，进而提出一种 对不完整信息进行处理的支持向量回归算法，该算法拓展了支持向量回归算法的应用范围和处理能力，将其应 用于网页信息挖掘中的实验表明，该算法在不完整或残缺的网页信息挖掘方面可行而有效，具有现实的推广意 义。 关键词：回归,支持向量, 网页挖掘,区间 One Kind of Interval Support Vector Regression Algorithm and Its Applicati
5、on in Web Information Mining Yinggang Zhao1, Yangguang Liu2, Qinming He1,2 1. College of Computer Science, Zhejiang University, Hangzhou 310027, China 2. School of Information Science & Engineering, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China Abstract: Traditional suppo
6、rt vector regression (SVR) algorithm can not handle training data which contain incomplete information. In order to overcome this shortcoming, this paper introduced the interval number to represent the incomplete information, and uses interval operation to replace the real operation, then an uncerta
7、inty support vector regression algorithm (USVR) was proposed, which can extend the SVRs application area and improve its learning ability. We used the USVR algorithm to web information mining experiment, and the results show that this algorithm is feasible and effective. Key words: regression, suppo
8、rt vector, web mining, interval825支持向量回归（Support Vector Regression, SVR）算法是支持向量机（Support Vector Machine, SVM）用于函数逼近和回归问题时的变种算法，由于其良好的预测性能，SVR算法在Web日志挖掘中已有成功的应用。但是传统的SVR算法只能对具有确定性日志信息的数据进行较好预测，对于回归中遇到的大量的不完整日志信息则力不从心。 本文中我们用区间数来表示不完整日志信息， 提出了一种基于不完整信息的支持向量回归算法， 该算法可以对具有包含不完整数据信息的日志记录 进行处理，扩宽了支持向量回归算法
9、应用的范围， 很有推广意义。. 2 支 持 向 量 回 归 算 法 (Support Vector Regression Algorithm)支 持 向 量 回 归 算 法 (Support Vector Regression Algorithm)1212 对于给定的训练样本集1(（,)Niiix y=n ixR为输入变量的值，iyR为相应的输出目标值， 为训练样本数），函数回归问题就是找到一个从输入空间到输出空间的映射N:nfR Ri使得 ( ),iif xw xb= , 满足时,式(4)显然等价于: 1,2,.iN=21min2 , ,iiiiwyw xbsubject tow xby +
10、 + + (6) 松弛回归方法的几何意义如图1所示,对优化问 题式(6),通过采用数学规划中的对偶方法,可得到最 优回归的线性函数的和支持向量. w图 1 松弛回归方法 图中和之间的区域称为回归间隔. 引入Lagrange系数i、* i,最后将式(6)转化为如下的对偶问题: *11max()()NNiiiii iiWy=+*,11()()(2Niijji i j)xx=*1 *()00,1,.,Nii iiisubject to CiN = =(7) 求解上面的二次规划,得到最优的Lagrange系数i、* i以及阀值. 其中bi, * i0所对应的样本被称为支持向量(Support vect
11、or, SV). 在非线性情况下,引入变换:nRH,将样本从输入空间nR映射到一个高维特征空间H,然后 在H中求取最优的函数使得定义的风险函数最小, 根据Mercer条件存在映射和核函数(, )K ,使得 ( ,)( )()ijijK x xxx=,引入核函数后,得支持向量回归估计函数为: 826*1( )() ( , )Niii if xK x=xb+ (8)3 区间运算(Interval Operation)区间运算(Interval Operation)345345 记表示实数集，则实数上的区间数可表示 为：R , :,x xxR xxx=x其中，x和x分别 称为区间数的下限 （或左端点
12、） 和上限 （或右端点） ， xx称为区间的宽度。 当xx=时， 区间数退化为一 个实数，实数集上的所有区间组成的集合记为R IR，即 , : ,.IRx xx xR xx=。 区间数还可以表示为，其中x( ), ( )mw=xyxyxyxxyx如果或此处假定 0 , (9)R， ,0, , ,0. , ,xxx xxxx xx= +=+=+xxx(10)同样可以把实值函数的概念的扩展可以得到所 谓 的 区 间 函 数 . 如 果( )f x是 实 函 数 ， 其 中12( ,.,)Tnx xx=x，通过把相应的实变量x替换为区 间变量，相应的运算规则为(9)-(10)则可以得到所谓 函数的区
13、间扩展. 下面给出我们将要用到的有关区间运算表达式 的一个重要定理. 定理1 （ 区间 分 析 基本 定 理） 如果函数 是区间运算符连接的表达式， 其中1(,.,)nf zz( , , , )+ 1,.,nIRzz为有限个区间.如果 11,.,nnxzxz 那么 11(,.,)(,.,).nnffxxzz 4 不完整信息的支持向量回归算法(Support Vector Regression Algorithm for Incomplete Information)不完整信息的支持向量回归算法(Support Vector Regression Algorithm for Incomplete
14、 Information) 4.1 4.1 输入样本的区间表示(Interval Express for Input Samples) 具有个属性的输入样本的属性值用 维向量n12,.,na aan1(,.,)pppnxx=x表示.假设目前还没有度量任何属性值.那么属性值将按顺序1(,.,)n=，其 中12 ,.,1,2,.,ina aain=，逐个度量属性值.在 回归阶段，当我们对px回归的时候，已经度量一些属性值，而没有度量或无法度量另外的一些属性值. 也就是说，n维向量1(,.,)pppnxx=x是一个不完整信息的输入.我们用区间向量表示这信息不完整的向量.当属性值1(,.,)pppXX
15、=Xnpix是已知的， 相应的区间表示为,pipipiXxx=； 当属性值pix未知时候，piX为包含pix的所有可能值的区间.下面的引理说明了，当所有的属性值都已知时，判别函数的输出与 标准支持向量回归算法的输出是完全相同的. 引 理 1 假 设 支 持 向 量 回 归 机 的 训 练 集 为 ( ,),1,2,.,iix yiN=， 训 练 后 的 分 类 函 数 为1(,.,)pppnxx=x， 给 定 新 的 输 入 模 式 为1(,.,)pppnxx=x.如果的每个属性都已知，那么 px()()ppff=xX (11) 其中，为相应的区间表示形式，为回归函数（8）的区间扩展. pXpx( )f X证明：容易验证当区间的宽度为0时候，根据区 间运算规则(9)-(10)运算结果的区间宽度为0， 并且结 果中包含的唯一的一个数等于根据实数代数运算的 结果.核函数项计算值 (,) (,)|,pipippiiKK=XXxxxXxX， 1,2,.,iN=.因为分别只包含一个数,1,2,.,pii =XXN,1,2,.,pii =xxl，所以的宽度为0，包含的唯一实数等于.所以引理成立
