数据挖掘中强局部加权回归算法实现

数据挖掘中强局部加权回归算法实现

虞 乐，肖基毅

(南华大学计算机科学与技术学院，湖南 衡阳 421001)

摘 要： 线性回归是利用称为线性回归方程的最小二乘函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。在数据挖掘中占有十分重要的地位。而强局部加权回归方法应用得尤为广泛。本文建立了变参数回归模型，并在算法上加以实现.

关键词： 数据挖掘，变参数回归模型，强局部加权回归

Implementation of robust locally weighted regression algorithm in Data Mining Abstract: Regression analysis includes any techniques for modeling and analyzing several variables, when the focus is on the relationship between a dependent variable and one or more independent variables .It plays a very important position in Data Mining. And application of robust locally weighted regression algorithm is particularly extensive.In this paper, provides a kind of model of varying parameter regression and implementation it in algorithm.

Keywords: Data Mining; varying parameter regression model; robust locally weighted regression

0.引言

在这样一个信息爆炸的时代，信息过量成为需要面对的问题，如何才能不被信息的过量所淹没，并从中及时发现有用的知识，提高信息利用率呢?数据挖掘（Data Mining,DM）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中, 提取隐含在其中的、人们事先不知道的, 但又是潜在有用的信息和知识的过程。在数据挖掘技术的发展过程中,回归分析是会经常使用的到。回归分析是通过一个或几个变量的变化去解释另一变量的变化。包括找出自变量与因变量、建立数学模型、检验模型、估计预测等环节。变量之间的关系，有的是确定的函数关系，有的则没有，变量 y 随着变量 x 而变化，但不能由 x 的取值精确求出 y 的值。在回归分析技术中，最为基础的是一元线性回归技术。因变量观测值的观测误差服从同一正态分布( 即等权、 等方差)的情况是最常见的。因此,等权回归的情况较多。其实, 两个变量之间的关系, 有时会是非常微妙的, 仅凭简单的直线、曲线参数方程模型是远远不够的。所以本文采用强局部加权回归方法。

1.局部加权回归

局部加权回归算法(LOWESS)由C1eveland提出，并由C1eveland和Develin推广到多个自变量的情形，主要利用局部观测数据对欲拟合点进行多项式加权拟合，并用最小二乘法进行估计。它允许线性回归模型中的参数随着自变量的不同取值而变化，即不同的观测值对应于一组不同的参数，在自变量空间的任一点处给出回归函数的一个估计值。

1.1 变参数回归模型

对于单参变量来说，设{xi,yi}, i 1,2, ,n.为n组观测值。建立如下模型

yi 0(xi) 1(xi)xi p(xi)xip i,i 1,2, n （1.1）

其中 0(xi), 1(xi), p(xi)为相对于xi的未知参数， i,i 1,2, n为独立同分布的随机

误差项。p为事先给定的值。

1.2 相关概念

1.2.1 r次最近邻点

对每一个xi计算周围每一个点xm(m 1,2, ,n)到它的距离，记为dim xi xm。记hi为dim(m 1,2, ,n)中第r个小的值。令0 f 1,为离fn最近的整数值，即

，f称为平滑r fn 。r相当于对数据进行局部回归时所选取的数据的宽度（窗口宽度）

系数。

1.2.2局部加权回归

对每一个点xi，在窗口内所有的xk上，k 1,2, n，由权值函数可得到权值 k(xi)，使用带有权值 k(xi)的加权最小二乘法对xi进行d阶多项式拟合，得到拟合值yi。利用^ k(xi)得到yi就称为局部加权回归。

1.3权函数的确定

对于一系列观测点 xi,yi ,i 1,2,3, ,n,给出一个权值函数W(x)，满足：

(1)x 1时，W(x) 0；^

(2)W( x) W(x)；

(3)对于x 0,W(x)是一个非增函数；(4)当x 1时,W(x) 0.

满足上述条件的函数有很多，目前最常用的是三次权函数

3 (1 x)x 1W(x) 0,x 1 3

