基于Sinc函数的回归算法
Sinc Function-Based Regression Algorithm

作者: 陈 董 * , 于永斌 , 郭雨欣 , 王承韬 , Nyima Tashi :电子科技大学信息与软件工程学院,四川 成都;

关键词: Sinc线性回归逻辑回归Sinc Linear Regression Logistic Regression

摘要:
本文引入采样定理中离散信号的重构思想,提出基于Sinc函数的线性与逻辑回归模型及其算法。为使回归函数的均方误差最小化,在数据的自变量域中设计出Sinc函数,然后直接重构出回归曲线。在基于Sinc函数的线性与逻辑回归模型推导与算法分析基础上,进行了充分的仿真实验验证。与传统线性回归相比,基于Sinc的回归算法在回归函数关系不明显时具有明显优势。最后,将基于Sinc的线性回归算法成功用于月最低气温预测。

Abstract: In this paper, the reconstruction of discrete signals in sampling theorem is introduced, and a linear and logistic regression model based on Sinc function is proposed. In order to minimize the mean square error of the regression function, Sinc function is designed in the independent variable do-main of data, and then the regression curve is reconstructed directly. On the basis of the linear and logistic regression model based on Sinc function and the algorithm analysis, a sufficient simulation experiment is carried out. And compared with the traditional linear regression, regression algorithm based on Sinc function has obvious advantages when the regression function is not obvious. Finally, the linear regression algorithm based on Sinc function is succeeding to predict the monthly minimum temperature.

1. 引言

回归分析(regression analysis)是一种确定两种或两种以上变量间相互依赖关系的统计分析方法。回归分析按照涉及变量的多少,分为一元回归和多元回归分析;按照自变量和因变量之间的关系类型,可分为线性回归分析和非线性回归分析。如果回归模型的因变量和自变量是非线性函数形式,回归规律在图形上表现为形态各异的各种曲线,称为非线性回归 [1] 。回归分析已广泛应用于社会,经济,工程,医学,卫生,农业,气象和水文 [2] 。

非线性函数的求解一般有两种情况:非线性可变换成线性和不可变换成线性。处理可线性化的非线性回归的基本方法是,通过变量变换,将非线性回归化为线性回归,然后用线性回归方法处理。这种处理方式需要根据理论或经验、已获得输出变量与输入变量之间的非线性表达式、输入输出的n次观察结果来确定系数的值 [3] 。

本文针对一元非线性可变换成线性的回归问题中存在的需要根据经验进行变量带换、求表达式系数需要训练、较复杂回归方程中因变量和自变量函数关系不易得出的问题,通过引入采样定理中离散信号的重构思想,提出基于Sinc函数的回归算法。在信号处理领域,Sinc滤波器是一种理想的电子滤波器,可消除给定带宽的信号分量,仅保留低频信号 [4] 。由于具有无限延迟的理想Sinc滤波器(称为矩形滤波器),现实世界中的滤波器只是其近似值之一。但它在概念验证和论证验证中仍然被广泛应用,如采样定理和Whittaker-Shannon插值公式 [5] 。该算法引入数字信号处理中时域重构原理,首先根据数据集找到自变量间的最小间隔,使得数据集对应所要拟合的函数呈现过采样,再基于局部线性回归模型的思想(详细介绍见 [6] ),通过在每个数据点求解一个单独的最小二乘问题来逼近目标函数 [7] 。最后根据数据的最小间隔对应的Sinc函数进行时域重构,得出使代价函数最小的回归曲线。基于相同思想,本文进一步提出该算法在逻辑回归算法中的应用。最后,考虑到算法只能在数据范围内预测的局限性,本文将基于Sinc的线性回归算法应用于月最低温度预测。

2. 回归模型

我们做出如下假设:

假设I:所要求得的回归曲线可以通过低通滤波获得其频域的主频范围。由数字信号处理的相关知识可知,时限信号的频域不可能为带限信号,即由目标函数采样而来的数据集在频域无绝对带宽。又考虑到一般要求得到的回归函数的泛化能力,回归函数应为较简单曲线,所以目标函数频域的主频范围可通过低通滤波获得。

假设II:数据集足够大。这里数据集足够大是指对于自变量的最小值 x 0 ,每个间隔点上 x 0 + n T (其中T为自变量最小间隔, )都存在数据点。

2.1. 基于Sinc的线性回归

2.1.1. 代价函数最小化

