迭代求解方法

迭代求解方法#

最小角回归#

最小角回归（Least Angle Regression，简称LARS）是一种用于线性回归和特征选择的迭代算法。它通过一系列步骤逐渐构建回归模型，并根据变量与目标变量之间的相关性来选择特征。

LARS算法的主要思想是每次选择与目标变量具有最大相关性的特征，并沿着该方向移动。在每个步骤中，LARS将当前的解投影到残差向量上，然后确定一个新变量进入解集，并决定如何移动。

残差：实际观测值与模型预测值之间的差异 \(y - ŷ\)

算法步骤：

初始化：设置所有系数\(β\)为\(0\)，残差\(r\)为\(y\)，其中\(y\)是目标变量。
在每一步中重复以下步骤：
- a. 计算预测变量\(x\)与残差\(r\)的相关性，选择与残差最相关的变量作为当前活动变量。
- b. 沿着与当前活动变量的相关方向移动，更新系数\(β\)。
- c. 更新残差\(r\)。
重复步骤2直到达到所需的特征数量或满足其他停止准则（例如残差最小化，交叉验证等）。

以下是LARS算法的伪代码表示：

输入：特征矩阵X，目标变量向量y
输出：系数估计值β
初始化：\(β = 0, r = y\)
while (某个停止准则未被满足) do:
- 计算与残差\(r\)的相关性：\(c = X^T * r\)
- 选择与残差最相关的特征：\(j = argmax(|c|)\)
- 选择\(j\)对应的特征向量：\(x_j = X[:, j]\)
- 计算沿着\(x_j\)方向的步长：\(s = X^T * (r - X * β) / (n * ||x_j - X * β||_2)\)
- 更新系数：\(β = β + s * x_j\)
- 更新残差：\(r = y - X * β\)
其中，\(X\)是特征矩阵，\(y\)是目标变量向量，\(β\)是系数估计值，\(r\)是残差，\(n\)是样本数量。\(||.||_2\)表示\(L2\)范数。

LARS算法可以用于拟合线性回归模型并进行特征选择。它能够处理高维数据集，同时具有较低的计算复杂度。

其主要的优点有：

特别适合于特征维度n 远高于样本数m的情况。
算法的最坏计算复杂度和最小二乘法类似，但是其计算速度几乎和前向选择算法一样
可以产生分段线性结果的完整路径，这在模型的交叉验证中极为有用。

主要的缺点是：

由于LARS的迭代方向是根据目标的残差而定，所以该算法对样本的噪声极为敏感。

在Scikit-learn中，你可以使用Lars类来实现最小角回归。例如：

from sklearn.linear_model import Lars
import numpy as np

# 生成样本数据
np.random.seed(0)
n_samples, n_features = 100, 10
X = np.random.randn(n_samples, n_features)
Y = np.random.randn(n_samples, 5)  # 生成5个相关联的目标变量

# 创建Lars对象并进行拟合
lars = Lars()
lars.fit(X, y)

# 输出模型系数
print("模型系数：")
print(lars.coef_)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[1], line 12
     10 # 创建Lars对象并进行拟合
     11 lars = Lars()
---> 12 lars.fit(X, y)
     14 # 输出模型系数
     15 print("模型系数：")

NameError: name 'y' is not defined

LARS Lasso#

LARS Lasso（Least Angle Regression Lasso）是一种结合了最小角回归（LARS）和Lasso回归的正则化方法。

与传统的LASSO回归相比，LARS Lasso具有更高的计算效率，因为它使用了逐步向前的方式来确定特征的顺序，而不需要像坐标下降或拟梯度等方法那样进行迭代优化。

在Scikit-learn中，你可以使用LassoLars类来实现LARS Lasso回归。以下是一个示例代码：

from sklearn.linear_model import LassoLars

# 创建LassoLars对象并进行拟合
lasso_lars = LassoLars(alpha=0.1)
lasso_lars.fit(X, y)

# 输出模型系数
print("模型系数：")
print(lasso_lars.coef_)

模型系数：
[ 0.          0.          0.          0.21248063 -0.00992147  0.
  0.00512876  0.          0.00215299 -0.00265399]

正交匹配追踪法#

正交匹配追踪法（Orthogonal Matching Pursuit，简称OMP）是一种用于稀疏信号恢复和特征选择的迭代算法。它通过逐步选择与残差具有最大相关性的原子（基向量），并将其投影到残差上，以逐步逼近原始信号或寻找最佳特征子集。

这个算法通过k次迭代来逼近目标信号的稀疏表示，每一次迭代都选择与当前残差具有最大相关性的原子，并将其加入到稀疏表示中。然后更新残差，并继续循环，直到达到所需的稀疏度\(k\)。

以下是OMP算法的基本步骤：#

输入：测量矩阵\(X\)（大小为\(m × n\)），观测向量\(y\)（长度为\(m\)），稀疏度\(k\)
输出：稀疏表示向量\(β\)（长度为\(n\)）
初始化：设置估计稀疏表示向量\(β\)为零，并设置残差\(r\)为\(y\)。
重复以下步骤\(k\)次：
- a. 计算原子与残差的相关性：\(c = X^T * r\)
- b. 选择与残差具有最大相关性的原子：\(j = argmax(|c|)\)
- c. 将该原子加入到稀疏表示中：\(β[j] = β[j] + c[j]\)
- d. 更新残差：\(r = r - X[:, j] * c[j]\)
返回稀疏表示向量\(β\)。

其中，\(X^T\)是\(X\)的转置，\(|c|\)表示\(c\)的绝对值。

OMP与LARS类似，但在每一步中仅选择一个原子，因此结果可能是非稀疏的。

OMP算法可以用于恢复稀疏信号、特征选择和压缩感知等领域。它是一种简单而高效的迭代算法，适用于处理高维数据和大规模问题。

在Python中，你可以使用sklearn.linear_model.OrthogonalMatchingPursuit类来实现OMP算法。以下是一个示例代码：

from sklearn.linear_model import OrthogonalMatchingPursuit

# 创建OrthogonalMatchingPursuit对象并进行拟合
omp = OrthogonalMatchingPursuit(n_nonzero_coefs=5)  # 设置估计系数的非零数量
omp.fit(X, y)

# 输出模型系数
print("模型系数：")
print(omp.coef_)

模型系数：
[ 0.          0.          0.          0.30219523 -0.13606972 -0.10775375
  0.          0.          0.09119663 -0.11162544]