还有形如下式的（n,m）型权函数

nm (1 x),x 1 W(x) 0,x 1

除上述两种权函数外还有其他的权函数，如高斯加权函数和正态型权函数。

1.4参数估计

局部加权拟合方法应用于变参数模型（1.1），即对于任意给定的自变量空间的点xi,i 1,2, ,n，求 0(xi), 1(xi), p(xi)使得

(x)[y (x) (x)x ii0i1ii

i 1np(xi)xip]2

达到最小

令

1x1 1x2X 1xn

而 0(x) y1 x1p (x) y x2p 12 ，Y ， (x) (x)y xnp n p

W(x) diag[w1(x),w2(x), ,wn(x)]

为对角矩阵，则由加权最小二乘理论可知x点处的参数向量 (x)的估计值为：

(x) ( 0(x), 1(x), p(x)) [X W(x)X] 1X W(x)Y

这里假设对任意的x，[X W(x)X] 1均存在。因变量在x处的拟合值为 ^^^^

y(x) 0(x) 1(x)x p(x)xp

1.5 强局部加权回归

在局部加权回归中对每一个点xi，在窗口内所有的xk上，k 1,2, n，由权值函数可得到权值 k(xi)，使用带有权值 k(xi)的加权最小二乘法对xi进行d阶多项式拟合，得到拟合值yi。然后在每个观测点{xi,yi}，根据残差yi yi确定 i值，当残差较大时取较小的 i，当残差较小时取较大的 i。再利用 i k(xi)代替原来的 k(xi)计算得到新的拟合值。重复进行多次得到最后的拟合值yi。利用 k(xi)和 i k(xi)进行多次迭代得到yi就称为强局部加权回归。 ^^^^^^^^

2 强局部加权回归算法实施流程

2.1 算法实施流程

,1（1）选取适当的f，对每一个观测点xi，（i 2 n）尽量以xi为中心选取窗口宽度。

（2）定义区间内所有点的权数。权数由权值函数来确定。

（3）利用最小二乘法对每个带有权值 k(xi)的观测点(xi,yi)，计算回归系数 (xi)的估计值，此时得到的yi为在xi处的拟合值。 ^

y(xi) 0(xi) 1(xi)xi p(xi)xip，i 1,2, n。

（4）令B由式定义的4次方权值函数 ^^^^

(1 z2)2z 1 B(z) z 1 0

并令ei yi yi为拟合值的残差，S为ei的中位值。定义： ^

k B(ek/(6S))

（5）对每一个i在{xi,yi}点处用 i k(xi)代替原来的权值 k(xi)，利用最小二乘法进行d阶多项式拟合，计算新的yi。

（6）重复执行（4）、（5）R次，最后得到的yi就是强局部加权拟合值。

一般来说，利用强局部加权回归算法对观测点进行拟合时，多项式的阶数、权值函数、迭代次数以及窗口宽度是很重要的，但是前三个参数是可以预先给出来的。正常情况下，多项式阶数取1，迭代次数取2，权值函数取3次方权值函数已经足够。f是参加局部回归的观测值的个数占观测值个数的比例，一般来说f的取值在1/3到2/3之n是观测值的个数，

间。本文我们选取f 0.5。r 与f 的取值一般没有确定的准则,其大小会影响平滑值的外观。 增大r 或f 值,将会导致平滑程度的增加, 而对于数据中潜在的细微变化模式则分辨率低, 但噪音小。而对数据中大的变化模式的表现则比较好; 而小的r 或f值, 则会使曲线非常粗糙。对于数据中潜在的细微的变化模式的分辨率则较高, 但噪音大。 对数据中大的变化模式的表现就比较差。 ^^

2.2算法的程序实现

由于强加权局部最小二乘法中，大量运用了矩阵运算，比如矩阵的加减乘除、矩阵的迹，矩阵的转置和秩，以及求取矩阵的特征值特征向量，所以从网 …… 此处隐藏：3362字，全部文档内容请下载后查看。喜欢就下载吧 ……