定义 x ( k ) ( k = 0 , 1 , m ) 为第k个自变量的值,且满足 x ( k ) = x ( 1 ) + ( k 1 ) T 。假定 x ( k ) 上有p个数据点

x ( k ) 上的代价函数为:

J ( θ ) k = 1 p i = 1 p 1 2 ( h θ ( x ( k ) ) y k ( i ) ) 2 (1)

1) 中 h θ ( x ( k ) ) 表示最终的回归函数在 x ( k ) 上对应因变量的值。

d J ( θ ) k d h θ ( x ( k ) ) = 1 p i = 1 p ( h θ ( x ( k ) ) y k ( i ) ) = h θ ( x ( k ) ) i = 1 p y k ( i ) p = 0 h θ ( x ( k ) ) = i = 1 p y k ( i ) p = y k (2)

由(2)可知,当回归函数经过每一个自变量 x ( k ) 上数据的平均值点时,该点处代价函数将最小。又因为总的代价函数为每个自变量点上代价函数的加和,所以当回归函数经过每个自变量上因变量的均值点时,总的代价函数达到最小。

这里,我们称使代价函数最小的每个自变量上的点成为最优点,用 x [ n ] 表示:

x [ n ] = y k ( n = k = 1 , 2 , 3 , ) (3)

我们称经过最优点的回归曲线(函数)为最优曲线(最优函数),用 f ( x ) 表示。

2.1.2. 基于低通滤波的时域重构

为了方便用数字信号处理知识进行相关推导,我们在此用t代替自变量x,用 Ω 表示其对应频域变量。

F的傅里叶变换为:

F ( f ) = e 2 π j ( x Ω ) f ( x ) d x (4)

T s 表示数据集中自变量t间的最小间隔, x a ( t ) 为最优曲线 f ( x ) 的原函数。

为了方便表述,以下用带限信号举例(非带限信号整个过程不变)。

下图为最优曲线采样时,时域与频域的变换情况,其中A、B、C表示时域,a、b、c表示频域,且C中采样后的时域数据即为由数据集得来的最优点。

图1中B到C的采样过程:

δ T ( t ) = n = δ ( t n T ) (5)

x d ( t ) = x a ( t ) δ T ( t ) = n = x a ( n T ) δ ( t n T ) (6)

由于时域离散化,对应频域周期化,所以频域对应b到c变化:

Figure 1. Sampling process

图1. 最优曲线的采样过程中时域、频域变化情况

X d ( j Ω ) = 1 T s k = X a ( j ( Ω k Ω 0 ) ) (7)

在c的基础上,经过低通滤波,可以得到最优函数频域的主频频范围。在假设I和假设II的前提下,

Ω s 2 可以包含最优函数频域的主频范围。低通滤波器的频域表达式如下:

H r ( j Ω ) = { T , | Ω | Ω s / 2 0 , | Ω | > Ω s / 2

Ω s 2 = π T s

上述低通滤波的过程,在频域表现为: X d ( j Ω ) × H r ( j Ω ) . 对应如图2。。

则对应时域为:

x a ( t ) = x d ( t ) h r ( t ) = n = x a ( n T s ) h r ( t n T s ) = n = x [ n ] h r ( t n T s ) (8)

其中:

h r ( t ) = 1 H r ( j Ω ) e j Ω t d Ω = T Ω s / 2 Ω s / 2 e j Ω t d Ω = sin ( Ω s t / 2 ) Ω s t / 2 , t (9)

图1流程,在我们假定A中最优曲线存在的前提下,可以由数据集与公式(2)得到C中各个最优点。此时要求得时域原函数只需根据数据自变量间最小间隔 T s 对应的Sinc函数(Sinc函数图形如图4)进行时域重构。重构后的时域图像如图3

Figure 2. Obtain the frequency domain function by the low pass filter

图2. 由低通滤波获得主频范围

Figure 3. Time domain reconstruction

图3. 时域重构

Figure 4. Sinc

图4. Sinc

2.1.3. 基于DTFT基本公式的时域重构

更纯粹的公式推导如下:

x a ( t ) 的正反傅里叶变换:

X a ( j Ω ) = t = x a ( t ) e ( j Ω t ) d t x a ( t ) = 1 Ω = X ( Ω ) e ( j Ω t ) d Ω = 1 Ω = Ω 0 Ω 0 X ( Ω ) e ( j Ω t ) d Ω (10)

x[n]的正反DTFT变换:

X ( ω ) = n = x [ n ] e ( j ω n ) x [ n ] = 1 ω = π π X ( ω ) e ( j ω n ) d ω (11)

其中 ω = Ω T s

假定 X a ( j Ω ) = X ( ω ) .

x [ n ] = 1 ω = π π X ( ω ) e ( j ω n ) d ω = 1 ω = π π X ( Ω ) e ( j Ω T s ) d Ω T s = T s x ( n T s ) (12)

X ( ω ) = X a ( j Ω ) T s .

x a ( t ) = 1 Ω = X ( Ω ) e ( j Ω t ) d Ω = T s ω = π π X ( ω ) e ( j ω t T s ) d ω T s = T s ω = π π ( n = x [ n ] e ( j ω n ) ) e ( j ω t T s ) d ω T s = T s 2 π n = x [ n ] ( ω = π π e ( j ω n ) e ( j ω t T s ) d ω T s ) = n = x [ n ] sin ( ( t n T s ) π T s ) ( t n T s ) π T s = n = x [ n ] h r ( t ) (13)

可以看出由DTFT推导的时域重构结果与低通滤波原理的时域重构结果相同,且在由数据集经量化等处理过程后,在仅知道最小数据间隔 T s 的情况下,就可以求出使代价函数最小的回归函数。

2.1.4. 基于Sinc函数的线性回归算法步骤

基于Sinc函数的线性回归算法沿用传统的代价函数公式(1),但不再进行自变量与因变量形式的代换,也不再训练自变量前的系数。其算法的具体步骤如下:

输入:数据矩阵 x 1 × a ,其中a代表a个数据; y 1 × a

输出:因变量预测值 y .

算法步骤:

对x操作,适当量化,求出尽可能小的自变量间隔,放入T,同时将不同自变量按间隔以从小到大顺序放入 x 1 × N ,这里假定在间隔T时,有N个不同自变量。

根据 x 1 × N ,将y变为 y m × N ,其中m代表每个不同自变量上m个因变量的值。

1) 求出每个自变量上的最优点,对y做如下操作:

for i = 1:N

y m × N 第i列加和除以m,放入x[i]中

end for。

2) 将T带入公式(9)求出相应Sinc函数。

3) 最优点分别与4)中所得Sinc函数相乘并累加,得y。

4) 算法结束。

时间复杂度:

T ( n ) = O ( a + N ) (14)

2.2. 基于Sinc的逻辑回归

2.2.1. 旋转

为了方便陈述基于Sinc函数的逻辑回归算法思想,以二分类问题为例,且令每个自变量上,两类因变量个数相当。当不满足该条件时,对数据集进行适当旋转,以使数据集尽量满足该条件。以图5图6为例。

2.2.2. 代价函数最小化

C o s t ( h θ ( x ) , y ) = { log ( 1 h θ ( x ) ) , if y = 0 log ( h θ ( x ) ) , if y = 1 (15)

Figure 5. Admission data [8]

图5. 入学成绩数据 [8]

Figure 6. Data rotated 60˚

图6. 逆时针旋转60˚

h θ ( x ) = sigmoid ( z ) = 1 1 + e z z = W T X (16)

从公式(15)可以看出,当 y = 1 h θ ( x ) 越接近1,代价函数越小;当时, h θ ( x ) 越接近0代价函数越小。

图7可以看出,z越大h越大,为了使z尽可能的大,应满足当z = 0时,数据点尽可能的远离 z = f ( x 1 , x 2 ) 在x1Ox2上的投影。这里我们称该投影为边界函数,其中 x 1 , x 2 分别表示两种自变量。

2.2.3. 确定边界函数

为了使用和线性回归相同的原理,我们需要找到使代价函数最小的边界函数上的点 x 0 k 。当 x 1 i 被确定, x 0 k 表示 x 2 i 的数值。

假设当 x 1 ( i ) = x 1 ( k ) ( k = 0 , 1 , , m ) 时,有p个 x 2 i x 1 k 上,其中m表示满足假设Ⅰ的 x 1 个数。

对每个 x 1 k ,我们应当使得所有 x 2 i 离边界函数尽可能的远。所以定义如下距离函数:

distince k = i = 1 p ( x 2 i x 0 k ) 2 (17)

我们需要使每一类数据公式(17)的值尽可能的大,又由于每个 x 1 i 上有两类数据,可得图8

图中蓝色的线代表y = 0的距离函数值随 x 0 k 的变化情况,橘色线代表y = 1的距离函数值随 x 0 k 变化的情况;实线之外代表不存在数据点的部分,红色点和绿色点仅表示曲线的趋势;红色“x”表示y = 0的数据的 x 2 x 1 k 上的均值;绿色“x”表示y = 1的数据的 x 2 x 1 k 上的均值。

当y = 0的一部分 x 2 i 大于 x 0 k 时,它们将对距离函数值做负贡献;同样,当y = 1的一部分 x 2 i 小于 x 0 k 时,它们也将对距离函数值做负贡献。假设一共有q个做出负贡献的点,我们可以得到如下新的距离函数:

Figure 7. Sigmoid function

图7. Sigmoid函数

Figure 8. Distance function

图8. 距离函数

distince k = i = 1 p q ( x 2 i x 0 k ) 2 j = 1 q ( x 2 i x 0 k ) 2 (18)

对于此处讨论的逻辑回归问题,由于之前假定y = 0与y = 1在每个 x 1 上个数相当。在求 x 0 k 时,我们令两类距离函数值相等。

i = 1 p 2 ( x 2 1 i x 0 k ) 2 = j = 1 p 1 ( x 2 0 j x 0 k ) 2 x 0 k = ( 2 x 0 ¯ p 1 2 x 1 ¯ p 2 ) ± ( 2 x 0 ¯ p 1 2 x 1 ¯ p 2 ) 2 4 ( p 1 p 2 ) N 2 ( p 1 p 2 ) x 0 ¯ = j = 1 p 1 x 2 0 j p 1 x 1 ¯ = i = 1 p 2 x 2 1 i p 2 N = j = 1 p 1 ( x 2 0 j ) 2 i = 1 p 2 ( x 2 1 i ) 2 (19)

其中 x 2 0 i 代表y = 0的数据, x 2 1 i 代表y = 1的数据。

2.2.4. 基于Sinc函数的逻辑回归算法步骤

基于Sinc的逻辑回归算法关键在于找到使代价函数最小的边界函数上的点,再对这些点进行“时域重构”。其算法的具体步骤如下:

输入:数据矩阵 x 2 × a ,其中a代表a个数据, x 2 × a 为一个2 × a大小的矩阵,每一行为一个自变量,两个自变量分别表示为x1、x2 y 1 × a

输出:因变量预测值边界函数。

算法步骤:

1) 对 x 2 × a 进行旋转操作,使得每个 x 1 上两类 x 2 数量尽可能相当。

2) 对 x 1 操作,适当量化,求出尽可能小的自变量间隔,放入T,同时将不同自变量按间隔以从小到大顺序放入 x 1 1 × N ,这里假定在间隔T时,有N个不同自变量 x 1

3) 根据 x 1 1 × N ,将 x 2 变为 x 2 m × N ,其中m代表每个不同自变量上m个 x 2 的值。

4) 求出每个 x 1 上的边界函数上的点,对 x 2 做如下操作:

for i = 1:N

x 2 m × N 第i列加和除以m,放入x[i]中

end for。

5) 将T带入公式(9)求出相应Sinc函数。

6) 最优点分别与4)中所得Sinc函数相乘并累加,得边界函数。

7) 算法结束。

时间复杂度与基于Sinc的线性回归基本相当在不考虑旋转等步骤的情况下,可以近似为 T ( n ) = O ( a + k )

3. 仿真实验

3.1. 线性回归仿真与对比

定义 为回归的目标曲线, 按正态分布在每个自变量上随机生成30个点,按间距0.5在[0:50]范围内生成3000个数据点。数据图9如下:

基于Sinc的线性回归生成如图10曲线。

Figure 9. Generate data

图9. 生成数据

Figure 10. Sinc linear regression

图10. 基于Sinc的回归

使用相同分布,按间隔0.7生成测试集数据对回归函数进行检验。

与传统线性回归进行对比。首先进行变量代换,令 x = x 。按线性做法,使用梯度下降法进行训练,令学习率为0.01,迭代次数为10,得回归曲线,后用同样测试集进行测试。

两种算法测试集代价函数值与运行时间,见下表1

对比图11图12可知,传统线性回归所求的函数泛化能力更强,同时由表1可知,对于 y = x 两种算法性能基本相同。但本实验可以由数据明显看出自变量与因变量的关系,进而进行变量代换,当这种关系不明显时基于Sinc的回归将具有明显优势。但同时应注意到基于Sinc的回归只能在数据范围内进行预测。

3.2. 逻辑回归仿真

围绕 y = x y = x + 6 在[0:50]上以间隔0.5,按正太分布随机生成3000个点,每个x上总共生成30个点。

Table 1. The comparison of two algorithms

表1. 两种算法对比

Figure 11. Sinc linear regression test

图11. 基于Sinc的回归测试

Figure 12. Traditional linear regression

图12. 传统线性回归

按照基于Sinc的逻辑回归算法找到最优的边界曲线上的点,如下图13黄色的“x”。

边界点乘以对应的边界函数得下图14

可以看出基于Sinc的逻辑回归算法可以较好的解决数据数量分布相当的线性可分的二分类问题。

Figure 13. Generate data

图13. 数据生成

Figure 14. Sinc logistic regression

图14. 逻辑回归边界函数

4. 基于Sinc的回归算法的气候预测

由以上过程可知基于Sinc函数的线性回归适合对周期性数据进行预测。而天文气候类数据正好符合(如年太阳黑子活动时间,月降水量等)。我们从NOAA拿到BIJIE从1952年到2016年的月最低气温(TMIN)数据,将数据按时间分布排列,如图15

图16中,使用历年2月、4月、6月、8月、10月12月数据为样本数据,对3月、5月、7月、9月、11月的最低温度进行预测。代价函数值为7.26322704418。

Figure 15. Months minimum temperature of 732 data

图15. BIJIE月最低温度的732条数据

Figure 16. TMIN of BIJIE based on Sinc linear regression

图16. 基于Sinc的线性回归的BIJIE TMIN预测

5. 结论

本文研究基于Sinc函数的线性与逻辑回归算法,主要工作归纳如下。

1) 在采样定理中离散信号的重构思想启示下,最小化回归函数的均方误差,在数据的自变量域中设计出Sinc函数,然后直接重构出回归曲线;

2) 通过理论推导、算法分析与仿真实验,提出基于Sinc函数的线性与逻辑回归模型及其算法;

3) 将基于Sinc的线性回归算法成功用于月最低气温预测。

致 谢

这项工作由中国国家自然科学基金国际青年科学家基金(NSFC Grant No. 61550110248)和西藏自治区重点科研项目(批准号:Z2014A18G2-13)资助。同时,作者要感谢编辑和审稿人的认真负责。

文章引用: 陈 董 , 于永斌 , 郭雨欣 , 王承韬 , Nyima Tashi (2018) 基于Sinc函数的回归算法。 计算机科学与应用, 8, 339-353. doi: 10.12677/CSA.2018.83039

参考文献

[1] Yahia, M., Hamrouni, T.-A. and Abdelfattah, R. (2017) Infinite Number of Looks Prediction in SAR Filtering by Linear Regression. IEEE Geoscience & Remote Sensing Letters, 14, 2205-2209.
https://doi.org/10.1109/LGRS.2017.2749322

[2] Watts, B. 非线性回归分析及其应用[M]. 北京: 中国统计出版社, 1998.

[3] 徐全智, 吕恕. 概率论与数理统计[M]. 第二版. 北京: 高等教育出版社, 2010: 201-202.

[4] Dooley, S.R. and Nandi, A.K. (2000) Notes on the Interpolation of Discrete Periodic Signals Using Sinc Function Related Approaches. IEEE Transactions on Signal Processing, 48, 1201-1203.
https://doi.org/10.1109/78.827555

[5] Schanze, T. (1995) Sinc Interpolation of Discrete Periodic Signals. IEEE Transactions on Signal Processing, 43, 1502-1503.
https://doi.org/10.1109/78.388863

[6] Hastie, T., Tibshirani, R. and Friedman, J. (2009) The Elements of Statistical Learning. 2nd Edition, Springer, New York.

[7] Cervellera, C. and Macciò, D. (2014) Local Linear Regression for Function Learning: An Analysis Based on Sample Discrepancy. IEEE Transactions on Neural Networks & Learning Systems, 25, 2086-2098.
https://doi.org/10.1109/TNNLS.2014.2305193

[8] Ng, A. (2017) Machine Learning.
https://www.coursera.org/learn/machine-learning

分享
Top